Время выполнения в худшем и среднем случае

Существуют алгоритмы, время работы которых зависит только от размера входных данных, но не зависит от самих данных (например, поиск суммы элементов заданного массива). Однако чаще всего для разных входных данных одного и того же размера алгоритм работает разное время. Поэтому говорят о времени выполнения алгоритма в наихудшем случае (т.е. максимальное время выполнения по возможным входным данным) и о времени выполнения в среднем. Время выполнения в среднем можно определить по-разному:

среднее время работы алгоритма по всем возможных вариантам входных данных;

ожидаемое время его работы по всем возможным вариантам входных данных с учетом вероятности их появления

Недостатки есть и у того, и у другого способов:

Первый способ не учитывает, что в реальных задачах данные часто распределены неравномерно.

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

Чаще всего при анализе времени работы алгоритма ограничиваются наихудшим случаем. Причины этого в следующем:

Время выполнения в наихудшем случае обычно найти гораздо проще, чем в среднем.

Зная верхнюю границу, мы можем быть уверены, что алгоритм не будет работать дольше ни на каких входных данных.

Для многих алгоритмов плохие случаи (или близкие к ним) могут происходить очень часто

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

Тем не менее, время выполнения в среднем также иногда анализируют – например, для тех алгоритмов, где оно существенно отличается от наиухудшего, и при этом вероятность появления «плохих» входных данных достаточно мала (алгоритм быстрой сортировки Хоара и др.)

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

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