2. Анализ сложности алгоритмов

2.1. Основы асимптотического анализа

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

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

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

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

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

Существуют и другие виды асимптотических оценок:

• $Ω(𝑓(𝑛))$ («омега большое») – нижняя граница: функция $T(n)$ возрастает не медленнее $f(n)$:

• $Θ(𝑓(𝑛))$ («тета большое») – точная граница (одновременно и верхняя, и нижняя): $T(n)$ растёт с той же скоростью, что и $f(n)$ при больших $n$:

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

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

Некоторые важные свойства асимптотических оценок:

Примеры:

• $5n^2 + n + 2 = O(n^2)$;
• $3n \cdot (2n^2+6) = O(n^3)$;
• $\log_2 n + 5n = O(n)$.

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

Основные классы сложности:

• $O(1)$ – константная;
• $O(\log n)$ – логарифмическая;
• $O(n)$ – линейная;
• $O(n \log n)$ – линейно-логарифмическая;
• $O(n^2)$ – квадратичная;
• $O(n^3)$ – кубическая;
• $O(c^n)$ – экспоненциальная;
• $O(n!)$ – факториальная.

Скорости их роста соотносятся как:

Константная, линейная, квадратичная и кубическая сложности – частные случаи полиномиальной сложности $O(n^k)$, где $k$ – константа. Всякая полиномиальная сложность является более эффективной, чем экспоненциальная и факториальная.

2.2. Случаи

Эффективность алгоритма может зависеть не только от размера входных данных, но и от их характеристик и структуры. Поэтому принято различать:

• Худший случай – данные, при которых алгоритм работает дольше всего;
• Средний случай – математическое ожидание времени выполнения по всем возможным входным данным;
• Лучший случай – наилучшие для алгоритма данные.

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

На примере линейного поиска в массиве (последовательного обхода всех элементов):

• Худший случай: искомого элемента нет или он последний – $𝑂(n)$;
• Лучший случай: элемент стоит первым – $𝑂(1)$;
• Средний случай: элемент равновероятно находится в любой позиции, поэтому в среднем обходится половина массива – $𝑂(n/2)=𝑂(n)$.

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

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

2.3. Примеры анализа сложности

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

В большинстве случаев достаточно руководствоваться следующими эмпирическими правилами:

• Элементарная операция (присваивание, арифметическая или логическая операция, обращение по адресу в памяти) выполняется за постоянное время: $O(1)$.
• Последовательное выполнение блоков: если несколько операций или блоков выполняются один за другим, общая сложность определяется максимальной из них (если блоки не зависят друг от друга): $O(max(f(n), g(n)))$.
• Условный оператор:

if условие:
    блок A
else:
    блок B

Общая сложность равна: O(условие) + max(O(A), O(B)).

• Цикл: O(число итераций × (O(итерации) + O(условия))).
• Сложность вызова функции равна сложности этой функции. Если функция рекурсивная – используется рекуррентный подход.

Пример 1. Условный оператор

if item in array:
    result = True
else:
    result = False

Оператор in выполняет линейный поиск, проходя массив до первого совпадения или до конца. Следовательно, условие выполняется за $O(n)$, где $n$ – длина массива. Основной и альтернативный блок команд – элементарные операции ($O(1)$). Итоговая сложность: $O(n) + max(O(1), O(1)) = O(n)$.

Пример 2. Вложенный цикл со сдвигом счётчика

for i = 0; i < n; i++:
  for k = i; k < n; k += 2:
    # тело цикла

Посчитаем общее количество итераций внутреннего цикла. Для каждого $i$ внутренний цикл выполняется $\lceil (n - i) / 2 \rceil$ раз. Суммарно по $i = 0..(n-1)$ получаем:

Итоговая сложность – $O(n^2)$. Таким образом, шаг счётчика и смещение диапазона (если фиксированы) не влияют на класс сложности – лишь на константу.

Пример 3. Геометрическая прогрессия счётчика

for i = 1; i < n; i *= 2:
  # тело цикла

Здесь счётчик $i$ растёт как степени двойки: $1, 2, 4, 8, ..., 2^k$. Последняя итерация: $2^k < n ⇒ k < \log_2(n)$. Таким образом, итоговая сложность – $O(\log_2(n))$.

