Асимптотика (Big O, Ω, Θ, o)
Асимптотика
- Асимптотика — оценка роста функции затрат алгоритма (время или память) при увеличении размера входа \(n\).
- \(f(n)\) — функция затрат алгоритма
- \(g(n)\) — функция сравнения (например, \(n\), \(n^2\), \(\log n\) и т.д.)
Большое O — \(O(f(n))\)
- Верхняя граница роста.
- Алгоритм не будет работать хуже, чем \(O(f(n))\) в худшем случае.
- Формально:
\[
f(n) = O(g(n)) \iff \exists C>0, n_0 : \forall n \ge n_0, f(n) \le C \cdot g(n)
\]
- Примеры:
- Линейный поиск → \(O(n)\)
- Пузырьковая сортировка → \(O(n^2)\)
- Бинарный поиск → \(O(\log n)\)
Большое Ω — \(\Omega(f(n))\)
- Нижняя граница роста.
- Алгоритм будет выполняться как минимум \(\Omega(f(n))\) шагов в лучшем случае.
- Формально:
\[
f(n) = \Omega(g(n)) \iff \exists C>0, n_0 : \forall n \ge n_0, f(n) \ge C \cdot g(n)
\]
- Пример:
- Поиск минимума в массиве → \(\Omega(n)\)
4. Большое Θ — \(\Theta(f(n))\)
- Точная асимптотика.
- Функция растёт как \(g(n)\) сверху и снизу.
- Формально:
\[
f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ и } f(n) = \Omega(g(n))
\]
- Пример:
- Сортировка слиянием → \(\Theta(n \log n)\)
5. Малое o — \(o(f(n))\)
- “Строго меньше”, растёт медленнее, чем \(f(n)\) при \(n \to \infty\)
- Формально:
\[
f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0
\]
- Примеры:
- \(n = o(n^2)\)
- \(\log n = o(n)\)
Типичные функции роста
| Функция | Рост |
|---|---|
| \(O(1)\) | константа |
| \(O(\log n)\) | логарифмическая |
| \(O(n)\) | линейная |
| \(O(n \log n)\) | линейно-логарифмическая |
| \(O(n^2)\) | квадратичная |
| \(O(n^3)\) | кубическая |
| \(O(2^n)\) | экспоненциальная |
| \(O(n!)\) | факториальная |
Таблица популярных алгоритмов и их асимптотики
| Алгоритм / Структура | Худший случай \(O\) | Лучший случай \(\Omega\) | Средний / точный \(\Theta\) |
|---|---|---|---|
| Линейный поиск | \(O(n)\) | \(\Omega(1)\) | \(\Theta(n)\) |
| Бинарный поиск | \(O(\log n)\) | \(\Omega(1)\) | \(\Theta(\log n)\) |
| Сортировка пузырьком | \(O(n^2)\) | \(\Omega(n)\) | \(\Theta(n^2)\) |
| Сортировка вставками | \(O(n^2)\) | \(\Omega(n)\) | \(\Theta(n^2)\) |
| Сортировка слиянием | \(O(n \log n)\) | \(\Omega(n \log n)\) | \(\Theta(n \log n)\) |
| Быстрая сортировка (QuickSort) | \(O(n^2)\) | \(\Omega(n \log n)\) | \(\Theta(n \log n)\) |
| Сортировка кучей (HeapSort) | \(O(n \log n)\) | \(\Omega(n \log n)\) | \(\Theta(n \log n)\) |
| Поиск минимума в массиве | \(O(n)\) | \(\Omega(n)\) | \(\Theta(n)\) |
| Минимальное остовное дерево (Краскал) | \(O(E \log V)\) | \(\Omega(E \log V)\) | \(\Theta(E \log V)\) |
| Минимальное остовное дерево (Прим) | \(O(E \log V)\) | \(\Omega(E \log V)\) | \(\Theta(E \log V)\) |
| Кратчайший путь (Дейкстра) | \(O(V^2)\) / \(O(E+V \log V)\) | \(\Omega(V)\) | \(\Theta(V^2)\) / \(\Theta(E+V \log V)\) |
| Кратчайший путь (Флойд) | \(O(V^3)\) | \(\Omega(V^3)\) | \(\Theta(V^3)\) |
| Динамическое программирование (рюкзак, Фибоначчи) | \(O(n^2)\) / \(O(n)\) | \(\Omega(n^2)\) / \(\Omega(n)\) | \(\Theta(n^2)\) / \(\Theta(n)\) |
| Рекурсия деления пополам | \(O(\log n)\) | \(\Omega(\log n)\) | \(\Theta(\log n)\) |
Легенда:
- \(V\) — количество вершин графа
- \(E\) — количество рёбер
- \(n\) — размер входа (массив, число элементов)
Советы
- Big \(O\) — худший случай
- \(\Omega\) — лучший случай
- \(\Theta\) — средний / точный рост
- \(o\) — “чуть медленнее”, редко спрашивают, но знать нужно
- Часто сравнивают функции через предел:
- \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 \implies f = o(g)\)
- \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = c \neq 0 \implies f = \Theta(g)\)
- \(\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty \implies f = \omega(g)\)
- Принцип подсчёта:
- Берём только самую быстрорастущую часть
- Отбрасываем константы и менее значимые члены
- Это и есть асимптотическая сложность