Асимптотика
- Асимптотика — оценка роста функции затрат алгоритма (время или память) при увеличении размера входа $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)$
- Принцип подсчёта:
- Берём только самую быстрорастущую часть
- Отбрасываем константы и менее значимые члены
- Это и есть асимптотическая сложность