Matematyka dyskretna 1/Wykład 9: Asymptotyka

From Studia Informatyczne

Widzieliśmy już, że wskazanie postaci zwartej dla ciągu zadanego równaniem rekurencyjnym jest często zadaniem niełatwym. Do tej pory nie jest znana zwarta postać wielu równań. Na szczęście często jesteśmy w sytuacji, w której zadowoli nas przybliżenie odpowiedzi. Wróćmy do rozważanej wielokrotnie sumy kolejnych kwadratów \displaystyle \sum_{i=0}^ni^2. Fakt, że jest to wielomian 3-go stopnia zmiennej n, to już wartościowa informacja, często zupełnie wystarczająca. Spotkaliśmy się już nie raz z oszacowaniami poprzez zwykłe nierówności. To podejście często wymaga użycia narzędzi z analizy matematycznej, w szczególności znajdowania ekstremum funkcji.

Przykład

Silnię liczby naturalnej można trywialnie oszacować przez n!=1\cdot\ldots\cdot n\leq n^n. Przyjrzyjmy się delikatniejszemu oszacowaniu wskazującemu także dolne ograniczenie na n!.

Najpierw zauważmy, że


\displaystyle (n!)^2=(1\cdot\ldots\cdot n)(n\cdot\ldots\cdot1)=\prod_{i=1}^ni(n+1-i).


Potraktujmy i(n+1-i)=\frac{1}{4}(n+1)^2-(i-\frac{1}{2}(n+1))^2 jako wielomian drugiego stopnia zmiennej i. Łatwo zauważyć, że dla i\in[1,\ldots,n] przybiera on najmniejszą wartość w punkcie i=1, a największą w punkcie i=\frac{1}{2}(n+1). Zatem dla i\in{\left\{ {1,\ldots,n} \right\}\ } mamy n\leq i(n+1-i)\leqslant\frac{1}{4}(n+1)^2 i dalej


n^n\leqslant(n!)^2\leqslant\left(\frac{1}{4}(n+1)^2\right)^n,


czyli


n^{\frac{n}{2}}\leq n!\leqslant\left(\frac{n+1}{2}\right)^n.


Nierówności w oszacowaniach bywają niepotrzebnie krępujące. Zaś wyniki w ten sposób otrzymane, często skupiają naszą uwagę na zbędnych i czasem nieinteresujących detalach. Często bowiem wystarczają nam przybliżone, asymptotyczne oszacowania ciągów lub ogólniej funkcji. Opisują one zachowanie funkcji wraz ze wzrostem argumentu. Podczas przekształceń rachunkowych celowo ograniczamy naszą wiedzę o funkcji, dzięki czemu łatwiej jest rachować i otrzymać zadowalającą postać przybliżającą.

W oszacowaniach asymptotycznych posługujemy się ogólnie przyjętymi symbolami opisującymi asymptotyczne zachowanie jednej funkcji wobec drugiej. Najpowszechniej używany jest symbol O przydatny w analizie górnej granicy asymptotycznej. Po raz pierwszy tego symbolu użył niemiecki teorio-liczbowiec Paul Bachmann w 1894. Prace Edmunda Landau'a (także niemieckiego teorio-liczbowca) spopularyzowały tę notację, stąd czasami O jest nazywany symbolem Landau'a. Notację asymptotyczną wprowadzimy jedynie dla funkcji zdefiniowanych na zbiorze \mathbb{N} (lub jego podzbiorach postaci \mathbb{N}-\mathbb{Z}_k) o wartościach w \mathbb{R}.

Notacja asymptotyczna



SW_7.1.swf

Funkcja asymptotycznie niewiększa od funkcji g(n) to taka funkcja f: \mathbb{N} \longrightarrow \mathbb{R}, dla której istnieją c>0 i n_0\in\mathbb{N}, że \left\vert f(n)\right\vert\leq c\cdot\left\vert g(n)\right\vert dla wszystkich n\geq n_0.
Będziemy też często mówić, że \left\vert f(n)\right\vert\leq c\cdot\left\vert g(n)\right\vert zachodzi dla prawie wszystkich liczb naturalnych n.
Zbiór funkcji asymptotycznie niewiększych niż g(n) oznaczamy przez O(g(n)).

Ponieważ O(g(n)) jest zbiorem funkcji, poprawnie powinniśmy zapisywać f(n)\in O(g(n)), gdy f spełnia warunek podany w definicji. Jednak przyjęło się zapisywać f(n)=O(g(n)). Jest to pewne nadużycie symbolu równości =. Jednak tradycja, a jak się niebawem okaże, również i wygoda użycia, są wystarczającym usprawiedliwieniem dla tego nadużycia. W związku z tym napis f(n)=O(g(n)) czytamy "f(n) jest O-duże od g(n)".

Przykład

  • O(1), to zbiór funkcji ograniczonych.

