Асимптотическая сложность
Эта глава является вспомогательной для основной части. Здесь содержатся лишь некоторые моменты, облегчающие/углубляющие понимание материала, изложенного по вышеприведённой ссылке.
Свойства степеней
Договоримся, что, записывая \(a^b\), мы подразумеваем, что \(a>0\), а \(b\) — произвольное действительное число.
Полезно помнить следующие алгебраические свойства:
- \(a^x \cdot b^x = (ab)^x\)
- \(a^x \cdot a^y = a^{x+y}\)
- \((a^x)^y = a^{xy} = (a^{y})^x\)
а также — следующие аналитические свойства:
- если \(x>0\), то \(a>b\) равносильно \(a^x > b^x\)
- если \(a>1\), то \(x>y\) равносильно \(a^x > a^y\)
Для равенства \(a=b^x\) используется равносильная запись \(\log_b a = x\). Также договоримся, что по умолчанию \(\log = \log_2\).
Если выписать для основания \(2\) релевантные свойства степеней из вышеприведённого списка, получится следующее:
- \(2^x \cdot 2^y = 2^{x+y}\)
- \((2^x)^y = 2^{xy} = (2^y)^x\)
- \(x>y\) равносильно \(2^x > 2^y\)
Подставляя \(x=\log a\) и \(y=\log b\) в первое и третье свойства, получаем:
- \(ab = 2^{\log a + \log b}\)
- \(\log a > \log b\) равносильно \(a > b\)
Применяя к первому из получившихся свойств логарифм, получаем
- \(\log (ab) = \log a + \log b\)
Наконец, подставляя \(y=\log a\) во второе из свойств степеней двойки, получим
- \(a^x = 2^{x\log a}\)
из чего, применяя к обеим частям логарифм, получаем
- \(\log (a^x) = x\log a\)
Итого свойства степеней в терминах логарифмов выглядят так:
- \(\log (ab) = \log a + \log b\)
- \(\log (a^x) = x\log a\)
- \(a > b\) равносильно \(\log a > \log b\)
Немного неравенств
Начнём со вспомогательного неравенства
\[2^x > x\]
При \(x\lt 1\) оно очевидно, а при \(x\geqslant 1\) оно следует из неравенства Юнга
\( (1+1)^x \geqslant 1 + x\cdot 1 \)
Само неравенство Юнга для рациональных степеней является следствием неравенства Коши о средних, а для иррациональных следует из соображений монотонности.
Теперь сформулируем и докажем очень важное неравенство.
Асимптотическое неравенство между степенью и логарифмом
Для любого \(a > 0\) существует \(X\) такой, что при всех \(x > X\) выполнено
\[ x^{a} > \log x \]
Доказательство
Поскольку
\[ \log x = \log (x^a)^{1/a} = \frac{1}{a} \log (x^a) \]
то нам достаточно доказать, что есть такое \(Y\), что для всех \(y > Y\) выполнено
\[ y > \frac{1}{a} \log y \]
Но это неравенство эквивалентно
\[ 2^{ay} > y = \frac{ay}{a} \]
Поэтому нам достаточно доказать, что есть такое \(Z\), что для всех \(z > Z\) выполнено
\[ 2^z > \frac{z}{a} \]
Пусть \(z = \frac{2}{a} + h\). Тогда
\[ 2^z = 2^{2/a} \cdot 2^h > \frac{2}{a} \cdot h \]
Осталось обеспечить
\[ 2h > \frac{2}{a} + h \]
выбором
\[ Z = \frac{2}{a} + \frac{2}{a} = \frac{4}{a} \]
Замечание
Вообще говоря, для разговора об асимптотической сложности достаточно доказать более слабое утверждение о том, что для любого \(a > 0\) существуют \(X\) и \(k>0)) такие, что при всех \(x > X\) выполнено
\[ x^{a} > k\log x \]
Для его доказательства достаточно выбрать \(k=a\) и перейти к эквивалентному (при замене \(y=x^a\)) неравенству
\[ y > \log y \]
которое следует из \(2^y > y\).
Классы асимптотической сложности
Пусть функция \(f\) является нижней асимптотической оценкой для \(g\): а именно, существуют такие \(X\) и \(k>0\), что для всех \(x>X\) выполнено
\[ k f(x) \lt g(x) \]
Заметим, что при этом \(g\) является верхней асимптотической оценкой для \(f\): для тех же \(x\) выполнено
\[ f(x) \lt \frac{1}{k} g(x) \]
Договоримся любую из этих ситуаций (а, следовательно, и обе) обозначать \(f\prec g\).
Для отношения \(\prec\) выполнены следующие свойства:
- рефлексивность: \(f\prec g\)
- транзитивность: из \(f\prec g\) и \(g\prec h\) следует \(f\prec h\)
Если \(f\prec g\) и \(g\prec f\), будем говорить, что \(f\) и \(g\) асимптотически эквивалентны и обозначать это \(f\equiv g\).
Поскольку отношение \(\equiv\) симметрично, то его можно рассматривать как рёбра графа, вершинами которого являются всевозможные функции (натурального аргумента). Компоненты связности этого графа мы будем называть классами сложности.
Очевидно, что если есть неравенство \(f\prec g\) между представителями классов сложности \(F\) и \(G\), то такое же неравенство есть между любой парой представителей этих классов. Поэтому, записывая, напимер, \(\log n\prec n\) мы будем этой записью подразумевать высказывание «любой представитель класса сложности логарифма является нижней асимптотической оценкой для любого представителя класса сложности линейной функции».
Нижеприведённые соотношения между классами (следующие из неравенства, доказанного в предыдущем разделе) полезно помнить: для всех \(a > 0\) и \(b > 0\)
- \(1 \prec (\log n)^a\)
- \((\log n)^a \prec n^b\)
- \(n^a \prec 2^{n^b}\)
Все эти неравенства строгие: ни одна из указанных пар классов не совпадает.