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

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