Notacja dużego O

Notacja dużego O (wielka literą 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ę.

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₀, że dla wszystkich x>x₀ zachodzi nierówność |f(x)| ≤ C·|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 δ>0, że dla dowolnych x takich, że |x - a| < δ zachodzi nierówność |f(x)| ≤ C · |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.

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) ± g(x) = O(r(x)).
przy założeniach jak poprzednio, f(x)·g(x) = O(r²(x))

Wygoda notacji O-duże widoczna jest w następującej sytuacji: jeżeli f(x) = 2x³ - x²+100x, to można napisać zarówno f(x) = O(x³), jak i f(x) = 2x³ + O(x²), czy wreszcie f(x) = 2x³ - x² + 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)).

Przykłady

Jeżeli f(x) = 1000x⁵⁰ + 2x² oraz g(x) = 0,0000001x⁵⁰ + 666x, to f(x) = O(x⁵⁰) oraz g(x) = O(x⁵⁰), ale również f(x) = O(g(x)).
Niech S(n) = 1 + 2 + ... + n. Korzystając ze wzorów sumacyjnych: S(n) = n(n+1)/2 < 3·n², a zatem O(n²).
Jeżeli potrzebne jest dokładniejsze oszacowanie S(n), to na podstawie

tego samego wzoru sumacyjnego można napisać S(n) = n²/2 + n/2 = n²/2 + O(n)

Analogicznie można napisać, że 1² + 2² + ... + n² = O(n³)

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(nlog n)
f(x) = O(n^k) – funkcja f(x) jest ograniczona przez funkcję potęgową lub wielomian
f(x) = O(aⁿ) – funkcja f(x) jest ograniczona przez funkcję wykładniczą
f(x) = O(n!) – funkcja f(x) jest ograniczona przez silnię

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) = Ω(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)| ≤ c·|f(x)| dla x określonych jak w definicji O.
f(x) = Θ(g(x)), gdy f(x) = O(g(x)) i f(x) = Ω(g(x)) jednocześnie. Oznacza to, że istnieją stałe c i C takie, że c·|g(x)| ≤ |f(x)| ≤ C·|g(x)| dla wszystkich dużych x, a zatem funkcje f i g wzrastają "jednakowo" szybko.
f(x) = o(g(x)), gdy lim f(x)/g(x) = 0
f(x) = ω(g(x)), gdy g(x) = o(f(x))

Szczególnie ważne i często używane są dwie pierwsze notacje z tej listy.

Zobacz też