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

Żeby zdać sobie sprawę co do rzeczywistej skali ulepszeń rozważmy tabelkę:

N	1 + log₂ N
10	4
100	7
1000	10
milion	20
miliard	30

Zatem przeszukanie książki telefonicznej dla miliarda abonentów wymagałoby jedynie 30 kroków.

Warto zauważyć, że gdy szukamy czegoś w książce telefoniczne świadomie lub nieświadomie stosujemy wariant wyszukiwania binarnego, choć nie porównujemy szukanego nazwiska z nazwiskiem dokładnie w V.2 książki, a potem w ¹/4 lub %. Ale znając nazwisko w sposób przybliżony lokujemy je ograniczając przeszukiwaną listę. Działamy według intuicyjnych reguł tzw. reguł heurystycznych. Okazuje się, że według tych reguł też można budować algorytmy wyszukiwania działające w sposób dopasowany do charakteru i rozkładu elementów. Mają one średnio lepszą złożoność ale wykonują takie pesymistyczne zachowanie typu O (log W). Relacja miedzy złożonością średnia fśrednim czasem oczekiwania na wyniki) a pesymistyczną nie jest ściśle określona, a jej oszacowanie jest trudne i nie ma tu ogólnej metody działania. Bardzo często średnia i pesymistyczna złożoność jest tego samego rzędu. Np. dla większości algorytmów sortowania jest ona typu O (N²). Ale np. dla jednego konkretnego algorytmu Ouicksort, złożoność średnia jest 1.4 N log2 N, a pesymistyczna O (N²) czyli znacznie większa.

Co brać pod uwagę przy szacowaniu złożoności typu O (N²)?

Okazuje się, że decydująca dla czasu działania algorytmu jest rola pętli (czy cykli wykonywanych na zasadzie rekurencji). Inne działania wykonywane jednorazowo mogą, co najwyżej, dodawać jedynie stały składnik do zasadniczego, rosnącego wraz z wykonywaniem pętli czasu wykonywania algorytmu. Podczas każdego obiegu pętli dokonuje się przynajmniej jednego porównania, które decyduje o dalszym działaniu w pętli czy też o jej opuszczeniu. Zatem z dokładnością do stałego czynnika będącego miara liczby instrukcji wykonywanych w pętli można stwierdzić, że liczba czynności wykonywanych przez algorytm decydująca o złożoności O jest określona przez liczbę sprawdzanych warunków (porównań). Zapis złożoności typu O () ignoruje stałe składniki, stąd nie są istotne elementy programu leżące poza pętlami oraz stałe czynniki (czyli liczby instrukcji wewnątrz pętli). Dla algorytmu binarnego wyszukiwania dla listy o długości N całkowita liczba instrukcji jest ograniczona przez K + (M * log2 N), gdzie K liczba instrukcji poza pętlą, a M liczba instrukcji wewnątrz pętli, ale to w naszej notacji nadal oznacza złożoność typu O (log N).

Co ciekawe, mało istotne jest także wewnętrzna struktura instrukcji, z których buduje się algorytm. Zatem oszacowanie typu O 0 jest niezależne od rodzaju języka używanego do zapisu algorytmu . z wyjątkiem wszakże języków, gdzie iteracja będzie ukryta wewnątrz instrukcji (jest tak w językach obsługi baz danych) np. w poleceniu "szukaj E na liście L". Wówczas mamy jedną instrukcję i teoretycznie złożoność O (1). Ale to pozór! Wtedy dla prawdziwego oszacowania złożoności konieczne jest ujawnienie iteracyjności lub rekurencyjności tej instrukcji.

Wspomnieliśmy także, że i podstawa w zapisie O (log N) nie jest istotna i dlatego ją zaniedbujemy. Wszakże

log,, b

log- X=\og_aX

czyli log₃ X i log_b X różnią się jedynie o stały czynnik (log₃ b)'¹.