Пример 4. Подсчёт частот символов в строке

def count_frequencies(text):
  freq = {}
  for ch in text:
    if ch in freq:
      freq[ch] += 1
    else:
      freq[ch] = 1
  return freq

Переменная freq содержит динамическую структуру словаря. Поэтому чтобы проанализировать сложность алгоритма, необходимо знать детали реализации. В Python словари основаны на хеш-таблицах с константной сложностью выполнения основных операций, тогда сложность алгоритма по времени будет линейной. Т.к. имеются динамически расширяемые вспомогательные данные, имеет смысл оценить и пространственную сложность. В переменную freq будут помещаться все встречающиеся символы, а также их частоты. В худшем случае потребуется $O(k)$ памяти, где $k$ – количество различных символов в исходном тексте (ограничено размером алфавита или $O(n)$). Если размер алфавита ограничен константой, то имеем константную сложность по памяти.

2.4. Анализ рекурсивных алгоритмов. Мастер-теорема

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

Метод декомпозиции заключается в разбиении задачи на некоторое число подзадач, их независимом решении и, затем, объединении результатов в решение исходной задачи. Если задача размера $n$ делится на $a≥1$ подзадач в $b$ раз меньше исходной, а алгоритм объединения результатов решения подзадач имеет временную сложность $f(n)$ (если разбиение требует времени, оно также учитывается), то оценка временной сложности алгоритма выражается рекуррентным соотношением:

Мастер теорема. Пусть алгоритм объединения результатов имеет полиномиальную сложность $\Theta(n^d)$, где $d \ge 0$, тогда временная сложность алгоритма равна

К примеру, сортировка слиянием, которая будет обсуждаться далее, разбивает последовательность на две равные половины ($a = 2$, $b = 2$) и выполняет сортировку рекурсивно для каждой, объединяя полученные отсортированные последовательности алгоритмом с линейной сложностью ($d = 1$). Это соответствует второму случаю, следовательно, временная сложность равна $O(n^1 \cdot log(n)) = O(n \cdot log(n))$.

2.5. Амортизационный анализ

Некоторые алгоритмы или операции над структурами данных имеют непостоянную временную сложность при многократном последовательном выполнении: в большинстве случаев они выполняются быстро, но изредка требуют значительных затрат. Эти редкие «дорогие» операции обычно обусловлены не входными данными, а внутренним состоянием структуры данных.

Классический пример – динамический массив (динамическая таблица). Его типичная реализация заключается в следующем: изначально выделяется память под массив фиксированного размера. При вставке элементы заполняют ячейки. Когда массив полностью заполняется, при попытке следующей вставки создаётся новый массив увеличенного размера (например, в 2 раза больше), и все элементы копируются в него. Такая стратегия называется мультипликативной. Пока в массиве есть свободные ячейки, вставка требует постоянного времени $O(1)$. Однако при увеличении массива перенос всех элементов занимает $O(n)$, где $n$ – текущее число элементов.

Обычный анализ фокусируется на оценке времени выполнения отдельной операции. В приведённом примере это означает, что оценкой сверху станет худший случай – $O(n)$. Но такая оценка не отражает реальную эффективность, если операция выполняется многократно: «дорогие» вставки редки и компенсируются множеством дешёвых.

Это подводит нас к идее амортизационного анализа – подхода, при котором оценивается среднее время выполнения одной операции в серии из $n$ последовательных вызовов. Соответствующая оценка называется амортизационной. Для её обозначения иногда используется специальная нотация: $\sim O(1)$, $\mathit{O}(1)$ или сноска с пояснением.

Рассмотрим пример вставки $n$ элементов в динамический массив с удвоением размера. При каждом переполнении массив копируется в новый, вдвое больший по размеру. Пусть изначально массив имеет размер 1. Тогда на всём пути вставки $n$ элементов копирования будут происходить при достижении размеров 1, 2, 4, 8, ..., $2^{\lfloor\log_2 n\rfloor}$. Затраты на вставку новых элементов в сумме составят $n$. Следовательно, общее время работы алгоритма:

Т.к. $2^{\lfloor\log_2 n\rfloor} \le n$, то $T(n) \le 3n -1$. Получаем среднее время выполнения одной операции: $T(n) / n = \frac{3n - 1}{n} = \sim O(1)$.

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