Istotnie warunek \left\vert f(n)\right\vert\leq c zachodzący dla prawie wszystkich n łatwo jest, poprzez zamianę stałej c na inną c', sprowadzić do warunku \left\vert f(n)\right\vert\leq c' zachodzącego już dla wszystkich n\in\mathbb{N}, jako że skończenie wiele wartości \left\vert f(n)\right\vert dla początkowych n daje się ograniczyć przez stałą.

    • każda funkcja stała jest O(1) np. f(n)=1000 jest O(1), bo \left\vert f(n)\right\vert=1000\leqslant1000 dla dowolnego n,
    • (-1)^n=O(1), bo \left\vert (-1)^n\right\vert\leqslant 1 dla dowolnego n,
    • \frac{1}{n}=O(1), bo \frac{1}{n}\leq 1 dla dowolnego n\geqslant 1,
    • \frac{\log{n}}{n}=O(1), bo \log{n}<n dla n\geqslant 1, zatem \frac{\log{n}}{n}\leqslant 1 dla n\geqslant 1.
  • O(n) to zbiór funkcji ograniczonych przez funkcję liniową:
    • wszystkie funkcje O(1) są też O(n),
    • 10n+25=O(n), bo \left\vert 10n+25\right\vert\leq 11n dla n\geq 25,
    • 2n+3\log{n}-100=O(n), bo \left\vert 2n+3\log{n}-100\right\vert\leqslant 3n dla dowolnego n.
  • O(n^2)
    • 3n^2+10n-1=O(n^2),
    • \frac{n(n+1)}{2}=O(n^2),
    • 3\log{n}+2=O(n^2) (funkcja ta jest także O(n) i O(\log{n})).
  • O(2^n)
    • 3\cdot2^n+n=O(2^n), bo n\leq 2^n, a zatem 3\cdot2^n+n\leq 4\cdot2^n dla dowolnego n.

Więcej przykładów i ogólniejszych obserwacji poznamy po prezentacji pozostałych pojęć i symboli notacji asymptotycznej.



SW_7.2.swf

Funkcja asymptotycznie niemniejsza od funkcji g(n) to taka funkcja f: \mathbb{N} \longrightarrow \mathbb{R}, dla której istnieją c>0 i n_0\in\mathbb{N}, że c\cdot\left\vert g(n)\right\vert\leq \left\vert f(n)\right\vert dla wszystkich n\geq n_0.
Zbiór funkcji asymptotycznie niemniejszych niż g(n) oznaczamy przez \Omega(g(n)).

Funkcja asymptotycznie podobna do funkcji g(n) to taka funkcja f: \mathbb{N} \longrightarrow \mathbb{R}, dla której istnieją c_0,c_1>0 i n_0\in\mathbb{N}, że c_0\cdot\left\vert g(n)\right\vert\leqslant\left\vert f(n)\right\vert\leq c_1\cdot\left\vert g(n)\right\vert dla wszystkich n\geq n_0.
Zbiór funkcji asymptotycznie podobnych do g(n) oznaczamy przez \Theta(g(n)). A zatem \Theta(g(n))= O(g(n)) \cap \Omega(g(n)).

Pozostałe dwa symbole: o,\omega są rzadziej stosowane w informatyce. Wyznaczają one funkcje asymptotycznie, ściśle mniejsze [większe] od podanej funkcji.

Funkcja asymptotycznie mniejsza od funkcji g(n) to taka funkcja f: \mathbb{N} \longrightarrow \mathbb{R}, że dla każdego c>0 istnieje n_0\in\mathbb{N}, przy którym \left\vert f(n)\right\vert<c\cdot\left\vert g(n)\right\vert dla wszystkich n\geq n_0.
Zbiór funkcji asymptotycznie mniejszych niż g(n) oznaczamy przez o(g(n)). A zatem f(n)= o(g(n)) wtedy i tylko wtedy, gdy \displaystyle \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}=0.

Funkcja asymptotycznie większa od funkcji g(n) to taka funkcja f: \mathbb{N} \longrightarrow \mathbb{R}, że dla każdego c>0 istnieje n_0\in\mathbb{N}, przy którym c\cdot\left\vert g(n)\right\vert<\left\vert f(n)\right\vert dla wszystkich n\geq n_0.
Zbiór funkcji asymptotycznie większych niż g(n) oznaczamy przez \omega(g(n)). A zatem f(n)=\omega(g(n)) wtedy i tylko wtedy, gdy \displaystyle \lim_{n \rightarrow \infty} \frac{g(n)}{f(n)}=0.

Oto kilka prostych faktów wiążących kolejne symbole asymptotyczne. Pozostawiamy je bez dowodu.

Obserwacja 9.1

Dla funkcji f,g: \mathbb{N} \longrightarrow \mathbb{R} mamy:

  • jeśli f(n)=O(g(n)), g(n)=O(h(n)), to f(n)=O(h(n)),
  • jeśli f(n)=\Omega(g(n)), g(n)=\Omega(h(n)), to f(n)=\Omega(h(n)),
  • jeśli f(n)=o(g(n)), g(n)=o(h(n)), to f(n)=o(h(n)),
  • jeśli f(n)=\omega(g(n)), g(n)=\omega(h(n)), to f(n)=\omega(h(n)),
  • f(n)=\Theta(g(n)) wtedy i tylko wtedy, gdy g(n)=\Theta(f(n)),
  • f(n)=O(g(n)) wtedy i tylko wtedy, gdy g(n)=\Omega(f(n)),
  • f(n)=o(g(n)) wtedy i tylko wtedy, gdy g(n)=\omega(f(n)).

