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 Thinking in Java. Edycja polska. Wydanie IV
149,00 zł
Python. Zacznij programować!
89,00 zł
ASP.NET Core 2.0. Wprowadzenie
−30%48,30 zł
Docker. Projektowanie i wdrażanie aplikacji
54,90 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: +1 Tak Nie
Liczba głosów: 1.

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

REKLAMA

Zobacz też

Algorytm genetycznymetaheurystyka inspirowana biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość

Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.

W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:

Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:

Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.

Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.

→ Czytaj całość

Metoda Forda-Fulkersona – algorytm służący do wyznaczania maksymalnego przepływu. Jest to algorytm bardzo ogólny, dlatego często nie jest nazywany algorytmem, a metodą. Popularną implementacją tej metody jest algorytm Edmondsa-Karpa. Algorytm można opisać następująco:

  1. Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
  2. Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
  3. Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
  4. W przeciwnym razie zwiększ przepływ w sieci (w sposób opisany w dalszej części artukułu) i wróć do punktu 1.
→ Czytaj całość
Polityka prywatnościKontakt