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
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łą.
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:
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:
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:
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
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)) \).