% Разбор задач практики 07.09.15 \Section{Разбор задач практики} \vspace*{-1em} \begin{MyList} \setlength{\itemsep}{0.5em} \item {\bf Простые задачи на асимптотику.}\\ Найдите запись через $\Theta$. Если не существует, объяснить, почему, и записать через $\O$. \begin{InnerMyList}[4pt] \item $2n = \Theta(n)$, по определению =) \item $f(n) = 2n+1$,\\ $\forall n \in \N \quad n \le 2n + 1 \le 2n + n \le 3n \SO f(n) = \Theta(n)$. \item $f(n) = n^2 + 5n + 1$,\\ $\forall n \in \N \quad n^2 \le f(n) \le n^2 + 5n^2 + n^2 = 7n^2 \SO f(n) = \Theta(n^2)$. Способ \NO{2}: $5n + 1 = \O(n^2) \SO 5n + 1 = \alpha n^2 \SO f(n) \le (1 + \alpha)n^2 \SO f(n) = \Theta(n^2)$. \item $f(n) = \dfrac{n^2+3}{7n+1}$,\\ Поделим числитель на знаменатель: $f(n) = (\tfrac{1}{7}n - \tfrac{1}{49}) + \underbrace{\dfrac{3 - \tfrac{1}{49}}{7n + 1}}_\text{беск. малая} \SO f(n) = \Theta(n)$. Способ \NO{2}: $\dfrac{n^2}{7n+n} \le f(n) \le \dfrac{n^2+n^2}{7n} \SO \tfrac{1}{8}n \le f(n) \le \tfrac{2}{7}n$. \item $f(n) = n(2 + \sin n)$,\\ $-1 \le \sin n \le 1 \SO 1 \le 2 + \sin n \le 3 \SO n \le f(n) \le 3n \SO f(n) = \O(n)$. \item $f(n) = \frac{\arctg n}{n} + \frac{\log \log n}{\log n}$,\\ Пусть $g(n) = \dfrac{\log \log n}{\log n}$.\\ $\arctan n < \tfrac{\pi}{2} < \log \log n,\ n > \log n \SO f(n) \le 2g(n) = \Theta(g(n))$. \item Докажите: $\forall f, g > 0 \colon f + g = \Theta(\max(f, g))$,\\ $\forall n \in \N \quad \max(f(n), g(n)) \le f(n) + g(n) \le 2 \max(f(n), g(n))$. \end{InnerMyList} \item {\bf Истина или ложь?}\\ Проверьте корректность, докажите. \begin{InnerMyList}[4pt] \item $2^{n+3} = \Theta(2^n)$,\\ Верно: $2^{n+3} = 8\cdot 2^n = \Theta(2^n)$. \item $2^{2n+1} = \Theta(2^n)$,\\ Неверно, что $2^{2n+1} = \O(2^n)$, докажем от противного.\\ Предположим, что $\forall n \ge N \quad 2^{2n+1} \le c \cdot 2^n \SO 2^{n + 1} \le c \SO n \le \log c - 1$. Противоречие. \item $g(n) = \O(f(n)) \SO 2^{g(n)} = \O(2^{f(n)})$,\\ Неверно, возьмём $f(n) = 2n + 1,\ g(n) = n$. Получим условие предыдущей задачи. \item $g(n) = o(f(n)) \SO 2^{g(n)} = o(2^{f(n)})$,\\ Верно, если $f(n) \xrightarrow[n \to \infty]{} +\infty$. $g(n) = o(f(n)) \EQ \tfrac{g(n)}{f(n)}\xrightarrow[n \to \infty]{} 0$. $\dfrac{2^{g(n)}}{2^{f(n)}} = 2^{g(n) - f(n)}$, но $f(n) - g(n) = f(n) - f(n) \cdot \tfrac{g(n)}{f(n)} = f(n)\left(1 - \tfrac{g(n)}{f(n)}\right) \ge 0.5f(n)$. $2^{g(n) - f(n)} \le \dfrac{1}{2^{0.5f(n)}} \xrightarrow[n \to \infty]{} 0$. \vspace{5mm} \underline{Способ \NO{2}:} $2^{g(n)} < c\cdot 2^{f(n)} \EQ g(n) < \log c + f(n)\ (*)$, но $\forall c_1 > 0 \quad g(n) < c_1 \cdot f(n)$, значит\\ $(*) \Leftarrow c_1 \cdot f(n) < \log c + f(n) \EQ (1 - c_1)f(n) > -\log c \stackrel{c_1 < 1}{\iff} f(n) > \dfrac{-\log c}{1 - c_1}$. Возьмём $c_1 = \tfrac{1}{2}$, тогда $\exists N \quad \forall n \ge N \quad f(n) > -2\log c \SO 2^{g(n)} < c\cdot 2^{f(n)}$. Таким образом, $\forall c > 0 \quad \exists N \quad \forall n \ge N \quad 2^{g(n)} < c\cdot 2^{f(n)}$. \item $g(n) = \O(f(n)) \SO \log{g(n)} = \O(\log{f(n)})$,\\ Верно, если $f(n) \xrightarrow[n \to \infty]{} +\infty$. $\log{g(n)} < c \cdot \log{f(n)} \EQ g(n) < \left( f(n) \right)^c$. $g(n) = \O(f(n)) \EQ \exists c_1 > 0 \quad g(n) < c_1 f(n)$, таким образом $g(n) < (f(n))^c \Leftarrow c_1 f(n) < (f(n))^c \EQ (f(n))^{c-1} > c_1$~--- верно, если $f(n) \to +\infty$ и $c > 1$. \item $g(n) = o(f(n)) \SO \log{g(n)} = o(\log{f(n)})$,\\ Неверно, при $f(n) \to +\infty$. $\log{g(n)} < c\log{f(n)} \EQ g(n) < (f(n))^c$. $g(n) = o(f(n)) \EQ \forall c_1 > 0 \quad g(n) < c_1 f(n)$, таким образом $g(n) < (f(n))^c \Leftarrow c_1 f(n) < (f(n))^c \EQ (f(n))^{c-1} > c_1 \EQ (c - 1) \log f(n) > \log c_1$. Это неверно, если $f(n) \to +\infty$ и $c < 1$, так как\\ $\log f(n)$ не может быть ограничен сверху числом $\dfrac{\log c_1}{c - 1}$. \item $f(n) + g(n) = \Theta(\frac{f(n) + g(n)}{2})$, верно по определению. \item $n^2 = \O(2^n)$,\\ Верно, так как $\dfrac{n^2}{2^n} \xrightarrow[n \to \infty]{} 0 \SO n^2 = o(2^n) \SO n^2 = \O(2^n)$. \item $\log n = o(\mfrac{n}{\log n})$,\\ Верно: $\log n = o(\mfrac{n}{\log n}) \EQ \log n < c \cdot \dfrac{n}{\log n} \EQ \log^2 n = n \EQ \log^2 n = o(n)$. Сделаем замену переменной $n = 2^y$, получим $y^2 = o(2^y)$, верное по предыдущему пункту. \item $\mfrac{n}{\log n} = \Theta(0.5 \cdot n)$,\\ Неверно: $\mfrac{n}{\log n} = \Theta(0.5 \cdot n) \EQ n = \Theta(n\log n) \SO n\log n = \O(n)$. Если $n\log n < c \cdot n$, то $\log n < c$, что неверно, в силу неограниченности $\log n$. \end{InnerMyList} \item {\bf Реккурентность} \begin{InnerMyList}[4pt] \item $T(n) = 2T(\mfrac{n}{2}) + 1$,\\ $2^k = n \EQ k = \log n$ $T(n) = 2T(\mfrac{n}{2}) + 1 = 2(2T(\mfrac{n}{4}) + 1) + 1 = \underbrace{2(2(2(\dots(2}_\text{k двоек}T(\mfrac{n}{2^k}) + \underbrace{1) \dots) + 1) + 1) + 1}_\text{k единиц}$. Раскроем скобки: $2^k + 2^{k - 1} + \dots + 2^1 + 1 = 2^{k+1} - 1 = 2n - 1 = \Theta(n)$. Способ \NO{2} (по теореме): $a = 2, b = 2, c = 0, f(n) = 1 = \Theta(n^c), c < \log_ba \SO T(n) = \Theta(n)$. \item $T(n) = 3T(\mfrac{n}{2}) + n^2$,\\ $2^k = n \EQ k = \log n$ $T(n) = 3T(\mfrac{n}{2}) + n^2 = 3(3T(\mfrac{n}{2^2}) + (\mfrac{n}{2^1})^2) + (\mfrac{n}{2^0})^2 = \\ = \underbrace{3(3(3(\dots(3}_\text{k троек}T(\mfrac{n}{2^k}) + \underbrace{(\mfrac{n}{2^{k-1}})^2) \dots) + (\mfrac{n}{2^2})^2) + (\mfrac{n}{2^1})^2) + (\mfrac{n}{2^0})^2}_\text{k штук} = \\ = 3^k + 3^{k-1}(\mfrac{n}{2^{k-1}})^2 + 3^{k-2}(\mfrac{n}{2^{k-2}})^2 + \dots + 3(\mfrac{n}{2^1})^2 + 1\cdot (\mfrac{n}{2^0})^2 = \\ = n^2((\mfrac{3}{4})^k + (\mfrac{3}{4})^{k-1} + (\mfrac{3}{4})^{k-2} + \dots + \mfrac{3}{4} + 1) \le n^2\sum\limits_{k=0}^{\infty}{(\mfrac{3}{4})^k} = n^2 \dfrac{1}{1 - \mfrac{3}{4}} = 4n^2 \SO \\ n^2 \le T(n) \le 4n^2 \SO T(n) = \Theta(n^2)$. Способ \NO{2} (по теореме):\\ $a = 3, b = 2, c = 2, f(n) = \Omega(n^2), c > \log_ba, 3(\mfrac{n}{2})^2 \le \mfrac{3}{8}n^2 \SO T(n) = \Theta(n^2)$. \item $T(n) = 5T(\mfrac{n}{2}) + n$,\\ $2^k = n \EQ k = \log n$ $T(n) = 5T(\mfrac{n}{2}) + n = 5(5T(\mfrac{n}{2^2}) + \mfrac{n}{2^1}) + \mfrac{n}{2^0} = \\ = \underbrace{5(5(5(\dots(5}_\text{k штук}T(\mfrac{n}{2^k}) + \underbrace{\mfrac{n}{2^{k-1}}) \dots) + \mfrac{n}{2^2}) + \mfrac{n}{2^1}) + \mfrac{n}{2^0}}_\text{k штук} = \\ = 5^k + 5^{k-1}\mfrac{n}{2^{k-1}} + 5^{k-2}\mfrac{n}{2^{k-2}} + \dots + 5\mfrac{n}{2^1} + 1\cdot \mfrac{n}{2^0} = \\ = n((\mfrac{5}{2})^k + (\mfrac{5}{2})^{k-1} + (\mfrac{5}{2})^{k-2} + \dots + \mfrac{5}{2} + 1) = n\sum\limits_{i=0}^{k}{2.5^i} = n \dfrac{2.5^{k+1} - 1}{2.5 - 1} = \Theta(n \cdot 2.5^k)$. $2.5^k = 2.5^{\log n} = 2^{\log(2.5^{\log n})} = 2^{\log n \cdot \log 2.5} = n^{\log 2.5} \SO \\ T(n) = \Theta(n^{1 + \log 2.5}) = \Theta(n^{\log 2 + \log 2.5}) = \Theta(n^{\log 5})$. Способ \NO{2} (по теореме):\\ $a = 5, b = 2, c = 1, f(n) = \O(n^1), c < \log_ba \SO T(n) = \Theta(n^{\log_b a}) = \Theta(n^{\log_2 5})$. \item $T(n) = 2T(\mfrac{n}{2}) + n\log n$,\\ $a = 2, b = 2, f(n) = \Theta(n^1 \log^1 n), c = \log_ba = 1 \SO T(n) = \Theta(n^c \log^{1+1} n) = \Theta(n\log^2 n)$. \item $T(n) = 3T(\mfrac{n}{3}) + n$,\\ $a = 3, b = 3, f(n) = \Theta(n^1 \log^0 n), c = \log_ba = 1 \SO T(n) = \Theta(n \log^{0+1} n) = \Theta(n\log n)$. \item $T(n) = T(n{-}1) + T(n{-}1) + 1$,\\ $T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = 2(2\dots (2T(1) + 1) + \dots + 1) + 1 =\\ = 2^{n-1} + \dots + 2^1 + 1 = 2^{n} - 1 = \Theta(2^n)$. Можно доказать это и по индукции, посмотрев на первые несколько членов. \end{InnerMyList} \end{MyList}