Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
19,90 zł
Szkoła programisty PLC. Język LAD w programowaniu sterowników przemysłowych
−30%41,30 zł
Algorytmy bez tajemnic
44,90 zł
Czysty kod. Podręcznik dobrego programisty
69,00 zł
Cyberwojna. Metody działania hakerów
49,00 zł
Bitcoin dla zaawansowanych. Programowanie z użyciem otwartego łańcucha bloków. Wydanie II
69,00 zł

Notacja dużego O

Wykresy funkcji 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

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

  1. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012.
  2. A.Y. Bhargava, Algorytmy. Ilustrowany przewodnik, Wydawnictwo Helion, Gliwice, 2017 (fragment książki w PDF).
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 1 lutego 2018 16:17, ostatnia edycja: 1 lutego 2018 16:20.

Zobacz też

Algorytm najmniejszej krawędzi – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną, jednak w inny sposób, niż algorytm najbliższego sąsiada. W anglojęzycznej literaturze algorytm jest najczęściej określany po prostu jako greedy algorithm (algorytm zachłanny), w skrócie GR.
→ Czytaj całość

Metoda przyrostowa – technika projektowania algorytmów polegająca na dodawaniu do rozwiązania kolejnych elementów z danych wejściowych. Przykładem algorytmu opartego na tej metodzie jest sortowanie przez wstawianie, gdzie kolejne elementy są wstawiane do posortowanej części tablicy.

Jest to metoda prosta, jednak sprawdza się tylko dla niektórych problemów obliczeniowych.

→ 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