Асимптотический анализ

Часто бывает полезно оценить, сколько времени работает алгоритм. Конечно, можно его просто реализовать и запустить, но тут возникают проблемы:

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

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

• арифметические операции с числами: +, -, *, /
• сравнение чисел: <, >, <=, >=, ==, !=
• присваивание: a[0] = 3

При этом важно не просто считать строчки, а ещё учитывать, как реализованы некоторые отдельные вещи в самом языке. Например, в питоне срезы массива (array[3:10]) копируют этот массив, то есть этот срез работает за 7 элементарных действий. А swap, например, можно реализовать за 3 присваивания.

Упражнение. Попробуйте посчитать точное число сравнений и присваиваний в сортировках пузырьком, выбором, вставками и подсчетом в худшем случае. Это должна быть какая-то формула, зависящая от $n$ — длины массива.

Чтобы учесть вообще все элементарные операции, ещё надо посчитать, например, сколько раз прибавилась единичка внутри цикла for. А ещё, например, строчка n = len(array) — это тоже действие. Поэтому даже посчитав их, не сразу очевидно, какой из этих алгоритмов работает быстрее — сравнивать формулы сложно. Хочется придумать способ упростить эти формулы так, чтобы

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

Для этого придумали О-нотацию — асимптотическое время работы вместо точного (часто его ещё называют просто асимптотикой).

Определение. Пусть $f(n)$ — это какая-то функция. Говорят, что функция $g(n) = O(f(n))$, если существует такие константы $c$ и $n_0$, что $g(n) < c \cdot f(n)$ для всех $n \geq n_0$.

Например:

• $\frac{n}{3} = O(n)$
• $\frac{n(n-1)(n-2)}{6} = O(n^3)$
• $1 + 2 + 3 + \ldots + n = O(n^2)$
• $1^2 + 2^2 + 3^2 + \ldots + n^2 = O(n^3)$
• $\log_2{n} + 3 = O(\log n)$
• $179 = O(1)$
• $10^{100} = O(1)$

В контексте анализа алгоритмов, фраза «алгоритм работает за $O(f(n))$ операций» означает, что начиная с какого-то $n$ он делает не более чем за $c \cdot f(n)$ операций.

В таких обозначениях можно сказать, что

• сортировка пузырьком работает за $O(n^2)$;
• сортировка выбором работает за $O(n^2)$;
• сортировка вставками работает за $O(n^2)$;
• сортировка подсчетом работает за $O(n + m)$.

Это обозначение удобно тем, что оно короткое и понятное, а также не зависит от умножения на константу или прибавления константы. Например, если алгоритм работает за $O(n^2)$, то это может значить, что он работает за $n^2$, за $n^2 + 3$, за $\frac{n(n-1)}{2}$ или даже за $1000 \cdot n^2 + 1$ действие. Главное — что функция ведет себя как $n^2$, то есть при увеличении $n$ она увеличивается как некоторая квадратичная функция: если увеличить $n$ в 10 раз, время работы программы увеличится приблизительно в 100 раз.

Основное преимущество О-нотации в том, что все рассуждения про то, сколько операций в swap или считать ли отдельно присваивания, сравнения и циклы — отпадают. Каков бы ни был ответ на эти вопросы, они меняют ответ лишь на константу, а значит асимптотическое время работы алгоритма не меняется.

Первые три сортировки поэтому называют квадратичными — они работают за $O(n^2)$. Сортировка подсчетом может работать намного быстрее — она работает за $O(n + m)$, а если $m \leq n$, то это вообще линейная функция $O(n)$.