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

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertf(n)\right\vert\leq c\cdot\left\vertg(n)\right\vert} dla wszystkich $n\ge n_0$.
Będziemy też często mówić, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertf(n)\right\vert\leq c\cdot\left\vertg(n)\right\vert} 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.

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