Matematyka dyskretna 1/Ćwiczenia 9: Asymptotyka

From Studia Informatyczne

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.


\displaystyle 51n+101, \quad  \frac{n^3}{7\lg^7{n}}, \quad  \frac{n^2+2}{\lg{n}}, \quad  (\sqrt{n}+1)^3, \quad  \frac{\lg{n}}{n}, \quad  \frac{n}{\lg{n}}, \quad \sum_{k=0}^n k\sqrt{k}.


Wskazówka

Porządek ten to:


\displaystyle \frac{\lg{n}}{n}, \quad  \frac{n}{\lg{n}}, \quad  51n+101, \quad  (\sqrt{n}+1)^3, \quad  \frac{n^2+2}{\lg{n}}, \quad  \sum_{k=0}^n k\sqrt{k}, \quad \frac{n^3}{7\lg^7{n}}.


Ćwiczenie 2

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

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

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

Ćwiczenie 3

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

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

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

Ćwiczenie 4

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

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

  • \displaystyle a=4, \displaystyle b=2, \displaystyle f(n)=n^2\lg{n},
  • \displaystyle n^{\log_2{4}}=n^2, \displaystyle f(n)\in\Omega(n^2), ale ...
  • \displaystyle f(n)\not\in\Omega(n^{2+\varepsilon}) dla dowolnego \displaystyle \varepsilon>0,
  • nie możemy w tym przypadku zastosować Twierdzenia o rekursji uniwersalnej.

Ćwiczenie 5

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

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

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

Ćwiczenie 6

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

Wskazówka

Skorzystaj z Twierdzenia o rekursji uniwersalnej.

Rozwiązanie

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

Ćwiczenie 7

Dla


\displaystyle \aligned T(n)&=7T\left( \frac{n}{2} \right)+n^2,\\ T'(n)&=aT'\left( \frac{n}{4} \right)+n^2 \endaligned


wskaż największą całkowitą wartość parametru \displaystyle a taką, że \displaystyle T'(n)\in O(T(n)).

Wskazówka

Oszacuj asymptotyczny rząd wielkości funkcji \displaystyle T(n) oraz \displaystyle T'(n).

Rozwiązanie

Z Twierdzenia o rekursji uniwersalnej mamy:


\displaystyle T(n)=\Theta(n^{\log_2{7}}).


Ponadto


\displaystyle \log_2 7 \approx 2.807.


Przeanalizujmy teraz rząd wielkości funkcji \displaystyle T'(n) w zależności od parametru \displaystyle a:

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


czyli \displaystyle 7\geqslant\sqrt{a}, tzn. \displaystyle a\leqslant 49.

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

Ćwiczenie 8

Udowodnij przez indukcję, że dla \displaystyle n\geqslant 1 zachodzi:


\displaystyle \left( \frac{n}{e} \right)^n<n!\leqslant \left( \frac{n}{e} \right)^n\sqrt{n}e.


Wskazówka

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


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


jeśli tylko \displaystyle n>0.

Rozwiązanie

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


\displaystyle \aligned \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. \endaligned


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