Matematyka dyskretna 1/Wykład 9: Asymptotyka

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 $\sum _{i=0}^n{i}^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 \dots \cdot n\le n^n$. Przyjrzyjmy się delikatniejszemu oszacowaniu wskazującemu także dolne ograniczenie na $n!$.

Najpierw zauważmy, że

$(n!{)}^2=(1\cdot \dots \cdot n)(n\cdot \dots \cdot 1)=\prod _{i=1}^{n}i(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,\dots ,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,\dots ,n\right\}$ mamy $n\le i(n+1-i)⩽\frac{1}{4}(n+1{)}^2$ i dalej

$n^n⩽(n!{)}^2⩽{(\frac{1}{4}(n+1{)}^2)}^n$,

czyli

$n^{\frac{n}{2}}\le n!⩽{\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{\mathbb{N}}$ (lub jego podzbiorach postaci $\mathbb{\mathbb{N}}-{\mathbb{\mathbb{Z}}}_k$) o wartościach w $\mathbb{ℝ}$.

Notacja asymptotyczna

SW_7.1.swf

Funkcja asymptotycznie niewiększa od funkcji $g(n)$ to taka funkcja $f:\mathbb{\mathbb{N}}⟶\mathbb{ℝ}$, dla której istnieją $c>0$ i $n_0\in \mathbb{\mathbb{N}}$, że $|f(n)|\le c\cdot |g(n)|$ dla wszystkich $n\ge n_0$.
Będziemy też często mówić, że $|f(n)|\le c\cdot |g(n)|$ 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 $|f(n)|\le c$ zachodzący dla prawie wszystkich $n$ łatwo jest, poprzez zamianę stałej $c$ na inną $c^{\prime }$, sprowadzić do warunku $|f(n)|\le c^{\prime }$ zachodzącego już dla wszystkich $n\in \mathbb{\mathbb{N}}$, jako że skończenie wiele wartości $|f(n)|$ 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 $|f(n)|=1000⩽1000$ dla dowolnego $n$,
  • $(-1{)}^n=O(1)$, bo $|(-1{)}^n|⩽1$ dla dowolnego $n$,
  • $\frac{1}{n}=O(1)$, bo $\frac{1}{n}\le 1$ dla dowolnego $n⩾1$,
  • $\frac{\log n}{n}=O(1)$, bo $\log n<n$ dla $n⩾1$, zatem $\frac{\log n}{n}⩽1$ dla $n⩾1$.

• $O(n)$ to zbiór funkcji ograniczonych przez funkcję liniową:
  • wszystkie funkcje $O(1)$ są też $O(n)$,
  • $10n+25=O(n)$, bo $|10n+25|\le 11n$ dla $n\ge 25$,
  • $2n+3\log n-100=O(n)$, bo $|2n+3\log n-100|⩽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\cdot 2^n+n=O(2^n)$, bo $n\le 2^n$, a zatem $3\cdot 2^n+n\le 4\cdot 2^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{\mathbb{N}}⟶\mathbb{ℝ}$, dla której istnieją $c>0$ i $n_0\in \mathbb{\mathbb{N}}$, że $c\cdot |g(n)|\le |f(n)|$ dla wszystkich $n\ge n_0$.
Zbiór funkcji asymptotycznie niemniejszych niż $g(n)$ oznaczamy przez $\mathrm{\Omega }(g(n))$.

Funkcja asymptotycznie podobna do funkcji $g(n)$ to taka funkcja $f:\mathbb{\mathbb{N}}⟶\mathbb{ℝ}$, dla której istnieją $c_0,c_1>0$ i $n_0\in \mathbb{\mathbb{N}}$, że $c_0\cdot |g(n)|⩽|f(n)|\le c_1\cdot |g(n)|$ dla wszystkich $n\ge n_0$.
Zbiór funkcji asymptotycznie podobnych do $g(n)$ oznaczamy przez $\mathrm{\Theta }(g(n))$. A zatem $\mathrm{\Theta }(g(n))=O(g(n))\cap \mathrm{\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{\mathbb{N}}⟶\mathbb{ℝ}$, że dla każdego $c>0$ istnieje $n_0\in \mathbb{\mathbb{N}}$, przy którym $|f(n)|<c\cdot |g(n)|$ dla wszystkich $n\ge 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 $\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}=0$.

Funkcja asymptotycznie większa od funkcji $g(n)$ to taka funkcja $f:\mathbb{\mathbb{N}}⟶\mathbb{ℝ}$, że dla każdego $c>0$ istnieje $n_0\in \mathbb{\mathbb{N}}$, przy którym $c\cdot |g(n)|<|f(n)|$ dla wszystkich $n\ge 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 $\underset{n\to \mathrm{\infty }}{\lim }\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{\mathbb{N}}⟶\mathbb{ℝ}$ mamy:

• jeśli $f(n)=O(g(n))$, $g(n)=O(h(n))$, to $f(n)=O(h(n))$,

• jeśli $f(n)=\mathrm{\Omega }(g(n))$, $g(n)=\mathrm{\Omega }(h(n))$, to $f(n)=\mathrm{\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)=\mathrm{\Theta }(g(n))$ wtedy i tylko wtedy, gdy $g(n)=\mathrm{\Theta }(f(n))$,

• $f(n)=O(g(n))$ wtedy i tylko wtedy, gdy $g(n)=\mathrm{\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: $\sum _{i=0}^n{i}^2=\frac{1}{3}{n}^3+\frac{1}{2}{n}^2+\frac{1}{6}n$. Możemy teraz napisać $\sum _{i=0}^n{i}^2=O(n^3)$, ale także $\sum _{i=0}^n{i}^2=\frac{1}{3}{n}^2+O(n^2)$, co formalnie oznacza $\sum _{i=0}^n{i}^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)\ne \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 $\mathrm{\Omega }$ i $\mathrm{\Theta }$.

Obserwacja 9.2

Dla funkcji $f,g,f_1,f_2,g_1,g_2:\mathbb{\mathbb{N}}\mathbb{ℝ}$ mamy:

• $f(n)=O(f(n))$,

• $f(n)=O(O(g(n)))$ wtedy i tylko wtedy, gdy $f(n)=O(g(n))$,

• $f(n)=O|(g(n))|$ wtedy i tylko wtedy, gdy $f(n)=O(g(n))$,

• $f(n)=c\cdot O(g(n))$ wtedy i tylko wtedy, gdy $f(n)=O(g(n))$,

• jeśli $f_1(n)=O(g_1(n))$ i $f_2(n)=O(g_2(n))$, to $f_1(n)+f_2(n)=O(g_1(n))+O(g_2(n))$,

• jeśli $f_1(n)=O(g_1(n))$ i $f_2(n)=O(g_2(n))$, to $f_1(n)\cdot f_2(n)=O(g_1(n)g_2(n))$.

Przykład

Pokażemy, że wielomiany $k$-tego stopnia są $\mathrm{\Theta }(n^k)$.

Zauważmy najpierw, że jeśli $k<l$ to $O(n^k)=O(n^l)$, czyli jeśli $f(n)\in O(n^k)$ to $f(n)\in O(n^l)$. Rozważmy zatem dowolny wielomian $k$-tego stopnia $p(n)=a_k{n}^k+\dots +a_{1}n+a_0$, gdzie $a_k\ne 0$. Wtedy

$\begin{array}{rlll}|p(n)|& =|a_k{n}^k+\dots +a_{1}n+a_0|& & \\ & ⩽\left|a_k\right|n^k+\dots +\left|a_1\right|n+\left|a_0\right|& \\ & =a_k\cdot O(n^k)+\dots +a_1\cdot O(n)+a_0\cdot O(1)& \text{bo}{n}^i=O(n^i)\\ & =O(n^k)+\dots +O(n)+O(1)& \text{bo}c\cdot O(n^i)=O(n^i)\\ & =O(n^k)+\dots +O(n^k)+O(n^k)& \text{bo}O(n^i)=O(n^k),\text{dla}i⩽k\\ & =O(n^k),& \text{bo}O(n^k)+O(n^k)=O(n^k)\end{array}$

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

Dla dowodu $p(n)=\mathrm{\Omega }(n^k)$, niech $a=\max (\left|a_0\right|,\left|a_1\right|,\dots ,\left|a_{k-1}\right|)$. Wtedy

$\left|a_k\right|n^k\ge 2ka{n}^{k-1}\ge 2(\left|a_{k-1}\right|n^{k-1}+\left|a_{k-2}\right|n^{k-2}+\dots +\left|a_0\right|)$

dla $n\ge \frac{2ka}{\left|a_k\right|}$. Mamy zatem

$\begin{array}{rl}|p(n)|& =|a_k{n}^k+a_{k-1}{n}^{k-1}+\dots +a_0|⩾\left|a_k\right|n^k-(\left|a_{k-1}\right|n^{k-1}+\dots +\left|a_0\right|)\\ & ⩾\left|a_k\right|n^k-ka{n}^{k-1}⩾\frac{\left|a_k\right|n^k}{2},\end{array}$

co dowodzi $p(n)=\mathrm{\Omega }(n^k)$.

Przykład

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

${\log }_{a}n=\mathrm{\Theta }({\log }_{b}n),\text{dla}a,b>1$.

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

${\log }_{a}n=\frac{1}{{\log }_{b}a}\cdot {\log }_{b}n$,

gdzie ta sama stała $\frac{1}{{\log }_{b}a}$ jest dobra do dolnego i górnego ograniczenia.

Przykład

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

$f=O(g)$ wtedy i tylko wtedy, gdy $\mathrm{deg}(f)\le \mathrm{deg}(g)$.

Ustala to hierarchię rzędów funkcji:

$n,n^2,n^3,n^4,\dots ,n^d,n^{d+1},\dots$

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

$n^a=O(n^b)$ wtedy i tylko wtedy, gdy $a\le b$

Na przykład:

• $\sqrt{n}\in O(n)$,

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

Przykład

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

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

$(n+1{)}^2=n^2+2n+1\le c\cdot 2^n+(2n+1)\le c\cdot 2^n+c\cdot 2^n=c\cdot 2^{n+1}$

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

$(n+1{)}^3=n^3+3n^2+3n+1\le c\cdot 2^n+c\cdot 2^n=c\cdot 2^{n+1}$

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

Przykład

Oczywiście $2^n\le 3^n$, więc $2^n\in O(3^n)$.
Ale $3^n\in ̸O(2^n)$. Gdyby bowiem $3^n\le c\cdot 2^n$ to

${\left(\frac{3}{2}\right)}^n=\frac{3^n}{2^n}\le c$,

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

Przykład

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

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

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

Obserwacja 9.3

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

$\frac{1}{n^n},\frac{1}{n!},\dots ,\frac{1}{3^n},\frac{1}{2^n},\dots ,\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}},\dots ,\frac{1}{\lg n},\frac{1}{\lg \lg n},1$

