Вычислительная сложность: различия между версиями

Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных. Например, количество операций алгоритма [[сортировка вставками|сортировки вставками]] значительно меньше в случае, если входные данные уже отсортированы. Чтобы избежать подобных трудностей, рассматривают понятие временной сложности алгоритма ''в худшем случае''.
 
''Временная сложность алгоритма'' (в худшем случае) — это функция от размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных.
 
Аналогично понятию ''временной сложности в худшем случае'' определяется понятие ''временная сложность алгоритма в наилучшем случае''. Также рассматривают понятие ''среднее время работы алгоритма'', то есть [[математическое ожидание]] времени работы алгоритма. Иногда говорят просто: «''Временная сложность алгоритма''» или «''Время работы алгоритма''», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).
Анонимный участник