1 00:00:00,000 --> 00:00:11,100 >> [Prehrávanie hudby] 2 00:00:11,100 --> 00:00:11,490 >> David J. Malan: Dobre. 3 00:00:11,490 --> 00:00:12,170 Tak vitaj späť. 4 00:00:12,170 --> 00:00:15,180 To je CS50, a je Koniec týždňa tri. 5 00:00:15,180 --> 00:00:17,770 >> Takže pripomínajú v posledných niekoľkých týždňoch, sme strávili celkom dosť 6 00:00:17,770 --> 00:00:20,820 čas na C, na programovanie, na syntax. 7 00:00:20,820 --> 00:00:24,680 A to je celkom normálne, ak ste ešte zápasí s problémovými Set 2, sa 8 00:00:24,680 --> 00:00:25,950 búchanie hlavou proti múru. 9 00:00:25,950 --> 00:00:28,310 Je to tajomné vyzerajúce chybové správy a chyby, ktoré 10 00:00:28,310 --> 00:00:29,220 nemožno úplne naháňať. 11 00:00:29,220 --> 00:00:32,310 Vzhľadom k tomu, byť istí, že práve Doba pár týždňov budete obzerať na 12 00:00:32,310 --> 00:00:35,930 veci ako Caesara a [? V-genair,?] možno aj Crack a 13 00:00:35,930 --> 00:00:40,050 uvedomiť si, ako ďaleko ste prišli v krátkom časovom období. 14 00:00:40,050 --> 00:00:43,670 Takže či je to nejaká útecha, vydrž teraz. 15 00:00:43,670 --> 00:00:46,610 >> V súčasnej dobe sa však začneme prechod na veci vyššej úrovne. 16 00:00:46,610 --> 00:00:49,820 A začneme brať za samozrejmosť, že vy viete, ako programovať, alebo 17 00:00:49,820 --> 00:00:52,090 najmenej počiatky že úroveň pohodlia. 18 00:00:52,090 --> 00:00:56,520 A začneme uvažovať o tom, ako môžeme ísť o navrhovaní programov viac 19 00:00:56,520 --> 00:00:57,440 efektívne. 20 00:00:57,440 --> 00:01:01,090 Ako môžeme ísť o optimalizáciu Účinnosť našich algoritmov a 21 00:01:01,090 --> 00:01:03,110 všeobecne viac riešení zaujímavé problémy. 22 00:01:03,110 --> 00:01:06,850 A začínajú brať za samozrejmosť, že keby sme chceli, mohli by sme kódu vzostupne každý 23 00:01:06,850 --> 00:01:08,350 z príkladov, ktoré máme na mysli. 24 00:01:08,350 --> 00:01:11,430 Takže dnes sme sa nedotýkajte klávesnica pre akejkoľvek forme kódu. 25 00:01:11,430 --> 00:01:15,150 To bude oveľa vyššiu úroveň, a nakoniec, o riešení problémov. 26 00:01:15,150 --> 00:01:20,490 >> Takže sa dostať do tohto bodu, dovoľte mi navrhnúť že nasledujúce sedem 27 00:01:20,490 --> 00:01:24,290 obdĺžniky predstavujú sedem dvere, za ktoré sú celá partia 28 00:01:24,290 --> 00:01:26,340 čísla, medzi ktorými je číslo 50. 29 00:01:26,340 --> 00:01:30,470 Dovoľte mi, aby som to premietnuť na tomto displej i tu. 30 00:01:30,470 --> 00:01:36,770 A navrhnúť, že potrebujeme dobrovoľníka pomôže mi nájsť číslo pred 31 00:01:36,770 --> 00:01:38,140 internet tu. 32 00:01:38,140 --> 00:01:40,755 Poďte hore, v ružovej. 33 00:01:40,755 --> 00:01:43,050 Dobrá. 34 00:01:43,050 --> 00:01:43,930 Ako sa voláte? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [nepočuteľné] 36 00:01:44,850 --> 00:01:45,170 >> David J. Malan: Je nám ľúto? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> David J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Dobre, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Rád Vás vidím. 41 00:01:47,630 --> 00:01:48,370 Poď hore. 42 00:01:48,370 --> 00:01:52,430 Tak to tu je sedem dverí, a to, čo Chcel by som, aby si pre nás, 43 00:01:52,430 --> 00:01:56,560 v prednej časti všetkých vašich spolužiakov, sa k nám dostanete číslo, 50. 44 00:01:56,560 --> 00:02:00,860 Ak chcete nájsť číslo, môžete nahliadnuť za niektoré z týchto dverí jednoduchým poklepaním 45 00:02:00,860 --> 00:02:03,030 na jednej strane dverí, a to odhalí jeho číslo. 46 00:02:03,030 --> 00:02:06,080 A pozrime sa, ako rýchlo sa Nájdete u nás číslo, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16.. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Dobrá práca. 54 00:02:17,350 --> 00:02:18,040 Dobrá. 55 00:02:18,040 --> 00:02:19,906 Potlesk pre Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [APPLAUSE] 57 00:02:21,530 --> 00:02:22,320 >> Dobrá. 58 00:02:22,320 --> 00:02:25,254 Tak aká bola vaša stratégia pre nájsť číslo 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Hm, myslela som, že ak - 60 00:02:27,222 --> 00:02:27,714 [Nepočuteľný] 61 00:02:27,714 --> 00:02:28,206 >> David J. Malan: Oh. 62 00:02:28,206 --> 00:02:29,630 Dajte mu jednu sekundu. 63 00:02:29,630 --> 00:02:32,420 Tak bola vaša stratégia pre nájsť číslo 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Tak som sa začať na začína vidieť, čo prvé číslo 65 00:02:34,760 --> 00:02:38,590 bol, a potom som si myslel, možno, ak oni sú radené, budem len držať 66 00:02:38,590 --> 00:02:39,970 kliknutím výš? 67 00:02:39,970 --> 00:02:40,140 >> David J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 A zdá sa, že našli že tomu tak je. 69 00:02:42,910 --> 00:02:45,670 Aj keď, poďme Zlúpnite vrstvy len trochu, a vy chcete ísť 70 00:02:45,670 --> 00:02:47,640 dopredu a odhaliť ďalšie dvere si mohol vybrať? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Ach jo. 73 00:02:51,712 --> 00:02:53,128 >> David J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Tak som mal šťastie. 75 00:02:54,280 --> 00:02:55,270 >> David J. Malan: Takže máš šťastie. 76 00:02:55,270 --> 00:02:55,710 Dobrá. 77 00:02:55,710 --> 00:02:56,795 Takže to nie je zlé. 78 00:02:56,795 --> 00:02:58,750 Ale to je zaujímavé, pohľad, nie? 79 00:02:58,750 --> 00:03:01,870 Ak máte predpokladať, a vy ste sa, naozaj, trochu šťastia tam. 80 00:03:01,870 --> 00:03:05,350 Ale ak sa predpokladá, že tieto čísla triedené, môžete byť presnejší 81 00:03:05,350 --> 00:03:08,750 ako ktorý ovplyvnil vaše správanie? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Takže ak by boli zoradené, som si myslel, že najmenšie k najväčšej. 83 00:03:11,715 --> 00:03:11,970 >> David J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Alebo, ak to skončilo ako bytia naozaj veľké, potom najväčšieho k najmenšiemu. 85 00:03:15,260 --> 00:03:15,540 >> David J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Takže najväčšieho k najmenšiemu, alebo najmenšie k najväčšej. 87 00:03:18,170 --> 00:03:21,990 Ale dovoľte mi navrhnúť, že by ste mali dostali nešťastný, a predpokladáme, že 88 00:03:21,990 --> 00:03:26,840 nebola v skutočnosti, triedenie, koľko tie dvere by ste mali nahliadnuť 89 00:03:26,840 --> 00:03:28,590 pozadu v tomto najhoršom prípade? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Všetky z nich. 91 00:03:29,860 --> 00:03:30,420 >> David J. Malan: Všetky z nich. 92 00:03:30,420 --> 00:03:31,740 Takže poďme sa zovšeobecniť, že pre n 93 00:03:31,740 --> 00:03:34,790 Tam sa stane byť 7, ale poďme sa viac sa všeobecne povedať, že je to n dvere na 94 00:03:34,790 --> 00:03:35,650 screen tu. 95 00:03:35,650 --> 00:03:40,110 Takže v najhoršom prípade, mali by ste nahliadnuť za dvere, 7 alebo N dverí. 96 00:03:40,110 --> 00:03:44,140 A tak to je naozaj, je to trochu šťastie dnes, ale je to naozaj lineárna 97 00:03:44,140 --> 00:03:46,440 algoritmus druhov, aj keď ste milý preskočenie okolo. 98 00:03:46,440 --> 00:03:47,080 Je to fér? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Jo. 100 00:03:47,500 --> 00:03:50,000 >> David J. Malan: No, dovoľte mi, či váš stratégie zmeny, keď nás posunú 101 00:03:50,000 --> 00:03:52,190 náš druhý príklad tu 7 rôznych dvere. 102 00:03:52,190 --> 00:03:55,240 Rovnaké čísla, ale čas sú radené. 103 00:03:55,240 --> 00:03:58,350 Aká je vaša stratégia tu bude, snaží dať zo svojej mysle, čo 104 00:03:58,350 --> 00:03:59,310 iné čísla bola - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> David J. Malan: - skôr? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Začnime s prvým. 108 00:04:03,180 --> 00:04:03,540 >> David J. Malan: Dobre. 109 00:04:03,540 --> 00:04:05,190 Začnite s prvou. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Teraz, kam ísť, a prečo? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 je naozaj malá. 113 00:04:10,040 --> 00:04:12,500 Takže keď tak trochu možno najmenšie po najväčšie, mala by byť 114 00:04:12,500 --> 00:04:13,290 sa dvakrát, a -. 115 00:04:13,290 --> 00:04:13,670 >> David J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Poďme sa pozrieť, ktoré si myslíte? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Skúste ten posledný. 118 00:04:19,050 --> 00:04:19,500 Pekný. 119 00:04:19,500 --> 00:04:20,880 >> David J. Malan: Veľmi pekne urobil. 120 00:04:20,880 --> 00:04:21,860 Dobrá. 121 00:04:21,860 --> 00:04:23,010 >> [APPLAUSE] 122 00:04:23,010 --> 00:04:24,310 >> David J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Takže ste vlastne robíš hrozne, pretože si 124 00:04:26,790 --> 00:04:27,700 robí to veľmi dobre. 125 00:04:27,700 --> 00:04:31,150 Čo nám dáva schopný vykonať určité body. 126 00:04:31,150 --> 00:04:32,565 Skúsme sa vrátiť späť. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> David J. Malan: Veľmi dobre práce, však. 129 00:04:35,980 --> 00:04:39,060 Takže ste začal na začiatku, si videl, že to bolo 4, potom 130 00:04:39,060 --> 00:04:40,240 presunutý na koniec. 131 00:04:40,240 --> 00:04:42,320 Ale predpokladajme, že ste nemali šťastie tam, a predpokladajme, 50 132 00:04:42,320 --> 00:04:42,890 niekde inde. 133 00:04:42,890 --> 00:04:46,190 Čo si Tretím krokom bolo? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Vráťte sa späť na začiatok. 135 00:04:47,680 --> 00:04:48,320 >> David J. Malan: Vykonať späť na začiatok. 136 00:04:48,320 --> 00:04:51,320 OK, takže by ste sa na to dotkol tieto dvere, čo bolo 8.. 137 00:04:51,320 --> 00:04:51,660 Dobrá. 138 00:04:51,660 --> 00:04:52,650 Takže to nie je 50. 139 00:04:52,650 --> 00:04:55,380 Kam by ste sa pozrel ďalej? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Ak som to neurobil vedia, že radené. 141 00:04:56,720 --> 00:04:57,005 >> David J. Malan: Správne. 142 00:04:57,005 --> 00:04:58,490 No, ak ste vedieť boli zaradené - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Jo, to viem, jo. 144 00:04:58,700 --> 00:05:00,910 >> David J. Malan - ale nie vedieť, kde 50 bol ešte? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Len pokračuj. 146 00:05:01,785 --> 00:05:02,130 >> David J. Malan: Dobre. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Len tak ďalej. 149 00:05:03,800 --> 00:05:05,270 OK, že môžem pracovať. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> David J. Malan: Teraz, keď ste len bude ďalej, aký je váš 152 00:05:07,210 --> 00:05:09,680 Algoritmus pripadajúca cúval do. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Lineárne -. 154 00:05:10,740 --> 00:05:11,820 >> David J. Malan: Je to tak trochu lineárny. 155 00:05:11,820 --> 00:05:13,480 Ale dovoľte mi navrhnúť, nech mi, aby som dal na mieste. 156 00:05:13,480 --> 00:05:14,900 Dovoľte mi, aby som aktualizujte stránku. 157 00:05:14,900 --> 00:05:17,120 rovnaké číslo, rovnaké usporiadanie, Rovnaké dvere. 158 00:05:17,120 --> 00:05:21,350 Ale si spomeniem na ten prvý deň v triedy, keď vytrhol telefónny zoznam vo 159 00:05:21,350 --> 00:05:25,480 polovice, tak nejako, a to, čo bolo naša stratégia tam? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Začnite u stredu. 161 00:05:26,450 --> 00:05:26,690 >> David J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Takže začať v polovici. 163 00:05:27,610 --> 00:05:28,790 Tak poďme ďalej a simulovať to. 164 00:05:28,790 --> 00:05:30,720 Začnite v stredu ukázať, že dvere. 165 00:05:30,720 --> 00:05:31,660 Takže číslo 16. 166 00:05:31,660 --> 00:05:35,290 Takže to, čo by urobil silný chlap, ktorý trhal telefónny zoznam na polovicu, 167 00:05:35,290 --> 00:05:38,450 sa dostanete do ďalšej hádať? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Choď v tejto polovici. 169 00:05:39,400 --> 00:05:41,700 >> David J. Malan: A prečo na pravej strane? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Ak by boli nejako najmenšie po najväčšie, potom by mala byť 50 171 00:05:43,900 --> 00:05:44,720 na tento účel. 172 00:05:44,720 --> 00:05:44,920 >> David J. Malan: Dobrý. 173 00:05:44,920 --> 00:05:45,390 Úplne rozumné. 174 00:05:45,390 --> 00:05:48,380 Tak ako telefónny zoznam, môžete ísť do právo na rozdiel od ľavej strane, ale tu 175 00:05:48,380 --> 00:05:49,500 je kľúčom stánok s jedlom. 176 00:05:49,500 --> 00:05:53,930 Teraz môžete vyhodiť, alebo odtrhnúť, polovica tohto problému, takže vám nebude 177 00:05:53,930 --> 00:05:55,970 s 7 dverí, ale v skutočnosti sa len tri. 178 00:05:55,970 --> 00:05:57,870 Čo je zhruba polovica Veľkosť problému. 179 00:05:57,870 --> 00:05:58,350 Dobrá. 180 00:05:58,350 --> 00:06:01,890 Takže teraz, čo by ste si vykonané po prechode nie? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Takže 16 je ešte celkom malý, vzhľadom k 50, takže možno sa budem snažiť, 182 00:06:05,870 --> 00:06:06,700 podobne, je tento. 183 00:06:06,700 --> 00:06:07,890 >> David J. Malan: Dobre. 184 00:06:07,890 --> 00:06:08,720 42.. 185 00:06:08,720 --> 00:06:10,830 Dobre, tak teraz to, čo je vaša inštinkt ti? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Môžem vyhodiť to a potom už len - 187 00:06:12,100 --> 00:06:12,360 >> David J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Dobrá, môžete zahodiť ľavá polovica tam. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - vyberte jeden. 190 00:06:14,890 --> 00:06:15,530 >> David J. Malan: A pravdu. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Jo. 192 00:06:15,760 --> 00:06:17,820 >> David J. Malan: Takže aj keď je to ťažké vidieť snáď, keď je tu len 193 00:06:17,820 --> 00:06:21,320 7 dverí, premýšľať o tom, teraz, konzistencia 194 00:06:21,320 --> 00:06:22,620 Algoritmus stačí aplikovať. 195 00:06:22,620 --> 00:06:24,510 V predchádzajúcom prípade, ste šťastie, čo bolo skvelé. 196 00:06:24,510 --> 00:06:26,540 Ale ste použiť heuristiku, Povedal by som, že. 197 00:06:26,540 --> 00:06:29,150 Môžete použiť triedenie vašich inštinktov, a vedel, že radené, či je to dosť 198 00:06:29,150 --> 00:06:31,600 malá na začiatku, samozrejme, máme ísť viac doprava. 199 00:06:31,600 --> 00:06:34,990 Ale v istom zmysle, máš šťastie, pretože možno to bolo číslo 100, 200 00:06:34,990 --> 00:06:36,220 a možno aj 50 bol viac v strede. 201 00:06:36,220 --> 00:06:37,910 Možno, že 50 je ešte tu. 202 00:06:37,910 --> 00:06:40,960 >> Ale to, čo si urobil trochu inak Tentoraz bol si urobil to isté 203 00:06:40,960 --> 00:06:42,150 znova a znova. 204 00:06:42,150 --> 00:06:45,310 A ja by som tvrdiť, že to, čo ste práve to, aj keď vplyv na telefóne 205 00:06:45,310 --> 00:06:48,100 Kniha príklad, je niečo oveľa viac algoritmické a oveľa 206 00:06:48,100 --> 00:06:49,930 menej špeciálny puzdrom. 207 00:06:49,930 --> 00:06:51,620 Oveľa menej inštinktívny. 208 00:06:51,620 --> 00:06:57,160 Takže na konci dňa, ako by môžete popísať účinnosť 209 00:06:57,160 --> 00:07:00,530 Prvý algoritmus, kde sa stala zľava doprava, v porovnaní 210 00:07:00,530 --> 00:07:03,430 Druhý algoritmus tu? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: toto by mal, rovnako ako, možno polovicu času, alebo dokonca viac, jo. 212 00:07:06,460 --> 00:07:07,320 >> David J. Malan: OK, možno ešte viac. 213 00:07:07,320 --> 00:07:10,150 Poďme sa tlačiť trochu viac na to. 214 00:07:10,150 --> 00:07:13,030 Čo sa naozaj, ak budeme pokračovať v tejto logika, rozhodne polovicu 215 00:07:13,030 --> 00:07:15,830 doba chodu tohto druhého algoritmu by zahodili polovicu 216 00:07:15,830 --> 00:07:18,470 čísla, ale čo budeme robiť na budúci iterácie, keď Jennifer odhalil 217 00:07:18,470 --> 00:07:20,615 druhé číslo? 218 00:07:20,615 --> 00:07:22,830 >> Sme na polovicu počtu dverí znova. 219 00:07:22,830 --> 00:07:25,270 A potom to, čo sme urobili po tom, ak je tam bolo viac vráta na hranie? 220 00:07:25,270 --> 00:07:27,520 Radi by sme znížiť ich, a znova, a znova a znova. 221 00:07:27,520 --> 00:07:30,420 A to bolo len ako vy všetci vstávanie v prvom týždni 222 00:07:30,420 --> 00:07:33,000 triedy, polovica z vás sedieť, polovica z vás sedieť, polovica z vás 223 00:07:33,000 --> 00:07:35,440 sedieť, kým jeden osamelý duša stála. 224 00:07:35,440 --> 00:07:39,050 A my sme povedali, že doba chodu , Že počet krokov Stačilo 225 00:07:39,050 --> 00:07:40,430 na poradí, čo? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [nepočuteľné] 227 00:07:41,230 --> 00:07:43,970 >> David J. Malan: Takže log základňa 2 n, alebo len jednoduchšie, prihláste n 228 00:07:43,970 --> 00:07:45,060 Takže niečo logaritmické. 229 00:07:45,060 --> 00:07:48,380 A graf nebol priamka že práve dostal horšie a horšie, to bolo 230 00:07:48,380 --> 00:07:52,490 tento zaujímavý krivka, ktorá nie tak zle v priebehu času. 231 00:07:52,490 --> 00:07:53,910 Takže poďme sa držať na tejto myšlienke. 232 00:07:53,910 --> 00:07:54,690 Poďakujme Jennifer. 233 00:07:54,690 --> 00:07:56,150 Díky moc za účasť nahor. 234 00:07:56,150 --> 00:07:57,400 A jeden s 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Žiadne stolové lampy dnes, ale predsa majú CS50 stres gule. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> David J. Malan: Tak jo, tu. 239 00:08:04,410 --> 00:08:06,545 Ďakujem za vynaložení stres tu. 240 00:08:06,545 --> 00:08:07,350 Dobrá. 241 00:08:07,350 --> 00:08:10,620 Tak uvidíme, keď nie teraz formalizovať to trochu viac. 242 00:08:10,620 --> 00:08:14,820 Takže znova, čo sme práve urobili, bolo v podstate to isté ako my 243 00:08:14,820 --> 00:08:16,660 v tomto prvom týždni. 244 00:08:16,660 --> 00:08:23,780 Ale skôr než nakoniec len s lineárnou algoritmus, ktoré je znázornené 245 00:08:23,780 --> 00:08:27,210 predtým ako tento priamke, kedy, keď dáme ešte jednu dvere 246 00:08:27,210 --> 00:08:29,610 obrazovka, potom by Jennifer musel sa pozerať, potenciálne 247 00:08:29,610 --> 00:08:30,600 za jeden ďalšie dvere. 248 00:08:30,600 --> 00:08:33,490 Ak dáme dve dvere, mohla by mať aby sa za ďalšie dve dvere. 249 00:08:33,490 --> 00:08:35,990 >> A tak, že sa tento lineárny vzťah medzi veľkosťou 250 00:08:35,990 --> 00:08:39,059 problém na, povedzme, x-osi a množstvo času, ktoré trvá 251 00:08:39,059 --> 00:08:40,440 riešenie na y. 252 00:08:40,440 --> 00:08:43,330 Ale obraz bol som narážal na predtým bola táto zelená linka. 253 00:08:43,330 --> 00:08:45,970 Zelená zámerne, pretože to jednoducho cítil lepšie. 254 00:08:45,970 --> 00:08:49,790 Teoreticky algoritmus, keď sme to urobili s telefónneho zoznamu, keď sme to urobili 255 00:08:49,790 --> 00:08:52,420 s vami počítať seba, a V druhom prípade, kedy práve Jennifer 256 00:08:52,420 --> 00:08:55,250 urobil to tu, to bolo niečo o zásadne lepšie. 257 00:08:55,250 --> 00:08:57,180 Vzhľadom k tomu, že to nie je len dvakrát tak rýchlo. 258 00:08:57,180 --> 00:08:58,870 Nebolo to ani štyrikrát rýchlo. 259 00:08:58,870 --> 00:09:03,290 To bolo úplne závislé na tom, čo veľkosť vstupu bolo, pokiaľ ide o to, koľko 260 00:09:03,290 --> 00:09:05,220 kroky, ktoré nakoniec trvalo. 261 00:09:05,220 --> 00:09:08,040 >> A tak to jednoduchá myšlienka, že sme všetci vzali za samozrejmosť, sa v telefónnom zozname, 262 00:09:08,040 --> 00:09:10,200 dokument môže byť tiež použitá niečo ako toto. 263 00:09:10,200 --> 00:09:12,380 A to by mohlo byť viac uvoľnene známy ako, ako by ste si mohli 264 00:09:12,380 --> 00:09:13,940 predstaviť, rozdeľ a panuj. 265 00:09:13,940 --> 00:09:16,390 Nie na rozdiel od toho, čo sme urobili, samozrejme, s telefónneho zoznamu. 266 00:09:16,390 --> 00:09:18,300 >> Ale pseudokódu, odvolanie, to bolo. 267 00:09:18,300 --> 00:09:21,800 Tak sme sa to urobiť znovu, ale spomínam že prvý týždeň, všetci z nás vstal 268 00:09:21,800 --> 00:09:25,140 a polovica z vás sa posadil, polovica si sadol, polovica z vás sa posadil. 269 00:09:25,140 --> 00:09:29,280 Že algoritmus bol implementovaný v trochu podvádzanie spôsobom, že to 270 00:09:29,280 --> 00:09:32,870 Nebolo to len jeden z mnou počítať, Podstatnejšie je, že efektívnejšie. 271 00:09:32,870 --> 00:09:35,830 V tomto prípade som sa využitia sekundárny zdroj. 272 00:09:35,830 --> 00:09:39,470 Niečo, viac procesory, viac mozog, viac chytrých ľudí vo 273 00:09:39,470 --> 00:09:42,740 izba bola mi pomohol dostať sa z niečoho lineárne niečo 274 00:09:42,740 --> 00:09:45,190 logaritmické, z niečoho červenej na niečo zelené. 275 00:09:45,190 --> 00:09:48,650 >> Ale v tomto prípade, môže Jennifer sama zásadne zlepšiť na 276 00:09:48,650 --> 00:09:52,370 výkon jej prvý algoritmus, Znovu som premýšľal o niečo ťažšie. 277 00:09:52,370 --> 00:09:56,650 A teraz, keď príde čas na vykonanie tieto veci, prísť na to, 278 00:09:56,650 --> 00:10:00,670 aké riadky kódu môžete písať ako že môžete opakovať znovu a 279 00:10:00,670 --> 00:10:03,350 znovu a znovu, tak nejako v cyklické móde. 280 00:10:03,350 --> 00:10:06,370 Pretože nebudete mať luxusné, rovnako ako Jennifer to na prvý pohľad, na 281 00:10:06,370 --> 00:10:10,460 len veľa IFS a hovoria, hmm, je to prvé číslo 4, 282 00:10:10,460 --> 00:10:11,800 dovoľte mi, aby som skok celú cestu až do konca. 283 00:10:11,800 --> 00:10:14,180 Ooh, ak toto číslo je príliš veľká, dovoľte mi, aby som pohybovať ľubovoľne späť 284 00:10:14,180 --> 00:10:15,220 na druhý prvok. 285 00:10:15,220 --> 00:10:18,210 Zistíte, že to bude veľa ťažšie formalizovať, čo my ľudia 286 00:10:18,210 --> 00:10:21,270 brať za samozrejmosť, za veľmi rozumné heuristiky, ale počítač je len 287 00:10:21,270 --> 00:10:23,260 robiť to, čo poviete to urobiť. 288 00:10:23,260 --> 00:10:25,280 >> Teraz to má veľmi zaujímavé dôsledky. 289 00:10:25,280 --> 00:10:29,950 Tento graf je druh chcel nejako premôcť vizuálne, ale uvedomte si, kde 290 00:10:29,950 --> 00:10:32,230 je priamka v tomto grafe? 291 00:10:32,230 --> 00:10:35,330 Kde je lineárny graf ktoré nazývame n? 292 00:10:35,330 --> 00:10:37,580 No, je to trochu smerom k spodnej časti obrázku, nie? 293 00:10:37,580 --> 00:10:40,500 Takže všetko, čo sme urobili je, že sme si trochu oddialenie na osi x a 294 00:10:40,500 --> 00:10:44,780 os y pokúsiť sa získať zmysel toho, čo iné typy kriviek vyzerať. 295 00:10:44,780 --> 00:10:47,760 >> A špecifiká matematické výrazy dnes nebude záležať, aby 296 00:10:47,760 --> 00:10:52,440 moc, ale zistíte, že je tu veľa algoritmy, ktoré sú oveľa horšie, než 297 00:10:52,440 --> 00:10:53,470 niečo, čo je lineárna. 298 00:10:53,470 --> 00:10:55,410 Naozaj, n kocky vyzerá dosť zle. 299 00:10:55,410 --> 00:10:58,400 2 na n vyzerá dosť zle. n na druhú vyzerá dosť zle. 300 00:10:58,400 --> 00:11:01,630 A uvidíme, čo niektorí z tých, môže byť v skutočnosti dnes. 301 00:11:01,630 --> 00:11:05,430 A log n necíti tak zlé, ale lepšie ako n je základ log 2 n 302 00:11:05,430 --> 00:11:08,080 Ale viete, to by bolo ešte viac ohromujúci, pokiaľ Jennifer, alebo ak my, 303 00:11:08,080 --> 00:11:12,910 že prvý týždeň, prišiel s niečo, čo je log log n 304 00:11:12,910 --> 00:11:15,880 >> Takže inými slovami, je to celá Rozsah možných riešení 305 00:11:15,880 --> 00:11:18,570 problémy, ale aj tu si všimnite, čo sa bude diať. 306 00:11:18,570 --> 00:11:22,910 Keď som sa vzdialite, ktoré z týchto kriviek bude ukázať, že je absolútna 307 00:11:22,910 --> 00:11:26,630 Najhoršie z tých, na obrazovke teraz? 308 00:11:26,630 --> 00:11:28,680 Tak n kocky vyzerá celkom zle v túto chvíľu. 309 00:11:28,680 --> 00:11:32,470 Ale ak sa oddialiť a vidieť viac x a osi y, kto bude 310 00:11:32,470 --> 00:11:34,550 dominujú nakoniec? 311 00:11:34,550 --> 00:11:37,120 Takže to vlastne Ukazuje sa, že 2 až n, a môžete to vyriešiť len tým, 312 00:11:37,120 --> 00:11:39,990 zapojením niektorých čoraz väčšie čísla, a uvidíte, že 2 až 313 00:11:39,990 --> 00:11:42,070 n, v skutočnosti, sa zväčšuje oveľa rýchlejšie. 314 00:11:42,070 --> 00:11:45,530 Ak naozaj vzdialite, pre 2 až n algoritmus absolútne nič. 315 00:11:45,530 --> 00:11:48,170 Myslím, že to bude trvať celkom dosť času na 316 00:11:48,170 --> 00:11:49,460 počítač k chrliť cez. 317 00:11:49,460 --> 00:11:52,500 >> Ale uvidíte v priebehu času, a to najmä s budúcimi základné problémové okruhy a dokonca 318 00:11:52,500 --> 00:11:55,600 záverečných prác, je vaše dáta súbor dostane veľký, dobre? 319 00:11:55,600 --> 00:11:58,300 Aj v prvej verzii Facebooku, ako počet priateľov, a 320 00:11:58,300 --> 00:12:01,840 Počet registrovaných užívateľov má veľký, môžete nejako telefónu ho a 321 00:12:01,840 --> 00:12:05,530 implementovať niečo s lineárnym vyhľadávania alebo veľmi jednoduché triedenie 322 00:12:05,530 --> 00:12:07,030 algoritmus, ako uvidíme dnes. 323 00:12:07,030 --> 00:12:09,280 Musíte začať premýšľať ťažšie a ťažšie o týchto problémoch. 324 00:12:09,280 --> 00:12:12,070 A druhy problémov miestach, ako je Facebook a Google a Microsoft, 325 00:12:12,070 --> 00:12:16,350 a iní pracujú na presne tie druh veľkého dátového druhu otázok 326 00:12:16,350 --> 00:12:18,530 čoraz častejšie v týchto dňoch. 327 00:12:18,530 --> 00:12:18,900 >> Dobrá. 328 00:12:18,900 --> 00:12:23,800 Takže úspech Jennifer v tom druhom algoritmus, úprimne povedané, ona prekvapivo 329 00:12:23,800 --> 00:12:26,110 tiež prvýkrát, ale poďme napísať, že ako šťastie tak, že sme 330 00:12:26,110 --> 00:12:27,000 môže tento bod. 331 00:12:27,000 --> 00:12:30,970 V druhom prípade sa zadlžujú algoritmus, ktorý znovu a 332 00:12:30,970 --> 00:12:34,670 znova, ale vzala za samozrejmosť istý predpoklad, že smieme 333 00:12:34,670 --> 00:12:39,370 nej, ale ona využívané niektoré detaily Druhýkrát, že nemala 334 00:12:39,370 --> 00:12:39,840 prvýkrát. 335 00:12:39,840 --> 00:12:41,800 Čo je to, čo? 336 00:12:41,800 --> 00:12:43,050 >> To, že bol zoznam zoradený. 337 00:12:43,050 --> 00:12:46,350 Aby, akonáhle bol priradený zoznam, sme tvrdí, že Jennifer bol schopný urobiť 338 00:12:46,350 --> 00:12:47,480 zásadne lepší. 339 00:12:47,480 --> 00:12:51,450 7 dverí, áno, nie je to zaujímavé, Predpokladajme však, že to, že sme 7000000 dvere. 340 00:12:51,450 --> 00:12:54,080 Prihlásiť n je určite vykonávať oveľa 341 00:12:54,080 --> 00:12:55,610 rýchlejšie v dlhodobom horizonte. 342 00:12:55,610 --> 00:12:58,880 Ale musela mať Dvere radené pre ňu. 343 00:12:58,880 --> 00:13:02,320 Teraz som si dovolil robiť, že vopred na obrazovke počítača 344 00:13:02,320 --> 00:13:05,160 tu, ale predpokladám, že Jennifer Musel to urobiť sama? 345 00:13:05,160 --> 00:13:10,120 Predpokladajme, že dvere v otázke zastúpené dáta v databáze, alebo 346 00:13:10,120 --> 00:13:14,260 priatelia registrovaní na Facebook, alebo všetky webové stránky na internete, ktoré 347 00:13:14,260 --> 00:13:16,880 rôzne webové stránky, môže byť potrebné k indexu alebo prehľadávať. 348 00:13:16,880 --> 00:13:20,940 >> Predpokladajme, že ste práve mal surové dáta nastavenie a bolo ponechané na vás, alebo 349 00:13:20,940 --> 00:13:23,010 Jennifer k tomu, že triedenie? 350 00:13:23,010 --> 00:13:26,950 To skôr si vyžaduje, aby sme odpoveď otázka, no, koľko času 351 00:13:26,950 --> 00:13:31,080 by trvalo Jennifer, alebo dokonca ma, triediť tie čísla vopred, aby 352 00:13:31,080 --> 00:13:32,680 že by mohla využiť, že? 353 00:13:32,680 --> 00:13:32,880 Je to tak? 354 00:13:32,880 --> 00:13:36,620 Vzhľadom k tomu, dôsledky, samozrejme, je ak mi trvá dosť dlho, než triedenie 355 00:13:36,620 --> 00:13:40,800 čísla, ktoré to zaujíma, že ťa sakra môžete nájsť číslo ako 50 tak rýchlo, 356 00:13:40,800 --> 00:13:44,850 rovnako ako v prípade, Jennifer, pokiaľ sa viac než ohromený množstvo celkového času 357 00:13:44,850 --> 00:13:46,920 trvalo triedenie veci vopred? 358 00:13:46,920 --> 00:13:49,320 >> Tak uvidíme, či nemôžeme namaľovať obraz tu. 359 00:13:49,320 --> 00:13:51,370 Mám celá partia väčší dôraz guľa, je-li, že pomáha 360 00:13:51,370 --> 00:13:52,270 prelomiť ľady tu. 361 00:13:52,270 --> 00:13:55,690 A ak vám to nebude vadiť, my Potrebujete sedem dobrovoľníka - 362 00:13:55,690 --> 00:13:57,060 na, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Takže nemáme utrácať na stolných lampách, zdá sa. 365 00:13:59,250 --> 00:13:59,690 Dobrá. 366 00:13:59,690 --> 00:14:01,530 Tak čo tie dva vpredu. 367 00:14:01,530 --> 00:14:04,160 Ako sa o vás dvaja chlapci v chrbte. 368 00:14:04,160 --> 00:14:04,870 Tak to je štyri. 369 00:14:04,870 --> 00:14:09,890 Ako sa o vás pred päť, šesť a sedem. 370 00:14:09,890 --> 00:14:10,320 Presne tam. 371 00:14:10,320 --> 00:14:13,260 Váš priateľ sa ukázal von, tak dostanete cenu. 372 00:14:13,260 --> 00:14:13,700 >> Dobrá. 373 00:14:13,700 --> 00:14:14,410 Poď hore. 374 00:14:14,410 --> 00:14:17,120 A prečo sme si chlapci poď sem. 375 00:14:17,120 --> 00:14:18,960 Chystám sa vám každé číslo. 376 00:14:18,960 --> 00:14:22,150 A do toho pustite a zariadiť sami zhodne s tým, čo je 377 00:14:22,150 --> 00:14:25,180 zobrazený na obrazovke. 378 00:14:25,180 --> 00:14:26,530 >> [Prechodová Hlasy] 379 00:14:26,530 --> 00:14:28,160 >> David J. Malan: OOP, je mi ľúto. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Dobrá. 382 00:14:32,180 --> 00:14:32,750 Tak, ideme na to. 383 00:14:32,750 --> 00:14:34,180 Číslo päť. 384 00:14:34,180 --> 00:14:35,136 Číslo šesť. 385 00:14:35,136 --> 00:14:37,770 Jedna, dve, tri, štyri, päť, šesť, sedem. 386 00:14:37,770 --> 00:14:39,410 Oh, to je trápne. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Budem len dostať -. 388 00:14:41,210 --> 00:14:41,900 >> David J. Malan: dobrý obchod. 389 00:14:41,900 --> 00:14:43,130 Dobrá. 390 00:14:43,130 --> 00:14:44,611 Ďakujem vám za účasť. 391 00:14:44,611 --> 00:14:47,200 >> [APPLAUSE] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Dobrá. 394 00:14:48,860 --> 00:14:51,970 Takže máme štyri, dva, šesť, jeden, tri, sedem, päť. 395 00:14:51,970 --> 00:14:56,010 Perfektné takže máme sedem dobrovoľníkov , Ktorí tu sú rovnakej šírky, aby 396 00:14:56,010 --> 00:14:57,430 Pole, ktoré hráme s predtým. 397 00:14:57,430 --> 00:14:59,470 A ja som si vybral sedem dôvodov že bude len 398 00:14:59,470 --> 00:15:00,840 výhodné v trochu. 399 00:15:00,840 --> 00:15:04,400 A ja idem navrhnúť, že prvá triedime týchto sedem dobrovoľníkov. 400 00:15:04,400 --> 00:15:06,786 Ak by ste chceli, prvý, pozdraviť hoci. 401 00:15:06,786 --> 00:15:08,970 Vzhľadom k tomu bude nevhodné niekoľko minút. 402 00:15:08,970 --> 00:15:10,370 Predstavte sa. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Ahoj, ja som milosť. 404 00:15:10,980 --> 00:15:14,190 Som vo druháku na Leverett domu. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Ahoj. 406 00:15:14,620 --> 00:15:15,620 Som Branson. 407 00:15:15,620 --> 00:15:16,920 Som prvák na zvaru. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Ahoj. 410 00:15:20,230 --> 00:15:21,040 Som Gabe. 411 00:15:21,040 --> 00:15:22,300 Som junior v Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Som Neil. 414 00:15:25,980 --> 00:15:29,090 Som prvák na Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Som Jason. 416 00:15:29,550 --> 00:15:32,816 Som prvák na Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Ja som Mike. 418 00:15:33,700 --> 00:15:37,360 Som prvák na Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Som Jess. 420 00:15:37,990 --> 00:15:40,313 Som vo druháku na Leverett. 421 00:15:40,313 --> 00:15:41,300 >> David J. Malan: Výborný. 422 00:15:41,300 --> 00:15:41,850 Dobrá. 423 00:15:41,850 --> 00:15:44,190 No, ďakujem všetkým našim Dobrovoľníci tu tak ďaleko. 424 00:15:44,190 --> 00:15:47,110 A výzva na dosah ruky teraz sa deje bude triediť z týchto chlapci, ale potom 425 00:15:47,110 --> 00:15:50,250 budeme musieť trošku premýšľať ťažké o tom, ako efektívne sme vlastne 426 00:15:50,250 --> 00:15:51,110 zoradené. 427 00:15:51,110 --> 00:15:52,580 Takže poďme sa najprv skúsiť. 428 00:15:52,580 --> 00:15:55,970 Vy môžete vidieť navzájom čísla len tým, v rohoch. 429 00:15:55,970 --> 00:15:59,380 Nehanbite sa a trvať niekoľko sekúnd a radiť sami od najmenšej na 430 00:15:59,380 --> 00:16:01,240 vľavo najväčšou na pravej strane. 431 00:16:01,240 --> 00:16:02,490 Prejsť. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Dobre. 435 00:16:08,030 --> 00:16:09,370 To bolo naozaj čertovsky rýchlo. 436 00:16:09,370 --> 00:16:14,040 Teraz tu niekto, čo to bolo algoritmus že títo ľudia aplikovať? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: od najmenej po najväčšie. 438 00:16:14,900 --> 00:16:15,000 >> David J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Aspoň najväčší je naozaj nejako objektívne, ale nie som si istý, že to 440 00:16:18,070 --> 00:16:18,890 naozaj algoritmus. 441 00:16:18,890 --> 00:16:21,810 Aspoň najväčšie nehovorí ma krok-za-krokom, čo robiť. 442 00:16:21,810 --> 00:16:22,833 Jo? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [nepočuteľné] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> David J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Takže ak uvidíte osoba menšia než Vaše telefónne číslo, potom sa presuňte na 447 00:16:28,920 --> 00:16:29,680 právo z nich. 448 00:16:29,680 --> 00:16:32,800 Tak to je teraz stále viac expresívne, spíš algoritmu, pretože 449 00:16:32,800 --> 00:16:35,410 Dá sa povedať,, je-li to, potom je to. 450 00:16:35,410 --> 00:16:37,050 Takže máme nejaký podmienené konštrukcie. 451 00:16:37,050 --> 00:16:39,700 A títo chlapci zrejme k tomu, že niektoré časy, pretože niektorí z vás presťahoval trochu 452 00:16:39,700 --> 00:16:40,420 na diaľku. 453 00:16:40,420 --> 00:16:43,410 Takže tam bol pravdepodobne nejaký druh opakovanie deje v ich mysliach. 454 00:16:43,410 --> 00:16:44,610 >> Ale poďme sa snaží formalizovať, že. 455 00:16:44,610 --> 00:16:47,540 Ak ste mohli obnoviť späť na ne toto dojednanie. 456 00:16:47,540 --> 00:16:50,650 Uvidíme, či sa nemôžeme formalizovať tento bit, a potom položiť otázku, len 457 00:16:50,650 --> 00:16:51,580 ako efektívne je to? 458 00:16:51,580 --> 00:16:54,220 Samozrejme, že keď budeme robiť to pomalšie, to bude mať pocit, ako dobrý 459 00:16:54,220 --> 00:16:57,210 algoritmus, ale uvidíme, či to pôjde dať naše prsty na presných krokoch. 460 00:16:57,210 --> 00:16:58,670 >> Takže vy dvaja sú štyri a dva. 461 00:16:58,670 --> 00:17:01,020 Alebo si správne alebo nesprávne, aby? 462 00:17:01,020 --> 00:17:01,900 Je zrejmé nesprávne. 463 00:17:01,900 --> 00:17:02,710 Tak sme vymenili. 464 00:17:02,710 --> 00:17:05,170 Teraz idem oddialiť tu a hovoria štyroch až šiestich. 465 00:17:05,170 --> 00:17:06,240 Ste správne alebo nesprávne? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Správne. 467 00:17:06,599 --> 00:17:07,180 >> David J. Malan: Správne. 468 00:17:07,180 --> 00:17:08,300 Šesť a jedna? 469 00:17:08,300 --> 00:17:08,609 Nie. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Tak to je dva swapy. 472 00:17:10,490 --> 00:17:11,710 Šesť a tri? 473 00:17:11,710 --> 00:17:11,980 Nie. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Šesť a sedem? 476 00:17:13,930 --> 00:17:14,630 Vyzerá to dobre. 477 00:17:14,630 --> 00:17:15,396 Sedem a päť? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [nepočuteľné] 479 00:17:16,150 --> 00:17:17,089 >> David J. Malan: OK, vymeniť. 480 00:17:17,089 --> 00:17:19,770 A triediť. 481 00:17:19,770 --> 00:17:19,980 Dobrá. 482 00:17:19,980 --> 00:17:21,440 Takže samozrejme nie je, že jo? 483 00:17:21,440 --> 00:17:22,470 Takže tam bolo viac deje. 484 00:17:22,470 --> 00:17:24,920 Ale naozaj, títo ľudia, a to aj len inštinktívne. 485 00:17:24,920 --> 00:17:25,450 stále v pohybe. 486 00:17:25,450 --> 00:17:27,710 Nemali zastaviť, akonáhle sa opravený jeden problém. 487 00:17:27,710 --> 00:17:27,839 Tak. 488 00:17:27,839 --> 00:17:29,390 Naozaj, budem mať urobiť rovnakú vec. 489 00:17:29,390 --> 00:17:32,720 Budem musieť nejako chrbte vzad na začiatku tohto problému, 490 00:17:32,720 --> 00:17:35,630 alebo na začiatku tejto rady ľudia, začnime volať im. 491 00:17:35,630 --> 00:17:38,366 >> A teraz, čo by môj algoritmus Na druhom prechode bude? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: To je to isté. 493 00:17:39,220 --> 00:17:39,940 >> David J. Malan: To je to isté. 494 00:17:39,940 --> 00:17:41,460 A to ja začínam mať rada, nie? 495 00:17:41,460 --> 00:17:44,720 Akonáhle si môžete nájsť sami robiť to isté znova a znova, je to 496 00:17:44,720 --> 00:17:47,890 čoraz viac ako algoritmus, a menej ľudský inštinkt. 497 00:17:47,890 --> 00:17:48,680 >> Takže teraz je to tu zase. 498 00:17:48,680 --> 00:17:49,870 Dva a štyri? 499 00:17:49,870 --> 00:17:50,220 Nie. 500 00:17:50,220 --> 00:17:51,050 Štyri a jedna? 501 00:17:51,050 --> 00:17:53,380 Ah, bola naozaj niektorí práce je potrebné ešte urobiť. 502 00:17:53,380 --> 00:17:53,620 Pre a tri? 503 00:17:53,620 --> 00:17:54,572 Dobre. 504 00:17:54,572 --> 00:17:56,000 Štyri a šesť? 505 00:17:56,000 --> 00:17:58,380 Šesť a päť? 506 00:17:58,380 --> 00:17:59,470 Šesť a sedem? 507 00:17:59,470 --> 00:18:00,970 OK, teraz, hotovo. 508 00:18:00,970 --> 00:18:01,550 OK, no. 509 00:18:01,550 --> 00:18:02,710 Musím sa vrátiť. 510 00:18:02,710 --> 00:18:05,130 >> Takže teraz znova, toto robíme trochu zámerne. 511 00:18:05,130 --> 00:18:08,700 A teraz je tu len jeden mozog vykonávanie tohto algoritmu. 512 00:18:08,700 --> 00:18:10,290 Jeden CPU, ak chcete. 513 00:18:10,290 --> 00:18:13,090 A úprimne povedané, to je jediný zdroj budeme mať prístup. 514 00:18:13,090 --> 00:18:16,280 A akonáhle sme sa vrátiť ku klávesnici a niečo ako C v našom 515 00:18:16,280 --> 00:18:19,600 likvidácia, budeme len písať program ktorý môže robiť jednu vec naraz. 516 00:18:19,600 --> 00:18:22,900 Vzhľadom k tomu, títo ľudia pred chvíľou sme pákový efekt, ich kolektívne inteligenčného 517 00:18:22,900 --> 00:18:24,180 ako ste urobili v týždni nulu. 518 00:18:24,180 --> 00:18:24,980 Takže poďme v tom pokračovať. 519 00:18:24,980 --> 00:18:26,260 >> Dva a 520 00:18:26,260 --> 00:18:26,945 Dva a tri. 521 00:18:26,945 --> 00:18:27,460 Tri a štyri. 522 00:18:27,460 --> 00:18:28,310 Štyri a päť. 523 00:18:28,310 --> 00:18:28,620 Päť a šesť. 524 00:18:28,620 --> 00:18:30,510 Šesť a sedem. 525 00:18:30,510 --> 00:18:31,880 Hotovo? 526 00:18:31,880 --> 00:18:34,560 Takže som, ale dovoľte mi, aby som hrať diablovho advokáta. 527 00:18:34,560 --> 00:18:37,950 Musím sa trochu počítača, ktorý práve urobil priechod tejto rady 528 00:18:37,950 --> 00:18:40,225 ľudí, viem, že som urobil? 529 00:18:40,225 --> 00:18:40,670 >> Reproduktor 1: Nie 530 00:18:40,670 --> 00:18:41,050 >> David J. Malan: Tak prečo? 531 00:18:41,050 --> 00:18:46,900 Čo by som mal urobiť, aby sa k záveru, rozhodne, že som to urobil? 532 00:18:46,900 --> 00:18:48,230 Pravdepodobne jeden priechod. 533 00:18:48,230 --> 00:18:48,430 Je to tak? 534 00:18:48,430 --> 00:18:51,760 Pretože viem, že od predchádzajúcej priechod je, že som opravil chybu. 535 00:18:51,760 --> 00:18:53,920 A to znamená, možno je tu ešte jedna chyba 536 00:18:53,920 --> 00:18:54,840 že musím opraviť. 537 00:18:54,840 --> 00:18:58,680 Tak som sa môľete byť istí len tým, prevíjanie a potom kontrola, jeden dva, a dva 538 00:18:58,680 --> 00:19:00,940 tri, tri a štyri, štyri a päť, päť a šesť, šesť a sedem. 539 00:19:00,940 --> 00:19:02,510 OK, teraz som žiadnu prácu. 540 00:19:02,510 --> 00:19:05,990 >> Môžem si určite spomenú, že som žiadny pracovať s niečím ako premenné, 541 00:19:05,990 --> 00:19:06,975 ako int. 542 00:19:06,975 --> 00:19:12,490 Nazvime to swapy, swapy a ak je 0, keď som sem, a začala na 0, potom 543 00:19:12,490 --> 00:19:15,520 Ja by som jednoducho hlúpe ísť ďalej tam a späť, kontrola znova a 544 00:19:15,520 --> 00:19:16,450 znova a znova, že jo? 545 00:19:16,450 --> 00:19:18,450 Vzhľadom k tomu, uviaznete v niektorých druh nekonečnej slučke. 546 00:19:18,450 --> 00:19:21,250 Takže akonáhle tam je 0 swapy, môžeme konštatovať, že táto 547 00:19:21,250 --> 00:19:23,810 algoritmus je naozaj kompletný. 548 00:19:23,810 --> 00:19:25,400 >> Teraz sa poďme dať meno na túto tému. 549 00:19:25,400 --> 00:19:28,930 Algoritmus, ktorý navrhujem, aby sme len implementuje, je niečo, čo nazýva bubble 550 00:19:28,930 --> 00:19:32,800 druh, známy ako taká v tom zmysle, že čísla, ktoré sú väčšie druh 551 00:19:32,800 --> 00:19:37,990 bublina cestu až na vrchol, alebo sa na koniec rady čísel. 552 00:19:37,990 --> 00:19:40,270 Ale ako efektívne bol tento algoritmus? 553 00:19:40,270 --> 00:19:44,600 Koľko krokov som musel fyzicky Vezmite si napríklad, triediť tieto 554 00:19:44,600 --> 00:19:45,850 sedem ľudí? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Štyri až päť? 557 00:19:49,550 --> 00:19:51,420 OK, príliš veľa je v konečnom dôsledku bude odpoveď. 558 00:19:51,420 --> 00:19:54,960 Ale aj potom, konkrétne číslo nie je ani tak zaujímavé. 559 00:19:54,960 --> 00:19:56,670 Poďme zovšeobecniť ju ako n 560 00:19:56,670 --> 00:20:00,520 Takže keby som n ľudí tu, a oni boli, tak nejako, v náhodnom poradí na 561 00:20:00,520 --> 00:20:02,180 na začiatku, v tomto pôvodnom poradí. 562 00:20:02,180 --> 00:20:04,910 No, koľko krokov som mal aby sa v prvom prechode? 563 00:20:04,910 --> 00:20:09,810 To bol jeden, dva, tri, štyri, päť, šesť, a sú sedem ľudí, tak 564 00:20:09,810 --> 00:20:13,670 to je sedem, šesť -, takže je n mínus jeden pár prvýkrát. 565 00:20:13,670 --> 00:20:16,280 >> Teraz, koľko krokov som mal vziať, keď som pretočil? 566 00:20:16,280 --> 00:20:19,310 No, mohli by sme dokonca zdvojnásobiť, že ak sme naozaj chceli, ale teraz som 567 00:20:19,310 --> 00:20:22,300 Len poviem, jo, ďalšie n mínus 1. 568 00:20:22,300 --> 00:20:25,240 Tak n mínus jedna je dostane nepríjemné sledovať, takže sa poďme 569 00:20:25,240 --> 00:20:26,400 Hneď za mierne. 570 00:20:26,400 --> 00:20:27,770 Takže 2n krokov. 571 00:20:27,770 --> 00:20:29,310 Takže 14 schodov, dávať alebo brať. 572 00:20:29,310 --> 00:20:31,930 >> Koľkokrát som sa krok nabudúce? 573 00:20:31,930 --> 00:20:33,740 No, je to 3n. 574 00:20:33,740 --> 00:20:34,510 Naozaj. 575 00:20:34,510 --> 00:20:37,920 A teraz, v najhoršom prípade pre inštancie, by koľkokrát mám 576 00:20:37,920 --> 00:20:41,730 išiel tam a späť, tam a späť, vykonávanie tohto algoritmu, vymieňať 577 00:20:41,730 --> 00:20:44,620 ľudia na každom priechode, asi? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Je to vlastne n na druhú, nie? 580 00:20:50,010 --> 00:20:53,000 >> Vzhľadom k tomu, v najhoršom prípade môžete druh ze si o tom myslíte intuitívne, 581 00:20:53,000 --> 00:20:54,800 aj keď to môže trvať trochu trochu času potopiť palcov 582 00:20:54,800 --> 00:20:57,590 V najhoršom prípade, čo by títo sedem ľudí vyzeral v 583 00:20:57,590 --> 00:21:00,230 podmienky zmluvy ich čísla? 584 00:21:00,230 --> 00:21:01,460 Úplne dozadu, nie? 585 00:21:01,460 --> 00:21:02,815 A len simulovať to, ako sa voláte? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> David J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Miku, stačí pripojiť ma tu len jedna sekunda? 589 00:21:08,100 --> 00:21:08,880 V skutočnosti, no. 590 00:21:08,880 --> 00:21:10,150 Ospravedlňujeme sa Mike, poďme vzad. 591 00:21:10,150 --> 00:21:10,910 Ako sa voláte? 592 00:21:10,910 --> 00:21:11,180 >> Neil Neil. 593 00:21:11,180 --> 00:21:11,640 >> David J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, pôjdeš sa ma, či vám to nevadí. 595 00:21:13,750 --> 00:21:17,150 Takže budem navrhovať, len pre jednoduchosť, že Neil je teraz v jeho 596 00:21:17,150 --> 00:21:18,510 najhorší možný prípad. 597 00:21:18,510 --> 00:21:20,720 Ale spomínam, ako som implementoval môj algoritmus. 598 00:21:20,720 --> 00:21:24,530 Som porovnávanie, porovnávanie, porovnávanie, porovnávanie, porovnávanie, oh. 599 00:21:24,530 --> 00:21:26,640 Teraz títo ľudia sú mimo prevádzka, tak som opraviť. 600 00:21:26,640 --> 00:21:27,980 Takže vy vymeniť. 601 00:21:27,980 --> 00:21:31,630 Ale teraz zvážiť, ako moc ďalej Neil nemá ísť? 602 00:21:31,630 --> 00:21:32,690 Je to zhruba n 603 00:21:32,690 --> 00:21:33,570 Viete, nie je to v skutočnosti n 604 00:21:33,570 --> 00:21:36,040 Je to ako, n mínus jedna, ale ja som stále rozmrzelí sledovať tiež trochu 605 00:21:36,040 --> 00:21:37,550 číslo, tak nech to jednoducho hovoriť n 606 00:21:37,550 --> 00:21:42,860 >> Takže ak Neil posunie o jeden krok maximálne každý čas a prejsť Neil jeden krok, 607 00:21:42,860 --> 00:21:46,580 Musím si to naozaj nudný pas tam a späť, to je zhruba 608 00:21:46,580 --> 00:21:52,080 Tým, n krokov, celkovo n krát, , Pretože to bude pre mňa 609 00:21:52,080 --> 00:21:55,820 že mnoho opatrení, aby sa Neil všetky spôsob, ako sa tam, kam patrí. 610 00:21:55,820 --> 00:21:58,620 Nieto potom všetci ostatní, ak ste boli všetci mis-nariadil rovnako. 611 00:21:58,620 --> 00:22:01,100 >> Takže hovorme bublinkové triedenie n štvorcov. 612 00:22:01,100 --> 00:22:04,860 Doba chodu tohto algoritmu, Výkon tohto algoritmu, 613 00:22:04,860 --> 00:22:07,120 Účinnosť tohto algoritmu, budeme len popísať viac 614 00:22:07,120 --> 00:22:08,800 všeobecne ako n na druhú. 615 00:22:08,800 --> 00:22:11,650 Čo je pekné, pretože som mohol urobiť Rovnaký príklad s ôsmimi ľuďmi, deväť 616 00:22:11,650 --> 00:22:15,450 ľudí, a milióny ľudí, a že Odpoveď sa nebude meniť. 617 00:22:15,450 --> 00:22:18,870 >> Takže ak ste to nebude vadiť, poďme obnoviť vás tam, kde ste začali. 618 00:22:18,870 --> 00:22:22,510 A skúsme ďalšie dva prístupy a uvidíme, či môžeme to urobiť v zásade 619 00:22:22,510 --> 00:22:23,820 lepší než tohle. 620 00:22:23,820 --> 00:22:27,130 Takže tentoraz, budem navrhovať druh iný algoritmus. 621 00:22:27,130 --> 00:22:29,950 To bolo veľmi múdre nás minule, a vy sa právo na 622 00:22:29,950 --> 00:22:32,470 správne inštinkty tak nejako prehodenie párového. 623 00:22:32,470 --> 00:22:36,500 Ale keď som chcel tento prístup jednoducho, a mojím cieľom je presunúť 624 00:22:36,500 --> 00:22:39,800 všetky z malých čísel týmto spôsobom, a tlačiť všetky veľké čísel, ktorá 625 00:22:39,800 --> 00:22:43,030 Tak prečo som si, že v najviac naivný spôsob, ako je to možné a či by som 626 00:22:43,030 --> 00:22:45,730 môže robiť lepšie, než to, čo bolo pomerne zložitý algoritmus? 627 00:22:45,730 --> 00:22:46,620 >> Tak uvidíme. 628 00:22:46,620 --> 00:22:48,940 Štyri je celkom malé množstvo, takže som nechám ťa tam chvíľku. 629 00:22:48,940 --> 00:22:50,610 Ooh, číslo dva je ešte lepší. 630 00:22:50,610 --> 00:22:52,230 Takže stačí krok vpred na chvíľu? 631 00:22:52,230 --> 00:22:55,670 To je v súčasnej dobe som najmenší číslované kandidát, a budem si pamätať 632 00:22:55,670 --> 00:22:57,000 ktoré sa, ako, premenné. 633 00:22:57,000 --> 00:22:57,930 Ale budem držať kontrolu. 634 00:22:57,930 --> 00:22:59,890 Je tu niekto, ktorého číslo je menšie? 635 00:22:59,890 --> 00:23:00,460 Šesť, no. 636 00:23:00,460 --> 00:23:01,390 Oh, to je Neil znova. 637 00:23:01,390 --> 00:23:04,050 >> Takže budem tlačiť staré nejako koncepčne. 638 00:23:04,050 --> 00:23:05,120 Neil príde dopredu. 639 00:23:05,120 --> 00:23:08,440 A teraz, premennú, ktorá som pomocou sa sledovať, kto má najmenší 640 00:23:08,440 --> 00:23:11,390 číslo je aktualizovaný, aby obsahoval Neil umiestnenia. 641 00:23:11,390 --> 00:23:12,110 No, uvidíme. 642 00:23:12,110 --> 00:23:13,960 Tri, sedem, päť. 643 00:23:13,960 --> 00:23:15,590 OK, ja viem, Neil bol najmenší. 644 00:23:15,590 --> 00:23:18,110 Čo je to tá najjednoduchšia vec Pre mňa robiť teraz? 645 00:23:18,110 --> 00:23:21,410 Nebudem strácať čas tým, že len bublajúce Neil jedno miesto doľava. 646 00:23:21,410 --> 00:23:25,350 Prečo som dal Neila, kde patrí, čo je samozrejme kde? 647 00:23:25,350 --> 00:23:26,160 >> Úplne na začiatku. 648 00:23:26,160 --> 00:23:27,720 Takže Neil, poď so mnou. 649 00:23:27,720 --> 00:23:28,910 A čo sa vlastne voláš? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Milosť. 651 00:23:29,310 --> 00:23:29,710 >> David J. Malan: Milosť. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Takže Milosť, bohužiaľ, ty si druh v ceste. 654 00:23:32,490 --> 00:23:34,290 Tak ako sme sa tento problém vyriešiť? 655 00:23:34,290 --> 00:23:34,490 Je to tak? 656 00:23:34,490 --> 00:23:37,500 Pokiaľ sa jedná o pole, je tu iba sedem miest. 657 00:23:37,500 --> 00:23:40,830 Pripomeňme, že s Robom, hovorili sme o deklarovať veky, a my sme mali len 658 00:23:40,830 --> 00:23:41,740 konečný počet vekov? 659 00:23:41,740 --> 00:23:42,535 Rovnaká myšlienka tu. 660 00:23:42,535 --> 00:23:44,300 Máme len konečný počet ints. 661 00:23:44,300 --> 00:23:47,590 Grace je druh v našom spôsobom, tak ako to napraviť? 662 00:23:47,590 --> 00:23:49,555 >> Najjednoduchší spôsob, ako je rád, Milosť, je mi ľúto. 663 00:23:49,555 --> 00:23:51,870 Budeš musieť ísť cez tam, takže môžeme vytvoriť priestor. 664 00:23:51,870 --> 00:23:55,290 Teraz, keď si o tom myslíte, možná Práve sme problém ešte horšie. 665 00:23:55,290 --> 00:23:58,510 A možno sme urobili, pretože čo keby Milosť boli na správnom mieste? 666 00:23:58,510 --> 00:24:01,730 Ale my vieme, že to tak nie je, pretože inak, bola by 667 00:24:01,730 --> 00:24:03,980 stojaci dopredu miesto Neil v tejto dobe, že jo? 668 00:24:03,980 --> 00:24:05,550 Už sme sa pozrela na číslo von. 669 00:24:05,550 --> 00:24:05,770 >> Dobrá. 670 00:24:05,770 --> 00:24:09,110 Takže teraz, Neil je na správnom mieste, a Môžem robiť mierne optimalizáciu. 671 00:24:09,110 --> 00:24:11,740 Pre budúci minútu, budem ignorovať Neil dohromady, tak, aby sa 672 00:24:11,740 --> 00:24:15,280 strácať čas, alebo náhodne vymeniť ho na zlom mieste. 673 00:24:15,280 --> 00:24:17,805 Takže teraz, ako mám nájsť ďalšie prvok, ktorý je najmenší? 674 00:24:17,805 --> 00:24:18,480 Dva. 675 00:24:18,480 --> 00:24:20,225 To je celkom dobré číslo, ak je Chcete urobiť krok vpred a 676 00:24:20,225 --> 00:24:21,100 Budem si ťa. 677 00:24:21,100 --> 00:24:21,980 Šesť, nie je dobré. 678 00:24:21,980 --> 00:24:24,820 Štyri, tri, sedem, päť, nie je dobré. 679 00:24:24,820 --> 00:24:26,800 Takže dovoľte mi, aby som vám pohybovať sa vaše pravé miesto. 680 00:24:26,800 --> 00:24:28,470 A my sme mali šťastie tentoraz. 681 00:24:28,470 --> 00:24:31,350 >> Teraz budem ignorovať dvaja chlapci, a teraz ešte jednu 682 00:24:31,350 --> 00:24:32,260 prejsť to. 683 00:24:32,260 --> 00:24:33,490 Šesť, že dosť malé číslo. 684 00:24:33,490 --> 00:24:34,300 Poď dopredu. 685 00:24:34,300 --> 00:24:35,220 Oh, ospravedlňujem sa. 686 00:24:35,220 --> 00:24:37,640 Grace číslo je lepšie, tak šliapnuť dopredu. 687 00:24:37,640 --> 00:24:38,260 Štyri. 688 00:24:38,260 --> 00:24:39,120 Je nám ľúto, Grace. 689 00:24:39,120 --> 00:24:39,950 Vráťte sa znova. 690 00:24:39,950 --> 00:24:41,550 Číslo tri je lepší. 691 00:24:41,550 --> 00:24:42,290 Sedem. 692 00:24:42,290 --> 00:24:42,720 Päť. 693 00:24:42,720 --> 00:24:43,550 A teraz, čo sa to voláte? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> David J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Takže Jason je teraz najmenší prvok som vybraná. 697 00:24:47,050 --> 00:24:49,160 Ak má ísť? 698 00:24:49,160 --> 00:24:50,380 Takže tam, kde je šesť. 699 00:24:50,380 --> 00:24:51,210 A vaše meno je znova? 700 00:24:51,210 --> 00:24:51,710 >> Gabe: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> David J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe je v ceste. 703 00:24:53,220 --> 00:24:54,640 Čo je to tá najjednoduchšia vec robiť? 704 00:24:54,640 --> 00:24:58,390 Vymeňte tieto dva chlapov a pokračovať. 705 00:24:58,390 --> 00:24:59,020 Takže teraz uvidíme. 706 00:24:59,020 --> 00:25:00,170 Kto je najmenší? 707 00:25:00,170 --> 00:25:01,030 Štyri. 708 00:25:01,030 --> 00:25:01,990 Dovoľte mi trochu podvádzať. 709 00:25:01,990 --> 00:25:03,090 Päť bude najmenší. 710 00:25:03,090 --> 00:25:05,220 Zistil som ďalšie, ak chcete krok dopredu, čo mám robiť s 711 00:25:05,220 --> 00:25:06,820 títo ľudia, s Gabe? 712 00:25:06,820 --> 00:25:08,450 Swap znova. 713 00:25:08,450 --> 00:25:10,740 Takže teraz, stále mierne mimo prevádzku. 714 00:25:10,740 --> 00:25:14,140 Zistil som, Gabe ako najmenší, a preto Aj pop mu von, pohybovať sa chlapci znova. 715 00:25:14,140 --> 00:25:15,190 A hotovo. 716 00:25:15,190 --> 00:25:17,200 >> Takže odpoveď je rovnaká. 717 00:25:17,200 --> 00:25:18,600 Konečný výsledok je rovnaký. 718 00:25:18,600 --> 00:25:22,730 , Ktorá z týchto algoritmov je lepší? 719 00:25:22,730 --> 00:25:23,500 Druhý, počul som. 720 00:25:23,500 --> 00:25:24,252 Prečo? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Je to n krokov [nepočuteľné]. 722 00:25:25,900 --> 00:25:27,600 >> David J. Malan: Je to n kroky na najviac. 723 00:25:27,600 --> 00:25:28,490 Zaujímavý. 724 00:25:28,490 --> 00:25:30,610 Tak to je keď? 725 00:25:30,610 --> 00:25:33,630 Tak ako som nenašiel najmenší prvok? 726 00:25:33,630 --> 00:25:37,060 Koľko krokov som vziať nájsť najmenší prvok? 727 00:25:37,060 --> 00:25:39,220 Som sa pozerať celú cestu na konci, nie? 728 00:25:39,220 --> 00:25:41,530 Vzhľadom k tomu, že v najhoršom prípade, čo ak Neil bol tu? 729 00:25:41,530 --> 00:25:45,700 Takže stačí nájsť najmenší prvok ma berie n kroky, alebo n mínus jedna. 730 00:25:45,700 --> 00:25:46,100 Ale OK. 731 00:25:46,100 --> 00:25:46,980 Takže opraviť Neila. 732 00:25:46,980 --> 00:25:48,740 Pamätajte si, že minútu alebo tak dávno. 733 00:25:48,740 --> 00:25:51,680 >> Ale ako som našiel ďalšie najmenší prvok? 734 00:25:51,680 --> 00:25:54,830 Je to n mínus 1 alebo n mínus 2 naozaj, z počtu krokov. 735 00:25:54,830 --> 00:25:55,440 Tak OK. 736 00:25:55,440 --> 00:25:57,390 Tak som sa n mínus 2. 737 00:25:57,390 --> 00:25:57,600 Dobrá. 738 00:25:57,600 --> 00:25:59,130 Tak, že sa cíti o niečo lepšie. 739 00:25:59,130 --> 00:25:59,730 Dobrá. 740 00:25:59,730 --> 00:26:03,270 Koľko krokov nabudúce nájsť číslo tri? 741 00:26:03,270 --> 00:26:04,420 Tak n mínus 4. 742 00:26:04,420 --> 00:26:07,670 Takže to klesá, jeden menej krok na každej iterácii. 743 00:26:07,670 --> 00:26:08,740 Tak to sa cítiť lepšie, nie? 744 00:26:08,740 --> 00:26:13,450 Pokiaľ poslednej dobe to bolo zhruba n krát n, tentokrát je to n mínus jedna plus mínus n 745 00:26:13,450 --> 00:26:16,500 2, a n mínus 3, a n mínus 4, bodka, bodka, bodka. 746 00:26:16,500 --> 00:26:18,750 Ale ak si spomínam z vašej vysokej škole učebnice, trochu podvádzať 747 00:26:18,750 --> 00:26:24,380 list na zadnej strane, ktorý má vzorce, ak spočítate túto radu čísel, 748 00:26:24,380 --> 00:26:31,280 Aký je celkový počet krokov bude, že som sa tu? 749 00:26:31,280 --> 00:26:36,580 >> To je jeden z tých, ako, n mínus 1, n krát, delené 2. 750 00:26:36,580 --> 00:26:39,040 Tak sa ukážte, či môžem vytiahnuť to sa len na chvíľu. 751 00:26:39,040 --> 00:26:42,230 A opäť som trochu zaokrúhľovania niektorých čísla len aby náš život jednoduchý, 752 00:26:42,230 --> 00:26:47,830 ale ak si spomínam, je to niečo, ako keby Ja n mínus jedna veci, potom n mínus 753 00:26:47,830 --> 00:26:53,570 2, potom n mínus tri, to je zhruba niečo také po 2, a keď som 754 00:26:53,570 --> 00:26:55,510 násobiť na to, že je v skutočnosti n námestí. 755 00:26:55,510 --> 00:26:58,940 To sa necíti moc dobre. n n mínus na 2. 756 00:26:58,940 --> 00:27:00,350 >> Ale tu je to vec. 757 00:27:00,350 --> 00:27:03,720 Vo vede o počítačoch, keď sa problémy začať byť zaujímavé, ak je n 758 00:27:03,720 --> 00:27:04,700 dostane naozaj veľký. 759 00:27:04,700 --> 00:27:08,110 A vtedy, keď n sa naozaj veľké, čo z Tieto hodnoty sa chystá ovládnuť všetky 760 00:27:08,110 --> 00:27:09,750 z ostatných? 761 00:27:09,750 --> 00:27:10,990 Je to tak trochu na n na druhú, nie? 762 00:27:10,990 --> 00:27:13,340 Áno, delenie 2 je celkom dobrý. 763 00:27:13,340 --> 00:27:16,740 Ale ak hovoríme o miliardách z kusov dát, alebo biliónoch 764 00:27:16,740 --> 00:27:18,700 časti dát, OK, tak ste dvakrát tak rýchlo. 765 00:27:18,700 --> 00:27:22,440 Ale kto naozaj zaujíma, či ten veľký počet, Keď je tento faktor je, čo sa bude 766 00:27:22,440 --> 00:27:23,040 väčšie a väčšie. 767 00:27:23,040 --> 00:27:25,990 A iste, to robí viac rozdiel, než toho chlapa. 768 00:27:25,990 --> 00:27:29,120 Takže aj keď ste pravdu, Druhý algoritmus, budeme nazývať 769 00:27:29,120 --> 00:27:32,970 výber druhu, je v reálnom svete, trochu rýchlejší potenciálne, pretože som 770 00:27:32,970 --> 00:27:35,360 s menej a menej kroky zakaždým. 771 00:27:35,360 --> 00:27:37,340 >> V skutočnosti to nie je zásadne rýchlejšie. 772 00:27:37,340 --> 00:27:41,430 Pretože ak budeme skutočne hrať to von veľké hodnoty n, na konci 773 00:27:41,430 --> 00:27:44,750 deň, po dobu dosť veľký n, je to stále bude cítiť celkom pomalý. 774 00:27:44,750 --> 00:27:46,770 No, dovoľte mi, aby som jednu posledný priechod na to. 775 00:27:46,770 --> 00:27:48,920 To je to, čo by som nazval Výber sort. 776 00:27:48,920 --> 00:27:51,040 Môže vás obnoviť sami raz naposledy? 777 00:27:51,040 --> 00:27:53,550 A v tomto poslednom prípade, idem navrhnúť niečo 778 00:27:53,550 --> 00:27:54,970 volal vloženie radenie. 779 00:27:54,970 --> 00:27:57,470 Vloženie druh bytia, koncepčne, trochu inak. 780 00:27:57,470 --> 00:28:00,980 >> Skôr než ísť tam a späť výberom najmenší prvok, som 781 00:28:00,980 --> 00:28:05,030 len tak vysporiadať s každou z nich chalani, ako som sa s nimi stretnúť, a vložte 782 00:28:05,030 --> 00:28:06,850 je do ich správne miesto. 783 00:28:06,850 --> 00:28:10,160 Tak som len tak začať s Grace, a vidím, že je to číslo štyri. 784 00:28:10,160 --> 00:28:11,720 Kde sa číslo štyri patrí? 785 00:28:11,720 --> 00:28:14,940 Som sa začala triediť nič, Milosť tak dostane zostať tu. 786 00:28:14,940 --> 00:28:18,355 A teraz budem tvrdiť, keby si mohol krok na pravej strane, to 787 00:28:18,355 --> 00:28:21,650 môj radené zoznam, to je moje netriedeného zostávajúce zoznam. 788 00:28:21,650 --> 00:28:23,260 Takže teraz budem pokračovať ďalej, a čo sa to voláte? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> David J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Takže Branson je číslo dva. 792 00:28:25,375 --> 00:28:27,490 Takže budem ťa vziať sa na chvíľu zamyslel. 793 00:28:27,490 --> 00:28:30,940 A teraz, kam patrí v tomto poli? 794 00:28:30,940 --> 00:28:32,360 Takže na pravej milosti. 795 00:28:32,360 --> 00:28:35,670 Takže znovu, sme druh výroby Milosť urobiť veľa práce tu. 796 00:28:35,670 --> 00:28:37,290 Kde sme ťa? 797 00:28:37,290 --> 00:28:40,120 Takže budeme kĺzať vás vľavo, a vložte tam Branson. 798 00:28:40,120 --> 00:28:41,680 Ale teraz tvrdia, že ste hotoví. 799 00:28:41,680 --> 00:28:43,240 Ale oznámenia, nebudem používať extra priestor. 800 00:28:43,240 --> 00:28:45,130 Je to stále dva elementy tu 5. sem. 801 00:28:45,130 --> 00:28:47,910 Celková veľkosť poľa je 7, takže som nepodvádza, v poriadku? 802 00:28:47,910 --> 00:28:51,950 >> Takže teraz máme s Gabe tu číslo šesť, kam patrí? 803 00:28:51,950 --> 00:28:52,650 Máš šťastie znova. 804 00:28:52,650 --> 00:28:53,820 Takže ste si zostať tu. 805 00:28:53,820 --> 00:28:57,210 Len sa mierny krok na pravej strane len aby bolo jasné, že ste radené. 806 00:28:57,210 --> 00:29:00,520 A teraz máme Neil opäť číslo jedno, kam pôjdeš? 807 00:29:00,520 --> 00:29:03,540 A teraz je tam, kde začneme vidieť, že Tento algoritmus, aj keď na prvý 808 00:29:03,540 --> 00:29:05,950 pohľad, sa cíti celkom múdra, sledovať čo sa stane. 809 00:29:05,950 --> 00:29:07,370 Ak by ste mohli krok vpred. 810 00:29:07,370 --> 00:29:09,260 >> Kde chceme dať Neila? 811 00:29:09,260 --> 00:29:11,830 Je teda jasné, tu, tak ako sa dostaneme Neila tam? 812 00:29:11,830 --> 00:29:12,970 Poďme urobiť tento krok-za-krokom. 813 00:29:12,970 --> 00:29:15,620 Gabe, kde budete musieť ísť? 814 00:29:15,620 --> 00:29:19,590 Jo, tak sa jeden veľký krok, alebo dve polovice-kroky, aby 815 00:29:19,590 --> 00:29:20,820 jeden krok tam. 816 00:29:20,820 --> 00:29:21,750 Milosť, kam ísť? 817 00:29:21,750 --> 00:29:22,510 Dobre. 818 00:29:22,510 --> 00:29:23,500 Takže ďalší krok. 819 00:29:23,500 --> 00:29:24,960 A konečne, Branson? 820 00:29:24,960 --> 00:29:25,460 Ďalším krokom. 821 00:29:25,460 --> 00:29:27,190 A teraz môžeme dať Neila na miesto. 822 00:29:27,190 --> 00:29:28,440 >> Takže teraz, aj naďalej túto logiku. 823 00:29:28,440 --> 00:29:32,420 Aj keď nie sme presúva Neil nad, a cez, a cez, aby ho 824 00:29:32,420 --> 00:29:36,420 kde ide, v najhoršom prípade, ďalšie číslo môžeme stretnúť mohli 825 00:29:36,420 --> 00:29:42,220 je číslo, povedzme, že sa rad nula, potom sa budeme presúvať všetky 826 00:29:42,220 --> 00:29:42,730 títo chlapci. 827 00:29:42,730 --> 00:29:44,950 Predpokladajme, že existuje celý rad, negatívny jeden, potom musíme posunúť 828 00:29:44,950 --> 00:29:46,080 všetkých týchto ľudí. 829 00:29:46,080 --> 00:29:48,500 Takže sme naozaj len tak preletia problém asi tak, že sme 830 00:29:48,500 --> 00:29:52,620 prevedenie náklady z Výberové konanie tak vloženie 831 00:29:52,620 --> 00:29:56,930 proces tak, že ste jednoducho musel pohybovať zhruba n mínus niečo 832 00:29:56,930 --> 00:29:57,940 počet krokov. 833 00:29:57,940 --> 00:30:01,200 A to počet krokov je až vo chvíli, zvýšiť, keď som vybrať viac čísel, 834 00:30:01,200 --> 00:30:04,730 keď budem musieť držať strkať chlapci späť, a späť, a späť. 835 00:30:04,730 --> 00:30:08,320 >> Tak smutné, teraz je všetko z nich algoritmy sú n na druhú. 836 00:30:08,320 --> 00:30:10,570 Poďme ďalej a vďaka týmto chlapci, a vizualizovať tieto trochu 837 00:30:10,570 --> 00:30:11,090 inak. 838 00:30:11,090 --> 00:30:12,312 Veľmi dobre. 839 00:30:12,312 --> 00:30:14,120 >> [APPLAUSE] 840 00:30:14,120 --> 00:30:15,030 >> Dobrá. 841 00:30:15,030 --> 00:30:16,280 Tu to je. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Vďaka za - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [nepočuteľné] držať čísla. 845 00:30:19,190 --> 00:30:21,990 >> David J. Malan: Nie, môžete držať čísla rovnako. 846 00:30:21,990 --> 00:30:23,440 Dobrá. 847 00:30:23,440 --> 00:30:24,100 Dobrá práca. 848 00:30:24,100 --> 00:30:25,300 Dobrá. 849 00:30:25,300 --> 00:30:30,510 Tak uvidíme, či nemôžeme teraz zhrnúť rýchlejšie a viac vizuálne, 850 00:30:30,510 --> 00:30:33,410 presne to, čo sa práve stalo tu takto. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Chystám sa ísť dopredu a vytiahnite Firefox. 853 00:30:38,770 --> 00:30:41,310 Budeme odkaz na túto demonštráciu na ihrisku internetových stránkach. 854 00:30:41,310 --> 00:30:43,870 Java je trochu nepríjemné, aby sa pracovné v niektorých prehliadačoch v týchto dňoch. 855 00:30:43,870 --> 00:30:46,760 Takže ak nechcete hrať s tým doma, Uvedomujem si, môže byť potrebné používať Firefox 856 00:30:46,760 --> 00:30:47,990 aby si to prácu. 857 00:30:47,990 --> 00:30:50,440 A čo budem robiť s tým ukážka je nasledujúci. 858 00:30:50,440 --> 00:30:54,875 >> Na dne, mám veľa možnosti ponuky, vrátane začiatku a 859 00:30:54,875 --> 00:30:55,840 tlačidlo stop. 860 00:30:55,840 --> 00:30:59,450 Tiež, ako stranou, sa zdá, že chyba v týchto programoch, pričom si 861 00:30:59,450 --> 00:31:03,720 nemôže skutočne vidieť štart alebo zastavenie tlačidlo, ak budete držať príkazu alebo Alt 862 00:31:03,720 --> 00:31:06,560 plus a zoom, ktorý zvedavo zobrazuje viac tlačidiel. 863 00:31:06,560 --> 00:31:09,090 Takže len FYI, ak budete hrať s tým doma. 864 00:31:09,090 --> 00:31:12,870 Teraz idem na tlačidlo Štart v práve Okamih, po zadaní oneskorenie, 865 00:31:12,870 --> 00:31:16,810 ako, 200 milisekúnd, jednoducho takže môžeme vidieť, čo sa stane. 866 00:31:16,810 --> 00:31:20,180 >> Takže tvrdím, že je to vizualizácia prvého algoritmu 867 00:31:20,180 --> 00:31:23,730 títo ľudia urobili, bublinková triedenia, pričom sme vymenili ľudí párová. 868 00:31:23,730 --> 00:31:27,490 Kľúčovou myšlienkou tohto vizualizácie je, že výška stĺpcov 869 00:31:27,490 --> 00:31:30,510 predstavuje veľkosť čísla. 870 00:31:30,510 --> 00:31:32,210 Takže je stĺpec vyšší, Čím vyššie je číslo. 871 00:31:32,210 --> 00:31:33,680 Kratšie bar, menšie číslo. 872 00:31:33,680 --> 00:31:38,630 A ak si všimnete, ideme cez Prvá iterácia tohto algoritmu, 873 00:31:38,630 --> 00:31:42,620 vymieňať veľké aj malé množstvo, takže malý počet je na prvom mieste a 874 00:31:42,620 --> 00:31:44,280 Veľké množstvo ide na pravej strane. 875 00:31:44,280 --> 00:31:48,770 >> A akonáhle sa dostaneme na koniec poľa mnoho viac ako sedem čísel, sme 876 00:31:48,770 --> 00:31:49,900 ísť späť na začiatok. 877 00:31:49,900 --> 00:31:51,140 A to predvídať. 878 00:31:51,140 --> 00:31:54,860 Na úplne vľavo, ten malý chlapec sa deje swap na stranu, a to 879 00:31:54,860 --> 00:31:56,010 proces sa opakuje. 880 00:31:56,010 --> 00:31:59,450 Teraz je táto vizualizácia rýchlo dostane nuda, tak nechajte ma ísť dopredu a zastavte sa 881 00:31:59,450 --> 00:32:04,170 , Zmeniť oneskorenie niečo oveľa rýchlejšie len preto, aby teraz, cit pre 882 00:32:04,170 --> 00:32:05,060 Tento algoritmus. 883 00:32:05,060 --> 00:32:07,840 >> Takže aj keď som sa ponáhľal hore, je to ako upgrade môj procesor, nákup 884 00:32:07,840 --> 00:32:08,580 nový počítač. 885 00:32:08,580 --> 00:32:12,980 Som zásadne nezmenil môj algoritmus, ale môžete naozaj vidieť viac 886 00:32:12,980 --> 00:32:16,800 jasne ako s ľuďmi, že veľký Čísla vyviera na vrchol, 887 00:32:16,800 --> 00:32:20,900 a malé čísla vyviera až na dno. 888 00:32:20,900 --> 00:32:22,390 A teraz toto, čo tu radené. 889 00:32:22,390 --> 00:32:25,260 A stranou, na námestiach, je tu len niektoré účtovníctva tam 890 00:32:25,260 --> 00:32:28,010 pomôže spočítať, koľko porovnanie, alebo koľko swapy majú 891 00:32:28,010 --> 00:32:28,950 skutočne vykonané. 892 00:32:28,950 --> 00:32:30,750 >> Dobre, poďme vyskúšať jednu z ostatné sme videli. 893 00:32:30,750 --> 00:32:37,116 Dovoľte mi, aby som kliknite na bubliny druhu tu, a zvolím, a celá táto webová stránka 894 00:32:37,116 --> 00:32:38,936 je trochu buggy. 895 00:32:38,936 --> 00:32:41,155 Poďme prijať riziko a spustite ho znova. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Tam ideme. 898 00:32:45,030 --> 00:32:47,180 Tak jdem na výber druhu. 899 00:32:47,180 --> 00:32:49,140 Neviem, prečo menu objaví sa tam. 900 00:32:49,140 --> 00:32:54,070 Poďme priblíženie napraviť chyba, zmeniť na 50 rokov. 901 00:32:54,070 --> 00:32:56,020 Ach, poďme skutočne o to rýchlejšie. 902 00:32:56,020 --> 00:32:59,160 Päť milisekúnd alebo tak, a začať. 903 00:32:59,160 --> 00:33:00,470 >> Tak to je výber druh. 904 00:33:00,470 --> 00:33:03,070 Takže znova, myslím, že o tom, čo robil s ľuďmi tady. 905 00:33:03,070 --> 00:33:08,490 Išli sme cez pole a vybrané najmenší prvok znovu, 906 00:33:08,490 --> 00:33:09,250 a znova a znova. 907 00:33:09,250 --> 00:33:11,110 Teraz tvrdí, že je stále dosť zlý. 908 00:33:11,110 --> 00:33:15,010 To bolo ešte n štvorcový, dávať alebo brať, ale to bolo v reálnom svete, trochu 909 00:33:15,010 --> 00:33:18,280 rýchlejší, pretože som bol naozaj s o niečo menej krokov zakaždým. 910 00:33:18,280 --> 00:33:19,800 Ale hovoríme len čo? 911 00:33:19,800 --> 00:33:21,830 Možno 40 alebo tak, bary tu? 912 00:33:21,830 --> 00:33:23,200 Nehovoríme 40 miliónov. 913 00:33:23,200 --> 00:33:27,430 Takže to nie je úplne jasné, že bol naozaj značný zisk. 914 00:33:27,430 --> 00:33:32,530 >> Dovoľte mi, aby som sa vrátiť a zmeniť k nášmu Tretí algoritmus, ktorý bol vyberte 915 00:33:32,530 --> 00:33:33,180 vloženie sort. 916 00:33:33,180 --> 00:33:36,380 A teraz je to naozaj buggy, pretože Ponuka naozaj by nemal byť tam dole. 917 00:33:36,380 --> 00:33:40,840 Takže teraz budeme listovať sem a začať tento algoritmus. 918 00:33:40,840 --> 00:33:43,270 Pokrik, spustenie a zastavenie. 919 00:33:43,270 --> 00:33:47,160 Takže to jeden druhov má pekný vzor na to, kedy sme znovu 920 00:33:47,160 --> 00:33:50,240 vloženie ľudí, alebo v V tomto prípade, bary do 921 00:33:50,240 --> 00:33:52,620 ich vhodné umiestnenie. 922 00:33:52,620 --> 00:33:55,430 A to už urobil pred Otočil som sa. 923 00:33:55,430 --> 00:33:58,940 Ale tento taky, teoreticky, je stále n na druhú. 924 00:33:58,940 --> 00:34:01,430 >> Tak uvidíme, či nemôžeme zhrnúť Tieto takto. 925 00:34:01,430 --> 00:34:04,750 Chystám sa ísť dopredu a len preto, aby nám trochu bežným spôsobom hovorí 926 00:34:04,750 --> 00:34:08,489 o týchto veciach, dovoľte mi predstaviť len trochu notácie tu. 927 00:34:08,489 --> 00:34:12,480 Chystáte sa vidieť niečo, čo nazýva veľký O, pretože je to doslova veľký 928 00:34:12,480 --> 00:34:16,320 O. A to je tak, že počítač vedec alebo matematik dokonca používa 929 00:34:16,320 --> 00:34:19,230 popísať prevádzkovú dobu nejakého algoritmu. 930 00:34:19,230 --> 00:34:21,400 Koľko krokov to vlastne trvá? 931 00:34:21,400 --> 00:34:25,080 >> Teraz idem do rozpakov som sa môj rukopis tú za chvíľu. 932 00:34:25,080 --> 00:34:29,020 Ale dovoľte mi ísť ďalej a povedať, že to bude veľký O sem. 933 00:34:29,020 --> 00:34:33,610 A dovoľte, aby som vám predstavil jeden ďalší symbol, kapitál omega. 934 00:34:33,610 --> 00:34:37,080 Omega bude naopak, v podstate z veľkej O. keďže veľké O 935 00:34:37,080 --> 00:34:40,790 znamená, v najhoršom prípade, koľko času môže nejaký algoritmus prijať, 936 00:34:40,790 --> 00:34:43,480 Podmienky n omega bude sa, koľko času mohlo by to 937 00:34:43,480 --> 00:34:45,409 sa v najlepšom prípade. 938 00:34:45,409 --> 00:34:48,090 A uvidíme, čo máme na mysli najlepšom prípade za chvíľu. 939 00:34:48,090 --> 00:34:49,940 >> Tak začnime niečo jednoduchého. 940 00:34:49,940 --> 00:34:54,719 Dovoľte mi začať s lineárnym vyhľadávania. 941 00:34:54,719 --> 00:34:55,679 Takže nie je triedenie. 942 00:34:55,679 --> 00:34:58,000 Nazveme to lineárne hľadanie. 943 00:34:58,000 --> 00:35:01,140 A teraz, aby sa trochu tabuľka z toho. 944 00:35:01,140 --> 00:35:06,600 A teraz, v prípade lineárneho vyhľadávania v najhoršom prípade sledovať, koľko krokov je 945 00:35:06,600 --> 00:35:11,770 bude trvať ma, počet ľubovoľnej voľby? 946 00:35:11,770 --> 00:35:14,540 A je tu celkom n dvere alebo n celkový počet. 947 00:35:14,540 --> 00:35:15,940 Najhorší prípad. 948 00:35:15,940 --> 00:35:18,800 Koľko krokov budem musieť sa nájsť číslo 50 v poli 949 00:35:18,800 --> 00:35:20,830 dverí n? 950 00:35:20,830 --> 00:35:21,410 A prečo? 951 00:35:21,410 --> 00:35:23,680 Vzhľadom k tomu, že to môže byť všetko cesta cez na koniec. 952 00:35:23,680 --> 00:35:27,120 Takže rovnako ako Jennifer sa stretol, Číslo 50 bolo celú cestu, tak v 953 00:35:27,120 --> 00:35:30,760 v najhoršom prípade lineárnej hľadanie je veľký O n, budeme hovoriť. 954 00:35:30,760 --> 00:35:33,430 >> A čo najlepšom prípade, ak máte naozaj šťastie? 955 00:35:33,430 --> 00:35:36,200 Je to len tak, aby sa jeden krok, alebo stály počet krokov. 956 00:35:36,200 --> 00:35:37,830 Takže budeme popisovať to ako jeden. 957 00:35:37,830 --> 00:35:39,010 Tak to je celkom dobrý. 958 00:35:39,010 --> 00:35:41,210 Teraz, čo keby sme urobili niečo ako binárne vyhľadávanie? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Takže binárne vyhľadávanie, v najhoršom prípad, vzal koľko času? 961 00:35:47,846 --> 00:35:49,250 >> [Prechodová Hlasy] 962 00:35:49,250 --> 00:35:51,310 >> David J. Malan: Takže vlastne som počul za pár miestach. 963 00:35:51,310 --> 00:35:56,390 Takže je to vlastne log n, dávať alebo brať, pretože ako rozdeliť zoznam na dve polovice 964 00:35:56,390 --> 00:36:00,730 znova a znova, a znova, sme schopní nájsť, nakoniec, je táto hodnota, 965 00:36:00,730 --> 00:36:04,750 či je to tam, ale je tu jeden háčik. 966 00:36:04,750 --> 00:36:08,590 Aký je predpoklad, že musíme brať za samozrejmosť, pre binárne vyhľadávanie? 967 00:36:08,590 --> 00:36:09,700 Musí byť triedené. 968 00:36:09,700 --> 00:36:12,770 Je to netriedi, môžete rozdeliť vec na polovicu znova a znova, a vy 969 00:36:12,770 --> 00:36:15,490 môže ísť vľavo, a môžete ísť vpravo, a môžete ísť doľava a doprava, ale vy ste 970 00:36:15,490 --> 00:36:18,070 nenájde prvok, ak zoznam nie je zoradený, pretože 971 00:36:18,070 --> 00:36:18,790 môžete si ho ujsť. 972 00:36:18,790 --> 00:36:22,120 Pretože vaše heuristiky pre prechod vľavo alebo doprava sa bude chybný, ak je to 973 00:36:22,120 --> 00:36:23,420 naozaj nie sú zoradené. 974 00:36:23,420 --> 00:36:26,110 Takže je tu akýsi skryté náklady s použitím niečo také. 975 00:36:26,110 --> 00:36:29,250 >> Teraz poďme do nášho triedenia algoritmy nehľadal - 976 00:36:29,250 --> 00:36:31,140 oh, vlastne ideme v tomto prázdne. 977 00:36:31,140 --> 00:36:33,190 Binárne hľadanie v najlepšom prípade? 978 00:36:33,190 --> 00:36:36,290 Je to tiež jedno, pokiaľ to len sa stane byť v samom strede poľa, alebo 979 00:36:36,290 --> 00:36:37,810 uprostred telefónneho zoznamu. 980 00:36:37,810 --> 00:36:39,710 Teraz sa poďme robiť bubliny druhu. 981 00:36:39,710 --> 00:36:42,570 Takže znova, teraz sa vstupom do druhy, nie hľadanie. 982 00:36:42,570 --> 00:36:47,220 >> V najhoršom prípade, koľko krokov to sme tvrdenie bublina trochu to bude trvať? 983 00:36:47,220 --> 00:36:48,410 n na druhú. 984 00:36:48,410 --> 00:36:49,200 Takže budem kresliť to. 985 00:36:49,200 --> 00:36:51,710 Ooh, môj rukopis vyzerá ešte horšie keď sa to predpokladá, že veľký. 986 00:36:51,710 --> 00:36:52,510 Dobrá. 987 00:36:52,510 --> 00:36:53,570 Tak to je n na druhú. 988 00:36:53,570 --> 00:36:59,460 A v najlepšom prípade bublinkovej druhu, koľko krokov to bude trvať? 989 00:36:59,460 --> 00:37:00,980 1, počul som. 990 00:37:00,980 --> 00:37:01,760 >> Reproduktor 1: n 991 00:37:01,760 --> 00:37:03,286 >> David J. Malan: n, počul som. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> David J. Malan: 2, počul som. 994 00:37:05,010 --> 00:37:06,670 Počujem 3? 995 00:37:06,670 --> 00:37:07,080 Dobrá. 996 00:37:07,080 --> 00:37:11,390 Počul som 1, n 2, ale poďme vybrať od seba aspoň prvé z nich 997 00:37:11,390 --> 00:37:12,330 návrhy, 1. 998 00:37:12,330 --> 00:37:15,370 Nie je to zlý inštinkt, pretože to druh kopíruje vzor tu. 999 00:37:15,370 --> 00:37:19,670 Ale ak to trvá len jeden krok, ako v svet mohol by som tvrdiť, že zoznam 1000 00:37:19,670 --> 00:37:22,900 je triedený, pretože keď som povolené len aby sa jeden krok, koľko prvkov 1001 00:37:22,900 --> 00:37:25,230 mohol by som vlastne skontrolujte, či? 1002 00:37:25,230 --> 00:37:28,270 No, len 1, čo znamená, že je n mínus 1 prvkov, ktoré by mohli byť z 1003 00:37:28,270 --> 00:37:31,310 poriadku, a ja som jednoducho ísť na viere po pri pohľade na jeden prvok, ktorý 1004 00:37:31,310 --> 00:37:31,850 vec je zoradený. 1005 00:37:31,850 --> 00:37:33,930 Takže 1. Nie je opraviť tady. 1006 00:37:33,930 --> 00:37:35,710 Takže minimálne, koľko musím sa pozrieť na? 1007 00:37:35,710 --> 00:37:36,680 >> [Prechodová Hlasy] 1008 00:37:36,680 --> 00:37:40,160 >> David J. Malan: n mínus jedna, alebo naozaj, n, pretože som sa treba pozrieť sa na každý 1009 00:37:40,160 --> 00:37:42,190 prvok, aby sa ubezpečil, že to nie je mimo prevádzky. 1010 00:37:42,190 --> 00:37:44,750 Ale opäť budeme triediť vlny nášho ruky na menších číslach a 1011 00:37:44,750 --> 00:37:47,100 Predpokladajme, že, ako n sa zväčší, sú nezaujímavé rovnako. 1012 00:37:47,100 --> 00:37:48,380 Tak to je bublina triedenie. 1013 00:37:48,380 --> 00:37:49,830 A teraz, poďme sa tieto dva posledné. 1014 00:37:49,830 --> 00:37:53,520 Výber druhu, a potom budeme robiť vloženie radenie. 1015 00:37:53,520 --> 00:37:57,160 A potom sa stočí svojou myseľ sa niečo oveľa 1016 00:37:57,160 --> 00:37:58,926 lepšie ako všetky z nich. 1017 00:37:58,926 --> 00:38:00,410 Dobrá. 1018 00:38:00,410 --> 00:38:04,700 >> Čo je najhoršie beh Doba výber druhu? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n na druhú. 1020 00:38:05,680 --> 00:38:06,710 >> David J. Malan: n námestí, počujem. 1021 00:38:06,710 --> 00:38:09,790 Ale prečo n na druhú, intuitívne? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Pretože sme práve urobili. 1023 00:38:11,170 --> 00:38:12,260 >> David J. Malan: Pretože sme práve urobili. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Dobrá odpoveď. 1026 00:38:13,380 --> 00:38:16,660 Ale intuitívne, prečo je výber radiť n na druhú? 1027 00:38:16,660 --> 00:38:18,980 Čo musíme urobiť, znova a znova? 1028 00:38:18,980 --> 00:38:22,570 Museli sme sa držať skenovaním, sú môžete najmenší, ste 1029 00:38:22,570 --> 00:38:24,020 Najmenšie sú tie najmenšie. 1030 00:38:24,020 --> 00:38:27,480 A samozrejmosť, sme boli schopní prijať n kroky, potom n mínus 1, potom n mínus 2. 1031 00:38:27,480 --> 00:38:30,700 Ale ak si trochu pridať tie všetko, alebo ju na viere, že som pridal 1032 00:38:30,700 --> 00:38:34,810 je s predstihom, dostaneme zhruba n na druhú mínus niektorých menších čísel. 1033 00:38:34,810 --> 00:38:36,730 Takže budem volať to n na druhú. 1034 00:38:36,730 --> 00:38:39,530 Ale s výberom druhu v najlepšom prípad sledovať, koľko krokov je 1035 00:38:39,530 --> 00:38:40,632 ma vezme? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [nepočuteľné] 1037 00:38:41,840 --> 00:38:44,350 >> David J. Malan: Je to bohužiaľ Stále n na druhú, nie? 1038 00:38:44,350 --> 00:38:49,590 Pretože keď som výberom najmenší prvok, a mali sme sedem ľudí tu, 1039 00:38:49,590 --> 00:38:53,280 Ja len viem, akonáhle sa dostanem k veľmi koniec, že ​​som našiel najmenší 1040 00:38:53,280 --> 00:38:55,670 číslo, kde on alebo ona môže byť. 1041 00:38:55,670 --> 00:38:58,820 Ale ako nájdem ďalšie najmenšie číslo? 1042 00:38:58,820 --> 00:39:00,160 Musím urobiť ďalšiu prihrávku. 1043 00:39:00,160 --> 00:39:04,810 Takže v najlepšom prípade, aký je Vstup do výberu druhu? 1044 00:39:04,810 --> 00:39:07,830 Je to už trochu zoznamu číslo jedna, číslo dva, číslo tri, číslo štyri. 1045 00:39:07,830 --> 00:39:08,600 Ale ja som počítač. 1046 00:39:08,600 --> 00:39:10,190 Môžem len pozrieť na jeden vec naraz. 1047 00:39:10,190 --> 00:39:12,465 Nemôžem nejako krok späť ako človek a povedal: 1048 00:39:12,465 --> 00:39:14,030 ooh, to vyzerá správne. 1049 00:39:14,030 --> 00:39:17,580 >> Môžem len rozhodnúť korektnosť Triediť podľa výberu 1050 00:39:17,580 --> 00:39:18,370 najmenšie číslo. 1051 00:39:18,370 --> 00:39:21,390 Ale aj keď som si prvé číslo jedna, či neviem niečo o 1052 00:39:21,390 --> 00:39:24,460 iné čísla, ktoré nemám, všetko, čo som viem, že som podal rad 1053 00:39:24,460 --> 00:39:27,930 alebo sada za sebou dvere, ktoré sú čísla, jediný spôsob, ako viem, že jedna 1054 00:39:27,930 --> 00:39:28,680 Jednalo sa o najmenší? 1055 00:39:28,680 --> 00:39:32,440 Ak sa dostanem až sem a uvedomiť si, sakra, jeden bol naozaj najmenší. 1056 00:39:32,440 --> 00:39:34,870 >> Ale ako som sa potom rozhodne, že dva je ďalší najmenší? 1057 00:39:34,870 --> 00:39:38,350 Tým, že robí rovnakú neefektívnosť znova a znova. 1058 00:39:38,350 --> 00:39:42,210 Tak konečne sa vloženie druhu, how, v najhoršom prípade, 1059 00:39:42,210 --> 00:39:44,990 sme sa, že to robí? 1060 00:39:44,990 --> 00:39:49,100 To tiež je n na druhú. 1061 00:39:49,100 --> 00:39:53,020 A čo s tým najlepšom prípade? 1062 00:39:53,020 --> 00:39:56,282 Necháme to ako Cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Budeme vyplniť tej prázdne nabudúce, ale najprv mi dovoľte navrhnúť, aby sme 1064 00:40:00,090 --> 00:40:02,620 podstatne lepšie ako všetky z nich, v poriadku? 1065 00:40:02,620 --> 00:40:05,220 >> Takže myslíte, že to, čo pre seba vloženie druh to bude. 1066 00:40:05,220 --> 00:40:06,910 No, to nie je príliš dramatický, pretože som jediný 1067 00:40:06,910 --> 00:40:08,970 ktorá videla zmenu. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Takže tu máme niečo rôzne demonštrácie. 1071 00:40:12,615 --> 00:40:16,580 Keby som priblížiť tu, uvidíte, že na vľavo máme bubliny druh, v 1072 00:40:16,580 --> 00:40:20,740 Stredná máme výber druhu a na krajnej pravice, máme niečo, čo sme 1073 00:40:20,740 --> 00:40:23,380 som sa pozrel na doteraz tzv zlúčenie druhu. 1074 00:40:23,380 --> 00:40:26,080 Ale zvážte, čo sme boli tu robíš tak ďaleko ešte dnes. 1075 00:40:26,080 --> 00:40:29,200 Keď Jennifer prvýkrát prišiel na pódium, sme šli cez pole čísel 1076 00:40:29,200 --> 00:40:33,750 znova a znova, s lineárnou vyhľadávania a my sme dostali lineárny dobu chodu, veľké O 1077 00:40:33,750 --> 00:40:35,100 n, aby som tak povedal. 1078 00:40:35,100 --> 00:40:41,000 >> Keď sme sa teraz považujú za sebou prvý týždeň triedy, keď sme sa rozdeľ a panuj, 1079 00:40:41,000 --> 00:40:43,740 a my sme v telefónnom zozname slzenie, a Jennifer, a my spoločne 1080 00:40:43,740 --> 00:40:47,500 Kľúčovou myšlienkou, že hybnou silou, ktorá mala opakovať sa znova a znova 1081 00:40:47,500 --> 00:40:50,930 nejako zahodili, vyhadzovanie, zahodili, polovica problému, alebo 1082 00:40:50,930 --> 00:40:55,320 všeobecne, tak, že sa problém na polovicu, a liečbe menší kus 1083 00:40:55,320 --> 00:40:59,630 problém, koncepčne ekvivalentná na druhej strane, sa nejako 1084 00:40:59,630 --> 00:41:00,910 zásadne lepší. 1085 00:41:00,910 --> 00:41:04,720 Ale s bublinou druhu, s výber druhu, s vkladacie druhu, máme sa môžu 1086 00:41:04,720 --> 00:41:06,560 žiadne také poznatky, že Jennifer urobil. 1087 00:41:06,560 --> 00:41:10,220 Sme skoro rovnako vrátil a tam celá partia z časov, a my 1088 00:41:10,220 --> 00:41:12,650 Upravený veci trochu, vymieňať v tomto poradí, možno 1089 00:41:12,650 --> 00:41:13,730 vkladanie alebo výberu. 1090 00:41:13,730 --> 00:41:16,950 Ale na konci dňa, som veľa trápne chôdze tam a späť. 1091 00:41:16,950 --> 00:41:21,160 Nemali sme využiť čo chytrý ako Jennifer som rád delenie 1092 00:41:21,160 --> 00:41:22,040 a dobývanie. 1093 00:41:22,040 --> 00:41:25,620 >> Takže zlúčiť druh, naopak, ktoré neuvidí až do budúceho týždňa, bude to 1094 00:41:25,620 --> 00:41:29,540 sa pákového efektu, ktorý Kľúčovou myšlienkou vydelením vstup, a potom na polovicu, a potom 1095 00:41:29,540 --> 00:41:30,580 polovicu a potom polovicu. 1096 00:41:30,580 --> 00:41:34,590 A pri každom opakovaní tohto cyklu, triedenie ľavú polovicu, a právo 1097 00:41:34,590 --> 00:41:38,200 polovicu, potom Ľavá polovica ľavej polovice, a pravá polovica doľava, potom 1098 00:41:38,200 --> 00:41:40,990 Ľavá polovica v pravej polovici, a pravá polovica v pravej polovici. 1099 00:41:40,990 --> 00:41:42,840 A opakovať znovu a znovu. 1100 00:41:42,840 --> 00:41:46,170 >> Takže budete vidieť vizuálne, ale je to, čo nás čaká budúci týždeň. 1101 00:41:46,170 --> 00:41:49,760 A vôbec, keď si myslíme, že niečo trochu ťažšie na takéto prípadné problémy. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Máme n druhú vľavo, n druhú v polovici, a n 1104 00:41:57,970 --> 00:41:59,400 log n na pravej strane. 1105 00:41:59,400 --> 00:42:00,590 Takže tam je váš skutočný Cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Uvidíme sa v pondelok. 1107 00:42:02,040 --> 00:42:05,163 >> [APPLAUSE]