i dalej

$1,\lg \lg n,\lg n,\dots ,\sqrt[3]{n},\sqrt{n},\frac{n}{\lg n},n,n\lg n,n\sqrt{n},n^2,n^3,\dots ,n^{\lg n},2^n,3^n,n!,n^n,2^{2^n}$

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

• $g(n)=O(f(n))$,

• $f(n)=o(g(n))$.

Przykład

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

$f(n)=\{\begin{array}{cl}n,& \text{dla}n\text{parzystych}\\ n^3,& \text{dla}n\text{nieparzystych}\end{array}$

i $g(n)=n^2$ mamy $f(n)\ne \mathrm{\Omega }(g(n))$ i $f(n)\ne 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 $T(n)$ będzie funkcją opisującą złożoność czasową pewnego programu, czyli zwracającą liczbę wykonywanych operacji dla danych wielkości $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 $g(n)$ takiej, że $T(n)=\mathrm{\Theta }(g(n))$. Znając $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 $T(n)=a\cdot T\left(\lfloor \frac{n}{b}\rfloor \right)+f(n)$, czyli aby rozwiązać problem dla danych wielkości $n$, rozwiązujemy $a$ podproblemów wielkości $\lfloor \frac{n}{b}\rfloor$ i składamy z nich rozwiązanie całości w dodatkowym czasie $f(n)$. Twierdzenie o rekurencji uniwersalnej wskazuje funkcję asymptotycznie podobną do $T(n)$ w bardzo wielu przypadkach.

Twierdzenie 9.4 [o rekurencji uniwersalnej]

Dla funkcji $T(n)$ zadanej przez

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

zachodzi:

• jeśli $f(n)=O(n^{{\log }_{b}a-ϵ})$ dla pewnego $ϵ>0$, to $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$,

• jeśli $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$, to $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\lg n)$,

