1 00:00:00,000 --> 00:00:02,892 >> [MIZIK jwe] 2 00:00:02,892 --> 00:00:05,347 3 00:00:05,347 --> 00:00:07,180 Doug Lloyd: Lineyè rechèch se yon algorithm nou 4 00:00:07,180 --> 00:00:09,840 ka itilize yo jwenn yon eleman nan yon etalaj. 5 00:00:09,840 --> 00:00:11,990 Yon rapèl algorithm se yon seri etap-pa-etap 6 00:00:11,990 --> 00:00:15,030 nan enstriksyon pou ranpli yon travay. 7 00:00:15,030 --> 00:00:17,480 >> Rechèch la lineyè algorithm travay jan sa a. 8 00:00:17,480 --> 00:00:22,200 Repekte atravè etalaj la de gòch a dwat, kap chèche yon eleman espesifye. 9 00:00:22,200 --> 00:00:26,380 >> Nan pseudocode, ki se yon plis distile vèsyon an fraz sa a, 10 00:00:26,380 --> 00:00:29,840 si eleman nan premye se sa w ap chèche pou, ou ka sispann. 11 00:00:29,840 --> 00:00:33,930 Sinon, ale nan eleman nan pwochen ak kenbe prale sou yo ak sou jiskaske ou jwenn 12 00:00:33,930 --> 00:00:36,389 eleman nan, oswa ou pa fè sa. 13 00:00:36,389 --> 00:00:38,680 Se konsa, nou ka sèvi ak lineyè nan algorithm rechèch, pou egzanp, 14 00:00:38,680 --> 00:00:42,330 jwenn valè a sib nèf nan etalaj sa a. 15 00:00:42,330 --> 00:00:43,870 Oke nou kòmanse nan kòmansman an. 16 00:00:43,870 --> 00:00:45,970 Si li nan ki sa nou ap kap chèche, nou ka sispann. 17 00:00:45,970 --> 00:00:47,890 Li pa nan, nou ap pa kap chèche 11. 18 00:00:47,890 --> 00:00:50,220 Se konsa, otreman, deplase li nan yon eleman kap vini an. 19 00:00:50,220 --> 00:00:51,510 >> Se konsa, nou gade nan 23. 20 00:00:51,510 --> 00:00:52,730 Se 23 sa nou ap chèche pou? 21 00:00:52,730 --> 00:00:55,614 Oke pa gen okenn, se konsa nou deplase sou pwochen an eleman, ak eleman kap vini an, 22 00:00:55,614 --> 00:00:57,780 epi nou kenbe ale atravè tout pwosesis sa a sou yo ak sou 23 00:00:57,780 --> 00:01:01,030 yo ak sou, jiskaske nou peyi sou yon sitiyasyon tankou sa a. 24 00:01:01,030 --> 00:01:03,910 >> Nèf se sa nou ap chèche pou, ak sa a eleman nan etalaj la 25 00:01:03,910 --> 00:01:05,787 se, valè li a se nèf. 26 00:01:05,787 --> 00:01:08,120 Se konsa, nou jwenn sa nou ap chèche pou yo, epi nou ka sispann. 27 00:01:08,120 --> 00:01:11,910 Rechèch la lineyè gen fini, avèk siksè. 28 00:01:11,910 --> 00:01:15,370 >> Men, sa ki sou si nou ap chèche pou yon eleman sa a, se pa nan etalaj nou an. 29 00:01:15,370 --> 00:01:17,040 Rechèch lineyè toujou travay? 30 00:01:17,040 --> 00:01:17,540 Oke asire w. 31 00:01:17,540 --> 00:01:19,947 Se konsa, nou repete pwosesis sa a kòmanse nan eleman a an premye. 32 00:01:19,947 --> 00:01:21,780 Si li nan ki sa nou ap kap chèche, nou ka sispann. 33 00:01:21,780 --> 00:01:22,800 Li pa. 34 00:01:22,800 --> 00:01:25,020 Sinon, nou deplase li nan yon eleman kap vini an. 35 00:01:25,020 --> 00:01:29,050 >> Men, nou kapab kenbe repete pwosesis sa a, ekzamine chak eleman nan vire, 36 00:01:29,050 --> 00:01:31,720 avèk lespwa ke nou jwenn nimewo a 50. 37 00:01:31,720 --> 00:01:33,750 Men, nou pa pral konnen si nou te jwenn nimewo a 50 38 00:01:33,750 --> 00:01:38,290 oswa si nou pa t ', jouk nou te te demisyone sou tout eleman sèl nan etalaj la. 39 00:01:38,290 --> 00:01:40,440 >> Se sèlman yon fwa nou te fè ki e yo vini ti bout tan, 40 00:01:40,440 --> 00:01:43,040 nou ka konkli ke 50 se pa nan etalaj la. 41 00:01:43,040 --> 00:01:46,410 Se konsa, rechèch la lineyè algorithm, byen li echwe, se pou chak. 42 00:01:46,410 --> 00:01:49,181 Men, pa nan sans ke li te fèt san siksè nan fè sa 43 00:01:49,181 --> 00:01:49,930 nou te mande l 'bay fè. 44 00:01:49,930 --> 00:01:52,390 >> Li te fèt san siksè nan kòm anpil jan li pa t 'jwenn 50, 45 00:01:52,390 --> 00:01:54,070 men 50 pa t 'nan etalaj la. 46 00:01:54,070 --> 00:01:57,310 Men, nou te fouye limitativ nan chak eleman sèl 47 00:01:57,310 --> 00:02:00,550 e konsa, pandan ke nou pa t 'jwenn anyen, rechèch lineyè toujou 48 00:02:00,550 --> 00:02:05,230 reyisi menm si nan eleman se pa nan etalaj la. 49 00:02:05,230 --> 00:02:07,507 >> Se konsa, sa ki nan ka ki pi mal senaryo ak rechèch lineyè? 50 00:02:07,507 --> 00:02:09,590 Oke nou dwe gade nan chak eleman sèl, 51 00:02:09,590 --> 00:02:14,590 swa paske eleman nan sib se eleman ki sot pase a nan etalaj la, 52 00:02:14,590 --> 00:02:18,510 oswa eleman nan nou ap chèche pou pa fè sa aktyèlman egziste nan etalaj la nan tout. 53 00:02:18,510 --> 00:02:19,760 Ki sa ki nan senaryo a ka pi bon? 54 00:02:19,760 --> 00:02:22,430 Oke nou ta ka jwenn nan eleman imedyatman. 55 00:02:22,430 --> 00:02:24,360 Ak ki jan anpil eleman nou Lè sa a gen fè yon gade 56 00:02:24,360 --> 00:02:26,859 a nan ka a pi bon, si nou ap chèche pou li 57 00:02:26,859 --> 00:02:28,400 epi nou jwenn li nan konmansman an anpil? 58 00:02:28,400 --> 00:02:29,850 Nou ka sispann imedyatman. 59 00:02:29,850 --> 00:02:32,984 >> Ki sa sa di sou la konpleksite nan rechèch lineyè? 60 00:02:32,984 --> 00:02:35,650 Byen nan ka ki pi mal, nou gen fè yon gade nan chak eleman sèl. 61 00:02:35,650 --> 00:02:38,930 Se konsa, li kouri nan O nan N, nan ka ki pi mal la. 62 00:02:38,930 --> 00:02:41,540 >> Nan ka ki pi bon, nou ap pral jwenn eleman nan imedyatman. 63 00:02:41,540 --> 00:02:44,750 Se konsa, kouri nan Omega nan 1. 64 00:02:44,750 --> 00:02:45,780 >> Mwen se Doug Lloyd. 65 00:02:45,780 --> 00:02:48,020 Sa a se CS50. 66 00:02:48,020 --> 00:02:49,876