Notacja dużego O

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Zasugerowano, aby ten artykuł zintegrować z artykułem Asymptotyczne tempo wzrostu. (dyskusja)

Notacja dużego O (wielka litera O, nie zero), zwana również notacją Landaua, to symbolika używana w teorii złożoności obliczeniowej, informatyce i matematyce do opisu asymptotycznego zachowania funkcji. Notacja Landaua opisuje, jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.

Nazwa notacja Landaua pochodzi od niemieckiego teoretyka liczb Edmunda Landaua, który spopularyzował tę notację.

Spis treści

1 Definicje
2 Uwagi
3 Przykłady
- 3.1 Standardowe oszacowania
4 Rozwinięcie symboliki
5 Zobacz też

[edytuj] Definicje

Niech dane będą funkcje $f(x)\,$ i $g(x)\,$ zmiennej rzeczywistej o wartościach rzeczywistych.

Zapis $f(x)=O(g(x)) \,$ oznacza, że istnieje taka liczba $C>0\,$ i takie $x_0\,$ , że dla wszystkich $x > x_0\,$ zachodzi nierówność

$|f(x)| \leq C \cdot |g(x)|\,$ .

Wersja notacji dla zachowania się funkcji w pobliżu punktu $a\,$ :

$f(x)=O(g(x)) \,$ , jeżeli istnieje takie $C>0\,$ i takie $\delta>0\,$ , że dla dowolnych $x\,$ takich, że $|x-a|<\delta\,$ zachodzi nierówność

$|f(x)| \leq C \cdot |g(x)|$ .

Należy zauważyć, że nie precyzuje się tu dziedziny funkcji $f\,$ i $g\,$ – zależy ona od kontekstu w jakim występują obie funkcje.

[edytuj] Uwagi

Znak "=" nie oznacza tutaj równości, jest on zdefiniowany przez podane wyżej określenia. Notacja O-duże pozwala wykonywać działania na funkcjach, na przykład:

jeśli $f (x) = O (r (x))$ i $g (x) = O (r (x))$ , to również $f(x) \pm g(x) = O(r(x))$ .
przy założeniach jak poprzednio, $f(x) \cdot g(x) = O(r^2(x))$

Wygoda notacji O-duże widoczna jest w następującej sytuacji: jeżeli $f (x) = 2 x 3 - x 2 + 100 x$ , to można napisać zarówno $f (x) = O (x 3)$ , jak i $f (x) = 2 x 3 + O (x 2)$ , czy wreszcie $f (x) = 2 x 3 - x 2 + O (x)$ , zależnie od wymaganej dokładności oszacowań.

Napis $g(x) = f(x)+O(h(x))\,$ należy rozumieć jako $g(x)-f(x) = O(h(x))\,$ .

[edytuj] Przykłady

Jeżeli $f (x) = 1000 x 50 + 2 x 2$ oraz $g (x) = 0,0000001 x 50 + 665 x$ , to $f(x)=O(x^{50})\,$ oraz $g(x) = O(x^{50})\,$ , ale również $f(x) = O(g(x))\,$ .
Niech $S(n) = 1 + 2 + \cdots + n$ . Korzystając ze wzorów sumacyjnych: $S(n)=\frac{n(n+1)}{2} < 3 \cdot n^2$ , a zatem $O(n^2)\,$ .
Jeżeli potrzebne jest dokładniejsze oszacowanie $S(n)\,$ , to na podstawie tego samego wzoru sumacyjnego można napisać $S(n)= \frac{n^2}{2} + \frac{n}{2} = \frac{n^2}{2}+O(n)$ .
Analogicznie można napisać, że $1^2 + 2^2 + \cdots + n^2 = O(n^3)$ .

[edytuj] Standardowe oszacowania

W zastosowaniach szczególnie często notacja O-duże pojawia się w następujących sytuacjach:

$f(x)=O(1)\,$ – funkcja $f (x)$ jest ograniczona
$f(x)=O(\log n)\,$ – funkcja $f (x)$ jest ograniczona przez funkcję logarytmiczną
$f(x)=O(n)\,$ – funkcja $f (x)$ jest ograniczona przez funkcję liniową
$f(x)=O(n \log n)\,$
$f(x)=O(n^k)\,$ – funkcja $f (x)$ jest ograniczona przez funkcję potęgową lub wielomian
$f(x)=O(a^n)\,$ – funkcja $f (x)$ jest ograniczona przez funkcję wykładniczą
$f(x)=O(n!)\,$ – funkcja $f (x)$ jest ograniczona przez silnię

[edytuj] Rozwinięcie symboliki

Notacja O-duże pozwala tylko stwierdzić, że wzrost danej funkcji nie jest szybszy niż wzrost funkcji podanej w nawiasie za O. Często to nie wystarcza – notacja Landaua obejmuje i takie przypadki. Pisze się:

$f(x) = \Omega(g(x))\,$ , gdy $g(x) = O(f(x))\,$ – teraz $g (x)$ ogranicza wzrost $f (x)$ od dołu. Oznacza to, że istnieje taka stała $c$ , że $|g(x)| \leq c \cdot |f(x)|$ dla $x$ określonych jak w definicji $O$ .
$f(x) = \Theta(g(x))\,$ , gdy $f(x) = O(g(x))\,$ i $f(x) = \Omega(g(x))\,$ jednocześnie. Oznacza to, że istnieją stałe $c$ i $C$ takie, że $c \cdot |g(x)| \leq |f(x)| \leq C \cdot |g(x)|$ dla wszystkich dużych $x$ , a zatem funkcje $f$ i $g$ wzrastają "jednakowo" szybko.
$f(x) = o(g(x))\,$ , gdy $\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0$
$f(x) = \omega(g(x))\,$ , gdy $g(x) = o(f(x)\,$ )