\Section{Асимптотика}{12 сентября}{Сергей Копелиович}

\Subsection{$\O$-обозначния}

\begin{Def}{$f = \O(g)$} \quad
  $\exists N > 0, C > 0 \colon \forall n \ge N, f(n) \le C \cdot g(n)$
\end{Def}

\begin{Def}{$f = \Omega(g)$} \quad
  $\exists N > 0, C > 0 \colon \forall n \ge N, f(n) \ge C \cdot g(n)$
\end{Def}

\begin{Def}{$f = o(g)$} \quad
  $\forall C > 0 \exists N > 0 \colon \forall n \ge N, f(n) \le C \cdot g(n)$
\end{Def}

\begin{Def}{$f = \omega(g)$} \quad
  $\forall C > 0 \exists N > 0 \colon \forall n \ge N, f(n) \ge C \cdot g(n)$
\end{Def}

\begin{Def}{$f = \Theta(g)$} \quad
  $\exists N > 0, C_1 > 0, C_2 > 0 \colon \forall n \ge N, C_1 \cdot g(n) \le f(n) \le C_2 \cdot g(n)$
\end{Def}

\begin{Rem}$f = \Theta(g) \EQ g = \Theta(f)$\end{Rem}
\begin{Rem}$f = \O(g), g = \O(f) \EQ f = \Theta(g)$\end{Rem}
\begin{Rem}$f = \Omega(g) \EQ g = \O(f)$\end{Rem}
\begin{Rem}$f = \omega(g) \EQ g = o(f)$\end{Rem}
\begin{Rem}$f = \O(g), g = \O(h) \SO f = \O(h)$\end{Rem}
\begin{Rem}{Обобщение:} $\forall \beta \in \{\O, o, \Theta, \Omega, \omega\} \colon f = \beta(g), g = \beta(h) \SO \BOX{$f = \beta(h)$}$\end{Rem}

\Subsection{$\O$-обозначния через пределы}

\begin{Def}{$f = o(g)$} \quad Определение через предел:
  $\lim\limits_{n \to \INF} \frac{f(n)}{g(n)} = 0$
\end{Def}
\begin{Def}{$f = \O(g)$} \quad Определение через предел:
  $\overline{\lim\limits_{n \to \INF}} \frac{f(n)}{g(n)} < \INF$
\end{Def}
Здесь необходимо пояснение: $\overline{\lim\limits_{n \to \INF}}f(n) = \lim\limits_{n \to \INF}(\sup\limits_{x \in [n..\INF]} f(x))$, где $\sup$ -- верхняя грань.

\Subsection{Суммы и интегралы}

\begin{Lm}\label{Lm:easyint} $\forall f(x) \nearrow [a..a{+}1] \SO f(a) \le \int\limits_{a}^{a{+}1}f(x)dx \le f(a{+}1)$\end{Lm}

\begin{Lm}\label{Lm:int1} $\forall f(x) \nearrow [a..b{+}1] \SO \sum\limits_{i=a}^b f(i) \le \int\limits_{a}^{b{+}1}f(x)dx$\end{Lm}
\begin{proof} Сложили неравенства из \autoref{Lm:easyint} \end{proof}

\begin{Lm}\label{Lm:int2} $\forall f(x) \nearrow [a..b], f > 0 \SO  \int\limits_{a}^{b}f(x)dx \le \sum\limits_{i=a}^b f(i)$\end{Lm}
\begin{proof} Сложили неравенства из \autoref{Lm:easyint}, выкинули $[a{-}1,a]$ из интеграла. \end{proof}

\begin{Lm}$\forall f(x) \nearrow [a..b{+}1] \int\limits_{a}^{b{+}1}f(x)dx - \sum\limits_{i=a}^b f(i) \le f(b{+}1) - f(a)$\end{Lm}

\begin{Thm}{\emph{Замена суммы на интеграл}}\\
\label{Thm:inttosum} \\
$\forall f(x) \nearrow [1..\infty), f > 0, S(n) = \sum\limits_{i=1}^n f(i), I_1(n) = \int\limits_1^{n}, I_2(n) = \int\limits_1^{n{+}1}, 
I_1(n) = \Theta(I_2(n)) {\bf\SO} \BOX{$S(n) = \Theta(I_1(n))$}$
\end{Thm}
\begin{proof}
Из лемм \autoref{Lm:int1} и \autoref{Lm:int2} имеем $I_1(n) \le S(n) \le I_2(n)$. \\
$C_1 I_1(n) \le I_2(n) \le C_2 I_1(n) \SO I_1(n) \le S(n) \le I_2(n) \le C_2 I_1(n)$
\end{proof}

\Subsection{Примеры}

\THE{Вложенные циклы for}

\begin{code}
#define forn(i, n) for (int i = 0; i < n; i++)
int counter = 0, n = 100;
forn(i, n)
  forn(j, i)
    forn(k, j)
      forn(l, k)
        forn(m, l)
          counter++;
cout << counter << endl;
\end{code}

