Разница между сложностью времени и временем выполнения

Question

Просто интересно, если в вопросе идет речь о времени выполнения алгоритма, означает ли это то же самое, что и сложность времени, или есть какая-то разница между ними?

Answer 1

Время выполнения - это время, необходимое для запуска программы.Временная сложность - это описание асимптотического поведения времени выполнения, так как размер ввода стремится к бесконечности.

Вы можете сказать, что время выполнения "равно" O (n ^ 2) или как угодно, потому что это идиоматический способописать классы сложности и обозначения Big-O.На самом деле время выполнения - это не класс сложности, это либо продолжительность, либо функция, которая дает вам продолжительность.«Быть ​​O (n ^ 2)» является математическим свойством этой функции, а не ее полной характеристикой.Точное время работы может составлять 2036 * n ^ 2 + 17453 * n + 18464 тактов ЦП или что-то еще.Не то чтобы вам очень часто нужно было знать это настолько подробно, и в любом случае это вполне может зависеть от фактического ввода, а также от размера ввода.

Answer 2

Сложность и время выполнения - это две разные вещи.

Сложность времени - это полная теоретическая концепция, относящаяся к алгоритмам, в то время как время выполнения - это время, которое займет код для выполнения, а вовсе не теоретическое.

Два алгоритма могут иметь одинаковую сложность по времени, скажем, O (n ^ 2), но один может занять вдвое больше времени работы, чем другой.

Answer 3

«Время выполнения» относится к рассматриваемому алгоритму:

Другой алгоритм может решить ту же самую проблему асимптотически быстрее, то есть с меньшим временем выполнения.

«Сложность времени», с другой стороны, присуща рассматриваемой проблеме . Он определяется как наименьшее время работы любого алгоритма, решающего указанную проблему.

То же самое различие применяется к другим мерам алгоритмической стоимости, таким как память, количество процессоров, объем связи и т. Д.

(теорема Блюма об ускорении показывает, что «наименьшее» время может быть вообще недостижимым ...)

Answer 4

С CLRS 2.2 стр. 25

Время работы алгоритма на конкретном входе - это число выполнено примитивных операций или «шагов». Это удобно определить понятие шага так, чтобы оно было таким же независимым от машины, как возможно.

Теперь из Википедия

... временная сложность алгоритма определяет количество времени, затраченного алгоритмом на выполнение, как функцию длины строки представляющий ввод.

Сложность времени обычно оценивается путем подсчета количества элементарные операции , выполняемые по алгоритму, где элементарные Операция занимает фиксированное количество времени для выполнения.

Обратите внимание, что оба описания подчеркивают отношение размера ввода к числу примитивных / элементарных операций.

Полагаю, из этого ясно, что оба относятся к одной и той же концепции.

На практике вы обнаружите, что корпоративный жаргон редко соответствует академической терминологии, например, тонны людей работают над оптимизацией кода, но редко решают проблем оптимизации .

Answer 5

Для анализа алгоритма необходимо определить количество ресурсов (таких как время и память), необходимых для его выполнения.Большинство алгоритмов предназначены для работы с входами произвольной длины.Обычно efficiency or running time of an algorithm указывается как функция, связывающая длину ввода с number of steps (time complexity) или местом хранения (сложность пространства).