Przeszukiwanie liniowe (lub wyszukiwanie sekwencyjne) to najprostszy algorytm wyszukiwania informacji w ciągu danych, np. zapisanych w tablicy lub na liście.
Polega na porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji
danych – wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony
klucz, albo niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.
Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do
, gdzie to całkowita liczba elementów. Algorytm ma złożoność 
Algorytm przeszukiwania liniowego:
Liczba koniecznych porównań zależy wprost od położenia szukanego elementu w sekwencji danych – wynosi od 1 do
, gdzie to całkowita liczba elementów. Algorytm ma złożoność
Algorytm przeszukiwania liniowego:
| Dane | n - ilość elementów zbioru x1 .. xn - elementy zbioru y - szukany element |
| Wyniki | jeśli y należy do zbioru: i - indeks pierwszego wystąpienia elementu y w zbiorze, w przeciwnym przypadku informacja, że y nie należy do zbioru, |
| Krok 1 | dla i = 1, 2 .... n: jeśli y = xi to i jest wynikiem, zakończ algorytm {element y po raz pierwszy wystąpił w zbiorze na pozycji i-tej}, w przeciwnym przypadku w zbiorze nie ma elementu równego y, zakończ algorytm. |
Brak komentarzy:
Prześlij komentarz