1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Prehrávanie hudby] 3 00:00:10,800 --> 00:00:13,500 DAVID Malan: Dobre. 4 00:00:13,500 --> 00:00:14,670 Dobre, vitaj späť. 5 00:00:14,670 --> 00:00:18,120 Tak toto je 4. týždeň, začiatok tejto zmluvy, už. 6 00:00:18,120 --> 00:00:21,320 A budete pripomenúť, že minulý týždeň, dáme kód stranou pre len trochu 7 00:00:21,320 --> 00:00:24,240 a začali sme hovoriť trochu viac na vysokej úrovni, o veci, ako je 8 00:00:24,240 --> 00:00:28,130 vyhľadávanie a radenie, ktoré, hoci trochu jednoduché nápady, sú 9 00:00:28,130 --> 00:00:31,840 zástupca skupiny problémov si začne riešiť najmä 10 00:00:31,840 --> 00:00:34,820 ako začnete premýšľať o finále projekty a zaujímavé riešenie, ktoré 11 00:00:34,820 --> 00:00:36,760 Možno budete musieť reálnych problémov. 12 00:00:36,760 --> 00:00:39,490 Teraz bublina druh bol jeden z najjednoduchších Takéto algoritmy, a to 13 00:00:39,490 --> 00:00:42,900 pracoval tým, že tieto malé množstvo v zozname alebo v poli typu 14 00:00:42,900 --> 00:00:46,530 bublina svoju cestu až na vrchol, a vysoké čísla pohybovať ich cestu až do 15 00:00:46,530 --> 00:00:47,930 koniec tohto zoznamu. 16 00:00:47,930 --> 00:00:50,650 >> A pripomínajú, že by sme mohli predstaviť bubble sort trochu 17 00:00:50,650 --> 00:00:52,310 niečo také. 18 00:00:52,310 --> 00:00:53,640 Tak ma nechaj ísť ďalej a kliknite na tlačidlo Spustiť. 19 00:00:53,640 --> 00:00:55,350 Som predvybrané bublina triedenie. 20 00:00:55,350 --> 00:00:58,920 A pokiaľ si spomínam, že vyššia modrá čiary predstavujú veľké čísla, malé 21 00:00:58,920 --> 00:01:03,300 Modrej čiary predstavujú malé množstvo, ako prejdeme to znova a znova a 22 00:01:03,300 --> 00:01:07,680 Znovu, porovnať dve tabuľky vedľa seba ďalšie v červenej farbe, ideme k výmene 23 00:01:07,680 --> 00:01:11,010 najväčšie a najmenšie, ak sú mimo prevádzky. 24 00:01:11,010 --> 00:01:14,150 >> Takže to bude pokračovať ďalej a ďalej a ísť na, a uvidíte, že čím väčšia 25 00:01:14,150 --> 00:01:16,700 prvky robia ich cestu k Dobre, a menšie prvky sú 26 00:01:16,700 --> 00:01:17,900 aby ich cestu na ľavej strane. 27 00:01:17,900 --> 00:01:21,380 Ale začali sme kvantifikovať účinnosť, 28 00:01:21,380 --> 00:01:22,970 Kvalita tohto algoritmu. 29 00:01:22,970 --> 00:01:25,200 A my sme povedali, že v najhoršom prípad, tento algoritmus sa 30 00:01:25,200 --> 00:01:27,940 zhruba, koľko krokov? 31 00:01:27,940 --> 00:01:28,980 >> Tak n na druhú. 32 00:01:28,980 --> 00:01:30,402 A čo bolo n? 33 00:01:30,402 --> 00:01:31,650 >> DIVÁKOV: Počet prvkov. 34 00:01:31,650 --> 00:01:32,790 >> DAVID Malan: Takže n bol počet prvkov. 35 00:01:32,790 --> 00:01:33,730 A tak sme si to často. 36 00:01:33,730 --> 00:01:36,650 Kedykoľvek chceme hovoriť o veľkosti o probléme alebo veľkosť 37 00:01:36,650 --> 00:01:39,140 vstup, alebo množstvo času, ktoré trvá produkovať výstup, budeme len 38 00:01:39,140 --> 00:01:41,610 zovšeobecniť, čo vstup je pre n 39 00:01:41,610 --> 00:01:45,970 Takže späť v týždni 0, počet strán v telefónnom zozname bolo n 40 00:01:45,970 --> 00:01:47,550 Počet študentov v miestnosti n 41 00:01:47,550 --> 00:01:49,630 Takže aj tu sledujeme že vzor. 42 00:01:49,630 --> 00:01:52,800 >> Teraz n na druhú nie je obzvlášť rýchlo, takže sme sa snažili urobiť lepšie. 43 00:01:52,800 --> 00:01:55,970 A tak sme sa pozreli na pár ďalšie algoritmy, z ktorých 44 00:01:55,970 --> 00:01:57,690 bol výber sort. 45 00:01:57,690 --> 00:01:59,180 Takže výber bol druh trochu iný. 46 00:01:59,180 --> 00:02:03,130 Bolo to skoro jednoduchšie, trúfam si povedať, kedy som začal na začiatku 47 00:02:03,130 --> 00:02:06,740 Zoznam našich dobrovoľníkov a ja len znova a znovu a znovu prechádzal 48 00:02:06,740 --> 00:02:10,060 zoznam, olúpanie najmenší prvok v čase a dávať ho alebo 49 00:02:10,060 --> 00:02:13,040 ju na začiatku zoznamu. 50 00:02:13,040 --> 00:02:16,410 >> Ale aj to, keď sme začali uvažovať cez matematiku a väčšie 51 00:02:16,410 --> 00:02:19,860 obraz, myslel na to, koľkokrát Bol som tam a späť a späť 52 00:02:19,860 --> 00:02:24,090 a tam sme si povedali, v najhoršom prípade, Výber druhu, bola taky čo? 53 00:02:24,090 --> 00:02:24,960 n na druhú. 54 00:02:24,960 --> 00:02:27,490 Teraz, v reálnom svete, môžu sa v skutočnosti mierne rýchlejší. 55 00:02:27,490 --> 00:02:30,620 Vzhľadom k tomu, znovu som nemusel držať backtracking, akonáhle som radené 56 00:02:30,620 --> 00:02:31,880 najmenšie prvky. 57 00:02:31,880 --> 00:02:35,090 Ale ak si myslíme, že o veľké n, ak si trochu urobiť z matematiky ako 58 00:02:35,090 --> 00:02:39,170 Ja som na doske s n na druhú mínus niečo, všetko ostatné 59 00:02:39,170 --> 00:02:41,850 okrem n na druhú, akonáhle n dostane naozaj veľký, nie je 60 00:02:41,850 --> 00:02:42,850 naozaj záležať. 61 00:02:42,850 --> 00:02:45,470 Takže ako počítačových vedcov, sme tak nejako prižmúriť oko menšie 62 00:02:45,470 --> 00:02:49,220 faktory a sústrediť sa iba na faktora v výraz, ktorý to bude robiť 63 00:02:49,220 --> 00:02:50,330 najväčší rozdiel. 64 00:02:50,330 --> 00:02:52,840 >> No, nakoniec sme sa zamerali pri vkladaní druhu. 65 00:02:52,840 --> 00:02:56,620 A to bol podobný v duchu, ale skôr než ísť cez opakované a 66 00:02:56,620 --> 00:03:01,250 vyberte najmenší prvok jeden na Tentoraz som namiesto toho vzal za ruku, že som 67 00:03:01,250 --> 00:03:04,070 bola riešená, a rozhodol som sa, všetko Dobre, sem patrí. 68 00:03:04,070 --> 00:03:06,160 Potom som sa presunul na ďalší prvok a rozhodol, že on alebo 69 00:03:06,160 --> 00:03:07,470 patrila tu. 70 00:03:07,470 --> 00:03:08,810 A potom som sa presunul ďalej a ďalej. 71 00:03:08,810 --> 00:03:11,780 A mohol by som sa, po ceste, presunúť týchto ľudí, aby sa 72 00:03:11,780 --> 00:03:13,030 aby pre nich priestor. 73 00:03:13,030 --> 00:03:16,880 Takže to bolo niečo ako duševná zvrat výberového druhu, ktorý sme 74 00:03:16,880 --> 00:03:18,630 volal vloženie radenie. 75 00:03:18,630 --> 00:03:20,810 >> Takže tieto témy sa objavujú v reálnom svete. 76 00:03:20,810 --> 00:03:23,640 Ešte pred niekoľkými rokmi, kedy určité Senátor sa uchádzal o prezidenta, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, v čase, keď generálny riaditeľ Google, skutočne možnosť 78 00:03:27,160 --> 00:03:28,040 aby ho vypočuť. 79 00:03:28,040 --> 00:03:32,010 A my sme si povedali, že zdieľať YouTube klip pre teba, keby sa nám podarilo otočiť až 80 00:03:32,010 --> 00:03:32,950 hlasitosť. 81 00:03:32,950 --> 00:03:39,360 >> [PLAYBACK] 82 00:03:39,360 --> 00:03:44,620 >> -Teraz, senátor, ste tu na Google, a ja som rád, že predsedníctvo 83 00:03:44,620 --> 00:03:46,042 ako pohovoru. 84 00:03:46,042 --> 00:03:47,770 >> [Smiech] 85 00:03:47,770 --> 00:03:50,800 >> -Teraz je to ťažké sa dostať práce ako prezident. 86 00:03:50,800 --> 00:03:52,480 A ty teraz prechádzaš stuhnutosť teraz. 87 00:03:52,480 --> 00:03:54,330 Je to tiež ťažké získať prácu v Google. 88 00:03:54,330 --> 00:03:59,610 Máme na otázky a pýtame Naši kandidáti otázky. 89 00:03:59,610 --> 00:04:02,250 A toto je od Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Smiech] 91 00:04:05,325 --> 00:04:06,400 -Myslíte si, že si robím srandu? 92 00:04:06,400 --> 00:04:08,750 Je to tu. 93 00:04:08,750 --> 00:04:12,110 Aký je najúčinnejší spôsob, ako zoradiť milión dve bit celé číslo? 94 00:04:12,110 --> 00:04:15,810 >> [Smiech] 95 00:04:15,810 --> 00:04:18,260 >> -No, uh - 96 00:04:18,260 --> 00:04:19,029 >> Je mi ľúto. 97 00:04:19,029 --> 00:04:19,745 Možno, že by sme mali - 98 00:04:19,745 --> 00:04:21,000 >> Nie, nie, nie, nie, nie. 99 00:04:21,000 --> 00:04:21,470 >> -To nie je - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Myslím, že bublina druhu by je zlý spôsob, ako ísť. 102 00:04:25,328 --> 00:04:26,792 >> [Smiech] 103 00:04:26,792 --> 00:04:28,510 >> [Fandenie a potlesk] 104 00:04:28,510 --> 00:04:31,211 >> -No tak, kto mu to? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [END PLAYBACK] 107 00:04:33,350 --> 00:04:35,070 >> DAVID Malan: Tak tu to máte. 108 00:04:35,070 --> 00:04:39,600 Takže sme začali kvantifikovať beh krát, aby som tak povedal, s niečím 109 00:04:39,600 --> 00:04:43,480 tzv asymptotickej notácie, ktorá je len s odkazom na náš druh sústruženie 110 00:04:43,480 --> 00:04:47,420 slepé oko k tým menším faktorov a len pri pohľade na dobu prevádzky, 111 00:04:47,420 --> 00:04:51,250 výkon týchto algoritmov, ako n dostane naozaj veľký v priebehu času. 112 00:04:51,250 --> 00:04:55,110 A tak sme zaviedli veľký O. a veľký O predstavoval niečo, čo sme si mysleli, 113 00:04:55,110 --> 00:04:57,000 ako horná hranica. 114 00:04:57,000 --> 00:04:59,570 A skutočne, Barry, môžeme znížiť než mic trochu? 115 00:04:59,570 --> 00:05:01,040 >> Mysleli sme si, ze je to horná hranica. 116 00:05:01,040 --> 00:05:04,710 Tak veľký O prostriedkov n mocnín, že najhorší prípad, niečo ako 117 00:05:04,710 --> 00:05:07,780 Výber sort by sa n štvorcová kroky. 118 00:05:07,780 --> 00:05:10,310 Alebo niečo podobné vloženie druhu by n na druhú kroky. 119 00:05:10,310 --> 00:05:15,150 Teraz niečo ako vloženie sort, čo bolo najhoršie? 120 00:05:15,150 --> 00:05:18,200 Vzhľadom k tomu, pole, čo je to najhoršie možný scenár, že by ste mohli nájsť 121 00:05:18,200 --> 00:05:20,650 sám tvárou v tvár? 122 00:05:20,650 --> 00:05:21,860 >> Je to úplne obrátene, nie? 123 00:05:21,860 --> 00:05:24,530 Pretože ak je to úplne dozadu, čo musíte urobiť veľa práce. 124 00:05:24,530 --> 00:05:26,420 Pretože ak ste úplne dozadu, budete si 125 00:05:26,420 --> 00:05:28,840 najväčšia prvkom je tu, a to aj keď patrí tam. 126 00:05:28,840 --> 00:05:31,140 Takže sa chystáte povedať, jo, na tento okamih v čase, patríte sem, 127 00:05:31,140 --> 00:05:32,310 takže nechať to byť. 128 00:05:32,310 --> 00:05:35,425 >> Potom si uvedomíte, oh, sakra, musím presunúť o niečo menšie element 129 00:05:35,425 --> 00:05:36,470 naľavo od vás. 130 00:05:36,470 --> 00:05:38,770 Potom som to robiť znova a znova a znova. 131 00:05:38,770 --> 00:05:41,410 A keď som išiel tam a späť, je by sa nejako cítiť výkon 132 00:05:41,410 --> 00:05:45,540 že algoritmus, pretože stále som miešanie všetci ostatní v 133 00:05:45,540 --> 00:05:46,510 pole, aby sa priestor pre to. 134 00:05:46,510 --> 00:05:47,750 Tak to je najhoršie. 135 00:05:47,750 --> 00:05:48,570 >> Naproti tomu - 136 00:05:48,570 --> 00:05:50,320 a to bol Cliffhanger poslednej dobe - 137 00:05:50,320 --> 00:05:54,065 sme si povedali, že vloženie triedenie bola omega čoho? 138 00:05:54,065 --> 00:05:57,530 Aký je najlepší-case beh čas vloženia druhu? 139 00:05:57,530 --> 00:05:58,520 Takže je to vlastne n 140 00:05:58,520 --> 00:06:00,980 To bol prázdny, že sme opustili na doske naposledy. 141 00:06:00,980 --> 00:06:03,160 >> A je to omega n, pretože prečo? 142 00:06:03,160 --> 00:06:06,630 No, v tom najlepšom prípade to, čo je vloženie triedenie bude odovzdaná? 143 00:06:06,630 --> 00:06:09,830 No, zoznam, ktorý je úplne radené už minimálnu prácu robiť. 144 00:06:09,830 --> 00:06:12,460 Ale to, čo je pekné o vloženie druhu je to, že z dôvodu, že tu začína a 145 00:06:12,460 --> 00:06:15,340 rozhodne, oh, ty si číslo jeden, patríš sem. 146 00:06:15,340 --> 00:06:16,970 Ach, to je šťastie. 147 00:06:16,970 --> 00:06:17,740 >> Ty si číslo dva. 148 00:06:17,740 --> 00:06:19,030 Tiež sem patrí. 149 00:06:19,030 --> 00:06:21,010 Číslo tri, ešte lepšie, Patríš sem. 150 00:06:21,010 --> 00:06:25,210 Akonáhle sa dostane na koniec Zoznam, na vkladacieho SORT v pseudokódu 151 00:06:25,210 --> 00:06:28,010 že sme prechádzali slovne Minule sa to robí. 152 00:06:28,010 --> 00:06:32,790 Ale výber druhu, naopak, stále robí čo? 153 00:06:32,790 --> 00:06:35,260 >> Ďalej v zozname znova a znova a znova. 154 00:06:35,260 --> 00:06:39,160 Pretože Kľúčovou myšlienkou bolo len akonáhle ste sa pozrel až do 155 00:06:39,160 --> 00:06:42,500 koniec zoznamu si môžete byť istí, že prvok vyberiete bola 156 00:06:42,500 --> 00:06:45,560 v skutočnosti v súčasnej dobe najmenší prvok. 157 00:06:45,560 --> 00:06:48,920 Tak to rôzne mentálne modely koniec up dávať niektoré veľmi reálny svet 158 00:06:48,920 --> 00:06:53,130 rozdiely u nás, ale aj v týchto teoretické asymptotickej rozdiely. 159 00:06:53,130 --> 00:06:56,910 >> Takže len zhrnúť, potom veľký O n štvorcový, videli sme niekoľko takých 160 00:06:56,910 --> 00:06:58,350 algoritmy tak ďaleko. 161 00:06:58,350 --> 00:06:59,580 Veľký O n? 162 00:06:59,580 --> 00:07:02,870 Čo je to algoritmus, ktorý by sa povedať, že veľký O n? 163 00:07:02,870 --> 00:07:06,930 V najhoršom prípade to trvá lineárny počet krokov. 164 00:07:06,930 --> 00:07:07,810 >> OK, lineárne hľadanie. 165 00:07:07,810 --> 00:07:10,470 A v najhoršom prípade, kedy je prvok, ktorý hľadáte, ak 166 00:07:10,470 --> 00:07:12,950 použitie lineárne hľadanie? 167 00:07:12,950 --> 00:07:14,680 >> OK, v najhoršom prípade, to nie je ani tam. 168 00:07:14,680 --> 00:07:17,000 Alebo v druhom najhoršom prípade je to úplne na konci, ktorý je 169 00:07:17,000 --> 00:07:18,880 plus alebo mínus jeden krok rozdiel. 170 00:07:18,880 --> 00:07:21,180 Takže na konci dňa, môžeme povedať, že je lineárna. 171 00:07:21,180 --> 00:07:23,910 Veľký O n by byť lineárne vyhľadávanie, preto, že v najhoršom prípade, 172 00:07:23,910 --> 00:07:26,610 prvok nie je to ani tam, alebo je to úplne na konci. 173 00:07:26,610 --> 00:07:29,370 >> No, veľký O log n 174 00:07:29,370 --> 00:07:32,760 Nehovorili sme veľmi podrobne o , Ale my sme videli predtým. 175 00:07:32,760 --> 00:07:36,840 Čo prebieha v tzv logaritmický čas, v najhoršom prípade? 176 00:07:36,840 --> 00:07:38,500 >> Jo, binárne vyhľadávanie. 177 00:07:38,500 --> 00:07:42,930 A binárne hľadanie v najhoršom prípade môže mať prvok niekde 178 00:07:42,930 --> 00:07:45,640 stredná, alebo niekde vnútri poľa. 179 00:07:45,640 --> 00:07:48,040 Ale nájdete len raz vás rozdeliť zoznam na polovicu, v roku 180 00:07:48,040 --> 00:07:48,940 polovice, na polovicu, na polovicu. 181 00:07:48,940 --> 00:07:50,200 A potom ajhľa, je to tam. 182 00:07:50,200 --> 00:07:52,500 Alebo znovu, v najhoršom prípade, to nie je ani tam. 183 00:07:52,500 --> 00:07:56,770 Ale vy neviete, že to tam nie je kým sa nejako dostať, že posledný 184 00:07:56,770 --> 00:08:00,470 zdola väčšina prvkov podľa polovicu a polovicu a znížiť. 185 00:08:00,470 --> 00:08:01,400 >> Veľký O z 1. 186 00:08:01,400 --> 00:08:03,540 Tak by sme mohli o veľký O 2, O 3 veľké. 187 00:08:03,540 --> 00:08:06,260 Kedykoľvek budete chcieť len konštantný počet, sme tak nejako jednoducho zjednodušiť 188 00:08:06,260 --> 00:08:07,280 že tak veľkú O. 1. 189 00:08:07,280 --> 00:08:10,440 Aj keď, ak realisticky, je potreba 2, alebo dokonca 100 stupňov, ak je to 190 00:08:10,440 --> 00:08:13,680 konštantný počet krokov, povieme veľký O z 1. 191 00:08:13,680 --> 00:08:15,930 Čo je to algoritmus, ktorý je vo veľkom O. 1? 192 00:08:15,930 --> 00:08:18,350 >> DIVÁKOV: Hľadanie dĺžku premenné. 193 00:08:18,350 --> 00:08:21,090 >> DAVID Malan: Hľadanie dĺžka premenné? 194 00:08:21,090 --> 00:08:23,870 >> DIVÁKOV: Nie, dĺžka ak už je zoradený. 195 00:08:23,870 --> 00:08:24,160 >> DAVID Malan: Dobrý. 196 00:08:24,160 --> 00:08:27,850 OK, takže nájsť dĺžku niečo v prípade, že dĺžka tohto niečoho, ako je 197 00:08:27,850 --> 00:08:30,020 pole, je uložený v nejakej premennej. 198 00:08:30,020 --> 00:08:33,380 Pretože môžete len čítať premennú, alebo vytlačiť premennú alebo 199 00:08:33,380 --> 00:08:34,960 len všeobecne prístup k tejto premennej. 200 00:08:34,960 --> 00:08:37,299 A voila, že trvá konštantný čas. 201 00:08:37,299 --> 00:08:38,909 >> Naopak, myslím, že späť do nuly. 202 00:08:38,909 --> 00:08:42,460 Spomeňte si na prvý týždeň v C, volanie len printf a tlač 203 00:08:42,460 --> 00:08:46,240 niečo na obrazovke, je pravdepodobne konštantný čas, pretože to jednoducho trvá 204 00:08:46,240 --> 00:08:50,880 určitý počet CPU cyklov ukázať tento text na obrazovke. 205 00:08:50,880 --> 00:08:52,720 Alebo čakať - je to tak? 206 00:08:52,720 --> 00:08:56,430 Ako inak by sme mohli modelovať výkon printf? 207 00:08:56,430 --> 00:09:00,420 By niekto chcel nesúhlasiť, že Možno to naozaj nie je konštantný čas? 208 00:09:00,420 --> 00:09:03,600 V akom zmysle by printf beží čas, v skutočnosti tlačí reťazec na 209 00:09:03,600 --> 00:09:05,580 na obrazovke, bude niečo iné ako konštantný. 210 00:09:05,580 --> 00:09:07,860 >> DIVÁKOV: [nepočuteľné]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID Malan: Jo. 212 00:09:08,230 --> 00:09:09,300 Takže to závisí na našej perspektíve. 213 00:09:09,300 --> 00:09:13,390 Ak sme vlastne myslieť na vstup do printf ako reťazec, a 214 00:09:13,390 --> 00:09:16,380 Preto meriame veľkosť, ktorá Vstup jeho dĺžkou - tak hovorme 215 00:09:16,380 --> 00:09:17,780 že dĺžka n i - 216 00:09:17,780 --> 00:09:21,990 pravdepodobne, printf je samo o sebe veľký O n , Pretože to bude trvať n kroky 217 00:09:21,990 --> 00:09:24,750 tlačiť každý z týchto n znaky, s najväčšou pravdepodobnosťou. 218 00:09:24,750 --> 00:09:27,730 Aspoň do tej miery, že predpokladáme, že možno to pomocou slučky for 219 00:09:27,730 --> 00:09:28,560 pod kapotou. 220 00:09:28,560 --> 00:09:30,860 >> Ale budeme musieť pozrieť na to kód pochopiť lepšie. 221 00:09:30,860 --> 00:09:33,650 A skutočne, akonáhle ste začať analyzovať svoje vlastné algoritmy, budete 222 00:09:33,650 --> 00:09:34,900 doslova robiť len to. 223 00:09:34,900 --> 00:09:37,765 Druh oka kódu a myslím, o - v poriadku, mám túto slučku 224 00:09:37,765 --> 00:09:41,870 tu alebo mám vnorené slučky tu že bude robiť veci n n-krát, 225 00:09:41,870 --> 00:09:46,050 a môžete zoradiť rozumu cestu prostredníctvom kódu, aj keď je to 226 00:09:46,050 --> 00:09:47,980 pseudokódu, a nie skutočný kód. 227 00:09:47,980 --> 00:09:49,730 >> A čo omega-n na druhú? 228 00:09:49,730 --> 00:09:53,582 Čo bol algoritmus, ktorý v najlepšom prípad, trvalo ešte n na druhú kroky? 229 00:09:53,582 --> 00:09:54,014 Jo? 230 00:09:54,014 --> 00:09:54,880 >> DIVÁKOV: [nepočuteľné]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID Malan: Takže výber sort. 232 00:09:55,900 --> 00:09:59,150 Vzhľadom k tomu, v tomto probléme veľmi znížená k tomu, že opäť neviem 233 00:09:59,150 --> 00:10:02,600 Našiel som najmenší prúd, kým Skontroloval som všetky čertovsky prvky. 234 00:10:02,600 --> 00:10:08,050 Tak omega, povedzme, n, sú Prišiel s jedným. 235 00:10:08,050 --> 00:10:09,300 Vloženie sort. 236 00:10:09,300 --> 00:10:12,370 Keď je zoznam sa stane byť radené už v najlepšom prípade budeme musieť 237 00:10:12,370 --> 00:10:15,090 aby jeden priechod cez to, na ktorom mieste sme si istí. 238 00:10:15,090 --> 00:10:17,890 A potom by sa dalo povedať byť lineárne, pre istotu. 239 00:10:17,890 --> 00:10:20,570 >> Čo je Omega 1? 240 00:10:20,570 --> 00:10:23,790 Čo, v najlepšom prípade, môže trvať konštantný počet krokov? 241 00:10:23,790 --> 00:10:27,220 Takže lineárne vyhľadávanie, ak ste práve šťastie a prvok, ktorý hľadáte 242 00:10:27,220 --> 00:10:31,000 je hneď na začiatku zoznamu, či je to to, kam spustenie 243 00:10:31,000 --> 00:10:33,070 lineárny priechod z tohto zoznamu. 244 00:10:33,070 --> 00:10:35,180 >> A to je pravda rad vecí. 245 00:10:35,180 --> 00:10:37,660 Napríklad, aj binárne hľadanie omegou 1. 246 00:10:37,660 --> 00:10:40,310 Pretože čo ak naozaj čertovsky šťastie a plácnutí DAB uprostred 247 00:10:40,310 --> 00:10:42,950 vaša pole je číslo ste hľadali? 248 00:10:42,950 --> 00:10:45,730 Takže môžete mať šťastie tam, rovnako. 249 00:10:45,730 --> 00:10:49,190 >> Ten konečne, omega n log n 250 00:10:49,190 --> 00:10:52,573 Tak n log n, my sme naozaj hovoriť o tom, ešte nie, ale - 251 00:10:52,573 --> 00:10:53,300 >> DIVÁKOV: Zlúčiť druh? 252 00:10:53,300 --> 00:10:53,960 >> DAVID Malan: Merge sort. 253 00:10:53,960 --> 00:10:56,920 To bol Cliffhanger poslednej dobe, kde sme navrhli, a ukázali sme 254 00:10:56,920 --> 00:10:58,600 vizuálne, že existujú algoritmy. 255 00:10:58,600 --> 00:11:02,470 A zlúčiť druh len jeden taký algoritmus, ktorý je v podstate rýchlejší 256 00:11:02,470 --> 00:11:03,450 ako niektoré z týchto ostatných chalanov. 257 00:11:03,450 --> 00:11:07,800 V skutočnosti, je krátky spojiť nielen najlepšom prípade n log n, v najhoršom 258 00:11:07,800 --> 00:11:09,460 Prípad n log n 259 00:11:09,460 --> 00:11:14,540 A keď máte túto koincidencii omega a veľké O je to isté? 260 00:11:14,540 --> 00:11:17,310 Môžeme vlastne popisovať to ako to, čo je tzv theta, keď je to 261 00:11:17,310 --> 00:11:18,220 trochu menej časté. 262 00:11:18,220 --> 00:11:21,730 Ale to znamená len dve medze, V tomto prípade, sú rovnaké. 263 00:11:21,730 --> 00:11:25,770 >> Takže zlúčiť druh, čo to Naozaj sa redukuje na pre nás? 264 00:11:25,770 --> 00:11:27,000 No, spomínam motiváciu. 265 00:11:27,000 --> 00:11:30,340 Dovoľte mi, aby som vytiahnuť ďalšie animáciu, ktorá sme sa nepozeral na minule. 266 00:11:30,340 --> 00:11:33,390 Ten, rovnaký nápad, ale je to trochu väčšie. 267 00:11:33,390 --> 00:11:36,160 A ja idem ďalej a poukázať na Prvý - máme kurzor na druh 268 00:11:36,160 --> 00:11:39,410 vľavo hore, potom výber triedenie, bublina triedenie, pár ďalších druhov - 269 00:11:39,410 --> 00:11:42,670 shell a rýchlo - že sme spolu nehovorili o, a halda a zlúčiť druh. 270 00:11:42,670 --> 00:11:47,090 >> Tak sa aspoň pokúsiť zamerať svoj pohľad na prvé tri vľavo a potom 271 00:11:47,090 --> 00:11:49,120 zlúčiť druh, keď kliknem táto zelená šípka. 272 00:11:49,120 --> 00:11:51,900 Ale nechám všetky z nich spustiť, len aby dá vám pocit rozmanitosti 273 00:11:51,900 --> 00:11:53,980 algoritmy, ktoré existujú vo svete. 274 00:11:53,980 --> 00:11:56,180 Chystám sa nechať to plynúť len na pár sekúnd. 275 00:11:56,180 --> 00:11:59,640 A ak sa sústredíte vaše oči - vyberte si algoritmus, sústrediť sa na to len za 276 00:11:59,640 --> 00:12:02,970 sekúnd - Začnete vidieť vzor, ​​ktorý to vykonáva. 277 00:12:02,970 --> 00:12:04,530 >> Merge sort, oznámenia, je hotovo. 278 00:12:04,530 --> 00:12:06,430 Heap sort, Quick sort, shell - 279 00:12:06,430 --> 00:12:09,480 takže sa zdá, sme predstavili tri najhoršie algoritmy minulý týždeň. 280 00:12:09,480 --> 00:12:12,960 Ale to je dobre, že sme tu dnes sa na druhu korešpondencie, ktorý je jedným z 281 00:12:12,960 --> 00:12:16,500 koncentrácia je ľahšie je pozrieť sa na, a to aj aj keď to asi bude ohýbať vaša myseľ 282 00:12:16,500 --> 00:12:17,490 len trochu. 283 00:12:17,490 --> 00:12:21,130 Tu môžeme vidieť, ako moc Výber trochu naštve. 284 00:12:21,130 --> 00:12:24,600 >> Ale na druhú stranu, je to veľmi ľahko implementovať. 285 00:12:24,600 --> 00:12:28,160 A možno pre sadu P 3, to je jedna z algoritmy ste sa rozhodli realizovať 286 00:12:28,160 --> 00:12:28,960 pre štandardnú verziu. 287 00:12:28,960 --> 00:12:30,970 Úplne v poriadku, úplne správne. 288 00:12:30,970 --> 00:12:35,210 >> Ale opäť, ako n sa zväčší, ak sa možnosť vykonať rýchlejší algoritmus 289 00:12:35,210 --> 00:12:39,020 chcel zlúčiť druh, šance sú väčšie a väčšie vstupy, váš kód je len 290 00:12:39,020 --> 00:12:39,800 bude bežať rýchlejšie. 291 00:12:39,800 --> 00:12:41,090 Váš web bude fungovať lepšie. 292 00:12:41,090 --> 00:12:42,650 Vaši užívatelia sa bude šťastnejší. 293 00:12:42,650 --> 00:12:45,280 A tak sú tieto účinky skutočne dáva 294 00:12:45,280 --> 00:12:47,350 nám niektoré hlbšie myšlienka. 295 00:12:47,350 --> 00:12:49,990 >> Takže poďme sa pozrieť na to, čo zlúčiť Triedenie je vlastne všetko okolo. 296 00:12:49,990 --> 00:12:52,992 Super vec je, že zlúčenie Triedenie je práve tento. 297 00:12:52,992 --> 00:12:56,300 To je opäť to, čo sme tzv pseudokódu, pseudokódu bytosť 298 00:12:56,300 --> 00:12:57,720 Angličtina-ako syntax. 299 00:12:57,720 --> 00:12:59,890 A jednoduchosť je druh fascinujúce. 300 00:12:59,890 --> 00:13:02,840 >> Takže na vstupe n prvkov - tak, že jednoducho znamená, tu je pole. 301 00:13:02,840 --> 00:13:04,000 Je tu n veci v ňom. 302 00:13:04,000 --> 00:13:05,370 To je všetko, čo hovoríme tam. 303 00:13:05,370 --> 00:13:07,560 >> Ak je n menšie ako 2, vrátiť. 304 00:13:07,560 --> 00:13:08,640 Tak to je len triviálne prípad. 305 00:13:08,640 --> 00:13:12,580 Ak je n menšie ako 2, potom samozrejme je to 1 alebo 0, v tomto prípade ide o to 306 00:13:12,580 --> 00:13:14,780 už je zoradený alebo neexistujúce, takže stačí vrátiť. 307 00:13:14,780 --> 00:13:15,900 Nie je nič robiť. 308 00:13:15,900 --> 00:13:18,360 Takže je to jednoduchý prípad trhať off. 309 00:13:18,360 --> 00:13:20,110 >> Inak máme tri kroky. 310 00:13:20,110 --> 00:13:23,650 Radenie ľavú polovicu prvkov, triedenie pravá polovica prvkov, 311 00:13:23,650 --> 00:13:26,650 a potom zlúčiť zoradené polovice. 312 00:13:26,650 --> 00:13:29,400 Čo je zaujímavé je to, že Som trochu plaviť, že jo? 313 00:13:29,400 --> 00:13:32,300 Je to niečo ako definícia v kruhu do tohto algoritmu. 314 00:13:32,300 --> 00:13:35,986 V akom zmysle je tento algoritmus je definícia kruhové? 315 00:13:35,986 --> 00:13:37,850 >> DIVÁKOV: [nepočuteľné]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID Malan: Jo, môj algoritmus triedenia, dvaja z jeho kroky sú "druh 317 00:13:41,670 --> 00:13:44,640 niečo. "A tak to pozdáva otázka, no, čo budem používať 318 00:13:44,640 --> 00:13:46,460 triediť ľavú polovicu aj pravá polovica? 319 00:13:46,460 --> 00:13:49,600 A najlepšie je, že aj keď Znovu, toto je myseľ-ohýbanie 320 00:13:49,600 --> 00:13:54,030 časť potenciálne, môžete použiť rovnaké algoritmus pre triedenie ľavú polovicu. 321 00:13:54,030 --> 00:13:54,700 >> Ale počkajte chvíľku. 322 00:13:54,700 --> 00:13:57,070 Keď ste povedal, triediť ľavá polovica, čo sú dva 323 00:13:57,070 --> 00:13:58,240 kroky bude ďalej? 324 00:13:58,240 --> 00:14:00,550 Vyriešime ľavú polovicu ľavá polovica a právo 325 00:14:00,550 --> 00:14:01,420 polovica ľavej polovici. 326 00:14:01,420 --> 00:14:04,430 Sakra, ako to mám vyriešiť tie dva Polovičky alebo štvrtiny, teraz? 327 00:14:04,430 --> 00:14:05,260 >> Ale to je v poriadku. 328 00:14:05,260 --> 00:14:07,830 Máme triediace algoritmus tu. 329 00:14:07,830 --> 00:14:10,660 A aj keď by ste mohli starať vôbec Spočiatku to tak trochu nekonečný 330 00:14:10,660 --> 00:14:12,780 slučky, je to cyklus, ktorý nikdy skončí - to bude 331 00:14:12,780 --> 00:14:15,770 koniec raz, čo sa stane? 332 00:14:15,770 --> 00:14:16,970 Akonáhle n je menej ako 2. 333 00:14:16,970 --> 00:14:19,180 Ktorý nakoniec sa stane, pretože ak budete mať na polovicu a 334 00:14:19,180 --> 00:14:23,020 znížiť na polovicu týchto polovíc, určite nakoniec sa chystáte na koniec 335 00:14:23,020 --> 00:14:25,350 s len 1 alebo 0 prvkov. 336 00:14:25,350 --> 00:14:28,500 V tom okamihu, tento algoritmus hovorí, že je hotovo. 337 00:14:28,500 --> 00:14:31,020 >> Takže mágie v tejto algoritmus sa zdá byť v 338 00:14:31,020 --> 00:14:33,470 že posledný krok, zlučovanie. 339 00:14:33,470 --> 00:14:37,190 To jednoduchá myšlienka len zlúčenie dvoch veci, to je to, čo nakoniec bude 340 00:14:37,190 --> 00:14:40,920 ktoré nám umožnia vyriešiť rad, povedzme, osem prvkov. 341 00:14:40,920 --> 00:14:44,410 Takže mám ďalších osem stresovej loptičky tu osem kúsky papiera, a jeden 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 ktoré som sa udržať. 344 00:14:46,140 --> 00:14:46,960 >> [Smiech] 345 00:14:46,960 --> 00:14:48,970 >> DAVID Malan: Keby sme mohli mať osem dobrovoľníkov, a uvidíme, či to pôjde 346 00:14:48,970 --> 00:14:51,430 hrať sa na to, tak. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Počítačová veda je stále baviť. 349 00:14:53,565 --> 00:14:54,320 Dobrá. 350 00:14:54,320 --> 00:14:57,770 Tak čo vy traja, Najväčšia ruka hore. 351 00:14:57,770 --> 00:14:58,580 Štyri v chrbte. 352 00:14:58,580 --> 00:15:02,220 A čo budeme robiť vás tri v tejto rade? 353 00:15:02,220 --> 00:15:03,390 A štyri v prednej časti. 354 00:15:03,390 --> 00:15:04,920 Takže si osem, ísť hore. 355 00:15:04,920 --> 00:15:12,060 >> [Smiech] 356 00:15:12,060 --> 00:15:13,450 >> DAVID Malan: V skutočnosti som nie ste istí, čo to je. 357 00:15:13,450 --> 00:15:14,810 Je to stresové gule? 358 00:15:14,810 --> 00:15:16,510 Na stolové lampy? 359 00:15:16,510 --> 00:15:18,650 Materiál? 360 00:15:18,650 --> 00:15:19,680 Internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Tak poď hore. 363 00:15:21,310 --> 00:15:22,310 Kto by chcel - 364 00:15:22,310 --> 00:15:23,570 udržať prichádza. 365 00:15:23,570 --> 00:15:24,240 Poďme sa pozrieť. 366 00:15:24,240 --> 00:15:26,460 A to vám dáva lokalite - 367 00:15:26,460 --> 00:15:27,940 ste na mieste jeden. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, počkaj. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - Oh, dobre. 370 00:15:30,760 --> 00:15:31,310 Tak jo, sme v pohode. 371 00:15:31,310 --> 00:15:35,130 Dobre, takže všetci majú sídlo, ale nie na sklo Google. 372 00:15:35,130 --> 00:15:36,475 Dovoľte mi, aby som do fronty tieto hore. 373 00:15:36,475 --> 00:15:37,115 Ako sa voláte? 374 00:15:37,115 --> 00:15:37,440 >> Michelle Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID Malan: Michelle? 376 00:15:38,090 --> 00:15:42,000 V poriadku, dostanete vyzerať geek, či je to OK. 377 00:15:42,000 --> 00:15:44,625 No, ja tiež, myslím, len na chvíľu. 378 00:15:44,625 --> 00:15:45,875 Dobre, v pohotovostnom režime. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Snažili sme sa prísť s prípad použitia pre Google skla a my 381 00:15:50,950 --> 00:15:53,750 si myslel, že by bolo zábavné sa jednoducho to keď sú ľudia na javisku. 382 00:15:53,750 --> 00:15:57,120 Budeme zaznamenávať svet z ich pohľadu. 383 00:15:57,120 --> 00:15:58,410 Dobrá. 384 00:15:58,410 --> 00:15:59,830 Nie je asi to, čo Google určený. 385 00:15:59,830 --> 00:16:02,260 Dobre, ak vám nevadí, že na sebe na dobu najbližších nepríjemných minút, 386 00:16:02,260 --> 00:16:03,150 že by bolo báječné. 387 00:16:03,150 --> 00:16:08,620 >> Dobre, takže tu máme rad prvky, a že pole, podľa 388 00:16:08,620 --> 00:16:11,480 kúsky papiera v týchto ľuďoch " ruky, je v súčasnej dobe netriedený. 389 00:16:11,480 --> 00:16:12,050 >> Michelle: Oh, to je tak divné. 390 00:16:12,050 --> 00:16:12,810 >> DAVID Malan: Je to do značnej miery náhodné. 391 00:16:12,810 --> 00:16:15,760 A za chvíľu sa budeme snažiť realizovať zlúčiť dohromady akúsi 392 00:16:15,760 --> 00:16:17,950 a zistiť, kde ten kľúč je vhľad. 393 00:16:17,950 --> 00:16:21,970 A trik tu sa druhu korešpondencia je niečo, čo sme sa doteraz predpokladalo. 394 00:16:21,970 --> 00:16:24,030 Potrebujeme teda nejaký priestor navyše. 395 00:16:24,030 --> 00:16:26,650 Tak čo to bude najmä Zaujímavé na tom je, že sa jedná 396 00:16:26,650 --> 00:16:29,270 chlapci budú trochu pohybovať bit, pretože budem predpokladať, že 397 00:16:29,270 --> 00:16:31,880 je tam navyše poľa priestoru, povedzme, hneď za nimi. 398 00:16:31,880 --> 00:16:34,570 >> Takže ak sú za ich predsedami, to je sekundárna pole. 399 00:16:34,570 --> 00:16:36,960 Ak ste tu sídlil, to je primárne polia. 400 00:16:36,960 --> 00:16:40,170 Ale to je zdroj, ktorý máme nevyužívajú pákový efekt, tak ďaleko s bublinou 401 00:16:40,170 --> 00:16:42,040 druhu, s výberom druhu, s vkladacie druhu. 402 00:16:42,040 --> 00:16:44,600 Pripomeňme si minulý týždeň, všetci len druh miešané na mieste. 403 00:16:44,600 --> 00:16:46,840 Nemali používať žiadnu ďalšiu pamäť. 404 00:16:46,840 --> 00:16:49,310 Urobili sme priestor pre ľudí tým, pohybujúce sa ľudia okolo. 405 00:16:49,310 --> 00:16:50,580 >> Tak to je kľúčový vhľad taky. 406 00:16:50,580 --> 00:16:53,410 Tam je to kompromis, všeobecne v výpočtová technika, zdrojov. 407 00:16:53,410 --> 00:16:55,800 Ak chcete urýchliť niečo napríklad čas, budete 408 00:16:55,800 --> 00:16:56,900 musieť zaplatiť cenu. 409 00:16:56,900 --> 00:17:00,750 A jedna z týchto cien je veľmi často priestor, množstvo pamäte alebo pevného 410 00:17:00,750 --> 00:17:01,700 disku, ktorý používate. 411 00:17:01,700 --> 00:17:03,640 Alebo, úprimne povedané, vyššie programátor času. 412 00:17:03,640 --> 00:17:06,700 Ako dlho to trvá vám, človek, skutočne realizovať niektoré ďalšie 413 00:17:06,700 --> 00:17:07,829 komplikovaný algoritmus. 414 00:17:07,829 --> 00:17:09,760 Ale pre dnešok, trade-off je čas a priestor. 415 00:17:09,760 --> 00:17:11,930 >> Takže ak ste mohol len zdvihnúť vaše čísla, takže môžeme vidieť, že ste 416 00:17:11,930 --> 00:17:15,839 skutočne zodpovedajúce 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Výborný. 418 00:17:16,599 --> 00:17:19,520 Takže budem snažiť organizovať veci, ak môže ste práve 419 00:17:19,520 --> 00:17:21,800 za mnou tu. 420 00:17:21,800 --> 00:17:26,650 >> Takže budem realizovať jednak Prvým krokom tohto pseudokódu, ktorý je 421 00:17:26,650 --> 00:17:29,440 na vstupe prvkov n, pokiaľ je n menej ako 2, potom sa vrátiť. 422 00:17:29,440 --> 00:17:31,370 Je zrejmé, že nie je Použiť, takže sme ďalej. 423 00:17:31,370 --> 00:17:33,340 Takže radiť ľavú polovicu prvkov. 424 00:17:33,340 --> 00:17:36,220 Takže to znamená, že budem zamerať svoje pozornosť na chvíľu o týchto 425 00:17:36,220 --> 00:17:37,310 štyri chlapi. 426 00:17:37,310 --> 00:17:39,774 Tak jo, čo mám nabudúce urobiť? 427 00:17:39,774 --> 00:17:40,570 >> DIVÁKOV: Radenie ľavú polovicu. 428 00:17:40,570 --> 00:17:42,780 >> DAVID Malan: Takže teraz musím vyriešiť Ľavá polovica týchto chalanov. 429 00:17:42,780 --> 00:17:45,580 Pretože opäť predpokladajme, že na seba na Cieľom je zoradiť ľavú polovicu. 430 00:17:45,580 --> 00:17:46,440 Ako to robíte, že? 431 00:17:46,440 --> 00:17:49,140 Stačí sledovať inštrukcie, a to aj keď robíme to znova. 432 00:17:49,140 --> 00:17:50,160 Takže radiť ľavú polovicu. 433 00:17:50,160 --> 00:17:52,030 Teraz som triedenie títo dvaja. 434 00:17:52,030 --> 00:17:53,563 Čo bude nasledovať? 435 00:17:53,563 --> 00:17:54,510 >> DIVÁKOV: Radenie ľavú polovicu. 436 00:17:54,510 --> 00:17:55,460 >> DAVID Malan: Radenie ľavú polovicu. 437 00:17:55,460 --> 00:18:00,680 Takže teraz ty, toto sedadlo tu je zoznam veľkosti 1. 438 00:18:00,680 --> 00:18:01,365 A čo že sa to voláš? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Princess Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID Malan: Princezná Daisy je tu. 441 00:18:03,690 --> 00:18:07,470 A tak už je zoradený, pretože Zoznam je veľkosti 1. 442 00:18:07,470 --> 00:18:09,490 Čo mám robiť ďalšie? 443 00:18:09,490 --> 00:18:13,680 OK, návrat, pretože tento zoznam je veľkosť 1, ktorý je menší ako 2. 444 00:18:13,680 --> 00:18:14,320 Tak čo je ďalší krok? 445 00:18:14,320 --> 00:18:17,490 A teraz ste si na druh ustúpiť vo vašej mysli. 446 00:18:17,490 --> 00:18:19,340 >> Radenie pravú polovicu, čo je - 447 00:18:19,340 --> 00:18:19,570 Ako sa voláte? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID Malan: Linda. 450 00:18:20,980 --> 00:18:23,210 A tak to, čo budeme robiť teraz, máme zoznam o veľkosti 1? 451 00:18:23,210 --> 00:18:24,440 >> DIVÁKOV: Návrat. 452 00:18:24,440 --> 00:18:24,760 >> DAVID Malan: Opatrne. 453 00:18:24,760 --> 00:18:29,540 Vrátime sa prvý, a teraz tretia krok - a keď som sa trochu popísať ju 454 00:18:29,540 --> 00:18:33,490 zahŕňa dve miesta teraz, teraz som majú zlúčiť tieto dva prvky. 455 00:18:33,490 --> 00:18:35,530 Takže teraz bohužiaľ prvky sú mimo prevádzky. 456 00:18:35,530 --> 00:18:39,920 Ale to je miesto, kde proces zlúčenia začína byť presvedčivé. 457 00:18:39,920 --> 00:18:42,410 >> Takže ak ste mohol postaviť len za Okamih, budem ťa potrebujem, v 458 00:18:42,410 --> 00:18:44,170 okamih, krok za svojho kresla. 459 00:18:44,170 --> 00:18:46,480 A ak Linda, pretože 2 je menšie ako 4, prečo nie 460 00:18:46,480 --> 00:18:48,130 Prídete okolo prvej? 461 00:18:48,130 --> 00:18:48,690 Zostaň tam. 462 00:18:48,690 --> 00:18:50,520 Takže Linda, prídete asi prvý. 463 00:18:50,520 --> 00:18:53,820 >> Teraz v skutočnosti, ak je to len pole sme mohli len presunúť ju v reálnom čase 464 00:18:53,820 --> 00:18:55,360 z tohto kresla tomto mieste. 465 00:18:55,360 --> 00:18:57,770 Tak si predstavte, že sa nejaká konštanta počet krokov 1. 466 00:18:57,770 --> 00:18:58,480 A teraz - 467 00:18:58,480 --> 00:19:01,490 ale musíme dať do Na prvom mieste je tu. 468 00:19:01,490 --> 00:19:03,930 >> A teraz, ak by ste mohli prísť okolo, rovnako, budeme 469 00:19:03,930 --> 00:19:06,300 byť v mieste dvoch. 470 00:19:06,300 --> 00:19:09,120 A aj keď to pocit, že je to pričom na chvíľu, čo je pekné je teraz 471 00:19:09,120 --> 00:19:14,710 že ľavá polovica ľavá polovica je teraz radené. 472 00:19:14,710 --> 00:19:18,010 Takže aký bol ďalší krok, keď sme teraz previnúť ďalej v príbehu? 473 00:19:18,010 --> 00:19:18,980 >> Divákov: Pravá polovica. 474 00:19:18,980 --> 00:19:19,900 >> DAVID Malan: Triediť pravú polovicu. 475 00:19:19,900 --> 00:19:21,320 Takže vy musíte urobiť to rovnako. 476 00:19:21,320 --> 00:19:23,510 Takže ak by ste mohli postaviť len na chvíľu? 477 00:19:23,510 --> 00:19:25,192 A Ako sa voláte? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID Malan: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, takže Jess je teraz vľavo polovica pravej polovici. 481 00:19:29,720 --> 00:19:31,400 A tak je zoznam veľkosti 1. 482 00:19:31,400 --> 00:19:32,380 Ona samozrejme radené. 483 00:19:32,380 --> 00:19:33,070 A voláte? 484 00:19:33,070 --> 00:19:33,630 >> Michelle Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID Malan: Michelle je samozrejme Zoznam veľkosti 1. 486 00:19:35,340 --> 00:19:36,050 Už je triediť. 487 00:19:36,050 --> 00:19:38,690 Takže teraz mágia stane, proces zlúčenia. 488 00:19:38,690 --> 00:19:39,790 Takže kto príde ako prvý? 489 00:19:39,790 --> 00:19:41,560 Je zrejmé, Michelle. 490 00:19:41,560 --> 00:19:43,280 Takže ak ste prišiel zadom. 491 00:19:43,280 --> 00:19:47,090 Priestor máme k dispozícii pre ňu teraz je hneď za téhle stoličku tu. 492 00:19:47,090 --> 00:19:51,580 A teraz, keď sa môže vrátiť tiež, teraz máme, aby bolo jasno, dva 493 00:19:51,580 --> 00:19:53,810 polovice, každá o veľkosti 2 - 494 00:19:53,810 --> 00:19:57,090 a len pre zobrazenie jeho záujmu, ak by mohlo byť trochu priestoru - 495 00:19:57,090 --> 00:19:59,780 zostala polovica tu, jeden Pravá polovica tu. 496 00:19:59,780 --> 00:20:01,160 >> Rewind ďalej v príbehu. 497 00:20:01,160 --> 00:20:02,270 Čo krok ďalej? 498 00:20:02,270 --> 00:20:03,030 >> Divákov: Zlúčiť. 499 00:20:03,030 --> 00:20:04,160 >> DAVID Malan: Takže teraz musíme spojiť. 500 00:20:04,160 --> 00:20:07,490 Takže OK, takže teraz, našťastie sme práve uvoľnil štyri stoličky. 501 00:20:07,490 --> 00:20:11,480 Takže sme použili dvakrát toľko pamäte, ale môžeme dať flip-flope medzi 502 00:20:11,480 --> 00:20:12,330 dve polia. 503 00:20:12,330 --> 00:20:14,190 Takže, aké číslo je na prvom mieste? 504 00:20:14,190 --> 00:20:14,850 Takže Michelle, samozrejme. 505 00:20:14,850 --> 00:20:16,680 Tak poď sa okolo seba a vziať vaše sídlo tu. 506 00:20:16,680 --> 00:20:19,120 A potom číslo 2 je zrejme Ďalej, ak ste sem prišiel. 507 00:20:19,120 --> 00:20:21,520 Číslo 4, číslo 6. 508 00:20:21,520 --> 00:20:23,390 A opäť, aj keď je trochu chôdze zapojený, 509 00:20:23,390 --> 00:20:26,010 Naozaj, mohli by stáť okamžite, pohybom jedného - 510 00:20:26,010 --> 00:20:26,880 OK, dobre hral. 511 00:20:26,880 --> 00:20:28,350 >> [Smiech] 512 00:20:28,350 --> 00:20:29,680 >> DAVID Malan: A teraz sme v dobrom stave. 513 00:20:29,680 --> 00:20:34,910 Ľavá polovica celého Vstup bol teraz radené. 514 00:20:34,910 --> 00:20:37,370 Dobre, takže títo ľudia mali Výhodou môjho - 515 00:20:37,370 --> 00:20:40,340 ako to skončí všetky dievčatá na doľava a všetci chlapci na pravej strane? 516 00:20:40,340 --> 00:20:42,450 >> OK, takže chlapci 'sa teraz. 517 00:20:42,450 --> 00:20:44,680 Nebudem vás prevedie tieto kroky. 518 00:20:44,680 --> 00:20:46,550 Uvidíme, či sa nám podarí znovu rovnaký pseudokódu. 519 00:20:46,550 --> 00:20:50,050 Ak chcete ísť dopredu a vstať, a vy, dovoľte mi, aby som vám mikrofón. 520 00:20:50,050 --> 00:20:52,990 Uvidíme, či nemôže replikovať to, čo Jednoducho sme tu na 521 00:20:52,990 --> 00:20:53,880 Druhý koniec zoznamu. 522 00:20:53,880 --> 00:20:59,530 Kto potrebuje hovoriť ako prvý, na základe algoritmu? 523 00:20:59,530 --> 00:21:03,210 Takže vysvetliť, čo robíte, ako vykonáte nohy pohyby. 524 00:21:03,210 --> 00:21:05,930 >> SPEAKER 1: Dobre, takže od tej doby Som Ľavá polovica 525 00:21:05,930 --> 00:21:07,790 ľavá polovica, vrátim. 526 00:21:07,790 --> 00:21:08,730 Je to tak? 527 00:21:08,730 --> 00:21:09,250 >> DAVID Malan: Dobrý. 528 00:21:09,250 --> 00:21:10,350 >> SPEAKER 1: A potom - 529 00:21:10,350 --> 00:21:11,800 >> DAVID Malan: Kto mic ísť ďalej? 530 00:21:11,800 --> 00:21:12,920 >> SPEAKER 1: Ďalšie číslo. 531 00:21:12,920 --> 00:21:14,720 >> SPEAKER 2: Tak som pravá polovica na ľavej polovici 532 00:21:14,720 --> 00:21:17,830 ľavá polovica, a ja som sa vrátiť. 533 00:21:17,830 --> 00:21:18,050 >> DAVID Malan: Dobrý. 534 00:21:18,050 --> 00:21:18,550 Vrátite sa. 535 00:21:18,550 --> 00:21:21,855 Takže teraz, čo je ďalší pre vás dvoch? 536 00:21:21,855 --> 00:21:23,740 >> SPEAKER 2: Chceme zistiť, kto je menšia. 537 00:21:23,740 --> 00:21:24,200 >> DAVID Malan: Presne tak. 538 00:21:24,200 --> 00:21:24,940 Chceme spojiť. 539 00:21:24,940 --> 00:21:27,590 Priestor budeme používať k zlúčeniu vás do, aj keď sú 540 00:21:27,590 --> 00:21:30,250 samozrejme radené už ideme podľa rovnakého algoritmu. 541 00:21:30,250 --> 00:21:31,560 Tak kto ide späť ako prvý? 542 00:21:31,560 --> 00:21:35,720 Takže 3 a potom 7.. 543 00:21:35,720 --> 00:21:38,570 A teraz ide mic na tých chlapov, OK? 544 00:21:38,570 --> 00:21:43,590 >> SPEAKER 3: Takže som pravá polovica ľavá polovica, a moja je n menšie ako 545 00:21:43,590 --> 00:21:45,048 1, takže som len tak prejsť - 546 00:21:45,048 --> 00:21:46,380 >> DAVID Malan: Dobrý. 547 00:21:46,380 --> 00:21:49,450 >> SPEAKER 4: Som pravá polovica pravá polovica pravej polovici, a ja som 548 00:21:49,450 --> 00:21:51,740 tiež jeden človek, takže som chystá k návratu. 549 00:21:51,740 --> 00:21:52,990 Takže teraz sme zlúčiť. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> SPEAKER 3: Tak ideme naspäť. 552 00:21:56,150 --> 00:21:57,160 >> DAVID Malan: Takže idete do chrbta. 553 00:21:57,160 --> 00:21:59,200 Takže 5 ide prvý, a potom 8. 554 00:21:59,200 --> 00:22:01,240 A teraz publikum, čo je krok musíme sa pretočiť 555 00:22:01,240 --> 00:22:02,200 späť v našich mysliach? 556 00:22:02,200 --> 00:22:02,940 >> Divákov: Zlúčiť. 557 00:22:02,940 --> 00:22:07,270 >> DAVID Malan: Zlúčenie ľavej a pravej polovice polovicu pôvodného ľavej polovici. 558 00:22:07,270 --> 00:22:08,840 Takže teraz - 559 00:22:08,840 --> 00:22:10,520 a len preto, aby to bolo jasné, aby trochu priestoru 560 00:22:10,520 --> 00:22:11,690 medzi vami dvaja chlapci. 561 00:22:11,690 --> 00:22:13,800 Takže teraz, že to sú dva zoznamy, doľava a doprava. 562 00:22:13,800 --> 00:22:18,320 Tak ako sme sa spojiť tých ľudí do Predný rad sedadiel znova? 563 00:22:18,320 --> 00:22:19,600 >> 3. ide prvý. 564 00:22:19,600 --> 00:22:20,850 Potom 5, samozrejme. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Potom 7, 8 a teraz. 567 00:22:27,330 --> 00:22:28,710 OK, a teraz sme? 568 00:22:28,710 --> 00:22:29,650 >> Divákov: nerobí. 569 00:22:29,650 --> 00:22:32,440 >> DAVID Malan: Nie je urobil, pretože samozrejme, je tu jeden krok zostáva. 570 00:22:32,440 --> 00:22:35,720 Ale znovu, dôvod, prečo som pomocou tohto žargóne ako "dozadu vo vašej mysli," 571 00:22:35,720 --> 00:22:37,160 je to preto, že je naozaj čo sa deje. 572 00:22:37,160 --> 00:22:39,610 Ideme cez všetky tieto kroky, ale my sme trochu odmlčal 573 00:22:39,610 --> 00:22:42,480 moment, potápanie hlbšie do algoritmus, zastavil sa na okamih, 574 00:22:42,480 --> 00:22:45,840 potápanie hlbšie do algoritmu a teraz musíme nejako dozadu v našom 575 00:22:45,840 --> 00:22:49,430 myseľ a vrátiť späť všetky tieto vrstvy že sme trochu podrží. 576 00:22:49,430 --> 00:22:51,790 >> Takže teraz máme dva zoznamy veľkosti 4. 577 00:22:51,790 --> 00:22:54,790 Ak ste mohol postaviť jeden posledný čas a aby sa trochu priestoru tu 578 00:22:54,790 --> 00:22:57,230 bolo zrejmé, že sa jedná o ľavú polovica z originálu, 579 00:22:57,230 --> 00:22:58,620 Pravá polovica originálu. 580 00:22:58,620 --> 00:23:01,060 Kto je prvé číslo, ktoré sme musí vytiahnuť na zadnej? 581 00:23:01,060 --> 00:23:01,870 Michelle samozrejme. 582 00:23:01,870 --> 00:23:03,230 >> Takže sme dali Michelle tu. 583 00:23:03,230 --> 00:23:05,080 A kto má číslo 2? 584 00:23:05,080 --> 00:23:06,440 Číslo 2 je na zadnej strane rovnako. 585 00:23:06,440 --> 00:23:07,800 Číslo 3? 586 00:23:07,800 --> 00:23:08,510 Výborný. 587 00:23:08,510 --> 00:23:16,570 Č 4, č 5, č 6, číslo 7 a č 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, tak to pripadalo ako veľa krokov, pre istotu. 589 00:23:18,850 --> 00:23:22,390 Ale teraz uvidíme, či nemôžeme potvrdiť, nejako intuitívne, že tento 590 00:23:22,390 --> 00:23:26,190 algoritmus zásadne, najmä pokiaľ n dostane naozaj veľký, ako sme videli 591 00:23:26,190 --> 00:23:29,170 s animáciou, je zásadne rýchlejší. 592 00:23:29,170 --> 00:23:33,400 Takže tvrdím, tento algoritmus, v najhoršom prípad a dokonca v najlepšom prípade, 593 00:23:33,400 --> 00:23:36,160 je veľký O n žurnál n krát. 594 00:23:36,160 --> 00:23:39,160 To znamená, že tam je nejaký aspekt tohto Algoritmus, ktorý má n krokov, ale 595 00:23:39,160 --> 00:23:43,110 je tu ďalší aspekt, niekde že iterácie, že slučky, že 596 00:23:43,110 --> 00:23:44,410 trvá log n krokov. 597 00:23:44,410 --> 00:23:49,154 Môže dáme prst na to, čo tí dve čísla sú na mysli? 598 00:23:49,154 --> 00:23:51,320 No, kde - 599 00:23:51,320 --> 00:23:54,160 Kde mic ísť? 600 00:23:54,160 --> 00:23:58,660 >> Reproduktor 1: Malo by log n je lámanie nás do dvoch - 601 00:23:58,660 --> 00:23:59,630 delenie dvoma, v podstate. 602 00:23:59,630 --> 00:24:00,120 >> DAVID Malan: Presne tak. 603 00:24:00,120 --> 00:24:03,000 Kedykoľvek vidíme v každom algoritme teda Zatiaľ tam bol tento vzor 604 00:24:03,000 --> 00:24:04,200 delenie, delenie, delenie. 605 00:24:04,200 --> 00:24:05,700 A je to typicky znížený na niečo, čo je 606 00:24:05,700 --> 00:24:07,100 logaritmické, log základ 2. 607 00:24:07,100 --> 00:24:10,180 Ale mohlo by to byť naozaj čokoľvek, ale prihlásiť základ 2. 608 00:24:10,180 --> 00:24:11,330 >> Teraz, čo o n? 609 00:24:11,330 --> 00:24:14,550 Vidím, že sme trochu rozdeliť vás chlapci - delí vás delí vás, 610 00:24:14,550 --> 00:24:15,910 delí vás delí vás. 611 00:24:15,910 --> 00:24:18,760 Kde sa koniec pochádza? 612 00:24:18,760 --> 00:24:19,810 >> Takže je to zlúčenie. 613 00:24:19,810 --> 00:24:20,610 Pretože o tom premýšľať. 614 00:24:20,610 --> 00:24:25,420 Pri zlúčení osem ľudí dohromady, pričom polovica z nich je sada štyroch 615 00:24:25,420 --> 00:24:27,770 a druhá polovica sú ďalšie sada štyroch, ako sa vám ísť 616 00:24:27,770 --> 00:24:28,820 o tom zlúčenie? 617 00:24:28,820 --> 00:24:30,830 No, vy ste to urobil pomerne intuitívne. 618 00:24:30,830 --> 00:24:34,140 >> Ale keby som to robil namiesto toho trochu viac metodicky, možno som už uviedol v 619 00:24:34,140 --> 00:24:38,090 vľavo osoba najprv po mojej ľavici ruku, ukázal na ľavom osoby 620 00:24:38,090 --> 00:24:42,080 tejto polovice sa mojej pravici, a len následne prešiel 621 00:24:42,080 --> 00:24:46,990 Zoznam a ukázal na najmenší prvok zakaždým, pohybujúce sa cez môj prst a 622 00:24:46,990 --> 00:24:48,970 viac ako v prípade potreby v celom zozname. 623 00:24:48,970 --> 00:24:51,890 Ale čo je kľúčové o tomto zlúčení proces som porovnanie týchto párov 624 00:24:51,890 --> 00:24:53,460 prvkov. 625 00:24:53,460 --> 00:24:57,270 Z pravej polovice a zľava polovice, som ani raz cúvať. 626 00:24:57,270 --> 00:25:00,570 >> Takže zlúčenie sám je pri nie viac ako n krokov. 627 00:25:00,570 --> 00:25:03,250 A koľkokrát to mám k tomu, že zlúčenie? 628 00:25:03,250 --> 00:25:07,150 No, nie viac ako n, a my sme videl, že s konečnou zlúčenie. 629 00:25:07,150 --> 00:25:13,120 A tak, ak robíte niečo, čo trvá log n krokov n-krát, alebo naopak, 630 00:25:13,120 --> 00:25:15,210 to nám dá n log n krát. 631 00:25:15,210 --> 00:25:16,310 >> A prečo je to lepšie? 632 00:25:16,310 --> 00:25:19,600 No, keď už vieme, že protokol n je lepší ako n - P? 633 00:25:19,600 --> 00:25:22,590 Videli sme v binárnom vyhľadávanie v telefónnom zozname Napríklad log n rozhodne 634 00:25:22,590 --> 00:25:23,760 lepšie ako lineárny. 635 00:25:23,760 --> 00:25:28,420 Tak, že znamená, že n-krát log n je rozhodne lepšie ako n krát iný 636 00:25:28,420 --> 00:25:30,390 n, n AKA druhú. 637 00:25:30,390 --> 00:25:32,400 A to je to, čo sme nakoniec pocit. 638 00:25:32,400 --> 00:25:34,928 >> Tak veľký potlesk, keď Mohli by sme týchto ľudí. 639 00:25:34,928 --> 00:25:38,920 >> [APPLAUSE] 640 00:25:38,920 --> 00:25:41,550 >> DAVID Malan: A vaša rozlúčka darčeky - môžete držať čísla, 641 00:25:41,550 --> 00:25:44,010 ak by ste chceli. 642 00:25:44,010 --> 00:25:45,620 A váš dar na rozlúčku, ako obvykle. 643 00:25:45,620 --> 00:25:47,290 Jo, a my vám radi zašleme zábery, Michelle. 644 00:25:47,290 --> 00:25:48,343 Ďakujem. 645 00:25:48,343 --> 00:25:49,250 Dobrá. 646 00:25:49,250 --> 00:25:50,400 Poslúžte stresu loptu. 647 00:25:50,400 --> 00:25:54,110 >> A dovoľte mi vytiahnuť, do tej doby, náš priateľ Rob Bowden ponúknuť 648 00:25:54,110 --> 00:25:59,520 trochu odlišný pohľad na to, pretože si môžete myslieť o týchto 649 00:25:59,520 --> 00:26:01,280 kroky sa dejú v trochu odlišným spôsobom. 650 00:26:01,280 --> 00:26:04,750 V skutočnosti, set-up, čo Rob je asi aby nám ukázal, predpokladá, že máme 651 00:26:04,750 --> 00:26:09,030 už vykonáva delenie na veľký zoznam do ôsmich menších zoznamov, 652 00:26:09,030 --> 00:26:10,570 každý z veľkosti 1. 653 00:26:10,570 --> 00:26:13,350 >> Takže Meníme pseudokódu trochu, len aby nejako dostať 654 00:26:13,350 --> 00:26:15,320 Základnou myšlienkou, ako sa zlúčenie práce. 655 00:26:15,320 --> 00:26:17,600 Ale doba chodu čo sa chystá urobiť, je stále 656 00:26:17,600 --> 00:26:19,110 bude rovnaká. 657 00:26:19,110 --> 00:26:23,540 A opäť, set-up je, že je začala s ôsmimi zoznamov veľkosti 1. 658 00:26:23,540 --> 00:26:27,730 Takže ste vynechal tú časť, kde je to vlastne urobil log n, log n log n, 659 00:26:27,730 --> 00:26:31,205 delenie vstupu. 660 00:26:31,205 --> 00:26:32,120 >> [PLAYBACK] 661 00:26:32,120 --> 00:26:33,615 >> -A je to pre krok jedna. 662 00:26:33,615 --> 00:26:38,270 Na druhom kroku, a to opakovane spojí dva zoznamy. 663 00:26:38,270 --> 00:26:39,210 >> DAVID Malan: Hm. 664 00:26:39,210 --> 00:26:41,270 Iba zvuk prichádza z môjho počítača. 665 00:26:41,270 --> 00:26:42,520 Skúsme to znova. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Len ľubovoľne vybrať, ktoré - Teraz máme štyri zoznamy. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Naučte predtým. 670 00:26:52,120 --> 00:26:53,040 >> DAVID Malan: Tak ideme. 671 00:26:53,040 --> 00:27:00,510 >> Zlúčenie-108 a 15, sme sa nakoniec s zoznam 15, 108. 672 00:27:00,510 --> 00:27:07,170 Zlúčenie 50 a 4, sa skončiť s 4, 50. 673 00:27:07,170 --> 00:27:12,990 Zlúčenie 8 a 42, sa skončiť s 8, 42. 674 00:27:12,990 --> 00:27:19,970 A zlúčenie 23 a 16, sa skončiť s 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Teraz sú všetky naše zoznamy sú o veľkosti 2. 676 00:27:23,270 --> 00:27:26,690 Všimnite si, že každý z štyri zoznamy sa triedi. 677 00:27:26,690 --> 00:27:29,450 Takže môžeme začať zlúčenie pary opäť kompletný zoznam. 678 00:27:29,450 --> 00:27:38,420 Zlúčenie 15 a 108 a 4 a 50, sa prvá sa na 4, potom 15, potom 679 00:27:38,420 --> 00:27:41,500 50, potom 108. 680 00:27:41,500 --> 00:27:50,610 Zlúčenie 8, 42 a 16, 23, najprv sa 8, potom 16, potom 23, 681 00:27:50,610 --> 00:27:52,700 potom 42. 682 00:27:52,700 --> 00:27:57,600 >> Takže teraz máme len dva zoznamy veľkosti 4, z ktorých každý je triedený. 683 00:27:57,600 --> 00:28:01,170 Takže teraz sme zlúčiť tieto dva zoznamy. 684 00:28:01,170 --> 00:28:11,835 Najprv zoberieme 4, potom sa 8, potom budeme mať 15, potom 16, potom 685 00:28:11,835 --> 00:28:19,456 23, potom 42, potom 50, potom 108. 686 00:28:19,456 --> 00:28:19,872 >> [END PLAYBACK] 687 00:28:19,872 --> 00:28:23,430 >> DAVID Malan: Opäť, oznámenia, nikdy dotkol danej šálka viac ako raz 688 00:28:23,430 --> 00:28:24,860 po postupuje za ňou. 689 00:28:24,860 --> 00:28:26,200 Takže nikdy opakovať. 690 00:28:26,200 --> 00:28:29,850 Takže je vždy v pohybe do strany, a to je, kde sme dostali náš n 691 00:28:29,850 --> 00:28:33,290 >> Prečo nie, dajte mi vytiahnuť jednu animáciu ktoré sme videli predtým, ale tentoraz 692 00:28:33,290 --> 00:28:35,110 zameriava iba na druhu korešpondencie. 693 00:28:35,110 --> 00:28:38,030 Nechaj ma ísť dopredu a zoom do toho tu. 694 00:28:38,030 --> 00:28:42,530 Najprv mi dovoľte, aby som si vybrať náhodný vstup, zväčšiť to, a môžete nejako vidieť 695 00:28:42,530 --> 00:28:46,600 to, čo sme považovali za samozrejmé, skôr, zlúčiť druh skutočne robí. 696 00:28:46,600 --> 00:28:50,330 >> Tak zistíte, že vám tieto polovice alebo Tieto štvrtí alebo tie osminy 697 00:28:50,330 --> 00:28:53,140 problém, ktorý sa z ničoho nič začnú mať dobrú formu. 698 00:28:53,140 --> 00:28:57,070 A nakoniec, uvidíte na veľmi koniec, ktorý bam, 699 00:28:57,070 --> 00:28:58,860 všetko je spojil. 700 00:28:58,860 --> 00:29:01,690 >> Tak to sú len tri rôzne sa na rovnakú myšlienku. 701 00:29:01,690 --> 00:29:05,980 Ale hlavný pohľad, rovnako ako rozdelenie a podmaniť si hneď v prvej triede, 702 00:29:05,980 --> 00:29:10,640 bolo to, že sme sa rozhodli nejako rozdeliť problém do niečoho veľkého, do 703 00:29:10,640 --> 00:29:14,760 niečo trochu identické v duchu, ale menšie a menšie a menšie 704 00:29:14,760 --> 00:29:15,660 a menšie. 705 00:29:15,660 --> 00:29:18,420 >> Teraz ďalší zábavný spôsob, ako nejako myslieť o nich, aj keď to nie je 706 00:29:18,420 --> 00:29:20,520 bude vám rovnako intuitívne porozumenie, je 707 00:29:20,520 --> 00:29:21,640 Nasledujúci animácie. 708 00:29:21,640 --> 00:29:25,400 Tak toto je video niekto dať dohromady aké sú spojené rôzne 709 00:29:25,400 --> 00:29:29,970 zvukov s rôznymi operáciami vloženie druhu, pre druh korešpondencie a 710 00:29:29,970 --> 00:29:31,150 na pár ďalších. 711 00:29:31,150 --> 00:29:32,330 Takže vo chvíli, idem zasiahnuť Play. 712 00:29:32,330 --> 00:29:33,600 Je to asi minútu dlhý. 713 00:29:33,600 --> 00:29:37,410 A aj keď stále môžete vidieť vzory deje, tentoraz si môžete 714 00:29:37,410 --> 00:29:41,420 tiež počuť, ako tieto algoritmy sú vykonávanie odlišne a s 715 00:29:41,420 --> 00:29:43,950 trochu rôzne vzory. 716 00:29:43,950 --> 00:29:45,830 >> To je druh vloženie. 717 00:29:45,830 --> 00:29:50,400 >> [TÓNY PLAYBACK] 718 00:29:50,400 --> 00:29:52,400 >> DAVID Malan: Opäť sa snažia vložiť každý prvok 719 00:29:52,400 --> 00:29:52,900 na tam, kam patrí. 720 00:29:52,900 --> 00:29:54,628 To je bublina druh. 721 00:29:54,628 --> 00:30:10,097 >> [TÓNY PLAYBACK] 722 00:30:10,097 --> 00:30:13,630 >> DAVID Malan: A môžete tak nejako pocit ako relatívne málo práce to robí 723 00:30:13,630 --> 00:30:15,834 na každom kroku. 724 00:30:15,834 --> 00:30:20,470 To je to, čo znie ako nudnost. 725 00:30:20,470 --> 00:30:21,472 >> [TÓNY PLAYBACK] 726 00:30:21,472 --> 00:30:25,222 >> DAVID Malan: Toto je výber druhu, kde vyberte element, ktorý chceme do 727 00:30:25,222 --> 00:30:28,845 prechádza znova a znova a znova a uvedenie na začiatku. 728 00:30:28,845 --> 00:30:37,674 >> [TÓNY PLAYBACK] 729 00:30:37,674 --> 00:30:43,970 >> DAVID Malan: Toto je zlúčiť druh, ktorý môžete naozaj začať cítiť. 730 00:30:43,970 --> 00:30:51,810 >> [TÓNY PLAYBACK] 731 00:30:51,810 --> 00:30:54,770 >> [Smiech] 732 00:30:54,770 --> 00:30:58,395 >> DAVID Malan: Niečo s názvom gnome triedenie, ktoré sme sa pozrel na. 733 00:30:58,395 --> 00:31:13,630 >> [TÓNY PLAYBACK] 734 00:31:13,630 --> 00:31:17,910 >> DAVID Malan: Tak sa ukážte, teraz, roztržitý, ako ste snáď sú vo 735 00:31:17,910 --> 00:31:21,110 hudba, či môžem skĺznuť trochu Trocha matematiky tu. 736 00:31:21,110 --> 00:31:24,850 Takže tam je štvrtý spôsob, ktorý môžeme premýšľať o tom, čo to znamená, že tieto 737 00:31:24,850 --> 00:31:29,210 funkcií, ktoré sú rýchlejšie ako tie že sme nevideli. 738 00:31:29,210 --> 00:31:32,470 A ak idete na kurze od matematika pozadia, môžete 739 00:31:32,470 --> 00:31:36,030 vlastne viete, možno už, že ste môže udrieť termín na tejto technike - 740 00:31:36,030 --> 00:31:40,400 to rekurzia, funkcie že tak nejako volá sama seba. 741 00:31:40,400 --> 00:31:44,780 >> A opäť pripomenúť, že druh korešpondencie pseudokódu bol rekurzívne v tom zmysle, 742 00:31:44,780 --> 00:31:48,460 že jeden z Merge sort v krokoch nazval druh - 743 00:31:48,460 --> 00:31:49,740 to znamená, že sama o sebe. 744 00:31:49,740 --> 00:31:52,480 Ale našťastie, pretože sme si nechali volanie triediť, alebo zlúčiť druh, 745 00:31:52,480 --> 00:31:55,880 špecificky, na menšie a menšie a menšie zoznam, nakoniec sme 746 00:31:55,880 --> 00:32:00,005 dna vďaka, čo budeme nazývať referenčný prípad, pevne platí, že 747 00:32:00,005 --> 00:32:04,270 povedal, že ak je zoznam je malý, menší než 2 V takom prípade si okamžite vráti. 748 00:32:04,270 --> 00:32:07,550 Ak by sme nemali mať tento osobitný prípad, Algoritmus by nikdy dna, 749 00:32:07,550 --> 00:32:11,010 a vy by ste naozaj dostať do nekonečná slučka naozaj navždy. 750 00:32:11,010 --> 00:32:14,330 >> Ale predpokladajme, že sme chceli, aby sa dal niektoré čísla na to, opäť za použitia n 751 00:32:14,330 --> 00:32:15,660 ako veľkosť vstupu. 752 00:32:15,660 --> 00:32:18,680 A chcel som sa vás opýtať, čo je celkový čas zúčastňuje 753 00:32:18,680 --> 00:32:19,800 spustenie hromadnej korešpondencie druh? 754 00:32:19,800 --> 00:32:22,960 Alebo všeobecnejšie, čo je náklady na neho v čase? 755 00:32:22,960 --> 00:32:24,730 >> No, je to celkom jednoduché zmerať to. 756 00:32:24,730 --> 00:32:29,010 Ak je n menšie ako 2, času potrebného pre v triedení n prvkov, 757 00:32:29,010 --> 00:32:30,480 kde n je 2, je 0. 758 00:32:30,480 --> 00:32:31,410 Pretože sme jednoducho vrátiť. 759 00:32:31,410 --> 00:32:32,510 Neexistuje žiadna práce je potrebné urobiť. 760 00:32:32,510 --> 00:32:35,660 Teraz pravdepodobne, možno je to jeden krok alebo dva kroky, aby zistili množstvo 761 00:32:35,660 --> 00:32:38,420 práca, ale je to dosť blízko 0, že Len som chcel povedať, nie práca 762 00:32:38,420 --> 00:32:40,940 vyžaduje chcete zoznam je tak malý, byť nezaujímavé. 763 00:32:40,940 --> 00:32:42,580 >> Ale v tomto prípade je zaujímavé. 764 00:32:42,580 --> 00:32:47,320 Rekurzívne prípad bol odbor pseudokódu, ktorý povedal inde, triedenie 765 00:32:47,320 --> 00:32:52,000 ľavá polovica, triediť právo polovice, zlúčiť dve polovice. 766 00:32:52,000 --> 00:32:55,530 A teraz, prečo sa tento výraz predstavujú, že náklady? 767 00:32:55,530 --> 00:32:58,690 No, T n len znamená, Doba triediť n prvkov. 768 00:32:58,690 --> 00:33:03,070 A potom na pravej strane znamienko rovnosti tam, T n delí 769 00:33:03,070 --> 00:33:06,600 o 2 odkazuje na cenu čo? 770 00:33:06,600 --> 00:33:07,570 Radenie ľavú polovicu. 771 00:33:07,570 --> 00:33:10,990 Druhý T n delené 2 je pravdepodobne sa odkazovať na náklady 772 00:33:10,990 --> 00:33:12,390 zoradiť pravú polovicu. 773 00:33:12,390 --> 00:33:14,590 >> A potom n a? 774 00:33:14,590 --> 00:33:15,420 Je zlúčenie. 775 00:33:15,420 --> 00:33:19,120 Vzhľadom k tomu, ak máte dva zoznamy, jeden z veľkosti n na 2 a ďalšie veľkosti n 776 00:33:19,120 --> 00:33:22,580 viac ako 2, máte v podstate dotýkať každý z týchto prvkov, rovnako ako Rob 777 00:33:22,580 --> 00:33:24,990 dotkol každého z košíčkov, a len ako sme upozornili na každej 778 00:33:24,990 --> 00:33:26,310 Dobrovoľníci na javisku. 779 00:33:26,310 --> 00:33:28,790 Tak n je náklad zlúčenie. 780 00:33:28,790 --> 00:33:31,780 >> Teraz bohužiaľ, tento vzorec je tiež sám rekurzívne. 781 00:33:31,780 --> 00:33:36,390 Takže ak sa pýtal, ak je n je, povedzme, 16, v prípade, že je 16 ľudí na javisku 782 00:33:36,390 --> 00:33:40,670 alebo 16 šálok na video, koľko celkom kroky je potrebné, aby triediť 783 00:33:40,670 --> 00:33:41,550 Pomocou Zoradiť korešpondencie? 784 00:33:41,550 --> 00:33:45,790 Je to vlastne nie je jasná odpoveď, pretože teraz budete musieť nejako 785 00:33:45,790 --> 00:33:48,500 rekurzívne odpovedať na tento vzorec. 786 00:33:48,500 --> 00:33:51,190 >> Ale to je v poriadku, pretože mi dovoľte navrhnúť, čo robíme nasledujúce. 787 00:33:51,190 --> 00:33:56,670 Času potrebného pre triedenie alebo 16 ľudí 16 šálok sa bude zastúpený 788 00:33:56,670 --> 00:33:58,020 všeobecne ako T zo 16.. 789 00:33:58,020 --> 00:34:01,400 Ale to sa rovná, podľa našich predchádzajúci vzorec, 2 násobok sumy 790 00:34:01,400 --> 00:34:04,780 čas potrebný k radeniu 8 šálok plus 16. 791 00:34:04,780 --> 00:34:08,590 A opäť, a 16 je čas spojiť, a dvakrát T z 8. je 792 00:34:08,590 --> 00:34:10,790 Doba triediť ľavú polovicu a pravej polovice. 793 00:34:10,790 --> 00:34:11,989 >> Ale znovu, to nestačí. 794 00:34:11,989 --> 00:34:13,210 Musíme sa do toho ponoriť hlbšie. 795 00:34:13,210 --> 00:34:16,409 To znamená, že musíme odpovedať otázka, čo je t 8? 796 00:34:16,409 --> 00:34:19,610 No T z 8 sa nachádza len 2 Časy T z 4 plus 8. 797 00:34:19,610 --> 00:34:20,520 No, čo sa t 4? 798 00:34:20,520 --> 00:34:23,780 T 4 je len 2 krát T z 2 plus 4. 799 00:34:23,780 --> 00:34:25,489 No, čo je t 2? 800 00:34:25,489 --> 00:34:29,030 T 2 je len 2 krát T z 1 plus 2. 801 00:34:29,030 --> 00:34:31,940 >> A opäť sme trochu dostať uviazol v tomto cykle. 802 00:34:31,940 --> 00:34:34,790 Ale je to o tom, že zasiahnuť tzv referenčný prípad. 803 00:34:34,790 --> 00:34:37,310 Pretože to, čo je t 1, sme sa tvrdí? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Takže teraz konečne môžeme pracovať pospiatky. 806 00:34:39,730 --> 00:34:44,290 >> Je-li T 1 je 0, teraz môžem vrátiť do jedného linky na toho chlapa tu, a môžem 807 00:34:44,290 --> 00:34:46,330 zapojte 0 pre T z 1.. 808 00:34:46,330 --> 00:34:51,770 Takže to znamená, že sa rovná 2 krát nula, inak známy ako 0, + 2. 809 00:34:51,770 --> 00:34:53,739 A tak, že celý výraz je 2.. 810 00:34:53,739 --> 00:34:58,740 >> Teraz, keď som si na T 2, ktorých odpoveď je 2, zapojte ho do prostrednej radu, T 811 00:34:58,740 --> 00:35:02,740 zo 4., že mi dáva 2 krát 2 a 4, tak 8.. 812 00:35:02,740 --> 00:35:07,080 Keď som potom pripojíte 8 na predchádzajúcu linka, ktorá mi dáva 2 krát 8, 16. 813 00:35:07,080 --> 00:35:12,470 A ak budeme pokračovať, že sa 24, tým, že do 16 rokov, sa konečne dostať 814 00:35:12,470 --> 00:35:13,820 hodnota 64. 815 00:35:13,820 --> 00:35:18,480 >> Teraz, keď sám o sebe trochu hovorí nič na zápis n, 816 00:35:18,480 --> 00:35:20,700 veľký O, omega, že máme o tom hovorili. 817 00:35:20,700 --> 00:35:24,890 Ale ukazuje sa, že 64 je naozaj 16, veľkosť vstupu, 818 00:35:24,890 --> 00:35:27,110 prihlásiť základňu 2 16 rokov. 819 00:35:27,110 --> 00:35:30,200 A ak je to trochu neznáma, rovnako spomínať, a to vrátim 820 00:35:30,200 --> 00:35:30,700 vám nakoniec. 821 00:35:30,700 --> 00:35:33,775 Ak je to log základ 2, je to ako 2 zvýšil na to, čo vám dáva 16? 822 00:35:33,775 --> 00:35:36,380 Oh, to je 4, takže je to 16 krát 4. 823 00:35:36,380 --> 00:35:39,380 >> A opäť, nie je to veľký problém, ak to je trochu hmlisté pamäti teraz. 824 00:35:39,380 --> 00:35:43,720 Ale teraz, sa na základe viery že 16 protokolu 16 je 64. 825 00:35:43,720 --> 00:35:46,590 A tak sa skutočne s týmto jednoduchým zdravého rozumu Skontrolujte, sme potvrdená - 826 00:35:46,590 --> 00:35:48,250 ale ukázalo formálne - 827 00:35:48,250 --> 00:35:52,800 že doba chodu zlúčenie Triedenie je naozaj n log n 828 00:35:52,800 --> 00:35:53,790 >> Takže to nie je zlé. 829 00:35:53,790 --> 00:35:57,260 Je to určite lepšie, než algoritmy sme videli doteraz, a 830 00:35:57,260 --> 00:36:00,710 je to preto, že sme zadlžujú, jedným, techniku ​​zvanú rekurzia. 831 00:36:00,710 --> 00:36:03,880 Ale zaujímavejšie než to, že Pojem delenie a dobývanie. 832 00:36:03,880 --> 00:36:07,460 Opäť platí, že naozaj veci, ktoré týždeň 0 aj dnes sa opakujúce v 833 00:36:07,460 --> 00:36:08,740 presvedčivejšie spôsobom. 834 00:36:08,740 --> 00:36:11,750 >> Teraz trochu zábavy cvičenia, ak ste nikdy nerobil - a pravdepodobne 835 00:36:11,750 --> 00:36:14,660 by nemal, pretože akosi normálne ľudia si nemyslím, že to urobiť. 836 00:36:14,660 --> 00:36:20,650 Ale keď idem do google.com, a ak Chcem sa dozvedieť niečo o 837 00:36:20,650 --> 00:36:22,356 rekurzia, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Smiech] 840 00:36:29,058 --> 00:36:32,030 [Ďalšia smiech] 841 00:36:32,030 --> 00:36:33,385 DAVID Malan: Bad joke pomaly šíri. 842 00:36:33,385 --> 00:36:34,450 [Smiech] 843 00:36:34,450 --> 00:36:36,970 DAVID Malan: Len v prípade, že tam je. 844 00:36:36,970 --> 00:36:38,710 Nechcel som to zle píše, a tam je ten vtip. 845 00:36:38,710 --> 00:36:40,810 Dobrá. 846 00:36:40,810 --> 00:36:42,950 Vysvetlite ľuďom vedľa vás, či to nie je úplne klikol len zatiaľ. 847 00:36:42,950 --> 00:36:47,650 Ale rekurzia, všeobecne sa odkazuje do procesu a volania funkcií 848 00:36:47,650 --> 00:36:51,430 sama o sebe, alebo všeobecnejšie, delenie problém do niečoho, čo môže byť 849 00:36:51,430 --> 00:36:56,220 rieši po častiach pri riešení zhodné reprezentatívny problémy. 850 00:36:56,220 --> 00:36:58,400 >> Dobre, poďme preradiť len na chvíľu. 851 00:36:58,400 --> 00:37:00,840 Radi by sme skončiť na určitých cliffhangers, takže poďme začať s nastavením 852 00:37:00,840 --> 00:37:05,870 fáze, po dobu niekoľkých minút, na veľmi jednoduchom nápadu - 853 00:37:05,870 --> 00:37:07,620 to prehodenie dvoch prvkov, nie? 854 00:37:07,620 --> 00:37:10,040 Všetky tieto algoritmy sme boli hovorí o posledných pár 855 00:37:10,040 --> 00:37:12,420 Prednášky zahŕňajú niektoré druh vymieňať. 856 00:37:12,420 --> 00:37:14,630 Dnes to bolo vizualizovať ich získavanie sa zo svojich stoličiek a 857 00:37:14,630 --> 00:37:18,570 chodia, ale v kóde, by sme len sa prvok z jedného poľa 858 00:37:18,570 --> 00:37:20,370 a PLOP to do druhého. 859 00:37:20,370 --> 00:37:21,880 >> Tak ako sme sa ísť asi robí? 860 00:37:21,880 --> 00:37:24,850 No, dovoľte mi ísť ďalej a písať rýchly program tu. 861 00:37:24,850 --> 00:37:31,600 Chystám sa ísť ďalej a robiť to je napríklad nasledovné. 862 00:37:31,600 --> 00:37:33,910 Povedzme to - 863 00:37:33,910 --> 00:37:38,070 Čo chceme volať toto? 864 00:37:38,070 --> 00:37:38,650 >> V skutočnosti, no. 865 00:37:38,650 --> 00:37:39,420 Nechaj ma dozadu. 866 00:37:39,420 --> 00:37:41,220 Nechcem k tomu, že Cliffhanger ešte. 867 00:37:41,220 --> 00:37:42,270 To bude kaziť zábavu. 868 00:37:42,270 --> 00:37:43,600 Poďme na to miesto. 869 00:37:43,600 --> 00:37:47,430 >> Dajme tomu, že chcem napísať niečo program, a teraz zahŕňa tento 870 00:37:47,430 --> 00:37:48,700 Myšlienka rekurzia. 871 00:37:48,700 --> 00:37:50,370 Tak nejako som sa dostal pred seba tam. 872 00:37:50,370 --> 00:37:51,420 Chystám sa vykonať nasledujúce kroky. 873 00:37:51,420 --> 00:38:00,220 >> Po prvé, je rýchly štandardný IO.H, rovnako ako patrí v cs50.h. 874 00:38:00,220 --> 00:38:03,200 A potom budem pokračovať a vyhlásiť za neplatné int main 875 00:38:03,200 --> 00:38:04,360 obvyklým spôsobom. 876 00:38:04,360 --> 00:38:07,920 Uvedomil som si, som nesprávne pomenovaný súbor, takže dovoľte mi pridať. c príponu, takže tu 877 00:38:07,920 --> 00:38:09,510 že môžeme zostaviť správne. 878 00:38:09,510 --> 00:38:10,970 Spustite túto funkciu vypnúť. 879 00:38:10,970 --> 00:38:13,290 >> A funkcie chcem napísať, docela Jednoducho povedané, je ten, ktorý žiada 880 00:38:13,290 --> 00:38:16,210 užívateľ pre číslo a potom spočíta všetky čísla, ktorá medzi 881 00:38:16,210 --> 00:38:19,920 číslo a, povedzme, 0. 882 00:38:19,920 --> 00:38:22,510 Takže v prvom rade budem pokračovať a vyhlasujú, int n 883 00:38:22,510 --> 00:38:24,760 Potom som skopírovať nejaký kód, ktorý sme použili na chvíľu. 884 00:38:24,760 --> 00:38:26,660 Aj keď je niečo pravda. 885 00:38:26,660 --> 00:38:28,000 Vrátim sa k tomu za chvíľu. 886 00:38:28,000 --> 00:38:29,010 >> Čo chcem robiť? 887 00:38:29,010 --> 00:38:33,460 Chcem povedať printf pozitívny celé číslo, prosím. 888 00:38:33,460 --> 00:38:36,130 A potom budem povedať, n dostane sa int. 889 00:38:36,130 --> 00:38:38,800 Takže znova, niektorí štandardizovaný kód že sme použili predtým. 890 00:38:38,800 --> 00:38:40,810 A ja idem na to keď n je menšia ako 1. 891 00:38:40,810 --> 00:38:44,120 Takže to bude zabezpečiť, že používateľ mi dáva kladné celé číslo. 892 00:38:44,120 --> 00:38:45,490 >> A teraz budem robiť nasledujúce. 893 00:38:45,490 --> 00:38:51,020 Chcem sa sčítať všetky čísla medzi 1 a a n, alebo 0 a n, 894 00:38:51,020 --> 00:38:52,570 ekvivalentne, aby celkový súčet. 895 00:38:52,570 --> 00:38:55,100 Takže veľká sigma symbol ktoré by vás mohli vyvolať. 896 00:38:55,100 --> 00:38:59,050 Takže budem robiť, tým prvým volanie volaná funkcia sigma, 897 00:38:59,050 --> 00:39:06,030 prechádzať skrz n, a potom budem hovoria printf, odpoveď je tu. 898 00:39:06,030 --> 00:39:08,180 >> Takže v skratke, som si a int od užívateľa. 899 00:39:08,180 --> 00:39:09,280 Ja sa zabezpečilo, že je to pozitívna. 900 00:39:09,280 --> 00:39:12,700 Prehlasujem premennú s názvom odpoveď typ int a uložiť v ňom návrat 901 00:39:12,700 --> 00:39:15,610 hodnota sigma, odovzdaním n ako vstup. 902 00:39:15,610 --> 00:39:17,060 A potom som vytlačiť túto odpoveď. 903 00:39:17,060 --> 00:39:19,550 >> Bohužiaľ, aj keď znie sigma ako niečo, čo by mohlo byť v 904 00:39:19,550 --> 00:39:24,040 math.h súboru, jeho vyhlásenie, je to v skutočnosti nie je. 905 00:39:24,040 --> 00:39:24,690 Tak to je v poriadku. 906 00:39:24,690 --> 00:39:26,170 Môžem vykonanie tohto sám. 907 00:39:26,170 --> 00:39:29,160 Chystám sa realizovať názvom funkcie sigma, a že to bude trvať 908 00:39:29,160 --> 00:39:29,900 parameter - 909 00:39:29,900 --> 00:39:32,100 Povedzme, že m, len tak to je niečo iné. 910 00:39:32,100 --> 00:39:35,910 A potom tu, budem hovoriť, a, ak je m je menšia ako 1 - jedná sa o 911 00:39:35,910 --> 00:39:38,180 veľmi nezaujímavý program. 912 00:39:38,180 --> 00:39:41,700 Takže budem pokračovať a bezodkladne vrátiť 0. 913 00:39:41,700 --> 00:39:45,920 To jednoducho nedáva zmysel sčítať všetky čísla medzi 1 a M, ak m 914 00:39:45,920 --> 00:39:48,470 je sám o sebe 0 alebo negatívne. 915 00:39:48,470 --> 00:39:50,900 >> A potom budem pokračovať a to veľmi iteratívne. 916 00:39:50,900 --> 00:39:53,090 Chystám sa robiť takéto starej školy, a ja idem do toho 917 00:39:53,090 --> 00:39:57,150 a hovoria, že budem deklarovať sumu za 0. 918 00:39:57,150 --> 00:39:59,630 Potom budem mať pre sláčiky int - 919 00:39:59,630 --> 00:40:02,820 a nechaj ma to urobiť tak, aby zodpovedala Our distribúcia kód, takže máte kópiu 920 00:40:02,820 --> 00:40:07,500 doma. int aj dostane až na 1 i je menšie ako alebo rovná m 921 00:40:07,500 --> 00:40:09,430 aj plus plus. 922 00:40:09,430 --> 00:40:11,430 A potom vnútri tohto cyklu for - 923 00:40:11,430 --> 00:40:12,440 Už sme skoro tam - 924 00:40:12,440 --> 00:40:15,810 Súčet dostane čiastku plus 1. 925 00:40:15,810 --> 00:40:17,670 A potom idem vrátiť čiastku. 926 00:40:17,670 --> 00:40:19,420 >> Tak som to urobil tak rýchlo, celkom pravda. 927 00:40:19,420 --> 00:40:22,775 Ale znovu, ktorého hlavnou funkciou je dosť jednoduchý, založený na kóde sme 928 00:40:22,775 --> 00:40:23,190 napísal tak ďaleko. 929 00:40:23,190 --> 00:40:25,610 Používa dvojaký slučku, aby sa pozitívne int od užívateľa. 930 00:40:25,610 --> 00:40:29,870 Potom som sa prejsť, že int do novej funkcie tzv sigma, volať to opäť n 931 00:40:29,870 --> 00:40:33,100 A ja uložiť návratovú hodnotu, odpoveď z čiernej skrinky v súčasnosti 932 00:40:33,100 --> 00:40:35,460 známy ako Sigma, v premennej volal odpoveď. 933 00:40:35,460 --> 00:40:36,580 Potom som vytlačiť. 934 00:40:36,580 --> 00:40:39,090 >> Ak by sme teraz pokračovať v príbehu, ako je sigma realizovaný? 935 00:40:39,090 --> 00:40:40,840 Navrhujem urobiť takto. 936 00:40:40,840 --> 00:40:43,560 Najprv trochu kontroly chýb aby sa ubezpečil, že používateľ nie je 937 00:40:43,560 --> 00:40:46,480 preberať sa mnou a odovzdaním niektoré negatívne alebo hodnota 0. 938 00:40:46,480 --> 00:40:49,710 Potom som deklarovať premennú s názvom zhrnúť a nastavte ju na hodnotu 0.. 939 00:40:49,710 --> 00:40:55,910 >> A teraz sa začne pohybovať aj zo rovná 1 celú cestu až do m, 940 00:40:55,910 --> 00:41:00,130 pretože chcem, aby zahŕňala všetky čísla od jednotky do m vrátane. 941 00:41:00,130 --> 00:41:04,350 A vnútri tohto cyklu for, som jednoducho Súčet dostane, čo je teraz, a 942 00:41:04,350 --> 00:41:08,900 hodnota i 943 00:41:08,900 --> 00:41:10,370 Navyše hodnota i 944 00:41:10,370 --> 00:41:14,090 >> Mimochodom, ak ste to ešte nevideli skôr, je tu nejaký syntaktickú cukor 945 00:41:14,090 --> 00:41:14,870 pre túto linku. 946 00:41:14,870 --> 00:41:21,120 Môžem prepísať ako a rovná i, len zachrániť seba niekoľko klávesových skratiek 947 00:41:21,120 --> 00:41:22,570 a pozrieť sa trochu chladnejšie. 948 00:41:22,570 --> 00:41:23,140 Ale to je všetko. 949 00:41:23,140 --> 00:41:24,660 Je to funkčne to isté. 950 00:41:24,660 --> 00:41:26,710 >> Bohužiaľ, tento kód je nebude kompilovať ešte. 951 00:41:26,710 --> 00:41:31,600 Keď som bežať, aby sigma 0, ako pm Budem sa dostať kričal na? 952 00:41:31,600 --> 00:41:33,473 Aké to bude nepáči? 953 00:41:33,473 --> 00:41:35,740 >> DIVÁKOV: [nepočuteľné]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID Malan: Jo, ja nepriznal funkcie až hore, vpravo? 955 00:41:37,800 --> 00:41:40,590 C je tak trochu blbosť, v tom, že iba robí to, čo poviete to urobiť, a vy 956 00:41:40,590 --> 00:41:41,880 musíte urobiť to v tomto poradí. 957 00:41:41,880 --> 00:41:45,910 A tak keď som stlačte klávesu Enter tu, idem dostať varovanie o sigma implicitné 958 00:41:45,910 --> 00:41:46,860 vyhlásenie. 959 00:41:46,860 --> 00:41:48,120 >> Oh, nie je problém. 960 00:41:48,120 --> 00:41:50,370 Môžem ísť až na vrchol, a môžem hovoria, dobre, počkaj. 961 00:41:50,370 --> 00:41:54,240 Sigma je funkcia, ktorá vracia int a očakáva, že 962 00:41:54,240 --> 00:41:56,620 int ako vstup, bodkočiarkou. 963 00:41:56,620 --> 00:41:59,550 Alebo by som mohol dať celú funkciu nad hlavnou, ale všeobecne, tak by som 964 00:41:59,550 --> 00:42:02,260 neodporúčame, pretože to je pekné vždy hlavné hornej časti, aby sa 965 00:42:02,260 --> 00:42:06,310 môžete ponoriť priamo a viem, čo Program robí čítaním hlavnej najskôr. 966 00:42:06,310 --> 00:42:07,930 >> Takže teraz mi dovoľte vyčistiť obrazovku. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Všetko vyzerá, že check-out. 969 00:42:10,340 --> 00:42:11,970 Dovoľte mi spustiť sigma 0. 970 00:42:11,970 --> 00:42:12,770 Pozitívne inter. 971 00:42:12,770 --> 00:42:15,580 Dám to číslo 3, aby to jednoduché. 972 00:42:15,580 --> 00:42:18,710 Tak, že by mi 3 plus 2 plus 1, tak 6. 973 00:42:18,710 --> 00:42:20,750 Zadajte, a naozaj som si 6. 974 00:42:20,750 --> 00:42:21,820 >> Môžem urobiť niečo väčšieho - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Rovnako ako dotyčnicu, budem robiť niečo smiešne ako naozaj veľký 977 00:42:27,690 --> 00:42:30,375 číslo, Oh, to skutočne dopadlo - 978 00:42:30,375 --> 00:42:31,600 eh, ja si nemyslím, že je to pravda. 979 00:42:31,600 --> 00:42:32,810 Poďme sa pozrieť. 980 00:42:32,810 --> 00:42:34,060 Poďme naozaj si s ním. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> To je problém. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Čo sa deje? 985 00:42:44,970 --> 00:42:46,050 Kód Nie je to tak zlé. 986 00:42:46,050 --> 00:42:48,470 Je to stále lineárna. 987 00:42:48,470 --> 00:42:50,810 Pískanie je dobrý účinok, hoci. 988 00:42:50,810 --> 00:42:52,060 Čo sa deje? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Nie je si istý, či som to počul. 991 00:42:55,620 --> 00:42:57,620 Tak to dopadá - a to je stranou. 992 00:42:57,620 --> 00:42:59,400 To nie je jadrom Myšlienka rekurzia. 993 00:42:59,400 --> 00:43:02,480 Ukazuje sa, pretože ja sa snažím predstavujú tak veľké množstvo, väčšina 994 00:43:02,480 --> 00:43:06,980 pravdepodobne je to byť mylne o C, ako to kladné číslo, 995 00:43:06,980 --> 00:43:09,980 ale záporné číslo. 996 00:43:09,980 --> 00:43:12,690 >> Nehovorili sme o tom, ale je to Ukazuje sa, že sú záporné čísla 997 00:43:12,690 --> 00:43:14,210 vo svete navyše do kladných čísel. 998 00:43:14,210 --> 00:43:16,290 A prostriedky, ktoré môžete predstavujú záporné číslo 999 00:43:16,290 --> 00:43:19,530 v podstate je, že môžete použiť jeden špeciálny bit pre indikáciu 1000 00:43:19,530 --> 00:43:20,400 pozitívne na negatívne. 1001 00:43:20,400 --> 00:43:22,950 Je to trochu zložitejšie, než to, ale to je základná myšlienka. 1002 00:43:22,950 --> 00:43:26,740 >> Takže bohužiaľ, ak C je mätúce z týchto bitov je v skutočnosti znamená, 1003 00:43:26,740 --> 00:43:30,790 oh, to je záporné číslo, moja slučka Tu, napríklad, je v skutočnosti nikdy 1004 00:43:30,790 --> 00:43:31,740 bude ukončená. 1005 00:43:31,740 --> 00:43:33,850 Takže keď som bol vlastne tlače niečo znovu a znovu, by sme 1006 00:43:33,850 --> 00:43:34,650 vidieť veľa. 1007 00:43:34,650 --> 00:43:36,220 Ale opäť, to je vedľa bodu. 1008 00:43:36,220 --> 00:43:38,590 To je naozaj len akýmsi intelektuálne zvedavosť, že prídeme 1009 00:43:38,590 --> 00:43:39,550 späť nakoniec. 1010 00:43:39,550 --> 00:43:43,400 Ale teraz je to správne Implementácia ak budeme predpokladať, že 1011 00:43:43,400 --> 00:43:45,970 užívateľ bude poskytovať ints ktoré zapadajú do ints. 1012 00:43:45,970 --> 00:43:49,370 >> Ale tvrdím, že tento kód, úprimne povedané, by sa dalo urobiť oveľa jednoduchšie. 1013 00:43:49,370 --> 00:43:54,060 Ak je cieľom po ruke, je prijať rad ako m a sčítať všetky 1014 00:43:54,060 --> 00:43:59,510 čísla medzi ním a 1, alebo naopak medzi 1 a, tvrdím, 1015 00:43:59,510 --> 00:44:03,380 že môžem požičať myšlienku, že zlúčenie druh mal, ktorý bol s problémami 1016 00:44:03,380 --> 00:44:05,660 tejto veľkosti a oddeľujúcich do niečoho menšieho. 1017 00:44:05,660 --> 00:44:09,875 Možno nie polovica, ale menšie, ale reprezentatívne rovnaké. 1018 00:44:09,875 --> 00:44:12,130 Rovnaký nápad, ale menší problém. 1019 00:44:12,130 --> 00:44:15,470 >> Takže som vlastne - dovoľte mi, aby som tento súbor uložiť s iným číslom verzie. 1020 00:44:15,470 --> 00:44:17,670 Zavoláme túto verziu 1 miesto 0. 1021 00:44:17,670 --> 00:44:20,790 A tvrdím, že som si vlastne reimplement to v tomto druhu 1022 00:44:20,790 --> 00:44:22,160 myseľ-ohýbanie cesta. 1023 00:44:22,160 --> 00:44:23,710 >> Chystám sa opustiť jeho časť samostatne. 1024 00:44:23,710 --> 00:44:27,710 Chystám sa povedať, či m je menej než alebo sa môže dokonca rovnať 0 - 1025 00:44:27,710 --> 00:44:29,280 Ja len bude trochu viac análny tentoraz 1026 00:44:29,280 --> 00:44:30,520 s mojou kontrolu chýb - 1027 00:44:30,520 --> 00:44:33,190 Chystám sa ísť dopredu a vráti 0. 1028 00:44:33,190 --> 00:44:34,490 To je ľubovoľná. 1029 00:44:34,490 --> 00:44:37,500 Som proste rozhodne, či používateľ mi dáva záporné číslo, ja som 1030 00:44:37,500 --> 00:44:41,490 vracia 0, a mali by Prečítal dokumentácie podrobnejšie. 1031 00:44:41,490 --> 00:44:42,170 >> Else - 1032 00:44:42,170 --> 00:44:44,070 Všimnite si, čo budem robiť. 1033 00:44:44,070 --> 00:44:49,260 Inak sa budem vracať M plus - 1034 00:44:49,260 --> 00:44:51,010 čo je sigma m? 1035 00:44:51,010 --> 00:44:56,710 No, sigma M plus M mínus 1, a m mínus 2 plus mínus 3 m 1036 00:44:56,710 --> 00:44:58,030 Nechcem písať všetky tie von. 1037 00:44:58,030 --> 00:44:59,120 Prečo proste nemôžem pramice? 1038 00:44:59,120 --> 00:45:05,080 Rekurzívne volať sám s mierne menší problém, bodkočiarku, 1039 00:45:05,080 --> 00:45:06,840 a nazývať to deň? 1040 00:45:06,840 --> 00:45:07,040 >> Je to tak? 1041 00:45:07,040 --> 00:45:10,980 Teraz tu taky, možno máte pocit, strach alebo že sa jedná o nekonečnú slučku, že som 1042 00:45:10,980 --> 00:45:15,450 vyvolávajúce, kedy som vykonávacích sigma sigma volaním. 1043 00:45:15,450 --> 00:45:20,342 Ale to je úplne v poriadku, pretože som myslel dopredu pridal ktoré riadky? 1044 00:45:20,342 --> 00:45:22,600 >> DIVÁKOV: [nepočuteľné]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID Malan: 23 až 26, ktoré ak je môj stav. 1046 00:45:25,430 --> 00:45:28,390 Pretože to, čo je pekné o odčítanie tu, pretože som sa udržať 1047 00:45:28,390 --> 00:45:31,180 rozdávajú sigma menšie problémy, menšie problémy, menšie - to nie je 1048 00:45:31,180 --> 00:45:31,870 polovičnej veľkosti. 1049 00:45:31,870 --> 00:45:34,380 Je to len krôčik menšie, ale to je v poriadku. 1050 00:45:34,380 --> 00:45:38,050 Pretože nakoniec, budeme pracovať naša cesta nadol na hodnotu 1 alebo 0. 1051 00:45:38,050 --> 00:45:41,630 A akonáhle sa dostaneme 0, sigma nie je zavolá sám už nie. 1052 00:45:41,630 --> 00:45:43,590 Bude to okamžite vráti 0. 1053 00:45:43,590 --> 00:45:47,960 >> Takže efekt, ak ste trochu vetra tento vo vašej mysli, je pridať M plus 1054 00:45:47,960 --> 00:45:52,740 m mínus 1 plus mínus m 2 plus mínus m 3 plus bodka, bodka, bodka, m mínus 1055 00:45:52,740 --> 00:45:57,820 m, ktorá vám nakoniec 0, a účinok je nakoniec pridať všetky 1056 00:45:57,820 --> 00:45:59,070 tieto veci dohromady. 1057 00:45:59,070 --> 00:46:02,380 Takže nemáme s rekurzia, vyriešiť problém, že sa 1058 00:46:02,380 --> 00:46:03,470 nemôže vyriešiť skôr. 1059 00:46:03,470 --> 00:46:06,840 V skutočnosti, verzia 0 tohto, a každý problém k dnešnému dňu, bol riešiteľný 1060 00:46:06,840 --> 00:46:09,980 len s použitím slučky, alebo keď slučky alebo podobné konštrukty. 1061 00:46:09,980 --> 00:46:13,150 >> Ale rekurzia, trúfam si povedať, nám dáva iný spôsob uvažovania o 1062 00:46:13,150 --> 00:46:17,010 Problémy, ktorým môžeme ak sa problém, rozdeliť ju z niečoho 1063 00:46:17,010 --> 00:46:22,340 trochu veľký na niečo trochu menšie, tvrdím, že môžeme vyriešiť 1064 00:46:22,340 --> 00:46:26,040 možno trochu viac elegantne, pokiaľ ide konštrukcie, s menej kódu, 1065 00:46:26,040 --> 00:46:30,980 a možno aj riešiť problémy, ktoré by bude ťažšie, pretože my budeme nakoniec 1066 00:46:30,980 --> 00:46:33,280 vidieť, riešenie čisto iteratívne. 1067 00:46:33,280 --> 00:46:35,980 >> Ale Cliffhanger, že som chcieť nechať nás na to bolo. 1068 00:46:35,980 --> 00:46:40,720 Nechaj ma ísť dopredu a otvorte sa súbor z - 1069 00:46:40,720 --> 00:46:44,300 vlastne, nechaj ma ísť a urobiť naozaj rýchlo. 1070 00:46:44,300 --> 00:46:46,875 Nechaj ma ísť napred a navrhnúť nasledujúce. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Medzi dnešné kódu je tento súbor tu. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Tenhle, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Tak to je hlúpy malý program, ktorý Prudko som sa, že tvrdí, že to 1076 00:47:06,260 --> 00:47:06,940 nasledujúce. 1077 00:47:06,940 --> 00:47:10,140 V zásade sa najprv deklaruje int x volal a priradí ju 1078 00:47:10,140 --> 00:47:11,100 hodnota 1. 1079 00:47:11,100 --> 00:47:13,520 Potom vyhlási, int y a priradí mu hodnotu 2. 1080 00:47:13,520 --> 00:47:15,310 Potom to vytlačí, čo x a y je. 1081 00:47:15,310 --> 00:47:17,781 Potom hovorí, vymieňať, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Potom tvrdia, že je volanie funkcie tzv swapu a odovzdať x a 1083 00:47:21,670 --> 00:47:24,290 y, myšlienka je, že snáď x a y sa vráti 1084 00:47:24,290 --> 00:47:25,620 inak, naopak. 1085 00:47:25,620 --> 00:47:27,110 Potom to tvrdí zameniť! 1086 00:47:27,110 --> 00:47:28,420 s výkričníkom. 1087 00:47:28,420 --> 00:47:30,190 Potom sa vytlačí x a y. 1088 00:47:30,190 --> 00:47:33,480 >> Ale ukazuje sa, že práve táto jednoduchá demonštrácia dole 1089 00:47:33,480 --> 00:47:35,570 tu je vlastne buggy. 1090 00:47:35,570 --> 00:47:38,870 Aj keď som vyhlásil dočasný variabilné a dočasne uvedení v 1091 00:47:38,870 --> 00:47:42,010 to, potom som prerozdelenie hodnota b - 1092 00:47:42,010 --> 00:47:45,080 ktoré sa cítia rozumné, pretože som uložili kópiu na teplote. 1093 00:47:45,080 --> 00:47:48,410 Potom som aktualizovať b rovná všetko, čo bolo v temp. 1094 00:47:48,410 --> 00:47:51,610 Tento druh hazardnú hru pohybujúce sa do b a b na použitie tohto 1095 00:47:51,610 --> 00:47:54,360 stredného muž menom temp cíti absolútne rozumné. 1096 00:47:54,360 --> 00:47:57,270 >> Ale tvrdím, že keď som tento príkaz kód, ako budem robiť teraz - 1097 00:47:57,270 --> 00:47:59,490 nechaj ma ísť dopredu a vložte ho sem. 1098 00:47:59,490 --> 00:48:01,995 Zavolám tento noswap.c. 1099 00:48:01,995 --> 00:48:05,630 A ako už názov napovedá, že to nie je Bude to správny program. 1100 00:48:05,630 --> 00:48:09,460 Urobiť noswap. / Nie swap. 1101 00:48:09,460 --> 00:48:12,110 x 1, y 2, vymieňať, prehodené. 1102 00:48:12,110 --> 00:48:14,220 x je 1, y je 2.. 1103 00:48:14,220 --> 00:48:16,920 To je zásadná chyba, a to aj aj keď sa to zdá úplne 1104 00:48:16,920 --> 00:48:17,730 primerané ku mne. 1105 00:48:17,730 --> 00:48:21,330 A je tu dôvod, ale nie sme chystá odhaliť príčinu len zatiaľ. 1106 00:48:21,330 --> 00:48:24,610 >> Pre túto chvíľu druhý Cliffhanger som chcel nechať sa je to, 1107 00:48:24,610 --> 00:48:27,120 Oznámenie druhov na kupon kódov. 1108 00:48:27,120 --> 00:48:31,590 Naše inovácie v neskorých dní tento rok vyvolalo netriviálne počet 1109 00:48:31,590 --> 00:48:33,830 otázok, ktorý bol Nie je naším zámerom. 1110 00:48:33,830 --> 00:48:36,590 Zámerom týchto kupon kódov, pričom ak tak urobíte časť problému 1111 00:48:36,590 --> 00:48:39,850 na začiatku, a tým získať ďalší deň, Bolo to naozaj pomôcť vy pomôcť 1112 00:48:39,850 --> 00:48:42,420 sami začať čoskoro, triediť vedľajších motivácie vám. 1113 00:48:42,420 --> 00:48:44,880 Nám pomáha distribuovať zaťaženie medzi úradné hodiny tak, aby lepšie 1114 00:48:44,880 --> 00:48:45,740 Je to niečo win-win. 1115 00:48:45,740 --> 00:48:48,860 >> Bohužiaľ si myslím, že moje inštrukcie neboli do dnešného dňa, veľmi jasné, takže 1116 00:48:48,860 --> 00:48:52,230 Vrátil som sa o tomto víkende a aktualizované spec väčšie, odvážnejšie textu na 1117 00:48:52,230 --> 00:48:53,600 vysvetliť guľky, ako sú tieto. 1118 00:48:53,600 --> 00:48:56,900 A práve to povedať viac verejne, a predvolené, základné problémové okruhy sú dané štvrtok 1119 00:48:56,900 --> 00:48:58,400 na poludnie, podľa sylabu. 1120 00:48:58,400 --> 00:49:02,030 Ak začnete skoro, dokončovacie časť problém nastaviť v stredu o 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, tá časť, ktorá sa vzťahuje k kupón kód, myšlienka je, že môžete rozšíriť 1122 00:49:05,170 --> 00:49:07,710 Váš termín pre P nastaviť až do piatku. 1123 00:49:07,710 --> 00:49:10,890 To znamená, že odhryzol malú časť P nastaviť voči tomu, čo je zvyčajne 1124 00:49:10,890 --> 00:49:13,200 väčší problém a kúpiť si deň naviac. 1125 00:49:13,200 --> 00:49:15,190 Opäť platí, že vás dostane premýšľať o tom, Problém set, dostane vás do 1126 00:49:15,190 --> 00:49:16,380 úradné hodiny skôr. 1127 00:49:16,380 --> 00:49:20,670 Ale kupónu problém je stále potrebné, aj keď nemáte predloží ju. 1128 00:49:20,670 --> 00:49:23,340 >> Ale presvedčivo to je. 1129 00:49:23,340 --> 00:49:26,520 (Šepot) A tí ľudia odchádza Už sú to ľutovať. 1130 00:49:26,520 --> 00:49:28,620 Ako sú ľudia na balkóne. 1131 00:49:28,620 --> 00:49:32,510 Ospravedlňujem sa vopred na ľudí na balkón z dôvodov, ktoré budú 1132 00:49:32,510 --> 00:49:33,920 jasné, za chvíľu. 1133 00:49:33,920 --> 00:49:37,050 >> Tak sme to šťastie, že jeden z CS50 bývalí kolegovia hlava výučby na 1134 00:49:37,050 --> 00:49:39,302 spoločnosť s názvom dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Majú veľmi veľkoryso darovali kupon kód tu pre túto toľko miesta, 1136 00:49:45,500 --> 00:49:48,180 ktorá je oproti obvyklé 2GB. 1137 00:49:48,180 --> 00:49:51,740 Takže to, čo som myslel, že by to na to Posledná poznámka je to trochu prezradí, 1138 00:49:51,740 --> 00:49:55,380 pričom za chvíľu budeme odhaliť víťaz a kto má kupón 1139 00:49:55,380 --> 00:49:57,980 kód, ktorý potom môžete ísť na ich webové stránky, zadajte do, a voila, získať 1140 00:49:57,980 --> 00:50:01,370 oveľa viac priestoru pre vašu Dropbox zariadení a osobných súborov. 1141 00:50:01,370 --> 00:50:05,690 >> A prvý, kto by sa chceli zúčastniť v tomto obrázku? 1142 00:50:05,690 --> 00:50:09,630 OK, teraz, že je to ešte väčšia zábava. 1143 00:50:09,630 --> 00:50:14,010 Osoba, ktorá dostane tento 25-gigabyte kupon kód - čo je oveľa 1144 00:50:14,010 --> 00:50:16,150 presvedčivejšie než neskoro dni teraz, možno - 1145 00:50:16,150 --> 00:50:20,620 je ten, kto sedí na vrchole sedák, pod ktorým je 1146 00:50:20,620 --> 00:50:21,620 že kupónu. 1147 00:50:21,620 --> 00:50:23,480 Teraz sa môžete pozrieť pod Váš sedák. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [PLAYBACK] 1150 00:50:29,680 --> 00:50:31,620 >> -Jeden, dva, tri. 1151 00:50:31,620 --> 00:50:35,015 >> [SCREAMING] 1152 00:50:35,015 --> 00:50:35,985 >> -Ty si auto! 1153 00:50:35,985 --> 00:50:36,670 Získate auto! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID Malan: Uvidíme ste v stredu. 1155 00:50:37,970 --> 00:50:38,904 >> -Ty si auto! 1156 00:50:38,904 --> 00:50:39,371 Získate auto! 1157 00:50:39,371 --> 00:50:40,305 Získate auto! 1158 00:50:40,305 --> 00:50:41,706 Získate auto! 1159 00:50:41,706 --> 00:50:43,107 Získate auto! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID Malan: Balkón ľudí, no sem na prednej strane, 1161 00:50:45,530 --> 00:50:46,866 kde máme naviac. 1162 00:50:46,866 --> 00:50:50,282 >> -Každý dostane auto! 1163 00:50:50,282 --> 00:50:52,234 Každý dostane auto! 1164 00:50:52,234 --> 00:50:52,722 >> [END PLAYBACK] 1165 00:50:52,722 --> 00:50:54,590 >> Rozprávač: V ďalšom CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> SPEAKER 5: Ach môj bože bože bože bože bože bože bože bože bože bože - 1167 00:51:00,374 --> 00:51:02,106 >> [Ukulele HRY]