Асимптотическая сложность
TL;DR
Асимптотическая сложность (asymptotic complexity) описывает, как растёт время или память алгоритма при неограниченном увеличении размера входа [math]\displaystyle{ n }[/math], отвлекаясь от постоянных множителей и младших слагаемых. Для этого используют семейства функций: [math]\displaystyle{ O }[/math] — оценка сверху, [math]\displaystyle{ \Omega }[/math] — оценка снизу, [math]\displaystyle{ \Theta }[/math] — точная (двусторонняя) оценка, а также [math]\displaystyle{ o }[/math] и [math]\displaystyle{ \omega }[/math] — строгие версии. Например, [math]\displaystyle{ 3n^2 + 5n + 7 = \Theta(n^2) }[/math]. Рекуррентные алгоритмы анализируют деревом рекурсии или мастер-теоремой (master theorem), а структуры с редкими дорогими операциями — амортизированным анализом (например, [math]\displaystyle{ O(1) }[/math] на push_back в динамический массив). Различают лучший, средний, худший и амортизированный случаи: это разные величины, и путать их — типовая ошибка.
| Свойство | Значение |
|---|---|
| Класс | Математический аппарат анализа алгоритмов и структур данных |
| Что описывает | скорость роста функции [math]\displaystyle{ T(n) }[/math] при [math]\displaystyle{ n \to \infty }[/math] |
| Базовые нотации | [math]\displaystyle{ O }[/math] (сверху), [math]\displaystyle{ \Omega }[/math] (снизу), [math]\displaystyle{ \Theta }[/math] (точно), [math]\displaystyle{ o }[/math], [math]\displaystyle{ \omega }[/math] (строго) |
| Что отбрасывается | постоянные множители и младшие (низшего порядка) слагаемые |
| Инструменты | подсчёт операций, рекуррентные соотношения, дерево рекурсии, мастер-теорема, амортизация, метод подстановки |
| Виды оценки | лучший, средний (ожидаемый), худший, амортизированный |
| Память | та же нотация: [math]\displaystyle{ O(n) }[/math] дополнительной памяти и т. п. |
| Логарифм | по умолчанию двоичный; смена основания меняет лишь константу, поэтому [math]\displaystyle{ O(\log_2 n) = O(\log_{10} n) }[/math] |
| Связанные понятия | время выполнения, число операций, нижние границы, NP-полнота (план) |
Определения
Размер входа [math]\displaystyle{ n }[/math] — числовой параметр, измеряющий объём данных (длина массива, число вершин графа, число бит). Асимптотика описывает поведение при [math]\displaystyle{ n \to \infty }[/math].
О-большое (big-O). Говорят, что [math]\displaystyle{ f(n) = O(g(n)) }[/math], если существуют такие константы [math]\displaystyle{ c \gt 0 }[/math] и [math]\displaystyle{ n_0 \ge 0 }[/math], что для всех [math]\displaystyle{ n \ge n_0 }[/math] выполнено
[math]\displaystyle{ 0 \le f(n) \le c \cdot g(n). }[/math]
Это оценка сверху: [math]\displaystyle{ f }[/math] растёт не быстрее [math]\displaystyle{ g }[/math] (с точностью до константы).
Омега (Ω). [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math], если существуют [math]\displaystyle{ c \gt 0 }[/math] и [math]\displaystyle{ n_0 \ge 0 }[/math], такие что
[math]\displaystyle{ 0 \le c \cdot g(n) \le f(n) \quad \text{для всех } n \ge n_0. }[/math]
Это оценка снизу: [math]\displaystyle{ f }[/math] растёт не медленнее [math]\displaystyle{ g }[/math].
Тета (Θ). [math]\displaystyle{ f(n) = \Theta(g(n)) }[/math], если одновременно [math]\displaystyle{ f(n) = O(g(n)) }[/math] и [math]\displaystyle{ f(n) = \Omega(g(n)) }[/math], то есть существуют [math]\displaystyle{ c_1, c_2 \gt 0 }[/math] и [math]\displaystyle{ n_0 }[/math], такие что
[math]\displaystyle{ 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \text{для всех } n \ge n_0. }[/math]
Это точная оценка: [math]\displaystyle{ f }[/math] и [math]\displaystyle{ g }[/math] растут с одинаковой скоростью.
о-малое (little-o) и омега-малое (ω). [math]\displaystyle{ f(n) = o(g(n)) }[/math], если для любой константы [math]\displaystyle{ c \gt 0 }[/math] найдётся [math]\displaystyle{ n_0 }[/math] с [math]\displaystyle{ f(n) \lt c \cdot g(n) }[/math] при всех [math]\displaystyle{ n \ge n_0 }[/math] (при [math]\displaystyle{ g(n) \gt 0 }[/math]); иными словами, [math]\displaystyle{ \lim_{n\to\infty} f(n)/g(n) = 0 }[/math]. Аналогично [math]\displaystyle{ f(n) = \omega(g(n)) }[/math] означает [math]\displaystyle{ \lim_{n\to\infty} f(n)/g(n) = \infty }[/math]. Это строгие версии [math]\displaystyle{ O }[/math] и [math]\displaystyle{ \Omega }[/math].
Время работы [math]\displaystyle{ T(n) }[/math] — число элементарных операций (сравнений, сложений, обращений к памяти) как функция размера входа. Ёмкость памяти [math]\displaystyle{ M(n) }[/math] измеряется аналогично.
Инвариант нотации. Константы [math]\displaystyle{ c }[/math] и [math]\displaystyle{ n_0 }[/math] существуют, но не называются: обозначение скрывает и машину, и конкретные множители. Запись [math]\displaystyle{ f(n) = O(g(n)) }[/math] — это «принадлежность множеству» [math]\displaystyle{ f \in O(g) }[/math], а не равенство; писать [math]\displaystyle{ O(g(n)) = f(n) }[/math] нельзя.
См. рис. 1: [math]\displaystyle{ O }[/math] держит функцию сверху, [math]\displaystyle{ \Omega }[/math] — снизу, [math]\displaystyle{ \Theta }[/math] — зажимает между двумя масштабами одной функции [math]\displaystyle{ g }[/math].
Мотивация и интуиция
Точное число операций зависит от процессора, компилятора, кэша и версии библиотек — сравнивать алгоритмы «по секундомеру» нельзя. Асимптотика даёт машинно-независимый критерий: как масштаб задачи влияет на стоимость. Вопрос, на который она отвечает, звучит так: «что произойдёт, если вход вырастет в 10 раз?»
Возьмём сортировку. На массиве из [math]\displaystyle{ n = 10^5 }[/math] элементов:
| Алгоритм | Оценка | Порядок числа операций при [math]\displaystyle{ n = 10^5 }[/math] |
|---|---|---|
| Вставками | [math]\displaystyle{ \Theta(n^2) }[/math] | [math]\displaystyle{ 10^{10} }[/math] |
| Слиянием | [math]\displaystyle{ \Theta(n \log n) }[/math] | [math]\displaystyle{ \approx 1.7 \cdot 10^6 }[/math] |
| Подсчётом | [math]\displaystyle{ \Theta(n + k) }[/math] | [math]\displaystyle{ 10^5 }[/math] при [math]\displaystyle{ k \ll n }[/math] |
Разница между [math]\displaystyle{ 10^{10} }[/math] и [math]\displaystyle{ 10^6 }[/math] — это секунды против миллисекунд. При удвоении [math]\displaystyle{ n }[/math] квадратичный алгоритм замедлится вчетверо, а линейно-логарифмический — чуть больше чем вдвое (см. рис. 2). Именно поэтому асимптотика — первый вопрос при выборе структуры данных.
Ключевая идея в одном абзаце: асимптотика — это предельное поведение, а не точная стоимость. Она отбрасывает всё, что не влияет на рост: множитель «в 10 раз быстрее» и слагаемое «плюс 100 операций» при больших [math]\displaystyle{ n }[/math] тонут на фоне главного члена [math]\displaystyle{ n^2 }[/math] или [math]\displaystyle{ 2^n }[/math].
Устройство
Аппарат состоит из трёх слоёв:
- Сравнение функций роста. Все функции упорядочены по скорости роста; «большая» структура классов [math]\displaystyle{ O(1) \subset O(\log n) \subset O(n) \subset O(n\log n) \subset O(n^2) \subset O(n^3) \subset O(2^n) \subset O(n!) }[/math] называется иерархией сложностей (см. рис. 3). Функция, попавшая в меньший класс, попадает и во все большие: [math]\displaystyle{ O(\log n) \subseteq O(n) }[/math].
- Нотация. [math]\displaystyle{ O }[/math] отвечает на вопрос «не хуже чего?», [math]\displaystyle{ \Omega }[/math] — «не лучше чего?», [math]\displaystyle{ \Theta }[/math] — «ровно как что?». При анализе алгоритма обычно указывают [math]\displaystyle{ O }[/math] (гарантия сверху) или [math]\displaystyle{ \Theta }[/math] (если граница точная).
- Методы вывода оценок. Для итеративных алгоритмов подсчитывают операции; для рекурсивных решают рекуррентные соотношения (подстановка, дерево рекурсии, мастер-теорема); для структур с редкими дорогими операциями применяют амортизацию.
Операции и алгоритмы
Метод: подсчёт операций (для итеративных алгоритмов)
Идея. Пронумеровать операторы и посчитать, сколько раз выполняется каждый при входе размера [math]\displaystyle{ n }[/math]; сложить и упростить, оставив главный член.
Пошаговое описание:
- Выбрать «элементарную операцию», стоимость которой считаем за 1 (обычно сравнение или присваивание).
- Для каждого оператора оценить число выполнений как функцию от [math]\displaystyle{ n }[/math] (часто через сумму ряда).
- Сложить оценки; отбросить константы и младшие слагаемые, сохранив главный член.
- Записать результат в виде [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math] или [math]\displaystyle{ \Theta }[/math].
Инвариант. Сумма локальных подсчётов равна полному числу операций; упрощение не меняет асимптотический класс.
Сложность. Для примера ниже — [math]\displaystyle{ \Theta(n^2) }[/math] операций при [math]\displaystyle{ O(1) }[/math] дополнительной памяти; сама выкладка по формулам занимает [math]\displaystyle{ O(1) }[/math].
Анализ Number-Of-Ops(n) # вложенные циклы
Вход: n — размер входа
Выход: асимптотическая оценка числа операций
Сложность: O(1) времени на выкладку
1 ops ← 0
2 for i ← 1 to n
3 for j ← 1 to i
4 ops ← ops + 1 # выполняется i раз при данном i
5 # ops = 1 + 2 + … + n = n(n+1)/2 = Θ(n²)
6 return Θ(n²)
Разбор. При [math]\displaystyle{ n = 4 }[/math] внутренний цикл выполняется [math]\displaystyle{ 1 + 2 + 3 + 4 = 10 }[/math] раз, а формула даёт [math]\displaystyle{ 4 \cdot 5 / 2 = 10 }[/math] (см. рис. 4). Оценка: [math]\displaystyle{ \tfrac{n(n+1)}{2} \le n^2 }[/math] и [math]\displaystyle{ \tfrac{n(n+1)}{2} \ge \tfrac{n^2}{2} }[/math], значит [math]\displaystyle{ \Theta(n^2) }[/math].
Крайние случаи. Если внутренний цикл зависит от данных (например, прерывается раньше), одна и та же схема даёт разные оценки для лучшего и худшего входов — тогда указывают диапазон от [math]\displaystyle{ \Omega }[/math] до [math]\displaystyle{ O }[/math].
Метод: рекуррентные соотношения
Идея. Для рекурсивного алгоритма записывают [math]\displaystyle{ T(n) }[/math] через меньшие [math]\displaystyle{ T }[/math] и стоимость «склейки», затем решают: подстановкой, деревом рекурсии или мастер-теоремой.
Пошаговое описание:
- Выписать рекуррентность и базовый случай, например [math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) }[/math], [math]\displaystyle{ T(1) = \Theta(1) }[/math].
- Построить дерево рекурсии: узлы — рекурсивные вызовы, подпись узла — стоимость его «склейки».
- Просуммировать по уровням и умножить на глубину; либо угадать и доказать по индукции.
Инвариант. Сумма по всем узлам дерева равна полной стоимости [math]\displaystyle{ T(n) }[/math].
Сложность. Время [math]\displaystyle{ T(n) = \Theta(n\log n) }[/math]; дополнительная память [math]\displaystyle{ O(n) }[/math] на слияние плюс [math]\displaystyle{ O(\log n) }[/math] на стек рекурсии.
Алгоритм Merge-Sort(A, lo, hi)
Вход: массив A[1..n], границы lo ≤ hi
Выход: A[lo..hi] отсортирован по неубыванию
Рекуррентность: T(n) = 2·T(n/2) + Θ(n), T(1) = Θ(1)
Сложность: T(n) = Θ(n log n)
1 if lo < hi
2 mid ← ⌊(lo + hi) / 2⌋
3 Merge-Sort(A, lo, mid)
4 Merge-Sort(A, mid + 1, hi)
5 Merge(A, lo, mid, hi) # слияние за Θ(hi − lo + 1)
Разбор. Дерево рекурсии имеет [math]\displaystyle{ \lceil\log_2 n\rceil + 1 }[/math] уровней; на каждом уровне суммарная стоимость слияний не превосходит [math]\displaystyle{ n }[/math] (см. рис. 5). Итого [math]\displaystyle{ T(n) \le n(\lceil\log_2 n\rceil + 1) = O(n\log n) }[/math]; нижняя оценка [math]\displaystyle{ \Omega(n\log n) }[/math] (мастер-теорема, случай 2) даёт [math]\displaystyle{ \Theta(n\log n) }[/math].
Крайние случаи. Если деление неравное ([math]\displaystyle{ T(n) = T(n-1) + \Theta(n) }[/math]), дерево вырождается в цепочку глубины [math]\displaystyle{ n }[/math] и [math]\displaystyle{ T(n) = \Theta(n^2) }[/math] — так деградирует быстрая сортировка на плохих опорных.
Мастер-теорема (master theorem). Для [math]\displaystyle{ T(n) = a\,T(n/b) + f(n) }[/math], [math]\displaystyle{ a \ge 1 }[/math], [math]\displaystyle{ b \gt 1 }[/math], сравнивают [math]\displaystyle{ f(n) }[/math] с [math]\displaystyle{ n^{\log_b a} }[/math]:
| Случай | Условие | Решение |
|---|---|---|
| 1 | [math]\displaystyle{ f(n) = O\!\left(n^{\log_b a - \varepsilon}\right) }[/math], [math]\displaystyle{ \varepsilon \gt 0 }[/math] | [math]\displaystyle{ T(n) = \Theta\!\left(n^{\log_b a}\right) }[/math] |
| 2 | [math]\displaystyle{ f(n) = \Theta\!\left(n^{\log_b a}\right) }[/math] | [math]\displaystyle{ T(n) = \Theta\!\left(n^{\log_b a} \log n\right) }[/math] |
| 3 | [math]\displaystyle{ f(n) = \Omega\!\left(n^{\log_b a + \varepsilon}\right) }[/math] и условие регулярности | [math]\displaystyle{ T(n) = \Theta(f(n)) }[/math] |
Для слияния: [math]\displaystyle{ a = 2 }[/math], [math]\displaystyle{ b = 2 }[/math], [math]\displaystyle{ n^{\log_b a} = n }[/math], [math]\displaystyle{ f(n) = \Theta(n) }[/math] — случай 2, значит [math]\displaystyle{ \Theta(n\log n) }[/math]. Мастер-теорема применима не всегда: при несбалансированных делениях (например, [math]\displaystyle{ T(n) = T(n-1) + n }[/math]) или при нерегулярном [math]\displaystyle{ f }[/math] пользуются деревом или подстановкой. Условие регулярности для случая 3 выполнено, если [math]\displaystyle{ a\,f(n/b) \le c\,f(n) }[/math] при некотором [math]\displaystyle{ c \lt 1 }[/math] и достаточно больших [math]\displaystyle{ n }[/math].
Метод: амортизированный анализ
Идея. Некоторые операции дороги, но редки. Амортизированная стоимость — это полная стоимость последовательности, делённая на число операций. Три способа учёта: агрегатный, метод предоплаты (бухгалтерский) и метод потенциала.
Пошаговое описание (пример: динамический массив с удвоением ёмкости):
- Новый элемент пишется за [math]\displaystyle{ O(1) }[/math], если есть свободное место.
- Если места нет, создаётся массив вдвое больше и все элементы копируются — [math]\displaystyle{ O(n) }[/math].
- Копирование на [math]\displaystyle{ k }[/math]-м расширении стоит [math]\displaystyle{ 2^{k-1} }[/math] и происходит после [math]\displaystyle{ 2^{k-1} }[/math] вставок.
- Суммируя, получаем геометрическую прогрессию [math]\displaystyle{ 1 + 2 + 4 + \dots \le 2n }[/math], то есть [math]\displaystyle{ O(1) }[/math] в среднем на операцию.
Инвариант. Каждая операция записывает ровно один элемент, поэтому за [math]\displaystyle{ m }[/math] операций суммарная стоимость лежит между [math]\displaystyle{ m }[/math] и [math]\displaystyle{ m + (\text{суммарные копирования}) \le 3m }[/math]; деление на [math]\displaystyle{ m }[/math] даёт [math]\displaystyle{ O(1) }[/math] в расчёте на операцию.
Операция Push-Back(A, x) # динамический массив с удвоением
Вход: массив A с полями size (занято) и cap (ёмкость); элемент x
Выход: x добавлен в конец A
Амортизированная сложность: O(1) на операцию (худшая отдельная — O(n))
1 if size = cap
2 cap ← max(1, 2·cap) # удвоить ёмкость
3 A' ← новый массив длины cap
4 for i ← 1 to size
5 A'[i] ← A[i] # копирование: O(size)
6 A ← A'
7 size ← size + 1
8 A[size] ← x
Разбор. За 16 операций копируется [math]\displaystyle{ 1 + 2 + 4 + 8 = 15 }[/math] элементов — меньше [math]\displaystyle{ n }[/math] (см. рис. 6). Значит, каждый push_back в среднем копирует меньше одного элемента: амортизированно [math]\displaystyle{ O(1) }[/math].
Крайние случаи. Если увеличивать ёмкость на константу ([math]\displaystyle{ cap + 1 }[/math]), суммарная стоимость станет [math]\displaystyle{ \Theta(n^2) }[/math]; удвоение (или умножение на любую константу [math]\displaystyle{ \gt 1 }[/math]) критично. Метод потенциала позволяет получить ту же оценку строго: [math]\displaystyle{ \Phi = 2\,\text{size} - \text{cap} }[/math].
Сводная таблица сложности
Таблица функций роста: как меняется число операций при увеличении [math]\displaystyle{ n }[/math] с [math]\displaystyle{ 10^3 }[/math] до [math]\displaystyle{ 10^6 }[/math].
| Класс | Название | [math]\displaystyle{ n = 10^3 }[/math] | [math]\displaystyle{ n = 10^6 }[/math] | Удвоение [math]\displaystyle{ n }[/math] умножает |
|---|---|---|---|---|
| [math]\displaystyle{ O(1) }[/math] | константа | 1 | 1 | ×1 |
| [math]\displaystyle{ O(\log n) }[/math] | логарифм | ≈10 | ≈20 | +1 |
| [math]\displaystyle{ O(n) }[/math] | линейная | [math]\displaystyle{ 10^3 }[/math] | [math]\displaystyle{ 10^6 }[/math] | ×2 |
| [math]\displaystyle{ O(n\log n) }[/math] | линия с логарифмом | ≈[math]\displaystyle{ 10^4 }[/math] | ≈[math]\displaystyle{ 2\cdot10^7 }[/math] | чуть больше ×2 |
| [math]\displaystyle{ O(n^2) }[/math] | квадратичная | [math]\displaystyle{ 10^6 }[/math] | [math]\displaystyle{ 10^{12} }[/math] | ×4 |
| [math]\displaystyle{ O(n^3) }[/math] | кубическая | [math]\displaystyle{ 10^9 }[/math] | [math]\displaystyle{ 10^{18} }[/math] | ×8 |
| [math]\displaystyle{ O(2^n) }[/math] | экспоненциальная | астрономично | астрономично | возводится в квадрат |
Операционная таблица по памяти:
| Оценка памяти | Смысл | Пример |
|---|---|---|
| [math]\displaystyle{ O(1) }[/math] | не зависит от [math]\displaystyle{ n }[/math] | счётчики, указатели |
| [math]\displaystyle{ O(\log n) }[/math] | как у двоичного представления числа | рекурсивный двоичный поиск (глубина стека) |
| [math]\displaystyle{ O(n) }[/math] | пропорционально входу | массив, копия графа |
| [math]\displaystyle{ O(n^2) }[/math] | матрица [math]\displaystyle{ n \times n }[/math] | таблица динамического программирования |
Оговорка: худший случай, средний случай и амортизированная оценка — разные величины (см. рис. 7); средний случай требует модели распределения входов, поэтому без неё оценка не определена. Рандомизация (например, случайный опорный в quicksort) превращает худший случай в вероятностный.
Трассировка примера
Разберём пять алгоритмов и выведем оценку «руками».
| Алгоритм | Шаги | Рекуррентность / сумма | Итог |
|---|---|---|---|
| Двоичный поиск | каждый шаг делит отрезок вдвое | [math]\displaystyle{ T(n) = T(n/2) + \Theta(1) }[/math] | [math]\displaystyle{ \Theta(\log n) }[/math] |
| Один проход по массиву | один цикл длины [math]\displaystyle{ n }[/math] | [math]\displaystyle{ \sum_{i=1}^{n} 1 = n }[/math] | [math]\displaystyle{ \Theta(n) }[/math] |
| Вложенные циклы | для каждого [math]\displaystyle{ i }[/math] до [math]\displaystyle{ i }[/math] шагов | [math]\displaystyle{ \sum_{i=1}^{n} i = n(n+1)/2 }[/math] | [math]\displaystyle{ \Theta(n^2) }[/math] |
| Сортировка слиянием | деление пополам и слияние | [math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) }[/math] | [math]\displaystyle{ \Theta(n\log n) }[/math] |
push_back × [math]\displaystyle{ n }[/math] |
редкие копии всего массива | [math]\displaystyle{ 1+2+4+\dots \le 2n }[/math] | амортизированно [math]\displaystyle{ \Theta(1) }[/math] за операцию |
Полный прогон. Проследим сортировку слиянием на [math]\displaystyle{ A = [5, 2, 8, 1, 9, 3, 7, 4] }[/math], [math]\displaystyle{ n = 8 }[/math] (индексация [math]\displaystyle{ 1..8 }[/math]). Сначала рекурсия делит массив до листьев, затем слияния идут снизу вверх.
| Шаг | Состояние [math]\displaystyle{ A }[/math] | Комментарий |
|---|---|---|
| 0 | [5 2 8 1 9 3 7 4] |
исходный массив |
| 1 | [5 2 8 1] [9 3 7 4] |
деление пополам: два отрезка по 4 |
| 2 | [5 2] [8 1] [9 3] [7 4] |
каждый отрезок делится ещё раз |
| 3 | [5] [2] [8] [1] [9] [3] [7] [4] |
листья: восемь отрезков по одному элементу |
| 4 | [2 5] [1 8] [3 9] [4 7] |
четыре слияния пар, по одному сравнению |
| 5 | [1 2 5 8] [3 4 7 9] |
два слияния по 3 сравнения |
| 6 | [1 2 3 4 5 7 8 9] |
финальное слияние, 7 сравнений |
Итого 17 сравнений при верхней оценке [math]\displaystyle{ n\lceil\log_2 n\rceil = 8 \cdot 3 = 24 }[/math]: стоимость каждого уровня слияний линейна по [math]\displaystyle{ n }[/math], число уровней логарифмично.
Разберём двоичный поиск. Инвариант: искомый элемент, если он есть, лежит в оставшемся отрезке. Каждая итерация делит отрезок пополам, значит после [math]\displaystyle{ k }[/math] итераций остаётся не более [math]\displaystyle{ n/2^k }[/math] элементов. Остановка при [math]\displaystyle{ n/2^k \lt 1 }[/math], то есть [math]\displaystyle{ k \gt \log_2 n }[/math]: всего [math]\displaystyle{ \Theta(\log n) }[/math] итераций, память [math]\displaystyle{ O(1) }[/math].
Корректность и оценка сложности
Доказательство асимптотических соотношений
Утверждение. [math]\displaystyle{ 3n^2 + 5n + 7 = \Theta(n^2) }[/math].
Доказательство. Нужно найти [math]\displaystyle{ c_1, c_2, n_0 \gt 0 }[/math].
- Сверху: [math]\displaystyle{ 3n^2 + 5n + 7 \le 3n^2 + 5n^2 + 7n^2 = 15n^2 }[/math] при [math]\displaystyle{ n \ge 1 }[/math]. Значит, [math]\displaystyle{ c_2 = 15 }[/math], [math]\displaystyle{ n_0 = 1 }[/math] дают [math]\displaystyle{ f(n) = O(n^2) }[/math].
- Снизу: [math]\displaystyle{ 3n^2 + 5n + 7 \ge 3n^2 }[/math] при [math]\displaystyle{ n \ge 0 }[/math]. Значит, [math]\displaystyle{ c_1 = 3 }[/math] дают [math]\displaystyle{ f(n) = \Omega(n^2) }[/math].
Обе границы выполнены, поэтому [math]\displaystyle{ f(n) = \Theta(n^2) }[/math]. [math]\displaystyle{ \square }[/math]
Общий приём для многочленов: степень [math]\displaystyle{ d }[/math] с ненулевым старшим коэффициентом даёт [math]\displaystyle{ \Theta(n^d) }[/math]. Для сравнения [math]\displaystyle{ f }[/math] и [math]\displaystyle{ g }[/math] часто берут предел [math]\displaystyle{ \lim_{n\to\infty} f(n)/g(n) }[/math]: ноль даёт [math]\displaystyle{ f = o(g) }[/math], константа — [math]\displaystyle{ f = \Theta(g) }[/math], бесконечность — [math]\displaystyle{ f = \omega(g) }[/math] (при положительных функциях).
Дерево рекурсии для [math]\displaystyle{ T(n) = 2T(n/2) + n }[/math]
Развернём рекурсию. На уровне [math]\displaystyle{ i }[/math] (нумерация с нуля) находится [math]\displaystyle{ 2^i }[/math] узлов, каждый со стоимостью [math]\displaystyle{ n/2^i }[/math]; сумма уровня не превосходит [math]\displaystyle{ 2^i \cdot (n/2^i) = n }[/math]. Уровней [math]\displaystyle{ \lceil\log_2 n\rceil + 1 }[/math] (от [math]\displaystyle{ n }[/math] до листьев единичного размера), поэтому
[math]\displaystyle{ T(n) \le \sum_{i=0}^{\lceil\log_2 n\rceil} n = n(\lceil\log_2 n\rceil + 1) = O(n\log n). }[/math]
Нижняя граница [math]\displaystyle{ T(n) = \Omega(n\log n) }[/math] следует из мастер-теоремы (случай 2): [math]\displaystyle{ a = 2 }[/math], [math]\displaystyle{ b = 2 }[/math], [math]\displaystyle{ f(n) = \Theta(n) }[/math]. Вместе это даёт [math]\displaystyle{ T(n) = \Theta(n\log n) }[/math].
Формально это доказывается индукцией (подстановкой констант): предполагаем [math]\displaystyle{ T(k) \le d\,k\log k }[/math] для [math]\displaystyle{ k \lt n }[/math], подставляем и подбираем [math]\displaystyle{ d }[/math].
Амортизация: агрегатный и потенциальный методы
Агрегатный метод. Стоимость [math]\displaystyle{ m }[/math] операций делится на [math]\displaystyle{ m }[/math]. Для динамического массива сумма копирований не превосходит [math]\displaystyle{ 2m }[/math] (геометрическая прогрессия до ближайшей степени двойки), поэтому полная стоимость [math]\displaystyle{ m }[/math] вставок [math]\displaystyle{ \le 3m }[/math]. Значит, амортизированно [math]\displaystyle{ O(1) }[/math] на операцию.
Метод потенциала. Задают потенциальную функцию [math]\displaystyle{ \Phi }[/math] на состоянии структуры; амортизированная стоимость операции [math]\displaystyle{ \hat{c} = c + \Delta\Phi }[/math]. Для массива [math]\displaystyle{ \Phi = 2\,\text{size} - \text{cap} }[/math] (считаем cap = 0 в пустом массиве). Тогда [math]\displaystyle{ \Phi \ge 0 }[/math], а после дорогой вставки потенциал резко падает — с cap до 2, — и это падение оплачивает копирование. Метод строг и позволяет давать амортизированные оценки для splay-дерева (план), DSU (план) и фибоначчиевой кучи (план).
Сравнение с альтернативами
Нотации. Выбор символа — вопрос того, какую гарантию вы хотите:
| Обозначение | Читается | Гарантия | Пример |
|---|---|---|---|
| [math]\displaystyle{ f = O(g) }[/math] | «не быстрее [math]\displaystyle{ g }[/math]» | верхняя граница | quicksort в среднем [math]\displaystyle{ O(n\log n) }[/math] |
| [math]\displaystyle{ f = \Omega(g) }[/math] | «не медленнее [math]\displaystyle{ g }[/math]» | нижняя граница | сортировка сравнением [math]\displaystyle{ \Omega(n\log n) }[/math] |
| [math]\displaystyle{ f = \Theta(g) }[/math] | «ровно как [math]\displaystyle{ g }[/math]» | точная | сортировка слиянием [math]\displaystyle{ \Theta(n\log n) }[/math] |
| [math]\displaystyle{ f = o(g) }[/math] | «строго медленнее» | верхняя, без константы | [math]\displaystyle{ n = o(n^2) }[/math], но [math]\displaystyle{ n \ne o(n) }[/math] |
| [math]\displaystyle{ f = \omega(g) }[/math] | «строго быстрее» | нижняя, без константы | [math]\displaystyle{ n^2 = \omega(n) }[/math] |
Важно: запись [math]\displaystyle{ O(n) }[/math] — это множество функций. «[math]\displaystyle{ O(n) = O(n^2) }[/math]» — сокращение для включения множеств [math]\displaystyle{ O(n) \subseteq O(n^2) }[/math], а не равенство чисел; обратное включение неверно.
Случаи. Четыре разных вопроса (см. рис. 7):
| Оценка | Что берём | Пример |
|---|---|---|
| Лучший | лучший вход | поиск в корне — [math]\displaystyle{ O(1) }[/math] |
| Средний | распределение входов | quicksort [math]\displaystyle{ O(n\log n) }[/math] |
| Худший | все входы | quicksort [math]\displaystyle{ O(n^2) }[/math] |
| Амортизированный | длинная последовательность операций | push_back [math]\displaystyle{ O(1) }[/math]
|
Вердикт: для инженерных гарантий указывайте худший случай; для алгоритмов со случайными входами — средний; для структур с редкими дорогими операциями — амортизированный; лучший случай почти всегда бесполезен для практики.
Где применяется
- Выбор алгоритма и структуры данных. Перед реализацией сравнивают [math]\displaystyle{ \Theta }[/math]-оценки: сортировка слиянием [math]\displaystyle{ \Theta(n\log n) }[/math] против квадратичной на больших [math]\displaystyle{ n }[/math] решает сотни миллисекунд против часов. Асимптотика — первый фильтр при проектировании [1][3].
- Стандартные библиотеки и их гарантии. В документации C++ указаны сложности:
std::sort— [math]\displaystyle{ O(n\log n) }[/math] (introsort),std::priority_queue::push— [math]\displaystyle{ O(\log n) }[/math],std::unordered_map— [math]\displaystyle{ O(1) }[/math] в среднем и [math]\displaystyle{ O(n) }[/math] в худшем. Амортизацияstd::vector::push_back— тоже асимптотический факт из стандарта [6][7].
- Планировщики СУБД. Оптимизатор запросов оценивает стоимость планов по асимптотическим моделям (стоимость соединений, сканирований, индексного доступа) и выбирает план с меньшей оценкой. Ошибка в модели роста приводит к выбору катастрофически медленного плана [4].
- Сетевые и распределённые системы. Оценки [math]\displaystyle{ \tilde{O} }[/math] (soft-O: [math]\displaystyle{ O }[/math] с точностью до логарифмических множителей) и амортизация лежат в основе анализа протоколов, хеш-таблиц с перехешированием и структур с гарантиями по задержке; при проектировании SLA важно знать, что происходит при росте нагрузки в 10 раз [5].
- Компиляторы. Алгоритмы анализа и оптимизации (построение графа потока управления, SSA, раскраска графа) оцениваются асимптотически; компилятор должен масштабироваться на миллионы строк кода [8].
- Спортивное программирование. Ограничения [math]\displaystyle{ n }[/math] и лимит времени задают допустимый класс: при [math]\displaystyle{ n = 10^5 }[/math] и 1 секунде [math]\displaystyle{ \Theta(n^2) }[/math] отбрасывают, а [math]\displaystyle{ \Theta(n\log n) }[/math] принимают. Оценка по таблице из раздела «Сводная таблица» — рутинный шаг решения [9].
Историческая справка
Символ [math]\displaystyle{ O }[/math] ввёл Пауль Бахман (Paul Bachmann) в 1894 году в книге по аналитической теории чисел для обозначения «порядка» функции [10]. Эдмунд Ландау (Edmund Landau) распространил и популяризовал обозначения, поэтому в литературе встречается название символы Ландау (Landau symbols); сам знак [math]\displaystyle{ \Omega }[/math] и слово «асимптотически» также связывают с его работами начала XX века [10][11].
В информатику нотацию ввёл в широкое употребление Дональд Кнут (Donald Knuth): в работе «Big Omicron and big Omega and big Theta» (1976) он предложил современное значение [math]\displaystyle{ \Theta }[/math] и систематизировал использование [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math], [math]\displaystyle{ o }[/math], [math]\displaystyle{ \omega }[/math] [11]. До этого в анализе алгоритмов обозначения применялись непоследовательно.
Амортизированный анализ как формальный метод развил Роберт Тарьян (Robert Tarjan) в 1985 году (метод потенциала и его применения к splay-деревьям, union-find, динамическим массивам) [12]. Мастер-теорема (master theorem) в современном виде сформулировали Джон Бентли, Доротея Хакен и Джеймс Сакс в 1980 году [13]. Нижние границы сложности сортировки сравнением ([math]\displaystyle{ \Omega(n\log n) }[/math]) получены в 1960-е (в т. ч. анализом «дерева решений»).
Типичные ошибки и подводные камни
- Путаница [math]\displaystyle{ O }[/math] и [math]\displaystyle{ \Theta }[/math]. Утверждение «алгоритм работает за [math]\displaystyle{ O(n^2) }[/math]» не запрещает ему работать за [math]\displaystyle{ O(n) }[/math]; для точности нужен [math]\displaystyle{ \Theta }[/math] или явная нижняя граница.
- «[math]\displaystyle{ O }[/math] — это худший случай». Неверно: [math]\displaystyle{ O }[/math] может описывать и среднюю, и амортизированную оценку. Худший случай — про вход, а [math]\displaystyle{ O }[/math] — про границу.
- Обратная запись равенства. [math]\displaystyle{ O(n) = O(n^2) }[/math] верно как вложение множеств, но «[math]\displaystyle{ O(n^2) = O(n) }[/math]» бессмысленно. Нельзя решать уравнения с символами [math]\displaystyle{ O }[/math].
- Отбрасывание констант там, где это ломает вывод. На малых [math]\displaystyle{ n }[/math] (или при очень большом множителе) алгоритм с лучшей асимптотикой может проигрывать; константы важны на практике (пример — алгоритмы с множителем [math]\displaystyle{ 10^6 }[/math], применимые лишь на огромных входах).
- Смешение времени и памяти. [math]\displaystyle{ O(1) }[/math] по памяти и [math]\displaystyle{ O(1) }[/math] по времени — разные утверждения; пишите, о каком ресурсе речь.
- Путаница среднего и амортизированного. Среднее требует вероятностной модели входов; амортизированное — детерминированная гарантия для последовательности. Ни то, ни другое не защищает от дорогой отдельной операции.
- Неверная база логарифма как «ошибка». [math]\displaystyle{ O(\log_2 n) = O(\log_{10} n) }[/math]: смена основания — константа, которая отбрасывается. Но при сравнении с иными функциями основание иногда важно (например, в [math]\displaystyle{ n^{\log_b a} }[/math]).
- Забытая модель операций. «[math]\displaystyle{ O(1) }[/math] на сравнение» неявно предполагает, что сравнение — элементарная операция; для длинных чисел/строк это не так (стоимость зависит от длины).
- Скрытая рекурсия и стек. Алгоритм «[math]\displaystyle{ O(\log n) }[/math] по времени», но с рекурсией глубины [math]\displaystyle{ n }[/math], требует [math]\displaystyle{ O(n) }[/math] памяти; второй ресурс легко упустить.
- Асимптотика ≠ бенчмарк. Микробенчмарки без прогона на разных [math]\displaystyle{ n }[/math] не показывают рост; измерять надо масштабированием, а не одной точкой.
Задачи для практики
- Классификация. Для функций [math]\displaystyle{ n^3 }[/math], [math]\displaystyle{ n\log n }[/math], [math]\displaystyle{ 2^n }[/math], [math]\displaystyle{ \log\log n }[/math], [math]\displaystyle{ n! }[/math], [math]\displaystyle{ \sqrt{n} }[/math] расставьте их по возрастанию скорости роста и укажите пары, где одна является [math]\displaystyle{ o }[/math] от другой. Подсказка: сравните пределы отношений. Ответ: [math]\displaystyle{ \log\log n \prec \sqrt{n} \prec n\log n \prec n^3 \prec 2^n \prec n! }[/math].
- Доказательство [math]\displaystyle{ \Theta }[/math]. Докажите, что [math]\displaystyle{ 2n^2 + 3n + 1 = \Theta(n^2) }[/math], предъявив [math]\displaystyle{ c_1 }[/math], [math]\displaystyle{ c_2 }[/math] и [math]\displaystyle{ n_0 }[/math]. Подсказка: возьмите [math]\displaystyle{ c_1 = 2 }[/math], [math]\displaystyle{ c_2 = 3 }[/math], [math]\displaystyle{ n_0 = 4 }[/math].
- Рекуррентность. Решите [math]\displaystyle{ T(n) = 3T(n/3) + n }[/math] мастер-теоремой и деревом рекурсии; сравните. Подсказка: [math]\displaystyle{ n^{\log_3 3} = n }[/math] — это случай 2, ответ [math]\displaystyle{ \Theta(n\log n) }[/math].
- Мастер-теорема. Для каких [math]\displaystyle{ a }[/math], [math]\displaystyle{ b }[/math], [math]\displaystyle{ f }[/math] её условия не выполняются, хотя рекуррентность корректна? Приведите [math]\displaystyle{ T(n) = T(n-1) + n }[/math] и решите дерево. Ответ: [math]\displaystyle{ \Theta(n^2) }[/math].
- Амортизация. Докажите, что при увеличении ёмкости массива на [math]\displaystyle{ 1 }[/math] суммарная стоимость [math]\displaystyle{ n }[/math] вставок есть [math]\displaystyle{ \Theta(n^2) }[/math], а при умножении на [math]\displaystyle{ 2 }[/math] — [math]\displaystyle{ \Theta(n) }[/math]. Подсказка: сумма арифметической прогрессии против геометрической.
- Оценка по коду. Определите [math]\displaystyle{ O }[/math] для программы с тройным циклом
for i to n / for j to n / for k to i. Подсказка: внутренний цикл даёт [math]\displaystyle{ i }[/math] шагов, средний — [math]\displaystyle{ n }[/math]; аккуратно пересчитайте.
- Нижняя граница. Покажите, что поиск в неотсортированном массиве требует [math]\displaystyle{ \Omega(n) }[/math] сравнений. Подсказка: если элемент не проверен, его значение может оказаться искомым.
- Практика констант. При каком [math]\displaystyle{ n }[/math] алгоритм [math]\displaystyle{ A }[/math] (1000 операций на элемент, [math]\displaystyle{ \Theta(n\log n) }[/math]) обгонит алгоритм [math]\displaystyle{ B }[/math] (1 операция на пару, [math]\displaystyle{ \Theta(n^2) }[/math])? Оцените аналитически и проверьте подсчётом. Подсказка: решите [math]\displaystyle{ 1000\,n\log n = n^2 }[/math].
Ответы и оценки сложности.
- Порядок: [math]\displaystyle{ \log\log n \prec \sqrt{n} \prec n\log n \prec n^3 \prec 2^n \prec n! }[/math]; например, [math]\displaystyle{ \sqrt{n} = o(n\log n) }[/math], [math]\displaystyle{ n\log n = o(n^3) }[/math], [math]\displaystyle{ n^3 = o(2^n) }[/math], [math]\displaystyle{ 2^n = o(n!) }[/math] — каждое отношение стремится к нулю.
- [math]\displaystyle{ 2n^2 + 3n + 1 \le 3n^2 }[/math] при [math]\displaystyle{ n \ge 4 }[/math] (так как [math]\displaystyle{ n^2 - 3n - 1 \ge 0 }[/math]), а [math]\displaystyle{ 2n^2 \le 2n^2 + 3n + 1 }[/math] при [math]\displaystyle{ n \ge 0 }[/math]: подходят [math]\displaystyle{ c_1 = 2 }[/math], [math]\displaystyle{ c_2 = 3 }[/math], [math]\displaystyle{ n_0 = 4 }[/math].
- [math]\displaystyle{ n^{\log_3 3} = n = f(n) }[/math] — случай 2, значит [math]\displaystyle{ T(n) = \Theta(n\log n) }[/math]. Дерево даёт [math]\displaystyle{ \lceil\log_3 n\rceil + 1 }[/math] уровней по [math]\displaystyle{ n }[/math], то есть ту же оценку.
- Условия нарушаются, когда деление не на константу или [math]\displaystyle{ f }[/math] нерегулярна. Для [math]\displaystyle{ T(n) = T(n-1) + n }[/math] дерево вырождается в цепочку: [math]\displaystyle{ T(n) = \sum_{i=1}^{n} i = \Theta(n^2) }[/math].
- При [math]\displaystyle{ +1 }[/math] копирований [math]\displaystyle{ 0 + 1 + 2 + \dots + (n-1) = n(n-1)/2 = \Theta(n^2) }[/math]. При умножении на 2 сумма [math]\displaystyle{ 1 + 2 + 4 + \dots \le 2n }[/math], то есть [math]\displaystyle{ \Theta(n) }[/math] и [math]\displaystyle{ O(1) }[/math] на операцию.
- [math]\displaystyle{ \sum_{i=1}^{n} n \cdot i = n \cdot n(n+1)/2 = \Theta(n^3) }[/math]: средний цикл выполняется [math]\displaystyle{ n }[/math] раз при каждом [math]\displaystyle{ i }[/math], внутренний — [math]\displaystyle{ i }[/math] раз.
- Если искомого нет, нельзя пропустить ни одного элемента: непроверенный элемент мог бы оказаться искомым. В худшем случае нужно [math]\displaystyle{ n }[/math] сравнений, то есть [math]\displaystyle{ \Omega(n) }[/math]; линейный поиск эту границу достигает.
- [math]\displaystyle{ 1000\,n\log_2 n = n^2 }[/math] сводится к [math]\displaystyle{ \log_2 n = n/1000 }[/math], откуда [math]\displaystyle{ n \approx 1{,}37 \cdot 10^4 }[/math]; при больших [math]\displaystyle{ n }[/math] выигрывает [math]\displaystyle{ A }[/math]. До этого порога квадратичный [math]\displaystyle{ B }[/math] быстрее, хотя его асимптотика хуже.
Связанные темы
- Двоичная куча — операции [math]\displaystyle{ O(\log n) }[/math],
build-heapза [math]\displaystyle{ O(n) }[/math]. - Двоичное дерево поиска — операции [math]\displaystyle{ O(h) }[/math], деградация до [math]\displaystyle{ O(n) }[/math].
- Хеш-таблица — средний случай [math]\displaystyle{ O(1) }[/math], худший [math]\displaystyle{ O(n) }[/math].
- Splay-дерево — амортизированные оценки через потенциал.
- Система непересекающихся множеств — амортизированно [math]\displaystyle{ O(\alpha(n)) }[/math].
- Очередь с приоритетом — сводка сложностей операций.
- Графы (план) — [math]\displaystyle{ O(V+E) }[/math] для обходов, нижние границы.
Источники
- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 3 «Growth of Functions», гл. 4 «Divide-and-Conquer» (master theorem), гл. 17 «Amortized Analysis».
- Knuth D. E. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. — Addison-Wesley, 3rd ed., 1997. — §1.2.11 «Asymptotic Representations».
- Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §1.4 «Analysis of Algorithms».
- Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts. — McGraw-Hill, 7th ed., 2019. — глава об оценке стоимости и оптимизации запросов.
- Motwani R., Raghavan P. Randomized Algorithms. — Cambridge University Press, 1995. — ожидаемое время и вероятностный анализ.
- ISO/IEC 14882:2017 (C++17). Complexity requirements for standard algorithms and containers.
- cppreference:
std::vector::push_back(аморт. [math]\displaystyle{ O(1) }[/math]). URL: https://en.cppreference.com/w/cpp/container/vector/push_back. - Aho A. V., Lam M. S., Sethi R., Ullman J. D. Compilers: Principles, Techniques, and Tools. 2nd ed. — Pearson, 2006. — анализ и оптимизации.
- Skiena S. S. The Algorithm Design Manual. 2nd ed. — Springer, 2008. — оценка ограничений и выбор алгоритма.
- Bachmann P. G. H. Die analytische Zahlentheorie. — Teubner, 1894. — введение символа [math]\displaystyle{ O }[/math] (проверено по вторичным источникам).
- Knuth D. E. Big Omicron and Big Omega and Big Theta // SIGACT News. — 1976. — Vol. 8, № 2.
- Tarjan R. E. Amortized Computational Complexity // SIAM J. Algebraic and Discrete Methods. — 1985. — Vol. 6, № 2.
- Bentley J. L., Haken D., Saxe J. B. A General Method for Solving Divide-and-Conquer Recurrences // SIGACT News. — 1980. — Vol. 12, № 3 (master theorem).