Matematyka dyskretna 1/Ćwiczenia 9: Asymptotyka: Różnice pomiędzy wersjami

Wersja z 13:00, 4 wrz 2006

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.

51 n + 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}, 51 n + 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) = 4 T (\frac{n}{2}) + n$

Wskazówka

Rozwiązanie

$a = 4$ , $b = 2$ , $f (n) = n$ ,
$n^{\log_{2} 4} = n^{2}$ , $f (n) \in O (n^{2 - ε})$ , np. dla $ε = 0.5$ ,
zatem, z pierwszego punktu Twierdzenia o rekursji uniwersalnej, mamy $T (n) = Θ (n^{2})$ .

Ćwiczenie 3

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

Wskazówka

Rozwiązanie

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

Ćwiczenie 4

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

Wskazówka

Rozwiązanie

$a = 4$ , $b = 2$ , $f (n) = n^{2} \lg n$ ,
$n^{\log_{2} 4} = n^{2}$ , $f (n) \in Ω (n^{2})$ , ale ...
$f (n) \in̸ Ω (n^{2 + ε})$ dla dowolnego $ε > 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) = 4 T (\frac{n}{2}) + n^{3}$

Wskazówka

Rozwiązanie

$a = 4$ , $b = 2$ , $f (n) = n^{3}$ ,
$n^{\log_{2} 4} = n^{2}$ , $f (n) \in Ω (n^{3 + ε})$ , np. dla $ε = 0.5$ ,
zatem, z trzeciego punktu Twierdzenia o rekursji uniwersalnej, mamy $T (n) = Θ (n^{3})$ .

Ćwiczenie 6

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

Wskazówka

Rozwiązanie

$a = 1$ , $b = 2$ , $f (n) = c$ ,
$n^{\log_{2} 1} = 1$ , $f (n) = Θ (1)$ ,
zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy

$T (n) = Θ (\lg n)$ .

Ćwiczenie 7

