1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Prehrávanie hudby] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. Malan: Toto je CS50. 5 00:00:12,550 --> 00:00:14,612 A to je začiatok troch týždňov. 6 00:00:14,612 --> 00:00:16,820 Takže máme veľa vzrušujúce veci na pokrytie dnes. 7 00:00:16,820 --> 00:00:20,160 Mnoho príležitostí pre dobrovoľníci sa na javisku. 8 00:00:20,160 --> 00:00:22,780 A nakoniec, dnes je nejde o kóde vôbec. 9 00:00:22,780 --> 00:00:24,820 Ale je to o myšlienkach, a je to o algoritmoch, 10 00:00:24,820 --> 00:00:28,420 a vlastne prinášať späť časť poučenie z týždňa nula, 11 00:00:28,420 --> 00:00:31,910 kde odvolanie, my predstavil túto obludnosť. 12 00:00:31,910 --> 00:00:33,880 A výpožičky inšpirácia od toho, pre spustenie 13 00:00:33,880 --> 00:00:36,879 riešiť stále sofistikovanejšie Problémy algoritmickým. 14 00:00:36,879 --> 00:00:38,420 Ale najprv pár oznámenia. 15 00:00:38,420 --> 00:00:42,020 Takže jeden, ak by ste sa radi pripojili CS50 personál a spolužiaci na obed 16 00:00:42,020 --> 00:00:44,670 tento piatok, ako tu, tak v Cambridge a v New Haven, 17 00:00:44,670 --> 00:00:48,060 navštívte kurz je webové stránky, kde je možné URL nájdená. 18 00:00:48,060 --> 00:00:50,390 Prednáška bude túto stredu nemôže byť tu v Sanders. 19 00:00:50,390 --> 00:00:53,610 Bude to on-line iba, takže naladiť na stránkach CS50 je, 20 00:00:53,610 --> 00:00:55,850 či už tu v Cambridge alebo New Haven rovnako. 21 00:00:55,850 --> 00:00:58,110 >> A potom problém nastaviť dve je už vo vašich rukách. 22 00:00:58,110 --> 00:01:03,067 Ak ste sa potápal v doteraz, dovoľte mi ponúknuť ostro formulovaný návrh 23 00:01:03,067 --> 00:01:05,150 , Že najmä teraz, as Problém stanovuje postup, 24 00:01:05,150 --> 00:01:08,669 si naozaj chcete začať hneď, ak nie fušovať trochu na víkend alebo pred 25 00:01:08,669 --> 00:01:10,710 kedy sa prvýkrát ísť na Piatky, pretože budete 26 00:01:10,710 --> 00:01:14,380 zistíte, že to nemusí byť nutne stále dlhšie a náročnejšie na 27 00:01:14,380 --> 00:01:14,950 sa. 28 00:01:14,950 --> 00:01:17,575 Myslím, že zistíte, že v Všeobecne platí, že majú tendenciu, aby sa zhruba 29 00:01:17,575 --> 00:01:18,892 zhruba rovnaké množstvo času. 30 00:01:18,892 --> 00:01:20,850 Ale to rozhodne záleží na študenta, a to 31 00:01:20,850 --> 00:01:22,880 závisí na myslenie s ktorým k nemu pristupovať. 32 00:01:22,880 --> 00:01:24,910 Ale vždy, budete bežať proti nejaké múru, 33 00:01:24,910 --> 00:01:26,350 a budete hit nejaký bug, a vy ste len 34 00:01:26,350 --> 00:01:27,950 nebude môcť dostať sa cez to v určitom okamihu. 35 00:01:27,950 --> 00:01:31,380 A to je veľmi cenné, aby bolo možné ustúpiť, vráť sa ďalší deň, 36 00:01:31,380 --> 00:01:35,286 ísť na pracovný čas, príspevok na CS50 Diskutovať alebo podobne, aby skutočne dostať odblokovať. 37 00:01:35,286 --> 00:01:36,160 Takže majte na pamäti, že. 38 00:01:36,160 --> 00:01:40,830 Spustenie najskôr to bude možné je to najlepšie, čo môžete urobiť. 39 00:01:40,830 --> 00:01:44,160 Tak tu je miesto, kde sme začali trieda, než v týždni nula. 40 00:01:44,160 --> 00:01:47,441 A môžeme dostať dobrovoľníka tu, aby mi pomohla nájsť mikrofóny? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 Stojí už hore. 43 00:01:48,900 --> 00:01:50,080 Poď hore. 44 00:01:50,080 --> 00:01:53,707 Hádajte, že to, ako to bude fungovať. 45 00:01:53,707 --> 00:01:54,415 Ako sa voláš? 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 Poď hore. 49 00:01:57,910 --> 00:01:58,619 Rád som ťa spoznal. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Teší ma. 51 00:01:59,910 --> 00:02:02,772 DAVID J. Malan: A vy ste tu u nás v týždni nula, samozrejme. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: som bol. 53 00:02:03,028 --> 00:02:03,160 Bol som. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. Malan: Takže by ste mohli ísť dopredu a nájsť pre nás Mike Smith, 55 00:02:05,868 --> 00:02:08,639 tak rýchlo, ako je to možné? 56 00:02:08,639 --> 00:02:10,639 Tak rýchlo, ako je to možné. 57 00:02:10,639 --> 00:02:13,756 Doslova trhá problém na polovicu, ako budete potrebovať. 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 trhanie problém na polovicu. 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 Veľmi dobre. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. Malan: OK. 65 00:02:23,700 --> 00:02:24,200 Dobre. 66 00:02:24,200 --> 00:02:24,701 Ďakujem. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Veľmi dobre. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. Malan: A tak teraz, ste orezaný dole 70 00:02:27,610 --> 00:02:29,320 na polovicu veľkosti problému. 71 00:02:29,320 --> 00:02:31,267 Teraz, sme až na štvrtinu. 72 00:02:31,267 --> 00:02:33,475 Ste venovať pozornosť na ktorej strane držíme? 73 00:02:33,475 --> 00:02:34,405 >> [Smeje sa] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Áno, ja think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. Malan: Aká časť sme v? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: tlmič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 sa deje byť po tlmiče. 79 00:02:42,810 --> 00:02:44,130 Tak-- 80 00:02:44,130 --> 00:02:48,180 >> [Smeje sa] 81 00:02:48,180 --> 00:02:48,742 >> Dobre. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Kde sa to pozerá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: Teraz sme v chirurgickej. 86 00:02:54,760 --> 00:02:57,840 Teraz lekári. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- poď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 OK. 92 00:03:01,470 --> 00:03:03,700 Ak potrebujete skutočný. 93 00:03:03,700 --> 00:03:05,250 Teraz, ktorá cesta je Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Tadiaľto. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. Malan: Kadiaľ? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Počkajte. 97 00:03:08,240 --> 00:03:08,790 M je-- pravdu? 98 00:03:08,790 --> 00:03:09,110 Začali sme 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 tu. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Čo? 105 00:03:13,990 --> 00:03:14,665 >> [Smeje sa] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Zlý príklad, chlapi. 108 00:03:18,330 --> 00:03:18,830 Prepáčte. 109 00:03:18,830 --> 00:03:21,610 DAVID J. Malan: To bude vyučovať vás vyskočiť zo stoličky. 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 ťa. 113 00:03:23,390 --> 00:03:24,670 Mám ťa. 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 ťa. 117 00:03:26,812 --> 00:03:27,520 Smith tu? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. Malan: Smith, ďakujem. 119 00:03:28,894 --> 00:03:30,535 Takže budem držať vzhliadol Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, jo. 121 00:03:30,790 --> 00:03:31,340 Nie nie nie. 122 00:03:31,340 --> 00:03:31,600 Ale nie. 123 00:03:31,600 --> 00:03:31,940 To je moja. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. Malan: Oh, máš Smith. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Jo, myslím, dostal Smith tu. 127 00:03:34,040 --> 00:03:34,700 Ospravedlňujeme sa, chlapi. 128 00:03:34,700 --> 00:03:35,860 Myslel som, že sme sa Michael-- hľadali Michaela. 129 00:03:35,860 --> 00:03:36,550 Prepáčte. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. Malan: To je v poriadku. 131 00:03:37,550 --> 00:03:39,950 Dobre, teraz sme do Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini a synovia. 133 00:03:41,242 --> 00:03:43,158 DAVID J. Malan: Iba vy a ja sme na túto tému. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Nájdite 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 Sme v R pre 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íľu trvať. 143 00:03:52,480 --> 00:03:54,340 >> [Smeje sa] 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 Sme v topánkach. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Teraz sme 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 [Smeje sa] 151 00:04:03,620 --> 00:04:05,440 Oh, to je skvelé. 152 00:04:05,440 --> 00:04:06,910 [Smeje sa] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. Malan: To je v poriadku. 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 budem majú PSAT kamarátmi 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 poďme roztrhať to na polovicu. 163 00:04:21,600 --> 00:04:22,270 Je to v poriadku. 164 00:04:22,270 --> 00:04:25,606 Týmto končí zle tak ako tak, pretože Mike Smith nebude v Zlatých stránkach. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. Malan: Nie, to je v poriadku. 167 00:04:27,140 --> 00:04:28,930 Ale poďme predstierať, že je na tejto stránke. 168 00:04:28,930 --> 00:04:33,260 Takže teraz, že ste orezaný problém dole na jednej strane, a zistili sme, Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [Fandenie] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Dobre ďakujem. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 OK. 174 00:04:41,200 --> 00:04:43,646 To bol mimoriadny. 175 00:04:43,646 --> 00:04:45,954 Ale to bolo ešte rýchlejšie než lineárne vyhľadávanie, 176 00:04:45,954 --> 00:04:47,870 kde začneme u začiatku knihy, 177 00:04:47,870 --> 00:04:51,210 a my sa pohybujú našu cestu zľava doprava, nakoniec hľadal Mike Smith. 178 00:04:51,210 --> 00:04:53,540 A tak, v prípade, že telefónny zoznam Mal snáď 1000 strán, 179 00:04:53,540 --> 00:04:56,300 Možno, že by to vzali us 10 alebo tak stránky slzy. 180 00:04:56,300 --> 00:04:59,380 >> Ale môžete mať zadlužuje dotkol predpoklad 181 00:04:59,380 --> 00:05:03,602 pri všetkých, ktoré, čo znamená že telefónny zoznam vopred bolo to, čo? 182 00:05:03,602 --> 00:05:04,310 Divákov: Triedený. 183 00:05:04,310 --> 00:05:05,000 DAVID J. Malan: Je to triediť. 184 00:05:05,000 --> 00:05:05,160 Je to tak? 185 00:05:05,160 --> 00:05:07,909 Je to radené abecedne, tak že všetky tieto mien a čísel 186 00:05:07,909 --> 00:05:11,230 sú radené od A to k Z ich, a abecedne medzi tým. 187 00:05:11,230 --> 00:05:13,100 Ale dnes, teraz sa opýtať otázka, dobre, 188 00:05:13,100 --> 00:05:16,170 Ako sa Verizon alebo sa telefón spoločnosť dostať do tohto stavu? 189 00:05:16,170 --> 00:05:19,560 >> Vzhľadom k tomu, že je to jedna vec je využiť tento predpoklad, a preto, 190 00:05:19,560 --> 00:05:22,570 vyriešiť problém s algoritmus efektívnejšie. 191 00:05:22,570 --> 00:05:24,900 Ale my sme nikdy spýtal sa v týždni nula, dobre, 192 00:05:24,900 --> 00:05:27,790 koľko to stálo Verizon alebo niekto iný 193 00:05:27,790 --> 00:05:29,620 sa dostať, že telefónny zoznam v zoradení poradí? 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, či vzhliadol Mike Smith 196 00:05:31,529 --> 00:05:35,190 je super rýchly, keď to trvá vám odkaz rok spočiatku zoradenie stránok. 197 00:05:35,190 --> 00:05:35,690 Je to tak? 198 00:05:35,690 --> 00:05:38,620 Tie by mohli rovnako dobre preosiať cez randomizovanej telefónny zoznam, 199 00:05:38,620 --> 00:05:40,690 ak to bude byť super drahé to triediť. 200 00:05:40,690 --> 00:05:42,350 Takže, či môžeme mať ďalšie dobrovoľník. 201 00:05:42,350 --> 00:05:46,350 Poďme sa pozrieť tu na ako might-- poď up-- ako 202 00:05:46,350 --> 00:05:48,100 môžeme ísť o triedení týchto. 203 00:05:48,100 --> 00:05:51,990 >> A ak by sa skutočne Jordan Pripojte sa k nám tu na javisku. 204 00:05:51,990 --> 00:05:55,100 Poďte hore len na chvíľu. 205 00:05:55,100 --> 00:05:56,359 Ako sa voláš? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. Malan: Caroline, poď hore. 208 00:05:58,691 --> 00:06:02,070 A vy budete spojené mnou a Jordánskom tu. 209 00:06:02,070 --> 00:06:03,800 Caroline, ďakujem. 210 00:06:03,800 --> 00:06:04,300 Dobre. 211 00:06:04,300 --> 00:06:08,330 Takže to, čo sme tu Caroline je 26 modrej knihy 212 00:06:08,330 --> 00:06:10,747 že FAS používa na spravovanie niektoré záverečné skúšky. 213 00:06:10,747 --> 00:06:13,330 Tie sú stále ťažké nájsť, ale to, čo sme urobili v predstihu 214 00:06:13,330 --> 00:06:15,800 je to, že sme vložili niečí meno na prednej strane každého z nich, 215 00:06:15,800 --> 00:06:18,133 ale my sme stále to jednoduché od potom uvedenie von plná mená. 216 00:06:18,133 --> 00:06:22,720 Takže by sme dať osobu s názvom L, D, J, B, celá cesta A až Z, 217 00:06:22,720 --> 00:06:24,090 ale sú v náhodnom poradí. 218 00:06:24,090 --> 00:06:26,890 A tak ak by ste, hovoril vašich cesta cez problém ako vy 219 00:06:26,890 --> 00:06:31,620 to je, môžete ísť dopredu a triediť tieto pre nás, od A do Z. 220 00:06:31,620 --> 00:06:34,070 >> Publikum: OK, takže L je ako, uprostred. 221 00:06:34,070 --> 00:06:35,050 C začína. 222 00:06:35,050 --> 00:06:42,410 B. J pred L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. Malan: Držte že Myslel dobu jednej sekundy. 224 00:06:45,140 --> 00:06:48,910 Vzhľadom k tomu, inak, je to len zaujímavé pre vás, ja, a Jordánskom. 225 00:06:48,910 --> 00:06:49,724 Tam sme ísť. 226 00:06:49,724 --> 00:06:50,640 Divákov: [Nepočuteľné]. 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 Čo robíš? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M prichádza 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 vyzerá to, že ste making-- ďalej. 238 00:07:10,689 --> 00:07:12,730 Vyzerá to, že robíte veľká hromada tu, 239 00:07:12,730 --> 00:07:13,910 a druh veľkú hromadu tamto. 240 00:07:13,910 --> 00:07:16,230 Takže prvá polovica abecedy, Druhá polovica abecedy. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Dobre. 243 00:07:16,960 --> 00:07:19,680 Druh rozdelenie problému na dve časti. 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ýberu je jeden po druhom, 248 00:07:25,070 --> 00:07:27,620 uvedenie buď vľavo alebo vpravo, alebo Z deje na zemi. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z sa deje 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 sa deje na zemi. 253 00:07:30,920 --> 00:07:31,735 Teraz môžeme dať 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 sa deje odišiel. 256 00:07:33,700 --> 00:07:36,017 S bude v poriadku. 257 00:07:36,017 --> 00:07:37,642 Dobre, A ide celú cestu vľavo. 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: Teraz, dobre. 260 00:07:39,873 --> 00:07:43,260 Máme A, B, C, W deje tam dole. 261 00:07:43,260 --> 00:07:45,566 Dobre, 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 centre, som 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 teraz, budeme druhu o zlúčenie týchto rôznych pilotov. 267 00:07:52,375 --> 00:08:00,730 Takže A až C, a potom 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 potom, to je hromada hore nohami, ale to je v poriadku. 269 00:08:05,540 --> 00:08:06,040 Iste. 270 00:08:06,040 --> 00:08:07,240 Môžeme znížiť niektoré rohy. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 A potom 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 veľké poďakovanie Caroline pre triedenie týchto. 276 00:08:14,122 --> 00:08:15,030 >> [Fandenie] 277 00:08:15,030 --> 00:08:17,287 >> Ďakujem. 278 00:08:17,287 --> 00:08:18,120 Ďakujem veľmi pekne. 279 00:08:18,120 --> 00:08:22,910 Takže teraz uvažujme na okamih ako Caroline šiel o tom, že, 280 00:08:22,910 --> 00:08:26,040 a čo presne my boli schopní to-- ako 281 00:08:26,040 --> 00:08:28,409 bol schopný riešiť, že problém, keď sme boli len 282 00:08:28,409 --> 00:08:29,950 vzhľadom k tomu, celá partia náhodných vstupov. 283 00:08:29,950 --> 00:08:31,610 >> No, vyzerá to, že tam bol trochu tam systému? 284 00:08:31,610 --> 00:08:32,110 Správne. 285 00:08:32,110 --> 00:08:34,495 Takže čím skôr listy v abecede, ona 286 00:08:34,495 --> 00:08:37,120 bolo uvedenie na ľavej strane, a neskôr písmen v abecede, 287 00:08:37,120 --> 00:08:38,270 bola uvedenie do pravej strane. 288 00:08:38,270 --> 00:08:40,500 A akonáhle zistila, že Niektoré proximálnej listy, ones 289 00:08:40,500 --> 00:08:43,124 ktoré idú hneď vedľa seba, ona by dal tie v poriadku. 290 00:08:43,124 --> 00:08:46,750 A tak sme trochu mali tieto malé hromady triedených vstupov vyskytujúcich. 291 00:08:46,750 --> 00:08:50,540 >> A tak to je celkom rád to, čo Väčšina z nás by ľudia robia. 292 00:08:50,540 --> 00:08:53,530 Radi by sme nejako preosiať cez to, a my by sme trochu mať mechanizmus. 293 00:08:53,530 --> 00:08:56,930 Ale to by mohlo byť ťažké písať že sa vo vzorci, per sa. 294 00:08:56,930 --> 00:08:59,010 Bolo to o niečo viac ekologická než to. 295 00:08:59,010 --> 00:09:02,560 Tak uvidíme, či môžeme teraz viazaný Problém s menším počtom vstupov. 296 00:09:02,560 --> 00:09:05,170 >> Namiesto toho, 26., poďme niečo ďaleko menej 297 00:09:05,170 --> 00:09:09,890 s len povedať, sedem, za tieto dvere, aby som tak povedal. 298 00:09:09,890 --> 00:09:11,300 Sú tam len sedem čísel? 299 00:09:11,300 --> 00:09:15,240 A v prípade, že cieľ teraz na ruka je nájsť hodnotu, 300 00:09:15,240 --> 00:09:17,850 pozrime sa, ako efektívne môžeme ísť asi robí. 301 00:09:17,850 --> 00:09:22,460 A uvidíme, či môžeme teraz začne platiť nejaké čísla, 302 00:09:22,460 --> 00:09:26,310 alebo niektoré vzorce, s ktorými popísať Účinnosť nášho telefónneho zoznamu 303 00:09:26,310 --> 00:09:31,060 algoritmus, naša skúška kniha algoritmus, a všeobecnejšie, vyhľadávanie informácií. 304 00:09:31,060 --> 00:09:34,770 >> Takže pre to, nechajte ma ísť dopredu, a Na dotykovej obrazovke sa sem, 305 00:09:34,770 --> 00:09:41,100 dať do webového prehliadača, ktorý má presne týchto sedem dvere. 306 00:09:41,100 --> 00:09:46,670 A ak by sme sa mohli dostať jednu ďalšiu dobrovoľne poď sem, 307 00:09:46,670 --> 00:09:48,480 Ja som dal tieto rovnaké dvere sem. 308 00:09:48,480 --> 00:09:49,170 Quick dobrovoľník. 309 00:09:49,170 --> 00:09:51,130 >> Tieto one-- dema idú na rýchlejší a rýchlejší teraz. 310 00:09:51,130 --> 00:09:51,600 Poď dole. 311 00:09:51,600 --> 00:09:52,308 Ako sa voláš? 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 Dobre, Trevor, poď dole. 315 00:09:55,770 --> 00:09:59,212 Takže Trevor sa tu dobrovoľne robiť podobný problém, ale ten, ktorý je 316 00:09:59,212 --> 00:10:02,170 užší rozsah, a to sa deje aby sme mohli pokúsiť formalizovať teraz 317 00:10:02,170 --> 00:10:03,970 Proces triedenia týchto čísel. 318 00:10:03,970 --> 00:10:05,500 >> Takže Trevor, rád vás spoznávam. 319 00:10:05,500 --> 00:10:08,720 Takže tu je pole, tak hovorí, zoznam siedmich dverí. 320 00:10:08,720 --> 00:10:10,327 Choďte do toho a nájsť nám číslo 50. 321 00:10:10,327 --> 00:10:12,410 A potom sa po faktu, povedzte nám, ako ste ju našli. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Ak by be-- v poriadku. 324 00:10:20,040 --> 00:10:21,945 Jo, to je ten tu? 325 00:10:21,945 --> 00:10:24,680 Uh Oh. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Klepli že jeden. 328 00:10:26,680 --> 00:10:28,690 Dobre. 329 00:10:28,690 --> 00:10:29,780 >> A veľa. 330 00:10:29,780 --> 00:10:30,970 Teraz ste klikli, že jeden. 331 00:10:30,970 --> 00:10:34,060 A dovoľte mi, aby som vám mikrofón, takže ju máte za chvíľu. 332 00:10:34,060 --> 00:10:37,000 Choďte do toho a kliknite na tlačidlo vedľa, že máte v úmysle. 333 00:10:37,000 --> 00:10:39,812 Áno dobre. 334 00:10:39,812 --> 00:10:41,020 Trevor: Môžem unclick dvere? 335 00:10:41,020 --> 00:10:42,620 DAVID J. Malan: Nie, 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š ísť? 339 00:10:45,640 --> 00:10:46,410 Ktorý? 340 00:10:46,410 --> 00:10:47,230 >> Trevor: Tenhle. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. Malan: Nie. 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: Áno. 345 00:10:49,020 --> 00:10:49,700 To bolo dobré. 346 00:10:49,700 --> 00:10:50,380 Dobre. 347 00:10:50,380 --> 00:10:53,900 Takže aká bola vaša algoritmus alebo Postup tohto postupu, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> Trevor: Len som prešiel dvere, až som našiel 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. Malan: OK. 350 00:10:56,940 --> 00:10:58,150 Vynikajúci algoritmus. 351 00:10:58,150 --> 00:10:59,540 Tak je to v poriadku. 352 00:10:59,540 --> 00:11:03,120 Pretože v skutočnosti, keď som odhalí, čo je Za týmito dvoma ďalšími dverami, čo 353 00:11:03,120 --> 00:11:06,954 zistíme je, že máme len náhodnou vstup. 354 00:11:06,954 --> 00:11:08,870 Takže to bol vlastne as dobrý, ako by ste mohli dostať. 355 00:11:08,870 --> 00:11:12,509 A v skutočnosti, máš lepší ako vyčerpávajúcom hľadaní celé pole, 356 00:11:12,509 --> 00:11:15,300 pretože by to bolo skutočne smolu, ak ste mali hit číslo 357 00:11:15,300 --> 00:11:16,604 50 na poslednú dvere. 358 00:11:16,604 --> 00:11:18,520 Ale čo keby sme namiesto Dal vám predpoklad. 359 00:11:18,520 --> 00:11:20,630 Dajme tomu, že nejako som všetky tieto dvere okolo, 360 00:11:20,630 --> 00:11:23,500 takže máte Čísla radené tentoraz 361 00:11:23,500 --> 00:11:29,730 ale tentoraz je to vlastne different-- tentoraz, 362 00:11:29,730 --> 00:11:32,640 je to vlastne radené pre vás. 363 00:11:32,640 --> 00:11:35,380 A teraz cieľ na dosah ruky je trafiť čí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: Čo je Váš algoritmus bude? 366 00:11:37,670 --> 00:11:39,628 >> Trevor: No, keď je to radené, je to buď ísť 367 00:11:39,628 --> 00:11:42,710 na be-- ak najväčší k najväčšej, zostupne, bude to prvý, 368 00:11:42,710 --> 00:11:44,751 alebo ak je to naopak, to bude posledná. 369 00:11:44,751 --> 00:11:48,897 Tak som si len kliknite na dvere, a potom stačí kliknúť na poslednú dvere. 370 00:11:48,897 --> 00:11:49,980 DAVID J. Malan: Výborný. 371 00:11:49,980 --> 00:11:50,270 Dobre. 372 00:11:50,270 --> 00:11:51,150 Takže sme zistili, že číslo 50. 373 00:11:51,150 --> 00:11:52,970 Takže akonáhle ste vedel, boli radené, my 374 00:11:52,970 --> 00:11:55,040 boli schopní využiť tento predpoklad. 375 00:11:55,040 --> 00:11:57,040 Takže sú veľmi rád telefónneho zoznamu príkladom. 376 00:11:57,040 --> 00:11:59,540 Akonáhle budete mať, a to aj malý problém ako je tento, 377 00:11:59,540 --> 00:12:02,380 vaše vstupy pre-triedené, môžeme skutočne nájsť hodnotu pravdepodobne 378 00:12:02,380 --> 00:12:03,130 efektívnejšie. 379 00:12:03,130 --> 00:12:05,800 >> A ja som ťa, či je to povedať radené malých až po veľké, alebo veľká, aby malé, 380 00:12:05,800 --> 00:12:08,080 a tak to bolo veľmi rozumné začať na jednom konci alebo na druhú 381 00:12:08,080 --> 00:12:09,750 skutočne zistiť, že cieľové hodnoty. 382 00:12:09,750 --> 00:12:11,400 Takže ďakujeme Trevorom rovnako. 383 00:12:11,400 --> 00:12:13,260 A ja budem propose-- pekne urobil. 384 00:12:13,260 --> 00:12:16,960 Máme trochu klip, v skutočnosti, že je medzi naše obľúbené momentov CS50, 385 00:12:16,960 --> 00:12:19,700 pričom niekedy tieto ukážky nie celkom podľa plánu. 386 00:12:19,700 --> 00:12:22,050 A skutočne práve teraz, myslím, vytiahol zlú rozhranie 387 00:12:22,050 --> 00:12:23,508 s ktorým používať dotykovú obrazovku. 388 00:12:23,508 --> 00:12:24,660 Takže to bola moja chyba tam. 389 00:12:24,660 --> 00:12:26,600 >> Takže to bude robiť na budúci rok klip as 390 00:12:26,600 --> 00:12:28,570 prečo som sa kliknutím na moje vlastné obrazovku. 391 00:12:28,570 --> 00:12:31,390 Ale poďme sa rýchlo pozrieť na to, čo sa stalo minulý rok 392 00:12:31,390 --> 00:12:34,770 s Jay, ktorý prišiel, veľa ako Trevor tu, dobrovoľne, 393 00:12:34,770 --> 00:12:39,380 a v tomto krátkom klipe uvidíte ako to to isté demo nie celkom 394 00:12:39,380 --> 00:12:41,074 odhaľujú rovnaké ponaučenie. 395 00:12:41,074 --> 00:12:41,740 [Videoprehrávanie] 396 00:12:41,740 --> 00:12:45,360 -všetky Chcem, aby ste urobiť, je teraz nájsť pre mňa a pre nás, 397 00:12:45,360 --> 00:12:51,674 Naozaj, číslo 50 jeden krok v čase. 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 odhaliť, čo je Za každú z týchto dverí 401 00:12:55,356 --> 00:12:58,540 jednoduchým dotykom s prstom. 402 00:12:58,540 --> 00:13:00,910 Dočerta. 403 00:13:00,910 --> 00:13:02,870 >> [Smeje sa] 404 00:13:02,870 --> 00:13:03,806 >> [END Prehrávanie] 405 00:13:03,806 --> 00:13:05,430 DAVID J. Malan: Takže to išlo veľmi dobre. 406 00:13:05,430 --> 00:13:06,796 Tí, ktorí boli netriedené dvere. 407 00:13:06,796 --> 00:13:08,670 Jay a, samozrejme, našiel to všetko príliš rýchlo. 408 00:13:08,670 --> 00:13:12,910 Trevor urobil oveľa lepšiu prácu v podmienkach učenlivý okamih 409 00:13:12,910 --> 00:13:15,850 tak povediac, v tomto roku trvá dlhšiu dobu ju nájsť. 410 00:13:15,850 --> 00:13:17,950 Samozrejme, potom sme dali Jay druhá šanca, 411 00:13:17,950 --> 00:13:20,320 čím sme radené dvere, ako sme to urobili pre Trevora, 412 00:13:20,320 --> 00:13:22,300 a Trevor DID Super dobre tentoraz. 413 00:13:22,300 --> 00:13:26,124 Ale Jay to urobil polovicu rýchlo. 414 00:13:26,124 --> 00:13:26,790 [Videoprehrávanie] 415 00:13:26,790 --> 00:13:29,650 -the Cieľom je teraz tiež nájsť nám číslo 50, 416 00:13:29,650 --> 00:13:33,030 ale to algoritmickým, a povedzte nám, ako budete o tom. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -A Ak zistíte, budete mať film. 419 00:13:35,604 --> 00:13:37,228 Ak nenájdete to, dať ju späť. 420 00:13:37,228 --> 00:13:38,044 >> -MAN. 421 00:13:38,044 --> 00:13:38,860 >> Oh! 422 00:13:38,860 --> 00:13:40,800 >> - [Nepočuteľný] OK. 423 00:13:40,800 --> 00:13:46,236 Takže ja idem skontrolovať koncov najprv zistiť, či 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 Prehrávanie] 427 00:13:55,729 --> 00:13:56,520 DAVID J. Malan: OK. 428 00:13:56,520 --> 00:13:59,760 Takže jasne triedenie dvere vedie k väčšej efektivite. 429 00:13:59,760 --> 00:14:01,680 A tak, dvakrát rýchlejšie je to, čo som tam mal na mysli. 430 00:14:01,680 --> 00:14:03,270 A tak Jay šťastie obaja časy. 431 00:14:03,270 --> 00:14:06,685 A tiež šťastie v tom, že posledný rok, objednal som nejaké disky Blu-ray 432 00:14:06,685 --> 00:14:07,560 skutočne rozdávať. 433 00:14:07,560 --> 00:14:09,768 Je mi ľúto, tento rok sme nemal rovnaký Trevor. 434 00:14:09,768 --> 00:14:11,540 Ale stále lepšie bola o niekoľko rokov späť. 435 00:14:11,540 --> 00:14:14,820 A niektorí z vás možno vedia to chlapík, Sean, ktorý kedy bol v CS50, 436 00:14:14,820 --> 00:14:17,780 bol napádaný s presný Rovnaký problém, aj keď v SD, 437 00:14:17,780 --> 00:14:19,360 ako budete čoskoro vidieť, späť v deň. 438 00:14:19,360 --> 00:14:22,622 A zistíte, že nielenže to trvať trochu dlhšie, než Jay, 439 00:14:22,622 --> 00:14:25,580 o niečo dlhšie, než Trevora, to bolo vlastne to skvelá príležitosť 440 00:14:25,580 --> 00:14:29,820 aby sa zapojili takmer všetci v dav a la Price is Right, povzbudzujúci 441 00:14:29,820 --> 00:14:31,889 ho nájsť číslo sme hľadali. 442 00:14:31,889 --> 00:14:32,930 Poďme. sa rýchlo pozrieť. 443 00:14:32,930 --> 00:14:33,320 >> [Videoprehrávanie] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Takže váš úlohu tu, Sean, je nasledujúci. 446 00:14:36,680 --> 00:14:40,860 Som sa skrýva za tieto Dvere číslo sedem. 447 00:14:40,860 --> 00:14:45,120 Ale zastrčená v niektorej z týchto dverí ako aj iné záporné čísla. 448 00:14:45,120 --> 00:14:47,500 A vaším cieľom je si myslieť, tejto hornej rady čísel 449 00:14:47,500 --> 00:14:50,390 len ako pole, alebo len Sekvencie kusov papiera 450 00:14:50,390 --> 00:14:51,510 s číslami za nimi. 451 00:14:51,510 --> 00:14:55,540 A vaším cieľom je, iba pomocou hornej array tú, nájdite mi číslo sedem. 452 00:14:55,540 --> 00:14:58,570 A potom sme sa k posudku ako sa chodí robiť. 453 00:14:58,570 --> 00:14:59,070 -Dobre. 454 00:14:59,070 --> 00:15:00,850 -Find Nám číslo sedem, prosím. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nie. 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 >> [Smeje sa] 461 00:15:24,770 --> 00:15:25,910 >> To nie je 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 >> [Smeje sa] 466 00:15:34,695 --> 00:15:37,861 V tomto okamihu, skóre nie je príliš dobre, takže si pokojne ďalej. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tri. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Smeje sa] 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 Úprimne povedané, nemôžem si pomôcť, ale zaujímalo čo si dokonca myslieť, tak-- 474 00:15:50,690 --> 00:15:51,959 >> [Smeje sa] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Len horný rad, takže Máš tri doľava. 477 00:15:55,020 --> 00:15:56,200 Takže mi nájsť sedem. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Smeje sa] 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 Sedem. 484 00:16:26,946 --> 00:16:28,780 >> [APPLAUSE] 485 00:16:28,780 --> 00:16:29,426 >> Dobre. 486 00:16:29,426 --> 00:16:30,360 >> [END Prehrávanie] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. Malan: Takže sme mohli Sledujte tieto celý deň. 488 00:16:31,840 --> 00:16:34,090 A samozrejme, niektoré tohtoročné dema možná 489 00:16:34,090 --> 00:16:36,330 bude teraz skončí v budúcom Tohtoročné videa rovnako. 490 00:16:36,330 --> 00:16:39,040 Takže teraz poďme vlastne zamerať sa na algoritmoch 491 00:16:39,040 --> 00:16:42,140 tu, a uvidíme, či nemôžeme Teraz začínajú formalizovať 492 00:16:42,140 --> 00:16:46,650 ako môžeme ísť o získanie našich dát do tohto stavu, že je to radené, 493 00:16:46,650 --> 00:16:50,054 takže nakoniec môžeme skutočne prehľadávať efektívnejšie. 494 00:16:50,054 --> 00:16:52,470 A aj keď ideme použiť pomerne malé dátové súbory, 495 00:16:52,470 --> 00:16:54,511 rovnako ako osem čísel, ktoré máme tu na doske, 496 00:16:54,511 --> 00:16:58,230 nakoniec by sa mohli vzťahovať tie isté myšlienky 1000 vstupov, milión vstupov, 497 00:16:58,230 --> 00:17:02,100 4 miliardy vstupy, pretože algoritmy sa bude v podstate rovnaké. 498 00:17:02,100 --> 00:17:05,359 >> A tak to je naša posledná príležitosť pre dobrovoľníkov dnes, 499 00:17:05,359 --> 00:17:09,790 ale snáď najviac zapojení, kto, pre ktoré potrebujeme osem dobrovoľníkov 500 00:17:09,790 --> 00:17:12,960 prísť a ísť cez nás proces triedenia čo bude čoskoro 501 00:17:12,960 --> 00:17:15,212 byť na tieto hudbu tu stoja. 502 00:17:15,212 --> 00:17:16,170 Dovoľte mi začať tu. 503 00:17:16,170 --> 00:17:19,692 >> Takže človek v turquoise-- Zelená je to? 504 00:17:19,692 --> 00:17:21,130 Ste spáchanie? 505 00:17:21,130 --> 00:17:21,630 Dva. 506 00:17:21,630 --> 00:17:23,069 Poď dole. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Tri. 509 00:17:24,420 --> 00:17:25,400 Štyri. 510 00:17:25,400 --> 00:17:27,247 Nech me-- OK, päť. 511 00:17:27,247 --> 00:17:28,830 Ste bol nominovaný váš priateľ. 512 00:17:28,830 --> 00:17:31,340 Šesť, sedem a osem. 513 00:17:31,340 --> 00:17:32,130 Poď hore. 514 00:17:32,130 --> 00:17:32,630 Dobre. 515 00:17:32,630 --> 00:17:33,190 Ďakujem ti veľmi pekne. 516 00:17:33,190 --> 00:17:33,689 Poď hore. 517 00:17:33,689 --> 00:17:34,790 Poď hore. 518 00:17:34,790 --> 00:17:35,330 >> Dobre. 519 00:17:35,330 --> 00:17:38,890 Takže to, čo máme, a to here-- je medzi tými viac neobvyklých, 520 00:17:38,890 --> 00:17:42,390 pretože to bude vyžadovať, aby ste humor pre mňa len trochu času. 521 00:17:42,390 --> 00:17:43,442 Tie musia byť číslo jedna. 522 00:17:43,442 --> 00:17:44,150 Ako sa voláš? 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 Ako sa voláš? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. Malan: Joseph, ste číslo dva. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, číslo tri. 530 00:17:52,260 --> 00:17:53,722 Stefan, číslo štyri. 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äť. 533 00:17:57,548 --> 00:17:58,452 [Nepočuteľných] 534 00:17:58,452 --> 00:17:59,618 DAVID J. Malan: [Nepočuteľné]. 535 00:17:59,618 --> 00:18:00,391 David, číslo šesť. 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 sedem. 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 osem. 541 00:18:04,470 --> 00:18:04,970 Dobre. 542 00:18:04,970 --> 00:18:06,510 Ak could-- Och. 543 00:18:06,510 --> 00:18:08,820 Ak sa vám všetkým, ako vaše Prvý výzvou, tam 544 00:18:08,820 --> 00:18:10,820 osem hudobné stojany Tu smerom k divákom. 545 00:18:10,820 --> 00:18:14,200 Ak by ste mohli dať svoje číslo na tieto hudba stojí tak, 546 00:18:14,200 --> 00:18:16,560 že line up s rovnaké čísla na doske. 547 00:18:16,560 --> 00:18:19,560 Tak, aby sami vyzerať, že uvedenie vaše čísla na tieto hudby 548 00:18:19,560 --> 00:18:21,960 stojí tu. 549 00:18:21,960 --> 00:18:25,980 Vynikajúca tak ďaleko. 550 00:18:25,980 --> 00:18:26,600 >> Výborne. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Takže teraz, budeme sa opýtať otázka v niekoľkými rôznymi spôsobmi. 553 00:18:29,556 --> 00:18:31,610 Ako môžeme ísť o triedení títo ľudia tu hore? 554 00:18:31,610 --> 00:18:34,500 Pretože sme mali niekoľko prístupov skôr, pričom sme boli 555 00:18:34,500 --> 00:18:36,360 druh výroby dvoch rôznych vedierka. 556 00:18:36,360 --> 00:18:38,842 A potom sme boli všeobecne Zostavujeme veci dohromady. 557 00:18:38,842 --> 00:18:41,050 Akonáhle sme videli dve čísla že patria k sebe, 558 00:18:41,050 --> 00:18:41,975 sme dali dohromady. 559 00:18:41,975 --> 00:18:43,350 Dva listy, ktoré patria k sebe. 560 00:18:43,350 --> 00:18:45,058 >> Ale uvidíme, či budeme nemožno formalizovať to, 561 00:18:45,058 --> 00:18:48,044 takže nakoniec sme sa niektorí pseudo-kód budete, 562 00:18:48,044 --> 00:18:49,710 pomocou ktorého môžete vyriešiť tieto problémy. 563 00:18:49,710 --> 00:18:51,870 Takže teraz, som pozeral sa na týchto číslach tu. 564 00:18:51,870 --> 00:18:55,030 A vidím veľa chýb. 565 00:18:55,030 --> 00:18:57,750 Nakoniec, chcem, jeden na vľavo a ôsmich na pravej strane. 566 00:18:57,750 --> 00:19:00,650 >> A tak som pri pohľade na tieto dva, štyri a dva. 567 00:19:00,650 --> 00:19:02,930 A v čom je problém, samozrejme? 568 00:19:02,930 --> 00:19:04,261 Jo. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Dva zrejme príde skôr štyri, takže viete, čo? 571 00:19:07,160 --> 00:19:10,210 Dovoľte mi, aby som najprv sa chamtivý prístup, ak chcete, rovnako ako problém 572 00:19:10,210 --> 00:19:13,790 nastaviť one-- ak si spomínate z Standard Edition z problému nastaviť jednu, 573 00:19:13,790 --> 00:19:16,820 kde som len lokálne vyriešiť problém že je tu predo mnou 574 00:19:16,820 --> 00:19:17,690 a uvidíme, kam ma to vedie. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Tak dva a štyri, nechajte ma ísť dopredu a len prehodiť vy dvaja. 577 00:19:20,161 --> 00:19:22,400 Ak môžete fyzicky presunúť sami a váš papier, 578 00:19:22,400 --> 00:19:25,040 Myslím, že som vyzrel Zoznam v lepšom stave. 579 00:19:25,040 --> 00:19:26,330 >> Teraz, sú dobrí. 580 00:19:26,330 --> 00:19:28,480 Chystám sa ísť ďalej, štyri a šesť, vyzerá dobre. 581 00:19:28,480 --> 00:19:29,110 Žiaden problém. 582 00:19:29,110 --> 00:19:30,440 Šesť a osem, na tlačidlo OK. 583 00:19:30,440 --> 00:19:31,860 Osem a jeden, ďalší problém. 584 00:19:31,860 --> 00:19:34,750 Vzhľadom k tomu, čo je pravda o osem a jedna? 585 00:19:34,750 --> 00:19:36,990 Raz príde pred ôsmou, a tak čo by sme mali robiť? 586 00:19:36,990 --> 00:19:38,090 Poďme vymeniť aj týchto dvoch. 587 00:19:38,090 --> 00:19:39,316 Jeden a osem. 588 00:19:39,316 --> 00:19:40,690 A teraz, budem pokračovať. 589 00:19:40,690 --> 00:19:42,030 Budem hľadať ďalej dopredu. 590 00:19:42,030 --> 00:19:42,840 A uvidíme, čo sa stane. 591 00:19:42,840 --> 00:19:44,680 Osem a tri, z Samozrejme, mimo prevádzky. 592 00:19:44,680 --> 00:19:45,815 Poďme swapu. 593 00:19:45,815 --> 00:19:46,940 Osem a sedem, samozrejme. 594 00:19:46,940 --> 00:19:47,481 Mimo prevádzky. 595 00:19:47,481 --> 00:19:48,280 Poďme swapu. 596 00:19:48,280 --> 00:19:49,940 Osem a päť, samozrejme, poďme swapu. 597 00:19:49,940 --> 00:19:50,560 Dobre. 598 00:19:50,560 --> 00:19:51,880 Zoznam je zoradený. 599 00:19:51,880 --> 00:19:53,060 ano? 600 00:19:53,060 --> 00:19:54,280 >> OK, zrejme nie. 601 00:19:54,280 --> 00:19:55,860 Ale je to trochu lepšie, že jo? 602 00:19:55,860 --> 00:19:57,270 Vzhľadom k tomu, upozornenie, čo sa stalo. 603 00:19:57,270 --> 00:20:01,749 Zakaždým, keď sme vykonali výmenu, menšie Počet druh perkoluje takto, 604 00:20:01,749 --> 00:20:03,790 a väčšie číslo perkoluje týmto spôsobom, alebo budeme 605 00:20:03,790 --> 00:20:06,880 začať hovoriť bublala do vľavo alebo prebubláva doprava. 606 00:20:06,880 --> 00:20:10,080 >> Teraz, to nie je dosť, pretože prinajlepšom číslo by mohol 607 00:20:10,080 --> 00:20:11,990 sa posunie o jedno miesto vpred, alebo v najhoršom prípade, 608 00:20:11,990 --> 00:20:13,880 číslo môže mať posunie o jedno miesto ďalej. 609 00:20:13,880 --> 00:20:16,369 Takže viete, čo tento druh z fungovalo celkom dobre tak ďaleko. 610 00:20:16,369 --> 00:20:17,410 Dovoľte mi, aby som to skúsiť znova. 611 00:20:17,410 --> 00:20:18,880 Dva a štyri, sú v poriadku. 612 00:20:18,880 --> 00:20:20,180 Štyri a šesť, sú v poriadku. 613 00:20:20,180 --> 00:20:21,790 Šesť a jedným, mimo prevádzky. 614 00:20:21,790 --> 00:20:23,007 Takže poďme vymeniť vy dvaja. 615 00:20:23,007 --> 00:20:25,840 A teraz, Všimnite si, že problém je začína byť trochu zase lepší. 616 00:20:25,840 --> 00:20:27,006 Šesť a tri, mimo prevádzky. 617 00:20:27,006 --> 00:20:28,100 Poďme vymeniť vy dvaja. 618 00:20:28,100 --> 00:20:29,730 Šesť a sedem, si dobrý. 619 00:20:29,730 --> 00:20:32,230 Sedem a päť, samozrejme, mimo prevádzky. 620 00:20:32,230 --> 00:20:33,920 Sedem a osem, v uvedenom poradí. 621 00:20:33,920 --> 00:20:36,470 A teraz, by som mohol potrebovať to urobiť ešte niekoľkokrát. 622 00:20:36,470 --> 00:20:39,830 A v skutočnosti, myslím, že pre seba snáď koľkokrát maximálne 623 00:20:39,830 --> 00:20:41,330 Možno budem musieť chodiť sem a tam? 624 00:20:41,330 --> 00:20:42,390 >> Vrátime sa k tomu. 625 00:20:42,390 --> 00:20:43,700 Tak dve a štyri sú stále v poriadku. 626 00:20:43,700 --> 00:20:44,940 Štyri a jeden, ani náhodou. 627 00:20:44,940 --> 00:20:45,747 Takže, poďme výmenu. 628 00:20:45,747 --> 00:20:47,830 A opäť si všimnite, vizuálne jeden je druh prebublávania 629 00:20:47,830 --> 00:20:49,163 na ľavej strane, ak by malo byť. 630 00:20:49,163 --> 00:20:50,010 Štyri a tri odkladacie. 631 00:20:50,010 --> 00:20:51,330 Štyri a šesť. 632 00:20:51,330 --> 00:20:53,100 Šesť a päť swapu. 633 00:20:53,100 --> 00:20:53,959 Šesť a sedem. 634 00:20:53,959 --> 00:20:55,000 Sedem a osem je dobré. 635 00:20:55,000 --> 00:20:55,500 >> Dobre. 636 00:20:55,500 --> 00:20:58,460 Dostávame ešte lepší. 637 00:20:58,460 --> 00:20:59,130 Takže poďme sa pozrieť. 638 00:20:59,130 --> 00:21:00,940 Teraz máme dva a jeden. 639 00:21:00,940 --> 00:21:02,520 Samozrejme, vymeniť. 640 00:21:02,520 --> 00:21:07,520 Dva a tri, tri a štyri, a päť, šesť a sedem, sedem a osem. 641 00:21:07,520 --> 00:21:08,020 Dobre. 642 00:21:08,020 --> 00:21:08,730 A viete čo? 643 00:21:08,730 --> 00:21:11,190 Pretože som tam jednu zmenu, dovoľte mi urobiť jednu kontrolu zdravý rozum. 644 00:21:11,190 --> 00:21:13,023 Nechaj ma ísť celú cestu späť na začiatok. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 Jeden z nich, two-- Jo, vidíš? 647 00:21:14,750 --> 00:21:15,870 Niečo bolo zle. 648 00:21:15,870 --> 00:21:18,420 Tri, štyri, päť, šesť, sedem, osem. 649 00:21:18,420 --> 00:21:21,920 A v tomto poslednom priechodu, sú pohodlné s mojím teraz 650 00:21:21,920 --> 00:21:23,830 vyhlasovať, že to je triediť? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Vizuálne, že je to úplná pravda. 653 00:21:25,880 --> 00:21:28,410 Ale to, čo Funkčne sa tiež len tak 654 00:21:28,410 --> 00:21:31,870 V tej poslednej priechod, ktorá vám umožní potvrdiť, že tento zoznam je naozaj 655 00:21:31,870 --> 00:21:32,660 radené? 656 00:21:32,660 --> 00:21:34,477 >> Čo som urobil, alebo nie tento posledný pas? 657 00:21:34,477 --> 00:21:35,810 Divákov: nedošlo k žiadnym zmenám. 658 00:21:35,810 --> 00:21:36,120 DAVID J. Malan: Sorry? 659 00:21:36,120 --> 00:21:37,070 Divákov: žiadne zmeny. 660 00:21:37,070 --> 00:21:38,653 DAVID J. Malan: nedošlo k žiadnym zmenám. 661 00:21:38,653 --> 00:21:41,947 Tak to by bolo hlúpe ma Urob to rovnaký algoritmus znovu 662 00:21:41,947 --> 00:21:43,780 keby som neurobil akýkoľvek zmení prvýkrát. 663 00:21:43,780 --> 00:21:45,160 A stať sa nezmenil. 664 00:21:45,160 --> 00:21:47,576 Iste, nebudem robiť Akékoľvek zmeny druhýkrát. 665 00:21:47,576 --> 00:21:49,820 A tak je to teraz v bezpečí hovoriť, zoznam je triedený. 666 00:21:49,820 --> 00:21:52,069 >> A skutočne, to je teraz niečo, že budeme všeobecne 667 00:21:52,069 --> 00:21:56,900 hovor bublinkové radenie, pričom po dvoch, znovu opraviť chyby, 668 00:21:56,900 --> 00:22:00,210 a znova a znova, a tí udržať tam a späť, 669 00:22:00,210 --> 00:22:03,370 a sem a tam, kým sa neposkytujeme žiadne také swapy, na ktorom mieste 670 00:22:03,370 --> 00:22:07,089 môžete si byť istí, jo, ja dokončil upevnenie všetky chyby. 671 00:22:07,089 --> 00:22:08,630 Poďme reset a skúsiť iný prístup. 672 00:22:08,630 --> 00:22:11,590 Ak vy mohol vrátiť do poradie ste pred chvíľou, 673 00:22:11,590 --> 00:22:13,780 ktorý vyzeral takto. 674 00:22:13,780 --> 00:22:17,640 Teraz sa poďme k prístupu, ktorý trochu viac ako skúšku knihe, 675 00:22:17,640 --> 00:22:21,122 kedy sme boli neustále výberom písmeno abecedy 676 00:22:21,122 --> 00:22:22,830 že sme trochu chceli riešiť ďalšie. 677 00:22:22,830 --> 00:22:26,420 Možno to bol vysoký list, Rovnako ako, alebo s nízkou písmeno Z. 678 00:22:26,420 --> 00:22:28,170 >> Takže každý je späť v tomto poradí. 679 00:22:28,170 --> 00:22:29,800 A teraz ma to urobiť. 680 00:22:29,800 --> 00:22:34,880 Poďme sa pozrieť, viem, že mám osem čísla tu. 681 00:22:34,880 --> 00:22:37,410 Chystám sa ísť dopredu a len zámerne zvoľte 682 00:22:37,410 --> 00:22:38,520 najmenší prvky. 683 00:22:38,520 --> 00:22:38,760 Je to tak? 684 00:22:38,760 --> 00:22:39,801 To sa zdá byť intuitívne taky. 685 00:22:39,801 --> 00:22:42,560 Prečo mi pripadá najmenšiu prvok, vložte ju tam, kam patrí, 686 00:22:42,560 --> 00:22:45,280 potom dostanete ďalšie najmenší prvok, dal je tam, kam patrí, a len zopakovať. 687 00:22:45,280 --> 00:22:46,820 >> Vzhľadom k tomu, intuitívne, ktorý by mal fungovať tiež. 688 00:22:46,820 --> 00:22:48,441 Tak štyri, to je celkom malý počet. 689 00:22:48,441 --> 00:22:49,940 Idem si spomenúť, kde to je. 690 00:22:49,940 --> 00:22:50,523 Počkaj minútu. 691 00:22:50,523 --> 00:22:51,577 Two je menšia. 692 00:22:51,577 --> 00:22:53,910 Dovoľte mi teraz spomenúť, kde dvoch je, a zabudnúť na štyri. 693 00:22:53,910 --> 00:22:55,050 Vybavíme to neskôr. 694 00:22:55,050 --> 00:22:56,460 Šesť, nemám záujem. 695 00:22:56,460 --> 00:22:57,810 Osem, nemám záujem. 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 budem pamätať, kde jeden je. 698 00:23:01,470 --> 00:23:02,534 Tri, nemám záujem. 699 00:23:02,534 --> 00:23:03,450 Sedem, nemám záujem. 700 00:23:03,450 --> 00:23:04,530 Five, nemám záujem. 701 00:23:04,530 --> 00:23:07,390 >> Takže bez pádu fázy v tomto roku, 702 00:23:07,390 --> 00:23:09,890 Chystám sa chytiť počet one-- a to, čo bolo zasa Vaše meno? 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 keby ste sa mnou na začiatok zoznamu 706 00:23:13,540 --> 00:23:14,870 poďme ťa tam, kam patríte. 707 00:23:14,870 --> 00:23:16,080 Bohužel-- Ako sa voláte? 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 ceste. 710 00:23:18,191 --> 00:23:23,490 Takže ako Stefan rieši tento Problém, čo by sme mali robiť? 711 00:23:23,490 --> 00:23:25,412 Čo budeme robiť s Stefan? 712 00:23:25,412 --> 00:23:27,269 >> Divákov: [Nepočuteľné]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. Malan: OK. 714 00:23:28,060 --> 00:23:28,850 Takže sme mohli urobiť. 715 00:23:28,850 --> 00:23:31,730 Mohli by sme nejako vziať Stefan a jeho štyri, a len dať to do premennej 716 00:23:31,730 --> 00:23:33,530 a držať sa jej za určité množstvo času, 717 00:23:33,530 --> 00:23:35,220 čím sa vytvorí priestor pre číslo jedna. 718 00:23:35,220 --> 00:23:36,280 A to nie je zlé. 719 00:23:36,280 --> 00:23:39,270 Mohol by som navrhnúť, prečo nie sme len dať tú Stefana? 720 00:23:39,270 --> 00:23:41,610 Prečo by to mohlo porušiť jeden nápadov sme začali 721 00:23:41,610 --> 00:23:44,830 hovorí o minule, minulý týždeň? 722 00:23:44,830 --> 00:23:45,330 Jo? 723 00:23:45,330 --> 00:23:45,740 >> Divákov: [Nepočuteľné]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. Malan: Neexistuje žiadny index pre neho. 725 00:23:46,860 --> 00:23:49,735 Ak si myslíte o tom, naozaj, ako pole, to je ako negatívne, 726 00:23:49,735 --> 00:23:52,900 takže nie je žiadna pamäťová vlastne Tu, ak je to skutočne poľa, 727 00:23:52,900 --> 00:23:55,090 ako sme deklarovali minulý týždeň v prednáške. 728 00:23:55,090 --> 00:23:56,250 Takže by sme nemali robiť. 729 00:23:56,250 --> 00:23:57,340 Môžeme uložiť ho do premennej. 730 00:23:57,340 --> 00:23:57,820 >> Alebo viete čo? 731 00:23:57,820 --> 00:23:59,153 Počul som, že niekto iný to naznačujú. 732 00:23:59,153 --> 00:24:01,020 Čo iného môžeme robiť s Stefan? 733 00:24:01,020 --> 00:24:03,770 Prečo sme ho len vysťahovať a ho cez číslo jedna, kde bol. 734 00:24:03,770 --> 00:24:05,170 Takže ak chcete ísť tam. 735 00:24:05,170 --> 00:24:07,300 A skutočne, to je celkom dobré riešenie. 736 00:24:07,300 --> 00:24:10,480 Teraz na jednej strane, som druh z robil problém ešte horšie. 737 00:24:10,480 --> 00:24:13,650 Štyri je teraz ďalej od miesta, kde by mala byť. 738 00:24:13,650 --> 00:24:14,900 To by malo byť k tomuto polovicu. 739 00:24:14,900 --> 00:24:16,100 >> Ale viete čo? 740 00:24:16,100 --> 00:24:17,630 To by mohlo byť smola. 741 00:24:17,630 --> 00:24:18,822 Možno, že číslo osem pozeral. 742 00:24:18,822 --> 00:24:20,530 A tak, možno by sme sa dostali šťastie, 743 00:24:20,530 --> 00:24:22,460 a tlačil ôsmich bližšie ku koncu. 744 00:24:22,460 --> 00:24:24,710 Takže na konci dňa, celkom to všetky priemery von. 745 00:24:24,710 --> 00:24:26,085 Nemusíme sa starať o štyri. 746 00:24:26,085 --> 00:24:29,400 Všetko o čo sa starám práve teraz výberu najmenší prvok. 747 00:24:29,400 --> 00:24:32,030 >> A teraz, čo budem urobiť, je zabudnúť na číslo jedna 748 00:24:32,030 --> 00:24:35,160 natrvalo, pretože viem, že Zoznam za mnou je teraz zoradené. 749 00:24:35,160 --> 00:24:36,720 Takže môj zoznam bol predtým veľkosti osem. 750 00:24:36,720 --> 00:24:37,720 Teraz je to o veľkosti sedem. 751 00:24:37,720 --> 00:24:40,340 Takže môj problém je dostať menšie, ale napriek tomu lineárne. 752 00:24:40,340 --> 00:24:43,022 Takže teraz, budem vyberte prúd najmenší prvok, dva. 753 00:24:43,022 --> 00:24:46,520 Šesť, osem, štyri, tri, sedem, päť. 754 00:24:46,520 --> 00:24:47,770 To bol ten najmenší prvok. 755 00:24:47,770 --> 00:24:49,416 Tak čo mám robiť with-- čo bol opäť Vaše meno? 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 nechať Jozefa na mieste. 759 00:24:52,000 --> 00:24:54,842 Teraz, budem predstierať že týchto ľudí are-- dobre, 760 00:24:54,842 --> 00:24:56,550 Viem, že tieto dve už je zoradený. 761 00:24:56,550 --> 00:24:58,424 Poďme sa teraz zameriavajú na Zostávajúcu časť zoznamu. 762 00:24:58,424 --> 00:25:00,080 Šesť je aktuálna najmenší. 763 00:25:00,080 --> 00:25:01,190 Osem je väčšia. 764 00:25:01,190 --> 00:25:02,970 Štyri je teraz aktuálne najmenší. 765 00:25:02,970 --> 00:25:04,762 Tri je teraz aktuálne najmenší. 766 00:25:04,762 --> 00:25:07,720 A tak teraz, budem vybrať tri, kto je-- aké je vaše meno 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, keby mohol 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 Poď späť, a my sme chystá vymeniť tie dva. 772 00:25:15,220 --> 00:25:17,360 A teraz, poďme dať na autopilota to. 773 00:25:17,360 --> 00:25:21,589 Chystám sa ísť a nechať to na vás chlapci zvoliť najbližší menšie prvky. 774 00:25:21,589 --> 00:25:22,380 Dún, šedivý, šedivý, dún. 775 00:25:22,380 --> 00:25:24,560 Číslo štyri, čo by ste mali robiť? 776 00:25:24,560 --> 00:25:26,261 Výborne. 777 00:25:26,261 --> 00:25:27,760 Teraz, budem robiť ďalšie prihrávka. 778 00:25:27,760 --> 00:25:28,590 Dún, šedivý, šedivý, dún. 779 00:25:28,590 --> 00:25:31,465 Vidím piatich je ďalší najmenší. 780 00:25:31,465 --> 00:25:32,840 Teraz, budem trvať ďalšie prihrávka. 781 00:25:32,840 --> 00:25:33,631 Dún, šedivý, šedivý, dún. 782 00:25:33,631 --> 00:25:34,880 Šesť je najmenší. 783 00:25:34,880 --> 00:25:35,520 Dobre. 784 00:25:35,520 --> 00:25:36,585 Sedem je najmenší. 785 00:25:36,585 --> 00:25:37,085 Žiadna zmena. 786 00:25:37,085 --> 00:25:38,630 Osem je najmenší. 787 00:25:38,630 --> 00:25:39,170 Hotovo. 788 00:25:39,170 --> 00:25:43,900 >> Takže to, čo sme práve vykonáva opakovane výber jedného prvku za sebou 789 00:25:43,900 --> 00:25:47,230 je implementovať niečo, čo sme bude formalizovať ako výber druhu. 790 00:25:47,230 --> 00:25:49,120 A to je možno aj jednoduchšie na vysvetlenie, 791 00:25:49,120 --> 00:25:51,310 v tom, že doslova po vás chcieť urobiť, je len udržať 792 00:25:51,310 --> 00:25:54,700 tam a späť cez zoznam výberu, ďalší najmenší prvok, 793 00:25:54,700 --> 00:25:55,720 kým máte hotovo. 794 00:25:55,720 --> 00:25:58,650 >> Takže je to ešte jednoduchšie, snáď intuitívne, než posledný. 795 00:25:58,650 --> 00:26:00,020 Skúsme posledná jeden. 796 00:26:00,020 --> 00:26:03,060 Ak vy sami mohli obnoviť do nasledujúcich polôh 797 00:26:03,060 --> 00:26:08,600 jeden posledný čas, uvidíme, či nemôžeme Teraz formalizovať jednu ďalší postup. 798 00:26:08,600 --> 00:26:12,857 V skutočnosti, by niekto tam chcel navrhnúť, 799 00:26:12,857 --> 00:26:14,440 ako inak by sme mohli ísť asi robí? 800 00:26:14,440 --> 00:26:17,439 Bez hodil out módne slová alebo zoradiť z odpovedí, ktoré sú už známe, 801 00:26:17,439 --> 00:26:19,689 len intuitívne, čo sme mohli robiť? 802 00:26:19,689 --> 00:26:21,635 >> Divákov: [Nepočuteľné]. 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 nejaký veľký intuície. 805 00:26:24,620 --> 00:26:28,020 Dobré veci sa zdá, tak ďaleko sa stalo v oblasti počítačovej vedy, keď sme sa rozdeliť 806 00:26:28,020 --> 00:26:30,832 a dobyť problém delenie je na polovicu a pol na pol. 807 00:26:30,832 --> 00:26:32,540 A tak my, mohol začať robiť to. 808 00:26:32,540 --> 00:26:35,754 A v skutočnosti, že to bude, budeme vidieť, jeden z našich najlepších riešení doteraz. 809 00:26:35,754 --> 00:26:37,420 Ale poďme sa vrátiť k tomu onedlho. 810 00:26:37,420 --> 00:26:40,500 V skutočnosti, budeme robiť že o niečo neskôr tento týždeň. 811 00:26:40,500 --> 00:26:42,180 Čo iné môžeme robiť to vyriešiť? 812 00:26:42,180 --> 00:26:44,647 Takže všetci tu je v zdanlivo náhodnom poradí. 813 00:26:44,647 --> 00:26:45,230 Vieš čo? 814 00:26:45,230 --> 00:26:48,320 Skôr ako ísť tam a späť, sem a tam, tam a späť 815 00:26:48,320 --> 00:26:50,624 zakaždým, to cíti ako Robím veľa chôdze. 816 00:26:50,624 --> 00:26:52,790 Prečo som sa začať na začiatok zoznamu 817 00:26:52,790 --> 00:26:54,960 a len dať štyri kam patrí? 818 00:26:54,960 --> 00:26:59,680 Dovoľte mi teda predpokladať, že pre túto chvíľu môj zoznam je len tento prvý prvok. 819 00:26:59,680 --> 00:27:04,937 So štyrmi radené v tomto okamihu v čase, ak všetko ma zaujíma, je tu všetko? 820 00:27:04,937 --> 00:27:06,520 To je trochu triviálne pravda, že jo? 821 00:27:06,520 --> 00:27:10,000 Rovnako ako v zozname, ktorý obsahuje jedno číslo, a že číslo štyri je samozrejme zoradené. 822 00:27:10,000 --> 00:27:13,070 >> Takže mi dovoľte stanoviť že tento zoznam je zoradený. 823 00:27:13,070 --> 00:27:15,090 Ale teraz mám zvyšok tohto zoznamu. 824 00:27:15,090 --> 00:27:17,240 Takže teraz, som sa stretávajú dva. 825 00:27:17,240 --> 00:27:21,690 Kde sa dva zjavne patria s ohľadom na štyri? 826 00:27:21,690 --> 00:27:22,580 Pred štyri. 827 00:27:22,580 --> 00:27:23,862 Takže to, čo môžem robiť? 828 00:27:23,862 --> 00:27:24,820 Čo sa voláš? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. Malan: Joseph, ak by ste mohli krok späť 831 00:27:26,030 --> 00:27:27,790 na chvíľku so svojím číslom. 832 00:27:27,790 --> 00:27:31,130 A teraz, čo by mal robiť Stefan tu? 833 00:27:31,130 --> 00:27:33,720 Poďme posun Stefana tu. 834 00:27:33,720 --> 00:27:35,520 A teraz, nech Joseph prísť sem. 835 00:27:35,520 --> 00:27:39,660 A teraz mi dovoľte, aby som tvrdia, že Všetko je tu radené. 836 00:27:39,660 --> 00:27:42,474 Takže, Podobný výsledok, ale zásadne odlišný prístup. 837 00:27:42,474 --> 00:27:44,140 Ani som sa pozrel, čo tam dole. 838 00:27:44,140 --> 00:27:46,310 Len som pokračovať v užívaní prvky ako sa im odovzdali mi, 839 00:27:46,310 --> 00:27:47,240 a vysporiadať sa s nimi. 840 00:27:47,240 --> 00:27:48,330 >> Takže teraz, vidím číslo šesť. 841 00:27:48,330 --> 00:27:51,110 Kde sa číslo šesť patrí? 842 00:27:51,110 --> 00:27:53,250 Máme dve, štyri, šesť. 843 00:27:53,250 --> 00:27:54,800 Presne tam, kde ona je práve teraz. 844 00:27:54,800 --> 00:27:57,750 Takže nechajme to samo o sebe, a teraz tvrdí, že tejto časti zoznamu 845 00:27:57,750 --> 00:27:58,772 Teraz je zoradený. 846 00:27:58,772 --> 00:28:01,230 A tak, to cíti zásadne líšia v tom, ja som len 847 00:28:01,230 --> 00:28:05,230 pohybujúce sa v zozname tu lineárne, a ja som sa nikdy zdvojnásobenie späť. 848 00:28:05,230 --> 00:28:05,730 Áno. 849 00:28:05,730 --> 00:28:06,230 Dobre. 850 00:28:06,230 --> 00:28:08,190 Tak osem, kam patríte? 851 00:28:08,190 --> 00:28:08,730 Práve tu. 852 00:28:08,730 --> 00:28:09,310 Perfektné. 853 00:28:09,310 --> 00:28:10,210 Takže teraz, 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 Teraz, v predchádzajúcom algoritmu, Len som vymenil ľudí. 857 00:28:15,690 --> 00:28:18,648 Tak som mu mohol dať celú cestu na začiatok, ale potom sa sťahoval Joseph. 858 00:28:18,648 --> 00:28:21,450 Ale keď som sa presunúť Joseph, teraz čo sa deje, aby byť zle? 859 00:28:21,450 --> 00:28:24,250 >> A teraz, som nejako undone-- som vziať jeden krok vpred a potom 860 00:28:24,250 --> 00:28:26,300 jeden krok späť, pretože teraz Josef by bolo mimo prevádzky. 861 00:28:26,300 --> 00:28:26,830 Tak ideme na to. 862 00:28:26,830 --> 00:28:29,150 Ak by ste mohli mať číslo jedna a krok späť len na chvíľu. 863 00:28:29,150 --> 00:28:30,490 Ako môžeme put-- čo bol opäť Vaše meno? 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 mieste? 866 00:28:32,610 --> 00:28:36,091 Čo sa má stať, pokiaľ ide na dve, štyri, šesť a osem? 867 00:28:36,091 --> 00:28:37,570 Tí všetci potrebujú posunúť. 868 00:28:37,570 --> 00:28:42,590 Takže ak ôsmich chceli posunúť prvý, potom šesť, potom štyri, potom dve. 869 00:28:42,590 --> 00:28:45,380 A potom Annan, ak by ste Páči sa prísť sem, dobre. 870 00:28:45,380 --> 00:28:47,760 Ale tu, práve sme druh zaplatil cenu 871 00:28:47,760 --> 00:28:49,510 na inom mieste v algoritme. 872 00:28:49,510 --> 00:28:52,550 Kým minule s výberom triedenie, a dokonca aj bublinkové radenia, 873 00:28:52,550 --> 00:28:54,700 Idem späť a tam, tam a späť, 874 00:28:54,700 --> 00:28:58,360 ktorá je určite sčítanie časovo a doslova postupne. 875 00:28:58,360 --> 00:29:00,660 >> Insertion sort, najprv pohľad, vyzerá, že je to 876 00:29:00,660 --> 00:29:05,150 výborný múdrejší, v tom, že som len robiť pomalý, postupný pokrok, 877 00:29:05,150 --> 00:29:07,120 ale nehodlám to tam a späť. 878 00:29:07,120 --> 00:29:09,410 Ale ak niekto skutočne mimo prevádzku, oznámenia 879 00:29:09,410 --> 00:29:10,840 všetky práce som musel urobiť. 880 00:29:10,840 --> 00:29:14,750 Musel som sa presunúť polovicu zoznamu len aby sa priestor pre číslo jedna. 881 00:29:14,750 --> 00:29:16,790 Takže je to rovnaká suma práce doteraz ju 882 00:29:16,790 --> 00:29:18,690 cíti, len iný druh práce. 883 00:29:18,690 --> 00:29:19,370 >> Poďme pokračovať. 884 00:29:19,370 --> 00:29:22,657 Takže teraz vieme, že každý medzi jedným a osem sú zoradené. 885 00:29:22,657 --> 00:29:23,740 Tu mám číslo tri. 886 00:29:23,740 --> 00:29:25,864 Ak máte radi vyzdvihnúť číslo tri, jeden krok späť. 887 00:29:25,864 --> 00:29:28,260 A čo vy musíte urobiť? 888 00:29:28,260 --> 00:29:28,760 Jo. 889 00:29:28,760 --> 00:29:33,070 Tak to je ešte jeden, dva, tri kroky. 890 00:29:33,070 --> 00:29:36,010 Tri jednotky času, ktorý práve stáli ma, takže tri môžu teraz zmestí. 891 00:29:36,010 --> 00:29:37,460 A konečne, sedem. 892 00:29:37,460 --> 00:29:39,730 >> Poďme ďalej a majú si vziať krok späť. 893 00:29:39,730 --> 00:29:42,780 Toto je ešte len vo chvíli, aby nám štát jedna jednotka času, ale to je v poriadku. 894 00:29:42,780 --> 00:29:44,170 A teraz, päť deje na byť o niečo drahšie. 895 00:29:44,170 --> 00:29:45,340 Ak by ste chceli urobiť krok späť. 896 00:29:45,340 --> 00:29:48,380 Musíme sa pohybovať osem, a sedem a šesť. 897 00:29:48,380 --> 00:29:50,749 A potom sa všetci je teraz zoradené. 898 00:29:50,749 --> 00:29:52,290 Tak veľká ruka našim dobrovoľníkom tu. 899 00:29:52,290 --> 00:29:53,554 Ďakujem ti veľmi pekne. 900 00:29:53,554 --> 00:29:56,220 >> [APPLAUSE] 901 00:29:56,220 --> 00:29:56,860 >> Ďakujem vám všetkým. 902 00:29:56,860 --> 00:29:57,520 Ďakujem vám všetkým. 903 00:29:57,520 --> 00:30:02,940 Tak uvidíme, teraz len, ako nákladné to všetko bolo. 904 00:30:02,940 --> 00:30:06,210 Poďme zvážiť možná najjednoduchšie z nich, bublinkové radenie. 905 00:30:06,210 --> 00:30:09,950 A ja hovorím najjednoduchšie, len preto, môžete vyriešiť ju nenásytne obyčajným 906 00:30:09,950 --> 00:30:11,660 vyriešiť pairwise problém. 907 00:30:11,660 --> 00:30:13,720 Opraviť pairwise problém Tu, znovu a znovu 908 00:30:13,720 --> 00:30:17,680 a znovu, opakovanie toľko koľkokrát je skutočne potrebujú, aby. 909 00:30:17,680 --> 00:30:21,050 >> Tak to dopadá, že s bublinou druhu, dobre, 910 00:30:21,050 --> 00:30:25,820 koľko krokov musím prijať Prvý priechod z tohto algoritmu? 911 00:30:25,820 --> 00:30:30,850 Mohol by som take-- poďme see-- jedného, dva, tri, štyri, päť, šesť, sedem. 912 00:30:30,850 --> 00:30:32,190 A je tu osem elementov sem. 913 00:30:32,190 --> 00:30:35,280 Takže je to ako n mínus 1 krokov k sa od začiatku zoznamu 914 00:30:35,280 --> 00:30:36,380 na koniec zoznamu. 915 00:30:36,380 --> 00:30:41,350 >> Ale s výberom Triediť, pripomenúť, že ja som znovu a znovu Výber prvkov 916 00:30:41,350 --> 00:30:44,590 a znovu to najmenšie, Dávam to na mieste, 917 00:30:44,590 --> 00:30:46,616 ale potom som nie som pozerá za mnou znova. 918 00:30:46,616 --> 00:30:49,490 Takže si myslím, že je to trochu jasnejšie potom, že prvýkrát, môžem 919 00:30:49,490 --> 00:30:52,680 musieť vziať všetky n mínus 1 stupni nájsť najmenší prvok. 920 00:30:52,680 --> 00:30:55,920 Potom som dal je na mieste, a ja vypudiť ten, kto tu bol predtým. 921 00:30:55,920 --> 00:30:57,500 >> Ale potom som si nemusím držať pri pohľade na tento prvok, 922 00:30:57,500 --> 00:30:59,040 pretože viem, že je to Už najmenšie. 923 00:30:59,040 --> 00:31:01,581 Takže teraz, môžem sa pozrieť na práve siedmich elementov a potom šesť prvky, 924 00:31:01,581 --> 00:31:03,290 potom päť prvkov, potom štyri elementy. 925 00:31:03,290 --> 00:31:06,900 A tak matematicky, ak n je počet prvkov alebo čísel 926 00:31:06,900 --> 00:31:11,990 že sme začali s, ktore si možno predstavit že sa jedná o rovnaké ako n mínus 1, 927 00:31:11,990 --> 00:31:14,250 a n mínus 2 stupne, a n mínus 3 stupne, 928 00:31:14,250 --> 00:31:16,780 plus n mínus 4 kroky, a to tým až na doraz jednom kroku. 929 00:31:16,780 --> 00:31:18,160 A ja som na poslednú osobu. 930 00:31:18,160 --> 00:31:20,650 >> A ak si spomínate, že veľa Štatistiky knihy alebo matematické knihy 931 00:31:20,650 --> 00:31:24,730 mať tie vzorce na strane Viazaná zadné alebo predné z nich, 932 00:31:24,730 --> 00:31:27,690 Ukazuje sa, že tejto sérii môže byť vyjadrená jednoduchšie 933 00:31:27,690 --> 00:31:28,857 ako n krát n mínus 1 nad 2. 934 00:31:28,857 --> 00:31:31,273 A to je v poriadku, ak to nie je v popredí svojej mysli. 935 00:31:31,273 --> 00:31:32,420 To je však skutočne pravda. 936 00:31:32,420 --> 00:31:34,449 To je len jednoduchší spôsob písania. 937 00:31:34,449 --> 00:31:36,240 A potom, ak si myslíte, späť na základnej škole, 938 00:31:36,240 --> 00:31:38,698 keď ste práve spustenie násobí veci, to samozrejme, 939 00:31:38,698 --> 00:31:41,820 práve n druhú mínus n deleno 2. 940 00:31:41,820 --> 00:31:44,772 Všetko, čo som urobil, je rozšíriť výrazy tam. 941 00:31:44,772 --> 00:31:46,730 A tak sa poďme prepísať trochu inak. 942 00:31:46,730 --> 00:31:49,780 To n štvorčekované delí o 2 mínus N / 2. 943 00:31:49,780 --> 00:31:53,270 >> Takže znovu, som len trochu uplatnenie niektorí aritmetický pravidlá tu. 944 00:31:53,270 --> 00:31:57,140 Nevšimnúť teraz, že najväčší termín v tomto výraze, aby som tak povedal, 945 00:31:57,140 --> 00:31:58,540 je to, že n na druhú. 946 00:31:58,540 --> 00:32:02,910 Takže áno, je to n kvadrát delené 2, mínus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Všeobecne ale, ak je n je Bude to veľká hodnota, 948 00:32:05,080 --> 00:32:08,740 Budem tvrdiť, že n štvorcový bude dominantným faktorom. 949 00:32:08,740 --> 00:32:10,490 Je to len bude väčší prispievateľ 950 00:32:10,490 --> 00:32:12,877 na počte krokov, ako n / 2. 951 00:32:12,877 --> 00:32:13,960 Tak čo tým myslím? 952 00:32:13,960 --> 00:32:16,795 Skúsme si jednoduchý príklad, a to aj hoci matematika dostane trochu veľký. 953 00:32:16,795 --> 00:32:20,210 >> Takže predpokladám, že sme mali 1 milión ľudí na javisku, alebo 1 milión vecí 954 00:32:20,210 --> 00:32:21,320 že chceme usporiadať. 955 00:32:21,320 --> 00:32:23,730 Poďme zapojte milión do presne v tomto vzorci 956 00:32:23,730 --> 00:32:27,230 vidieť, koľko krokov to trvá celkom triediť milión prvky pomocou povedzme, 957 00:32:27,230 --> 00:32:28,560 výber triedenia. 958 00:32:28,560 --> 00:32:30,760 >> Takže budeme mať rovnaký vzorec ako predtým. 959 00:32:30,760 --> 00:32:34,120 Ja by som pripojiť milión, tak, že som si milión štvorčekované delené 2, 960 00:32:34,120 --> 00:32:35,990 mínus jeden milión deleno 2. 961 00:32:35,990 --> 00:32:40,180 Ak sa mi, že matematiku v predstihu tu máme 500 miliárd 962 00:32:40,180 --> 00:32:47,460 mínus 500000, ktorý nám dáva 499999500000, 963 00:32:47,460 --> 00:32:49,270 čo je sakramentsky veľký. 964 00:32:49,270 --> 00:32:54,370 >> V skutočnosti, ak si porovnať teraz 499000000000, 999000000, 965 00:32:54,370 --> 00:33:01,210 500000 proti našej pôvodnej hodnoty, 500000000000, je to tak sakramentsky blízko. 966 00:33:01,210 --> 00:33:06,850 Je to tak? n štvorčekované deleno 2 dáva us-- alebo skôr, n štvorčekované deleno 2 967 00:33:06,850 --> 00:33:08,370 dal nám 500 miliárd. 968 00:33:08,370 --> 00:33:13,510 To je sakramentsky blízko na 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 čo znamená, že sa odpočíta off 500000, alebo všeobecnejšie, odpočítaním off 970 00:33:17,970 --> 00:33:20,010 n štvorčekované, nie je naozaj veľký problém. 971 00:33:20,010 --> 00:33:22,490 N štvorcový robí tieto Čísla rastú naozaj rýchlo. 972 00:33:22,490 --> 00:33:25,790 >> Teraz, to je dôležité len do tej miery ako my, ako počítačových vedcov, 973 00:33:25,790 --> 00:33:29,350 sú všeobecne nebude toľko starostlivosti o nuansy týchto vzorkách 974 00:33:29,350 --> 00:33:31,400 a čo presne presné odpovede. 975 00:33:31,400 --> 00:33:33,390 Vieme len, že starostlivosť, viete čo? 976 00:33:33,390 --> 00:33:37,810 Na konci dňa, tento vzorec je na poradie n štvorcový. 977 00:33:37,810 --> 00:33:39,350 >> Áno, sme vydelením 2 v tam. 978 00:33:39,350 --> 00:33:41,360 Áno, budeme odčítať z n mínus 2. 979 00:33:41,360 --> 00:33:46,860 Ale na konci dňa, termín že nás naozaj bolí a stojí nás 980 00:33:46,860 --> 00:33:48,995 veľa krokov, je to, že námestie termín. 981 00:33:48,995 --> 00:33:51,370 A tak to, čo počítačový vedec bude všeobecne robiť 982 00:33:51,370 --> 00:33:54,160 je ignorovať všetky tie menších objednávok podmienky, 983 00:33:54,160 --> 00:33:56,900 a len sa pozrite na ten, ktorý najviac prispieva k nákladom. 984 00:33:56,900 --> 00:34:00,530 >> A to je pekné, pretože môžeme teraz hovoriť v oveľa väčšej univerzálnosti 985 00:34:00,530 --> 00:34:02,470 o algoritmy, a môžu porovnávať ich. 986 00:34:02,470 --> 00:34:04,550 A skutočnosť, že som O použití tohto je zámerné. 987 00:34:04,550 --> 00:34:06,680 Keď poviem, že na objednávke o, ja som konkrétne 988 00:34:06,680 --> 00:34:09,560 s odkazom na niečo volal veľký O. A big O 989 00:34:09,560 --> 00:34:14,090 je zápis, že počítač vedec používa na opis 990 00:34:14,090 --> 00:34:16,710 horná hranica niečo. 991 00:34:16,710 --> 00:34:21,150 >> Takže keď hovoríte, že algoritmus je vo veľkom O z n na druhú, 992 00:34:21,150 --> 00:34:23,380 ako som navrhol len pred chvíľou, že prostriedky 993 00:34:23,380 --> 00:34:27,710 že pokiaľ ide o jej chod úväzok alebo jeho účinnosť, 994 00:34:27,710 --> 00:34:30,090 to znamená v poriadku n druhú krokov. 995 00:34:30,090 --> 00:34:31,420 Možno viac, možno menej. 996 00:34:31,420 --> 00:34:33,435 Ale to je na poradie n na druhú. 997 00:34:33,435 --> 00:34:34,560 A to je horná hranica. 998 00:34:34,560 --> 00:34:36,530 Nie je to bude viac bolestivé než to. 999 00:34:36,530 --> 00:34:40,800 Nie je to bude n kubický, alebo 2 na n, alebo niečo oveľa väčšieho. 1000 00:34:40,800 --> 00:34:43,800 Jedná sa o hornú hranicu Na čo to je cena. 1001 00:34:43,800 --> 00:34:46,150 Takže vzhľadom k tomu, poďme zvážiť len niekoľko príkladov. 1002 00:34:46,150 --> 00:34:49,820 A to je len konečný zoznam veľmi časté prevádzková doba 1003 00:34:49,820 --> 00:34:52,870 pre algoritmy, ktorý je určený na ilustratívny niektorých vecí, ktoré sme 1004 00:34:52,870 --> 00:34:53,600 Videl už. 1005 00:34:53,600 --> 00:34:58,060 >> Tak napríklad v prípade výber triedenie, čo som tvrdil tu 1006 00:34:58,060 --> 00:35:02,250 je beh tejto výberom Triediť je čas je na poradie n na druhú. 1007 00:35:02,250 --> 00:35:06,260 V najhoršom prípade, budem mať celá partia náhodných čísel tu. 1008 00:35:06,260 --> 00:35:08,600 A ako sme videli matematicky, keď som chôdzi držať 1009 00:35:08,600 --> 00:35:11,310 v zozname, a to prostredníctvom zoznam, výber budúci najmenší 1010 00:35:11,310 --> 00:35:14,410 znovu a znovu prvok, ak I vlastne zapísať všetky kroky 1011 00:35:14,410 --> 00:35:18,750 Beriem, ako som navrhol formulaically predtým, je to na objednávku n štvorcové 1012 00:35:18,750 --> 00:35:20,370 kroky, ktoré beriem. 1013 00:35:20,370 --> 00:35:24,520 >> A ukázalo sa, že bublina triedenie a insertion sort 1014 00:35:24,520 --> 00:35:27,370 sú rovnako pomaly v najhoršom prípade. 1015 00:35:27,370 --> 00:35:32,040 Zoberme si napríklad, insertion sort, úplne posledný algoritmus sme sa zaoberali, 1016 00:35:32,040 --> 00:35:35,500 ktorý mal s nami pozrieť na prvok, a vložte ju tam, kam patrí. 1017 00:35:35,500 --> 00:35:38,720 A potom sme sa pozreli na ďalší prvok, a vložil ju tam, kam patrí. 1018 00:35:38,720 --> 00:35:40,990 >> Tak zváži najlepší možný scenár. 1019 00:35:40,990 --> 00:35:45,590 Dajme tomu, že som mal môj dobrovoľníci line up doslova ako je tento, jedna až osem, 1020 00:35:45,590 --> 00:35:47,440 už je zoradený. 1021 00:35:47,440 --> 00:35:51,300 Koľko krokov je insertion sort bude trvať triediť osem ľudí, 1022 00:35:51,300 --> 00:35:55,640 keď dorazí na pódiu vyzerajúce takto? 1023 00:35:55,640 --> 00:35:57,410 >> Osem ľudí už je zoradený. 1024 00:35:57,410 --> 00:35:58,760 A ja používam insertion sort. 1025 00:35:58,760 --> 00:36:02,180 Že posledný z algoritmov. 1026 00:36:02,180 --> 00:36:03,640 Dobre, poďme reenact naozaj rýchlo. 1027 00:36:03,640 --> 00:36:05,504 Takže keď začnem tu, vidím jeden. 1028 00:36:05,504 --> 00:36:06,420 Kde vôbec nepatrí? 1029 00:36:06,420 --> 00:36:07,730 Patrí tu. 1030 00:36:07,730 --> 00:36:08,330 Vidím dva. 1031 00:36:08,330 --> 00:36:09,660 Kde dvoch patrí? 1032 00:36:09,660 --> 00:36:10,260 Práve tu. 1033 00:36:10,260 --> 00:36:10,900 Vidím tri. 1034 00:36:10,900 --> 00:36:11,920 Kde Tri patrí? 1035 00:36:11,920 --> 00:36:12,480 Práve tu. 1036 00:36:12,480 --> 00:36:13,100 >> Vidím štyri. 1037 00:36:13,100 --> 00:36:13,600 Práve tu. 1038 00:36:13,600 --> 00:36:15,660 Päť, šesť, sedem, osem. 1039 00:36:15,660 --> 00:36:17,320 Neexistuje žiadny dôvod, aby sa opakujem. 1040 00:36:17,320 --> 00:36:21,260 A tak, ako veľa krokov je to, že, pokiaľ ide o n? 1041 00:36:21,260 --> 00:36:23,870 Je to na objednávku n schodíky, že jo? n mínus 1. 1042 00:36:23,870 --> 00:36:27,567 Ale vzal som lineárny číslo krokov, a teraz som urobil. 1043 00:36:27,567 --> 00:36:28,900 Tak to je najlepšie prípad, hoci. 1044 00:36:28,900 --> 00:36:29,983 Čo najhoršom prípade? 1045 00:36:29,983 --> 00:36:32,730 Aké bolo osem tam, a sedem bolo tam dole, 1046 00:36:32,730 --> 00:36:35,840 a jeden a dvaja boli tu, tak že zoznam bol skutočne zvrátiť? 1047 00:36:35,840 --> 00:36:38,300 >> No, čo sa deje v skutočnosti či je to číslo? 1048 00:36:38,300 --> 00:36:41,300 A urobíme len pár príkladov. 1049 00:36:41,300 --> 00:36:49,300 Čo keď, naozaj, číslo osem je tu, a number-- pokriky. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Takže to, čo v prípade, naozaj, číslo Osem je celú cestu sem, 1052 00:36:56,430 --> 00:36:57,790 a ja som s použitím insertion sort? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Tvrdím, v tejto chvíli je to na mieste. 1055 00:37:00,280 --> 00:37:03,152 Ale teraz, siedmej Odkiaľ siedmich ísť? 1056 00:37:03,152 --> 00:37:04,360 Samozrejme, že ide cez tu. 1057 00:37:04,360 --> 00:37:06,760 Takže som sa pohybovať cez osem jednom mieste. 1058 00:37:06,760 --> 00:37:08,554 A teraz šesť, kde to ide? 1059 00:37:08,554 --> 00:37:09,220 No, v poriadku. 1060 00:37:09,220 --> 00:37:13,150 Teraz musím sa pohybovať cez osem miesto, a sedem viac než na mieste, 1061 00:37:13,150 --> 00:37:14,440 a potom som PLOP nadol šesť. 1062 00:37:14,440 --> 00:37:16,870 >> Takže prvý čas, že náklady mi jeden krok veci do poriadku, 1063 00:37:16,870 --> 00:37:18,570 Potom ma to stálo dva kroky opraviť veci. 1064 00:37:18,570 --> 00:37:20,370 Koľko krokov je to bude trvať na opravu 1065 00:37:20,370 --> 00:37:22,720 Čo dať päť na správnom mieste? 1066 00:37:22,720 --> 00:37:23,340 Tri. 1067 00:37:23,340 --> 00:37:29,520 Pretože teraz musím presunúť jeden, dva, tri. 1068 00:37:29,520 --> 00:37:32,430 Koľko krokov to bude trvať dať štyri na správnom mieste? 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, čo sme popísali pre výber druhu. 1071 00:37:40,260 --> 00:37:42,130 Máme túto sériu to je len rastie. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, alebo naopak, 7 a 6 1073 00:37:45,650 --> 00:37:52,610 a 5 plus 4 spočíta pre dnešné účely tak, aby na poradie n na druhú. 1074 00:37:52,610 --> 00:37:57,640 >> Dovoľte mi tiež, že stanovuje, bublinkové radenie je tiež v n na druhú. 1075 00:37:57,640 --> 00:38:01,340 Vzhľadom k tomu, s perličkovou druhu, každý Tentokrát som prejsť zoznam, 1076 00:38:01,340 --> 00:38:03,100 Beriem zhruba koľko krokov? 1077 00:38:03,100 --> 00:38:06,260 Zakaždým, keď som sa doslova pešo odtiaľ tam? 1078 00:38:06,260 --> 00:38:07,960 Zhruba n krokov. 1079 00:38:07,960 --> 00:38:12,650 Ale koľkokrát by som mohol musieť prejsť zoznamu? 1080 00:38:12,650 --> 00:38:13,920 >> No, hrubo n čas. 1081 00:38:13,920 --> 00:38:15,680 Možno n mínus 1, ale zhruba n časy. 1082 00:38:15,680 --> 00:38:16,430 Tak prečo je to? 1083 00:38:16,430 --> 00:38:19,560 No, s bublinou druhu, pokiaľ začneme s bublinou druhu, 1084 00:38:19,560 --> 00:38:23,570 so zoznamom v ten najhorší možný situácie, čo je opäť úplne 1085 00:38:23,570 --> 00:38:25,550 dozadu, čo sa bude diať? 1086 00:38:25,550 --> 00:38:28,830 Aj prejsť zoznam, a číslo Patríte-celú cestu tam. 1087 00:38:28,830 --> 00:38:33,280 >> Ale s bublinou druhu, ako ďaleko sa môže stať jeden prejsť na svojom prvom prechode zoznamu? 1088 00:38:33,280 --> 00:38:36,620 Koľko miesta sa dostal bližšie na správne miesto? 1089 00:38:36,620 --> 00:38:37,240 Len jeden. 1090 00:38:37,240 --> 00:38:40,281 Takže ak máte trochu dôvod cez to, zakaždým, prostredníctvom tohto algoritmu, 1091 00:38:40,281 --> 00:38:41,880 Dávidovi, ktorí sa zhruba n krokov. 1092 00:38:41,880 --> 00:38:44,940 Ale koľko prechádza v zozname je to 1093 00:38:44,940 --> 00:38:49,060 bude trvať na jeden bublať na ľavej strane, kam patrí? 1094 00:38:49,060 --> 00:38:51,840 >> Má sa pohybovať podobne, n priestory Tadiaľ. 1095 00:38:51,840 --> 00:38:57,960 Takže stačí k tomu triedenie zoznamu, Musím chodiť sem a tam n-krát. 1096 00:38:57,960 --> 00:39:01,540 A zakaždým, ja som pri pohľade na n elementy. 1097 00:39:01,540 --> 00:39:05,410 Takže robiť veci, n n krát na poradie n na druhú. 1098 00:39:05,410 --> 00:39:07,220 >> Teraz uvidíme v niektorých šortiek, ktoré 1099 00:39:07,220 --> 00:39:10,440 sú uložené v CS50 je ďalší problém set, iný prístup na nich, 1100 00:39:10,440 --> 00:39:13,490 ale teraz, nech to jednoducho vziať do úvahy niektoré iné prevádzkové časy, 1101 00:39:13,490 --> 00:39:16,840 zvlášť v prípade, že triedenie tí brať trochu času, aby drez. 1102 00:39:16,840 --> 00:39:21,790 Čo je to algoritmus sme videli už , Ktorý berie na poradí n krokov? 1103 00:39:21,790 --> 00:39:27,560 >> To, čo by mal mať lineárny číslo krokov, ktoré sme doteraz videli? 1104 00:39:27,560 --> 00:39:29,350 Čo je to? 1105 00:39:29,350 --> 00:39:30,480 Vyhľadávanie telefónny zoznam. 1106 00:39:30,480 --> 00:39:31,390 Prvý algoritmus. 1107 00:39:31,390 --> 00:39:31,560 Je to tak? 1108 00:39:31,560 --> 00:39:33,650 Tam, kde sme lineárne hľadanie Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Naozaj. 1110 00:39:34,150 --> 00:39:37,180 Od týždňa nula, keď som začal sústruženie jednu stránku naraz, 1111 00:39:37,180 --> 00:39:40,095 a dokonca povedal som, že to bolo celkom lineárneho pocit algoritmu, 1112 00:39:40,095 --> 00:39:42,720 a mali sme ten obraz na strane doska s rovnou červenou čiarou 1113 00:39:42,720 --> 00:39:44,678 a rovný žltý linka, tie boli skutočne 1114 00:39:44,678 --> 00:39:46,810 algoritmy, ktoré sú vo veľkej O n. 1115 00:39:46,810 --> 00:39:50,680 >> Vzhľadom k tomu, nájsť Mike Smith v telefóne kniha n stránok, v najhoršom prípade, 1116 00:39:50,680 --> 00:39:52,422 mi n krokov môže trvať. 1117 00:39:52,422 --> 00:39:53,630 Čo o tom, dochádzku? 1118 00:39:53,630 --> 00:39:55,790 Jeden dva tri štyri päť šesť. 1119 00:39:55,790 --> 00:39:59,420 Aký je doba chodu tohto algoritmus pre prijatie dochádzku? 1120 00:39:59,420 --> 00:40:03,070 Veľký O n, pretože teoreticky I musieť bod všetci v miestnosti. 1121 00:40:03,070 --> 00:40:05,861 >> Teraz ako stranou, čo o ďalšia optimalizácia z týždňa nula? 1122 00:40:05,861 --> 00:40:08,117 Dve, ​​štyri, šesť, osem, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Počítač by vedec si uvedomiť, počkajte chvíľu, 1124 00:40:10,200 --> 00:40:12,320 to je na poradie n delené dvoch krokoch. 1125 00:40:12,320 --> 00:40:12,820 Je to tak? 1126 00:40:12,820 --> 00:40:14,444 Pretože robím dvoch ľudí naraz. 1127 00:40:14,444 --> 00:40:17,015 Ale budeme ignorovať tieto nižšieho rádu podmienky, 1128 00:40:17,015 --> 00:40:19,140 a my len tak vyhodiť priepasť o 2, 1129 00:40:19,140 --> 00:40:21,830 a len povedať, veľké O n pre tento algoritmus, tak. 1130 00:40:21,830 --> 00:40:22,760 >> A čo toto? 1131 00:40:22,760 --> 00:40:26,170 Budeme preskočiť niektoré z nich, ale to, čo bol algoritmus, ktorý bol 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 Priepasť a panuj. 1134 00:40:30,870 --> 00:40:31,369 Presne tak. 1135 00:40:31,369 --> 00:40:33,900 Rovnako ako telefónneho zoznamu napríklad v týždeň nula a dnes ráno, 1136 00:40:33,900 --> 00:40:36,191 kde sme rozdelili problém znovu a znovu a znovu. 1137 00:40:36,191 --> 00:40:39,070 Čerpal sme to na tabuli v týždni nula ako zakrivený zelená linka, 1138 00:40:39,070 --> 00:40:41,460 a my sme povedali, že je to deň, logaritmickou algoritmus. 1139 00:40:41,460 --> 00:40:44,970 >> A naozaj, počet krokov IT potrebná na vykonanie rozdeľ a panuj, 1140 00:40:44,970 --> 00:40:48,610 alebo binárne vyhľadávanie, ako začneme volať to, rovnako ako v telefónnom zozname, 1141 00:40:48,610 --> 00:40:50,680 je rádovo log a len pár krokov. 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, čo sa jeden krok, alebo presnejšie 1144 00:40:54,910 --> 00:40:56,240 konštantný počet krokov? 1145 00:40:56,240 --> 00:40:58,865 Možno je to dvoch, možno je to tri, ale počítačový vedec len 1146 00:40:58,865 --> 00:41:01,423 zjednodušuje to ako veľký O 1, niektoré konštantný počet krokov. 1147 00:41:01,423 --> 00:41:04,256 Čo je to niečo, čo by ste mohli urobiť, že trvá konštantný počet krokov? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Aký je doba prevádzky tlieskať? 1150 00:41:10,930 --> 00:41:11,920 Konštantný čas. 1151 00:41:11,920 --> 00:41:12,420 Je to tak? 1152 00:41:12,420 --> 00:41:15,490 Rovnako ako to, čo je doba prevádzky robiť niečo, ktorý berie len jeden 1153 00:41:15,490 --> 00:41:18,570 prevádzku, rovnako ako vytlačiť F Hello World. 1154 00:41:18,570 --> 00:41:24,110 To by mohlo byť povedal, aby bol konštantný čas, ibaže menej rohový prípade s tlačovým F, 1155 00:41:24,110 --> 00:41:28,260 Čo by mohlo čas beží tlače F byť v skutočnosti? 1156 00:41:28,260 --> 00:41:28,790 A prečo? 1157 00:41:28,790 --> 00:41:30,550 Čo je n meranie v tomto prípade? 1158 00:41:30,550 --> 00:41:32,251 >> Divákov: [Nepočuteľné]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. Malan: Presne tak. 1160 00:41:33,250 --> 00:41:34,900 Počet znakov chceme vytlačiť. 1161 00:41:34,900 --> 00:41:36,191 Takže je to veľmi kontextová. 1162 00:41:36,191 --> 00:41:39,910 Dnes sme sa zameriava veľa na písmená a číslice tu na palube. 1163 00:41:39,910 --> 00:41:43,540 Ale môže to byť tiež znaky v skutočnom reťazci. 1164 00:41:43,540 --> 00:41:46,420 Tak to dopadá je tu ďalší opatrenie, ktoré začnú starať o, 1165 00:41:46,420 --> 00:41:48,530 a to je opak big O, aby som tak povedal. 1166 00:41:48,530 --> 00:41:50,120 >> To je omega notácie. 1167 00:41:50,120 --> 00:41:53,380 Vzhľadom k tomu, veľký O znamená, že to, čo je so horná viazané na bežiaci čas? 1168 00:41:53,380 --> 00:41:55,580 Maximálne, koľko času Možno niečo vziať? 1169 00:41:55,580 --> 00:41:59,250 Omega-- Ospravedlňujeme sa, tento stále prichádza up-- je opak toho, 1170 00:41:59,250 --> 00:42:02,960 čím je to dolná hranica na Množstvo času, niečo, čo by mohlo trvať. 1171 00:42:02,960 --> 00:42:10,480 >> So. Napríklad, čo je algoritmus ktorý berie vždy n štvorcových kroky? 1172 00:42:10,480 --> 00:42:15,600 No, jeden z algoritmov sme videli dnes, v skutočnosti, že môže byť tiež. 1173 00:42:15,600 --> 00:42:16,720 Selection sort. 1174 00:42:16,720 --> 00:42:18,270 Výberom Triediť to celkom hlúpe. 1175 00:42:18,270 --> 00:42:21,760 Aj keď sa algorithm-- ľúto, a to aj v prípade, že je pole už zoradené, 1176 00:42:21,760 --> 00:42:24,150 Voľba triedenie sa chystá chôdzu držať v zozname 1177 00:42:24,150 --> 00:42:28,907 aby sa uistil, že má najmenší prvok znovu a znovu a znovu. 1178 00:42:28,907 --> 00:42:31,740 A aj keď ľudia v diváci vedia, že, počkajte chvíľu, 1179 00:42:31,740 --> 00:42:33,948 už prešiel najmenší prvok, počítač 1180 00:42:33,948 --> 00:42:37,300 nevie, že až to vyzerá celú cestu v zozname. 1181 00:42:37,300 --> 00:42:40,240 Podobne, dolná hranica, ktorá môžu byť tiež vzaté do úvahy 1182 00:42:40,240 --> 00:42:42,000 by mohol byť lineárny čas. 1183 00:42:42,000 --> 00:42:48,260 >> Koľko času trvá triediť n prvky v najlepšej 1184 00:42:48,260 --> 00:42:52,420 Prípad použitia niečo ako bublina druhu? 1185 00:42:52,420 --> 00:42:54,280 Predpokladajme, že váš zoznam už je zoradený. 1186 00:42:54,280 --> 00:42:56,696 Povedali sme, bublinkové radenie berie na poradie n druhú krokov. 1187 00:42:56,696 --> 00:42:59,640 Ale čo keď je to už je zoradený? 1188 00:42:59,640 --> 00:43:02,310 Čo keď si uvedomíte, po jeden priechod cez pole 1189 00:43:02,310 --> 00:43:03,540 že ste urobili žiadne swapy? 1190 00:43:03,540 --> 00:43:05,970 Potrebujete udržať robiť viac prechádza? 1191 00:43:05,970 --> 00:43:06,470 >> Nie. 1192 00:43:06,470 --> 00:43:10,340 Takže spodnú hranicu bublinkové triedenie by mohlo byť povedal, aby bol lineárny. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 A my si pozrieť ďalšie z nich, ako. 1195 00:43:14,450 --> 00:43:17,990 Takže poďme sa rýchlo pozrieť na iba vizualizáciu tu 1196 00:43:17,990 --> 00:43:20,790 vidieť, ako sa tieto odlíšiť. 1197 00:43:20,790 --> 00:43:24,592 Chystám sa ísť sem dole do toho Stránka, ktorá je k dispozícii na internetových stránkach C50 je, 1198 00:43:24,592 --> 00:43:27,550 ale bude to bolieť, aby si prácu, pretože používa technológiu nazvanú 1199 00:43:27,550 --> 00:43:30,560 Java applety, čo je z veľkej časti podporovaný v týchto dňoch, 1200 00:43:30,560 --> 00:43:32,730 aspoň Chrome a niektoré ďalšie produkty. 1201 00:43:32,730 --> 00:43:37,070 >> A dovoľte mi, aby som do toho pustite a urýchlite up a vysvetliť, čo sa deje. 1202 00:43:37,070 --> 00:43:40,840 To je prejavom bubliny triedenie, prvý algoritmus sme sa na. 1203 00:43:40,840 --> 00:43:43,950 A to je vizualizácia, že každý z týchto tyčí predstavuje číslo. 1204 00:43:43,950 --> 00:43:45,710 Čím väčšia je bar, Čím vyššie je číslo. 1205 00:43:45,710 --> 00:43:47,520 Čím menší je bar, čím menšia je počet. 1206 00:43:47,520 --> 00:43:50,353 A čo môžete vidieť vizuálne, a to aj aj keď to bude super rýchly, 1207 00:43:50,353 --> 00:43:53,699 je to, že červený pruh je ako ja, chôdza sem a tam upevnenie problémy. 1208 00:43:53,699 --> 00:43:56,740 Môžete vidieť, že väčšie prvky skutočne vyviera na pravej strane, 1209 00:43:56,740 --> 00:43:59,650 a na menších elementy vyviera doľava. 1210 00:43:59,650 --> 00:44:01,870 A tu dole, keby sme v skutočnosti vyzerajú lepšie, 1211 00:44:01,870 --> 00:44:04,330 vlastne môžeme počítať počet porovnania a swapov 1212 00:44:04,330 --> 00:44:05,350 ktoré boli vyrobené. 1213 00:44:05,350 --> 00:44:07,360 >> Ale namiesto toho, poďme sa pozrieť na druhom algoritmu 1214 00:44:07,360 --> 00:44:11,240 sme sa pozreli na skôr s našou dobrovoľníci, výber druhu. 1215 00:44:11,240 --> 00:44:13,500 Vizuálne, to má veľmi odlišný efekt. 1216 00:44:13,500 --> 00:44:16,820 Ale je to opäť veľmi intuitívne, v že držíme výber budúci najmenší 1217 00:44:16,820 --> 00:44:18,660 prvok, a dostali sme trochu šťastia. 1218 00:44:18,660 --> 00:44:20,110 To sa cítil zásadne rýchlejšie. 1219 00:44:20,110 --> 00:44:22,840 Ale keď sme bežali to znova a znova a opäť s množstvom vstupov, 1220 00:44:22,840 --> 00:44:26,680 videli by sme, že je to naozaj stále ešte vo veľkej O n na druhú. 1221 00:44:26,680 --> 00:44:29,920 >> Poďme urobiť jednu poslednú tu, insertion sort, 1222 00:44:29,920 --> 00:44:33,180 ktorý bol tretí algoritmus sme sa pozreli na, a odvolanie 1223 00:44:33,180 --> 00:44:36,700 že tento človek sa zaoberá prvky, ako to s nimi stretne, 1224 00:44:36,700 --> 00:44:39,290 ale potom sa to možno posuny veci, nad aby sa uvoľnilo miesto, 1225 00:44:39,290 --> 00:44:41,660 vkladanie prvkov tam, kam patrí. 1226 00:44:41,660 --> 00:44:45,330 >> A to tiež skončí dávať Konečný výsledok. Teraz všetky tri z tých, 1227 00:44:45,330 --> 00:44:46,490 cítil celkom rýchlo. 1228 00:44:46,490 --> 00:44:48,740 A skutočne, bežal som ich v celkom dobrý klip. 1229 00:44:48,740 --> 00:44:52,510 Ale v podstate, oni sú všetci dosť hrozné, aby som bol úprimný. 1230 00:44:52,510 --> 00:44:56,960 Všetky tieto algoritmy doteraz že dráha v veľký O n štvorcový 1231 00:44:56,960 --> 00:44:59,270 trvať docela dost čas pre spustenie v konci. 1232 00:44:59,270 --> 00:45:01,920 >> A skutočne, môžeme vidieť a cítiť sa to konečne 1233 00:45:01,920 --> 00:45:04,090 keď som vytiahnuť tento tretí a posledný demo. 1234 00:45:04,090 --> 00:45:05,840 To je ďalší vizualizácie, čo sa deje 1235 00:45:05,840 --> 00:45:08,500 ukázať bublinkové radenia na ľavej strane, výberom Triediť v stredu, 1236 00:45:08,500 --> 00:45:13,410 a niečo, ako jeden z našich ruka vyvoláva skôr navrhol, 1237 00:45:13,410 --> 00:45:15,020 merge sort na pravej strane. 1238 00:45:15,020 --> 00:45:16,937 Predel a panuj Stratégia na pravej strane. 1239 00:45:16,937 --> 00:45:19,520 A to je v skutočnosti to, čo sme ísť sa pozrieť na stredu. 1240 00:45:19,520 --> 00:45:21,990 Ale poďme čas tieto bežať paralelne. 1241 00:45:21,990 --> 00:45:26,765 To je zhruba rovnaký počet prvky, všetky beží v rovnakom čase. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs výberu triediť vs zlúčenie druhu. 1244 00:45:34,440 --> 00:45:36,760 >> Teraz sa všetci beží teoreticky v rovnakom čase. 1245 00:45:36,760 --> 00:45:39,830 CPU beží na rovnakú rýchlosť, ale 1246 00:45:39,830 --> 00:45:44,014 Môžete cítiť, ako je to nudné veľmi rýchlo stane, 1247 00:45:44,014 --> 00:45:45,930 a ako rýchlo, keď sme sa vniesť trochu týždňa 1248 00:45:45,930 --> 00:45:49,330 algoritmy Zero môže sme sa veci urýchliť. 1249 00:45:49,330 --> 00:45:51,760 >> A teraz poďme porovnať tieto v poslednom forme. 1250 00:45:51,760 --> 00:45:55,710 Chystám sa pokračovať na webové stránky CS50, kde 1251 00:45:55,710 --> 00:45:59,020 máme túto konečnú odkaz pre dnešok, kde niekto na internete 1252 00:45:59,020 --> 00:46:03,960 láskavo dal dohromady video, ktoré zachytáva to, čo iný triedenie 1253 00:46:03,960 --> 00:46:07,510 algoritmy znieť. 1254 00:46:07,510 --> 00:46:09,577 To je insertion sort. 1255 00:46:09,577 --> 00:46:12,072 >> [Pípanie] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Pričom sa uchádzate frekvenciu založené na výške 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ípanie] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Pripravujeme ďalšie je-- prichádza up ďalšie je-- výber triediť, 1262 00:46:45,774 --> 00:46:48,820 kde opäť, my výber budúci najmenší prvok, 1263 00:46:48,820 --> 00:46:51,820 a my môžeme vidieť, že rast zľava doprava. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge sort, náš víťaz tak ďaleko ešte dnes. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Všimnite si, ako je to delenie vecí do [nepočuteľný] polovicu a štvrtiny. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome triedenie, ktoré my nie hovoril o, a vytvára vizuálne 1270 00:47:21,660 --> 00:47:24,450 a audally trochu iný tvar a zvuk. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Tam a späť, čistenie veci. 1273 00:47:30,160 --> 00:47:32,230 Tiež check out Heapsort na webových stránkach tento chlapík. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> A to je všetko. 1276 00:47:36,810 --> 00:47:38,210 Uvidíme sa nabudúce. 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