złożoność obliczeniowa dla algorytmu wyszukiwania sekwencyjn

[111sadysta]

Poniższy algorytm znajduje najmniejszy indeks szukanego elementu (o ile istnieje)

K1. Niech\(\displaystyle{ i \leftarrow 1}\), \(\displaystyle{ K_{n+1}=K}\).
K2. Jeśli \(\displaystyle{ K=K_i}\)to idź do K4.
K3. Niech \(\displaystyle{ i \leftarrow i+1}\). Wróć do K2.
K4. Jeśli \(\displaystyle{ i \le n}\), to algorytm kończy się sukcesem (zwróć \(\displaystyle{ i}\)). W przeciwnym razie algorytm kończy się porażką (zwróć 0).

a) Zapisz klasyczny algorytm wyszukiwania sewwencyjnego w pseudokodzie
b) Dokonując podobnej analizy dla podanego algorytmu przy założeniu, że operacja dominującą jest porównywanie kluczy

[kadiii]

Złożoność tego algorytmu to O(K) czyli złożoność liniowa. Wykonujemy przeszukiwanie element po elemencie więc musimy porównać w najgorszym wypadku wszystkie K kluczy.