Symbole asymptotyczne mogą pojawić się w złożonych wyrażeniach arytmetycznych. Dla przykładu wspomnijmy jeszcze raz sumę kolejnych kwadratów: \displaystyle \sum_{i=0}^n i^2=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n. Możemy teraz napisać \displaystyle \sum_{i=0}^ni^2=O(n^3), ale także \displaystyle \sum_{i=0}^ni^2=\frac{1}{3}n^2+O(n^2), co formalnie oznacza \displaystyle \sum_{i=0}^ni^2-\frac{1}{3}n^3\in O(n^2). Co więcej okazuje się, że symbol = może pełnić nie tylko rolę \in, ale czasami także rolę \subseteq. Na przykład wyrażenie


\frac{1}{3}n^3+O(n^2)=O(n^3),


ma po obu stronach"równości" zbiory funkcji, przy czym po lewej stronie są to wszystkie funkcje postaci \frac{1}{3}n^3+f(n) dla f(n)=O(n^2). W tej sytuacji znak = powinien być formalnie rozumiany jako inkluzja \subseteq.

Nadużywając znaku "równości" musimy jednak uważać i pamiętać, że w konwencji asymptotycznej taki nadużyty znak = nie jest relacją symetryczną. Rzeczywiście, O(n^3)\neq\frac{1}{3}n^3+O(n^2), gdyż np. funkcja n^3\in O(n^3), ale n^3\notin\frac{1}{3}n^3+O(n^2). Jednak pożytki płynące z takiego "przeciążenia" znaku równości sprawiedliwiają te nadużycia. W następnej Obserwacji w taki właśnie sposób sformułujemy (bez oczywistego dowodu) kilka własności notacji O. Z nich mozna łatwo otrzymać analogiczne własności dla \Omega i \Theta.

Obserwacja 9.2

Dla funkcji \displaystyle f,g,f_1,f_2,g_1,g_2: \mathbb{N} \map \mathbb{R} mamy:

  • \displaystyle f(n)=O(f(n)),
  • \displaystyle f(n)=O(O(g(n))) wtedy i tylko wtedy, gdy \displaystyle f(n)=O(g(n)),
  • \displaystyle f(n)=O\left\vert (g(n)) \right\vert wtedy i tylko wtedy, gdy \displaystyle f(n)= O(g(n)),
  • \displaystyle f(n)=c\cdot O(g(n)) wtedy i tylko wtedy, gdy \displaystyle f(n)=O(g(n)),
  • jeśli \displaystyle f_1(n)= O(g_1(n)) i \displaystyle f_2(n)=O(g_2(n)), to \displaystyle f_1(n)+f_2(n)=O(g_1(n))+O(g_2(n)),
  • jeśli \displaystyle f_1(n)= O(g_1(n)) i \displaystyle f_2 (n)=O(g_2(n)), to \displaystyle f_1(n)\cdot f_2(n)=O(g_1(n)g_2(n)).

Przykład

Pokażemy, że wielomiany \displaystyle k-tego stopnia są \displaystyle \Theta(n^k).

Zauważmy najpierw, że jeśli \displaystyle k<l to \displaystyle O(n^k)=O(n^l), czyli jeśli \displaystyle f(n)\in O(n^k) to \displaystyle f(n)\in O(n^l). Rozważmy zatem dowolny wielomian \displaystyle k-tego stopnia \displaystyle p(n)=a_kn^k+\ldots+a_1n+a_0, gdzie \displaystyle a_k\neq0. Wtedy


\begin{array} {rlll} \left\vert p(n) \right\vert &=\left\vert a_kn^k+\ldots+a_1n+a_0 \right\vert &&\\ &\leqslant \left\vert a_k \right\vert n^k+\ldots+\left\vert a_1 \right\vert n+\left\vert a_0 \right\vert &\\ &=a_k\cdot O(n^k)+\ldots+a_1\cdot O(n)+a_0\cdot O(1)&\textrm{bo}\quad n^i=O(n^i)\\ &=O(n^k)+\ldots+O(n)+O(1)&\textrm{bo}\quad c\cdot O(n^i) = O(n^i)\\ &=O(n^k)+\ldots+O(n^k)+O(n^k)&\textrm{bo}\quad O(n^i)=O(n^k), \textrm{dla}\quad i\leqslant k\\ &=O(n^k),&\textrm{bo}\quad O(n^k)+O(n^k)= O(n^k) \end{array}


co dowodzi, że \displaystyle p(n)=O(n^k).

Dla dowodu \displaystyle p(n)=\Omega(n^k), niech \displaystyle a=\max(\left\vert a_{0} \right\vert,\left\vert a_{1} \right\vert,\ldots,\left\vert a_{k-1} \right\vert). Wtedy


