Время работы алгоритма

Пусть n – размер входа (для задач, где размер входа задаётся несколькими числами, рассуждения будут аналогичны). Определим более точно, что понимать под временем работы алгоритма. Поскольку алгоритм – это ещё не программа для конкретной вычислительной машины, время его работы нельзя измерять, например, в секундах. Обычно под временем работы алгоритма понимают число элементарных операций, которые он выполняет. При этом, если алгоритм записан на каком-то псевдокоде или языке высокого уровня, предполагается, что выполнение одной строки требует не более чем фиксированного числа операций (если, конечно, это не словесное описание каких-то сложных действий).

Примечание. Действуя более формально, мы могли бы записать алгоритм с помощью инструкций предполагаемой вычислительной модели, назначить каждой из них некую стоимость и вывести выражение для стоимости алгоритма. Однако, это достаточно трудоёмко и в большинстве случаев не требуется.

Поскольку почти любой алгоритм содержит ветвления, время его выполнения зависит не только от количества входных данных, но и от самих значений этих данных. В связи с этим записать аналитическую зависимость T(n) невозможно. Для сравнения различных алгоритмов обычно определяют время их выполнения для наихудшего или для среднего случая. Рассмотрим это подробнее.