• jeśli $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$ dla pewnego $ϵ>0$ oraz $af(\frac{n}{b})\le cf(n)$ dla pewnego $c<1$ i prawie wszystkich $n$, to $T(n)=\mathrm{\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 $T(n)$ domyślnie przyjmując, że są one $\mathrm{\Theta }(1)$. Nie będziemy też używać podłóg w wyrażeniach typu $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 $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 $n^{{\log }_{b}a}$ i $f(n)$. Może się zdarzyć (jak widzieliśmy w jednym z przykładów), iż $n^{{\log }_{b}a}$ i $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 $f(n)$ z funkcją istotnie mniejszą (wiekszą) od $n^{{\log }_{b}a}$, tzn. z funkcją $n^{{\log }_{b}a\pm ϵ}$ dla pewnego $ϵ$. Ten warunek już może przeszkadzać w praktyce. Dla przykładu $n\lg n\in \mathrm{\Omega }(n)$, ale $n\lg n\notin \mathrm{\Omega }(n^{1+ϵ})$ dla dowolnego $ϵ>0$. Pełny przykład takiego równania przedstawimy poniżej.
• Po trzecie, w ostatnim warunku dla $f(n)\in \mathrm{\Omega }(n^{{\log }_{b}a+ϵ})$ dla dowolnego $ϵ>0$ wymagamy dodatkowo, żeby $af(\frac{n}{b})\le cf(n)$ dla pewnego $c<1$ i dla wszystkich $n\ge n_0$ dla pewnego $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:

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

dostajemy kolejno:

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

Podobnie dla funkcji

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

mamy:

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

Niech teraz

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

Wtedy

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

Z kolei dla funkcji spełniającej

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

dostajemy

• $a=2$, $b=2$, $f(n)=n\lg n$,
• $n^{{\log }_{2}2}=n$,
• $n\lg n\in \mathrm{\Omega }(n)$ ale dla dowolnego $ϵ>0$, $n\lg n\notin \mathrm{\Omega }(n^{1+ϵ})$,
• 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 $b$ występująca w rekurencyjnym równaniu zadającym funkcję $T(n)$ jest potęgą liczby naturalnej, czyli dla liczb postaci $1,b,b^2,\dots$. Rozszerzenie tego rozumowania na cały zbiór $\mathbb{\mathbb{N}}$ jest dość techniczne i wymaga szacowania podłóg. Ponadto, symboli asymptotycznych będziemy używać tylko dla $n\in \{1,b,b^2,\dots \}$. To nieformalne nadużycie nie ogranicza poprawności rozumowania -- wymaga wszakże rozszerzenia notacji asymptotycznej na funkcje postaci $f:\mathbb{ℝ}\mathbb{ℝ}$.

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

$\begin{array}{rl}T(n)& =T(b^k)=f(b^k)+aT(b^{k-1})=f(n)+af(b^{k-1})+a^{2}T(b^{k-2})=\dots \\ & =f(b^k)+af(b^{k-1})+a^{2}f(b^{k-2})+\dots +a^{k-1}f(b)+a^{k}T(1).\end{array}$

Ponieważ $a^k=a^{{\log }_{b}n}=a^{\frac{{\log }_{a}n}{{\log }_{a}b}}=n^{{\log }_{b}a}$ możemy kontynuować:

$\begin{array}{rl}T(n)& =f(b^k)+af(b^{k-1})+a^{2}f(b^{k-2})+\dots +a^{k-1}f(b)+a^{k}T(1).\\ & =\mathrm{\Theta }(n^{{\log }_{b}n})+\sum _{i=0}^{k-1}{a}^{i}f(b^{k-i}).\end{array}$

Dalsze szacowanie rozbijamy na $3$ przypadki zgodnie z warunkami na zachowanie funkcji $f(n)$ wobec $n^{{\log }_{b}a}$:

• $f(n)=O(n^{{\log }_{b}a-ϵ})$,

$\begin{array}{rl}T(n)& =\mathrm{\Theta }(n^{{\log }_{b}n})+\sum _{i=0}^{k-1}{a}^{i}f(b^{k-i})\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+\sum _{i=0}^{k-1}{a}^i\cdot O((b^{k-i}{)}^{{\log }_{b}a-ϵ})\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+O\left(b^{k({\log }_{b}a-ϵ)}\sum _{i=0}^{k-1}{\left(\frac{a}{b^{{\log }_{b}a-ϵ}}\right)}^i\right)\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+n^{{\log }_{b}a-ϵ}\cdot O\left(\sum _{i=0}^{k-1}{\left(\frac{a{b}^{ϵ}}{a}\right)}^i\right)\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+n^{{\log }_{b}a-ϵ}\cdot O\left(\sum _{i=0}^{k-1}{b}^{iϵ}\right)\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+n^{{\log }_{b}a-ϵ}\cdot O\left(\frac{b^{kϵ}-1}{b^{ϵ}-1}\right)\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+n^{{\log }_{b}a-ϵ}\cdot O\left(\frac{n^{ϵ}-1}{b^{ϵ}-1}\right).\end{array}$

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

$T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})+O(n^{{\log }_{b}a})=\mathrm{\Theta }(n^{{\log }_{b}a})$

