Matematyka dyskretna 1/Ćwiczenia 9: Asymptotyka

Asymptotyka

Ćwiczenie 1

Posortuj podane niżej funkcje według asymptotycznego stopnia złożoności tak, by każda funkcja była asymptotycznie niemniejsza od następujących po niej.

$51n+101,\frac{n^3}{7{\lg }^{7}n},\frac{n^2+2}{\lg n},(\sqrt{n}+1{)}^3,\frac{\lg n}{n},\frac{n}{\lg n},\sum _{k=0}^{n}k\sqrt{k}$

Wskazówka

Porządek ten to:

$\frac{\lg n}{n},\frac{n}{\lg n},51n+101,(\sqrt{n}+1{)}^3,\frac{n^2+2}{\lg n},\sum _{k=0}^{n}k\sqrt{k},\frac{n^3}{7{\lg }^{7}n}$

Ćwiczenie 2

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T(n)=4T\left(\frac{n}{2}\right)+n$

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

• $a=4$, $b=2$, $f(n)=n$,
• $n^{{\log }_{2}4}=n^2$, $f(n)\in O(n^{2-\epsilon })$, np. dla $\epsilon =0.5$,
• zatem, z pierwszego punktu Twierdzenia o rekursji uniwersalnej, mamy $T(n)=\mathrm{\Theta }(n^2)$.

Ćwiczenie 3

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T(n)=4T\left(\frac{n}{2}\right)+n^2$

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

• $a=4$, $b=2$, $f(n)=n^2$,
• $n^{{\log }_{2}4}=n^2$, $f(n)\in \mathrm{\Theta }(n^2)$,
• zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy $T(n)=\mathrm{\Theta }(n^2\lg n)$.

Ćwiczenie 4

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T(n)=4T\left(\frac{n}{2}\right)+n^2{\lg }_{2}n$

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

• $a=4$, $b=2$, $f(n)=n^2\lg n$,
• $n^{{\log }_{2}4}=n^2$, $f(n)\in \mathrm{\Omega }(n^2)$, ale ...
• $f(n)\in ̸\mathrm{\Omega }(n^{2+\epsilon })$ dla dowolnego $\epsilon >0$,
• nie możemy w tym przypadku zastosować Twierdzenia o rekursji uniwersalnej.

Ćwiczenie 5

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T(n)=4T\left(\frac{n}{2}\right)+n^3$

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

• $a=4$, $b=2$, $f(n)=n^3$,
• $n^{{\log }_{2}4}=n^2$, $f(n)\in \mathrm{\Omega }(n^{3+\epsilon })$, np. dla $\epsilon =0.5$,
• zatem, z trzeciego punktu Twierdzenia o rekursji uniwersalnej, mamy $T(n)=\mathrm{\Theta }(n^3)$.

Ćwiczenie 6

Oszacuj rząd wielkości funkcji $T$ zadanej równaniem rekurencyjnym: $T(n)=T\left(\frac{n}{2}\right)+c$

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

• $a=1$, $b=2$, $f(n)=c$,
• $n^{{\log }_{2}1}=1$, $f(n)=\mathrm{\Theta }(1)$,
• zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy $T(n)=\mathrm{\Theta }(\lg n)$.

Ćwiczenie 7

Dla

$\begin{array}{rl}T(n)& =7T\left(\frac{n}{2}\right)+n^2,\\ T^{\prime }(n)& =a{T}^{\prime }\left(\frac{n}{4}\right)+n^2\end{array}$

wskaż największą całkowitą wartość parametru $a$ taką, że $T^{\prime }(n)\in O(T(n))$.

Wskazówka

Oszacuj asymptotyczny rząd wielkości funkcji $T(n)$ oraz $T^{\prime }(n)$.

Rozwiązanie

Z Twierdzenia o rekursji uniwersalnej mamy:

$T(n)=\mathrm{\Theta }(n^{{\log }_{2}7})$

Ponadto

${\log }_{2}7\approx 2.807$

Przeanalizujmy teraz rząd wielkości funkcji $T^{\prime }(n)$ w zależności od parametru $a$:

• jeśli $a<16$, to $T^{\prime }(n)$ podpada pod trzeci punkt Twierdzenia o rekursji uniwersalnej i $T^{\prime }(n)=\mathrm{\Theta }(n^2)=O(n^{{\log }_{2}7})$,
• jeśli $a=16$, to $T^{\prime }(n)$ podpada pod drugi punkt Twierdzenia o rekursji uniwersalnej i $T^{\prime }(n)=\mathrm{\Theta }(n^2\lg n)=O(n^{{\log }_{2}7})$,
• jeśli zaś $a>16$, to z trzeciego punktu Twierdzenia o rekursji uniwersalnej mamy $T^{\prime }(n)=\mathrm{\Theta }(n^{{\log }_{4}a})$. Zatem wartości $a$, przy których $T^{\prime }(n)=O(T(n))$ muszą spełniać nierówność

${\log }_{2}7⩾{\log }_{4}a={\log }_2\sqrt{a}$

czyli $7⩾\sqrt{a}$, tzn. $a⩽49$.

Największą całkowitą wartością parametru $a$ taką, że $T^{\prime }(n)=O(T(n))$ jest więc $49$.

Ćwiczenie 8

Udowodnij przez indukcję, że dla $n⩾1$ zachodzi:

${\left(\frac{n}{e}\right)}^n<n!⩽{\left(\frac{n}{e}\right)}^n\sqrt{n}e$

Wskazówka

Pomocne może być następujące oszacowanie liczby $e$:

${\left(\frac{n+1}{n}\right)}^n<e<{\left(\frac{n+1}{n}\right)}^{n+\frac{1}{2}},$

jeśli tylko $n>0$.

Rozwiązanie

Pokażemy jedynie indukcyjny dowód nierówności ${\left(\frac{n}{e}\right)}^n<n!$. Dla $n=1$ mamy $\frac{1}{e}<1$. Wychodząc od lewej nierówności podanej we wskazówce, mamy kolejno:

$\begin{array}{rl}{\left(\frac{n+1}{n}\right)}^n& <e,\\ {\left(\frac{n+1}{n}\right)}^n\frac{n+1}{e}& <n+1,\\ {\left(\frac{n+1}{e}\right)}^{n+1}{\left(\frac{e}{n}\right)}^n& <n+1.\end{array}$

Mnożąc ostatnią nierówność przez nierówność ${\left(\frac{n}{e}\right)}^n<n!$, pochodzącą z założenia indukcyjnego, dostajemy ${\left(\frac{n+1}{e}\right)}^{n+1}<(n+1)!$.