1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Přehrávání hudby] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Tohle je CS50. 5 00:00:12,550 --> 00:00:14,612 A to je začátek tří týdnů. 6 00:00:14,612 --> 00:00:16,820 Takže máme spoustu vzrušující věci k pokrytí dnes. 7 00:00:16,820 --> 00:00:20,160 Mnoho příležitostí pro dobrovolníci se na jevišti. 8 00:00:20,160 --> 00:00:22,780 A nakonec, dnes je nejde o kódu vůbec. 9 00:00:22,780 --> 00:00:24,820 Ale je to o myšlenkách, a je to o algoritmech, 10 00:00:24,820 --> 00:00:28,420 a vlastně přinášet zpět část poučení z týdne nula, 11 00:00:28,420 --> 00:00:31,910 kde odvolání, my představil tuto obludnost. 12 00:00:31,910 --> 00:00:33,880 A výpůjčky inspirace od toho, pro spuštění 13 00:00:33,880 --> 00:00:36,879 řešit stále sofistikovanější Problémy algoritmicky. 14 00:00:36,879 --> 00:00:38,420 Ale nejprve pár oznámení. 15 00:00:38,420 --> 00:00:42,020 Takže jeden, pokud byste se rádi připojili CS50 personál a spolužáci na oběd 16 00:00:42,020 --> 00:00:44,670 tento pátek, jak zde, tak v Cambridge a v New Haven, 17 00:00:44,670 --> 00:00:48,060 navštivte kurz je webové stránky, kde je možné URL nalezena. 18 00:00:48,060 --> 00:00:50,390 Přednáška bude tuto středu nemůže být tady v Sanders. 19 00:00:50,390 --> 00:00:53,610 Bude to on-line pouze, takže naladit na stránkách CS50 je, 20 00:00:53,610 --> 00:00:55,850 ať už tady v Cambridge nebo New Haven stejně. 21 00:00:55,850 --> 00:00:58,110 >> A pak problém nastavit dvě je již ve vašich rukou. 22 00:00:58,110 --> 00:01:03,067 Pokud jste se potápěl v dosud, dovolte mi nabídnout ostře formulovaný návrh 23 00:01:03,067 --> 00:01:05,150 , že zejména nyní, as Problém stanovuje postup, 24 00:01:05,150 --> 00:01:08,669 si opravdu chcete začít hned, ne-li fušovat trochu na víkend nebo před 25 00:01:08,669 --> 00:01:10,710 kdy se poprvé jít na Pátky, protože budete 26 00:01:10,710 --> 00:01:14,380 zjistíte, že to nemusí být nutně stále delší a náročnější na 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Myslím, že zjistíte, že v Obecně platí, že mají tendenci, aby se zhruba 29 00:01:17,575 --> 00:01:18,892 zhruba stejné množství času. 30 00:01:18,892 --> 00:01:20,850 Ale to rozhodně záleží na studenta, a to 31 00:01:20,850 --> 00:01:22,880 závisí na myšlení se kterým k němu přistupovat. 32 00:01:22,880 --> 00:01:24,910 Ale vždy, budete běžet proti nějaké zdi, 33 00:01:24,910 --> 00:01:26,350 a budete hit nějaký bug, a vy jste jen 34 00:01:26,350 --> 00:01:27,950 nebude moci dostat se přes to v určitém okamžiku. 35 00:01:27,950 --> 00:01:31,380 A to je velmi cenné, aby bylo možné ustoupit, vrať se další den, 36 00:01:31,380 --> 00:01:35,286 jít na pracovní dobu, příspěvek na CS50 Diskutovat nebo podobně, aby skutečně dostat odblokovat. 37 00:01:35,286 --> 00:01:36,160 Takže mějte na paměti, že. 38 00:01:36,160 --> 00:01:40,830 Spuštění nejdříve to bude možné je to nejlepší, co můžete udělat. 39 00:01:40,830 --> 00:01:44,160 Tak tady je místo, kde jsme začali třída, než v týdnu nula. 40 00:01:44,160 --> 00:01:47,441 A můžeme dostat dobrovolníka tady, aby mi pomohla najít mikrofony? 41 00:01:47,441 --> 00:01:47,940 DOBŘE. 42 00:01:47,940 --> 00:01:48,900 Stojí už vzhůru. 43 00:01:48,900 --> 00:01:50,080 Pojď nahoru. 44 00:01:50,080 --> 00:01:53,707 Hádejte, že to, jak to bude fungovat. 45 00:01:53,707 --> 00:01:54,415 Jak se jmenuješ? 46 00:01:54,415 --> 00:01:55,570 ALAN ESTRADA: Alan Estrada. 47 00:01:55,570 --> 00:01:56,778 DAVID J. Malan: Alan Estrada. 48 00:01:56,778 --> 00:01:57,910 Pojď nahoru. 49 00:01:57,910 --> 00:01:58,619 Rád tě poznávám. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Těší mě. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: A vy jste tady u nás v týdnu nula, samozřejmě. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: jsem byl. 53 00:02:03,028 --> 00:02:03,160 Byl jsem. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Takže byste mohli jít dopředu a najít pro nás Mike Smith, 55 00:02:05,868 --> 00:02:08,639 tak rychle, jak je to možné? 56 00:02:08,639 --> 00:02:10,639 Tak rychle, jak je to možné. 57 00:02:10,639 --> 00:02:13,756 Doslova trhá problém na polovinu, jak budete potřebovat. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Hm. 59 00:02:15,130 --> 00:02:17,380 DAVID J. Malan: Doslova trhání problém na polovinu. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> ALAN ESTRADA: Oh. 62 00:02:22,083 --> 00:02:22,583 Mm. 63 00:02:22,583 --> 00:02:23,300 Velmi dobře. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Dobrý. 66 00:02:24,200 --> 00:02:24,701 Děkuji. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Velmi dobře. 68 00:02:25,700 --> 00:02:26,210 DOBŘE. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: A tak teď, jste ořezaný dolů 70 00:02:27,610 --> 00:02:29,320 na polovinu velikosti problému. 71 00:02:29,320 --> 00:02:31,267 Teď, jsme až na čtvrtinu. 72 00:02:31,267 --> 00:02:33,475 Jste věnovat pozornost na které straně držíme? 73 00:02:33,475 --> 00:02:34,405 >> [Směje se] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Ano, já think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Jaká část jsme v? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: tlumiče, takže. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. Malan: OK. 78 00:02:39,941 --> 00:02:42,810 Ale Mike Smith se děje být po tlumiče. 79 00:02:42,810 --> 00:02:44,130 Tak-- 80 00:02:44,130 --> 00:02:48,180 >> [Směje se] 81 00:02:48,180 --> 00:02:48,742 >> Dobře. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Kde se to díváme? 83 00:02:50,200 --> 00:02:52,049 DAVID J. Malan: Mike Smith. 84 00:02:52,049 --> 00:02:53,090 ALAN ESTRADA: Mike Smith. 85 00:02:53,090 --> 00:02:54,760 DAVID J. Malan: Nyní jsme v chirurgické. 86 00:02:54,760 --> 00:02:57,840 Nyní lékaři. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- pojďme s real. 89 00:02:59,856 --> 00:03:00,370 Real. 90 00:03:00,370 --> 00:03:00,970 >> DAVID J. Malan: Real. 91 00:03:00,970 --> 00:03:01,470 DOBŘE. 92 00:03:01,470 --> 00:03:03,700 Potřebujete-li skutečný. 93 00:03:03,700 --> 00:03:05,250 Nyní, která cesta je Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Tudy. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Kudy? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Počkejte. 97 00:03:08,240 --> 00:03:08,790 M je-- pravdu? 98 00:03:08,790 --> 00:03:09,110 Začali jsme with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. Malan: Jo. 100 00:03:10,090 --> 00:03:10,650 Oni opustili. 101 00:03:10,650 --> 00:03:11,430 Vaše právo. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Jo. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. Malan: Takže Mike tady. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Co? 105 00:03:13,990 --> 00:03:14,665 >> [Směje se] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Špatný příklad, chlapi. 108 00:03:18,330 --> 00:03:18,830 Litovat. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: To bude vyučovat vás vyskočit ze židle. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Aha. 112 00:03:22,890 --> 00:03:23,390 Mám tě. 113 00:03:23,390 --> 00:03:24,670 Mám tě. 114 00:03:24,670 --> 00:03:25,170 Aha. 115 00:03:25,170 --> 00:03:25,669 Aha. 116 00:03:25,669 --> 00:03:26,812 To je-- OK, mám tě. 117 00:03:26,812 --> 00:03:27,520 Smith tady? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, děkuji. 119 00:03:28,894 --> 00:03:30,535 Takže budu držet vzhlédl Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, jo. 121 00:03:30,790 --> 00:03:31,340 Ne ne ne. 122 00:03:31,340 --> 00:03:31,600 Ale ne. 123 00:03:31,600 --> 00:03:31,940 To je moje. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, máš Smith. 125 00:03:32,580 --> 00:03:33,415 DOBŘE. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Jo, myslím, dostal Smith tady. 127 00:03:34,040 --> 00:03:34,700 Omlouváme se, chlapi. 128 00:03:34,700 --> 00:03:35,860 Myslel jsem, že jsme se Michael-- hledali Michaela. 129 00:03:35,860 --> 00:03:36,550 Litovat. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: To je v pořádku. 131 00:03:37,550 --> 00:03:39,950 Dobře, teď jsme do Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini a synové. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Pouze vy a já jsme na toto téma. 134 00:03:43,158 --> 00:03:44,050 DOBŘE. 135 00:03:44,050 --> 00:03:45,130 Najděte nás Mike Smith. 136 00:03:45,130 --> 00:03:45,830 Smith. 137 00:03:45,830 --> 00:03:46,310 >> ALAN ESTRADA: Smith. 138 00:03:46,310 --> 00:03:46,750 >> DAVID J. Malan: Smith. 139 00:03:46,750 --> 00:03:47,728 Jsme v R pro odpadky. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Odpadky. 141 00:03:48,644 --> 00:03:50,096 Aha. 142 00:03:50,096 --> 00:03:52,480 Bude to chvíli trvat. 143 00:03:52,480 --> 00:03:54,340 >> [Směje se] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. Malan: Shoes. 146 00:03:56,720 --> 00:03:58,080 Jsme v botách. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Teď jsme gonna-- 148 00:04:00,210 --> 00:04:01,105 >> DAVID J. Malan: Nice. 149 00:04:01,105 --> 00:04:01,980 ALAN ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Směje se] 151 00:04:03,620 --> 00:04:05,440 Oh, to je skvělé. 152 00:04:05,440 --> 00:04:06,910 [Směje se] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: To je v pořádku. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, to je dobré. 156 00:04:11,365 --> 00:04:14,425 Nemyslím si, že budu mají PSAT kamarády po tomto. 157 00:04:14,425 --> 00:04:15,300 DAVID J. Malan: Dobrý. 158 00:04:15,300 --> 00:04:16,078 Sporting. 159 00:04:16,078 --> 00:04:17,036 ALAN ESTRADA: Sporting. 160 00:04:17,036 --> 00:04:18,668 Um, L, M, N, O, P. 161 00:04:18,668 --> 00:04:19,459 DAVID J. Malan: OK. 162 00:04:19,459 --> 00:04:21,600 Takže pojďme roztrhat to na polovinu. 163 00:04:21,600 --> 00:04:22,270 Je to v pohodě. 164 00:04:22,270 --> 00:04:25,606 Tímto končí špatně tak jako tak, protože Mike Smith nebude ve Zlatých stránkách. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Ne, to je v pořádku. 167 00:04:27,140 --> 00:04:28,930 Ale pojďme předstírat, že je na této stránce. 168 00:04:28,930 --> 00:04:33,260 Takže teď, že jste ořezaný problém dolů na jedné straně, a zjistili jsme, Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Fandění] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 OK, díky. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 DOBŘE. 174 00:04:41,200 --> 00:04:43,646 To byl mimořádný. 175 00:04:43,646 --> 00:04:45,954 Ale to bylo ještě rychlejší než lineární vyhledávání, 176 00:04:45,954 --> 00:04:47,870 kde začneme u začátku knihy, 177 00:04:47,870 --> 00:04:51,210 a my se pohybují naši cestu zleva doprava, nakonec hledal Mike Smith. 178 00:04:51,210 --> 00:04:53,540 A tak, v případě, že telefonní seznam Měl snad 1000 stran, 179 00:04:53,540 --> 00:04:56,300 Možná, že by to vzali us 10 nebo tak stránky slzy. 180 00:04:56,300 --> 00:04:59,380 >> Ale můžete mít zadlužuje dotkl předpoklad 181 00:04:59,380 --> 00:05:03,602 při všech, které, což znamená že telefonní seznam předem bylo to, co? 182 00:05:03,602 --> 00:05:04,310 Diváků: Tříděný. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Je to třídit. 184 00:05:05,000 --> 00:05:05,160 Je to tak? 185 00:05:05,160 --> 00:05:07,909 Je to řazeny abecedně, tak že všechny tyto jmen a čísel 186 00:05:07,909 --> 00:05:11,230 jsou řazeny od A to k Z je, a abecedně mezi tím. 187 00:05:11,230 --> 00:05:13,100 Ale dnes, nyní se zeptat otázka, dobře, 188 00:05:13,100 --> 00:05:16,170 Jak se Verizon nebo se telefon společnost dostat do tohoto stavu? 189 00:05:16,170 --> 00:05:19,560 >> Vzhledem k tomu, že je to jedna věc je využít tento předpoklad, a proto, 190 00:05:19,560 --> 00:05:22,570 vyřešit problém s algoritmus efektivněji. 191 00:05:22,570 --> 00:05:24,900 Ale my jsme nikdy zeptal se v týdnu nula, dobře, 192 00:05:24,900 --> 00:05:27,790 kolik to stálo Verizon nebo někdo jiný 193 00:05:27,790 --> 00:05:29,620 se dostat, že telefonní seznam v seřazeném pořadí? 194 00:05:29,620 --> 00:05:29,780 >> Je to tak? 195 00:05:29,780 --> 00:05:31,529 Nezáleží na tom, zda vzhlédl Mike Smith 196 00:05:31,529 --> 00:05:35,190 je super rychlý, když to trvá vám odkaz rok zpočátku seřazení stránek. 197 00:05:35,190 --> 00:05:35,690 Je to tak? 198 00:05:35,690 --> 00:05:38,620 Ty by mohly stejně dobře prosít přes randomizované telefonní seznam, 199 00:05:38,620 --> 00:05:40,690 pokud to bude být super drahé to třídit. 200 00:05:40,690 --> 00:05:42,350 Takže, jestli můžeme mít další dobrovolník. 201 00:05:42,350 --> 00:05:46,350 Pojďme se podívat tady na jak might-- pojď up-- jak 202 00:05:46,350 --> 00:05:48,100 můžeme jít o třídění těchto. 203 00:05:48,100 --> 00:05:51,990 >> A pokud by se skutečně Jordan Připojte se k nám tady na jevišti. 204 00:05:51,990 --> 00:05:55,100 Pojďte nahoru jen na chvíli. 205 00:05:55,100 --> 00:05:56,359 Jak se jmenuješ? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, pojď nahoru. 208 00:05:58,691 --> 00:06:02,070 A vy budete spojeny mnou a Jordánskem zde. 209 00:06:02,070 --> 00:06:03,800 Caroline, děkuji. 210 00:06:03,800 --> 00:06:04,300 Dobře. 211 00:06:04,300 --> 00:06:08,330 Takže to, co jsme tady Caroline je 26 modré knihy 212 00:06:08,330 --> 00:06:10,747 že FAS používá ke správě některé závěrečné zkoušky. 213 00:06:10,747 --> 00:06:13,330 Ty jsou stále těžké najít, ale to, co jsme udělali v předstihu 214 00:06:13,330 --> 00:06:15,800 je to, že jsme vložili něčí jméno na přední straně každého z nich, 215 00:06:15,800 --> 00:06:18,133 ale my jsme stále to jednoduché od pak uvedení ven plná jména. 216 00:06:18,133 --> 00:06:22,720 Takže bychom dát osobu s názvem L, D, J, B, celá cesta A až Z, 217 00:06:22,720 --> 00:06:24,090 ale jsou v náhodném pořadí. 218 00:06:24,090 --> 00:06:26,890 A tak pokud byste, mluvil vašich cesta přes problém jako vy 219 00:06:26,890 --> 00:06:31,620 to je, můžete jít dopředu a třídit tyto pro nás, od A do Z. 220 00:06:31,620 --> 00:06:34,070 >> Publikum: OK, takže L je jako, uprostřed. 221 00:06:34,070 --> 00:06:35,050 C začíná. 222 00:06:35,050 --> 00:06:42,410 B. J před L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Držte že Myslel dobu jedné sekundy. 224 00:06:45,140 --> 00:06:48,910 Vzhledem k tomu, jinak, je to jen zajímavé pro vás, já, a Jordánskem. 225 00:06:48,910 --> 00:06:49,724 Tam jedeme. 226 00:06:49,724 --> 00:06:50,640 Diváků: [Neslyšitelné]. 227 00:06:50,640 --> 00:06:57,299 R. 228 00:06:57,299 --> 00:06:58,090 DAVID J. Malan: OK. 229 00:06:58,090 --> 00:06:59,310 Co děláš? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M přichází po O. 231 00:07:01,730 --> 00:07:02,564 >> DAVID J. Malan: OK. 232 00:07:02,564 --> 00:07:03,064 >> CAROLINE: O. 233 00:07:03,064 --> 00:07:04,120 DAVID J. Malan: Ó, dobrá. 234 00:07:04,120 --> 00:07:04,970 >> CAROLINE: E. 235 00:07:04,970 --> 00:07:06,730 >> DAVID J. Malan: E, F. Jo. 236 00:07:06,730 --> 00:07:07,620 >> CAROLINE: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> DAVID J. Malan: V, T, U, V. tak to vypadá to, že jste making-- dál. 238 00:07:10,689 --> 00:07:12,730 Vypadá to, že děláte velká hromada tady, 239 00:07:12,730 --> 00:07:13,910 a druh velkou hromadu tamhle. 240 00:07:13,910 --> 00:07:16,230 Takže první polovina abecedy, Druhá polovina abecedy. 241 00:07:16,230 --> 00:07:16,460 DOBŘE. 242 00:07:16,460 --> 00:07:16,960 Dobrý. 243 00:07:16,960 --> 00:07:19,680 Druh rozdělení problému na dvě části. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Jo. 245 00:07:21,771 --> 00:07:22,270 CAROLINE: K. 246 00:07:22,270 --> 00:07:22,980 DAVID J. Malan: OK. 247 00:07:22,980 --> 00:07:25,070 K. Takže druh výběru je jeden po druhém, 248 00:07:25,070 --> 00:07:27,620 uvedení buď vlevo nebo vpravo, nebo Z děje na zemi. 249 00:07:27,620 --> 00:07:28,012 DOBŘE. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z se děje na zemi. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. Malan: OK. 252 00:07:29,360 --> 00:07:30,920 Y se děje na zemi. 253 00:07:30,920 --> 00:07:31,735 Nyní můžeme dát X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. Malan: G se děje odešel. 256 00:07:33,700 --> 00:07:36,017 S bude v pořádku. 257 00:07:36,017 --> 00:07:37,642 Dobře, A jde celou cestu vlevo. 258 00:07:37,642 --> 00:07:38,790 >> CAROLINE: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> DAVID J. Malan: Teď, dobře. 260 00:07:39,873 --> 00:07:43,260 Máme A, B, C, W děje tam dole. 261 00:07:43,260 --> 00:07:45,566 Dobře, T. 262 00:07:45,566 --> 00:07:46,611 >> CAROLINE: H, I, J. 263 00:07:46,611 --> 00:07:47,860 DAVID J. Malan: H, I, J. Good. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: V centru, jsem gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. Malan: OK. 266 00:07:50,000 --> 00:07:52,375 Takže teď, budeme druhu o sloučení těchto různých piloty. 267 00:07:52,375 --> 00:08:00,730 Takže A až C, a pak vidím, D, a E a F a G a H a I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. A pak, to je hromada vzhůru nohama, ale to je v pořádku. 269 00:08:05,540 --> 00:08:06,040 Jistě. 270 00:08:06,040 --> 00:08:07,240 Můžeme snížit některé rohy. 271 00:08:07,240 --> 00:08:07,950 DOBŘE. 272 00:08:07,950 --> 00:08:10,530 A pak musíme W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Jo. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. Malan: Výborný. 275 00:08:11,880 --> 00:08:14,122 Tak velké poděkování Caroline pro třídění těchto. 276 00:08:14,122 --> 00:08:15,030 >> [Fandění] 277 00:08:15,030 --> 00:08:17,287 >> Děkuji. 278 00:08:17,287 --> 00:08:18,120 Děkuji mnohokrát. 279 00:08:18,120 --> 00:08:22,910 Takže teď uvažujme na okamžik jak Caroline šel o tom, že, 280 00:08:22,910 --> 00:08:26,040 a co přesně my byli schopni to-- jak 281 00:08:26,040 --> 00:08:28,409 byl schopen řešit, že problém, když jsme byli jen 282 00:08:28,409 --> 00:08:29,950 vzhledem k tomu, celá parta náhodných vstupů. 283 00:08:29,950 --> 00:08:31,610 >> No, vypadá to, že tam byl trochu tam systému? 284 00:08:31,610 --> 00:08:32,110 Správně. 285 00:08:32,110 --> 00:08:34,495 Takže čím dříve dopisy v abecedě, ona 286 00:08:34,495 --> 00:08:37,120 bylo uvedení na levé straně, a později písmen v abecedě, 287 00:08:37,120 --> 00:08:38,270 byla uvedení do pravé straně. 288 00:08:38,270 --> 00:08:40,500 A jakmile zjistila, že Některé proximální dopisy, ones 289 00:08:40,500 --> 00:08:43,124 které jdou hned vedle sebe, ona by dal ty v pořádku. 290 00:08:43,124 --> 00:08:46,750 A tak jsme trochu měli tyto malé hromady tříděných vstupů vyskytujících. 291 00:08:46,750 --> 00:08:50,540 >> A tak to je docela rád to, co Většina z nás by lidé dělají. 292 00:08:50,540 --> 00:08:53,530 Rádi bychom nějak prosít přes to, a my bychom trochu mít mechanismus. 293 00:08:53,530 --> 00:08:56,930 Ale to by mohlo být těžké psát že se ve vzorci, per se. 294 00:08:56,930 --> 00:08:59,010 Bylo to o něco více ekologická než to. 295 00:08:59,010 --> 00:09:02,560 Tak uvidíme, jestli můžeme nyní vázaný Problém s menším počtem vstupů. 296 00:09:02,560 --> 00:09:05,170 >> Místo toho, 26., pojďme něco daleko méně 297 00:09:05,170 --> 00:09:09,890 s jen říct, sedm, za tyto dveře, abych tak řekl. 298 00:09:09,890 --> 00:09:11,300 Jsou tam jen sedm čísel? 299 00:09:11,300 --> 00:09:15,240 A v případě, že cíl nyní na ruka je najít hodnotu, 300 00:09:15,240 --> 00:09:17,850 podívejme se, jak efektivně můžeme jít asi dělá. 301 00:09:17,850 --> 00:09:22,460 A uvidíme, jestli můžeme nyní začne platit nějaká čísla, 302 00:09:22,460 --> 00:09:26,310 nebo některé vzorce, s nimiž popsat Účinnost našeho telefonního seznamu 303 00:09:26,310 --> 00:09:31,060 algoritmus, naše zkouška kniha algoritmus, a obecněji, vyhledávání informací. 304 00:09:31,060 --> 00:09:34,770 >> Takže pro to, nechte mě jít dopředu, a Na dotykové obrazovce se sem, 305 00:09:34,770 --> 00:09:41,100 dát do webového prohlížeče, který má přesně těchto sedm dveře. 306 00:09:41,100 --> 00:09:46,670 A pokud bychom se mohli dostat jednu další dobrovolně pojď sem, 307 00:09:46,670 --> 00:09:48,480 Já jsem dal tyto stejné dveře sem. 308 00:09:48,480 --> 00:09:49,170 Quick dobrovolník. 309 00:09:49,170 --> 00:09:51,130 >> Tyto one-- dema jdou na rychlejší a rychlejší nyní. 310 00:09:51,130 --> 00:09:51,600 Pojď dolů. 311 00:09:51,600 --> 00:09:52,308 Jak se jmenuješ? 312 00:09:52,308 --> 00:09:53,040 Trevor: Trevor. 313 00:09:53,040 --> 00:09:53,998 >> DAVID J. Malan: Trevor? 314 00:09:53,998 --> 00:09:55,770 Dobře, Trevor, pojď dolů. 315 00:09:55,770 --> 00:09:59,212 Takže Trevor se tu dobrovolně dělat podobný problém, ale ten, který je 316 00:09:59,212 --> 00:10:02,170 užší rozsah, a to se děje abychom mohli pokusit formalizovat teď 317 00:10:02,170 --> 00:10:03,970 Proces třídění těchto čísel. 318 00:10:03,970 --> 00:10:05,500 >> Takže Trevor, rád vás poznávám. 319 00:10:05,500 --> 00:10:08,720 Takže tady je pole, tak mluví, seznam sedmi dveří. 320 00:10:08,720 --> 00:10:10,327 Jděte do toho a najít nám číslo 50. 321 00:10:10,327 --> 00:10:12,410 A pak se po faktu, řekněte nám, jak jste ji našli. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Pokud by be-- v pořádku. 324 00:10:20,040 --> 00:10:21,945 Jo, to je ten tady? 325 00:10:21,945 --> 00:10:24,680 Uh-oh. 326 00:10:24,680 --> 00:10:25,560 DOBŘE. 327 00:10:25,560 --> 00:10:26,680 Klepli že jeden. 328 00:10:26,680 --> 00:10:28,690 Dobrý. 329 00:10:28,690 --> 00:10:29,780 >> A hodně. 330 00:10:29,780 --> 00:10:30,970 Nyní jste klikli, že jeden. 331 00:10:30,970 --> 00:10:34,060 A dovolte mi, abych vám mikrofon, takže ji máte za chvíli. 332 00:10:34,060 --> 00:10:37,000 Jděte do toho a klikněte na tlačítko vedle, že máte v úmyslu. 333 00:10:37,000 --> 00:10:39,812 Ano dobře. 334 00:10:39,812 --> 00:10:41,020 Trevor: Mohu unclick dveře? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Ne, nemůžeš unclick. 336 00:10:42,620 --> 00:10:43,119 Trevor: OK. 337 00:10:43,119 --> 00:10:43,974 Toto. 338 00:10:43,974 --> 00:10:45,640 DAVID J. Malan: Kam chceš jít? 339 00:10:45,640 --> 00:10:46,410 Který? 340 00:10:46,410 --> 00:10:47,230 >> Trevor: Tenhle. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: Ne. 342 00:10:48,042 --> 00:10:48,450 >> Trevor: OK. 343 00:10:48,450 --> 00:10:48,735 Toto. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. Malan: Ano. 345 00:10:49,020 --> 00:10:49,700 To bylo dobré. 346 00:10:49,700 --> 00:10:50,380 Dobře. 347 00:10:50,380 --> 00:10:53,900 Takže jaká byla vaše algoritmus nebo Postup tohoto postupu, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> Trevor: Jen jsem prošel dveře, až jsem našel 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Vynikající algoritmus. 351 00:10:58,150 --> 00:10:59,540 Tak je to v pořádku. 352 00:10:59,540 --> 00:11:03,120 Protože ve skutečnosti, když jsem odhalí, co je Za těmito dvěma dalšími dveřmi, co 353 00:11:03,120 --> 00:11:06,954 zjistíme je, že máme jen náhodnou vstup. 354 00:11:06,954 --> 00:11:08,870 Takže to byl vlastně as dobrý, jak byste mohli dostat. 355 00:11:08,870 --> 00:11:12,509 A ve skutečnosti, máš lepší než vyčerpávajícím hledání celé pole, 356 00:11:12,509 --> 00:11:15,300 protože by to bylo skutečně smůlu, pokud jste měli hit číslo 357 00:11:15,300 --> 00:11:16,604 50 na poslední dveře. 358 00:11:16,604 --> 00:11:18,520 Ale co kdybychom namísto Dal vám předpoklad. 359 00:11:18,520 --> 00:11:20,630 Dejme tomu, že nějak jsem všechny tyto dveře kolem, 360 00:11:20,630 --> 00:11:23,500 takže máte Čísla řazeny tentokrát 361 00:11:23,500 --> 00:11:29,730 ale tentokrát je to vlastně different-- tentokrát, 362 00:11:29,730 --> 00:11:32,640 je to vlastně řazeny pro vás. 363 00:11:32,640 --> 00:11:35,380 A teď cíl na dosah ruky je trefit číslo 50. 364 00:11:35,380 --> 00:11:36,090 >> Trevor: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. Malan: Co je Váš algoritmus bude? 366 00:11:37,670 --> 00:11:39,628 >> Trevor: No, když je to řazeny, je to buď jít 367 00:11:39,628 --> 00:11:42,710 na be-- pokud největší k největší, sestupně, bude to první, 368 00:11:42,710 --> 00:11:44,751 nebo pokud je to naopak, to bude poslední. 369 00:11:44,751 --> 00:11:48,897 Tak jsem si jen klepněte na dveře, a pak stačí klepnout na poslední dveře. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Výborný. 371 00:11:49,980 --> 00:11:50,270 Dobře. 372 00:11:50,270 --> 00:11:51,150 Takže jsme zjistili, že číslo 50. 373 00:11:51,150 --> 00:11:52,970 Takže jakmile jste věděl, byly řazeny, my 374 00:11:52,970 --> 00:11:55,040 byli schopni využít tento předpoklad. 375 00:11:55,040 --> 00:11:57,040 Takže jsou moc rád telefonního seznamu příkladem. 376 00:11:57,040 --> 00:11:59,540 Jakmile budete mít, a to i malý problém jako je tento, 377 00:11:59,540 --> 00:12:02,380 vaše vstupy pre-tříděné, můžeme skutečně najít hodnotu pravděpodobně 378 00:12:02,380 --> 00:12:03,130 efektivněji. 379 00:12:03,130 --> 00:12:05,800 >> A já jsem tě, jestli je to říci řazeny malých až po velké, nebo velká, aby malé, 380 00:12:05,800 --> 00:12:08,080 a tak to bylo velmi rozumné začít na jednom konci nebo na druhou 381 00:12:08,080 --> 00:12:09,750 skutečně zjistit, že cílové hodnoty. 382 00:12:09,750 --> 00:12:11,400 Takže děkujeme Trevorem stejně. 383 00:12:11,400 --> 00:12:13,260 A já budu propose-- pěkně udělal. 384 00:12:13,260 --> 00:12:16,960 Máme trochu klip, ve skutečnosti, že je mezi naše oblíbené momentů CS50, 385 00:12:16,960 --> 00:12:19,700 přičemž někdy tyto ukázky ne zcela podle plánu. 386 00:12:19,700 --> 00:12:22,050 A skutečně právě teď, myslím, vytáhl špatnou rozhraní 387 00:12:22,050 --> 00:12:23,508 se kterým používat dotykovou obrazovku. 388 00:12:23,508 --> 00:12:24,660 Takže to byla moje chyba tam. 389 00:12:24,660 --> 00:12:26,600 >> Takže to bude dělat na příští rok klip as 390 00:12:26,600 --> 00:12:28,570 proč jsem se kliknutím na mé vlastní obrazovku. 391 00:12:28,570 --> 00:12:31,390 Ale pojďme se rychle podívat na to, co se stalo loni 392 00:12:31,390 --> 00:12:34,770 s Jay, který přišel, hodně jako Trevor tady, dobrovolně, 393 00:12:34,770 --> 00:12:39,380 a v tomto krátkém klipu uvidíte jak to totéž demo ne zcela 394 00:12:39,380 --> 00:12:41,074 odhalují stejné ponaučení. 395 00:12:41,074 --> 00:12:41,740 [VIDEOPŘEHRÁVÁNÍ] 396 00:12:41,740 --> 00:12:45,360 -všechny Chci, abyste udělat, je nyní najít pro mě a pro nás, 397 00:12:45,360 --> 00:12:51,674 Opravdu, číslo 50 krok za krokem. 398 00:12:51,674 --> 00:12:52,450 >> -The Číslo 50? 399 00:12:52,450 --> 00:12:53,190 >> -The Číslo 50. 400 00:12:53,190 --> 00:12:55,356 A můžete odhalit, co je Za každou z těchto dveří 401 00:12:55,356 --> 00:12:58,540 pouhým dotykem s prstem. 402 00:12:58,540 --> 00:13:00,910 Sakra. 403 00:13:00,910 --> 00:13:02,870 >> [Směje se] 404 00:13:02,870 --> 00:13:03,806 >> [END Přehrávání] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Takže to šlo velmi dobře. 406 00:13:05,430 --> 00:13:06,796 Ti, kteří byli netříděné dveře. 407 00:13:06,796 --> 00:13:08,670 Jay a, samozřejmě, našel to všechno příliš rychle. 408 00:13:08,670 --> 00:13:12,910 Trevor udělal mnohem lepší práci v podmínkách učenlivý okamžik 409 00:13:12,910 --> 00:13:15,850 tak říkajíc, v tomto roce trvá delší dobu ji najít. 410 00:13:15,850 --> 00:13:17,950 Samozřejmě, pak jsme dali Jay druhá šance, 411 00:13:17,950 --> 00:13:20,320 čímž jsme řazeny dveře, jako jsme to udělali pro Trevora, 412 00:13:20,320 --> 00:13:22,300 a Trevor DID Super dobře tentokrát. 413 00:13:22,300 --> 00:13:26,124 Ale Jay to udělal polovinu rychle. 414 00:13:26,124 --> 00:13:26,790 [VIDEOPŘEHRÁVÁNÍ] 415 00:13:26,790 --> 00:13:29,650 -The Cílem je nyní také najít nám číslo 50, 416 00:13:29,650 --> 00:13:33,030 ale to algoritmicky, a řekněte nám, jak budete o tom. 417 00:13:33,030 --> 00:13:33,660 >> -DOBŘE. 418 00:13:33,660 --> 00:13:35,604 >> -A Pokud zjistíte, budete mít film. 419 00:13:35,604 --> 00:13:37,228 Pokud nenajdete to, dát ji zpět. 420 00:13:37,228 --> 00:13:38,044 >> -Muž. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Neslyšitelný] OK. 423 00:13:40,800 --> 00:13:46,236 Takže já jdu zkontrolovat konců nejprve zjistit, zda there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [APPLAUSE] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END Přehrávání] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Takže jasně třídění dveře vede k větší efektivitě. 429 00:13:59,760 --> 00:14:01,680 A tak, dvakrát rychleji je to, co jsem tam měl na mysli. 430 00:14:01,680 --> 00:14:03,270 A tak Jay štěstí oba časy. 431 00:14:03,270 --> 00:14:06,685 A také štěstí v tom, že poslední rok, objednal jsem nějaké disky Blu-ray 432 00:14:06,685 --> 00:14:07,560 skutečně rozdávat. 433 00:14:07,560 --> 00:14:09,768 Je mi líto, letos jsme neměl stejný Trevor. 434 00:14:09,768 --> 00:14:11,540 Ale pořád lepší byla o několik let zpět. 435 00:14:11,540 --> 00:14:14,820 A někteří z vás možná vědí to chlapík, Sean, který kdy byl v CS50, 436 00:14:14,820 --> 00:14:17,780 byl napadán s přesný Stejný problém, i když v SD, 437 00:14:17,780 --> 00:14:19,360 jak budete brzy vidět, zpět v den. 438 00:14:19,360 --> 00:14:22,622 A zjistíte, že nejenže to trvat trochu déle, než Jay, 439 00:14:22,622 --> 00:14:25,580 o něco déle, než Trevora, to bylo vlastně to skvělá příležitost 440 00:14:25,580 --> 00:14:29,820 aby se zapojily téměř všichni v dav a la Price is Right, povzbuzující 441 00:14:29,820 --> 00:14:31,889 ho najít číslo jsme hledali. 442 00:14:31,889 --> 00:14:32,930 Pojďme. se rychle podívat. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEOPŘEHRÁVÁNÍ] 444 00:14:33,320 --> 00:14:33,820 >> -DOBŘE. 445 00:14:33,820 --> 00:14:36,680 Takže váš úkol tady, Sean, je následující. 446 00:14:36,680 --> 00:14:40,860 Jsem se skrývá za tyto Dveře číslo sedm. 447 00:14:40,860 --> 00:14:45,120 Ale zastrčená v některé z těchto dveří jakož i jiné záporná čísla. 448 00:14:45,120 --> 00:14:47,500 A vaším cílem je si myslet, této horní řady čísel 449 00:14:47,500 --> 00:14:50,390 jen jako pole, nebo jen Sekvence kusů papíru 450 00:14:50,390 --> 00:14:51,510 s čísly za nimi. 451 00:14:51,510 --> 00:14:55,540 A vaším cílem je, pouze pomocí horní array tu, najděte mi číslo sedm. 452 00:14:55,540 --> 00:14:58,570 A pak jsme se k posudku jak se chodí dělat. 453 00:14:58,570 --> 00:14:59,070 -Dobře. 454 00:14:59,070 --> 00:15:00,850 -Find Nám číslo sedm, prosím. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Ne. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Five, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Směje se] 461 00:15:24,770 --> 00:15:25,910 >> To není chyták. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 One. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Směje se] 466 00:15:34,695 --> 00:15:37,861 V tomto okamžiku, skóre není příliš dobře, takže si klidně dál. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tři. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Směje se] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Pokračuj. 473 00:15:47,774 --> 00:15:50,690 Upřímně řečeno, nemůžu si pomoct, ale zajímalo co si dokonce myslet, tak-- 474 00:15:50,690 --> 00:15:51,959 >> [Směje se] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Jen horní řada, takže Máš tři doleva. 477 00:15:55,020 --> 00:15:56,200 Takže mi najít sedm. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Směje se] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Sedm. 484 00:16:26,946 --> 00:16:28,780 >> [APPLAUSE] 485 00:16:28,780 --> 00:16:29,426 >> Dobře. 486 00:16:29,426 --> 00:16:30,360 >> [END Přehrávání] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Takže jsme mohli Sledujte tyto celý den. 488 00:16:31,840 --> 00:16:34,090 A samozřejmě, některé letošní dema možná 489 00:16:34,090 --> 00:16:36,330 bude nyní skončí v příštím Letošní videa stejně. 490 00:16:36,330 --> 00:16:39,040 Takže teď pojďme vlastně zaměřit se na algoritmech 491 00:16:39,040 --> 00:16:42,140 tady, a uvidíme, jestli nemůžeme Nyní začínají formalizovat 492 00:16:42,140 --> 00:16:46,650 jak můžeme jít o získání našich dat do tohoto stavu, že je to řazeny, 493 00:16:46,650 --> 00:16:50,054 takže nakonec můžeme skutečně prohledávat efektivněji. 494 00:16:50,054 --> 00:16:52,470 A i když jdeme použít poměrně malé datové soubory, 495 00:16:52,470 --> 00:16:54,511 stejně jako osm čísel, která máme zde na desce, 496 00:16:54,511 --> 00:16:58,230 nakonec by se mohly vztahovat tytéž myšlenky 1000 vstupů, milion vstupů, 497 00:16:58,230 --> 00:17:02,100 4 miliardy vstupy, protože algoritmy se bude v podstatě stejné. 498 00:17:02,100 --> 00:17:05,359 >> A tak to je naše poslední příležitost pro dobrovolníky dnes, 499 00:17:05,359 --> 00:17:09,790 ale snad nejvíce zapojeni, kdo, pro které potřebujeme osm dobrovolníků 500 00:17:09,790 --> 00:17:12,960 přijít a jít přes nás proces třídění co bude brzy 501 00:17:12,960 --> 00:17:15,212 být na tyto hudbu zde stojí. 502 00:17:15,212 --> 00:17:16,170 Dovolte mi začít tady. 503 00:17:16,170 --> 00:17:19,692 >> Takže člověk v turquoise-- Zelená je to? 504 00:17:19,692 --> 00:17:21,130 Jste spáchání? 505 00:17:21,130 --> 00:17:21,630 Dva. 506 00:17:21,630 --> 00:17:23,069 Pojď dolů. 507 00:17:23,069 --> 00:17:23,569 DOBŘE. 508 00:17:23,569 --> 00:17:24,420 Tři. 509 00:17:24,420 --> 00:17:25,400 Čtyři. 510 00:17:25,400 --> 00:17:27,247 Nechť me-- OK, pět. 511 00:17:27,247 --> 00:17:28,830 Jste byl nominován váš přítel. 512 00:17:28,830 --> 00:17:31,340 Šest, sedm a osm. 513 00:17:31,340 --> 00:17:32,130 Pojď nahoru. 514 00:17:32,130 --> 00:17:32,630 Dobře. 515 00:17:32,630 --> 00:17:33,190 Děkuji mnohokrát. 516 00:17:33,190 --> 00:17:33,689 Pojď nahoru. 517 00:17:33,689 --> 00:17:34,790 Pojď nahoru. 518 00:17:34,790 --> 00:17:35,330 >> Dobře. 519 00:17:35,330 --> 00:17:38,890 Takže to, co máme, a to here-- je mezi těmi více neobvyklých, 520 00:17:38,890 --> 00:17:42,390 protože to bude vyžadovat, abyste humor pro mě jen trochu času. 521 00:17:42,390 --> 00:17:43,442 Ty musí být číslo jedna. 522 00:17:43,442 --> 00:17:44,150 Jak se jmenuješ? 523 00:17:44,150 --> 00:17:44,610 >> ANNAN: Annan. 524 00:17:44,610 --> 00:17:45,526 >> DAVID J. Malan: Annan. 525 00:17:45,526 --> 00:17:46,092 David. 526 00:17:46,092 --> 00:17:46,800 Jak se jmenuješ? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, jste číslo dvě. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, číslo tři. 530 00:17:52,260 --> 00:17:53,722 Stefan, číslo čtyři. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. Malan: Cynthia, číslo pět. 533 00:17:57,548 --> 00:17:58,452 [Neslyšitelných] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [Neslyšitelné]. 535 00:17:59,618 --> 00:18:00,391 David, číslo šest. 536 00:18:00,391 --> 00:18:00,890 Matt: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. Malan: Mattova číslo sedm. 538 00:18:02,160 --> 00:18:02,850 A? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. Malan: Waverly, číslo osm. 541 00:18:04,470 --> 00:18:04,970 Dobře. 542 00:18:04,970 --> 00:18:06,510 Pokud could-- Jejda. 543 00:18:06,510 --> 00:18:08,820 Pokud se vám všem, jak vaše První výzvou, tam 544 00:18:08,820 --> 00:18:10,820 osm hudební stojany Zde směrem k divákům. 545 00:18:10,820 --> 00:18:14,200 Pokud byste mohli dát své číslo na tyto hudba stojí tak, 546 00:18:14,200 --> 00:18:16,560 že line up s stejná čísla na desce. 547 00:18:16,560 --> 00:18:19,560 Tak, aby sami vypadat, že uvedení vaše čísla na tyto hudby 548 00:18:19,560 --> 00:18:21,960 stojí zde. 549 00:18:21,960 --> 00:18:25,980 Vynikající tak daleko. 550 00:18:25,980 --> 00:18:26,600 >> Výborně. 551 00:18:26,600 --> 00:18:26,890 DOBŘE. 552 00:18:26,890 --> 00:18:29,556 Takže teď, budeme se zeptat otázka v několika různými způsoby. 553 00:18:29,556 --> 00:18:31,610 Jak můžeme jít o třídění tito lidé tady nahoře? 554 00:18:31,610 --> 00:18:34,500 Protože jsme měli několik přístupů dříve, přičemž jsme byli 555 00:18:34,500 --> 00:18:36,360 druh výroby dvou různých kbelíky. 556 00:18:36,360 --> 00:18:38,842 A pak jsme byli všeobecně Sestavujeme věci dohromady. 557 00:18:38,842 --> 00:18:41,050 Jakmile jsme viděli dvě čísla že patří k sobě, 558 00:18:41,050 --> 00:18:41,975 jsme dali dohromady. 559 00:18:41,975 --> 00:18:43,350 Dva dopisy, které patří k sobě. 560 00:18:43,350 --> 00:18:45,058 >> Ale uvidíme, jestli budeme nelze formalizovat to, 561 00:18:45,058 --> 00:18:48,044 takže nakonec jsme se někteří pseudo-kód budete, 562 00:18:48,044 --> 00:18:49,710 pomocí kterého můžete vyřešit tyto problémy. 563 00:18:49,710 --> 00:18:51,870 Takže teď, jsem díval se na těchto číslech zde. 564 00:18:51,870 --> 00:18:55,030 A vidím spoustu chyb. 565 00:18:55,030 --> 00:18:57,750 Nakonec, chci, jeden na vlevo a osmi na pravé straně. 566 00:18:57,750 --> 00:19:00,650 >> A tak jsem při pohledu na tyto dva, čtyři a dva. 567 00:19:00,650 --> 00:19:02,930 A v čem je problém, samozřejmě? 568 00:19:02,930 --> 00:19:04,261 To jo. 569 00:19:04,261 --> 00:19:04,760 Tak. 570 00:19:04,760 --> 00:19:07,160 Dva zřejmě přijde dříve čtyři, takže víte, co? 571 00:19:07,160 --> 00:19:10,210 Dovolte mi, abych nejprve se chamtivý přístup, chcete-li, stejně jako problém 572 00:19:10,210 --> 00:19:13,790 nastavit one-- pokud si vzpomínáte z Standard Edition z problému nastavit jednu, 573 00:19:13,790 --> 00:19:16,820 kde jsem jen místně vyřešit problém že je tady přede mnou 574 00:19:16,820 --> 00:19:17,690 a uvidíme, kam mě to vede. 575 00:19:17,690 --> 00:19:17,870 >> DOBŘE. 576 00:19:17,870 --> 00:19:20,161 Tak dva a čtyři, nechte mě jít dopředu a jen prohodit vy dva. 577 00:19:20,161 --> 00:19:22,400 Pokud můžete fyzicky přesunout sami a váš papír, 578 00:19:22,400 --> 00:19:25,040 Myslím, že jsem vyzrál Seznam v lepším stavu. 579 00:19:25,040 --> 00:19:26,330 >> Teď, jsou dobří. 580 00:19:26,330 --> 00:19:28,480 Chystám se jít dál, čtyři a šest, vypadá dobře. 581 00:19:28,480 --> 00:19:29,110 Není problem. 582 00:19:29,110 --> 00:19:30,440 Šest a osm, na tlačítko OK. 583 00:19:30,440 --> 00:19:31,860 Osm a jeden, další problém. 584 00:19:31,860 --> 00:19:34,750 Vzhledem k tomu, co je pravda o osm a jedna? 585 00:19:34,750 --> 00:19:36,990 Jednou přijde před osmou, a tak co bychom měli dělat? 586 00:19:36,990 --> 00:19:38,090 Pojďme vyměnit tyhle dva. 587 00:19:38,090 --> 00:19:39,316 Jeden a osm. 588 00:19:39,316 --> 00:19:40,690 A teď, budu pokračovat. 589 00:19:40,690 --> 00:19:42,030 Budu hledat dál dopředu. 590 00:19:42,030 --> 00:19:42,840 A uvidíme, co se stane. 591 00:19:42,840 --> 00:19:44,680 Osm a tři, z Samozřejmě, mimo provoz. 592 00:19:44,680 --> 00:19:45,815 Pojďme swapu. 593 00:19:45,815 --> 00:19:46,940 Osm a sedm, samozřejmě. 594 00:19:46,940 --> 00:19:47,481 Mimo provoz. 595 00:19:47,481 --> 00:19:48,280 Pojďme swapu. 596 00:19:48,280 --> 00:19:49,940 Osm a pět, samozřejmě, pojďme swapu. 597 00:19:49,940 --> 00:19:50,560 Dobře. 598 00:19:50,560 --> 00:19:51,880 Seznam je seřazen. 599 00:19:51,880 --> 00:19:53,060 ano? 600 00:19:53,060 --> 00:19:54,280 >> OK, zřejmě ne. 601 00:19:54,280 --> 00:19:55,860 Ale je to trochu lepší, že jo? 602 00:19:55,860 --> 00:19:57,270 Vzhledem k tomu, upozornění, co se stalo. 603 00:19:57,270 --> 00:20:01,749 Pokaždé, když jsme provedli výměnu, menší Počet druh perkoluje takhle, 604 00:20:01,749 --> 00:20:03,790 a větší číslo perkoluje tímto způsobem, nebo budeme 605 00:20:03,790 --> 00:20:06,880 začít říkat bublal do vlevo nebo probublává doprava. 606 00:20:06,880 --> 00:20:10,080 >> Nyní, to není dost, protože přinejlepším číslo by mohl 607 00:20:10,080 --> 00:20:11,990 se posune o jedno místo vpřed, nebo v nejhorším případě, 608 00:20:11,990 --> 00:20:13,880 číslo může mít posune o jedno místo dál. 609 00:20:13,880 --> 00:20:16,369 Takže víte, co tento druh z fungovalo docela dobře tak daleko. 610 00:20:16,369 --> 00:20:17,410 Dovolte mi, abych to zkusit znovu. 611 00:20:17,410 --> 00:20:18,880 Dva a čtyři, jsou v pořádku. 612 00:20:18,880 --> 00:20:20,180 Čtyři a šest, jsou v pořádku. 613 00:20:20,180 --> 00:20:21,790 Šest a jedním, mimo provoz. 614 00:20:21,790 --> 00:20:23,007 Takže pojďme vyměnit vy dva. 615 00:20:23,007 --> 00:20:25,840 A teď, Všimněte si, že problém je začíná být trochu zase lepší. 616 00:20:25,840 --> 00:20:27,006 Šest a tři, mimo provoz. 617 00:20:27,006 --> 00:20:28,100 Pojďme vyměnit vy dva. 618 00:20:28,100 --> 00:20:29,730 Šest a sedm, jsi dobrý. 619 00:20:29,730 --> 00:20:32,230 Sedm a pět, samozřejmě, mimo provoz. 620 00:20:32,230 --> 00:20:33,920 Sedm a osm, v uvedeném pořadí. 621 00:20:33,920 --> 00:20:36,470 A teď, bych mohl potřebovat to udělat ještě několikrát. 622 00:20:36,470 --> 00:20:39,830 A ve skutečnosti, myslím, že pro sebe snad kolikrát maximálně 623 00:20:39,830 --> 00:20:41,330 Možná budu muset chodit sem a tam? 624 00:20:41,330 --> 00:20:42,390 >> Vrátíme se k tomu. 625 00:20:42,390 --> 00:20:43,700 Tak dvě a čtyři jsou stále v pořádku. 626 00:20:43,700 --> 00:20:44,940 Čtyři a jeden, ani náhodou. 627 00:20:44,940 --> 00:20:45,747 Takže, pojďme výměnu. 628 00:20:45,747 --> 00:20:47,830 A opět si všimněte, vizuálně jeden je druh probublávání 629 00:20:47,830 --> 00:20:49,163 na levé straně, pokud by mělo být. 630 00:20:49,163 --> 00:20:50,010 Čtyři a tři odkládací. 631 00:20:50,010 --> 00:20:51,330 Čtyři a šest. 632 00:20:51,330 --> 00:20:53,100 Šest a pět swapu. 633 00:20:53,100 --> 00:20:53,959 Šest a sedm. 634 00:20:53,959 --> 00:20:55,000 Sedm a osm je dobré. 635 00:20:55,000 --> 00:20:55,500 >> Dobrý. 636 00:20:55,500 --> 00:20:58,460 Dostáváme ještě lepší. 637 00:20:58,460 --> 00:20:59,130 Takže pojďme se podívat. 638 00:20:59,130 --> 00:21:00,940 Nyní máme dva a jeden. 639 00:21:00,940 --> 00:21:02,520 Samozřejmě, vyměnit. 640 00:21:02,520 --> 00:21:07,520 Dva a tři, tři a čtyři, a pět, šest a sedm, sedm a osm. 641 00:21:07,520 --> 00:21:08,020 Dobrý. 642 00:21:08,020 --> 00:21:08,730 A víte co? 643 00:21:08,730 --> 00:21:11,190 Protože jsem tam jednu změnu, dovolte mi udělat jednu kontrolu zdravý rozum. 644 00:21:11,190 --> 00:21:13,023 Nech mě jít celou cestu zpět na začátek. 645 00:21:13,023 --> 00:21:13,680 DOBŘE. 646 00:21:13,680 --> 00:21:14,750 Jeden z nich, two-- Jo, vidíš? 647 00:21:14,750 --> 00:21:15,870 Něco bylo špatně. 648 00:21:15,870 --> 00:21:18,420 Tři, čtyři, pět, šest, sedm, osm. 649 00:21:18,420 --> 00:21:21,920 A v tomto posledním průchodu, jsou pohodlné s mým teď 650 00:21:21,920 --> 00:21:23,830 prohlašovat, že to je třídit? 651 00:21:23,830 --> 00:21:24,330 DOBŘE. 652 00:21:24,330 --> 00:21:25,880 Vizuálně, že je to naprostá pravda. 653 00:21:25,880 --> 00:21:28,410 Ale to, co Funkčně se také jen tak 654 00:21:28,410 --> 00:21:31,870 V té poslední průchod, která vám umožní potvrdit, že tento seznam je opravdu 655 00:21:31,870 --> 00:21:32,660 řazeny? 656 00:21:32,660 --> 00:21:34,477 >> Co jsem udělal, nebo ne tento poslední pas? 657 00:21:34,477 --> 00:21:35,810 Diváků: nedošlo k žádným změnám. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Sorry? 659 00:21:36,120 --> 00:21:37,070 Diváků: žádné změny. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: nedošlo k žádným změnám. 661 00:21:38,653 --> 00:21:41,947 Tak to by bylo hloupé mě Udělej to stejný algoritmus znovu 662 00:21:41,947 --> 00:21:43,780 kdybych neudělal jakýkoli změní poprvé. 663 00:21:43,780 --> 00:21:45,160 A stát se nezměnil. 664 00:21:45,160 --> 00:21:47,576 Jistě, nebudu dělat Jakékoli změny podruhé. 665 00:21:47,576 --> 00:21:49,820 A tak je to teď v bezpečí říkat, seznam je tříděn. 666 00:21:49,820 --> 00:21:52,069 >> A skutečně, to je nyní něco, že budeme obecně 667 00:21:52,069 --> 00:21:56,900 hovor bublinkové řazení, přičemž po dvou, znovu opravit chyby, 668 00:21:56,900 --> 00:22:00,210 a znovu a znovu, a ti udržet tam a zpět, 669 00:22:00,210 --> 00:22:03,370 a sem a tam, dokud se neposkytujeme žádné takové swapy, na kterém místě 670 00:22:03,370 --> 00:22:07,089 můžete si být jisti, jo, já dokončil upevnění všechny chyby. 671 00:22:07,089 --> 00:22:08,630 Pojďme reset a zkusit jiný přístup. 672 00:22:08,630 --> 00:22:11,590 Pokud vy mohl vrátit do pořadí jste před chvílí, 673 00:22:11,590 --> 00:22:13,780 který vypadal takhle. 674 00:22:13,780 --> 00:22:17,640 Nyní se pojďme k přístupu, který trochu více jako zkoušku knize, 675 00:22:17,640 --> 00:22:21,122 kdy jsme byli neustále výběrem písmeno abecedy 676 00:22:21,122 --> 00:22:22,830 že jsme trochu chtěli řešit další. 677 00:22:22,830 --> 00:22:26,420 Možná to byl vysoký dopis, Stejně jako, nebo s nízkou písmeno Z. 678 00:22:26,420 --> 00:22:28,170 >> Takže každý je zpět v tomto pořadí. 679 00:22:28,170 --> 00:22:29,800 A teď mě to udělat. 680 00:22:29,800 --> 00:22:34,880 Pojďme se podívat, vím, že mám osm čísla zde. 681 00:22:34,880 --> 00:22:37,410 Chystám se jít dopředu a jen záměrně zvolte 682 00:22:37,410 --> 00:22:38,520 nejmenší prvky. 683 00:22:38,520 --> 00:22:38,760 Je to tak? 684 00:22:38,760 --> 00:22:39,801 To se zdá být intuitivní taky. 685 00:22:39,801 --> 00:22:42,560 Proč mi připadá nejmenší prvek, vložte ji tam, kam patří, 686 00:22:42,560 --> 00:22:45,280 pak dostanete další nejmenší prvek, dal je tam, kam patří, a jen zopakovat. 687 00:22:45,280 --> 00:22:46,820 >> Vzhledem k tomu, intuitivně, který by měl fungovat také. 688 00:22:46,820 --> 00:22:48,441 Tak čtyři, to je docela malý počet. 689 00:22:48,441 --> 00:22:49,940 Jdu si vzpomenout, kde to je. 690 00:22:49,940 --> 00:22:50,523 Počkej chvíli. 691 00:22:50,523 --> 00:22:51,577 Two je menší. 692 00:22:51,577 --> 00:22:53,910 Dovolte mi nyní vzpomenout, kde dvou je, a zapomenout na čtyři. 693 00:22:53,910 --> 00:22:55,050 Vyřídíme to později. 694 00:22:55,050 --> 00:22:56,460 Šest, nemám zájem. 695 00:22:56,460 --> 00:22:57,810 Osm, nemám zájem. 696 00:22:57,810 --> 00:22:59,780 Jedním z nich je můj nový malý počet. 697 00:22:59,780 --> 00:23:01,470 Takže budu pamatovat, kde jeden je. 698 00:23:01,470 --> 00:23:02,534 Tři, nemám zájem. 699 00:23:02,534 --> 00:23:03,450 Sedm, nemám zájem. 700 00:23:03,450 --> 00:23:04,530 Five, nemám zájem. 701 00:23:04,530 --> 00:23:07,390 >> Takže bez pádu fáze v tomto roce, 702 00:23:07,390 --> 00:23:09,890 Chystám se chytit počet one-- a to, co bylo zase Vaše jméno? 703 00:23:09,890 --> 00:23:10,150 >> ANNAN: Annan. 704 00:23:10,150 --> 00:23:11,220 >> DAVID J. Malan: Annan. 705 00:23:11,220 --> 00:23:13,540 A kdybyste se mnou na začátek seznamu 706 00:23:13,540 --> 00:23:14,870 pojďme tě tam, kam patříte. 707 00:23:14,870 --> 00:23:16,080 Bohužel-- Jak se jmenujete? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. Malan: Stefan je v cestě. 710 00:23:18,191 --> 00:23:23,490 Takže než Stefan řeší tento Problém, co bychom měli dělat? 711 00:23:23,490 --> 00:23:25,412 Co budeme dělat s Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Diváků: [Neslyšitelné]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Takže jsme mohli udělat. 715 00:23:28,850 --> 00:23:31,730 Mohli bychom nějak vzít Stefan a jeho čtyři, a jen dát to do proměnné 716 00:23:31,730 --> 00:23:33,530 a držet se jí za určité množství času, 717 00:23:33,530 --> 00:23:35,220 čímž se vytvoří prostor pro číslo jedna. 718 00:23:35,220 --> 00:23:36,280 A to není špatné. 719 00:23:36,280 --> 00:23:39,270 Mohl bych navrhnout, proč ne jsme jen dát tu Stefana? 720 00:23:39,270 --> 00:23:41,610 Proč by to mohlo porušit jeden nápadů jsme začali 721 00:23:41,610 --> 00:23:44,830 mluví o minule, minulý týden? 722 00:23:44,830 --> 00:23:45,330 To jo? 723 00:23:45,330 --> 00:23:45,740 >> Diváků: [Neslyšitelné]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Neexistuje žádný index pro něj. 725 00:23:46,860 --> 00:23:49,735 Pokud si myslíte o tom, opravdu, jako pole, to je jako negativní, 726 00:23:49,735 --> 00:23:52,900 takže není žádná paměťová vlastně Zde, pokud je to skutečně pole, 727 00:23:52,900 --> 00:23:55,090 jako jsme deklarovali minulý týden v přednášce. 728 00:23:55,090 --> 00:23:56,250 Takže bychom neměli dělat. 729 00:23:56,250 --> 00:23:57,340 Můžeme uložit jej do proměnné. 730 00:23:57,340 --> 00:23:57,820 >> Nebo víte co? 731 00:23:57,820 --> 00:23:59,153 Slyšel jsem, že někdo jiný to naznačují. 732 00:23:59,153 --> 00:24:01,020 Co jiného můžeme dělat s Stefan? 733 00:24:01,020 --> 00:24:03,770 Proč jsme ho jen vystěhovat a ho přes číslo jedna, kde byl. 734 00:24:03,770 --> 00:24:05,170 Takže pokud chcete jít tam. 735 00:24:05,170 --> 00:24:07,300 A skutečně, to je docela dobré řešení. 736 00:24:07,300 --> 00:24:10,480 Nyní na jedné straně, jsem druh z dělal problém ještě horší. 737 00:24:10,480 --> 00:24:13,650 Čtyři je nyní dál od místa, kde by měla být. 738 00:24:13,650 --> 00:24:14,900 To by mělo být k tomuto polovinu. 739 00:24:14,900 --> 00:24:16,100 >> Ale víte co? 740 00:24:16,100 --> 00:24:17,630 To by mohlo být smůla. 741 00:24:17,630 --> 00:24:18,822 Možná, že číslo osm díval. 742 00:24:18,822 --> 00:24:20,530 A tak, možná bychom se dostali štěstí, 743 00:24:20,530 --> 00:24:22,460 a tlačil osmi blíže ke konci. 744 00:24:22,460 --> 00:24:24,710 Takže na konci dne, docela to všechny průměry ven. 745 00:24:24,710 --> 00:24:26,085 Nemusíme se starat o čtyři. 746 00:24:26,085 --> 00:24:29,400 Vše o co se starám právě teď výběru nejmenší prvek. 747 00:24:29,400 --> 00:24:32,030 >> A teď, co budu udělat, je zapomenout na číslo jedna 748 00:24:32,030 --> 00:24:35,160 natrvalo, protože vím, že Seznam za mnou je nyní seřazeny. 749 00:24:35,160 --> 00:24:36,720 Takže můj seznam byl dříve velikosti osm. 750 00:24:36,720 --> 00:24:37,720 Teď je to o velikosti sedm. 751 00:24:37,720 --> 00:24:40,340 Takže můj problém je dostat menší, ale přesto lineárně. 752 00:24:40,340 --> 00:24:43,022 Takže teď, budu vyberte proud nejmenší prvek, dva. 753 00:24:43,022 --> 00:24:46,520 Šest, osm, čtyři, tři, sedm, pět. 754 00:24:46,520 --> 00:24:47,770 To byl ten nejmenší prvek. 755 00:24:47,770 --> 00:24:49,416 Tak co mám dělat with-- co byl opět Vaše jméno? 756 00:24:49,416 --> 00:24:49,760 >> JOSEPH: Joseph. 757 00:24:49,760 --> 00:24:50,085 >> DAVID J. Malan: Joseph? 758 00:24:50,085 --> 00:24:52,000 Budeme nechat Josefa na místě. 759 00:24:52,000 --> 00:24:54,842 Teď, budu předstírat že tyto lidi are-- dobře, 760 00:24:54,842 --> 00:24:56,550 Vím, že tyto dvě je již řazeno. 761 00:24:56,550 --> 00:24:58,424 Pojďme se nyní zaměřují na Zbývající část seznamu. 762 00:24:58,424 --> 00:25:00,080 Šest je aktuální nejmenší. 763 00:25:00,080 --> 00:25:01,190 Osm je větší. 764 00:25:01,190 --> 00:25:02,970 Čtyři je nyní aktuální nejmenší. 765 00:25:02,970 --> 00:25:04,762 Tři je nyní aktuální nejmenší. 766 00:25:04,762 --> 00:25:07,720 A tak teď, budu vybrat tři, kdo je-- jaké je vaše jméno znovu? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. Malan: Serena, kdybyste mohl urvat si číslo a swapu with-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: Kalsang. 770 00:25:11,550 --> 00:25:12,940 DAVID J. Malan: Kalsang. 771 00:25:12,940 --> 00:25:15,220 Pojď zpátky, a my jsme chystá vyměnit ty dva. 772 00:25:15,220 --> 00:25:17,360 A teď, pojďme dát na autopilota to. 773 00:25:17,360 --> 00:25:21,589 Chystám se jít a nechat to na vás kluci zvolit nejbližší menší prvky. 774 00:25:21,589 --> 00:25:22,380 Dun, šedivý, šedivý, dun. 775 00:25:22,380 --> 00:25:24,560 Číslo čtyři, co byste měli dělat? 776 00:25:24,560 --> 00:25:26,261 Výborně. 777 00:25:26,261 --> 00:25:27,760 Teď, budu dělat další přihrávka. 778 00:25:27,760 --> 00:25:28,590 Dun, šedivý, šedivý, dun. 779 00:25:28,590 --> 00:25:31,465 Vidím pěti je další nejmenší. 780 00:25:31,465 --> 00:25:32,840 Teď, budu trvat další přihrávka. 781 00:25:32,840 --> 00:25:33,631 Dun, šedivý, šedivý, dun. 782 00:25:33,631 --> 00:25:34,880 Šest je nejmenší. 783 00:25:34,880 --> 00:25:35,520 Dobrý. 784 00:25:35,520 --> 00:25:36,585 Sedm je nejmenší. 785 00:25:36,585 --> 00:25:37,085 Žádná změna. 786 00:25:37,085 --> 00:25:38,630 Osm je nejmenší. 787 00:25:38,630 --> 00:25:39,170 Hotovo. 788 00:25:39,170 --> 00:25:43,900 >> Takže to, co jsme právě provádí opakovaně výběr jednoho prvku za sebou 789 00:25:43,900 --> 00:25:47,230 je implementovat něco, co jsme bude formalizovat jako výběr druhu. 790 00:25:47,230 --> 00:25:49,120 A to je možná i jednodušší na vysvětlení, 791 00:25:49,120 --> 00:25:51,310 v tom, že doslova po vás chtít udělat, je jen udržet 792 00:25:51,310 --> 00:25:54,700 tam a zpět přes seznam výběru, další nejmenší prvek, 793 00:25:54,700 --> 00:25:55,720 dokud máte hotovo. 794 00:25:55,720 --> 00:25:58,650 >> Takže je to ještě jednodušší, snad intuitivně, než poslední. 795 00:25:58,650 --> 00:26:00,020 Zkusme poslední jeden. 796 00:26:00,020 --> 00:26:03,060 Pokud vy sami mohli obnovit do následujících poloh 797 00:26:03,060 --> 00:26:08,600 jeden poslední čas, uvidíme, jestli nemůžeme Nyní formalizovat jednu další postup. 798 00:26:08,600 --> 00:26:12,857 Ve skutečnosti, by někdo tam chtěl navrhnout, 799 00:26:12,857 --> 00:26:14,440 jak jinak bychom mohli jít asi dělá? 800 00:26:14,440 --> 00:26:17,439 Bez hodil out módní slova nebo seřadit z odpovědí, které jsou již známy, 801 00:26:17,439 --> 00:26:19,689 jen intuitivně, co jsme mohli dělat? 802 00:26:19,689 --> 00:26:21,635 >> Diváků: [Neslyšitelné]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. Malan: Jo. 804 00:26:22,510 --> 00:26:24,620 Takže tam je tam nějaký velký intuice. 805 00:26:24,620 --> 00:26:28,020 Dobré věci se zdá, tak daleko se stalo v oblasti počítačové vědy, když jsme se rozdělit 806 00:26:28,020 --> 00:26:30,832 a dobýt problém dělení je na polovinu a půl na půl. 807 00:26:30,832 --> 00:26:32,540 A tak my, mohl začít dělat to. 808 00:26:32,540 --> 00:26:35,754 A ve skutečnosti, že to bude, budeme vidět, jeden z našich nejlepších řešení dosud. 809 00:26:35,754 --> 00:26:37,420 Ale pojďme se vrátit k tomu zanedlouho. 810 00:26:37,420 --> 00:26:40,500 Ve skutečnosti, budeme dělat že o něco později tento týden. 811 00:26:40,500 --> 00:26:42,180 Co jiného můžeme dělat to vyřešit? 812 00:26:42,180 --> 00:26:44,647 Takže všichni tady je v zdánlivě náhodném pořadí. 813 00:26:44,647 --> 00:26:45,230 Ty víš co? 814 00:26:45,230 --> 00:26:48,320 Spíše než jít tam a zpět, sem a tam, tam a zpět 815 00:26:48,320 --> 00:26:50,624 pokaždé, to cítí jako Dělám hodně chůze. 816 00:26:50,624 --> 00:26:52,790 Proč jsem se začít na začátek seznamu 817 00:26:52,790 --> 00:26:54,960 a jen dát čtyři kam patří? 818 00:26:54,960 --> 00:26:59,680 Dovolte mi tedy předpokládat, že pro tuto chvíli můj seznam je pouze tento první prvek. 819 00:26:59,680 --> 00:27:04,937 Se čtyřmi řazeny v tomto okamžiku v čase, pokud všechno mě zajímá, je tady všechno? 820 00:27:04,937 --> 00:27:06,520 To je trochu triviálně pravda, že jo? 821 00:27:06,520 --> 00:27:10,000 Stejně jako v seznamu, který obsahuje jedno číslo, a že číslo čtyři je samozřejmě seřazeny. 822 00:27:10,000 --> 00:27:13,070 >> Takže mi dovolte stanovit že tento seznam je seřazen. 823 00:27:13,070 --> 00:27:15,090 Ale teď mám zbytek tohoto seznamu. 824 00:27:15,090 --> 00:27:17,240 Takže teď, jsem se setkávají dva. 825 00:27:17,240 --> 00:27:21,690 Kde se dva zjevně patří s ohledem na čtyři? 826 00:27:21,690 --> 00:27:22,580 Před čtyři. 827 00:27:22,580 --> 00:27:23,862 Takže to, co můžu dělat? 828 00:27:23,862 --> 00:27:24,820 Co se jmenuješ? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, pokud byste mohli krok zpět 831 00:27:26,030 --> 00:27:27,790 na chvilku se svým číslem. 832 00:27:27,790 --> 00:27:31,130 A teď, co by měl dělat Stefan tady? 833 00:27:31,130 --> 00:27:33,720 Pojďme posun Stefana tady. 834 00:27:33,720 --> 00:27:35,520 A teď, ať Joseph přijít sem. 835 00:27:35,520 --> 00:27:39,660 A nyní mi dovolte, abych tvrdí, že Všechno je tu řazeny. 836 00:27:39,660 --> 00:27:42,474 Takže, Podobný výsledek, ale zásadně odlišný přístup. 837 00:27:42,474 --> 00:27:44,140 Ani jsem se podíval, co tam dole. 838 00:27:44,140 --> 00:27:46,310 Jen jsem pokračovat v užívání prvky jak se jim předali mi, 839 00:27:46,310 --> 00:27:47,240 a vypořádat se s nimi. 840 00:27:47,240 --> 00:27:48,330 >> Takže teď, vidím číslo šest. 841 00:27:48,330 --> 00:27:51,110 Kde se číslo šest patří? 842 00:27:51,110 --> 00:27:53,250 Máme dvě, čtyři, šest. 843 00:27:53,250 --> 00:27:54,800 Přesně tam, kde ona je právě teď. 844 00:27:54,800 --> 00:27:57,750 Takže nechme to samo o sobě, a teď tvrdí, že této části seznamu 845 00:27:57,750 --> 00:27:58,772 Nyní je seřazen. 846 00:27:58,772 --> 00:28:01,230 A tak, to cítí zásadně liší v tom, já jsem jen 847 00:28:01,230 --> 00:28:05,230 pohybující se v seznamu zde lineárně, a já jsem se nikdy zdvojnásobení zpět. 848 00:28:05,230 --> 00:28:05,730 Ano. 849 00:28:05,730 --> 00:28:06,230 Dobře. 850 00:28:06,230 --> 00:28:08,190 Tak osm, kam patříte? 851 00:28:08,190 --> 00:28:08,730 Právě tady. 852 00:28:08,730 --> 00:28:09,310 Perfektní. 853 00:28:09,310 --> 00:28:10,210 Takže teď, jedním. 854 00:28:10,210 --> 00:28:10,900 Uh-oh. 855 00:28:10,900 --> 00:28:13,010 Tento pocit, že je to bude drahé. 856 00:28:13,010 --> 00:28:15,690 Nyní, v předchozím algoritmu, Jen jsem vyměnil lidi. 857 00:28:15,690 --> 00:28:18,648 Tak jsem mu mohl dát celou cestu na začátek, ale pak se stěhoval Joseph. 858 00:28:18,648 --> 00:28:21,450 Ale když jsem se přesunout Joseph, nyní co se děje, aby být špatně? 859 00:28:21,450 --> 00:28:24,250 >> A teď, jsem nějak undone-- jsem vzít jeden krok vpřed a poté 860 00:28:24,250 --> 00:28:26,300 jeden krok zpátky, protože teď Josef by bylo mimo provoz. 861 00:28:26,300 --> 00:28:26,830 Tak jdeme na to. 862 00:28:26,830 --> 00:28:29,150 Pokud byste mohli mít číslo jedna a krok zpět jen na chvíli. 863 00:28:29,150 --> 00:28:30,490 Jak můžeme put-- co byl opět Vaše jméno? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. Malan: Annan na místě? 866 00:28:32,610 --> 00:28:36,091 Co se má stát, pokud jde na dvě, čtyři, šest a osm? 867 00:28:36,091 --> 00:28:37,570 Ti všichni potřebují posunout. 868 00:28:37,570 --> 00:28:42,590 Takže pokud osmi chtěli posunout první, pak šest, potom čtyři, pak dvě. 869 00:28:42,590 --> 00:28:45,380 A pak Annan, pokud byste Líbí se přijít sem, dobře. 870 00:28:45,380 --> 00:28:47,760 Ale tady, právě jsme druh zaplatil cenu 871 00:28:47,760 --> 00:28:49,510 na jiném místě v algoritmu. 872 00:28:49,510 --> 00:28:52,550 Zatímco minule s výběrem třídění, a dokonce i bublinkové řazení, 873 00:28:52,550 --> 00:28:54,700 Jdu zpátky a tam, tam a zpět, 874 00:28:54,700 --> 00:28:58,360 která je jistě sčítání časově a doslova postupně. 875 00:28:58,360 --> 00:29:00,660 >> Insertion sort, nejprve pohled, vypadá, že je to 876 00:29:00,660 --> 00:29:05,150 výborný chytřejší, v tom, že jsem jen dělat pomalý, postupný pokrok, 877 00:29:05,150 --> 00:29:07,120 ale nehodlám to tam a zpět. 878 00:29:07,120 --> 00:29:09,410 Ale pokud někdo skutečně mimo provoz, oznámení 879 00:29:09,410 --> 00:29:10,840 všechny práce jsem musel udělat. 880 00:29:10,840 --> 00:29:14,750 Musel jsem se přesunout polovinu seznamu jen aby se prostor pro číslo jedna. 881 00:29:14,750 --> 00:29:16,790 Takže je to stejná částka práce dosud ji 882 00:29:16,790 --> 00:29:18,690 cítí, jen jiný druh práce. 883 00:29:18,690 --> 00:29:19,370 >> Pojďme pokračovat. 884 00:29:19,370 --> 00:29:22,657 Takže teď víme, že každý mezi jedním a osm jsou seřazeny. 885 00:29:22,657 --> 00:29:23,740 Tady mám číslo tři. 886 00:29:23,740 --> 00:29:25,864 Máte-li rádi vyzvednout číslo tři, jeden krok zpět. 887 00:29:25,864 --> 00:29:28,260 A co vy musíte udělat? 888 00:29:28,260 --> 00:29:28,760 Jo. 889 00:29:28,760 --> 00:29:33,070 Tak to je ještě jeden, dva, tři kroky. 890 00:29:33,070 --> 00:29:36,010 Tři jednotky času, který právě stály mě, takže tři mohou nyní vejde. 891 00:29:36,010 --> 00:29:37,460 A konečně, sedm. 892 00:29:37,460 --> 00:29:39,730 >> Pojďme dál a mají si vzít krok zpět. 893 00:29:39,730 --> 00:29:42,780 Toto je teprve ve chvíli, aby nám stát jedna jednotka času, ale to je v pořádku. 894 00:29:42,780 --> 00:29:44,170 A teď, pět děje na být o něco dražší. 895 00:29:44,170 --> 00:29:45,340 Pokud byste chtěli udělat krok zpět. 896 00:29:45,340 --> 00:29:48,380 Musíme se pohybovat osm, a sedm a šest. 897 00:29:48,380 --> 00:29:50,749 A pak se všichni je nyní seřazeny. 898 00:29:50,749 --> 00:29:52,290 Tak velká ruka našim dobrovolníkům zde. 899 00:29:52,290 --> 00:29:53,554 Děkuji mnohokrát. 900 00:29:53,554 --> 00:29:56,220 >> [APPLAUSE] 901 00:29:56,220 --> 00:29:56,860 >> Děkuji vám všem. 902 00:29:56,860 --> 00:29:57,520 Děkuji vám všem. 903 00:29:57,520 --> 00:30:02,940 Tak uvidíme, teď jen, jak nákladné to všechno bylo. 904 00:30:02,940 --> 00:30:06,210 Pojďme zvážit možná nejjednodušší z nich, bublinkové řazení. 905 00:30:06,210 --> 00:30:09,950 A já říkám nejjednodušší, jen proto, můžete vyřešit ji nenasytně pouhým 906 00:30:09,950 --> 00:30:11,660 vyřešit pairwise problém. 907 00:30:11,660 --> 00:30:13,720 Opravit pairwise problém Zde, znovu a znovu 908 00:30:13,720 --> 00:30:17,680 a znovu, opakování tolik kolikrát je skutečně potřebují, aby. 909 00:30:17,680 --> 00:30:21,050 >> Tak to dopadá, že s bublinou druhu, dobře, 910 00:30:21,050 --> 00:30:25,820 kolik kroků musím přijmout První průchod z tohoto algoritmu? 911 00:30:25,820 --> 00:30:30,850 Mohl bych take-- pojďme see-- jednoho, dva, tři, čtyři, pět, šest, sedm. 912 00:30:30,850 --> 00:30:32,190 A je tu osm elementů sem. 913 00:30:32,190 --> 00:30:35,280 Takže je to jako n minus 1 kroků k se od začátku seznamu 914 00:30:35,280 --> 00:30:36,380 na konec seznamu. 915 00:30:36,380 --> 00:30:41,350 >> Ale s výběrem Třídit, připomenout, že já jsem znovu a znovu Výběr prvků 916 00:30:41,350 --> 00:30:44,590 a znovu to nejmenší, Dávám to na místě, 917 00:30:44,590 --> 00:30:46,616 ale pak jsem nejsem dívá za mnou znovu. 918 00:30:46,616 --> 00:30:49,490 Takže si myslím, že je to trochu jasnější pak, že poprvé, mohu 919 00:30:49,490 --> 00:30:52,680 muset vzít všechny n minus 1 stupni najít nejmenší prvek. 920 00:30:52,680 --> 00:30:55,920 Pak jsem dal je na místě, a já vypudit ten, kdo tu byl předtím. 921 00:30:55,920 --> 00:30:57,500 >> Ale pak jsem si nemusím držet při pohledu na tento prvek, 922 00:30:57,500 --> 00:30:59,040 protože vím, že je to Už nejmenší. 923 00:30:59,040 --> 00:31:01,581 Takže teď, můžu se podívat na právě sedmi elementů a pak šest prvky, 924 00:31:01,581 --> 00:31:03,290 pak pět prvků, pak čtyři elementy. 925 00:31:03,290 --> 00:31:06,900 A tak matematicky, pokud n je počet prvků nebo čísel 926 00:31:06,900 --> 00:31:11,990 že jsme začali s, ktere si lze predstavit že se jedná o stejné jako n minus 1, 927 00:31:11,990 --> 00:31:14,250 a n minus 2 stupně, a n minus 3 stupně, 928 00:31:14,250 --> 00:31:16,780 plus n minus 4 kroky, a to tím až na doraz jednom kroku. 929 00:31:16,780 --> 00:31:18,160 A já jsem na poslední osobu. 930 00:31:18,160 --> 00:31:20,650 >> A pokud si vzpomínáte, že hodně Statistiky knihy nebo matematické knihy 931 00:31:20,650 --> 00:31:24,730 mít ty vzorce na straně Vázaná zadní nebo přední z nich, 932 00:31:24,730 --> 00:31:27,690 Ukazuje se, že této sérii může být vyjádřena jednodušeji 933 00:31:27,690 --> 00:31:28,857 jak n krát n minus 1 nad 2. 934 00:31:28,857 --> 00:31:31,273 A to je v pořádku, pokud to není v popředí své mysli. 935 00:31:31,273 --> 00:31:32,420 To je však skutečně pravda. 936 00:31:32,420 --> 00:31:34,449 To je jen jednodušší způsob psaní. 937 00:31:34,449 --> 00:31:36,240 A pak, pokud si myslíte, zpět na základní škole, 938 00:31:36,240 --> 00:31:38,698 když jste právě spuštění násobí věci, to samozřejmě, 939 00:31:38,698 --> 00:31:41,820 právě n druhou minus n děleno 2. 940 00:31:41,820 --> 00:31:44,772 Všechno, co jsem udělal, je rozšířit výrazy tam. 941 00:31:44,772 --> 00:31:46,730 A tak se pojďme přepsat trochu jinak. 942 00:31:46,730 --> 00:31:49,780 To n čtverečkované dělí o 2 mínus N / 2. 943 00:31:49,780 --> 00:31:53,270 >> Takže znovu, jsem jen trochu uplatnění někteří aritmetický pravidla zde. 944 00:31:53,270 --> 00:31:57,140 Nevšimnout teď, že největší termín v tomto výrazu, abych tak řekl, 945 00:31:57,140 --> 00:31:58,540 je to, že n na druhou. 946 00:31:58,540 --> 00:32:02,910 Takže ano, je to n kvadrát děleno 2, mínus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Obecně ale, je-li n je Bude to velká hodnota, 948 00:32:05,080 --> 00:32:08,740 Budu tvrdit, že n čtvercový bude dominantním faktorem. 949 00:32:08,740 --> 00:32:10,490 Je to jen bude větší přispěvatel 950 00:32:10,490 --> 00:32:12,877 na počtu kroků, než n / 2. 951 00:32:12,877 --> 00:32:13,960 Tak co tím myslím? 952 00:32:13,960 --> 00:32:16,795 Zkusme si jednoduchý příklad, a to i ačkoli matematika dostane trochu velký. 953 00:32:16,795 --> 00:32:20,210 >> Takže předpokládám, že jsme měli 1 milion lidí na jevišti, nebo 1 milion věcí 954 00:32:20,210 --> 00:32:21,320 že chceme uspořádat. 955 00:32:21,320 --> 00:32:23,730 Pojďme zapojte milion do přesně v tomto vzorci 956 00:32:23,730 --> 00:32:27,230 vidět, kolik kroků to trvá celkem třídit milion prvky pomocí řekněme, 957 00:32:27,230 --> 00:32:28,560 výběr třídění. 958 00:32:28,560 --> 00:32:30,760 >> Takže budeme mít stejný vzorec jako předtím. 959 00:32:30,760 --> 00:32:34,120 Já bych připojit milion, tak, že jsem si milión čtverečkované děleno 2, 960 00:32:34,120 --> 00:32:35,990 minus jeden milion děleno 2. 961 00:32:35,990 --> 00:32:40,180 Pokud se mi, že matematiku v předstihu tady máme 500 miliard 962 00:32:40,180 --> 00:32:47,460 minus 500000, který nám dává 499999500000, 963 00:32:47,460 --> 00:32:49,270 což je zatraceně velký. 964 00:32:49,270 --> 00:32:54,370 >> Ve skutečnosti, pokud si porovnat teď 499000000000, 999000000, 965 00:32:54,370 --> 00:33:01,210 500000 proti naší původní hodnoty, 500000000000, je to tak zatraceně blízko. 966 00:33:01,210 --> 00:33:06,850 Je to tak? n čtverečkované děleno 2 dává us-- nebo spíše, n čtverečkované děleno 2 967 00:33:06,850 --> 00:33:08,370 dal nám 500 miliard. 968 00:33:08,370 --> 00:33:13,510 To je zatraceně blízko na 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 což znamená, že se odečte off 500000, nebo obecněji, odečtením off 970 00:33:17,970 --> 00:33:20,010 n čtverečkované, není opravdu velký problém. 971 00:33:20,010 --> 00:33:22,490 N čtvercový činí tyto Čísla rostou opravdu rychle. 972 00:33:22,490 --> 00:33:25,790 >> Nyní, to je důležité jen do té míry jako my, jako počítačových vědců, 973 00:33:25,790 --> 00:33:29,350 jsou obecně nebude tolik péče o nuance těchto vzorcích 974 00:33:29,350 --> 00:33:31,400 a co přesně přesné odpovědi. 975 00:33:31,400 --> 00:33:33,390 Víme jen, že péče, víte co? 976 00:33:33,390 --> 00:33:37,810 Na konci dne, tento vzorec je na pořadí n čtvercový. 977 00:33:37,810 --> 00:33:39,350 >> Ano, jsme vydělením 2 v tam. 978 00:33:39,350 --> 00:33:41,360 Ano, budeme odečítat z n minus 2. 979 00:33:41,360 --> 00:33:46,860 Ale na konci dne, termín že nás opravdu bolí a stojí nás 980 00:33:46,860 --> 00:33:48,995 hodně kroků, je to, že náměstí termín. 981 00:33:48,995 --> 00:33:51,370 A tak to, co počítačový vědec bude obecně dělat 982 00:33:51,370 --> 00:33:54,160 je ignorovat všechny ty menších objednávek podmínky, 983 00:33:54,160 --> 00:33:56,900 a jen se podívejte na ten, který nejvíce přispívá k nákladům. 984 00:33:56,900 --> 00:34:00,530 >> A to je pěkné, protože můžeme nyní hovořit v mnohem větší obecnosti 985 00:34:00,530 --> 00:34:02,470 o algoritmy, a mohou porovnávat je. 986 00:34:02,470 --> 00:34:04,550 A skutečnost, že jsem O použití tohoto je záměrné. 987 00:34:04,550 --> 00:34:06,680 Když řeknu, že na objednávce o, já jsem konkrétně 988 00:34:06,680 --> 00:34:09,560 s odkazem na něco volal velký O. A big O 989 00:34:09,560 --> 00:34:14,090 je zápis, že počítač vědec používá k popisu 990 00:34:14,090 --> 00:34:16,710 horní mez něco. 991 00:34:16,710 --> 00:34:21,150 >> Takže když říkáte, že algoritmus je ve velkém O z n na druhou, 992 00:34:21,150 --> 00:34:23,380 jak jsem navrhl jen před chvílí, že prostředky 993 00:34:23,380 --> 00:34:27,710 že pokud jde o její chod úvazek nebo jeho účinnost, 994 00:34:27,710 --> 00:34:30,090 to znamená v řádu n druhou kroků. 995 00:34:30,090 --> 00:34:31,420 Možná víc, možná méně. 996 00:34:31,420 --> 00:34:33,435 Ale to je na pořadí n na druhou. 997 00:34:33,435 --> 00:34:34,560 A to je horní mez. 998 00:34:34,560 --> 00:34:36,530 Není to bude více bolestivé než to. 999 00:34:36,530 --> 00:34:40,800 Není to bude n krychlový, nebo 2 na n, nebo něco mnohem většího. 1000 00:34:40,800 --> 00:34:43,800 Jedná se o horní mez Na co to je cena. 1001 00:34:43,800 --> 00:34:46,150 Takže vzhledem k tomu, pojďme zvážit jen několik příkladů. 1002 00:34:46,150 --> 00:34:49,820 A to je jen konečný seznam velmi časté provozní doba 1003 00:34:49,820 --> 00:34:52,870 pro algoritmy, který je určen k ilustrativní některých věcí, které jsme 1004 00:34:52,870 --> 00:34:53,600 Viděl už. 1005 00:34:53,600 --> 00:34:58,060 >> Tak například v případě výběr třídění, co jsem tvrdil zde 1006 00:34:58,060 --> 00:35:02,250 je běh této výběrem Třídit je čas je na pořadí n na druhou. 1007 00:35:02,250 --> 00:35:06,260 V nejhorším případě, budu mít celá parta náhodných čísel zde. 1008 00:35:06,260 --> 00:35:08,600 A jak jsme viděli matematicky, když jsem chůzi držet 1009 00:35:08,600 --> 00:35:11,310 v seznamu, a to prostřednictvím seznam, výběr příští nejmenší 1010 00:35:11,310 --> 00:35:14,410 znovu a znovu prvek, pokud I vlastně zapsat všechny kroky 1011 00:35:14,410 --> 00:35:18,750 Beru, jak jsem navrhl formulaically předtím, je to na objednávku n čtvercové 1012 00:35:18,750 --> 00:35:20,370 kroky, které beru. 1013 00:35:20,370 --> 00:35:24,520 >> A ukázalo se, že bublina třídění a insertion sort 1014 00:35:24,520 --> 00:35:27,370 jsou stejně pomalu v nejhorším případě. 1015 00:35:27,370 --> 00:35:32,040 Vezměme si například, insertion sort, úplně poslední algoritmus jsme se zabývali, 1016 00:35:32,040 --> 00:35:35,500 který měl s námi podívat na prvek, a vložte ji tam, kam patří. 1017 00:35:35,500 --> 00:35:38,720 A pak jsme se podívali na další prvek, a vložil ji tam, kam patří. 1018 00:35:38,720 --> 00:35:40,990 >> Tak zváží nejlepší možný scénář. 1019 00:35:40,990 --> 00:35:45,590 Dejme tomu, že jsem měl můj dobrovolníci line up doslova jako je tento, jedna až osm, 1020 00:35:45,590 --> 00:35:47,440 již řazeno. 1021 00:35:47,440 --> 00:35:51,300 Kolik kroků je insertion sort bude trvat třídit osm lidí, 1022 00:35:51,300 --> 00:35:55,640 když dorazí na pódiu vypadající takhle? 1023 00:35:55,640 --> 00:35:57,410 >> Osm lidí již řazeno. 1024 00:35:57,410 --> 00:35:58,760 A já používám insertion sort. 1025 00:35:58,760 --> 00:36:02,180 Že poslední z algoritmů. 1026 00:36:02,180 --> 00:36:03,640 Dobře, pojďme reenact opravdu rychle. 1027 00:36:03,640 --> 00:36:05,504 Takže když začnu tady, vidím jeden. 1028 00:36:05,504 --> 00:36:06,420 Kde vůbec nepatří? 1029 00:36:06,420 --> 00:36:07,730 Patří tady. 1030 00:36:07,730 --> 00:36:08,330 Vidím dva. 1031 00:36:08,330 --> 00:36:09,660 Kde dvou patří? 1032 00:36:09,660 --> 00:36:10,260 Právě tady. 1033 00:36:10,260 --> 00:36:10,900 Vidím tři. 1034 00:36:10,900 --> 00:36:11,920 Kde Tři patří? 1035 00:36:11,920 --> 00:36:12,480 Právě tady. 1036 00:36:12,480 --> 00:36:13,100 >> Vidím čtyři. 1037 00:36:13,100 --> 00:36:13,600 Právě tady. 1038 00:36:13,600 --> 00:36:15,660 Pět, šest, sedm, osm. 1039 00:36:15,660 --> 00:36:17,320 Neexistuje žádný důvod, aby se opakuji. 1040 00:36:17,320 --> 00:36:21,260 A tak, jak mnoho kroků je to, že, pokud jde o n? 1041 00:36:21,260 --> 00:36:23,870 Je to na objednávku n schůdky, že jo? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Ale vzal jsem lineární číslo kroků, a teď jsem udělal. 1043 00:36:27,567 --> 00:36:28,900 Tak to je nejlepší případ, ačkoli. 1044 00:36:28,900 --> 00:36:29,983 Co nejhorším případě? 1045 00:36:29,983 --> 00:36:32,730 Jaké bylo osm tam, a sedm bylo tam dole, 1046 00:36:32,730 --> 00:36:35,840 a jeden a dva byli tady, tak že seznam byl skutečně zvrátit? 1047 00:36:35,840 --> 00:36:38,300 >> No, co se děje ve skutečnosti jestli je to číslo? 1048 00:36:38,300 --> 00:36:41,300 A uděláme jen pár příkladů. 1049 00:36:41,300 --> 00:36:49,300 Co když, opravdu, číslo osm je tady, a number-- pokřiky. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Takže to, co v případě, opravdu, číslo Osm je celou cestu sem, 1052 00:36:56,430 --> 00:36:57,790 a já jsem s použitím insertion sort? 1053 00:36:57,790 --> 00:36:58,290 >> DOBŘE. 1054 00:36:58,290 --> 00:37:00,280 Tvrdím, v tuto chvíli je to na místě. 1055 00:37:00,280 --> 00:37:03,152 Ale teď, sedmé Odkud sedmi jít? 1056 00:37:03,152 --> 00:37:04,360 Samozřejmě, že jde přes zde. 1057 00:37:04,360 --> 00:37:06,760 Takže jsem se pohybovat přes osm jednom místě. 1058 00:37:06,760 --> 00:37:08,554 A teď šest, kde to jde? 1059 00:37:08,554 --> 00:37:09,220 No, v pořádku. 1060 00:37:09,220 --> 00:37:13,150 Teď musím se pohybovat přes osm místo, a sedm více než na místě, 1061 00:37:13,150 --> 00:37:14,440 a pak jsem plop dolů šest. 1062 00:37:14,440 --> 00:37:16,870 >> Takže první čas, že náklady mi jeden krok věci do pořádku, 1063 00:37:16,870 --> 00:37:18,570 Pak mě to stálo dva kroky opravit věci. 1064 00:37:18,570 --> 00:37:20,370 Kolik kroků je to bude trvat na opravu 1065 00:37:20,370 --> 00:37:22,720 Co dát pět na správném místě? 1066 00:37:22,720 --> 00:37:23,340 Tři. 1067 00:37:23,340 --> 00:37:29,520 Protože teď musím přesunout jeden, dva, tři. 1068 00:37:29,520 --> 00:37:32,430 Kolik kroků to bude trvat dát čtyři na správném místě? 1069 00:37:32,430 --> 00:37:36,040 4 a 5, a 6, a 7. 1070 00:37:36,040 --> 00:37:40,260 >> A tak je to matematicky totožné s to, co jsme popsali pro výběr druhu. 1071 00:37:40,260 --> 00:37:42,130 Máme tuto sérii to je jen roste. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, nebo naopak, 7 a 6 1073 00:37:45,650 --> 00:37:52,610 a 5 plus 4 sečte pro dnešní účely tak, aby na pořadí n na druhou. 1074 00:37:52,610 --> 00:37:57,640 >> Dovolte mi také, že stanoví, bublinkové řazení je také v n na druhou. 1075 00:37:57,640 --> 00:38:01,340 Vzhledem k tomu, s perličkovou druhu, každý Tentokrát jsem projít seznam, 1076 00:38:01,340 --> 00:38:03,100 Beru zhruba kolik kroků? 1077 00:38:03,100 --> 00:38:06,260 Pokaždé, když jsem se doslova pěšky odtud tam? 1078 00:38:06,260 --> 00:38:07,960 Zhruba n kroků. 1079 00:38:07,960 --> 00:38:12,650 Ale kolikrát bych mohl muset projít seznamu? 1080 00:38:12,650 --> 00:38:13,920 >> No, hrubě n čas. 1081 00:38:13,920 --> 00:38:15,680 Možná n minus 1, ale zhruba n časy. 1082 00:38:15,680 --> 00:38:16,430 Tak proč je to? 1083 00:38:16,430 --> 00:38:19,560 No, s bublinou druhu, pokud začneme s bublinou druhu, 1084 00:38:19,560 --> 00:38:23,570 se seznamem v ten nejhorší možný situace, což je opět zcela 1085 00:38:23,570 --> 00:38:25,550 dozadu, co se bude dít? 1086 00:38:25,550 --> 00:38:28,830 I projít seznam, a číslo Patříte-celou cestu tam. 1087 00:38:28,830 --> 00:38:33,280 >> Ale s bublinou druhu, jak daleko se může stát jeden přejít na svém prvním průchodu seznamu? 1088 00:38:33,280 --> 00:38:36,620 Kolik místa se dostal blíže na správné místo? 1089 00:38:36,620 --> 00:38:37,240 Jen jeden. 1090 00:38:37,240 --> 00:38:40,281 Takže pokud máte trochu důvod přes to, pokaždé, prostřednictvím tohoto algoritmu, 1091 00:38:40,281 --> 00:38:41,880 Davidovi, kteří se zhruba n kroků. 1092 00:38:41,880 --> 00:38:44,940 Ale kolik prochází v seznamu je to 1093 00:38:44,940 --> 00:38:49,060 bude trvat na jeden bublat na levé straně, kam patří? 1094 00:38:49,060 --> 00:38:51,840 >> Má se pohybovat podobně, n prostory Tudy. 1095 00:38:51,840 --> 00:38:57,960 Takže stačí k tomu třídění seznamu, Musím chodit sem a tam n-krát. 1096 00:38:57,960 --> 00:39:01,540 A pokaždé, já jsem při pohledu na n elementy. 1097 00:39:01,540 --> 00:39:05,410 Takže dělat věci, n n-krát na pořadí n na druhou. 1098 00:39:05,410 --> 00:39:07,220 >> Teď uvidíme v některých šortek, které 1099 00:39:07,220 --> 00:39:10,440 jsou uloženy v CS50 je další problém set, jiný přístup na nich, 1100 00:39:10,440 --> 00:39:13,490 ale teď, ať to prostě vzít v úvahu některé ostatní provozní časy, 1101 00:39:13,490 --> 00:39:16,840 zvláště v případě, že třídění ti brát trochu času, aby dřez. 1102 00:39:16,840 --> 00:39:21,790 Co je to algoritmus jsme viděli již , který bere na pořadí n kroků? 1103 00:39:21,790 --> 00:39:27,560 >> To, co by měl mít lineární číslo kroků, které jsme doposud viděli? 1104 00:39:27,560 --> 00:39:29,350 Co je to? 1105 00:39:29,350 --> 00:39:30,480 Vyhledávání telefonní seznam. 1106 00:39:30,480 --> 00:39:31,390 První algoritmus. 1107 00:39:31,390 --> 00:39:31,560 Je to tak? 1108 00:39:31,560 --> 00:39:33,650 Tam, kde jsme lineárně hledání Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Vskutku. 1110 00:39:34,150 --> 00:39:37,180 Od týdne nula, když jsem začal soustružení jednu stránku najednou, 1111 00:39:37,180 --> 00:39:40,095 a dokonce řekl jsem, že to bylo docela lineárního pocit algoritmu, 1112 00:39:40,095 --> 00:39:42,720 a měli jsme ten obraz na straně deska s rovnou červenou čárou 1113 00:39:42,720 --> 00:39:44,678 a rovný žlutý linka, ty byly skutečně 1114 00:39:44,678 --> 00:39:46,810 algoritmy, které jsou ve velké O n. 1115 00:39:46,810 --> 00:39:50,680 >> Vzhledem k tomu, najít Mike Smith v telefonu kniha n stránek, v nejhorším případě, 1116 00:39:50,680 --> 00:39:52,422 mi n kroků může trvat. 1117 00:39:52,422 --> 00:39:53,630 Co o tom, docházku? 1118 00:39:53,630 --> 00:39:55,790 Jedna dva tři čtyři pět šest. 1119 00:39:55,790 --> 00:39:59,420 Jaký je doba chodu tohoto algoritmus pro přijetí docházku? 1120 00:39:59,420 --> 00:40:03,070 Velký O n, protože teoreticky I muset bod všichni v místnosti. 1121 00:40:03,070 --> 00:40:05,861 >> Nyní jako stranou, co o další optimalizace z týdne nula? 1122 00:40:05,861 --> 00:40:08,117 Dvě, čtyři, šest, osm, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Počítač by vědec si uvědomit, počkejte chvíli, 1124 00:40:10,200 --> 00:40:12,320 to je na pořadí n děleno dvou krocích. 1125 00:40:12,320 --> 00:40:12,820 Je to tak? 1126 00:40:12,820 --> 00:40:14,444 Protože dělám dva lidi najednou. 1127 00:40:14,444 --> 00:40:17,015 Ale budeme ignorovat tyto nižšího řádu podmínky, 1128 00:40:17,015 --> 00:40:19,140 a my jen tak vyhodit propast o 2, 1129 00:40:19,140 --> 00:40:21,830 a jen říct, velké O n pro tento algoritmus, tak. 1130 00:40:21,830 --> 00:40:22,760 >> Co tenhle? 1131 00:40:22,760 --> 00:40:26,170 Budeme přeskočit některé z nich, ale to, co byl algoritmus, který byl log n? 1132 00:40:26,170 --> 00:40:29,900 To zabralo zhruba log n kroky? 1133 00:40:29,900 --> 00:40:30,870 Propast a panuj. 1134 00:40:30,870 --> 00:40:31,369 Přesně tak. 1135 00:40:31,369 --> 00:40:33,900 Stejně jako telefonního seznamu například v týden nula a dnes ráno, 1136 00:40:33,900 --> 00:40:36,191 kde jsme rozdělili problém znovu a znovu a znovu. 1137 00:40:36,191 --> 00:40:39,070 Čerpal jsme to na tabuli v týdnu nula jako zakřivený zelená linka, 1138 00:40:39,070 --> 00:40:41,460 a my jsme řekli, že je to den, logaritmickou algoritmus. 1139 00:40:41,460 --> 00:40:44,970 >> A opravdu, počet kroků IT potřebná k provedení rozděl a panuj, 1140 00:40:44,970 --> 00:40:48,610 nebo binární vyhledávání, jak začneme volat to, stejně jako v telefonním seznamu, 1141 00:40:48,610 --> 00:40:50,680 je řádově log a jen pár kroků. 1142 00:40:50,680 --> 00:40:52,470 A to je trochu divný jeden. 1143 00:40:52,470 --> 00:40:54,910 >> To, co se jeden krok, nebo přesněji 1144 00:40:54,910 --> 00:40:56,240 konstantní počet kroků? 1145 00:40:56,240 --> 00:40:58,865 Možná je to dvou, možná je to tři, ale počítačový vědec jen 1146 00:40:58,865 --> 00:41:01,423 zjednodušuje to jako velký O 1, některé konstantní počet kroků. 1147 00:41:01,423 --> 00:41:04,256 Co je to něco, co byste mohli udělat, že trvá konstantní počet kroků? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Jaký je doba provozu tleskat? 1150 00:41:10,930 --> 00:41:11,920 Konstantní čas. 1151 00:41:11,920 --> 00:41:12,420 Je to tak? 1152 00:41:12,420 --> 00:41:15,490 Stejně jako to, co je doba provozu dělat něco, který bere jen jeden 1153 00:41:15,490 --> 00:41:18,570 provoz, stejně jako vytisknout F Hello World. 1154 00:41:18,570 --> 00:41:24,110 To by mohlo být řekl, aby byl konstantní čas, ledaže méně rohový případě s tiskovým F, 1155 00:41:24,110 --> 00:41:28,260 Co by mohlo čas běží tisku F být ve skutečnosti? 1156 00:41:28,260 --> 00:41:28,790 A proč? 1157 00:41:28,790 --> 00:41:30,550 Co je n měření v tomto případě? 1158 00:41:30,550 --> 00:41:32,251 >> Diváků: [Neslyšitelné]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Přesně tak. 1160 00:41:33,250 --> 00:41:34,900 Počet znaků chceme vytisknout. 1161 00:41:34,900 --> 00:41:36,191 Takže je to velmi kontextová. 1162 00:41:36,191 --> 00:41:39,910 Dnes jsme se zaměřuje hodně na písmena a číslice tady na palubě. 1163 00:41:39,910 --> 00:41:43,540 Ale může to být také znaky v skutečném řetězci. 1164 00:41:43,540 --> 00:41:46,420 Tak to dopadá je tu další opatření, které začnou starat o, 1165 00:41:46,420 --> 00:41:48,530 a to je opak big O, abych tak řekl. 1166 00:41:48,530 --> 00:41:50,120 >> To je omega notace. 1167 00:41:50,120 --> 00:41:53,380 Vzhledem k tomu, velký O znamená, že to, co je se horní vázané na běžící čas? 1168 00:41:53,380 --> 00:41:55,580 Maximálně, kolik času Možná něco vzít? 1169 00:41:55,580 --> 00:41:59,250 Omega-- Omlouváme se, tento stále přichází up-- je opak toho, 1170 00:41:59,250 --> 00:42:02,960 čímž je to dolní mez na Množství času, něco, co by mohlo trvat. 1171 00:42:02,960 --> 00:42:10,480 >> Tak. Například, co je algoritmus který bere vždy n čtverečních kroky? 1172 00:42:10,480 --> 00:42:15,600 No, jeden z algoritmů jsme viděli dnes, ve skutečnosti, že může být také. 1173 00:42:15,600 --> 00:42:16,720 Selection sort. 1174 00:42:16,720 --> 00:42:18,270 Výběrem Třídit to docela hloupé. 1175 00:42:18,270 --> 00:42:21,760 I když se algorithm-- líto, a to i v případě, že je pole již seřazeny, 1176 00:42:21,760 --> 00:42:24,150 Volba třídění se chystá chůzi držet v seznamu 1177 00:42:24,150 --> 00:42:28,907 aby se ujistil, že má nejmenší prvek znovu a znovu a znovu. 1178 00:42:28,907 --> 00:42:31,740 A i když lidé v diváci vědí, že, počkejte chvíli, 1179 00:42:31,740 --> 00:42:33,948 již prošel nejmenší prvek, počítač 1180 00:42:33,948 --> 00:42:37,300 neví, že až to vypadá celou cestu v seznamu. 1181 00:42:37,300 --> 00:42:40,240 Podobně, dolní mez, která mohou být rovněž vzaty v úvahu 1182 00:42:40,240 --> 00:42:42,000 by mohl být lineární čas. 1183 00:42:42,000 --> 00:42:48,260 >> Kolik času trvá třídit n prvky v nejlepší 1184 00:42:48,260 --> 00:42:52,420 Případ použití něco jako bublina druhu? 1185 00:42:52,420 --> 00:42:54,280 Předpokládejme, že váš seznam je již řazeno. 1186 00:42:54,280 --> 00:42:56,696 Řekli jsme, bublinkové řazení bere na pořadí n druhou kroků. 1187 00:42:56,696 --> 00:42:59,640 Ale co když je to již řazeno? 1188 00:42:59,640 --> 00:43:02,310 Co když si uvědomíte, po jeden průchod přes pole 1189 00:43:02,310 --> 00:43:03,540 že jste udělali žádné swapy? 1190 00:43:03,540 --> 00:43:05,970 Potřebujete udržet dělat více prochází? 1191 00:43:05,970 --> 00:43:06,470 >> Ne. 1192 00:43:06,470 --> 00:43:10,340 Takže spodní hranici bublinkové řazení by mohlo být řekl, aby byl lineární. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 A my si prohlédnout další z nich, jakož. 1195 00:43:14,450 --> 00:43:17,990 Takže pojďme se rychle podívat na pouhých vizualizaci zde 1196 00:43:17,990 --> 00:43:20,790 vidět, jak se tyto odlišit. 1197 00:43:20,790 --> 00:43:24,592 Chystám se jít sem dolů do toho Stránka, která je k dispozici na internetových stránkách C50 je, 1198 00:43:24,592 --> 00:43:27,550 ale bude to bolet, aby si práci, protože používá technologii nazvanou 1199 00:43:27,550 --> 00:43:30,560 Java applety, což je z velké části podporován v těchto dnech, 1200 00:43:30,560 --> 00:43:32,730 alespoň Chrome a některé další produkty. 1201 00:43:32,730 --> 00:43:37,070 >> A dovolte mi, abych do toho pusťte a urychlíte up a vysvětlit, co se děje. 1202 00:43:37,070 --> 00:43:40,840 To je projevem bubliny třídění, první algoritmus jsme se na. 1203 00:43:40,840 --> 00:43:43,950 A to je vizualizace, že každý z těchto tyčí představuje číslo. 1204 00:43:43,950 --> 00:43:45,710 Čím větší je bar, Čím vyšší je číslo. 1205 00:43:45,710 --> 00:43:47,520 Čím menší je bar, čím menší je počet. 1206 00:43:47,520 --> 00:43:50,353 A co můžete vidět vizuálně, a to i i když to bude super rychlý, 1207 00:43:50,353 --> 00:43:53,699 je to, že červený pruh je jako já, chůze sem a tam upevnění problémy. 1208 00:43:53,699 --> 00:43:56,740 Můžete vidět, že větší prvky skutečně vyvěrá na pravé straně, 1209 00:43:56,740 --> 00:43:59,650 a na menších elementy vyvěrá doleva. 1210 00:43:59,650 --> 00:44:01,870 A tady dole, kdybychom ve skutečnosti vypadají lépe, 1211 00:44:01,870 --> 00:44:04,330 vlastně můžeme počítat počet porovnání a swapů 1212 00:44:04,330 --> 00:44:05,350 které byly vyrobeny. 1213 00:44:05,350 --> 00:44:07,360 >> Ale místo toho, pojďme se podívat na druhém algoritmu 1214 00:44:07,360 --> 00:44:11,240 jsme se podívali na dříve s naší dobrovolníci, výběr druhu. 1215 00:44:11,240 --> 00:44:13,500 Vizuálně, to má velmi odlišný efekt. 1216 00:44:13,500 --> 00:44:16,820 Ale je to opět velmi intuitivní, v že držíme výběr příští nejmenší 1217 00:44:16,820 --> 00:44:18,660 prvek, a dostali jsme trochu štěstí. 1218 00:44:18,660 --> 00:44:20,110 To se cítil zásadně rychleji. 1219 00:44:20,110 --> 00:44:22,840 Ale když jsme běželi to znovu a znovu a opět se spoustou vstupů, 1220 00:44:22,840 --> 00:44:26,680 viděli bychom, že je to opravdu stále ještě ve velké O n na druhou. 1221 00:44:26,680 --> 00:44:29,920 >> Pojďme udělat jednu poslední tady, insertion sort, 1222 00:44:29,920 --> 00:44:33,180 který byl třetí algoritmus jsme se podívali na, a odvolání 1223 00:44:33,180 --> 00:44:36,700 že tento člověk se zabývá prvky, jak to s nimi setká, 1224 00:44:36,700 --> 00:44:39,290 ale pak se to možná posuny věci, nad aby se uvolnilo místo, 1225 00:44:39,290 --> 00:44:41,660 vkládání prvků tam, kam patří. 1226 00:44:41,660 --> 00:44:45,330 >> A to také skončí dávat Konečný výsledek. Nyní všechny tři z těch, 1227 00:44:45,330 --> 00:44:46,490 cítil docela rychle. 1228 00:44:46,490 --> 00:44:48,740 A skutečně, běžel jsem je v docela dobrý klip. 1229 00:44:48,740 --> 00:44:52,510 Ale v podstatě, oni jsou všichni dost hrozné, abych byl upřímný. 1230 00:44:52,510 --> 00:44:56,960 Všechny tyto algoritmy dosud že dráha v velký O n čtvercový 1231 00:44:56,960 --> 00:44:59,270 trvat docela dost čas pro spuštění v konci. 1232 00:44:59,270 --> 00:45:01,920 >> A skutečně, můžeme vidět a cítit se to konečně 1233 00:45:01,920 --> 00:45:04,090 když jsem vytáhnout tento třetí a poslední demo. 1234 00:45:04,090 --> 00:45:05,840 To je další vizualizace, co se děje 1235 00:45:05,840 --> 00:45:08,500 ukázat bublinkové řazení na levé straně, výběrem Třídit ve středu, 1236 00:45:08,500 --> 00:45:13,410 a něco, jako jeden z našich ruka vyvolává dříve navrhl, 1237 00:45:13,410 --> 00:45:15,020 merge sort na pravé straně. 1238 00:45:15,020 --> 00:45:16,937 Předěl a panuj Strategie na pravé straně. 1239 00:45:16,937 --> 00:45:19,520 A to je ve skutečnosti to, co jsme jít se podívat na středu. 1240 00:45:19,520 --> 00:45:21,990 Ale pojďme čas tyto běžet paralelně. 1241 00:45:21,990 --> 00:45:26,765 To je zhruba stejný počet prvky, všechny běží ve stejnou dobu. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs výběru třídit vs sloučení druhu. 1244 00:45:34,440 --> 00:45:36,760 >> Teď se všichni běží teoreticky ve stejnou dobu. 1245 00:45:36,760 --> 00:45:39,830 CPU běží na stejnou rychlost, ale 1246 00:45:39,830 --> 00:45:44,014 Můžete cítit, jak je to nudné velmi rychle stane, 1247 00:45:44,014 --> 00:45:45,930 a jak rychle, když jsme se vnést trochu týdne 1248 00:45:45,930 --> 00:45:49,330 algoritmy Zero může jsme se věci urychlit. 1249 00:45:49,330 --> 00:45:51,760 >> A teď pojďme porovnat tyto v posledním formě. 1250 00:45:51,760 --> 00:45:55,710 Chystám se pokračovat na webové stránky CS50, kde 1251 00:45:55,710 --> 00:45:59,020 máme tuto konečnou odkaz pro dnešek, kde někdo na internetu 1252 00:45:59,020 --> 00:46:03,960 laskavě dal dohromady video, které zachycuje to, co jiný třídění 1253 00:46:03,960 --> 00:46:07,510 algoritmy znít. 1254 00:46:07,510 --> 00:46:09,577 To je insertion sort. 1255 00:46:09,577 --> 00:46:12,072 >> [Pípání] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Přičemž se ucházíte frekvenci založené na výšce baru baru. 1258 00:46:16,850 --> 00:46:19,826 Je to bublina druh. 1259 00:46:19,826 --> 00:46:21,822 >> [Warped pípání] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Připravujeme další je-- přichází up další je-- výběr třídit, 1262 00:46:45,774 --> 00:46:48,820 kde opět, my výběr příští nejmenší prvek, 1263 00:46:48,820 --> 00:46:51,820 a my můžeme vidět, že růst zleva doprava. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge sort, náš vítěz tak daleko ještě dnes. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Všimněte si, jak je to dělení věcí do [neslyšitelný] polovinu a čtvrtiny. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome třídění, které my ne mluvil o, a vytváří vizuálně 1270 00:47:21,660 --> 00:47:24,450 a audally trochu jiný tvar a zvuk. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Tam a zpět, čištění věci. 1273 00:47:30,160 --> 00:47:32,230 Také check out Heapsort na webových stránkách tenhle chlápek. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> A to je vše. 1276 00:47:36,810 --> 00:47:38,210 Uvidíme se příště. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing a hudba] 1279 00:47:48,334 --> 00:50:24,839