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} \)