>> [MUZYKI]
DOUG LLOYD: normalny Wyszukiwarka jest to algorytm
można użyć, aby znaleźć element w tablicy.
Przypomnieć algorytm to zestaw krok po kroku
instrukcji do wykonania zadania.
>> Wyszukiwanie liniowe Algorytm działa w następujący sposób.
Iteracji całej tablicy, od lewej do prawo, szukając określonego elementu.
>> W pseudokodzie, który jest bardziej Wersja destylowana tego zdania,
Jeśli pierwszy element jest tym, co szukasz, możesz przestać.
W przeciwnym razie przejdź do następnego elementu i nie poddawać się w kółko, aż znajdziesz
element, albo nie.
Tak więc możemy użyć liniowy Algorytm poszukiwania np
znaleźć wartość docelową dziewięć w tej tablicy.
Dobrze zacząć od początku.
Jeśli to, co jesteśmy szukamy, możemy zatrzymać.
To nie, my nie szukamy 11.
Więc inaczej, przejście do następnego elementu.
>> Więc patrzymy na 23.
Jest 23, co szukasz?
No nie, więc przechodzimy do następnego elementem, a kolejnym elementem,
A my wciąż przechodzi ten proces w kółko
kółko, aż wylądujemy o takiej sytuacji.
>> Dziewięć jest to, czego szukasz, i ten element macierzy
jest, to jest wartość nie jest dziewięć.
I tak okazało się to, co jesteśmy szuka, a my możemy się zatrzymać.
Wyszukiwanie liniowe ma zakończone powodzeniem.
>> Ale co, jeśli szukamy element, który nie jest w naszej tablicy.
Czy przeszukiwanie liniowe wciąż działa?
No pewnie.
Więc powtórzyć ten proces począwszy od pierwszego elementu.
Jeśli to, co jesteśmy szukamy, możemy zatrzymać.
To nie jest.
W przeciwnym razie, możemy przejść do następnego elementu.
>> Ale możemy powtarzać ten proces, badając każdy element z kolei
mając nadzieję, że znajdziemy numer 50.
Ale nie wiem, czy Odkryliśmy numer 50
lub jeśli nie, dopóki nie wszedł na każdym elemencie tablicy.
>> Tylko raz zrobiliśmy że i wymyślić krótkie,
możemy stwierdzić, że 50 nie znajduje się w tablicy.
I tak przeszukiwanie liniowe Algorytm, dobrze, że nie udało, per se.
Ale w tym sensie, że nie powiodło się w tym, co
Poprosiliśmy go zrobić.
>> To nie powiodła się, jak podobnie jak nie znaleźliśmy 50,
ale 50 nie był w tablicy.
Ale my wyczerpująco wyszukiwane przez każdego elementu
i tak, a nie znaleźliśmy coś, przeszukiwanie liniowe wciąż
powiedzie się, nawet jeśli element ten nie istnieje w tablicy.
>> Więc co jest najgorszym przypadku Scenariusz z wyszukiwania liniowego?
Cóż musimy patrzeć przez każdy pojedynczy element,
albo dlatego, że element docelowy jest to ostatni element tablicy,
lub element szukamy nie faktycznie istnieje w tablicy w ogóle.
Jaki jest najlepszy scenariusz?
Cóż możemy znaleźć Element natychmiast.
I jak wiele elementów Czy więc trzeba szukać
co w najlepszym przypadku, jeśli szukamy dla niego
i znajdujemy go na samym początku?
Możemy natychmiast zatrzymać.
>> Co nam to mówi o Złożoność wyszukiwania liniowego?
Cóż, w najgorszym przypadku, mamy patrzeć na każdego elementu.
I tak to działa w O. n, w najgorszym przypadku.
>> W najlepszym przypadku, zrobimy natychmiast znaleźć element.
I tak trwa w omega 1.
>> Jestem Doug Lloyd.
To CS50.