Асимптотические оценки

Асимптотическая оценка описывает, как растёт время работы (или память) с ростом длины входа, без точных констант. Три оценки: $O$ — сверху, $\Omega$ — снизу, $\Theta$ — с обеих сторон.

Зачем нужно

Точное число тактов вида $3+2N$ зависит от мелочей реализации, а замеры дают ломаную с колебаниями. Сравнивать алгоритмы удобнее по тенденции: растёт ли время как $N$, как $N^2$ или как $\log N$. При $N=10^8$ это разница между секундой и годами.

Как работает

Пусть $g(n)$ — число тактов, $f(n)$ — функция, с которой сравниваем.

O — оценка сверху

$g(n)=O(f(n))$ — «наши данные оценены сверху функцией $f$»:

$$\exists c>0\exists N\in \mathbb{N}\forall n>N:g(n)\le c\cdot f(n)$$

До какого-то N функция $g$ может вести себя как угодно, но дальше она всегда не выше $c\cdot f(n)$.

Ω — оценка снизу

$$g(n)=\Omega (f(n))⟺\exists c>0\exists N\in \mathbb{N}\forall n>N:g(n)\ge c\cdot f(n)$$

Θ — оценка с двух сторон

$$g(n)=\Theta (f(n))⟺\exists c_1,c_2>0\exists N\in \mathbb{N}\forall n>N:c_{1}f(n)\le g(n)\le c_{2}f(n)$$

После N функция $g$ зажата между $c_{1}f(n)$ и $c_{2}f(n)$.

Шкала асимптотик

От медленного роста к быстрому:

Оценка	Название
$O(1)$	константа
$O(\log N)$	логарифм
$O(\sqrt{N})$	корневая
$O(N)$	линейная
$O(N\log N)$
$O(N^2)$
…
$O(N!)$

$O(1)$ означает $g(n)\le c\cdot 1=c$: время ограничено константой и от N не зависит.

При $N=10^8$ и $10^8$ тактах в секунду:

Время работы	Тактов	Секунд
$O(N)$	$\sim 10^8$	1
$O(\sqrt{N})$	$\sim 10^4$	$1/10^4$
$O(\log N)$	$\sim 18$	$18/10^8$
$O(N^2)$	$\sim 10^{16}$	$10^8$

Константы и младшие слагаемые отбрасываются

$O(10\cdot N)=O(N)$: если $f(n)\le c_1\cdot 10\cdot n$, то $f(n)\le c_2\cdot n$ с $c_2=10\cdot c_1$. Множитель уходит в константу из определения.

$O(N^2+N)=O(N^2)$: младшее слагаемое поглощается старшим. Так же $O(3+2N)=O(N)$ в подсчёте для цикла — см. Циклы.

Тонкости

• Основание логарифма может быть любым — так сказали на лекции. Почему — в блоке ниже.
• В определениях важно «существует N, начиная с которого»: на малых входах оценка может не выполняться, и это нормально.
• $O$ не говорит, что алгоритм обязательно работает так долго, — только что не дольше. Точный порядок роста даёт $\Theta$.

Не из лекции: почему основание логарифма не важно

${\log }_{a}N={\log }_{b}N/{\log }_{b}a$ — логарифмы по разным основаниям отличаются постоянным множителем, а он поглощается константой $c$ из определения. Поэтому пишут просто $O(\log N)$.

Частые ошибки

• Путать $O$ (сверху), $\Omega$ (снизу) и $\Theta$ (с обеих сторон).
• Писать константы и основания внутри оценки: $O(2N)$, $O({\log }_{2}N)$.
• Считать, что break в цикле улучшает оценку. В худшем случае он не срабатывает — см. вариант «б» проверки на простоту.

Углубление — АиСД L02

Оценка памяти

Рядом с временем на лекции теперь записывают и память: у разложения на множители, линейного и бинарного поиска $M(N)=O(1)$. Дополнительная память ограничена константой — несколько переменных, сколько бы ни был вход. См. Время работы алгоритма.

Оценка от двух аргументов

У алгоритма Евклида вход — два числа, и оценка зависит от обоих: $T(a,b)=O(a+b)=O(\max (a,b))$ для версии с вычитанием, $T(a,b)=O(\log \max (a,b))$ для версии с остатком.

Не из лекции: почему $O(a+b)=O(\max (a,b))$

$\max (a,b)\le a+b\le 2\max (a,b)$. Функции отличаются не больше чем в 2 раза, а постоянный множитель поглощается константой $c$ из определения.

Откуда берётся логарифм

Если каждый шаг уменьшает задачу вдвое, после $k$ шагов остаётся $N/2^k$. Задача кончается, когда остался один элемент:

$$\frac{N}{2^k}=1\Rightarrow 2^k=N\Rightarrow k={\log }_{2}N$$

Так на лекции получили $T(N)=O(\log N)$ для бинарного поиска.

Сравнение на большом входе

При $N\sim 10^{12}$: $O(N)$ — это $10^{12}$ итераций, около $10^4$ секунд; $O(\log N)$ — $\log 10^{12}\approx 40$ итераций, около $40/10^8$ секунды.

Углубление — АиСД L03

Новые точки на шкале

• $O(N\log \log N)$ — Решето Эратосфена. $\log \log N$ растёт так медленно, что на практике это почти линейное время: при $N=10^8$ $\ln \ln N\approx 2,9$.
• $O(N\cdot N!)$ — тривиальная Сортировка: перемешивать, пока не отсортируется. Уже при $N=20$ это $\sim 10^{18}$ перестановок.

Одна оценка — разное поведение

У трёх квадратичных сортировок на лекции одна и та же оценка $T(N)=O(N^2)$.

Не из лекции: лучший и худший случай

$O$ — оценка сверху на худшем входе, и за ней может прятаться разное. Выбор и пузырёк делают $\Theta (N^2)$ сравнений на любом входе. Вставки делают $\Theta (N^2)$ на массиве по убыванию, но только $N-1$ сравнений на уже отсортированном. Когда важно, что оценка достигается всегда, пишут $\Theta$.

Не из лекции: ожидаемое время

У тривиальной сортировки $O(N\cdot N!)$ — не худший случай, а среднее по случайным перестановкам. Худшего случая у неё нет: может не повезти сколько угодно раз подряд.

Углубление — АиСД L04

$O(N\log N)$

Появляется, когда задачу делят пополам (${\log }_{2}N$ уровней) и на каждом уровне делают линейную работу: $T(N)=O({\log }_{2}N\cdot N)=O(N\log N)$ — Сортировка слиянием.

При $N=10^6$: $N^2=10^{12}$ — около $10^4$ секунд при $10^8$ операций в секунду; $N\log N\approx 10^6\cdot 20=2\cdot 10^7$ — около 0,2 секунды. Здесь ${\log }_{2}10^6=6{\log }_{2}10\approx 20$.

$\Omega$ как оценка для целого класса алгоритмов

Теорема с лекции: никакая сортировка сравнением не работает быстрее $\Omega (N\log N)$. Здесь $\Omega$ ограничивает снизу не один алгоритм, а все алгоритмы определённого вида. Доказательство — в Сортировка.

Не из лекции: что из этого следует

Если у задачи есть нижняя оценка $\Omega (f)$, а у алгоритма — верхняя $O(f)$, алгоритм асимптотически оптимален: лучше сделать нельзя, можно только улучшить константу. Сортировка слиянием — такой алгоритм.