[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.