02.10.082 Анализ высшего уровня(*) - justjune/AiSD2026 GitHub Wiki

Факультативный материал помогает понять некоторые функции временной сложности, рассматриваемые во второй части книги Скиена

Малораспространенные функции

• Обратная функция Аккермана: $f(n) = \alpha(n)$

Эта функция появляется в подробном анализе нескольких алгоритмов, в особенности в структурах данных объединение — поиск(раздел 8.1.3). Её следует воспринимать как технический термин для самой медленно возрастающей функции сложности алгоритмов. В отличие от функций-констант, $f(n) = 1$, $\alpha(n)$ достигает бесконечности при $n \to \infty$, но она определенно не торопится сделать это. Для любого значения $n$ в физической вселенной значение $\alpha(n)$ будет меньше 5.

• $f(n) = \log \log n$

Смысл функции «логарифм логарифма» очевиден по её имени — это логарифм логарифма числа $n$. Одним из естественных примеров её возникновения будет двоичный поиск в отсортированном массиве из всего лишь $\log n$ элементов.

• $f(n) = \log n / \log \log n$

Эта функция возрастает немного медленнее, чем функция $\log n$, т. к. она содержит в знаменателе еще более медленно растущую функцию. Чтобы понять, как возникла эта функция, рассмотрим корневое дерево с количеством потомков $d$, имеющее $n$ листьев. Высота двоичных корневых деревьев ($d = 2$) определяется формулой: $$n = 2^h \implies h = \log n.$$ Рассмотрим теперь высоту дерева, когда количество потомков равно $d = \log n$. Тогда высота определяется такой формулой: $$n = (\log n)^h \implies h = \log n / \log \log n.$$

• $f(n) = \log^2 n$

Это произведение двух логарифмических функций, т. е. $(\log n) \times (\log n)$. Такая функция может возникнуть, если мы хотим подсчитать просмотренные биты в процессе двоичного поиска в множестве из $n$ элементов, каждый из которых является целым числом в диапазоне от 1 до $n$. Для представления каждого из этих чисел требуется $\log(n^2) = 2 \log n$ битов, а поскольку количество чисел в множестве поиска равно $\log n$, общее количество битов будет равно $2 \log^2 n$.

• $f(n) = \sqrt{n}$

Функция квадратного корня встречается не так уж редко, но представляет класс «субквадратичных полиномов», поскольку $\sqrt{n} = n^{1/2}$. Такие функции возникают при построении $d$-мерных сеток, содержащих $n$ точек. Площадь квадрата размером $\sqrt{n} \times \sqrt{n}$ равна $n$, а объем куба размером $n^{1/3} \times n^{1/3} \times n^{1/3}$ также составляет $n$. В общем, объем $d$-мерного гиперкуба со стороной $n^{1/d}$ составляет $n$.

• $f(n) = n^{1+\epsilon}$

Греческая буква $\epsilon$ обозначает константу, которая может быть сколь угодно малой, но при этом не равняется нулю. Она может возникнуть в следующих обстоятельствах. Допустим, время исполнения алгоритма равно $2^\epsilon n^{1+\epsilon}$, и мы можем выбирать любое значение для $\epsilon$. При $\epsilon = 2$ время исполнения будет $4n^3$, или $O(n^3)$. При $\epsilon = 3$ время исполнения будет $8n^4$, или $O(n^4)$, что уже лучше. Действительно, чем больше значение $\epsilon$, тем лучше становится показатель степени. Но $\epsilon$ нельзя делать как угодно большим (до того как член $2^\epsilon$ станет доминировать). Вместо этого мы обозначаем время исполнения этого алгоритма как $O(n^{1+\epsilon})$ и предоставляем пользователю определить наилучшее значение для $\epsilon$.

Пределы и отношения доминирования

Говорят, что функция $f(n)$ доминирует над функцией $g(n)$, если $\lim_{n \to \infty} g(n)/f(n) = 0$.

$$n! \gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \log n \gg n \gg \sqrt{n} \gg \log^2 n \gg \log n \gg \log n / \log \log n \gg \log \log n \gg \alpha(n) \gg 1.$$