\displaystyle \left\vert a_k \right\vert n^k\geq 2kan^{k-1}\geq 2(\left\vert a_{k-1} \right\vert n^{k-1}+\left\vert a_{k-2} \right\vert n^{k-2}+\ldots+\left\vert a_0 \right\vert)


dla \displaystyle n\geq \frac{2ka}{\left\vert a_k \right\vert}. Mamy zatem


\displaystyle \aligned \left\vert p(n) \right\vert &=\left\vert a_kn^k+a_{k-1}n^{k-1}+\ldots+a_0 \right\vert \geqslant\left\vert a_k \right\vert n^k-(\left\vert a_{k-1} \right\vert n^{k-1}+\ldots+\left\vert a_0 \right\vert)\\ &\geqslant\left\vert a_k \right\vert n^k-kan^{k-1}\geqslant\frac{\left\vert a_k \right\vert n^k}{2}, \endaligned


co dowodzi \displaystyle p(n)=\Omega(n^k).

Przykład

Często pojawiają się logarytmy o różnych podstawach. Najczęściej są to \displaystyle \lg{n},\ln{n},\log{n}. Z asymptotycznego punktu widzenia wszystkie te funkcje są podobne tzn. np. \displaystyle \ln{n}=\Theta(\lg{n}) i \displaystyle \log{n}=\Theta(\lg{n}), lub ogólniej:


\displaystyle \log_a{n}=\Theta(\log_b{n}),\quad \textrm{dla}\quad a,b>1.


Rzeczywiście, jest to po prostu wzór na zamianę podstaw logarytmu,


\displaystyle \log_a{n}=\frac{1}{\log_b{a}}\cdot\log_b{n},


gdzie ta sama stała \displaystyle \frac{1}{\log_b{a}} jest dobra do dolnego i górnego ograniczenia.

Przykład

Dla wielomianów \displaystyle f(n),g(n) rząd ich wielkości wyznaczony jest przez stopień:


\displaystyle f = O(g) wtedy i tylko wtedy, gdy \displaystyle \deg(f)\leq \deg(g)
.


Ustala to hierarchię rzędów funkcji:


\displaystyle n, n^2, n^3, n^4, \ldots, n^d, n^{d+1}, \ldots


Również dla "stopni" będącymi dowolnymi liczbami dodatnimi mamy:


\displaystyle n^a = O(n^b) wtedy i tylko wtedy, gdy \displaystyle a \leq b


Na przykład:

  • \displaystyle \sqrt{n} \in O(n),
  • \displaystyle \sqrt[3]{n} \in O(\sqrt{n}).

Przykład

Mamy \displaystyle n \in O(2^n). Istotnie łatwo dowieść indukcyjnie, że \displaystyle n \leq 2^n.

Podobnie \displaystyle n^2 \in O(2^n). Wiemy już, że każda funkcja liniowa jest w \displaystyle O(2^n), istnieje więc stała \displaystyle c taka, że od pewnego miejsca \displaystyle 2n+1 \leq c\cdot 2^n.
Pokażemy, że wtedy też \displaystyle n^2 \leq c\cdot 2^n. Indukcyjnie


\displaystyle (n+1)^2 = n^2 +2n +1 \leq c \cdot 2^n +(2n +1) \leq c \cdot 2^n + c \cdot 2^n = c \cdot 2^{n+1}


Analogicznie, wiedząc już, że każda funkcja kwadratowa jest w \displaystyle O(2^n), czyli że dla pewnej stałej \displaystyle c od pewnego miejsca mamy { \displaystyle  3n^2 +3n +1 \leq c \cdot 2^n}, możemy pokazać indukcyjnie, że \displaystyle n^3 \leq c \cdot 2^n. Istotnie


\displaystyle (n+1)^3 = n^3 + 3n^2 +3n +1 \leq c \cdot 2^n + c \cdot 2^n = c \cdot 2^{n+1}.


Ogólnie, dla dowolnego stopnia \displaystyle d mamy \displaystyle n^d \in O(a^n), o ile tylko \displaystyle a>1.

Przykład

Oczywiście \displaystyle 2^n \leq 3^n, więc \displaystyle 2^n \in O(3^n).
Ale \displaystyle 3^n \not\in O(2^n). Gdyby bowiem \displaystyle 3^n \leq c \cdot 2^n to


\displaystyle \left(\frac{3}{2}\right)^n = \frac{3^n}{2^n} \leq c,


podczas gdy funkcja wykładnicza \displaystyle \left(\frac{3}{2}\right)^n rośnie do nieskończoności. Nie może zatem być ograniczona przez żadną stałą \displaystyle c.
Ogólnie dla \displaystyle a,b >1, mamy \displaystyle a^n \in O(b^n) wtedy i tylko wtedy, gdy \displaystyle a\leq b.

Przykład

