Informatyka MIMUW

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

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

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

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

• 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))$,

• 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)=\Theta(g(n))$ wtedy i tylko wtedy, gdy $g(n)=\Theta(f(n))$,

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

Obserwacja 9.2

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

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

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

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

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

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

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

Przykład

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

Zauważmy najpierw, że jeśli $\displaystyle k < l$ to $\displaystyle O(n^k)=O(n^l)$, czyli jeśli $\displaystyle f(n)\in O(n^k)$ to $\displaystyle f(n)\in O(n^l)$. Rozważmy zatem dowolny wielomian $\displaystyle k$-tego stopnia $\displaystyle p(n)=a_kn^k+\ldots+a_1n+a_0$, gdzie $\displaystyle a_k\neq0$. Wtedy

$\begin{array} {rlll} \vert p(n) \vert & =\vert a_kn^k+\ldots+a_1n+a_0 \vert & & \\ & \leq \vert a_k \vert n^k+\ldots+\vert a_1 \vert n+\vert a_0 \vert & \\ & =a_k\cdot O(n^k)+\ldots+a_1\cdot O(n)+a_0\cdot O(1) & \textrm{bo}\quad n^i=O(n^i) \\ & =O(n^k)+\ldots+O(n)+O(1) & \textrm{bo}\quad c\cdot O(n^i) = O(n^i) \\ & =O(n^k)+\ldots+O(n^k)+O(n^k) & \textrm{bo}\quad O(n^i)=O(n^k), \textrm{dla}\quad i\leq k \\ & =O(n^k), & \textrm{bo}\quad O(n^k)+O(n^k)= O(n^k) \end{array}$

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

Dla dowodu $\displaystyle p(n)=\Omega(n^k)$, niech $\displaystyle a=\max(\vert a_{0} \vert,\vert a_{1} \vert,\ldots,\vert a_{k-1} \vert)$. Wtedy

$\displaystyle \vert a_k \vert n^k\geq 2kan^{k-1}\geq 2(\vert a_{k-1} \vert n^{k-1}+\vert a_{k-2} \vert n^{k-2}+\ldots+\vert a_0 \vert)$

dla $\displaystyle n\geq \frac{2ka}{\vert a_k \vert}$. Mamy zatem

$\displaystyle \begin{align*} \vert p(n) \vert & =\vert a_kn^k+a_{k-1}n^{k-1}+\ldots+a_0 \vert \geq\vert a_k \vert n^k-(\vert a_{k-1} \vert n^{k-1}+\ldots+\vert a_0 \vert) \\ & \geq\vert a_k \vert n^k-kan^{k-1}\geq\frac{\vert a_k \vert n^k}{2}, \end{align*}$

co dowodzi $\displaystyle p(n)=\Omega(n^k)$.

Przykład

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

$\displaystyle \log_a{n}=\Theta(\log_b{n}),\quad \textrm{dla}\quad a,b>1.$

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

$\displaystyle \log_a{n}=\frac{1}{\log_b{a}}\cdot\log_b{n},$

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

Przykład

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

$\displaystyle f = O(g)$ wtedy i tylko wtedy, gdy $\displaystyle \deg(f)\leq \deg(g)$.

Ustala to hierarchię rzędów funkcji:

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

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

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

Na przykład:

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

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

Przykład

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

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

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

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

$\displaystyle (n+1)^3 = n^3 + 3n^2 +3n +1 \leq c \cdot 2^n + c \cdot 2^n = c \cdot 2^{n+1}.$

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

Przykład

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

$\displaystyle (\frac{3}{2})^n = \frac{3^n}{2^n} \leq c,$

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

Przykład

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

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

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

Obserwacja 9.3

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

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

i dalej

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

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

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

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

Przykład

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

$\displaystyle f(n)= \left\{ \begin{array} {cl} n, & \textrm{dla} \quad n \quad \textrm{parzystych} \\ n^3, & \textrm{dla}\quad n\quad \textrm{nieparzystych} \end{array} \right .$

i $\displaystyle g(n)=n^2$ mamy $\displaystyle f(n)\neq\Omega(g(n))$ i $\displaystyle f(n)\neq O(g(n))$.