• $f(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$,

$\begin{array}{rl}T(n)& =\mathrm{\Theta }(n^{{\log }_{b}a})+\sum _{i=0}^{k-1}{a}^{i}f(b^{k-i})\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+\mathrm{\Theta }\left(\sum _{i=0}^{k-1}\frac{a^i{b}^{k{\lg }_{b}a}}{b^{i{\log }_{b}a}}\right)\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+\mathrm{\Theta }\left(n^{{\log }_{b}a}\sum _{i=0}^{k-1}1\right)\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+\mathrm{\Theta }\left(n^{{\log }_{b}a}{\log }_{b}n\right)\\ & =\mathrm{\Theta }(n^{{\log }_{b}a}\lg n).\end{array}$

• $af(\frac{n}{b})\le cf(n)$ dla pewnego $c$ i prawie wszystkich $n$
  

oraz $f(n)=\mathrm{\Omega }(n^{{\log }_{b}a})$.

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

$\begin{array}{rl}T(n)& =\mathrm{\Theta }(n^{{\log }_{b}a})+\sum _{i=0}^{k-1}{a}^{i}f(b^{k-i})\\ & ⩽\mathrm{\Theta }(n^{{\log }_{b}a})+\sum _{i=0}^{k-1}{c}^{i}f(n)\\ & ⩽\mathrm{\Theta }(n^{{\log }_{b}a})+f(n)\sum _{i=0}^{\mathrm{\infty }}{c}^i\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+f(n)\frac{1}{1-c}\\ & =\mathrm{\Theta }(n^{{\log }_{b}a})+\mathrm{\Theta }f(n)\\ & =\mathrm{\Theta }(f(n)).\end{array}$

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

$\begin{array}{rl}{a}_0& =1,\\ a_{n+1}& =\frac{1}{n^3}\sum _{i=0}^{n-1}{a}_i,\end{array}$

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

$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}^{n}1\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

