Часто бывает полезно оценить, сколько времени работает алгоритм. Конечно, можно его просто реализовать и запустить, но тут возникают проблемы:
- На разных компьютерах время работы всегда будет отличаться.
- Не всегда заранее доступны именно те данные, на которых он в реальности будет запускаться.
- Иногда приходится оценивать алгоритмы, требующие часы или даже дни работы.
- Жизнь коротка, и если есть несколько вариантов алгоритмов, то хочется заранее предсказать, какой из них будет быстрее, чтобы реализовывать только его.
Для этого, в качестве первого приближения, попробуем оценить число операций в алгоритме. Возникает вопрос: какие именно операции считать. Как один из вариантов — учитывать любые элементарные операции:
- арифметические операции с числами:
+, -, *, / - сравнение чисел:
<, >, <=, >=, ==, != - присваивание:
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)$.