ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU

ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU

Złożoność czasową wyrażamy albo w jednostkach czasu, albo w liczbie operacji dominujących, które należy wykonać dla n danych, aby otrzymać rozwiązanie problemu. Operacja dominująca jest operacją, której wykonanie bezpośrednio wpływa na czas wykonania całego algorytmu. Podawanie złożoności czasowej w jednostkach czasu jest niewygodne, ponieważ wynik zależy od szybkości komputera, na którym dokonano pomiarów - trudno takie wyniki odnieść do innych komputerów, szczególnie wyposażonych w inne procesory, gdzie czas wykonania podobnych operacji może znacznie się różnić. Dlatego częściej złożoność czasową wyrażamy w liczbie operacji dominujących, gdyż każdy komputer, bez względu na swoje własności, operacje te musi wykonać. Dzięki temu wynik uniezależniamy od faktycznej szybkości komputerów

Ponieważ często zużycie zasobów w algorytmie uzależnione jest od postaci przetwarzanych danych, zarówno złożoność czasowa jak i pamięciowa może występować w trzech odmianach:

• T_O(n) - optymistycznej (ang. optimistic)
• T_A(n) - średniej (ang. average)
• T_W(n) - pesymistycznej (ang. worst)

Aby poglądowo wyjaśnić powyższe terminy, rozważmy prosty algorytm wyszukiwania robaczywego jabłka w koszu n jabłek. Algorytm jest bardzo prosty:

Dopóki w koszu są jabłka, wyjmij jedno jabłko z kosza, obejrzyj je, jeśli jest robaczywe, to zakończ. Inaczej odłóż je na bok i wróć do początku.

Rozważmy, ile operacji dominujących (ocena jabłka) wykona ten algorytm dla n jabłek.

1. Zakładamy przypadek optymistyczny - robaczywe jabłko napotkamy za pierwszym razem. Zatem:
   T_o(n) = 1 - złożoność optymistyczna
2. Zakładamy przypadek najgorszy - w koszu brak jabłek robaczywych lub robaczywe jabłko będzie wyjęte z kosza jako ostatnie:
   T_w(n) = n - złożoność pesymistyczna
3. W przypadku typowym robaczywe jabłko znajdziemy po przeglądnięciu połowy jabłek w koszu - tzn. raz będzie ono wyciągnięte wcześniej, raz później, a średnio w ⁿ/₂ teście:
   T_A(n) = ⁿ/₂ - złożoność średnia, oczekiwana

Zatem podsumowując:

Złożoność optymistyczna określa zużycie zasobów dla najkorzystniejszego zestawu danych.

Złożoność średnia określa zużycie zasobów dla typowych (tzw. losowych) danych.

Złożoność pesymistyczna określa zużycie zasobów dla najbardziej niekorzystnego zestawu danych.