$\begin{array}{rl}{a}_n& =\frac{1}{n^3}\sum _{i=0}^n{a}_i=\frac{1}{n^3}(a_0+\sum _{i=1}^n{a}_i)=\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{array}$

Wykorzystaliśmy tu fakt, iż szereg $\sum _{i=0}^{\mathrm{\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.

$a_n=\frac{1}{n^3}\sum _{i=0}^n{a}_i=\frac{1}{n^3}+\frac{1}{n^3}\sum _{i=1}^{n}O\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 $b_n$ spełnia

$b_n\cdot \ln b_n=n$

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

$n=b_n\cdot \ln b_n<b_n\ln n$,

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

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

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

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

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

$\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{g(n)}=1$

Fakt, że funkcje $f(n)$ i $g(n)$ są asymptotycznie równe zapisujemy jako $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]

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

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

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

dla pewnej stałej $c$. Wkładem Jamesa Stirlinga było pokazanie, że stałą tą jest $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:

$\sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n{e}^{-(12n+1)}\le n!\le \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 $n$ na sumy dodatnich liczb naturalnych, tzn. asymptotyczne przybliżenie funkcji $p_n=\sum _{k=1}^{n}P(n,k)$ .

Twierdzenie 9.6

$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ż $n$.

Twierdzenie 9.7

Jeśli $\pi (n)$ oznacza liczbę liczb pierwszych w zbiorze $\{1,2,3,\dots ,n\}$, to

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