\noindent{}Чему равен \t{counter}? Во-первых, есть точный ответ: $\binom{n}{5} \approx \mfrac{n^5}{5!}$. Во-вторых, мы
можем сходу посчитать число циклов и оценить ответ как $\O(n^5)$, правда константа $\mfrac{1}{120}$ важна,
оценка через~$\O$ не даёт полное представление о времени работы.

\THE{Число делителей числа}

\begin{code}
vector<int> divisors[n + 1]; // `все делители числа`
for (int a = 1; a <= n; a++)
  for (int b = a; b <= n; b += a)
    divisors[b].push_back(a); 
\end{code}

\noindent{}За сколько работает программа? \\
$\sum\limits_{a=1}^{n}\lceil\mfrac{n}{a}\rceil = \O(n) + \sum\limits_{a=1}^{n}\mfrac{n}{a} = \O(n) + n\sum\limits_{a=1}^{n}\mfrac{1}{a} 
\overset{\autoref{Thm:inttosum}}{=}
\O(n) + n \cdot \Theta(\int\limits_{1}^{n}\mfrac{1}{x}dx) = \Theta(n\log{n})$

\Subsection{Сравнение асимптотик}

\setlength{\tmpwidth}{0.5\textwidth}
\hspace*{-1em}\unskip
\begin{tabular}{ll}
  \parbox{\tmpwidth}{\Def Линейная сложность} & $\O(n)$ \\
  \parbox{\tmpwidth}{\Def Квадратичная сложность} & $\O(n^2)$ \\
  \parbox{\tmpwidth}{\Def Полиномиальная сложность} & $\exists k > 0 \colon \O(n^k)$ \\
  \parbox{\tmpwidth}{\Def Полилогарифм} & $\exists k > 0 \colon \O(\log^k{n})$ \\
  \parbox{\tmpwidth}{\Def Экспоненциальная сложность} & $\exists c > 0 \colon \O(2^{cn})$ \\
\end{tabular}

\vspace*{0.5em}
Попробуем сравнить функции:

\begin{tikzpicture}
\begin{axis}[axis lines = left, xlabel = $n$, ylabel = {$f(n)$},]
\addplot[domain=1:30,samples=100,color=red,]{x};\addlegendentry{$n$}
\addplot[domain=1:6,samples=100,color=blue,]{x^2};\addlegendentry{$n^2$}
\addplot[domain=1:50,samples=100,color=black!50!green,]{x^0.5};\addlegendentry{$\sqrt{n}$}
\addplot[domain=1:50,samples=100,color=black!50!yellow,]{(ln(x))^2};\addlegendentry{$\log^2{n}$}
\addplot[domain=1:10.5,samples=100,color=green!50!blue,]{2^(0.5*x)};\addlegendentry{$2^{n/2}$}
\end{axis}
\end{tikzpicture}

Заметим, что $2^{n/2}, n^2$ и $\log^2n, \sqrt{n}$ на бесконечности ведут себя иначе:

\setlength{\tmpwidth}{0.5\textwidth}
\hspace*{-1em}\unskip
\begin{tabular}{cc}
\parbox{\tmpwidth}{
  \begin{tikzpicture}
  \begin{axis}[axis lines = left, xlabel = $n$, ylabel = {$f(n)$},]
  \addplot[domain=1:50000,samples=100,color=black!50!green,]{x^0.5};\addlegendentry{$\sqrt{n}$}
  \addplot[domain=1:50000,samples=100,color=black!50!yellow,]{(ln(x))^2};\addlegendentry{$\log^2{n}$}
  \end{axis}
  \end{tikzpicture}
}&
\parbox{\tmpwidth}{
  \begin{tikzpicture}
  \begin{axis}[axis lines = left, xlabel = $n$, ylabel = {$f(n)$},]
  \addplot[domain=1:30,samples=100,color=blue,]{x^2};\addlegendentry{$n^2$}
  \addplot[domain=1:30,samples=100,color=green!50!blue,]{2^(0.5*x)};\addlegendentry{$2^{n/2}$}
  \end{axis}
  \end{tikzpicture}
}\\
\end{tabular}

\begin{Thm}{\emph{Сравнение асимптотик}} \quad $\forall a > 0, b > 0, c > 1, \log^b = \O(n^a), n^a = \O(c^n)$
\end{Thm}
\begin{proof} Смотри в следующей лекции... \end{proof}

\vspace*{-0.4em}
\Subsection{Рекуррентности}

\vspace*{-0.4em}
\THE{Пример: алгоритм Карацубы}

