Algorytmy wyszukiwania – podstawy

1.Algorytm wyszukiwania

Sposób postępowania, który pozwala znaleźć w zbiorze danych szukany element albo stwierdzić, że go nie ma. Określa kolejne kroki prowadzące do wyniku.

2.Wyszukiwanie liniowe

Metoda polegająca na sprawdzaniu elementów po kolei, od początku do końca, aż do znalezienia szukanej wartości lub wyczerpania danych. Działa także na danych nieuporządkowanych.

3.Wyszukiwanie binarne

Metoda wyszukiwania w danych uporządkowanych. Polega na porównaniu szukanego elementu ze środkowym i odrzucaniu połowy zbioru, w której na pewno go nie ma.

4.Dane uporządkowane

Zbiór elementów ustawionych według określonej kolejności, na przykład rosnąco lub malejąco. Taki układ jest konieczny, aby poprawnie działało wyszukiwanie binarne.

5.Klucz wyszukiwania

Cecha lub wartość, według której szukamy elementu w zbiorze danych. Może to być na przykład liczba, nazwisko, identyfikator lub kod.

6.Element znaleziony

Sytuacja, w której algorytm odnajduje szukaną wartość. Wynikiem może być sam element, jego pozycja w zbiorze albo informacja, że istnieje.

7.Brak wyniku

Sytuacja, w której po zakończeniu działania algorytmu okazuje się, że szukany element nie występuje w danych.

8.Indeks

Numer pozycji elementu w tablicy lub liście. Często algorytm wyszukiwania zwraca właśnie indeks znalezionego elementu.

9.Porównanie

Podstawowa operacja w algorytmach wyszukiwania. Polega na sprawdzeniu, czy dwa elementy są równe albo który z nich jest większy lub mniejszy.

10.Złożoność czasowa

Opisuje, jak szybko rośnie liczba operacji potrzebnych do wykonania algorytmu wraz ze wzrostem liczby danych. Pozwala porównywać efektywność różnych metod.

11.$O(n)$

Oznaczenie złożoności typowe dla wyszukiwania liniowego. Oznacza, że w najgorszym przypadku liczba sprawdzeń rośnie proporcjonalnie do liczby elementów.

12.$O(\log n)$

Oznaczenie złożoności typowe dla wyszukiwania binarnego. Liczba kroków rośnie dużo wolniej niż liczba elementów, bo w każdym kroku odrzucana jest połowa danych.

13.Najgorszy przypadek

Sytuacja, w której algorytm wykonuje największą możliwą liczbę kroków. Dla wyszukiwania liniowego dzieje się tak zwykle wtedy, gdy elementu nie ma lub jest na końcu.

14.Najlepszy przypadek

Sytuacja, w której algorytm znajduje wynik bardzo szybko. Na przykład w wyszukiwaniu liniowym, gdy szukany element znajduje się na początku zbioru.

15.Środkowy element

Element znajdujący się w połowie rozważanego zakresu danych. W wyszukiwaniu binarnym to od niego zaczyna się podejmowanie decyzji, którą połowę odrzucić.

16.Zakres wyszukiwania

Część zbioru danych, w której algorytm aktualnie szuka elementu. W wyszukiwaniu binarnym zakres ten stopniowo się zmniejsza.

17.Tablica

Struktura danych przechowująca elementy w ustalonej kolejności, zwykle pod numerowanymi indeksami. Często na tablicach pokazuje się działanie algorytmów wyszukiwania.

18.Lista

Uporządkowany zbiór elementów. W prostych zadaniach szkolnych pojęcie listy bywa używane podobnie do tablicy jako zbiór danych do przeszukiwania.

19.Warunek zakończenia

Warunek mówiący, kiedy algorytm ma przestać działać. Na przykład po znalezieniu elementu albo po sprawdzeniu wszystkich możliwych pozycji.

20.Efektywność algorytmu

Ocena, jak dobrze algorytm wykorzystuje czas i zasoby komputera. Przy wyszukiwaniu ważne jest zwłaszcza to, ile porównań trzeba wykonać.

21.Zastosowanie wyszukiwania liniowego

Sprawdza się przy małych zbiorach danych albo wtedy, gdy dane nie są uporządkowane i nie opłaca się ich wcześniej sortować.

22.Zastosowanie wyszukiwania binarnego

Jest bardzo przydatne przy dużych, uporządkowanych zbiorach danych, gdy zależy nam na szybkim odnalezieniu elementu.

23.Ograniczenie wyszukiwania binarnego

Nie można go poprawnie użyć na danych przypadkowo ułożonych. Najpierw zbiór musi być uporządkowany według tego samego klucza, według którego szukamy.

24.Sortowanie a wyszukiwanie

Sortowanie porządkuje dane, a wyszukiwanie służy do odnajdywania elementów. Często opłaca się najpierw posortować dane, aby potem wielokrotnie szybciej je przeszukiwać.