Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.

Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n²+20n+100 możemy zapisać jako O(n²). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.

Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n². Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.

Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v²e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.

Przykładowe rzędy złożoności

Przykładowe rzędy złożoności funkcji (posortowane rosnąco) to:

• O(1) – złożoność stała,
• O(logn) – złożoność logarytmiczna,
• O(n) – złożoność liniowa,
• O(nlogn) – złożoność liniowo-logarytmiczna,
• O(n²) – złożoność kwadratowa,
• O(n^k), gdzie k jest stałą – złożoność wielomianowa,
• O(kⁿ), gdzie k jest stałą – złożoność wykładnicza,
• O(n!) – złożoność rzędu silnia,

Przyjmuje się, że największą akceptowalną złożonością obliczeniową algorytmu jest złożoność wielomianowa. Istnieją jednak problemy obliczeniowe, dla których algorytm o takiej złożoności nie jest znany i być może w ogóle nie da się go opracować. Znanym przykładem takiego problemu jest problem komiwojażera.

REKLAMA

Formalna definicja

Zapis f(n) = O(g(n)) oznacza, że istnieje taka wartość n₀, że dla każdego n większego od n₀ jest spełniona nierówność: f(n) ≤ cg(n), gdzie c jest stałą wartością.

W zapisie tym można zauważyć pewną nieścisłość. O(g(n)) nie jest pojedynczą funkcją, ale całym ich zbiorem. Dlatego prawidłowym zapisem powinno być f(n) ∈ O(g(n)). Powszechnie używany jest jednak zapis ze znakiem równości.

Można również zauważyć, że definicja ta stanowi tylko ograniczenie górne. W związku z tym zapisy typu 2n = O(n¹⁰) są poprawne, choć bardzo nieprecyzyjne. Podobnie, jak stwierdzenie mam w kieszeni co najwyżej kilka tysięcy złotych jest prawdziwe również wtedy, gdy mówiący ma w kieszeni złotówkę.

Notacje pokrewne

Jak już zauważyliśmy, notacja dużego O określa asymptotyczne ograniczenie górne. W analogiczny sposób można zapisać asymptotyczne ograniczenie dole. Do jego zapisu wykorzystywana jest notacja Ω (omega). Formalnie można ją zdefiniować tak: f(n) = Ω(g(n)) oznacza, że istnieje taka wartość n₀, że dla każdego n większego od n₀ jest spełniona nierówność: f(n) ≥ cg(n), gdzie c jest stałą wartością.

Łącząc ograniczenie górne i dolne otrzymujemy oszacowanie asymptotycznie dokładne. Do jego zapisu wykorzystywana jest notacja Θ (theta). Aby można było zapisać f(n) = Θ(g(n)), prawdziwe musi być zarówno wyrażenie f(n) = Ω(g(n)), jak i f(n) = O(g(n)).

Można z tego wysnuć wniosek, że notacja Θ jako najbardziej precyzyjna powinna być najczęściej używana. Jednak jej używanie do zapisu złożoności często byłoby błędne, gdyż nie uwzględniłoby przypadków optymistycznych. Przykładowo, pesymistyczna (a nawet średnia) złożoność czasowa sortowania przez wstawianie jest rzędu O(n²). Jeśli jednak dane są wstępnie posortowane, to złożoność redukuje się do O(n). Tak więc stwierdzenie, że algorytm ma złożoność Θ(n²) byłoby nadużyciem. Dlatego bezpieczniejsze jest stosowanie notacji dużego O.

W tym miejscu warto zauważyć, że do zapisu notacji dużego O tak naprawdę powinna być stosowana nie łacińska litera „O”, ale grecka litera „Ο” (omikron).

REKLAMA

Bibliografia

• T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
• A.Y. Bhargava, Algorytmy. Ilustrowany przewodnik, Wydawnictwo HELION, 2017, ISBN 9788328334458 [fragment książki (pdf) • książka w księgarni Helion.pl].
• R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN , Warszawa, 2012, ISBN 9788301147648 [książka w księgarni Helion.pl].