1 00:00:00,000 --> 00:00:02,892 >> [Glazbom] 2 00:00:02,892 --> 00:00:05,347 3 00:00:05,347 --> 00:00:07,180 Doug LLOYD: Linearni Potraga je algoritam smo 4 00:00:07,180 --> 00:00:09,840 možete koristiti kako bi pronašli jedan element u nizu. 5 00:00:09,840 --> 00:00:11,990 Algoritam opoziv je korak-po-korak set 6 00:00:11,990 --> 00:00:15,030 uputa za dovršetak zadatka. 7 00:00:15,030 --> 00:00:17,480 >> Linearni pretragu algoritam radi na sljedeći način. 8 00:00:17,480 --> 00:00:22,200 Ponoviti preko polja s lijeva na pravo, u potrazi za određeni element. 9 00:00:22,200 --> 00:00:26,380 >> U pseudokod, što je još destilirana verzija ove rečenice, 10 00:00:26,380 --> 00:00:29,840 Ako je prvi element koji što tražite, možete zaustaviti. 11 00:00:29,840 --> 00:00:33,930 Inače, premjestiti na sljedeću elementa i zadržati ide više i više, sve dok ne pronađete 12 00:00:33,930 --> 00:00:36,389 element, ili ne. 13 00:00:36,389 --> 00:00:38,680 Dakle, možemo koristiti linearni algoritam za pretraživanje, primjerice, 14 00:00:38,680 --> 00:00:42,330 pronaći ciljanu vrijednost devet u ovom nizu. 15 00:00:42,330 --> 00:00:43,870 Pa smo započeli na početku. 16 00:00:43,870 --> 00:00:45,970 Ako je to ono što smo u potrazi za, možemo zaustaviti. 17 00:00:45,970 --> 00:00:47,890 To je ne, nismo u potrazi za 11. 18 00:00:47,890 --> 00:00:50,220 Dakle inače, pomicanje na sljedeći element. 19 00:00:50,220 --> 00:00:51,510 >> Dakle, mi gledamo na 23. 20 00:00:51,510 --> 00:00:52,730 Je li 23 ono što tražite? 21 00:00:52,730 --> 00:00:55,614 Pa ne, pa smo prešli na sljedeći Element, a sljedeći element 22 00:00:55,614 --> 00:00:57,780 a mi zadržati ide kroz ovaj proces više i više 23 00:00:57,780 --> 00:01:01,030 i više, dok ne sletimo na ovakvoj situaciji. 24 00:01:01,030 --> 00:01:03,910 >> Devet je ono što tražimo, i to element polja 25 00:01:03,910 --> 00:01:05,787 je, to je vrijednost devet. 26 00:01:05,787 --> 00:01:08,120 I tako smo našli ono što smo traže, a mi možemo zaustaviti. 27 00:01:08,120 --> 00:01:11,910 Linearni pretraga završena uspješno. 28 00:01:11,910 --> 00:01:15,370 >> Ali što ako smo u potrazi za element koji nije u našem nizu. 29 00:01:15,370 --> 00:01:17,040 Da li linearno pretraživanje i dalje raditi? 30 00:01:17,040 --> 00:01:17,540 Pa sigurno. 31 00:01:17,540 --> 00:01:19,947 Tako smo ponoviti ovaj postupak počevši od prvog elementa. 32 00:01:19,947 --> 00:01:21,780 Ako je to ono što smo u potrazi za, možemo zaustaviti. 33 00:01:21,780 --> 00:01:22,800 Nije. 34 00:01:22,800 --> 00:01:25,020 Inače, mi premjestiti na sljedeću elementu. 35 00:01:25,020 --> 00:01:29,050 >> Ali možemo zadržati taj proces ponavlja, ispitivanje svaki element pak, 36 00:01:29,050 --> 00:01:31,720 u nadi da ćemo pronaći broj 50. 37 00:01:31,720 --> 00:01:33,750 No, nećemo znati je li našli smo broj 50 38 00:01:33,750 --> 00:01:38,290 ili ako nije, dok smo zakoračili tijekom svakog elementa niza. 39 00:01:38,290 --> 00:01:40,440 >> Samo jednom smo učinili da i dolazi do kratkog, 40 00:01:40,440 --> 00:01:43,040 možemo zaključiti da 50 nije u nizu. 41 00:01:43,040 --> 00:01:46,410 I tako je linearna pretragu algoritam, ali to nije uspio, sam po sebi. 42 00:01:46,410 --> 00:01:49,181 Ali ne u smislu da bio je neuspješan u tome što 43 00:01:49,181 --> 00:01:49,930 smo ga pitali za napraviti. 44 00:01:49,930 --> 00:01:52,390 >> To je bio neuspješan u što koliko je nije pronašla 50, 45 00:01:52,390 --> 00:01:54,070 ali 50 nije bio u polju. 46 00:01:54,070 --> 00:01:57,310 Ali mi iscrpno su tražili kroz svaku elementa 47 00:01:57,310 --> 00:02:00,550 i tako, dok nisu pronašli ništa, linearni traži dalje 48 00:02:00,550 --> 00:02:05,230 uspijeva čak i ako je element nije u nizu. 49 00:02:05,230 --> 00:02:07,507 >> Dakle, što je najgori slučaj Scenarij s linearnim pretraživanjem? 50 00:02:07,507 --> 00:02:09,590 Pa moramo gledati kroz svaki element 51 00:02:09,590 --> 00:02:14,590 bilo zato što je ciljani element koji je posljednji element niza, 52 00:02:14,590 --> 00:02:18,510 ili element tražimo ne zapravo postoje u nizu na sve. 53 00:02:18,510 --> 00:02:19,760 Koji je najbolji mogući scenarij? 54 00:02:19,760 --> 00:02:22,430 Pa možemo naći Element odmah. 55 00:02:22,430 --> 00:02:24,360 A koliko su elementi mi onda morate gledati 56 00:02:24,360 --> 00:02:26,859 na u najboljem slučaju, ako ste u potrazi za njom 57 00:02:26,859 --> 00:02:28,400 a mi ga pronaći na samom početku? 58 00:02:28,400 --> 00:02:29,850 Možemo prestati odmah. 59 00:02:29,850 --> 00:02:32,984 >> Što to govori o Složenost linearno pretraživanje? 60 00:02:32,984 --> 00:02:35,650 Pa u najgorem slučaju, imamo gledati na svakog pojedinog elementa. 61 00:02:35,650 --> 00:02:38,930 I tako se radi u O. nje, u najgorem slučaju. 62 00:02:38,930 --> 00:02:41,540 >> U najboljem slučaju, mi ćemo odmah naći element. 63 00:02:41,540 --> 00:02:44,750 I tako radi omega od 1. 64 00:02:44,750 --> 00:02:45,780 >> Ja sam Doug Lloyd. 65 00:02:45,780 --> 00:02:48,020 Ovo je CS50. 66 00:02:48,020 --> 00:02:49,876