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{\{ {1,\ldots,n} \}\ } \) mamy \( n\leq i(n+1-i)\leq\frac{1}{4}(n+1)^2 \) i dalej
\( n^n\leq(n!)^2\leq(\frac{1}{4}(n+1)^2)^n, \)
czyli
\( n^{\frac{n}{2}}\leq n!\leq(\frac{n+1}{2})^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} \).
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 \( \vert f(n)\vert\leq c\cdot\vert g(n)\vert \) dla wszystkich \( n\geq n_0 \).
Będziemy też często mówić, że \( \vert f(n)\vert\leq c\cdot\vert g(n)\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
Istotnie warunek \( \vert f(n)\vert\leq c \) zachodzący dla prawie wszystkich \( n \) łatwo jest, poprzez zamianę stałej \( c \) na inną \( c' \), sprowadzić do warunku \( \vert f(n)\vert\leq c' \) zachodzącego już dla wszystkich \( n\in\mathbb{N} \), jako że skończenie wiele wartości \( \vert f(n)\vert \) dla początkowych \( n \) daje się ograniczyć przez stałą.
Więcej przykładów i ogólniejszych obserwacji poznamy po prezentacji pozostałych pojęć i symboli notacji asymptotycznej.
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\vert g(n)\vert\leq \vert f(n)\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\vert g(n)\vert\leq\vert f(n)\vert\leq c_1\cdot\vert g(n)\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 \( \vert f(n)\vert < c\cdot\vert g(n)\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 \to \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\vert g(n)\vert < \vert f(n)\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 \to \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:
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} \mathbb{R} \) mamy:
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} \vert p(n) \vert & =\vert a_kn^k+\ldots+a_1n+a_0 \vert & & \\ & \leq \vert a_k \vert n^k+\ldots+\vert a_1 \vert n+\vert a_0 \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\leq 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(\vert a_{0} \vert,\vert a_{1} \vert,\ldots,\vert a_{k-1} \vert) \). Wtedy
\( \displaystyle \vert a_k \vert n^k\geq 2kan^{k-1}\geq 2(\vert a_{k-1} \vert n^{k-1}+\vert a_{k-2} \vert n^{k-2}+\ldots+\vert a_0 \vert) \)
dla \( \displaystyle n\geq \frac{2ka}{\vert a_k \vert} \). Mamy zatem
\( \displaystyle \begin{align*} \vert p(n) \vert & =\vert a_kn^k+a_{k-1}n^{k-1}+\ldots+a_0 \vert \geq\vert a_k \vert n^k-(\vert a_{k-1} \vert n^{k-1}+\ldots+\vert a_0 \vert) \\ & \geq\vert a_k \vert n^k-kan^{k-1}\geq\frac{\vert a_k \vert n^k}{2}, \end{align*} \)
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:
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 (\frac{3}{2})^n = \frac{3^n}{2^n} \leq c, \)
podczas gdy funkcja wykładnicza \( \displaystyle (\frac{3}{2})^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
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)) \).
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( \lfloor\frac{n}{b}\rfloor )+f(n) \), czyli aby rozwiązać problem dla danych wielkości \( \displaystyle n \), rozwiązujemy \( \displaystyle a \) podproblemów wielkości \( \displaystyle \lfloor\frac{n}{b}\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( \lfloor\frac{n}{b}\rfloor )+f(n), & \textrm{dla}\quad n>1 \end{array} \right. \)
zachodzi:
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:
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
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\lbrace 1,b,b^2,\ldots \rbrace \). To nieformalne nadużycie nie ogranicza poprawności rozumowania -- wymaga wszakże rozszerzenia notacji asymptotycznej na funkcje postaci \( \displaystyle f: \mathbb{R} \mathbb{R} \).
Rozwijając rekurencyjną formułę \( \displaystyle T(n) \) dla \( \displaystyle n=b^k \) otrzymujemy:
\( \displaystyle \begin{align*} 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). \end{align*} \)
Ponieważ \( \displaystyle a^k=a^{\log_b{n}}=a^{\frac{\log_a{n}}{\log_a{b}}}=n^{\log_b{a}} \) możemy kontynuować:
\( \displaystyle \begin{align*} 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}). \end{align*} \)
Dalsze szacowanie rozbijamy na \( \displaystyle 3 \) przypadki zgodnie z warunkami na zachowanie funkcji \( \displaystyle f(n) \) wobec \( \displaystyle n^{\log_b{a}} \):
\( \displaystyle \begin{align*} 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). \end{align*} \)
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 \begin{align*} 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\left(n^{\log_b{a}})+\Theta( n^{\log_b{a}}\sum_{i=0}^{k-1}1 \right) \\ & =\Theta(n^{\log_b{a}})+\Theta( n^{\log_b{a}}\log_b{n} ) \\ & =\Theta( n^{\log_b{a}}\lg{n} ). \end{align*} \)
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 \begin{align*} T(n) & =\Theta(n^{\log_b{a}})+\sum_{i=0}^{k-1}a^if(b^{k-i}) \\ & \leq\Theta(n^{\log_b{a}})+\sum_{i=0}^{k-1}c^if(n) \\ & \leq\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)}). \end{align*} \)
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 \begin{align*} a_0 & =1, \\ a_{n+1} & =\frac{1}{n^3}\sum_{i=0}^{n-1}a_i, \end{align*} \)
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 \begin{align*} 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). \end{align*} \)
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 \to \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}( \frac{n}{e} )^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 \lbrace 1,2,3,\ldots,n \rbrace \), to
\( \displaystyle \pi(n) \sim \frac{n}{\ln n} \)