Informatyka MIMUW

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( \sum_{i=0}^n1 )=\frac{1}{n^3}\cdot O(n)=O( \frac{1}{n^2} ).$

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}( a_0+\sum_{i=1}^na_i )=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^{n}O( \frac{1}{n^2} )= \frac{1}{n^3}+\frac{1}{n^3}O(1) \\ & =O( \frac{1}{n^3} ). \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( \frac{1}{n^3} )=\frac{1}{n^3}+\frac{1}{n^3}\cdot O( \frac{1}{n^2} )=O( \frac{1}{n^3} ).$

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( \frac{n}{\ln{n}} )$.

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_{narrow\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}( \frac{n}{e} )^ne^{-(12n+1)}\leq n!\leq \sqrt{2\pi n}( \frac{n}{e} )^{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}$