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

Ulepszenia rzędu wielkości:

Poprzednio udało się nam skrócić czas o połowę. Sąjednak sytuacje i algorytmy, gdy możemy uzyskać ulepszenia rzędu wielkości wymaganego czasu obliczeń.

Rozważmy algorytm dotyczący wyszukiwania elementu w posortowanej, czyli uporządkowanej liście elementów np. telefonu jakiejś osoby we fragmencie książki telefonicznej. Gdyby zastosować tu algorytm z poprzedniego przykładu, czyli przeszukując listę element po elemencie każdorazowo sprawdzając czy jest to szukany element i czy jest już koniec listy, to dla listy N-elementowej wymagać to będzie w najgorszym przypadku N porównań (gdy szukanego elementu nie ma na liście lub jest na końcu) i 2N operacji.Mówimy wtedy, że ów algorytm wymaga dla wykonania w pesymistycznym przypadku czasu rzędu N. Zatem zależy linowo od liczby danych. Nazywamy to złożonością rzędu O (N). Liniowego charakteru tej złożoności nie zmieni użycie naszej inteligentnej sztuczki, bo może ona zmniejszyć czas do powiedzmy N, ale dalej będzie to złożoność rzędu O (N). Nie jest więc istotne czy czyli algorytm wykonuje się w czasie N, N / 2 czy 100 N. Istotna jest liniowa zależność czyli istnienie stałej K. takiej że algorytm wykonuje się nie dłużej niż w czasie K* N. Fakt ten jest prawdziyyy dla każdego N i dla każdych danycho długości N.

Można jednak dla tego samego zadania zbudować algorytm, który daje przyspieszenie nie typu zmiany "wewnętrznego czynnika" w O (N), ale rzędu wielkości. Takim algorytmem dla naszego przykładu będzie wyszukiwanie binarne:

wyszukaj E w liście [L (1)... L (N)] jeśli lista pusta wypisz "nie ma"; STOP podział listy na pół e = L (N / 2) wypisz "jest"; STOP inaczej

jeśli E < L (N /2) wyszukaj E w liście [L (1)... L (N / 2)] jeśli E > L (N / 2) wyszukaj E w liście [L (N12)... L (N)]

Powyższy algorytm ma charakter rekurencyjny (bo jest to jakby procedura obejmująca powtarzany etap czynności, zmieniać się będzie tylko lista, redukcja do połowy), ale można go też zapisać iteracyjnie:

wyszukaj E w liście [L (1)... L (N)] początek = L (1) koniec = L (N)

Dalej:

środek = (koniec — początek) / 2 jeśli E = L (środek) wypisz "jest" STOP inaczej

jeśli X < L (środek koniec = środek jeśli X > L (środek) początek = środek jeśli początek > koniec wróć do Dalej 1. inaczej wypisz "nie ma" STOP

Ten algorytm jest bardzo skuteczny i poprawny. Na pewno znajdzie E, jeśli tylko jest na liście. Jest bardzo szybki. Wymaga wykonania tylu kroków ile razy można podzielić N przez 2 zanim zmaleje do zera. Liczba ta wynosi Log2 N+1 (loęj2 N daje redukcja do 1). Zatem złożoność naszego wyszukiwania binarnego to 0 flog fNV> — przy opisie złożoności ignoruje sie stałe składniki i czynniki — wtv także podstawę logarytmów.