Dla

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $a$ taką, że $T^{'} (n) \in O (T (n))$ .

Wskazówka

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

Rozwiązanie

Z Twierdzenia o rekursji uniwersalnej mamy:

T (n) = Θ (n^{\log_{2} 7}) .

Ponadto

\log_{2} 7 \approx 2.807 .

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

jeśli $a < 16$ , to $T^{'} (n)$ podpada pod trzeci punkt Twierdzenia o rekursji uniwersalnej i $T^{'} (n) = Θ (n^{2}) = O (n^{\log_{2} 7})$ ,
jeśli $a = 16$ , to $T^{'} (n)$ podpada pod drugi punkt Twierdzenia o rekursji uniwersalnej i $T^{'} (n) = Θ (n^{2} \lg n) = O (n^{\log_{2} 7})$ ,
jeśli zaś $a > 16$ , to z trzeciego punktu Twierdzenia o rekursji uniwersalnej mamy $T^{'} (n) = Θ (n^{\log_{4} a})$ . Zatem wartości $a$ , przy których $T^{'} (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^{'} (n) = O (T (n))$ jest więc $49$ .

Ćwiczenie 8

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

{(\frac{n}{e})}^{n} < n! ⩽ {(\frac{n}{e})}^{n} \sqrt{n} e .

Wskazówka

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

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

jeśli tylko $n > 0$ .

Rozwiązanie

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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ść ${(\frac{n}{e})}^{n} < n!$ , pochodzącą z założenia indukcyjnego, dostajemy ${(\frac{n + 1}{e})}^{n + 1} < (n + 1)!$ .

@@ Linia 1: / Linia 1: @@
 ==Asymptotyka==
-{{cwiczenie|ex asymptotyka sort||
+{{cwiczenie|1|cw 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.
 <center><math>\displaystyle 51n+101, \quad
@@ Linia 15: / Linia 15: @@
 \sum_{k=0}^n k\sqrt{k}.
 </math></center>
 }}
@@ Linia 20: / Linia 21: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 Porządek ten to:
 <center><math>\displaystyle \frac{\lg{n}}{n}, \quad
@@ Linia 29: / Linia 31: @@
 \frac{n^3}{7\lg^7{n}}.
 </math></center>
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 1||
+{{cwiczenie|2|cw 2|
 Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
 <math>\displaystyle T(n)=4T\left( \frac{n}{2} \right)+n</math>
@@ Linia 46: / Linia 48: @@
 * <math>\displaystyle a=4</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=n</math>,
 * <math>\displaystyle n^{\log_2{4}}=n^2</math>, <math>\displaystyle f(n)\in O(n^{2-\varepsilon})</math>, np. dla <math>\displaystyle \varepsilon=0.5</math>,
-* zatem, z pierwszego punktu Twierdzenia o rekursji uniwersalnej,
+* zatem, z pierwszego punktu Twierdzenia o rekursji uniwersalnej, mamy <math>\displaystyle T(n)=\Theta(n^2)</math>.
-mamy <math>\displaystyle T(n)=\Theta(n^2)</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 2||
+{{cwiczenie|3|cw 3|
 Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
 <math>\displaystyle T(n)=4T\left( \frac{n}{2} \right)+n^2</math>
@@ Linia 65: / Linia 65: @@
 * <math>\displaystyle a=4</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=n^2</math>,
 * <math>\displaystyle n^{\log_2{4}}=n^2</math>, <math>\displaystyle f(n)\in\Theta(n^2)</math>,
-* zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy
+* zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy <math>\displaystyle T(n)=\Theta(n^2\lg{n})</math>.
-<math>\displaystyle T(n)=\Theta(n^2\lg{n})</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 3||
+{{cwiczenie|4|cw 4|
 Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
 <math>\displaystyle T(n)=4T\left( \frac{n}{2} \right)+n^2\lg_2{n}</math>
@@ Linia 89: / Linia 87: @@
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 4||
+{{cwiczenie|5|cw 5|
 Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
 <math>\displaystyle T(n)=4T\left( \frac{n}{2} \right)+n^3</math>
@@ Linia 103: / Linia 100: @@
 * <math>\displaystyle a=4</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=n^3</math>,
 * <math>\displaystyle n^{\log_2{4}}=n^2</math>, <math>\displaystyle f(n)\in\Omega(n^{3+\varepsilon})</math>, np. dla <math>\displaystyle \varepsilon=0.5</math>,
-* zatem, z trzeciego punktu Twierdzenia o rekursji uniwersalnej,
+* zatem, z trzeciego punktu Twierdzenia o rekursji uniwersalnej, mamy <math>\displaystyle T(n)=\Theta(n^3)</math>.
-mamy <math>\displaystyle T(n)=\Theta(n^3)</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka funkcja 5||
+{{cwiczenie|6|cw 6|
 Oszacuj rząd wielkości funkcji <math>\displaystyle T</math> zadanej równaniem rekurencyjnym:
 <math>\displaystyle T(n)=T\left( \frac{n}{2} \right)+c</math>
@@ Linia 122: / Linia 117: @@
 * <math>\displaystyle a=1</math>, <math>\displaystyle b=2</math>, <math>\displaystyle f(n)=c</math>,
 * <math>\displaystyle n^{\log_2{1}}=1</math>, <math>\displaystyle f(n)=\Theta(1)</math>,
 * zatem, z drugiego punktu Twierdzenia o rekursji uniwersalnej, mamy
 <math>\displaystyle T(n)=\Theta(\lg{n})</math>.
 </div></div>
-{{cwiczenie|ex asymptotyka dwie funkcje z parametrem a||
+{{cwiczenie|7|cw 7|
+Dla
-Dla
 <center><math>\displaystyle \aligned T(n)&=7T\left( \frac{n}{2} \right)+n^2,\\
 T'(n)&=aT'\left( \frac{n}{4} \right)+n^2
 \endaligned</math></center>
 wskaż największą całkowitą wartość parametru <math>\displaystyle a</math> taką, że <math>\displaystyle T'(n)\in O(T(n))</math>.
@@ Linia 145: / Linia 141: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
 Z Twierdzenia o rekursji uniwersalnej mamy:
 <center><math>\displaystyle T(n)=\Theta(n^{\log_2{7}}).
 </math></center>
 Ponadto
 <center><math>\displaystyle \log_2 7 \approx 2.807.
 </math></center>
 Przeanalizujmy teraz rząd wielkości funkcji <math>\displaystyle T'(n)</math> w zależności od parametru <math>\displaystyle a</math>:
-* jeśli <math>\displaystyle a<16</math>,
+* jeśli <math>\displaystyle a<16</math>, to <math>\displaystyle T'(n)</math> podpada pod trzeci punkt Twierdzenia o rekursji uniwersalnej i <math>\displaystyle T'(n)=\Theta(n^2)= O(n^{\log_2{7}})</math>,
-to <math>\displaystyle T'(n)</math> podpada pod trzeci punkt Twierdzenia o rekursji uniwersalnej
+* jeśli <math>\displaystyle a=16</math>, to <math>\displaystyle T'(n)</math> podpada pod drugi punkt Twierdzenia o rekursji uniwersalnej i <math>\displaystyle T'(n)=\Theta(n^2\lg{n})= O(n^{\log_2{7}})</math>,
-i <math>\displaystyle T'(n)=\Theta(n^2)= O(n^{\log_2{7}})</math>,
+* jeśli zaś <math>\displaystyle a>16</math>, to z trzeciego  punktu Twierdzenia o rekursji uniwersalnej mamy <math>\displaystyle T'(n)=\Theta(n^{\log_4{a}})</math>. Zatem wartości <math>\displaystyle a</math>, przy których <math>\displaystyle T'(n)=O(T(n))</math> muszą spełniać nierówność
-* jeśli <math>\displaystyle a=16</math>,
-to <math>\displaystyle T'(n)</math> podpada pod drugi punkt Twierdzenia o rekursji uniwersalnej
-i <math>\displaystyle T'(n)=\Theta(n^2\lg{n})= O(n^{\log_2{7}})</math>,
-* jeśli zaś <math>\displaystyle a>16</math>, to z trzeciego  punktu Twierdzenia o rekursji uniwersalnej mamy
-<math>\displaystyle T'(n)=\Theta(n^{\log_4{a}})</math>.
-Zatem wartości <math>\displaystyle a</math>, przy których <math>\displaystyle T'(n)=O(T(n))</math> muszą spełniać nierówność
 <center><math>\displaystyle \log_2{7}\geqslant\log_4{a}=\log_2{\sqrt{a}},
 </math></center>
 czyli <math>\displaystyle 7\geqslant\sqrt{a}</math>, tzn. <math>\displaystyle a\leqslant 49</math>.
@@ Linia 173: / Linia 168: @@
 </div></div>
-{{cwiczenie|ex asymptotyka indukcja||
+{{cwiczenie|8|cw 8|
+Udowodnij przez indukcję, że dla <math>\displaystyle n\geqslant 1</math> zachodzi:
-Udowodnij przez indukcję, że dla <math>\displaystyle n\geqslant 1</math> zachodzi:
 <center><math>\displaystyle \left( \frac{n}{e} \right)^n<n!\leqslant \left( \frac{n}{e} \right)^n\sqrt{n}e.
 </math></center>
 }}
@@ Linia 184: / Linia 180: @@
 <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
 Pomocne może być następujące oszacowanie liczby <math>\displaystyle e</math>:
 <center><math>\displaystyle \left( \frac{n+1}{n} \right)^n<e<\left( \frac{n+1}{n} \right)^{n+\frac{1}{2}},
 </math></center>
 jeśli tylko <math>\displaystyle n>0</math>.
@@ Linia 195: / Linia 193: @@
 Dla <math>\displaystyle n=1</math> mamy <math>\displaystyle \frac{1}{e}<1</math>.
 Wychodząc od lewej nierówności podanej we wskazówce, mamy kolejno:
 <center><math>\displaystyle \aligned \left( \frac{n+1}{n} \right)^n&<e,\\
@@ Linia 200: / Linia 199: @@
 \left( \frac{n+1}{e} \right)^{n+1}\left( \frac{e}{n} \right)^n&<n+1.
 \endaligned</math></center>
 Mnożąc ostatnią nierówność przez nierówność <math>\displaystyle \left( \frac{n}{e} \right)^n<n!</math>,

Matematyka dyskretna 1/Ćwiczenia 9: Asymptotyka: Różnice pomiędzy wersjami

Wersja z 13:00, 4 wrz 2006

Asymptotyka

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia