Асимптотическая сложность

Сортировка пузырьком

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

Один из самых широкоизвестных алгоритмов сортировки — сортировка «пузырьком» (англ. bubble sort).

В предположении, что доступ к массиву осуществляется посредством переменной array, этот алгоритм может быть записан на языке Python следующим образом:

N = len(array)
for _ in range(N-1):
  for i in range(N-1):
    if array[i] > array[i+1]:
      array[i], array[i+1] = array[i+1], array[i]

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

Сложность сортировки пузырьком

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

Будем считать, что каждая из этих операций занимает единицу времени, а всё остальное (например, обслуживание счётчиков циклов) бесплатно. Тогда для массива длины \(N\) алгоритм занимает

\[ 2(N-1)^2 = 2N^2 - 4N + 2 \]

единиц времени. Заметим, что, начиная с \(N=4\), выполнено неравенство

\[ 2(N-1)^2 \geqslant N^2 \]

Также всегда выполнено неравенство

\[ 2(N-1)^2 \leqslant 2N^2 \]

То есть, начиная с некоторого \(N\), время работы алгоритма заключено между значениями выражений, пропорциональных \(N^2\). В такой ситуации говорят, что \(N^2\) является асимптотической сложностью рассматриваемого алгоритма.

В общем случае, если \( T(N) \) — (максимально возможное) время работы алгоритма на наборе данных размера \( N \), а \(f\) — некоторая функция натурального аргумента, то говорят, что:

алгоритм обладает верхней асимптотической сложностью \( f(N) \), если существует такое положительное число \( \alpha \), что, начиная с некоторого \(N\), выполнено неравенство \( T(N) \leqslant \alpha f(N) \)
алгоритм обладает нижней асимптотической сложностью \( f(N) \), если существует такое положительное число \( \alpha \), что, начиная с некоторого \(N\), выполнено неравенство \( T(N) \geqslant \alpha f(N) \)
алгоритм обладает асимптотической сложностью \( f(N) \), если он обладает нижней и верхней асимптотическими сложностями \( f(N) \)

Например, про сортировку пузырьком можно сказать, что:

она обладает верхней асимптотической сложностью \( N^2 \)
она обладает верхней асимптотической сложностью \( 1000N^2 \)
она обладает верхней асимптотической сложностью \( N^{1000} \)
она обладает нижней асимптотической сложностью \( N^2 \)
она обладает нижней асимптотической сложностью \( 1000N^2 \)
она обладает нижней асимптотической сложностью \( N \)
она обладает асимптотической сложностью \( N^2 \)

Часто можно встретить обозначение \(O( f(N) )\) для множества алгоритмов, обладающих асимптотической сложностью \( f(N) \).

Иногда буква \(O\) относится только к верхней асимптотической сложности: в таких ситуациях для нижней асимптотической сложности используется буква \( \Omega \) (омега большая), а для (просто) асимптотической сложности — буква \( \Theta \) (тета большая).

Нижняя оценка сложности алгоритма сортировки

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

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

Проиллюстрируем это на примере пузырька размера 3, в котором все циклы полностью раскрыты, а последнее сравнение вообще убрано (оно ни на что не влияет):

if a[0] > a[1]:
  a[0], a[1] = a[1], a[0]
  if a[1] > a[2]:
    a[0], a[1] = a[1], a[0]
    if a[0] > a[1]:  
      a[0], a[1] = a[1], a[0]
  else:
    if a[0] > a[1]:  
      a[0], a[1] = a[1], a[0]
else:
  if a[1] > a[2]:
    a[0], a[1] = a[1], a[0]
    if a[0] > a[1]:  
      a[0], a[1] = a[1], a[0]
  else:
    if a[0] > a[1]:  
      a[0], a[1] = a[1], a[0]

В этом алгоритме массив [1,2,3] приводит к последовательности результатов сравнений False, False, False. А, например, массив [3,2,1] даёт последовательность True, True, True.

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

Если \(M\) — длина наидлиннейшей такой последовательности, то всего последовательностей не больше \(2^M\). А перестановок массива длины \(N\) ровно \(N!\). Поэтому для любого алгоритма сортировки

\[ 2^M \geqslant N! \]

Продолжим это неравенство, оценив половину сомножителей \(N!\) снизу числом \(1\), а другую половину — числом \(N/2\):

\[ 2^M \geqslant N! \geqslant 1^{N/2}\cdot (N/2)^{N/2} \]

Для нечётного \(N\) это неравенство тоже выполнено (оставляем это в качестве простого упражнения). Теперь применим к неравенству двоичный логарифм:

\[ M \geqslant (N/2) ( \log_2 N - 1 ) \]

Осталось заметить, что начиная с \(N=4\)

\[ M \geqslant (N/2) ( \log_2 N - 1 ) \geqslant (1/4) N \log_2 N \]

Мы доказали, что любой алгоритм сортировки, удовлетворяющий оговоренным выше условиям, обладает (по количеству ветвлений) нижней асимптотической сложностью \(N \log_2 N\).

Контрпример

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

Рассмотрим алгоритм

N = len(array)
for i in range(N):
  array[ array[i] - 1 ] = array[i]

Этот алгоритм отлично сортирует любой массив с различными числами от \(1\) до \(N\), но при этом в нём ровно одна возможная последовательность значений условий ветвлений: пустая. Он обладает асимптотической сложностью \(N\).