Badanie złożoności algorytmów cz I 4

Wszystko to świadczy o sile notacji O (). Ale jest ta siła także powodem stabilności.

Wyobraźmy sobie dwa algorytmy A i B o złożonościach odpowiadających O (log N) i O (W). Może się jednak zdarzyć, że dla pewnych danych algorytm B wykona się szybciej niż A. Diabef tkwi w szczegółach czyli w ukrytych stałych. Może być, że po analizie wszystkiego (liczba istniejących elementów, język programowania, kompilator, szybkość komputera) możemy oszacować, że czas wykonywania algorytmu A to Ci * log2, zaś B — C2 * N, ale Ci = 1000 a C2 = 10. Wtedy algorytm B będzie szybszy dla każdych danych o długości mniejszej niż 1000.

Dowód:

C-i * log₂ N = 10³ log₂ 10³ = 10 3 * 3 * log₂ 10 = 9.96 x 1Q³ log2 10 = 1/ logio 2 = 3.32 C₂ * N = 10 x 1Q³

Łatwo jednak pokazać, że dla N = 10 ⁶ algorytm A staje się szybszy od B 500 razy, zaś N = 10⁹ już 330 tys. razy.

Zatem użytkownik listy danych N > 1000 winien zdecydowanie przyjąć "naiwny" algorytm B mimo teoretycznej (w sensie złożoności) wyższości algorytmu A.

Morał zatem jest taki — szukać najpierw sprawnego w sensie O () algorytmu, ale potem starać się go poprawić (poprzez sztuczki typu używanych poprzednio), by zmniejszyć czynniki stałe. Widać, że sprawność w sensie O () może być myląca. Trzeba uruchomić algorytm i zebrać wyniki pomiaru czasów realizacji dla różnych typów danych.

Pętla zagnieżdżona a sprawność algorytmu:

Dotąd rozważaliśmy algorytmy z pętlami niezagnieżdżonymi. Jaki wpływ na złożoność ma zagnieżdżanie pętli? Oczywiście złożoność wtedy rośnie i można oczekiwać, że w sposób potęgowy, gdzie wykładnikiem potęgi jest krotność zagnieżdżenia. Zatem dla algorytmu działającego na N danych i zawierającego k - krotnie zagnieżdżone pętle złożoność będzie rzędu O (N*).

Przykład:

Jako przykład weźmy technikę sortowania "bąbelkowego".

Wymaga ona w najprostszej wersji dwóch zagnieżdżonych w sobie pętli:

wykonaj N - 1 razy wskaż na pierwszy element wykonaj N - 1 razy

porównaj wskazany element z następnym

jeśli kolejność elementów jest niewłaściwa — przestaw je

wskaż następny element

Pętla wewnętrzna jest wykonywana N - 1 razy dla każdego z W - 1 wykonań pętli zewnętrznej. Zatem (N — 1) (N — 1) = N² — 2N + 1.

Dominującym dla dużych N składnikiem jest N², stąd złożoność jest typu O (N²).

Algorytm sortowania bąbelkowego można jednak ulepszyć wykorzystując fakt, że coraz większa część listy jest posortowana i przeglądania wymaga coraz to mniejsza część listy. Musimy wtedy dokonywać porównywania i przestawiania malejącej liczby elementów listy. Stąd oszacowanie:

<N - 1) + <N - 2) + (N - 3) + ... + 3 + 2 + 1 = (N² - N) / 2

jako suma tego szeregu arytmetycznego

To mniej niż N² -2N + 1 o około 50%, ale po pominięciu stałych czynników i składników i tak daje złożoność O (N²). Widać, że algorytmy sortowania są rzędu O (N²) (jak to już zauważyliśmy przedtem), podczas gdy algorytmy prymitywnego wyszukiwania są liniowe a wyszukiwania binarnego - logarytmiczne.