>> [Glazbom]
Doug LLOYD: Linearni Potraga je algoritam smo
možete koristiti kako bi pronašli jedan element u nizu.
Algoritam opoziv je korak-po-korak set
uputa za dovršetak zadatka.
>> Linearni pretragu algoritam radi na sljedeći način.
Ponoviti preko polja s lijeva na pravo, u potrazi za određeni element.
>> U pseudokod, što je još destilirana verzija ove rečenice,
Ako je prvi element koji što tražite, možete zaustaviti.
Inače, premjestiti na sljedeću elementa i zadržati ide više i više, sve dok ne pronađete
element, ili ne.
Dakle, možemo koristiti linearni algoritam za pretraživanje, primjerice,
pronaći ciljanu vrijednost devet u ovom nizu.
Pa smo započeli na početku.
Ako je to ono što smo u potrazi za, možemo zaustaviti.
To je ne, nismo u potrazi za 11.
Dakle inače, pomicanje na sljedeći element.
>> Dakle, mi gledamo na 23.
Je li 23 ono što tražite?
Pa ne, pa smo prešli na sljedeći Element, a sljedeći element
a mi zadržati ide kroz ovaj proces više i više
i više, dok ne sletimo na ovakvoj situaciji.
>> Devet je ono što tražimo, i to element polja
je, to je vrijednost devet.
I tako smo našli ono što smo traže, a mi možemo zaustaviti.
Linearni pretraga završena uspješno.
>> Ali što ako smo u potrazi za element koji nije u našem nizu.
Da li linearno pretraživanje i dalje raditi?
Pa sigurno.
Tako smo ponoviti ovaj postupak počevši od prvog elementa.
Ako je to ono što smo u potrazi za, možemo zaustaviti.
Nije.
Inače, mi premjestiti na sljedeću elementu.
>> Ali možemo zadržati taj proces ponavlja, ispitivanje svaki element pak,
u nadi da ćemo pronaći broj 50.
No, nećemo znati je li našli smo broj 50
ili ako nije, dok smo zakoračili tijekom svakog elementa niza.
>> Samo jednom smo učinili da i dolazi do kratkog,
možemo zaključiti da 50 nije u nizu.
I tako je linearna pretragu algoritam, ali to nije uspio, sam po sebi.
Ali ne u smislu da bio je neuspješan u tome što
smo ga pitali za napraviti.
>> To je bio neuspješan u što koliko je nije pronašla 50,
ali 50 nije bio u polju.
Ali mi iscrpno su tražili kroz svaku elementa
i tako, dok nisu pronašli ništa, linearni traži dalje
uspijeva čak i ako je element nije u nizu.
>> Dakle, što je najgori slučaj Scenarij s linearnim pretraživanjem?
Pa moramo gledati kroz svaki element
bilo zato što je ciljani element koji je posljednji element niza,
ili element tražimo ne zapravo postoje u nizu na sve.
Koji je najbolji mogući scenarij?
Pa možemo naći Element odmah.
A koliko su elementi mi onda morate gledati
na u najboljem slučaju, ako ste u potrazi za njom
a mi ga pronaći na samom početku?
Možemo prestati odmah.
>> Što to govori o Složenost linearno pretraživanje?
Pa u najgorem slučaju, imamo gledati na svakog pojedinog elementa.
I tako se radi u O. nje, u najgorem slučaju.
>> U najboljem slučaju, mi ćemo odmah naći element.
I tako radi omega od 1.
>> Ja sam Doug Lloyd.
Ovo je CS50.