Złożoność czasu wyszukiwania

Wyszukiwanie liniowe to sekwencyjne wyszukiwanie. Ta metoda wyszukiwania sprawdza elementy listy jeden po drugim, zaczynając od pierwszego elementu. Kiedy zobaczy pierwsze wystąpienie elementu, którego szuka, wyszukiwanie kończy się. Element, którego szuka, nazywa się cel. Jeśli element nie zostanie znaleziony, wszystkie elementy na liście są sprawdzane. Wyszukiwanie liniowe jest bardzo prostym algorytmem wyszukiwania, którego każdy programista powinien się uczyć, oficjalnie lub intuicyjnie.

Rozważ następującą listę:

I j a c b g d h e f

Aby poszukać a, program musi iterować listę 3 razy. Aby szukać G, program musi iterować listę 6 razy. Aby szukać F, program musi iterować listę 10 razy. Aby szukać k lub dowolnego listu, który nie ma na liście, program musi iterować listę 10 razy i nie znajdzie dopasowania.

Celem tego artykułu jest wytworzenie złożoności czasowej dla wyszukiwania liniowego. Programowanie odbywa się w następującej dyskusji C.

Liniowy algorytm wyszukiwania

Algorytm do wyszukiwania liniowego jest prosty. Załóżmy, że lista jest tablicą opartą na zerowej indeksie. Niech zmienna reprezentująca każdy indeks będzie i. Niech tablica ma nazwę a. Kroki są następujące:

• • Niech będę 0.
  • Jeśli [i] jest celem, wartość i jest zwracana, a wyszukiwanie kończy się pomyślnie.
  • Jeśli [i] nie jest celem, zwiększ i o 1 i powtórz poprzedni krok.
  • Podczas gdy ja jest mniej niż n, gdzie n jest długością tablicy, powtarzaj poprzednie dwa kroki w kolejności.
  • Kontynuuj w ten sposób, aż cel zostanie znaleziony lub nie znaleziono.

Wyszukiwanie kończy się pomyślnie po znalezieniu celu. Wyszukiwanie kończy się bezskutecznie, gdy cel nie zostanie znaleziony. Aby uzyskać nieudane zakończenie, wszystkie elementy N są sprawdzane.

Złożoność czasu

Złożoność czasu to liczba głównych operacji dla niektórych kodów, aby wykonać swoje zadanie. Sprawdzanie, czy cel pasuje do elementu to jedna operacja. Istnieje gorsza złożoność czasu, średnia złożoność czasu i najlepiej złożoność czasu.

Gorsza złożoność czasu

Maksymalna liczba operacji występuje, gdy cel znajduje się na końcu listy lub w ogóle nie jest na liście. To jest gorszy przypadek. Złożoność czasowa jest podana jako:

NA)

To wykorzystuje notację Big-O. Notacja Big-O zaczyna się od wielkimi O, a następnie nawiasów. Wewnątrz nawiasów znajduje się wyrażenie liczby operacji w celu rozwiązania zadania.

Najlepsza złożoność czasu

Jeśli pierwszym elementem listy jest cel, tylko jedna operacja sprawdzania jest konieczna do wyszukiwania. To znaczy tylko jedna operacja jest konieczna do wyszukiwania. To jest najlepiej złożoność czasu. Jest napisane jako:

O (1)

Gdzie 1 w nawiasach oznacza jedną operację.

Średnia złożoność czasu

Średnia złożoność czasu zależy od rozkładu prawdopodobieństwa. Jeśli każdy element może być w dowolnej pozycji, każdy element może zostać przeszukany. W tej sytuacji średnia złożoność czasu jest podana jako:

O (N/2)

Programowanie w c

Wyszukiwanie liniowe to prawdopodobnie najłatwiejsze wyszukiwanie do napisania programu. Po prostu postępuj zgodnie z algorytmem, który jest tutaj powtarzany, aby uzyskać łatwe odniesienie:

• • Niech będę 0.
  • Jeśli [i] jest celem, wartość i jest zwracana, a wyszukiwanie kończy się pomyślnie.
  • Jeśli [i] nie jest celem, zwiększ i o 1 i powtórz poprzedni krok.
  • Podczas gdy ja jest mniej niż n, gdzie n jest długością tablicy, powtarzaj poprzednie dwa kroki w kolejności.
  • Kontynuuj w ten sposób, aż cel zostanie znaleziony lub nie znaleziono.

Zasadniczo program jest następujący:

#włączać
int linearSearch (char a [], int n, char t)
dla (int i = 0; iif (t == a [i])
powrót i;

Zaczyna się od włączenia Stdio.Biblioteka H, ​​która jest odpowiedzialna za wejście i wyjście. Następnie istnieje definicja funkcji LinearSearch (). Głównym kodem w definicji funkcji jest pętla. For pętka skanuje tablicę od początku do końca, szukając dopasowania celu. Jeśli zostanie znaleziony cel, wskaźnik elementu dopasowującego się w tablicy jest zwracany. Aby uzyskać porządek liczby indeksu dopasowanego elementu, dodaj 1 do indeksu opartego na zerowym.

Odpowiednia główna funkcja C dla powyższego programu jest następująca:

int main (int argc, char ** argv)

int n = 10;
char a [] = „i”, „j”, „a”, „c”, „b”, „g”, „d”, „h”, „e”, „f”;
int ret = linearSearch (a, n, „g”);
printf („%i \ n”, ret);
powrót 0;

Pierwsze stwierdzenie głównej funkcji C deklaruje liczbę elementów w danej tablicy. Następnie jest tablica z nazwą a. W tablicy jest dziesięć znaków. Deklaracja tablicy zaczyna się od „char”, a nie „int”. Stamtąd wywoływana jest zdefiniowana funkcja liniowa (). Pierwszym argumentem wywołania funkcji jest tablica. Drugim argumentem jest liczba elementów w tablicy. Trzecim argumentem jest cel, którego obecność w tablicy jest sprawdzana. Jeśli jest obecny, indeks zerowy jest zwracany. Jeśli nie jest obecny, nic nie jest zwracane.

Następna instrukcja drukuje wszelkie zwrócone indeks. W przypadku tej głównej funkcji C 5 jest wydrukowane. Jeśli 1 zostanie dodane do 5, byłoby to 6, czyli indeks porządkowy.

Wniosek

Złożoność czasowa jest podana jako:

NA)

To wykorzystuje notację Big-O. Notacja Big-O zaczyna się od wielkimi O, a następnie nawiasów. Wewnątrz nawiasów znajduje się wyrażenie liczby operacji w celu rozwiązania zadania.

Jeśli pierwszym elementem listy jest cel, tylko jedna operacja sprawdzania jest konieczna do wyszukiwania. To znaczy tylko jedna operacja jest konieczna do wyszukiwania. To jest najlepiej złożoność czasu. Jest napisane jako:

O (1)

Gdzie 1 w nawiasach oznacza jedną operację.

Średnia złożoność czasu zależy od rozkładu prawdopodobieństwa. Jeśli każdy element może być w dowolnej pozycji, wówczas każdy element może zostać przeszukany przez ten algorytm. W tej sytuacji średnia złożoność czasu wynosi:

O (N/2)