Чтобы перемножить два десятичных числа $A$ и $B$ длины $n$, разделим их на части по $k = \mfrac{n}{2}$ цифр -- $A_1, A_2, B_1, B_2$.
Заметим, что $A \cdot B = (A_1 + 10^kA_2)(B_1 + 10^kB_2) = A_1B_1 + 10^k(A_1B_2 + A_2B_1) + 10^{2k}A_2B_2$.
Если написать рекурсивную функцию умножения (числа длины 1 будем умножать за $\O(1)$), то получим время работы:
\begin{formula}
$$T_1(n) = 4T_1(\mfrac{n}{2}) + \Theta(n)$$
\end{formula}
Из последующей теоремы мы сделаем вывод, что $T_1(n) = \Theta(n^2)$.
Алгоритм можно улучшить, заметив, что $A_1B_2 + A_2B_1 = (A_1 + A_2)(B_1 + B_2) - A_1B_1 - A_2B_2$, где
вычитаемые величины уже посчитаны. Итого три умножения вместо четырёх:
\begin{formula}
$$T_2(n) = 3T_2(\mfrac{n}{2}) + \Theta(n)$$
\end{formula}
Из последующей теоремы мы сделаем вывод, что $T_2(n) = \Theta(n^{\log_{2}3}) = \Theta(n^{1.585\dots})$.
\pagebreak

\begin{Lm}{\emph{Доказательство по индукции}}\\
Есть простой метод решения рекуррентных соотношений: угадать ответ, доказать его по индукции.
Рассмотрим на примере $T(n) = \max\limits_{x=1..n{-}1} \bigl(T(x) + T(n-x) + x(n-x)\bigr)$. \\
Докажем, что $T(n) = \O(n^2)$, для этого достаточно доказать $T(n) \le n^2$:\\
База: $T(1) = 1 \le 1^2$.\\
Переход: $T(n) \le \max\limits_{x=1..n{-}1} \bigl(x^2 + (n-x)^2 + x(n-x)\bigr) \le \max\limits_{x=1..n{-}1} \bigl(x^2 + (n-x)^2 + 2x(n-x)\bigr) = n^2$
\end{Lm}

\begin{Thm}{\emph{О простом рекуррентном соотношении}}\\
Пусть $T(n) = aT(\mfrac{n}{b}) + n^c\log^{d}n$. При этом $a > 0, b > 1, c \ge 0, d \in \R$.\\
Определим глубину рекурсии $k = \log_{b}n$, обозначим $f(n) = n^c\log^{d}n$.
Тогда верно одно из трёх:
\begin{formula}\vspace*{0.2em}
$$
\begin{cases}
  T(n) = a^k = n^{\log_{b}a} & a > b^c \\
  T(n) = f(n) & a < b^c \\
  T(n) = k \cdot f(n) & a = b^c \\
\end{cases}
$$
\end{formula}\vspace*{0.2em}
\end{Thm}
\begin{proof}
Раскроем рекуррентность: \\
$T(n) = f(n) + aT(\mfrac{n}{b}) = f(n) + af(\mfrac{n}{b}) + a^2f\bigl((\mfrac{n}{b})^2\bigr) + \dots = n^c\log^{d}n + a\mfrac{n}{b}^c\log^{d}\mfrac{n}{b} + a^2\mfrac{n}{b^2}^c\log^{d}\mfrac{n}{b^2} + \dots$\\
Все полилогарифмы примерно равны, поговорим об этом позже.\\
Тогда $T(n) = f(n)(1 + \mfrac{a}{b^c} + \bigl(\mfrac{a}{b^c}\bigr)^2 + \dots + \bigl(\mfrac{a}{b^c}\bigr)^k)$. При этом в сумме $k+1$ слагаемых.\\
Обозначим $q = \mfrac{a}{b^c}$ и оценим сумму $S(q) = 1 + q + \dots + q^k$. \\
Если $q = 1$, то $S(q) = k + 1 = \log_{b}n + 1 = \Theta(\log_{b}n)$\\
Если $q < 1$, то $S(q) = \mfrac{1 - q^{k{+}1}}{1 - q} = \Theta(1)$\\
Если $q > 1$, то $S(q) = q^k + \mfrac{q^{k} - 1}{q - 1} = \Theta(q^k)$
\end{proof}

\begin{Thm}{\emph{О экспоненциальном рекуррентном соотношении}}\\
Пусть $T(n) = \sum b_iT(n - a_i)$. При этом $a_i > 0, b_i > 0, \sum b_i > 1$.\\
Тогда $T(n) = \Theta(\alpha^n)$, при этом $\alpha$ можно найти бинарным поиском.
\end{Thm}
\begin{proof}
Предположим, что $T(n) = \alpha^n$, тогда \\
$\alpha^n = \sum b_i\alpha^{n-a_i} \EQ 1 = \sum b_i\alpha^{\t{-}a_i} = f(\alpha)$.\\
Если $\alpha = 1$, то $f(\alpha) = \sum b_i > 1$, если $\alpha = \t{+}\infty$, то $f(\alpha) = 0 < 1$. Кроме того $f(\alpha) \nearrow [1,\t{+}\infty)$.
Получаем, что на $[1,\t{+}\infty)$ есть единственный корень уравнения $1 = f(\alpha)$ и его множно найти бинарным поиском.
Теперь можно по индукции доказать, \\
что $T(n) = \O(\alpha^n)$ (оценку сверху) и $T(n) = \Omega(\alpha^n)$ (оценку снизу).
\end{proof}
