Оценка сложности алгоритмов: асимптотическая O-нотация

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

Почему нельзя просто замерить время секундомером на компьютере?

• Время на реальном ПК зависит от мощности процессора, загруженности системы другими процессами, языка программирования и скорости оперативной памяти. На мощном сервере плохой алгоритм может выполниться за 1 секунду, а на слабом ноутбуке хороший алгоритм — за 2 секунды.

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

Асимптотическая сложность описывает поведение алгоритма при устремлении размера входных данных n к бесконечности ($n \to \infty$). Для записи используется математическая нотация $O(f(n))$ («О-большое» / Big O Notation).

Правила вычисления O-нотации:

1. Константные множители отбрасываются: алгоритмы с формулами операций $5n$, $100n$ и $0.5n$ имеют одинаковую асимптотическую сложность $O(n)$;

2. Младшие слагаемые отбрасываются: если время работы описывается многочленом $T(n) = 3n^2 + 50n + 1000$, при больших n (например, $n = 1\,000\,000$) слагаемое $n^2 = 10^{12}$ полностью доминирует над $50n = 5 \cdot 10^7$. Поэтому сложность равна $O(n^2)$.

Иерархия сложности от самых быстрых к самым медленным:

1. $O(1)$ — константное время: не зависит от размера данных (доступ к элементу списка по индексу a[i], получение значения из словаря по ключу);

2. $O(\log n)$ — логарифмическая сложность: время растет крайне медленно (бинарный поиск);

3. $O(n)$ — линейная сложность: один цикл по массиву (поиск минимума, подсчет суммы sum(a));

4. $O(n \log n)$ — квазилинейная сложность: оптимальные алгоритмы быстрой сортировки (MergeSort, QuickSort, Timsort в Python a.sort());

5. $O(n^2)$ — квадратичная сложность: два вложенных цикла (пузырьковая сортировка, перебор всех пар элементов);

6. $O(2^n)$ — экспоненциальная сложность: перебор всех подмножеств, наивные числа Фибоначчи. При $n = 100$ программа не завершится до конца существования Вселенной!

Помимо времени выполнения программы, инженеры обязаны оценивать и пространственную сложность (Space Complexity) — объем дополнительной оперативной памяти, требуемой алгоритму сверх самих входных данных.

Например, пузырьковая сортировка сортирует элементы прямо на месте без создания копий массива (дополнительная память $O(1)$), в то время как сортировка слиянием (MergeSort) требует выделения дополнительного вспомогательного массива размера $O(n)$.