Mamy \displaystyle 2^n \in O(n!) oraz \displaystyle n! \in O(n^n).
Istotnie \displaystyle 2^n \leq 2 \cdot 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n = 2 \cdot n!, bo każdy czynnik (poza pierwszym) w \displaystyle n! jest równy co najmniej \displaystyle 2. Pokazuje to, że \displaystyle 2^n \in O(n!).

Podobnie \displaystyle n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n \leq n \cdot n \cdot n \cdot \ldots \cdot n = n^n, bo każdy czynnik w \displaystyle n! jest nie większy niż \displaystyle n.

Jako ćwiczenie pozostawiamy dowód następnej obserwacji.

Obserwacja 9.3

Oto ciąg funkcji, z których każda jest \displaystyle O od następnej, ale nie od poprzedniej:


\displaystyle \frac{1}{n^n}, \frac{1}{n!}, \ldots, \frac{1}{3^n}, \frac{1}{2^n}, \ldots, \frac{1}{n^3}, \frac{1}{n^2}, \frac{1}{n \lg n}, \frac{1}{n}, \frac{\lg{n}}{n}, \frac{1}{\sqrt{n}}, \frac{1}{\sqrt[3]{n}}, \ldots,  \frac{1}{\lg{n}}, \frac{1}{\lg\lg n}, 1


i dalej


\displaystyle 1, \lg\lg{n}, \lg{n}, \ldots, \sqrt[3]{n}, \sqrt{n}, \frac{n}{\lg{n}}, n, n\lg{n}, n\sqrt{n}, n^2, n^3, \ldots,  n^{\lg{n}}, 2^n, 3^n, n!, n^n, 2^{2^n}.


W istocie, gdy \displaystyle g(n) występuje w tym ciagu wczesniej niż \displaystyle f(n), to

  • \displaystyle g(n)=O(f(n)),
  • \displaystyle f(n)=o(g(n)).

Przykład

Nie każde dwie funkcje są porównywalne asymptotycznie. Na przykład dla funkcji


