Временная сложность для разных входных размеров

Question

Я новичок в области компьютерных наук, и в моей книге есть таблица времени, необходимого для вычисления алгоритма в соответствии с размером ввода.Как получаются эти значения фиксированными?Я думал, что это также зависит от машины, где выполняются операции.Например, компьютер 1990 года даже не близок к компьютеру 2018 года с точки зрения эффективности.Я немного смущен.

Темпы роста для различных входных размеров.

Answer 1

Хорошо, я давно пишу код, поэтому я могу ответить на ваш вопрос: сложность времени, которую вы извлекаете, дает представление о том, сколько времени займет ваша программа в худшем случае, и эта сложность предназначена для больших данных, а не для маленьких. Даже если Вы выполняете алгоритм O (n ** 3) на суперкомпьютере и соответствующий ему алгоритм сложности O (n) на вашем персональном компьютере, ваш компьютер может работать намного быстрее на больших данных. Скорость процессора зависит от выбора алгоритма.
надеюсь, это поможет