Notacja dużego O

Wykresy funkcji (1) Wykresy funkcji: x2 (czarny), 50x+100 (czerwony) i 200log2x+1000 (zielony). Możemy zauważyć, że powyżej pewnej wartości x decydujące znaczenie ma rząd wieklości funkcji, a nie stałe współczynniki
REKLAMA Algorytmy. Ćwiczenia
34,90 zł
Wzorce projektowe. Elementy oprogramowania obiektowego wielokrotnego użytku
59,00 zł
WordPress 5 dla początkujących
−30%41,30 zł
Django 2. Praktyczne tworzenie aplikacji sieciowych. Wydanie II
79,00 zł

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)=5n2+20n+100 możemy zapisać jako O(n2). 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) = n2. 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(v2e). 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(n2) – złożoność kwadratowa,
  • O(nk), gdzie k jest stałą – złożoność wielomianowa,
  • O(kn), 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.

Formalna definicja

Zapis f(n) = O(g(n)) oznacza, że istnieje taka wartość n0, że dla każdego n większego od n0 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(n10) 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ść n0, że dla każdego n większego od n0 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(n2). 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ść Θ(n2) 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).

Bibliografia

Ocena: +3 Tak Nie
Liczba głosów: 3.

Dodano: 1 lutego 2018 16:17, ostatnia edycja: 26 stycznia 2019 17:44.

REKLAMA

Zobacz też

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość

2-opt, algorytm 2-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Jest to szczególny przypadek algorytmu k-optymalnego.

Algorytm 2-opt nie służy do wyznaczania trasy, a jedynie do ulepszania jej. Samą trasę można wyznaczyć np. za pomocą algorytmu najbliższego sąsiada. Algorytm może być wykorzystany do ulepszenia algorytmu genetycznego – w ten sposób powstanie algorytm memetyczny.

→ Czytaj całość

Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra.

Algorytm realizuje podejście zachłanne. W każdej iteracji wybierany jest ten spośród nieodwiedzonych wierzchołków, do którego można dotrzeć najmniejszym kosztem. Po wyznaczeniu ścieżki do konkretnego wierzchołka nie zostanie ona zmodyfikowana w trakcie wykonywania dalszej części algorytmu.

→ Czytaj całość
Polityka prywatnościKontakt