\displaystyle f(n)= \left\{ \begin{array} {cl} n,& \textrm{dla} \quad n \quad \textrm{parzystych}\\  n^3,& \textrm{dla}\quad n\quad \textrm{nieparzystych} \end{array}  \right.


i \displaystyle g(n)=n^2 mamy \displaystyle f(n)\neq\Omega(g(n)) i \displaystyle f(n)\neq O(g(n)).

Twierdzenie o rekursji uniwersalnej

Podstawowym zastosowaniem notacji asymptotycznej w informatyce jest szacowanie długości działania programów, w szczególności procedur rekurencyjnych, których złożoność łatwo opisać równaniem rekurencyjnym. Niech \displaystyle T(n) będzie funkcją opisującą złożoność czasową pewnego programu, czyli zwracającą liczbę wykonywanych operacji dla danych wielkości \displaystyle n. Zazwyczaj nie jesteśmy zainteresowani dokładną liczbą wykonywanych operacji, a jedynie dobrym oszacowaniem z góry i czasem z dołu. Dlatego zamiast szukać postaci zwartej rozwiązania rekurencyjnego, co na ogół jest zadaniem beznadziejnym, dopuszczamy użycie notacji asymptotycznej i szukamy pewnej "dobrze znanej" funkcji \displaystyle g(n) takiej, że \displaystyle T(n)=\Theta(g(n)). Znając \displaystyle g(n) wiemy w jaki sposób rośnie długość działania programu wraz z wzrostem wielkości danych.

Równania, o których mówimy często są postaci \displaystyle T(n)=a\cdot T\left( \left\lfloor\frac{n}{b}\right\rfloor \right)+f(n), czyli aby rozwiązać problem dla danych wielkości \displaystyle n, rozwiązujemy \displaystyle a podproblemów wielkości \displaystyle \left\lfloor\frac{n}{b}\right\rfloor i składamy z nich rozwiązanie całości w dodatkowym czasie \displaystyle f(n). Twierdzenie o rekurencji uniwersalnej wskazuje funkcję asymptotycznie podobną do \displaystyle T(n) w bardzo wielu przypadkach.

Twierdzenie 9.4 [o rekurencji uniwersalnej]

Dla funkcji \displaystyle T(n) zadanej przez


\displaystyle T(n)= \left \{\begin{array} {ll} \Theta(1),& \textrm{dla}\quad n\in \{0,1\}\\  a\cdot T\left( \left\lfloor\frac{n}{b}\right\rfloor \right)+f(n),& \textrm{dla}\quad n>1 \end{array}  \right.


zachodzi:

  • jeśli \displaystyle f(n)=O(n^{\log_b{a}-\epsi}) dla pewnego \displaystyle \epsi>0, to \displaystyle T(n)=\Theta(n^{\log_b{a}}),
  • jeśli \displaystyle f(n)=\Theta(n^{\log_b{a}}), to \displaystyle T(n)=\Theta(n^{\log_b{a}}\lg{n}),
  • jeśli \displaystyle f(n)=\Omega(n^{\log_b{a}+\epsi}) dla pewnego \displaystyle \epsi>0 oraz \displaystyle a f(\frac{n}{b})\leq c f(n) dla pewnego \displaystyle c<1 i prawie wszystkich \displaystyle n, to \displaystyle T(n)=\Theta(f(n)).

Zanim podamy dowód Twierdzenia 9.4, poczynimy kilka uwag i prześledzimy kilka przykładów.

W praktyce na ogół pomijamy opis początkowych wartości funkcji \displaystyle T(n) domyślnie przyjmując, że są one \displaystyle \Theta(1). Nie będziemy też używać podłóg w wyrażeniach typu \displaystyle T(\frac{n}{b}), traktując występujące tu dzielenie jako całkowito-liczbowe. Twierdzenie o rekurencji uniwersalnej jest silnym i praktycznym narzędziem. Jednak trzeba podkreślić, że nie szacuje ono rozwiązań wszystkich równań typu \displaystyle T(n)=aT\left( \frac{n}{b} \right)+f(n). Taka niemożność oszacowania może mieć miejsce z jednego z trzech powodów, przy czym drugi z nich jest istotny i zdarza się w praktyce:

  • W każdym z trzech przypadków opisanym w twierdzeniu, porównujemy funkcje \displaystyle n^{\log_b{a}} i \displaystyle f(n). Może się zdarzyć (jak widzieliśmy w jednym z przykładów), iż \displaystyle n^{\log_b{a}} i \displaystyle f(n) są asymptotycznie nieporównywalne i wobec tego nie będzie można zastosować żadnego z tych trzech przypadków. Na szczęście w praktyce takie funkcje raczej zdarzają się niezmiernie rzadko.
  • Po drugie, w przypadku pierwszym (i trzecim), tak naprawdę, porównujemy \displaystyle f(n) z funkcją istotnie mniejszą (wiekszą) od \displaystyle n^{\log_b{a}}, tzn. z funkcją \displaystyle n^{\log_b{a}\pm\epsilon} dla pewnego \displaystyle \epsilon. Ten warunek już może przeszkadzać w praktyce. Dla przykładu \displaystyle n\lg{n}\in\Omega(n), ale \displaystyle n\lg{n}\notin\Omega(n^{1+\epsilon}) dla dowolnego \displaystyle \epsilon>0. Pełny przykład takiego równania przedstawimy poniżej.
  • Po trzecie, w ostatnim warunku dla \displaystyle f(n)\in\Omega(n^{\log_b{a}+\epsilon}) dla dowolnego \displaystyle \epsilon>0 wymagamy dodatkowo, żeby \displaystyle af(\frac{n}{b})\leq c f(n) dla pewnego \displaystyle c<1 i dla wszystkich \displaystyle n\geq n_0 dla pewnego \displaystyle n _0. Znów, na szczęście, w większości spotykanych sytuacji ten warunek "regularności" jest spełniony. Jednak zawsze trzeba go sprawdzić.

Przykład

Dla funkcji zadanej przez:


\displaystyle T(n)=16T\left( \frac{n}{4} \right)+n\lg{n},


dostajemy kolejno:

Podobnie dla funkcji


\displaystyle T(n)=2T\left( \frac{n}{2} \right)+5n-15,


mamy:

Niech teraz


\displaystyle T(n)=2T\left( \frac{n}{3} \right)+n\lg{n}.


Wtedy

Z kolei dla funkcji spełniającej


\displaystyle T(n)=2T\left( \frac{n}{2} \right)+n\lg{n},


dostajemy

  • \displaystyle a=2, \displaystyle b=2, \displaystyle f(n)=n\lg{n},
  • \displaystyle n^{\log_2{2}}=n,
  • \displaystyle n\lg{n}\in\Omega(n) ale dla dowolnego \displaystyle \epsilon>0, \displaystyle n\lg{n}\notin\Omega(n^{1+\epsilon}),
  • i ... nie można zaaplikować Twierdzenia 9.4.

Po tych uwagach i przykładach podamy dowód Twierdzenia o rekurencji uniwersalnej.

Dowód

Rozumowanie nasze przeprowadzimy tylko w przypadku, gdy liczba \displaystyle b występująca w rekurencyjnym równaniu zadającym funkcję \displaystyle T(n) jest potęgą liczby naturalnej, czyli dla liczb postaci \displaystyle 1,b,b^2,\ldots. Rozszerzenie tego rozumowania na cały zbiór \displaystyle \mathbb{N} jest dość techniczne i wymaga szacowania podłóg. Ponadto, symboli asymptotycznych będziemy używać tylko dla \displaystyle n\in\left\lbrace 1,b,b^2,\ldots \right\rbrace. To nieformalne nadużycie nie ogranicza poprawności rozumowania -- wymaga wszakże rozszerzenia notacji asymptotycznej na funkcje postaci \displaystyle f: \mathbb{R} \map \mathbb{R}.

Rozwijając rekurencyjną formułę \displaystyle T(n) dla \displaystyle n=b^k otrzymujemy:


\displaystyle \aligned T(n)&=T(b^k)=f(b^k)+aT(b^{k-1})=f(n)+af(b^{k-1})+a^2T(b^{k-2})=\ldots\\ &=f(b^k)+af(b^{k-1})+a^2f(b^{k-2})+\ldots+a^{k-1}f(b)+a^kT(1). \endaligned


Ponieważ \displaystyle a^k=a^{\log_b{n}}=a^{\frac{\log_a{n}}{\log_a{b}}}=n^{\log_b{a}} możemy kontynuować:


\displaystyle \aligned T(n)&=f(b^k)+af(b^{k-1})+a^2f(b^{k-2})+\ldots+a^{k-1}f(b)+a^kT(1).\\ &=\Theta(n^{\log_b{n}})+\sum_{i=0}^{k-1}a^if(b^{k-i}). \endaligned


Dalsze szacowanie rozbijamy na \displaystyle 3 przypadki zgodnie z warunkami na zachowanie funkcji \displaystyle f(n) wobec \displaystyle n^{\log_b{a}}:

  • \displaystyle f(n)=O(n^{\log_b{a}-\epsilon}),
\displaystyle \aligned T(n)&=\Theta(n^{\log_b{n}})+\sum_{i=0}^{k-1}a^if(b^{k-i})\\ &=\Theta(n^{\log_b{a}})+\sum_{i=0}^{k-1}a^i\cdot O((b^{k-i})^{\log_b{a}-\epsilon})\\ &=\Theta(n^{\log_b{a}})+O\left( b^{k(\log_b{a}-\epsilon)}\sum_{i=0}^{k-1}\left( \frac{a}{b^{\log_b{a}-\epsilon}} \right)^i \right)\\ &=\Theta(n^{\log_b{a}})+n^{\log_b{a}-\epsilon}\cdot O\left( \sum_{i=0}^{k-1}\left( \frac{ab^{\epsilon}}{a} \right)^i \right)\\ &=\Theta(n^{\log_b{a}})+n^{\log_b{a}-\epsilon}\cdot O\left( \sum_{i=0}^{k-1}b^{i\epsilon} \right)\\ &=\Theta(n^{\log_b{a}})+n^{\log_b{a}-\epsilon}\cdot O\left( \frac{b^{k\epsilon}-1}{b^\epsilon-1} \right)\\ &=\Theta(n^{\log_b{a}})+n^{\log_b{a}-\epsilon}\cdot O\left( \frac{n^{\epsilon}-1}{b^\epsilon-1} \right). \endaligned


Ponieważ \displaystyle b i \displaystyle \epsilon są stałymi, ostatni składnik redukuje się do \displaystyle n^{\log_b{a}-\epsilon}\cdot O(n^{\epsilon})=O(n^{\log_b{a}}). Zatem


\displaystyle T(n)=\Theta(n^{\log_b{a}})+O(n^{\log_b{a}})=\Theta(n^{\log_b{a}}).
  • \displaystyle f(n)=\Theta(n^{\log_b{a}}),
\displaystyle \aligned T(n)&=\Theta(n^{\log_b{a}})+\sum_{i=0}^{k-1}a^if(b^{k-i})\\ &=\Theta(n^{\log_b{a}})+\Theta\left( \sum_{i=0}^{k-1}\frac{a^ib^{k\lg_b{a}}}{b^{i\log_b{a}}} \right)\\ &=\Theta(n^{\log_b{a}})+\Theta\left( n^{\log_b{a}}\sum_{i=0}^{k-1}1 \right)\\ &=\Theta(n^{\log_b{a}})+\Theta\left( n^{\log_b{a}}\log_b{n} \right)\\ &=\Theta\left( n^{\log_b{a}}\lg{n} \right). \endaligned
  • \displaystyle af(\frac{n}{b})\leq cf(n) dla pewnego \displaystyle c i prawie wszystkich \displaystyle n

oraz \displaystyle f(n)=\Omega(n^{\log_b{a}}).

Z założeń tego przypadku mamy \displaystyle a^if(b^{k-i})\leq c^if(n). Zatem


\displaystyle \aligned T(n)&=\Theta(n^{\log_b{a}})+\sum_{i=0}^{k-1}a^if(b^{k-i})\\ &\leqslant\Theta(n^{\log_b{a}})+\sum_{i=0}^{k-1}c^if(n)\\ &\leqslant\Theta(n^{\log_b{a}})+f(n)\sum_{i=0}^{\infty}c^i\\ &=\Theta(n^{\log_b{a}})+f(n)\frac{1}{1-c}\\ &=\Theta(n^{\log_b{a}})+\Theta{f(n)}\\ &=\Theta({f(n)}). \endaligned


image:End_of_proof.gif

Metoda przybliżeń

W pewnych sytuacjach łatwiejsze do uzyskania, ale słabsze oszacowanie zastosowane w odpowiedni sposób może prowadzić do lepszego końcowego szacowania zachowania asymptotycznego. Poznamy tę metodę w kilku kolejnych przykładach.

Przykład

Dla ciągu zadanego przez


\displaystyle \aligned a_0&=1,\\ a_{n+1}&=\frac{1}{n^3}\sum_{i=0}^{n-1}a_i, \endaligned


najpierw dowodzimy indukcyjnie, że \displaystyle 0<a_n\leq 1, czyli \displaystyle a_n=O(1). Podstawiając uzyskane oszacowanie do równania rekurencyjnego otrzymujemy:


\displaystyle a_n=\frac{1}{n^3}\sum_{i=0}^{n}a_i=\frac{1}{n^3}\cdot \sum_{i=0}^n O(1)=\frac{1}{n^3}\cdot O\left( \sum_{i=0}^n1 \right)=\frac{1}{n^3}\cdot O(n)=O\left( \frac{1}{n^2} \right).


Operację tę możemy powtórzyć uzyskując jeszcze lepsze oszacowanie


\displaystyle \aligned a_n&=\frac{1}{n^3}\sum_{i=0}^na_i=\frac{1}{n^3}\left( a_0+\sum_{i=1}^na_i \right)=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^{n}O\left( \frac{1}{n^2} \right)= \frac{1}{n^3}+\frac{1}{n^3}O(1)\\ &=O\left( \frac{1}{n^3} \right). \endaligned


Wykorzystaliśmy tu fakt, iż szereg \displaystyle \sum_{i=0}^{\infty}\frac{1}{i^2} jest zbieżny. Zauważmy też, że następne powtórzenie podobnej procedury szacującej już nam nic nie da.


\displaystyle a_n=\frac{1}{n^3}\sum_{i=0}^na_i=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^nO\left( \frac{1}{n^3} \right)=\frac{1}{n^3}+\frac{1}{n^3}\cdot O\left( \frac{1}{n^2} \right)=O\left( \frac{1}{n^3} \right).


Przykład

Niech ciąg \displaystyle b_n spełnia


\displaystyle b_n\cdot\ln{b_n}=n.


Z monotoniczności funkcji \displaystyle n\ln{n} dostajemy, że \displaystyle 0<b_n<n. Podstawiając to oszacowanie za drugie wystąpienie \displaystyle b_n w równaniu otrzymujemy:


\displaystyle n=b_n\cdot\ln{b_n}< b_n\ln{n},


czyli \displaystyle b_n>\frac{n}{\ln{n}}. Podstawiając powtórnie dostajemy:


\displaystyle n=b_n\ln{b_n}>b_n\cdot\ln{\frac{n}{\ln{n}}},


czyli \displaystyle b_n<\frac{n}{\ln{n}-\ln{\ln{n}}}. Uzyskaliśmy zatem, że \displaystyle b_n=\Theta\left( \frac{n}{\ln{n}} \right).

Na zakończenie tego wykładu poznamy jeszcze jeden symbol asymptotyczny. Jest on podobny do \displaystyle \Theta lecz znacznie precyzyjniejszy.

Funkcje asymptotycznie równe to takie funkcje \displaystyle f(n) i \displaystyle g(n), że


\displaystyle \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=1.


Fakt, że funkcje \displaystyle f(n) i \displaystyle g(n) są asymptotycznie równe zapisujemy jako \displaystyle f(n)\sim g(n).

Jednym z najbardziej znanych przybliżeń asymptotycznych jest tzw. Wzór Stirlinga przybliżający zachowanie silni.

Twierdzenie 9.5 [wzór Stirlinga]


\displaystyle n!\sim \sqrt{2\pi n}\left( \frac{n}{e} \right)^n.


Wzór ten został odkryty przez Abrahama de Moivre w postaci


\displaystyle n!\sim c \cdot n^{n+1/2} e^{-n},


dla pewnej stałej \displaystyle c. Wkładem Jamesa Stirlinga było pokazanie, że stałą tą jest \displaystyle c=\sqrt{2\pi}. Dowód tego oszacowania wykracza poza metody tego kursu. W oszacowaniach przez nierówności przydatna jest następująca wersja wzoru Stirlinga:


\displaystyle \sqrt{2\pi n}\left( \frac{n}{e} \right)^ne^{-(12n+1)}\leq n!\leq \sqrt{2\pi n}\left( \frac{n}{e} \right)^{n}e^{-12n}


Innym ważnym przybliżeniem asymptotycznym jest wzór na liczbę podziałów liczby naturalnej \displaystyle n na sumy dodatnich liczb naturalnych, tzn. asymptotyczne przybliżenie funkcji \displaystyle p_n = \sum_{k=1}^n P(n,k) .

Twierdzenie 9.6


\displaystyle p_n \sim \frac{e^{\pi\sqrt{\frac{2n}{3}}}}{4n\sqrt{3}}


Podamy też asymptotyczne przybliżenie na liczbę liczb pierwszych nie większych niż \displaystyle n.

Twierdzenie 9.7

Jeśli \displaystyle \pi(n) oznacza liczbę liczb pierwszych w zbiorze \displaystyle \left\lbrace 1,2,3,\ldots,n \right\rbrace, to


\displaystyle \pi(n) \sim \frac{n}{\ln n}