Informatyka MIMUW

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:

• jeśli $\displaystyle f(n)=O(n^{\log_b{a}-})$ dla pewnego $\displaystyle >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}+})$ dla pewnego $\displaystyle >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:

• $\displaystyle a=16$, $\displaystyle b=4$, $\displaystyle f(n)=n\lg{n}$,
• $\displaystyle n^{\log_4{16}}=n^2$, $\displaystyle f(n)=O(n^{2-\epsilon})$, np. dla $\displaystyle \epsilon=0.5$,
• zatem z pierwszego punktu Twierdzenia 9.4 mamy $\displaystyle T(n)=\Theta(n^2)$.

Podobnie dla funkcji

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

mamy:

• $\displaystyle a=2$, $\displaystyle b=2$, $\displaystyle f(n)=5n-15$,
• $\displaystyle n^{\log_2{2}}=n$, $\displaystyle f(n)=\Theta(n)$,
• zatem z drugiego punktu Twierdzenia 9.4 mamy $\displaystyle T(n)=\Theta(n\lg{n})$.

Niech teraz

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

Wtedy

• $\displaystyle a=2$, $\displaystyle b=3$, $\displaystyle f(n)=n\lg{n}$,
• $\displaystyle n^{\log_3{2}}\approx n^{0.6309}$, $\displaystyle f(n)\in\Omega(n^{\log_3{2}-\epsilon})$ dla $\displaystyle \epsilon=0.1$,
• $\displaystyle af(\frac{n}{b})\leq 2\cdot \frac{n}{3}\lg{\frac{n}{3}}\leq \frac{2}{3}n\lg{n}=\frac{2}{3}f(n)$,
• zatem z trzeciego punktu Twierdzenia 9.4 mamy $\displaystyle T(n)=\Theta(n\lg{n})$.

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\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 f(n)=O(n^{\log_b{a}-\epsilon})$,

$\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 f(n)=\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*}$

• $\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 \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*}$

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