\Section{Асимптотика}{3 сентября}{Сергей Копелиович} \Subsection{$\O$-обозначния} Рассмотрим функции $f, g \colon \mathbb{N} \to \mathbb{R}^{>0}$. \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{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} Понимание $\Theta$: ``равны с точностью до константы'', ``асимптотически равны''. Понимание $\O$: ``не больше с точностью до константы'', ``асимптотически не больше'' Понимание $o$: ``асимптотически меньше'', ``для сколь угодно малой константы не больше''\\ \begin{tabular}{|c|c|c|c|c|} \hline $\Theta$ & $\O$ & $\Omega$ & $o$ & $\omega$ \\ \hline $=$ & $\le$ & $\ge$ & $<$ & $>$ \\ \hline \end{tabular} \\ \begin{Rem}\label{Rem:Theta} $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} \begin{Rem}\label{Rem:MulConst} $\forall C > 0 \quad C{\cdot}f = \Theta(f)$\end{Rem} Докажем для примера \autoref{Rem:Theta}. \begin{proof} $C_1{\cdot}g(n) \le f(n) \le C_2{\cdot}g(n) \SO \mfrac{1}{C_2}f(n) \le g(n) \le \mfrac{1}{C_1}g(n) \le f(n)$ \end{proof} \begin{Ex}$f = \O(\Theta(\O(g))) \SO f = \O(g)$\end{Ex} \begin{Ex}$f = \Theta(o(\Theta(\O(g)))) \SO f = o(g)$\end{Ex} \begin{Ex}$f = \Omega(\omega(\Theta(g))) \SO f = \omega(g)$\end{Ex} \begin{Ex}$f = \Omega(\Theta(\O(g))) \SO f \text{ может быть любой функцией}$\end{Ex} \begin{Lm}\label{Lm:Add}$g = o(f) \SO f \pm g = \Theta(f)$\end{Lm} \begin{proof} $g = o(f)\ \exists N \colon \forall n \ge N \ g(n) \le \mfrac{1}{2}f(n) \SO \mfrac{1}{2}f(n) \le f(n) \pm g(n) \le \mfrac{3}{2}f(n)$% \SO f \pm g = \Theta(f)$ \end{proof} \begin{Lm}\label{Lm:Polynom}$n^k = o(n^{k+1})$\end{Lm} \begin{proof} $\forall C\,\forall n \ge C \quad n^{k+1} \ge C \cdot n^k$ \end{proof} \begin{Lm} $P(x)$ -- многочлен, тогда $P(x) = \Theta(x^{\t{deg}P})$ при старшем коэффициенте $> 0$. \end{Lm} \begin{proof} $P(x) = a_0 + a_1x + a_2x^2 + \dots + a_kx^k$. По леммам \autoref{Rem:MulConst}, \autoref{Lm:Polynom} имеем, что все слагаемые кроме $a_kx^k$ являются $o(x^{\t{deg}P})$. Поэтому по лемме \autoref{Lm:Add} вся сумма является $\Theta(x^k)$. \end{proof} \begin{comment} \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} Чему равен \t{counter}? Во-первых, есть точный ответ: $\binom{n}{5} \approx \mfrac{n^5}{5!}$. Во-вторых, мы можем сходу посчитать число циклов и оценить ответ как $\O(n^5)$, правда константа $\mfrac{1}{120}$ важна, оценка через~$\O$ не даёт полное представление о времени работы. \THE{Число делителей числа} \begin{code} vector 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} За сколько работает программа? \\ $\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} \end{comment} \pagebreak \vspace*{-1.5em} \Subsection{Рекуррентности и Карацуба} \vspace*{-0.4em} \THE{Алгоритм умножения чисел в столбик} Рассмотрим два многочлена $A(x) = 5 + 4x + 3x^2 + 2x^3 + x^4$ и $B(x) = 9 + 8x + 7x^2 + 6x^3$.\\ Запишем массивы \t{a[] = \{5, 4, 3, 2, 1\}}, \t{b[] = \{9, 8, 7, 6\}}. \begin{code} for (i = 0; i < an; i++) // an = 5 for (j = 0; j < bn; j++) // bn = 4 c[i + j] += a[i] * b[j]; \end{code} Мы получили в точности коэффициенты многочлена $C(x) = A(x)B(x)$. \vspace*{0.5em} Теперь рассмотрим два числа $A = 12345$ и $B = 6789$, запишем те же массивы и сделаем: \begin{code} // Перемножаем числа без переносов, как многочлены for (i = 0; i < an; i++) // an = 5 for (j = 0; j < bn; j++) // bn = 4 c[i + j] += a[i] * b[j]; // Делаем переносы, массив c = [45, 76, 94, 100, 70, 40, 19, 6, 0] for (i = 0; i < an + bn; i++) if (c[i] >= 10) c[i + 1] += c[i] / 10, c[i] %= 10; // Массив c = [5, 0, 2, 0, 1, 8, 3, 8, 0], ответ = 83810205 \end{code} Данное умножение работает за $\Theta(nm)$, или $\Theta(n^2)$ в случае $n = m$. \begin{Cons} Чтобы умножать длинные числа достаточно уметь умножать многочлены. \end{Cons} Многочлены мы храним, как массив коэффициентов. При программировании умножения, нам важно знать не степень многочлена $d$, а длину этого массива $n = d + 1$. \THE{Алгоритм Карацубы} Чтобы перемножить два многочлена (или два длинных целых числа) $A(x)$ и $B(x)$ из $n$ коэффициентов каждый, разделим их на части по $k = \mfrac{n}{2}$ коэффициентов -- $A_1, A_2, B_1, B_2$. \\ Заметим, что $A \cdot B = (A_1 + x^kA_2)(B_1 + x^kB_2) = A_1B_1 + x^k(A_1B_2 + A_2B_1) + x^{2k}A_2B_2$.\\ Если написать рекурсивную функцию умножения, то получим время работы: \begin{smallformula} $$T_1(n) = 4T_1(\mfrac{n}{2}) + \Theta(n)$$ \end{smallformula} Из последующей теоремы мы сделаем вывод, что $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{smallformula} $$T_2(n) = 3T_2(\mfrac{n}{2}) + \Theta(n)$$ \end{smallformula} Из последующей теоремы мы сделаем вывод, что $T_2(n) = \Theta(n^{\log_{2}3}) = \Theta(n^{1.585\dots})$. Данный алгоритм применим и для умножения многочленов, и для умножения чисел. \pagebreak Псевдокод алгоритма Карацубы для умножения многочленов: \begin{code} // n = 2$^k$, c(w) = a(w)*b(w) Mul(n, a, b) { if n == 1: return {a[0] * b[0]} a --> a1, a2 b --> b1, b2 x = Mul(n / 2, a1, b1) y = Mul(n / 2, a2, b2) z = Mul(n / 2, a1 + a2, b1 + b2) // Умножение на w$^i$ - сдвиг массива на i вправо return x + y * w^n + (z - x - y) * w^{n/2}; } \end{code} Чтобы умножить числа, сперва умножим их как многочлены, затем сделаем переносы. \begin{comment} \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} \end{comment} \pagebreak \vspace*{-1.5em} \Subsection{Теоремы о рекуррентных соотношениях} \begin{Thm}{\emph{Мастер Теорема}} (теорема о простом рекуррентном соотношении)\\ Пусть $T(n) = aT(\mfrac{n}{b}) + f(n)$, где $f(n) = n^c$. При этом $a > 0, b > 1, c \ge 0$. Определим глубину рекурсии $k = \log_{b}n$. Тогда верно одно из трёх: \begin{smallformula} $$ \begin{cases} T(n) = \Theta(a^k) = \Theta(n^{\log_{b}a}) & a > b^c \\ T(n) = \Theta(f(n)) = \Theta(n^c) & a < b^c \\ T(n) = \Theta(k \cdot f(n)) = \Theta(n^c \log n) & a = b^c \\ \end{cases} $$ \end{smallformula} \end{Thm} \begin{proof} Раскроем рекуррентность: \\ $T(n) = f(n) + aT(\mfrac{n}{b}) = f(n) + af(\mfrac{n}{b}) + a^2f(\mfrac{n}{b^2}) + \dots = n^c + a(\mfrac{n}{b})^c + a^2(\mfrac{n}{b^2})^c + \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) \SO T(n) = \Theta(f(n)\log n)$.\\ Если $q < 1$, то $S(q) = \mfrac{1 - q^{k{+}1}}{1 - q} = \Theta(1) \SO T(n) = \Theta(f(n))$.\\ Если $q > 1$, то $S(q) = q^k + \mfrac{q^{k} - 1}{q - 1} = \Theta(q^k) \SO T(n) = \Theta(a^k(\mfrac{n}{b^k})^c) = \Theta(a^k)$. \end{proof} \begin{Thm}{\emph{Обобщение Мастер Теоремы}}\\ Мастер Теорема верна и для $f(n) = n^c\log^d n$ \\ $T(n) = aT(\mfrac{n}{b}) + n^c\log^d n$. При $a > 0, b > 1, c \ge 0, d \ge 0$. \begin{smallformula} $$ \begin{cases} T(n) = \Theta(a^k) = \Theta(n^{\log_{b}a}) & a > b^c \\ T(n) = \Theta(f(n)) = \Theta(n^c\log^d n) & a < b^c \\ T(n) = \Theta(k \cdot f(n)) = \Theta(n^c\log^{d+1} n) & a = b^c \\ \end{cases} $$ \end{smallformula} \end{Thm} % \pagebreak \vspace*{-0.5em} Без доказательства.\hspace*{\fill}$\blacksquare$ \begin{Thm}{\emph{Об экспоненциальном рекуррентном соотношении}}\label{Thm:Exp}\\ Пусть $T(n) = \sum b_iT(n - a_i)$. При этом $a_i > 0, b_i > 0, \sum b_i > 1$.\\ Тогда $T(n) = \Theta(\alpha^n)$, при этом $\alpha > 1$ и является корнем уравнения $1 = \sum b_i\alpha^{-a_i}$, его можно найти бинарным поиском. \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)$.\\ Теперь нам нужно решить уравнение $f(\alpha) = 1$ для $\alpha \in [1,\INF)$.\\ Если $\alpha = 1$, то $f(\alpha) = \sum b_i > 1$, если $\alpha = \t{+}\infty$, то $f(\alpha) = 0 < 1$. Кроме того $f(\alpha) \searrow [1,\INF)$. Получаем, что на $[1,\t{+}\infty)$ есть единственный корень уравнения $1 = f(\alpha)$ и его множно найти бинарным поиском. \vspace*{0.5em} Мы показали, откуда возникает уравнение $1 = \sum b_i\alpha^{-a_i}$. Доказали, что у него $\exists!$ корень $\alpha$. Теперь докажем по индукции, что $T(n) = \O(\alpha^n)$ (оценку сверху) и $T(n) = \Omega(\alpha^n)$ (оценку снизу). Доказательства идентичны, покажем $T(n) = \O(\alpha^n)$. База индукции: \begin{smallformula} $$\exists C \colon \forall n \in B = [1 - \max_i a_i, 1] \ \ T(n) \le C\alpha^n$$ \end{smallformula} Переход индукции: \begin{smallformula} $$ T(n) = \sum b_iT(n - a_i) \overset{\text{по индукции}}{\le} C \sum b_i\alpha^{n - a_i} \overset{\t{(*)}}{=} C \alpha^n $$ \end{smallformula} \t{(*)} Верно, так как $\alpha$ -- корень уравнения. \end{proof} \pagebreak \vspace*{-1.5em} \Subsection{Доказательства по индукции} \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} \vspace*{-0.5em} \THE{Примеры по теме рекуррентные соотношения} \begin{MyList} \item $T(n)=T(n-1)+T(n-1)+T(n-2)$. \\ Угадаем ответ $2^n$, проверим по индукции: $2^n = 2^{n-1} + 2^{n-1} + 2^{n-2}$. \item $T(n)=T(n-3)+T(n-3) \SO T(n)=2T(n-3)=4T(n-6)=\dots=2^{n/3}$%\log_3{n}}=n^{\log_3{2}}$ \item $T(n)=T(n-1)+T(n-3)$. Применяем \autoref{Thm:Exp}, получаем $1 = \alpha^{-1} + \alpha^{-3}$, находим $\alpha$ бинпоиском, получаем $\alpha = 1.4655\dots$. \end{MyList} \vspace*{-0.5em} \Subsection{Числа Фибоначчи} \begin{Def}$f_1 = f_0 = 1, f_{i} = f_{i-1} + f_{i-2}$. $f_n$ -- $n$-е число Фибоначчи. \end{Def} \vspace*{-0.5em} \THE{Оценки снизу и сверху} $f_n = f_{n-1} + f_{n-2}$, рассмотрим $g_n = g_{n-1} + g_{n-1}$, $2^n = g_n \ge f_n$. $f_n = f_{n-1} + f_{n-2}$, рассмотрим $g_n = g_{n-2} + g_{n-2}$, $2^{n/2} = g_n \le f_n$. Воспользуемся \autoref{Thm:Exp}, получим $1 = \alpha^{-1} + \alpha^{-2} \EQ \alpha^2 - \alpha - 1 = 0$, получаем $\alpha = \mfrac{\sqrt{5}+1}{2} \approx 1.618$.\\ $f_n = \Theta(\alpha^n)$. \Subsection[*]{$\O$-обозначения через пределы} \begin{Def}{$f = o(g)$} \quad Определение через предел: $\lim\limits_{n \to \INF} \mfrac{f(n)}{g(n)} = 0$ \end{Def} \begin{Def}{$f = \O(g)$} \quad Определение через предел: $\overline{\lim\limits_{n \to \INF}} \mfrac{f(n)}{g(n)} < \infty$ \end{Def} Здесь необходимо пояснение: $\overline{\lim\limits_{n \to \INF}}f(n) = \lim\limits_{n \to \INF}(\sup\limits_{x \in [n..\INF]} f(x))$, где $\sup$ -- верхняя грань. \begin{Lm}Определения $o$ эквивалентны\end{Lm} \begin{proof} Вспомним, что речь о положительных функциях $f$ и $g$.\\ Распишем предел по определению: $\forall C > 0 \quad\exists N \quad\forall n \ge N \quad \mfrac{f(n)}{g(n)} \le C \EQ f(n) \le C g(n)$. \end{proof} \pagebreak \vspace*{-1.5em} \Subsection[*]{Замена сумм на интегралы} \vspace*{-1.2em} \hspace*{-0.7em} \begin{tabular}{ll} \parbox{12cm}{ \begin{Def} Определённый интеграл $\int\limits_{a}^{b}f(x)dx$ положительной функции $f(x)$ -- площадь под графиком $f$ на отрезке $[a..b]$. \end{Def} }& \parbox{6cm}{ \includegraphics[height=3cm]{pic/integral-1.jpg} }\\ \end{tabular} \hspace*{-0.7em} \begin{tabular}{ll} \parbox{10.9cm}{ \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} \up\up \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} }& \parbox{7cm}{ \includegraphics[width=7cm]{pic/integral-2.png} }\\ \end{tabular} \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} \down \begin{Thm} \emph{Замена суммы на интеграл \NO{1}}\\ \up\up \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} \up\up \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} \down \begin{Thm}{\emph{Замена суммы на интеграл \NO{2}}}\\ $\forall f(x) \nearrow [a..b], f > 0\quad\int\limits_{a}^bf(x)dx \le \sum\limits_{i=a}^b f(i) \le f(b) + \int\limits_{a}^bf(x)dx$ \end{Thm} \vspace*{-2em} \begin{proof} Первое неравенство -- лемма \autoref{Lm:int1}. Второе -- \autoref{Lm:int2}, применённая к $\sum\limits_{i=a}^{b-1}$. \end{proof} \up \begin{Cons} Для убывающих функций два последних факта тоже верны. \\ Во втором ошибкой будет не $f(b)$, а $f(a)$, которое теперь больше. \end{Cons} \THE{Как считать интегралы?} Формула Ньютона-Лейбница: $\int\limits_a^b{f'(x)dx} = f(b) - f(a)$ Пример: $\ln'(n) = \frac{1}{n} \SO \int\limits_{1}^{n}\frac{1}{x}dx = \ln{n} - \ln{1} = \ln{n}$ \pagebreak \vspace*{-1.5em} \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} Чему равен \t{counter}? Во-первых, есть точный ответ: $\binom{n}{5} \approx \mfrac{n^5}{5!}$. Во-вторых, мы можем сходу посчитать число циклов и оценить ответ как $\O(n^5)$, правда константа $\mfrac{1}{120}$ важна, оценка через~$\O$ не даёт полное представление о времени работы. \THE{За сколько вычисляется $n$-е число Фибоначчи?} \begin{code} f[0] = f[1] = 1; for (int i = 2; i < n; i++) f[i] = f[i - 1] + f[i - 2]; \end{code} Казалось бы за $\O(n)$. Но это в предположении, что ``\t{+}'' выполняется за $\O(1)$. На самом деле мы знаем, что $\log f_n = \Theta(n)$, т.е. складывать нужно числа длины $n$ $\SO$ ``\t{+}'' выполняется за $\Theta(i)$, а $n$-е число Фибоначчи считается за $\Theta(n^2)$. \THE{Задача из теста про $a^2 + b^2 = N$} \begin{code} int b = sqrt(N); for (int a = 1; a * a <= N; a++) while (a * a + b * b >= N; b--) ; if (a * a + b * b == N) cnt++; \end{code} Время работы $\Theta(N^{1/2})$, так как в сумме $b$ уменьшится лишь $N^{1/2}$ раз. Здесь мы первый раз использовали так называемый ``метод двух указателей''. \THE{Число делителей числа} \begin{code} vector 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} За сколько работает программа? \\ $\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})$ \pagebreak \vspace*{-1.5em} \THE{Сумма гармонического ряда} Докажем более простым способом, что $\sum_{i=1}^{n} \mfrac{1}{i} = \Theta(\log n)$ $1+\lfloor\log_2{n}\rfloor \ge \frac{1}{1} + \overbrace{\frac{1}{2} + \frac{1}{2}}^{1} + \overbrace{\frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4}}^{1} + \overbrace{\frac{1}{8} + \dots }^{1 \dots}\ge $ $\sum\limits_{k=1}^n\frac{1}{k} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \dots \ge $ $\frac{1}{1} + \underbrace{\frac{1}{2}}_{1/2} + \underbrace{\frac{1}{4} + \frac{1}{4}}_{1/2} + \underbrace{\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}}_{1/2} + \dots \ge 1 + \frac{1}{2}\lfloor\log_2{n} \rfloor \SO$ $\sum\limits_{k=1}^n\frac{1}{k} = \Theta(\log n)$ % \pagebreak % \vspace*{-1.5em} \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.6em} \begin{Thm}$\forall x, y > 0, z > 1\ \exists N\ \forall n > N\colon\ \log^x n < n^y < z^n$\end{Thm} \begin{proof} Сперва докажем первую часть неравенства через вторую.\\ Пусть $\log n = k$, тогда $\log^x n < n^y \EQ k^x < 2^{ky} = (2^y)^k = z^k \Leftarrow n^y < z^n \quad\blacksquare$\\ Докажем вторую часть исходного неравенства $n^y < z^n \EQ n < 2^{\frac{1}{y} n \log z}$\\ Пусть $n^\prime = \mfrac{1}{y} n \log z$, обозначим $C = 1 / (\mfrac{1}{y} \log z)$, пусть $C \le n^\prime$ (возьмём достаточно большое $n$), тогда $n^y < z^n \EQ n < 2^{\frac{1}{y} n \log z} \EQ C\cdot n^\prime < 2^{n^\prime} \Leftarrow (n^\prime)^2 < 2^{n^\prime}$\\ Осталось доказать $n^2 < 2^n$. Докажем по индукции. \\ База: для любого значения из интервала $[10..20)$ верно, \\ так как $n^2 \in [100..400) < 2^n \in [1024..1048576)$.\\ Если $n$ увеличить в два раза, то $n^2 \to 4 \cdot n^2$, а $2^n \to 2^{2n} = 2^n \cdot 2^n \ge 4 \cdot 2^n$ при $n \ge 2$.\\ Значит $\forall n \ge 2$ если для $n$ верно, то и для $2n$ верно.\\ %$\forall n \in [10;20)\colon n^2 < 20^2 = 400$; $2^n \ge 2^{10} = 1024 \EQ n^2 < 2^n$\\ Переход: $[10..20) \to [20..40) \to [40..80) \to \dots$ \end{proof} \begin{Cons}$\forall x, y > 0, z > 1\colon\ \log^x {n} = \O(n^y), n^y = \O(z^n)$\end{Cons} \begin{proof}Возьмём константу 1.\end{proof} \begin{Cons}$\forall x, y > 0, z > 1\colon\ \log^x {n} = o(n^y), n^y = o(z^n)$\end{Cons} \begin{proof} Достаточно перейти к чуть меньшим $y$, $z$ и воспользоваться теоремой.\\ $\exists N\, \forall n \ge N\, \log^{x}n < n^{y-\EPS} = \mfrac{1}{n^{\EPS}}n^y$, $\mfrac{1}{n^{\EPS}} \underset{\scriptstyle n \rightarrow \infty}{\rightarrow} 0 \SO \log^x = o(n^y)$.\\ $\exists N\, \forall n \ge N\, n^y < (z-\EPS)^n = \mfrac{1}{{\red{(}z/(z-\EPS)\red{)}}^n}z^n$, $\mfrac{1}{{\red{(}z/(z-\EPS)\red{)}}^n} \underset{\scriptstyle n \rightarrow \infty}{\rightarrow} 0 \SO n^y = o(z^n).$ \end{proof} %\vspace*{0.5em} \pagebreak \vspace*{-1.5em} \THE{Посмотрим как ведут себя функции на графике} \vspace*{1em} \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}$ на бесконечности ведут себя иначе: \vspace*{0.5em} \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}