zdj
1 (3)

Problem wyszukiwania w ciągu uporządkowanym

Algorytm liniowy

/' := 1;

while (/<=/?) and (a<x) do /':=/+1; p = a, =x;

Operacja elementarna: porównania między elementami ciągu a liczbą x.

Rozmiar danych: n - długość ciągu Złożoność czasowa pesymistyczna

Dane ..najgorszego" przypadku to ciąg. w którym x nie występuje i wszystkie liczby w ciągu są mniejsze od x.

(«) = max 11 (d): d s D„} = n = 0 (n)

Programowanie komputerów I

11