Informatyka MIMUW

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