PA170028

Ulepszanie rzędu wielkości

Jeżeli czds wykonywania algorytmu jest proporcjonalny do N niezależnie od stałej proporcjonalności mówimy, że algorytm wykonuje się w czasie O(N)

Algorytm z przykładu 8 jest O(N).

Przykład 9

Przeszukiwanie binarne

Ksiqżka telefoniczna liczy milion pozycji N=1 000 000, lista jest posortowana.

Porównujemy nazwisko Y ze środkowym nazwiskiem na liście. Mamy dwie możliwości:

(1)    Y< X500 000

(2)    Y> X5ooooo

Powtarzamy krok dla (1) z górnq połowq listy, a dla (2) z dolnq połowq listy.

Dla miliona daje najwyżej 20 porównań Algorytm ten jest O(lgN)

Sortowanie bqbelkowe .- zagnieżdżone pętle (N-l) Algorytm kwadratowy - 0(N²)