§ 23. Понятие правильности и сложности алгоритма

23.1. Сложность алгоритма

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

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

Емкостная сложность в худшем случае — функция от размера входа, равная максимальному количеству памяти, к которому было обращение при решении задач данного размера.

При анализе сложности для класса задач определяется некоторое число, характеризующее объем данных, которое требуется для представления входных данных задачи. Это величина называется  размер входа. Можно сделать вывод, что сложность алгоритма — функция размера входа. Размер входа может зависеть как от числа входных данных, так и от величины входных данных (пример 23.1).

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

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

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

Чтобы определить сверху трудоемкость алгоритма, используется обозначение O, читается «о большое» (пример 23.2).

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

Существует ряд важных практических причин для анализа алгоритмов. Одной из них является необходимость получения оценок или границ для объема памяти, или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память — относительно дефицитные (и дорогие) ресурсы, на которые часто одновременно претендуют многие пользователи. Всегда следует избегать прогонов программы, отвергаемых системой из-за нехватки запрошенного времени. Теоретический анализ способен выявить узкие места в программах. 

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

Будем пользоваться следующим критерием для оценки качества алгоритма: чем медленнее растет функция f(n) на каком-то участке области , тем алгоритм будет более эффективным (пример 23.3).

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

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

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

Пример 23.1. Оценка сложности поисковых алгоритмов.

Линейный поиск

Нахождение информации в неотсортированной структуре данных, например в массиве, требует применения последовательного поиска. Последовательный поиск в среднем случае выполнит проверку n/2 элементов, а в худшем —  элементов. При этом предполагается, что сравнение двух чисел выполняется за 1 операцию.

Бинарный поиск

Этот метод поиска значительно эффективнее, чем последовательный поиск, но требует, чтобы данные были предварительно упорядочены (отсортированы). В худшем случае выполняется не более log2n, в связи с чем метод еще называется логарифмическим поиском.

Пусть n — размер входных данных. Оценка сложности алгоритма f(n) = 0(g(n)), если при g  > 0 и n  > 0 существуют такие положительные C, n0, что f(n0) ≤ C * g(n0) .

Другими словами, скорость роста функции f при достаточно больших n  не выше скорости роста функции g.

Пример 23.2.

Оценка сложности алгоритмов сортировки.

Для метода сортировки обменом оценка трудоемкости составляет — O(n2). Это означает, что количество операций при сортировке  элементов не превосходит величину C · n2 при некотором значении коэффициента C, который не зависит от n.

Для быстрой сортировки оценка трудоемкости составляет в среднем — O(nlog2n).  Это означает, что количество операций при сортировке  элементов не превосходит величину C · nlog2n при некотором значении коэффициента C, который не зависит от n. Оценка в худшем случае такая же, как для сортировки обменом.

Пусть  — размер входных данных. Оценка сложности алгоритма

f(n) =   (g(n)),

если при g > 0 и n > 0 существуют такие положительные c, n0, что

f(n0) ≥  c * g(n0),.

Другими словами, скорость роста функции f при достаточно больших  не ниже скорости роста функции g.

Пример 23.3. Возможные оценки качества алгоритма.

Константный алгоритм —  O(1)

Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени. Важно то, что это время не зависит от входных данных.

Линейный алгоритм — O(n)

Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива. Если линейный алгоритм обрабатывает один элемент пять миллисекунд, то мы можем ожидать, что тысячу элементов он обработает за пять секунд. Например, линейный поиск.

Логарифмический алгоритм — O(logn)

Порядок роста O(logn) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. При анализе алгоритмов по умолчанию используется логарифм по основанию 2. Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность. Например, бинарный поиск.

Линейно-логарифмический алгоритм — O(nlogn)   

Линейно-логарифмический алгоритм имеет порядок роста O(nlogn). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию. Например, быстрая сортировка (в среднем) или метод  sort   в STL.

Квадратичный алгоритм — O(n2)

Время работы алгоритма с порядком роста O(n2)  зависит от квадрата размера входных данных. Например, если массив из тысячи элементов потребует 1 000 000 операций, то массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года. Например, сортировка обменом.

Полиномиальный алгоритм — O(nk)

О полиномиальной сложности (порядка k) говорят тогда, когда время работы алгоритма растет не быстрее, чем полином k-й степени от n.

Экспоненциальный алгоритм —  O(2n), O(en),  O(nn) и др.

Если время работы алгоритма растет не медленнее, чем экспонента от n, то говорят об экспоненциальном алгоритме.