1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Muziek] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. MALAN: Dit is CS50. 5 00:00:12,550 --> 00:00:14,612 En dit is het begin van week drie. 6 00:00:14,612 --> 00:00:16,820 Dus hebben we een heleboel spannende gekregen dingen te dekken vandaag. 7 00:00:16,820 --> 00:00:20,160 Veel mogelijkheden voor vrijwilligers op het podium. 8 00:00:20,160 --> 00:00:22,780 En uiteindelijk, vandaag de dag is niet om de code op alle. 9 00:00:22,780 --> 00:00:24,820 Maar het gaat over ideeën, en het gaat over algoritmen, 10 00:00:24,820 --> 00:00:28,420 en eigenlijk terugbrengen kennen de lessen van week nul, 11 00:00:28,420 --> 00:00:31,910 waarin recall, we introduceerde dit gedrocht. 12 00:00:31,910 --> 00:00:33,880 En lenen inspiratie van die, te beginnen 13 00:00:33,880 --> 00:00:36,879 oplossen steeds geavanceerdere problemen algoritmisch. 14 00:00:36,879 --> 00:00:38,420 Maar eerst een paar aankondigingen. 15 00:00:38,420 --> 00:00:42,020 Zo een, als je mee wil Personeel en klasgenoten CS50's tijdens de lunch 16 00:00:42,020 --> 00:00:44,670 deze vrijdag, zowel hier als in Cambridge, en in New Haven, 17 00:00:44,670 --> 00:00:48,060 kunt u terecht op de cursus website wanneer een URL te vinden. 18 00:00:48,060 --> 00:00:50,390 Lezing deze woensdag zal hier niet in Sanders. 19 00:00:50,390 --> 00:00:53,610 Het zal alleen online, zodat afstemmen op de website CS50's, 20 00:00:53,610 --> 00:00:55,850 of hier in Cambridge of New Haven ook. 21 00:00:55,850 --> 00:00:58,110 >> En dan probleem set twee is al in uw handen. 22 00:00:58,110 --> 00:01:03,067 Als u nog niet gedoken in nog, laat mij de sterk geformuleerde suggestie bieden 23 00:01:03,067 --> 00:01:05,150 dat, zeker nu, als het probleem stelt voorschot, 24 00:01:05,150 --> 00:01:08,669 je echt wilt nu beginnen, zo niet ploeteren een beetje aan het weekend of voorafgaande 25 00:01:08,669 --> 00:01:10,710 toen ze voor het eerst uit te gaan op Vrijdagen, want je zult 26 00:01:10,710 --> 00:01:14,380 vinden dat ze niet per se steeds langer of meer uitdagende per 27 00:01:14,380 --> 00:01:14,950 se. 28 00:01:14,950 --> 00:01:17,575 Ik denk dat je dat vindt, in algemeen, neigen zij tot ongeveer nemen 29 00:01:17,575 --> 00:01:18,892 rond dezelfde tijd. 30 00:01:18,892 --> 00:01:20,850 Maar het is zeker afhangt de student, en 31 00:01:20,850 --> 00:01:22,880 hangt af van de mentaliteit waarmee je benaderen. 32 00:01:22,880 --> 00:01:24,910 Maar altijd, je gaat te lopen tegen een aantal muur, 33 00:01:24,910 --> 00:01:26,350 en je gaat raken sommige bug, en je bent gewoon 34 00:01:26,350 --> 00:01:27,950 niet van plan om te kunnen krijgen over het op een bepaald punt. 35 00:01:27,950 --> 00:01:31,380 En het is enorm waardevol om te kunnen om weg te stappen, komen de volgende dag terug, 36 00:01:31,380 --> 00:01:35,286 ga naar de kantooruren, post op CS50 Bespreek of iets dergelijks, om daadwerkelijk te krijgen gedeblokkeerd. 37 00:01:35,286 --> 00:01:36,160 Dus hou dat in gedachten. 38 00:01:36,160 --> 00:01:40,830 Beginnend spoedig mogelijk is het beste wat je kunt doen. 39 00:01:40,830 --> 00:01:44,160 Dus hier is waar we begonnen de klasse, meer dan in week nul. 40 00:01:44,160 --> 00:01:47,441 En kunnen we een vrijwilliger hier om me te helpen microfoons vinden? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 Opstaan ​​al. 43 00:01:48,900 --> 00:01:50,080 Kom op maximaal. 44 00:01:50,080 --> 00:01:53,707 Denk dat dat is hoe het gaat werken. 45 00:01:53,707 --> 00:01:54,415 Hoe heet je? 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 Kom op maximaal. 49 00:01:57,910 --> 00:01:58,619 Leuk je te ontmoeten. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Leuk je te ontmoeten. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: En u was hier bij ons in week nul, natuurlijk. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: ik was. 53 00:02:03,028 --> 00:02:03,160 Ik was. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Dus zou je kunnen gaan vooruit en vind voor ons Mike Smith, 55 00:02:05,868 --> 00:02:08,639 zo snel als je kunt? 56 00:02:08,639 --> 00:02:10,639 Zo snel als je kunt. 57 00:02:10,639 --> 00:02:13,756 Letterlijk scheuren van het probleem in de helft als je nodig hebt om. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Letterlijk scheuren van het probleem in de helft. 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 Heel goed. 64 00:02:23,300 --> 00:02:23,700 >> DAVID J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 Goed. 66 00:02:24,200 --> 00:02:24,701 Dankjewel. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Zeer goed. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: En nu, je hebt het teruggebracht 70 00:02:27,610 --> 00:02:29,320 de helft van de omvang van het probleem. 71 00:02:29,320 --> 00:02:31,267 Nu, we zijn tot een kwartaal. 72 00:02:31,267 --> 00:02:33,475 Bent u aandacht te besteden aan welke kant we houden? 73 00:02:33,475 --> 00:02:34,405 >> [Lacht] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Ja, ik think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: Wat sectie zijn we? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: halsdoeken, zo. 77 00:02:39,150 --> 00:02:39,941 >> DAVID J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Maar Mike Smith gaat om na Uitlaten. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Lacht] 81 00:02:48,180 --> 00:02:48,742 >> Prima. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Waar zijn we op zoek? 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: Nu, we zijn in chirurgische. 86 00:02:54,760 --> 00:02:57,840 Nu, artsen. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- laten we gaan met echte. 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 Als u nodig hebt Real. 93 00:03:03,700 --> 00:03:05,250 Nu, welke manier is Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Op deze manier. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: Welke manier? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Wacht. 97 00:03:08,240 --> 00:03:08,790 M is-- toch? 98 00:03:08,790 --> 00:03:09,110 We begonnen met-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Ja. 100 00:03:10,090 --> 00:03:10,650 Ze zijn vertrokken. 101 00:03:10,650 --> 00:03:11,430 Je hebt gelijk. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Ja. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Dus Mike's hier. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Wat? 105 00:03:13,990 --> 00:03:14,665 >> [Lacht] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Slecht voorbeeld, jongens. 108 00:03:18,330 --> 00:03:18,830 Sorry. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: Dit zal je leren je te springen uit je stoel. 110 00:03:21,610 --> 00:03:22,318 >> ALAN ESTRADA: Oh. 111 00:03:22,318 --> 00:03:22,890 Oh. 112 00:03:22,890 --> 00:03:23,390 Ik heb je. 113 00:03:23,390 --> 00:03:24,670 Ik heb je. 114 00:03:24,670 --> 00:03:25,170 Oh. 115 00:03:25,170 --> 00:03:25,669 Oh. 116 00:03:25,669 --> 00:03:26,812 Dit is-- OK, ik heb je. 117 00:03:26,812 --> 00:03:27,520 Smith hier? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, dank je. 119 00:03:28,894 --> 00:03:30,535 Dus ik zal blijven opzoeken Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, ja. 121 00:03:30,790 --> 00:03:31,340 Nee nee nee. 122 00:03:31,340 --> 00:03:31,600 O nee. 123 00:03:31,600 --> 00:03:31,940 Dit is van mij. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Oh, heb je Smith. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Ja, ik Smith kreeg hier. 127 00:03:34,040 --> 00:03:34,700 Sorry, jongens. 128 00:03:34,700 --> 00:03:35,860 Ik dacht dat we Michael-- waren op zoek naar Michael. 129 00:03:35,860 --> 00:03:36,550 Sorry. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: Het is OK. 131 00:03:37,550 --> 00:03:39,950 Oké, nu zijn we in Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini en zonen. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Alleen jij en ik zijn in deze. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Vind ons 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 We zijn in R voor onzin. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Onzin. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Dit gaat een tijdje duren. 143 00:03:52,480 --> 00:03:54,340 >> [Lacht] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. MALAN: Schoenen. 146 00:03:56,720 --> 00:03:58,080 We zitten in de schoenen. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Nu zijn we 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 [Lacht] 151 00:04:03,620 --> 00:04:05,440 Oh, dit is geweldig. 152 00:04:05,440 --> 00:04:06,910 [Lacht] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. MALAN: Het is OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Oh, dit is goed. 156 00:04:11,365 --> 00:04:14,425 Ik denk niet dat ik ga hebben PSAT vrienden na dit. 157 00:04:14,425 --> 00:04:15,300 DAVID J. MALAN: Goed. 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 Dus laten we scheuren dit in de helft. 163 00:04:21,600 --> 00:04:22,270 Het is ok. 164 00:04:22,270 --> 00:04:25,606 Deze eindigt slecht toch, omdat Mike Smith zal niet in de gele pagina's. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: Nee, het is OK. 167 00:04:27,140 --> 00:04:28,930 Maar laten we doen alsof Hij is op deze pagina. 168 00:04:28,930 --> 00:04:33,260 Dus nu, je hebt het probleem teruggebracht op één pagina, en we vonden Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [TOEJUICHENDE] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 OK, dank je. 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 Dat was buitengewoon. 175 00:04:43,646 --> 00:04:45,954 Maar het was nog sneller dan lineair zoeken, 176 00:04:45,954 --> 00:04:47,870 waarin beginnen we bij de begin van het boek, 177 00:04:47,870 --> 00:04:51,210 en we bewegen weg van links naar rechts, uiteindelijk naar Mike Smith. 178 00:04:51,210 --> 00:04:53,540 En dus, als het telefoonboek hadden misschien 1.000 pagina's, 179 00:04:53,540 --> 00:04:56,300 misschien zou hebben genomen ons 10 of zo pagina tranen. 180 00:04:56,300 --> 00:04:59,380 >> Maar je kan hebben leveraged raakte een veronderstelling 181 00:04:59,380 --> 00:05:03,602 Tijdens dat alles, dat wil zeggen dat het telefoonboek van tevoren was wat? 182 00:05:03,602 --> 00:05:04,310 Publiek: Gesorteerd. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: Het is opgelost. 184 00:05:05,000 --> 00:05:05,160 Rechts? 185 00:05:05,160 --> 00:05:07,909 Het is alfabetisch gesorteerd, zodat dat al die namen en nummers 186 00:05:07,909 --> 00:05:11,230 worden gesorteerd van A tot de Z en alfabetische daartussen. 187 00:05:11,230 --> 00:05:13,100 Maar vandaag, nu vragen we de vraag, goed, 188 00:05:13,100 --> 00:05:16,170 hoe heeft Verizon of de telefoon bedrijf te krijgen in die staat? 189 00:05:16,170 --> 00:05:19,560 >> Want het is één ding om gebruik te maken die veronderstelling, en dus 190 00:05:19,560 --> 00:05:22,570 een probleem met een op te lossen algoritme efficiënter. 191 00:05:22,570 --> 00:05:24,900 Maar we nooit echt vroeg in week nul, goed, 192 00:05:24,900 --> 00:05:27,790 hoeveel heeft het gekost Verizon of iemand anders 193 00:05:27,790 --> 00:05:29,620 dat telefoonboek in gesorteerde volgorde te krijgen? 194 00:05:29,620 --> 00:05:29,780 >> Rechts? 195 00:05:29,780 --> 00:05:31,529 Het maakt niet uit of opzoeken Mike Smith 196 00:05:31,529 --> 00:05:35,190 is super snel, als het neemt je een jaar om de pagina's in eerste instantie afstand. 197 00:05:35,190 --> 00:05:35,690 Rechts? 198 00:05:35,690 --> 00:05:38,620 Je kan net zo goed te ziften door middel van een gerandomiseerde telefoonboek, 199 00:05:38,620 --> 00:05:40,690 Als het gaat super te zijn duur te sorteren. 200 00:05:40,690 --> 00:05:42,350 Dus als we een andere vrijwilliger kan hebben. 201 00:05:42,350 --> 00:05:46,350 Laten we eens een kijk omhoog hier bij hoe we might-- kom op up-- hoe 202 00:05:46,350 --> 00:05:48,100 we kunnen gaan over het sorteren van deze. 203 00:05:48,100 --> 00:05:51,990 >> En als Jordan kon eigenlijk bij ons hier op het podium. 204 00:05:51,990 --> 00:05:55,100 Kom op voor slechts een moment. 205 00:05:55,100 --> 00:05:56,359 Hoe heet je? 206 00:05:56,359 --> 00:05:57,150 CAROLINE: Caroline. 207 00:05:57,150 --> 00:05:58,691 DAVID J. MALAN: Caroline, kom op up. 208 00:05:58,691 --> 00:06:02,070 En je zult worden samengevoegd door mij en Jordanië hier. 209 00:06:02,070 --> 00:06:03,800 Caroline, dank je. 210 00:06:03,800 --> 00:06:04,300 Prima. 211 00:06:04,300 --> 00:06:08,330 Dus wat we hier hebben voor Caroline is 26 blauwe boeken 212 00:06:08,330 --> 00:06:10,747 dat FAS gebruikt te beheren bepaalde eindexamen. 213 00:06:10,747 --> 00:06:13,330 Deze worden steeds moeilijk te vinden, maar wat we hebben gedaan op voorhand 214 00:06:13,330 --> 00:06:15,800 is dat we iemands naam hebt gezet aan de voorzijde van elk van deze, 215 00:06:15,800 --> 00:06:18,133 maar we hebben het simpel gehouden door Vervolgens blussen volledige namen. 216 00:06:18,133 --> 00:06:22,720 Dus zouden we de persoon te zetten met de naam L, D, J, B, helemaal A tot Z, 217 00:06:22,720 --> 00:06:24,090 maar ze zijn in willekeurige volgorde. 218 00:06:24,090 --> 00:06:26,890 En dus als je zou doen, praat je weg door het probleem als je 219 00:06:26,890 --> 00:06:31,620 doe het, kunt u doorgaan en sorteren van deze voor ons, van A tot Z. 220 00:06:31,620 --> 00:06:34,070 >> Publiek: OK, dus L is als het midden. 221 00:06:34,070 --> 00:06:35,050 C begint. 222 00:06:35,050 --> 00:06:42,410 B. J voordat L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Houd die dacht een seconde. 224 00:06:45,140 --> 00:06:48,910 Want anders is dit slechts interessant voor jou, mij, en Jordanië. 225 00:06:48,910 --> 00:06:49,724 Daar gaan we. 226 00:06:49,724 --> 00:06:50,640 PUBLIEK: [onverstaanbaar]. 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 Wat ben je aan het doen? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M komt na 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: O, goed. 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. Yeah. 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. Zo ziet eruit alsof je making-- blijven gaan. 238 00:07:10,689 --> 00:07:12,730 Het lijkt erop dat je het maken van een grote stapel hier, 239 00:07:12,730 --> 00:07:13,910 en een soort van een grote stapel daar. 240 00:07:13,910 --> 00:07:16,230 Dus de eerste helft van het alfabet, tweede helft van het alfabet. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 Goed. 243 00:07:16,960 --> 00:07:19,680 Soort van het splitsen van het probleem in twee. 244 00:07:19,680 --> 00:07:21,771 M, N, X. Yeah. 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. Dus je soort selecteren ze een na de ander, 248 00:07:25,070 --> 00:07:27,620 zetten het links of rechts, of Z's gaan op de vloer. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z gaat op de vloer. 251 00:07:29,190 --> 00:07:29,360 >> DAVID J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y gaat op de vloer. 253 00:07:30,920 --> 00:07:31,735 Nu kunnen we X. zetten 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. MALAN: G's naar links. 256 00:07:33,700 --> 00:07:36,017 S gaat rechts. 257 00:07:36,017 --> 00:07:37,642 Oké, A gaat helemaal naar links. 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: Nu, goed. 260 00:07:39,873 --> 00:07:43,260 We hebben gekregen, B, C W's gaan daar beneden. 261 00:07:43,260 --> 00:07:45,566 Oké, 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: In het centrum, ik gonna-- 265 00:07:49,160 --> 00:07:50,000 DAVID J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Dus nu gaan we soort samenvoegen van deze verschillende palen. 267 00:07:52,375 --> 00:08:00,730 Dus A tot en met C, dan zie ik D en E en F, en G en H en I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. En dan, deze stapel is ondersteboven, maar dat is OK. 269 00:08:05,540 --> 00:08:06,040 Tuurlijk. 270 00:08:06,040 --> 00:08:07,240 We kunnen snijden sommige bochten. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 En dan moeten we W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> CAROLINE: Ja. 274 00:08:11,250 --> 00:08:11,880 >> DAVID J. MALAN: Excellent. 275 00:08:11,880 --> 00:08:14,122 Dus een grote dank aan Caroline voor het sorteren daarvan. 276 00:08:14,122 --> 00:08:15,030 >> [TOEJUICHENDE] 277 00:08:15,030 --> 00:08:17,287 >> Dankjewel. 278 00:08:17,287 --> 00:08:18,120 Hartelijk bedankt. 279 00:08:18,120 --> 00:08:22,910 Dus nu laten we eens kijken voor een moment hoe Caroline ging over dat te doen, 280 00:08:22,910 --> 00:08:26,040 en wat precies wij konden to-- hoe we 281 00:08:26,040 --> 00:08:28,409 waren in staat om op te lossen dat probleem toen we waren gewoon 282 00:08:28,409 --> 00:08:29,950 krijgt een hele hoop willekeurige ingangen. 283 00:08:29,950 --> 00:08:31,610 >> Nou, het lijkt erop dat er was een beetje een systeem is er? 284 00:08:31,610 --> 00:08:32,110 Rechts. 285 00:08:32,110 --> 00:08:34,495 Zodat de eerdere brieven in het alfabet, zij 286 00:08:34,495 --> 00:08:37,120 was zetten naar links, en de later letters in het alfabet, 287 00:08:37,120 --> 00:08:38,270 ze was het in de juiste. 288 00:08:38,270 --> 00:08:40,500 En zodra ze gevonden sommige proximale brieven, degenen 289 00:08:40,500 --> 00:08:43,124 die naar naast elkaar Ze zouden die op orde te brengen. 290 00:08:43,124 --> 00:08:46,750 En dus we soort had deze kleine stapels gesorteerde inputs optreedt. 291 00:08:46,750 --> 00:08:50,540 >> En dat is dus heel graag wat de meesten van ons mensen zou doen. 292 00:08:50,540 --> 00:08:53,530 We zouden een soort van ziften doorheen, en we zouden soort hebben een mechanisme. 293 00:08:53,530 --> 00:08:56,930 Maar het zou moeilijk zijn om te schrijven het beneden in een formule per se. 294 00:08:56,930 --> 00:08:59,010 Het voelde een beetje meer organische dan dat. 295 00:08:59,010 --> 00:09:02,560 Dus laten we kijken of we kunnen nu gebonden het probleem met minder inputs. 296 00:09:02,560 --> 00:09:05,170 >> In plaats van 26, laten we iets wat veel minder doen 297 00:09:05,170 --> 00:09:09,890 met alleen maar zeggen, zeven, achter deze deuren, om zo te zeggen. 298 00:09:09,890 --> 00:09:11,300 Zijn er slechts zeven nummers? 299 00:09:11,300 --> 00:09:15,240 En als het doel nu hand om een ​​waarde te vinden, 300 00:09:15,240 --> 00:09:17,850 laten we eens kijken hoe efficiënt we kunnen gaan doen. 301 00:09:17,850 --> 00:09:22,460 En laten we kijken of we kunnen nu beginnen met een aantal nummers passen, 302 00:09:22,460 --> 00:09:26,310 of een formules waarmee beschrijven de efficiëntie van onze telefoonboek 303 00:09:26,310 --> 00:09:31,060 algoritme, onze examen boek algoritme, en meer in het algemeen, het vinden van informatie. 304 00:09:31,060 --> 00:09:34,770 >> Dus voor deze, laat me doorgaan, en op het aanraakscherm hier, 305 00:09:34,770 --> 00:09:41,100 zetten een webbrowser die heeft juist deze zeven deuren. 306 00:09:41,100 --> 00:09:46,670 En als we konden een ander krijgen vrijwilliger te komen op hier, 307 00:09:46,670 --> 00:09:48,480 Ik heb deze zelfde deuren zetten hier. 308 00:09:48,480 --> 00:09:49,170 Quick vrijwilliger. 309 00:09:49,170 --> 00:09:51,130 >> Dit een-- demo gaan een sneller en sneller nu. 310 00:09:51,130 --> 00:09:51,600 Kom maar naar beneden. 311 00:09:51,600 --> 00:09:52,308 Hoe heet je? 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 Oké, Trevor, kom naar beneden. 315 00:09:55,770 --> 00:09:59,212 Dus Trevor heeft hier vrijwillig aan doe een soortgelijk probleem, maar een die 316 00:09:59,212 --> 00:10:02,170 beperkter in omvang, en dat gaat om ons in staat om te proberen om nu te formaliseren 317 00:10:02,170 --> 00:10:03,970 de werkwijze voor het sorteren van deze nummers. 318 00:10:03,970 --> 00:10:05,500 >> Dus Trevor, leuk je te ontmoeten. 319 00:10:05,500 --> 00:10:08,720 Dus hier is een array, om zo te spreken, een lijst van zeven deuren. 320 00:10:08,720 --> 00:10:10,327 Ga je gang en vinden ons de nummer 50. 321 00:10:10,327 --> 00:10:12,410 En dan na het feit, vertel ons hoe je het gevonden. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Moet be-- goed. 324 00:10:20,040 --> 00:10:21,945 Ja, dit is het hier? 325 00:10:21,945 --> 00:10:24,680 Oh Oh. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 U hebt geklikt die ene. 328 00:10:26,680 --> 00:10:28,690 Goed. 329 00:10:28,690 --> 00:10:29,780 >> En goed. 330 00:10:29,780 --> 00:10:30,970 Nu u hebt geklikt die ene. 331 00:10:30,970 --> 00:10:34,060 En laat me je de microfoon, zodat je het in slechts een moment. 332 00:10:34,060 --> 00:10:37,000 Ga je gang en klik op de naast de deur die u van plan bent. 333 00:10:37,000 --> 00:10:39,812 Ja goed. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Kan ik unclick een deur? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: Nee, je kan niet unclick. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Deze. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: Waar wil je heen? 339 00:10:45,640 --> 00:10:46,410 Welke? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Dat één. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: No. 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Deze. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Ja. 345 00:10:49,020 --> 00:10:49,700 Dat was goed. 346 00:10:49,700 --> 00:10:50,380 Prima. 347 00:10:50,380 --> 00:10:53,900 Dus wat was uw algoritme of procedure om dit te doen, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Ik ging gewoon door middel van deuren totdat ik vond een 50. 349 00:10:56,149 --> 00:10:56,940 DAVID J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Excellent algoritme. 351 00:10:58,150 --> 00:10:59,540 Dus dat is prima. 352 00:10:59,540 --> 00:11:03,120 Want in feite, als ik onthullen wat is Achter deze twee deuren, wat 353 00:11:03,120 --> 00:11:06,954 we zullen hier is dat we hebben alleen willekeurige ingang. 354 00:11:06,954 --> 00:11:08,870 Dus dat was eigenlijk als goed als je kon krijgen. 355 00:11:08,870 --> 00:11:12,509 En in feite, kun je beter dan kreeg uitputtend zoeken de hele reeks, 356 00:11:12,509 --> 00:11:15,300 omdat het echt zou zijn geweest pech als je het nummer had geraakt 357 00:11:15,300 --> 00:11:16,604 50 op het laatst de deur. 358 00:11:16,604 --> 00:11:18,520 Maar wat als we in plaats daarvan gaf je een veronderstelling. 359 00:11:18,520 --> 00:11:20,630 Stel dat ik een soort van alle deze deuren rond, 360 00:11:20,630 --> 00:11:23,500 zodat u de aantallen naargelang deze tijd, 361 00:11:23,500 --> 00:11:29,730 maar deze keer is het eigenlijk een different-- dit keer, 362 00:11:29,730 --> 00:11:32,640 het is eigenlijk gesorteerd voor u. 363 00:11:32,640 --> 00:11:35,380 En nu het doel bij de hand wordt het nummer 50 geraakt. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: Wat is algoritme gaat worden? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Nou, als het naargelang, het is ofwel gaan 367 00:11:39,628 --> 00:11:42,710 om be-- als grootste tot de grootste, afdalen, zal het de eerste te zijn, 368 00:11:42,710 --> 00:11:44,751 of als het is het tegenovergestelde, het zal de laatste zijn. 369 00:11:44,751 --> 00:11:48,897 Dus ik zal gewoon raak deze deur, en dan gewoon tik op de laatste deur. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Excellent. 371 00:11:49,980 --> 00:11:50,270 Prima. 372 00:11:50,270 --> 00:11:51,150 Dus vonden we het nummer 50. 373 00:11:51,150 --> 00:11:52,970 Dus zodra je wist zij waren gesorteerd, we 374 00:11:52,970 --> 00:11:55,040 konden deze veronderstelling hefboomwerking. 375 00:11:55,040 --> 00:11:57,040 Zodat ze te veel op het telefoonboek voorbeeld. 376 00:11:57,040 --> 00:11:59,540 Zodra je hebt, zelfs met een klein probleem als dit, 377 00:11:59,540 --> 00:12:02,380 Uw input voorgesorteerd, kunnen we de waarde eigenlijk vinden aantoonbaar 378 00:12:02,380 --> 00:12:03,130 efficiënter. 379 00:12:03,130 --> 00:12:05,800 >> En ik heb je als het niet vertellen naargelang klein tot groot, of groot naar klein, 380 00:12:05,800 --> 00:12:08,080 en dus het was zeer redelijk te beginnen aan één uiteinde of het andere 381 00:12:08,080 --> 00:12:09,750 om daadwerkelijk vinden dat streefwaarde. 382 00:12:09,750 --> 00:12:11,400 Dus dank aan Trevor ook. 383 00:12:11,400 --> 00:12:13,260 En ik zal propose-- mooi gedaan. 384 00:12:13,260 --> 00:12:16,960 We hebben een kleine clip, eigenlijk, dat is een van onze favoriete momenten in CS50, 385 00:12:16,960 --> 00:12:19,700 waarbij soms zijn deze demo's niet helemaal volgens plan. 386 00:12:19,700 --> 00:12:22,050 En inderdaad op dit moment, ik trok de verkeerde-interface 387 00:12:22,050 --> 00:12:23,508 waarmee het aanraakscherm te gebruiken. 388 00:12:23,508 --> 00:12:24,660 Dus dat was mijn schuld daar. 389 00:12:24,660 --> 00:12:26,600 >> Dus zal dit voor volgend jaar de clip als 390 00:12:26,600 --> 00:12:28,570 waarom ik klikken op mijn eigen scherm. 391 00:12:28,570 --> 00:12:31,390 Maar laten we eens een snelle blik wat vorig jaar gebeurde 392 00:12:31,390 --> 00:12:34,770 met Jay, die kwam, veel zoals Trevor hier vrijwillig, 393 00:12:34,770 --> 00:12:39,380 en in deze korte clip, zie je hoe deze zelfde demo niet helemaal 394 00:12:39,380 --> 00:12:41,074 onthullen dezelfde lessen. 395 00:12:41,074 --> 00:12:41,740 [VIDEO AFSPELEN] 396 00:12:41,740 --> 00:12:45,360 -Alle Ik wil dat je nu doen is te vinden voor mij, en voor ons, 397 00:12:45,360 --> 00:12:51,674 echt, het nummer 50 één stap tegelijk. 398 00:12:51,674 --> 00:12:52,450 >> -Het Nummer 50? 399 00:12:52,450 --> 00:12:53,190 >> -Het Nummer 50. 400 00:12:53,190 --> 00:12:55,356 En je kunt laten zien wat er achter elk van deze deuren 401 00:12:55,356 --> 00:12:58,540 simpelweg door aan te raken met een vinger. 402 00:12:58,540 --> 00:13:00,910 Verdomme. 403 00:13:00,910 --> 00:13:02,870 >> [Lacht] 404 00:13:02,870 --> 00:13:03,806 >> [END AFSPELEN] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Dus dat heel goed ging. 406 00:13:05,430 --> 00:13:06,796 Dat waren de ongesorteerde deuren. 407 00:13:06,796 --> 00:13:08,670 En Jay, natuurlijk vond het allemaal te snel. 408 00:13:08,670 --> 00:13:12,910 Trevor heeft een veel betere baan in termen van een leermoment, 409 00:13:12,910 --> 00:13:15,850 zo te zeggen, dit jaar duurt langer om het te vinden. 410 00:13:15,850 --> 00:13:17,950 Natuurlijk, dan gaven we Jay een tweede kans, 411 00:13:17,950 --> 00:13:20,320 waarbij wij naargelang de deuren, net zoals we deden voor Trevor, 412 00:13:20,320 --> 00:13:22,300 en Trevor deed super goed deze tijd. 413 00:13:22,300 --> 00:13:26,124 Maar Jay deed het half zo snel. 414 00:13:26,124 --> 00:13:26,790 [VIDEO AFSPELEN] 415 00:13:26,790 --> 00:13:29,650 -het Doel is nu om ook vinden wij het getal 50, 416 00:13:29,650 --> 00:13:33,030 maar doe het algoritmisch, en vertellen ons hoe je gaat over. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -En Als je het te vinden, houdt u de film. 419 00:13:35,604 --> 00:13:37,228 Als u niet vinden, geef je terug. 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 >> - [Onverstaanbaar] OK. 423 00:13:40,800 --> 00:13:46,236 Dus ik ga naar de uiteinden controleren eerst of there's-- te bepalen Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Applaus] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END AFSPELEN] 427 00:13:55,729 --> 00:13:56,520 DAVID J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Dus sorteren deuren duidelijk leidt tot meer efficiëntie. 429 00:13:59,760 --> 00:14:01,680 En ja, twee keer zo snel is wat ik daar bedoelde. 430 00:14:01,680 --> 00:14:03,270 En zo Jay geluk kregen beide keren. 431 00:14:03,270 --> 00:14:06,685 En hij kreeg ook geluk dat de laatste jaar, bestelde ik een aantal Blu-ray-schijven 432 00:14:06,685 --> 00:14:07,560 om daadwerkelijk te geven. 433 00:14:07,560 --> 00:14:09,768 Het spijt me dit jaar, we niet dezelfde zijn, Trevor. 434 00:14:09,768 --> 00:14:11,540 Maar beter nog was een paar jaar terug. 435 00:14:11,540 --> 00:14:14,820 En sommigen van jullie misschien weten collega, Sean, die toen hij in CS50 was, 436 00:14:14,820 --> 00:14:17,780 werd uitgedaagd met de exacte hetzelfde probleem, zij het in SD, 437 00:14:17,780 --> 00:14:19,360 als je snel zult zien, terug in de dag. 438 00:14:19,360 --> 00:14:22,622 En je zult zien dat niet alleen hij iets langer duren dan Jay, 439 00:14:22,622 --> 00:14:25,580 iets langer dan Trevor, was eigenlijk dit prachtige kans 440 00:14:25,580 --> 00:14:29,820 bijna iedereen in het betrekken menigte a la Price is Right, het stimuleren 441 00:14:29,820 --> 00:14:31,889 hem naar het nummer dat we op zoek waren te vinden. 442 00:14:31,889 --> 00:14:32,930 Laten we. neem snel een kijkje. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEO AFSPELEN] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Dus je taak hier Sean, is het volgende. 446 00:14:36,680 --> 00:14:40,860 Ik heb achter deze verborgen deuren van de nummer zeven. 447 00:14:40,860 --> 00:14:45,120 Maar weggestopt in een aantal van deze deuren evenals zijn andere negatieve getallen. 448 00:14:45,120 --> 00:14:47,500 En je doel is om na te denken van de bovenste rij getallen 449 00:14:47,500 --> 00:14:50,390 als onder array of gewoon opeenvolging van stukjes papier 450 00:14:50,390 --> 00:14:51,510 met cijfers achter hen. 451 00:14:51,510 --> 00:14:55,540 En je doel is, alleen met behulp van de top matrix hier, vind ik het getal zeven. 452 00:14:55,540 --> 00:14:58,570 En we vervolgens naar kritiek hoe je het gaan doen. 453 00:14:58,570 --> 00:14:59,070 -Prima. 454 00:14:59,070 --> 00:15:00,850 -Zoek Ons de nummer zeven, alsjeblieft. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nee. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Vijf, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Lacht] 461 00:15:24,770 --> 00:15:25,910 >> Het is geen strikvraag. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Een. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Lacht] 466 00:15:34,695 --> 00:15:37,861 Op dit punt, je score is niet erg goed, dus je kan net zo goed blijven gaan. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Drie. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Lacht] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Ga door. 473 00:15:47,774 --> 00:15:50,690 Eerlijk gezegd, ik kan het niet helpen, maar vraag me af wat je ook denkt over, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Lacht] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Alleen de bovenste rij, dus je hebt drie links. 477 00:15:55,020 --> 00:15:56,200 Dus vind ik zeven. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Lacht] 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 Zeven. 484 00:16:26,946 --> 00:16:28,780 >> [Applaus] 485 00:16:28,780 --> 00:16:29,426 >> Prima. 486 00:16:29,426 --> 00:16:30,360 >> [END AFSPELEN] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: Dus we konden bekijk deze hele dag lang. 488 00:16:31,840 --> 00:16:34,090 En natuurlijk, sommige demo's van dit jaar misschien 489 00:16:34,090 --> 00:16:36,330 Nu zal eindigen in next video jaar ook. 490 00:16:36,330 --> 00:16:39,040 Dus laten we nu eigenlijk focus op de algoritmen 491 00:16:39,040 --> 00:16:42,140 hier, en kijken of we kunnen niet nu beginnen te formaliseren 492 00:16:42,140 --> 00:16:46,650 hoe we kunnen gaan over het krijgen van onze data in deze staat dat het sorteren, 493 00:16:46,650 --> 00:16:50,054 zodat uiteindelijk, kunnen we eigenlijk doorzoeken efficiënter. 494 00:16:50,054 --> 00:16:52,470 En hoewel we gaan tamelijk kleine datasets gebruiken, 495 00:16:52,470 --> 00:16:54,511 net als de acht nummers die we hier hebben op het bord, 496 00:16:54,511 --> 00:16:58,230 uiteindelijk dezelfde ideeën zou kunnen gelden tot 1000 ingangen miljoen ingangen, 497 00:16:58,230 --> 00:17:02,100 4000000000 inputs, omdat de algoritmen zullen in wezen hetzelfde zijn. 498 00:17:02,100 --> 00:17:05,359 >> En dus dit is onze laatste kans voor de vrijwilligers van vandaag, 499 00:17:05,359 --> 00:17:09,790 maar misschien wel het meest betrokken is, waarvoor we nodig acht vrijwilligers 500 00:17:09,790 --> 00:17:12,960 om te komen en lopen ons door de proces van het sorteren van wat zal binnenkort 501 00:17:12,960 --> 00:17:15,212 op deze muziek staat hier. 502 00:17:15,212 --> 00:17:16,170 Laat me hier start. 503 00:17:16,170 --> 00:17:19,692 >> Zodat men in de turquoise-- groen is het? 504 00:17:19,692 --> 00:17:21,130 Bent u begaan? 505 00:17:21,130 --> 00:17:21,630 Twee. 506 00:17:21,630 --> 00:17:23,069 Kom maar naar beneden. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Drie. 509 00:17:24,420 --> 00:17:25,400 Four. 510 00:17:25,400 --> 00:17:27,247 Laat mij-- OK, vijf. 511 00:17:27,247 --> 00:17:28,830 Je bent door je vriend genomineerd. 512 00:17:28,830 --> 00:17:31,340 Zes, zeven en acht. 513 00:17:31,340 --> 00:17:32,130 Kom op maximaal. 514 00:17:32,130 --> 00:17:32,630 Prima. 515 00:17:32,630 --> 00:17:33,190 Heel erg bedankt. 516 00:17:33,190 --> 00:17:33,689 Kom op maximaal. 517 00:17:33,689 --> 00:17:34,790 Kom op maximaal. 518 00:17:34,790 --> 00:17:35,330 >> Prima. 519 00:17:35,330 --> 00:17:38,890 Dus wat we hebben hier-- en dit is een van de lastiger degenen, 520 00:17:38,890 --> 00:17:42,390 aangezien dit humor vereisen dat u me voor slechts een beetje tijd. 521 00:17:42,390 --> 00:17:43,442 Je moet nummer één. 522 00:17:43,442 --> 00:17:44,150 Hoe heet je? 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 Hoe heet je? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: Joseph, je bent nummer twee. 529 00:17:49,190 --> 00:17:52,260 >> SERENA: Serena, nummer drie. 530 00:17:52,260 --> 00:17:53,722 Stefan, nummer vier. 531 00:17:53,722 --> 00:17:54,430 CYNTHIA: Cynthia. 532 00:17:54,430 --> 00:17:57,548 DAVID J. MALAN: Cynthia, nummer vijf. 533 00:17:57,548 --> 00:17:58,452 [Onverstaanbaar] 534 00:17:58,452 --> 00:17:59,618 DAVID J. MALAN: [onverstaanbaar]. 535 00:17:59,618 --> 00:18:00,391 David, nummer zes. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. MALAN: Matt's nummer zeven. 538 00:18:02,160 --> 00:18:02,850 En? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Waverly. 540 00:18:03,210 --> 00:18:04,470 >> DAVID J. MALAN: Waverly, nummer acht. 541 00:18:04,470 --> 00:18:04,970 Prima. 542 00:18:04,970 --> 00:18:06,510 Als u could-- whoops. 543 00:18:06,510 --> 00:18:08,820 Als je al, als je eerste uitdaging, er 544 00:18:08,820 --> 00:18:10,820 zijn acht lessenaars Hier tegenover het publiek. 545 00:18:10,820 --> 00:18:14,200 Als je je nummers op kon zetten Deze lessenaars zodanig 546 00:18:14,200 --> 00:18:16,560 dat zij onmiddellijk boven het dezelfde nummers op het bord. 547 00:18:16,560 --> 00:18:19,560 Dus maak jezelf eruit dat door het zetten van uw nummers op deze muziek 548 00:18:19,560 --> 00:18:21,960 hier staat. 549 00:18:21,960 --> 00:18:25,980 Uitstekende dusver. 550 00:18:25,980 --> 00:18:26,600 >> Excellent. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Dus nu gaan we naar de vragen vraag in een paar verschillende manieren. 553 00:18:29,556 --> 00:18:31,610 Hoe kunnen we gaan over het sorteren deze mensen hier? 554 00:18:31,610 --> 00:18:34,500 Want we hadden een paar benaderingen eerder, waarbij wij waren 555 00:18:34,500 --> 00:18:36,360 soort die twee emmers. 556 00:18:36,360 --> 00:18:38,842 En dan over het algemeen waren we patchwork dingen samen. 557 00:18:38,842 --> 00:18:41,050 Zodra we zagen twee nummers dat behoorde samen, 558 00:18:41,050 --> 00:18:41,975 We zetten ze samen. 559 00:18:41,975 --> 00:18:43,350 Twee brieven die bij elkaar horen. 560 00:18:43,350 --> 00:18:45,058 >> Maar laten we eens kijken of we kan dit niet formaliseren, 561 00:18:45,058 --> 00:18:48,044 zodat we uiteindelijk sommige pseudo-code die u wilt, 562 00:18:48,044 --> 00:18:49,710 waarmee u deze problemen op te lossen. 563 00:18:49,710 --> 00:18:51,870 Dus nu ben ik op zoek op deze nummers in. 564 00:18:51,870 --> 00:18:55,030 En ik zie een hele hoop fouten. 565 00:18:55,030 --> 00:18:57,750 Uiteindelijk wil ik een op de acht links en rechts. 566 00:18:57,750 --> 00:19:00,650 >> En dus ik ben op zoek naar deze twee, vier en twee. 567 00:19:00,650 --> 00:19:02,930 En wat is het probleem, natuurlijk? 568 00:19:02,930 --> 00:19:04,261 Ja. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Twee natuurlijk komt voor vier, dus weet je wat? 571 00:19:07,160 --> 00:19:10,210 Laat me eerst een hebzuchtige aanpak, als je wil, net als probleem 572 00:19:10,210 --> 00:19:13,790 set een-- als u zich herinneren van de Standard Edition van Probleem Set One, 573 00:19:13,790 --> 00:19:16,820 waar ik alleen lokaal het probleem op te lossen dat is hier voor mij 574 00:19:16,820 --> 00:19:17,690 en zie waar het leidt me. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Dus twee en vier, laat me gaan vooruit en net swap jullie twee. 577 00:19:20,161 --> 00:19:22,400 Als je fysiek kunt bewegen uzelf en uw papieren, 578 00:19:22,400 --> 00:19:25,040 Ik lijken te hebben gekregen van de lijst in een betere staat. 579 00:19:25,040 --> 00:19:26,330 >> Nu, ze zijn goed. 580 00:19:26,330 --> 00:19:28,480 Ik ga om verder te gaan, vier en zes, ziet er goed uit. 581 00:19:28,480 --> 00:19:29,110 Geen probleem. 582 00:19:29,110 --> 00:19:30,440 Zes en acht, OK. 583 00:19:30,440 --> 00:19:31,860 Acht en een ander probleem. 584 00:19:31,860 --> 00:19:34,750 Want wat waar is ongeveer acht en één? 585 00:19:34,750 --> 00:19:36,990 Komt men voor acht, en dus wat moeten we doen? 586 00:19:36,990 --> 00:19:38,090 Laten we wisselen deze twee. 587 00:19:38,090 --> 00:19:39,316 Één en acht. 588 00:19:39,316 --> 00:19:40,690 En nu ga ik om door te gaan. 589 00:19:40,690 --> 00:19:42,030 Ik ga om te blijven kijken vooruit. 590 00:19:42,030 --> 00:19:42,840 En laten we zien wat er gebeurt. 591 00:19:42,840 --> 00:19:44,680 Acht en drie, van Natuurlijk, niet in orde. 592 00:19:44,680 --> 00:19:45,815 Laten we swap. 593 00:19:45,815 --> 00:19:46,940 Acht en zeven, natuurlijk. 594 00:19:46,940 --> 00:19:47,481 Buiten de orde. 595 00:19:47,481 --> 00:19:48,280 Laten we swap. 596 00:19:48,280 --> 00:19:49,940 Acht en vijf, natuurlijk, laten we swap. 597 00:19:49,940 --> 00:19:50,560 Prima. 598 00:19:50,560 --> 00:19:51,880 De lijst wordt gesorteerd. 599 00:19:51,880 --> 00:19:53,060 ja? 600 00:19:53,060 --> 00:19:54,280 >> OK, natuurlijk niet. 601 00:19:54,280 --> 00:19:55,860 Maar het is een beetje beter, toch? 602 00:19:55,860 --> 00:19:57,270 Omdat kennisgeving wat er is gebeurd. 603 00:19:57,270 --> 00:20:01,749 Elke keer uitgevoerd we een swap, een kleiner aantal soort doorgedrongen op die manier, 604 00:20:01,749 --> 00:20:03,790 en een groter aantal doorgesijpeld deze manier, of we zullen 605 00:20:03,790 --> 00:20:06,880 beginnen zeggende geborreld aan de links of naar rechts borrelen. 606 00:20:06,880 --> 00:20:10,080 >> Nu, het is niet genoeg, omdat in het beste geval een aantal zou kunnen 607 00:20:10,080 --> 00:20:11,990 een plek zijn verhuisd vooruit, of in het slechtste geval, 608 00:20:11,990 --> 00:20:13,880 een getal misschien verhuisde één plek verder. 609 00:20:13,880 --> 00:20:16,369 Zodat je weet wat dit soort gewerkte vrij goed tot nu toe. 610 00:20:16,369 --> 00:20:17,410 Laat me proberen het gewoon opnieuw. 611 00:20:17,410 --> 00:20:18,880 Twee en vier, ze zijn OK. 612 00:20:18,880 --> 00:20:20,180 Vier en zes, ze zijn OK. 613 00:20:20,180 --> 00:20:21,790 Zes en één, buiten de orde. 614 00:20:21,790 --> 00:20:23,007 Dus laten we ruilen jullie twee. 615 00:20:23,007 --> 00:20:25,840 En nu, ziet het probleem van de begint weer beter een beetje te krijgen. 616 00:20:25,840 --> 00:20:27,006 Zes en drie, buiten de orde. 617 00:20:27,006 --> 00:20:28,100 Laten we ruilen jullie twee. 618 00:20:28,100 --> 00:20:29,730 Zes en zeven, je goed bent. 619 00:20:29,730 --> 00:20:32,230 Zeven en vijf, natuurlijk, buiten de orde. 620 00:20:32,230 --> 00:20:33,920 Zeven en acht, in orde. 621 00:20:33,920 --> 00:20:36,470 En nu, zou ik moet doe dit een paar keer. 622 00:20:36,470 --> 00:20:39,830 En in feite, denk voor jezelf misschien hoeveel keer maximaal 623 00:20:39,830 --> 00:20:41,330 misschien moet ik heen en weer te lopen? 624 00:20:41,330 --> 00:20:42,390 >> We zullen terug naar die komen. 625 00:20:42,390 --> 00:20:43,700 Dus twee en vier zijn nog steeds OK. 626 00:20:43,700 --> 00:20:44,940 Vier en één, nope. 627 00:20:44,940 --> 00:20:45,747 Dus, laten we swap. 628 00:20:45,747 --> 00:20:47,830 En nogmaals, merken visueel één is een soort van borrelende 629 00:20:47,830 --> 00:20:49,163 aan de linkerkant, waar het zou moeten zijn. 630 00:20:49,163 --> 00:20:50,010 Vier en drie swap. 631 00:20:50,010 --> 00:20:51,330 Vier en zes. 632 00:20:51,330 --> 00:20:53,100 Zes en vijf swap. 633 00:20:53,100 --> 00:20:53,959 Zes en zeven. 634 00:20:53,959 --> 00:20:55,000 Zeven en acht zijn goed. 635 00:20:55,000 --> 00:20:55,500 >> Goed. 636 00:20:55,500 --> 00:20:58,460 We krijgen nog beter. 637 00:20:58,460 --> 00:20:59,130 Dus laten we zien. 638 00:20:59,130 --> 00:21:00,940 Nu hebben we twee en één. 639 00:21:00,940 --> 00:21:02,520 Uiteraard wisselen. 640 00:21:02,520 --> 00:21:07,520 Twee en drie, drie en vier, vier en vijf, zes en zeven, zeven en acht. 641 00:21:07,520 --> 00:21:08,020 Goed. 642 00:21:08,020 --> 00:21:08,730 En weet je wat? 643 00:21:08,730 --> 00:21:11,190 Want ik maakte een verandering daar, Laat mij u een sanity check. 644 00:21:11,190 --> 00:21:13,023 Laat me gaan de hele weg terug naar het begin. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 Eén, two-- yup, zie je? 647 00:21:14,750 --> 00:21:15,870 Er iets mis was. 648 00:21:15,870 --> 00:21:18,420 Drie, vier, vijf, zes, zeven, acht. 649 00:21:18,420 --> 00:21:21,920 En in deze laatste pas, zijn je comfortabel met mijn nu 650 00:21:21,920 --> 00:21:23,830 beweerde dat het wordt gesorteerd? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Visueel, dat is absoluut waar. 653 00:21:25,880 --> 00:21:28,410 Maar functioneel is, wat heb ook toevallig 654 00:21:28,410 --> 00:21:31,870 in dat laatste pas waarmee je om te bevestigen dat deze lijst is inderdaad 655 00:21:31,870 --> 00:21:32,660 naargelang? 656 00:21:32,660 --> 00:21:34,477 >> Wat heb ik gedaan of dit laatste pas niet doen? 657 00:21:34,477 --> 00:21:35,810 Publiek: Er waren geen veranderingen. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Sorry? 659 00:21:36,120 --> 00:21:37,070 Publiek: Geen wijzigingen. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: Er waren geen wijzigingen. 661 00:21:38,653 --> 00:21:41,947 Dus het zou stom van me te zijn dat doet hetzelfde algoritme weer 662 00:21:41,947 --> 00:21:43,780 als ik geen maakte verandert het eerst. 663 00:21:43,780 --> 00:21:45,160 En de staat is niet veranderd. 664 00:21:45,160 --> 00:21:47,576 Zeker, ik ben niet van plan om te maken elke verandert de tweede keer. 665 00:21:47,576 --> 00:21:49,820 En ja, het is nu veilig om te zeggen, is de lijst sorteren. 666 00:21:49,820 --> 00:21:52,069 >> Inderdaad is dit nu iets dat we in het algemeen 667 00:21:52,069 --> 00:21:56,900 oproep bubble sort, waarbij paarsgewijs, je fouten weer te corrigeren, 668 00:21:56,900 --> 00:22:00,210 en opnieuw, en opnieuw, en u houden heen en weer, 669 00:22:00,210 --> 00:22:03,370 en heen en weer, totdat je maken geen dergelijke swaps, op welk punt 670 00:22:03,370 --> 00:22:07,089 u kunt er zeker van zijn, ja, ik afgewerkt vaststelling van alle fouten. 671 00:22:07,089 --> 00:22:08,630 Laten we het resetten en probeer een andere aanpak. 672 00:22:08,630 --> 00:22:11,590 Als jullie terug kon gaan naar de volgorde waarin u een ogenblik geleden, 673 00:22:11,590 --> 00:22:13,780 die eruit zagen als deze. 674 00:22:13,780 --> 00:22:17,640 Nu, laten we eens een aanpak een weinig meer als het examen boek, 675 00:22:17,640 --> 00:22:21,122 waarbij we voortdurend waren het selecteren van de letter van het alfabet 676 00:22:21,122 --> 00:22:22,830 dat we soort wilden te behandelen volgende. 677 00:22:22,830 --> 00:22:26,420 Misschien was het een grote brief, zoals A, of een lage letter Z. 678 00:22:26,420 --> 00:22:28,170 >> Dus iedereen is terug in deze volgorde. 679 00:22:28,170 --> 00:22:29,800 En nu laat me dit te doen. 680 00:22:29,800 --> 00:22:34,880 Laten we eens kijken ik weet dat ik heb acht nummers hier. 681 00:22:34,880 --> 00:22:37,410 Ik ga om te gaan en gewoon doelbewust selecteren 682 00:22:37,410 --> 00:22:38,520 de kleinste elementen. 683 00:22:38,520 --> 00:22:38,760 Rechts? 684 00:22:38,760 --> 00:22:39,801 Dit lijkt ook intuïtief. 685 00:22:39,801 --> 00:22:42,560 Waarom heb ik niet de kleinste vinden element, het zetten waar het behoort, 686 00:22:42,560 --> 00:22:45,280 krijgen dan de volgende kleinste element, zet waar het behoort, en gewoon herhalen. 687 00:22:45,280 --> 00:22:46,820 >> Omdat intuïtief, dat zou ook moeten werken. 688 00:22:46,820 --> 00:22:48,441 Zo vier, dat is een vrij klein aantal. 689 00:22:48,441 --> 00:22:49,940 Ik ga om te onthouden waar dit is. 690 00:22:49,940 --> 00:22:50,523 Even wachten. 691 00:22:50,523 --> 00:22:51,577 Two kleiner. 692 00:22:51,577 --> 00:22:53,910 Laat me nu herinneren waar twee is, en vergeet vier. 693 00:22:53,910 --> 00:22:55,050 We zullen later gaan met dat. 694 00:22:55,050 --> 00:22:56,460 Zes, ik ben niet geïnteresseerd. 695 00:22:56,460 --> 00:22:57,810 Acht, ik ben niet geïnteresseerd in. 696 00:22:57,810 --> 00:22:59,780 Is mijn nieuwe kleine aantal. 697 00:22:59,780 --> 00:23:01,470 Dus ik ga om te onthouden waar men is. 698 00:23:01,470 --> 00:23:02,534 Drie, niet geïnteresseerd. 699 00:23:02,534 --> 00:23:03,450 Zeven, niet geïnteresseerd. 700 00:23:03,450 --> 00:23:04,530 Vijf, niet geïnteresseerd. 701 00:23:04,530 --> 00:23:07,390 >> Dus zonder te vallen het podium dit jaar, 702 00:23:07,390 --> 00:23:09,890 Ik ga nummer grijpen een-- en wat was je naam ook alweer? 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 En als je zou kunnen samen met mij op het begin van de lijst, 706 00:23:13,540 --> 00:23:14,870 laten we u waar u behoort. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- wat is uw naam? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan is in de weg. 710 00:23:18,191 --> 00:23:23,490 Dus voordat Stefan lost dit probleem, wat moeten we doen? 711 00:23:23,490 --> 00:23:25,412 Wat doen we met Stefan? 712 00:23:25,412 --> 00:23:27,269 >> PUBLIEK: [onverstaanbaar]. 713 00:23:27,269 --> 00:23:28,060 DAVID J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Dus we konden doen. 715 00:23:28,850 --> 00:23:31,730 We konden soort nemen Stefan en zijn vier, en zet ze gewoon in een variabele 716 00:23:31,730 --> 00:23:33,530 en vast te houden voor enige tijd, 717 00:23:33,530 --> 00:23:35,220 waardoor ruimte voor nummer één. 718 00:23:35,220 --> 00:23:36,280 En dat is niet slecht. 719 00:23:36,280 --> 00:23:39,270 Ik kon voorstellen, waarom niet we gewoon Stefan hier? 720 00:23:39,270 --> 00:23:41,610 Waarom zou dit in strijd zijn één van de ideeën die we begonnen 721 00:23:41,610 --> 00:23:44,830 over de vorige keer, afgelopen week? 722 00:23:44,830 --> 00:23:45,330 Ja? 723 00:23:45,330 --> 00:23:45,740 >> PUBLIEK: [onverstaanbaar]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: Er is geen index voor het. 725 00:23:46,860 --> 00:23:49,735 Als u denkt dat dit inderdaad als een array, dit is als negatief, 726 00:23:49,735 --> 00:23:52,900 dus er is geen geheugen eigenlijk hier als dit inderdaad een array, 727 00:23:52,900 --> 00:23:55,090 zoals wij verklaarde vorige week in collegezaal. 728 00:23:55,090 --> 00:23:56,250 Dus we moeten dit niet doen. 729 00:23:56,250 --> 00:23:57,340 We zouden het op te slaan in een variabele. 730 00:23:57,340 --> 00:23:57,820 >> Of weet je wat? 731 00:23:57,820 --> 00:23:59,153 Ik hoorde iemand anders suggereren. 732 00:23:59,153 --> 00:24:01,020 Wat kunnen we doen met Stefan? 733 00:24:01,020 --> 00:24:03,770 Waarom niet we hem gewoon uit te zetten en zet hem dan waar de nummer één was. 734 00:24:03,770 --> 00:24:05,170 Dus als je wilt om daar te gaan. 735 00:24:05,170 --> 00:24:07,300 Inderdaad is dit een vrij goede oplossing. 736 00:24:07,300 --> 00:24:10,480 Nu aan de ene kant, ik heb soort van maakte het probleem nog erger. 737 00:24:10,480 --> 00:24:13,650 Vier is nu verder weg van waar het zou moeten zijn. 738 00:24:13,650 --> 00:24:14,900 Het moet in de richting van deze helft. 739 00:24:14,900 --> 00:24:16,100 >> Maar weet je wat? 740 00:24:16,100 --> 00:24:17,630 Dat zou pech geweest. 741 00:24:17,630 --> 00:24:18,822 Misschien nummer acht was hier. 742 00:24:18,822 --> 00:24:20,530 En ja, misschien zouden we hebben gekregen geluk, 743 00:24:20,530 --> 00:24:22,460 en geduwd acht dichter bij het einde. 744 00:24:22,460 --> 00:24:24,710 Dus in het einde van de dag, het vriendelijk van alle gemiddelden uit. 745 00:24:24,710 --> 00:24:26,085 We hoeven niet over vier schelen. 746 00:24:26,085 --> 00:24:29,400 Alles wat ik zorg over nu is selecteren van het kleinste element. 747 00:24:29,400 --> 00:24:32,030 >> En nu, wat ik ga naar doen is vergeet nummer één 748 00:24:32,030 --> 00:24:35,160 permanent, omdat ik weet dat de lijst achter me is nu opgelost. 749 00:24:35,160 --> 00:24:36,720 Dus mijn lijst was eerder groot acht. 750 00:24:36,720 --> 00:24:37,720 Nu, het is van groot zeven. 751 00:24:37,720 --> 00:24:40,340 Dus mijn probleem is om kleinere, alhoewel lineair. 752 00:24:40,340 --> 00:24:43,022 Dus nu ga ik het selecteren huidige kleinste element, twee. 753 00:24:43,022 --> 00:24:46,520 Zes, acht, vier, drie, zeven, vijf. 754 00:24:46,520 --> 00:24:47,770 Dat was de kleinste element. 755 00:24:47,770 --> 00:24:49,416 Dus wat moet ik doen met-- Wat was je naam ook alweer? 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 We gaan naar Joseph in de plaats te verlaten. 759 00:24:52,000 --> 00:24:54,842 Nu, ik ga doen alsof dat deze jongens zijn-- goed, 760 00:24:54,842 --> 00:24:56,550 Ik weet dat deze twee zijn al naargelang. 761 00:24:56,550 --> 00:24:58,424 Laten we nu concentreren op de rest van de lijst. 762 00:24:58,424 --> 00:25:00,080 Zes is de kleinste stroom. 763 00:25:00,080 --> 00:25:01,190 Acht is groter. 764 00:25:01,190 --> 00:25:02,970 Vier is nu de huidige kleinste. 765 00:25:02,970 --> 00:25:04,762 Drie is nu de huidige kleinste. 766 00:25:04,762 --> 00:25:07,720 En nu, ga ik drie te selecteren, wie is-- wat is je naam ook alweer? 767 00:25:07,720 --> 00:25:08,190 SERENA: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, als je zou kunnen pak je nummer en swap met-- 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 Kom terug, en we zijn gaat verwisselen die twee. 772 00:25:15,220 --> 00:25:17,360 En nu, laten we dit op de automatische piloot. 773 00:25:17,360 --> 00:25:21,589 Ik ga om te gaan en laat het aan jullie naar de volgende kleinste elementen te selecteren. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Nummer vier, wat moet je doen? 776 00:25:24,560 --> 00:25:26,261 Excellent. 777 00:25:26,261 --> 00:25:27,760 Nu, ik ga nog een keer te maken. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Ik zie vijf is de kleinste. 780 00:25:31,465 --> 00:25:32,840 Nu, ga ik neem nog een pass. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Zes is het kleinst. 783 00:25:34,880 --> 00:25:35,520 Goed. 784 00:25:35,520 --> 00:25:36,585 Zeven is het kleinst. 785 00:25:36,585 --> 00:25:37,085 Geen verandering. 786 00:25:37,085 --> 00:25:38,630 Acht is het kleinst. 787 00:25:38,630 --> 00:25:39,170 Gedaan. 788 00:25:39,170 --> 00:25:43,900 >> Dus wat we hebben net gedaan door iteratief het selecteren van een element na elkaar 789 00:25:43,900 --> 00:25:47,230 wordt de uitvoering van iets dat we gaan formaliseren als selectie sorteren. 790 00:25:47,230 --> 00:25:49,120 En het is misschien wel eenvoudiger te leggen, 791 00:25:49,120 --> 00:25:51,310 in die letterlijk alles wat je wilt doen is gewoon blijven 792 00:25:51,310 --> 00:25:54,700 heen en weer door de lijst selecteren, de volgende kleinste element, 793 00:25:54,700 --> 00:25:55,720 totdat je klaar bent. 794 00:25:55,720 --> 00:25:58,650 >> Dus het is nog eenvoudiger, misschien intuïtief, dan vorig. 795 00:25:58,650 --> 00:26:00,020 Laten we proberen een laatste. 796 00:26:00,020 --> 00:26:03,060 Als jullie jezelf kunnen resetten in de volgende posities 797 00:26:03,060 --> 00:26:08,600 een laatste keer, laten we eens kijken of we kunnen niet Nu formaliseren een andere aanpak. 798 00:26:08,600 --> 00:26:12,857 In feite, zou iemand daar willen voorstellen 799 00:26:12,857 --> 00:26:14,440 hoe anders zouden we dat doen? 800 00:26:14,440 --> 00:26:17,439 Zonder gooien out buzzwords of sorteren van de antwoorden die reeds bekend zijn, 801 00:26:17,439 --> 00:26:19,689 gewoon intuïtief, wat kunnen we doen? 802 00:26:19,689 --> 00:26:21,635 >> PUBLIEK: [onverstaanbaar]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Ja. 804 00:26:22,510 --> 00:26:24,620 Dus er is een aantal grote intuïtie daar. 805 00:26:24,620 --> 00:26:28,020 Goede dingen lijken tot nu toe gebeuren in de informatica als we verdelen 806 00:26:28,020 --> 00:26:30,832 en verover het probleem van de te verdelen het in de helft en half en half. 807 00:26:30,832 --> 00:26:32,540 En zo ja, we kunnen gaan doen. 808 00:26:32,540 --> 00:26:35,754 En in feite, dat gaat worden, zullen we zie, een van onze beste oplossingen nog. 809 00:26:35,754 --> 00:26:37,420 Maar laten we terug naar die vóór lang. 810 00:26:37,420 --> 00:26:40,500 In feite, we gaan doen dat een beetje later deze week. 811 00:26:40,500 --> 00:26:42,180 Wat kunnen we doen om dit op te lossen? 812 00:26:42,180 --> 00:26:44,647 Dus iedereen is hier in schijnbaar willekeurige volgorde. 813 00:26:44,647 --> 00:26:45,230 Weet je wat? 814 00:26:45,230 --> 00:26:48,320 In plaats van heen en weer, heen en weer, heen en weer 815 00:26:48,320 --> 00:26:50,624 elke keer, dit voelt als Ik ben bezig met een veel wandelen. 816 00:26:50,624 --> 00:26:52,790 Waarom heb ik niet alleen beginnen bij het begin van de lijst, 817 00:26:52,790 --> 00:26:54,960 en gewoon vier waar het hoort? 818 00:26:54,960 --> 00:26:59,680 Dus laat ik neem aan dat voor het moment dat mijn lijst is alleen het eerste element. 819 00:26:59,680 --> 00:27:04,937 Wordt vier naargelang op dit moment in de tijd, Als alles wat ik zorg over is alles hier? 820 00:27:04,937 --> 00:27:06,520 Dit is een soort van triviaal waar, toch? 821 00:27:06,520 --> 00:27:10,000 Net als de lijst met één nummer, en dat nummer vier is uiteraard opgelost. 822 00:27:10,000 --> 00:27:13,070 >> Dus laat me gewoon bepalen dat deze lijst wordt gesorteerd. 823 00:27:13,070 --> 00:27:15,090 Maar nu heb ik de rest van deze lijst. 824 00:27:15,090 --> 00:27:17,240 Dus nu, ik tegenkom twee. 825 00:27:17,240 --> 00:27:21,690 Waar doet twee natuurlijk behoren met betrekking tot vier? 826 00:27:21,690 --> 00:27:22,580 Voordat vier. 827 00:27:22,580 --> 00:27:23,862 Dus wat kan ik hier doen? 828 00:27:23,862 --> 00:27:24,820 Wat is je naam ook al weer? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: Joseph, Als je terug kon stappen 831 00:27:26,030 --> 00:27:27,790 voor slechts een moment met uw nummer. 832 00:27:27,790 --> 00:27:31,130 En nu, wat moet Stefan hier doen? 833 00:27:31,130 --> 00:27:33,720 Laten we verschuiven Stefan hier. 834 00:27:33,720 --> 00:27:35,520 En nu, laat Joseph hier komen. 835 00:27:35,520 --> 00:27:39,660 En nu, laat me zeggen dat alles hier is gesorteerd. 836 00:27:39,660 --> 00:27:42,474 Dus, soortgelijk resultaat, maar een fundamenteel andere benadering. 837 00:27:42,474 --> 00:27:44,140 Ik heb niet eens gekeken wat daar beneden. 838 00:27:44,140 --> 00:27:46,310 Ik blijf gewoon het nemen van de elementen als ze overhandigd aan mij, 839 00:27:46,310 --> 00:27:47,240 en omgaan met hen. 840 00:27:47,240 --> 00:27:48,330 >> Dus nu zie ik nummer zes. 841 00:27:48,330 --> 00:27:51,110 Waar komt nummer zes behoort? 842 00:27:51,110 --> 00:27:53,250 We hebben twee, vier, zes. 843 00:27:53,250 --> 00:27:54,800 Precies waar ze nu is. 844 00:27:54,800 --> 00:27:57,750 Dus laten we dat alleen al, en nu beweren dat dit deel van de lijst 845 00:27:57,750 --> 00:27:58,772 is nu opgelost. 846 00:27:58,772 --> 00:28:01,230 En dus, dit voelt fundamenteel anders in dat ik ben gewoon 847 00:28:01,230 --> 00:28:05,230 bewegen door de lijst hier lineair, en ik ben nooit een verdubbeling van terug. 848 00:28:05,230 --> 00:28:05,730 Ja. 849 00:28:05,730 --> 00:28:06,230 Prima. 850 00:28:06,230 --> 00:28:08,190 Dus acht, waar moet je thuis? 851 00:28:08,190 --> 00:28:08,730 Hier. 852 00:28:08,730 --> 00:28:09,310 Perfect. 853 00:28:09,310 --> 00:28:10,210 Dus nu, één. 854 00:28:10,210 --> 00:28:10,900 Oh Oh. 855 00:28:10,900 --> 00:28:13,010 Dit voelt als het is zal duur. 856 00:28:13,010 --> 00:28:15,690 Nu in het vorige algoritme, Ik ruilde mensen. 857 00:28:15,690 --> 00:28:18,648 Dus ik zou hem de hele weg te zetten op het begin, maar dan verplaatst Joseph. 858 00:28:18,648 --> 00:28:21,450 Maar als ik Joseph bewegen, nu wat is er mis zijn? 859 00:28:21,450 --> 00:28:24,250 >> Nu, ik heb een soort van undone-- Ik heb genomen een stap vooruit en dan 860 00:28:24,250 --> 00:28:26,300 een stap terug, want nu Joseph zou zijn buiten de orde. 861 00:28:26,300 --> 00:28:26,830 Dus laten we dit doen. 862 00:28:26,830 --> 00:28:29,150 Als je nummer een zou kunnen nemen en stap terug voor slechts een moment. 863 00:28:29,150 --> 00:28:30,490 Hoe kunnen we put-- wat was je naam ook alweer? 864 00:28:30,490 --> 00:28:31,130 >> Annan: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: Annan in de plaats? 866 00:28:32,610 --> 00:28:36,091 Wat er moet gebeuren met respect twee, vier, zes en acht? 867 00:28:36,091 --> 00:28:37,570 Ze moeten allemaal te verschuiven. 868 00:28:37,570 --> 00:28:42,590 Dus als acht zou willen verschuiven Eerst dan zes dan vier, dan twee. 869 00:28:42,590 --> 00:28:45,380 En dan Annan, als je wilt zoals hier in te komen, goed. 870 00:28:45,380 --> 00:28:47,760 Maar hier, hebben we net soort betaalde een prijs 871 00:28:47,760 --> 00:28:49,510 op een ander punt in het algoritme. 872 00:28:49,510 --> 00:28:52,550 Overwegende dat de laatste keer met de selectie sorteren en zelfs bubble sort, 873 00:28:52,550 --> 00:28:54,700 Ik ga terug lopen en weer, heen en weer, 874 00:28:54,700 --> 00:28:58,360 die zeker is optelling qua tijd, en letterlijk stapsgewijze. 875 00:28:58,360 --> 00:29:00,660 >> Inbrengen sorteren, op het eerste oogopslag, ziet eruit als het is 876 00:29:00,660 --> 00:29:05,150 super slimmer, dat ik ben gewoon het maken van trage, stapsgewijze vooruitgang, 877 00:29:05,150 --> 00:29:07,120 maar ik ben niet van plan dit heen en weer. 878 00:29:07,120 --> 00:29:09,410 Maar als iemand inderdaad buiten de orde, bericht 879 00:29:09,410 --> 00:29:10,840 al het werk dat ik moest gewoon doen. 880 00:29:10,840 --> 00:29:14,750 Ik moest de helft van de lijst te verplaatsen alleen om ruimte voor nummer één te maken. 881 00:29:14,750 --> 00:29:16,790 Dus het is hetzelfde bedrag van het werk tot nu toe is 882 00:29:16,790 --> 00:29:18,690 voelt, gewoon een ander soort werk. 883 00:29:18,690 --> 00:29:19,370 >> Laten we doorgaan. 884 00:29:19,370 --> 00:29:22,657 Dus nu weten we dat iedereen tussen één en acht zijn gesorteerd. 885 00:29:22,657 --> 00:29:23,740 Hier, ik heb nummer drie. 886 00:29:23,740 --> 00:29:25,864 Als je wilt op te halen nummer drie, één stap terug. 887 00:29:25,864 --> 00:29:28,260 En wat doen jullie doen? 888 00:29:28,260 --> 00:29:28,760 Yep. 889 00:29:28,760 --> 00:29:33,070 Dus dat is een andere één, twee, drie stappen. 890 00:29:33,070 --> 00:29:36,010 Drie eenheden van de tijd die kosten slechts mij, dus dat drie kunnen nu passen. 891 00:29:36,010 --> 00:29:37,460 Tot slot, zeven. 892 00:29:37,460 --> 00:29:39,730 >> Laten we verder gaan en hebben je een stap terug te nemen. 893 00:29:39,730 --> 00:29:42,780 Dit is alleen maar om ons te kosten één eenheid van tijd, maar dat is OK. 894 00:29:42,780 --> 00:29:44,170 En nu, vijf gaat naar een beetje duurder. 895 00:29:44,170 --> 00:29:45,340 Indien u graag een stap terug. 896 00:29:45,340 --> 00:29:48,380 We moeten verhuizen acht, en zeven en zes. 897 00:29:48,380 --> 00:29:50,749 En dan iedereen is nu opgelost. 898 00:29:50,749 --> 00:29:52,290 Dus een grote hand aan onze vrijwilligers hier. 899 00:29:52,290 --> 00:29:53,554 Heel erg bedankt. 900 00:29:53,554 --> 00:29:56,220 >> [Applaus] 901 00:29:56,220 --> 00:29:56,860 >> Bedankt iedereen. 902 00:29:56,860 --> 00:29:57,520 Bedankt iedereen. 903 00:29:57,520 --> 00:30:02,940 Dus laten we zien nu hoe kostbaar dat alles was. 904 00:30:02,940 --> 00:30:06,210 Laten we eens kijken misschien wel de eenvoudigste van deze, bubble sort. 905 00:30:06,210 --> 00:30:09,950 En ik zeg eenvoudigste, alleen omdat je kunt het gretig op te lossen door gewoon 906 00:30:09,950 --> 00:30:11,660 bevestig de paarsgewijs probleem. 907 00:30:11,660 --> 00:30:13,720 Fix de paarsgewijze probleem hier, opnieuw en opnieuw 908 00:30:13,720 --> 00:30:17,680 en weer herhalen zoveel vaak als je echt nodig hebt om. 909 00:30:17,680 --> 00:30:21,050 >> Dus het blijkt dat met een bel soort, goed, 910 00:30:21,050 --> 00:30:25,820 hoeveel stappen moet ik op te nemen de eerste pas van dat algoritme? 911 00:30:25,820 --> 00:30:30,850 Ik zou take-- laten see-- één, twee, drie, vier, vijf, zes, zeven. 912 00:30:30,850 --> 00:30:32,190 En er is hier acht elementen. 913 00:30:32,190 --> 00:30:35,280 Dus het is net n minus 1 stappen krijgen vanaf het begin van de lijst 914 00:30:35,280 --> 00:30:36,380 aan het einde van de lijst. 915 00:30:36,380 --> 00:30:41,350 >> Maar met de selectie sorteren, herinneren dat ik het selecteren van elementen weer 916 00:30:41,350 --> 00:30:44,590 en nogmaals dat is de kleinste, Ik zet het op zijn plaats, 917 00:30:44,590 --> 00:30:46,616 maar dan ben ik niet zoek achter me weer. 918 00:30:46,616 --> 00:30:49,490 Dus ik denk dat het een beetje meer duidelijk dan is dat de eerste keer, zou ik 919 00:30:49,490 --> 00:30:52,680 moeten alle n min 1 stappen te ondernemen het kleinste element te vinden. 920 00:30:52,680 --> 00:30:55,920 Dan zet ik ze op hun plaats, en ik verdrijven wie was hier eerder. 921 00:30:55,920 --> 00:30:57,500 >> Maar dan hoef ik niet te blijven kijken naar dit element, 922 00:30:57,500 --> 00:30:59,040 omdat ik weet dat het reeds de kleinste. 923 00:30:59,040 --> 00:31:01,581 Dus nu kan ik kijken naar slechts zeven elementen dan zes elementen, 924 00:31:01,581 --> 00:31:03,290 dan vijf elementen, toen vier elementen. 925 00:31:03,290 --> 00:31:06,900 Dus mathematisch, als n het aantal elementen of getallen 926 00:31:06,900 --> 00:31:11,990 dat we begonnen met, kun je je voorstellen dat dit hetzelfde is als n minus 1, 927 00:31:11,990 --> 00:31:14,250 n plus minus 2 stappen, n plus minus 3 stappen, 928 00:31:14,250 --> 00:31:16,780 n plus minus 4 stappen, alle weg naar nog maar één stap. 929 00:31:16,780 --> 00:31:18,160 En ik ben op mijn laatste persoon. 930 00:31:18,160 --> 00:31:20,650 >> En als u zich herinneren dat veel van statistieken boeken of wiskunde boeken 931 00:31:20,650 --> 00:31:24,730 hebben die formules op de hardcover achter of voor hen, 932 00:31:24,730 --> 00:31:27,690 het blijkt dat deze serie kan eenvoudiger worden uitgedrukt 933 00:31:27,690 --> 00:31:28,857 zo n keer n minus 1 op 2. 934 00:31:28,857 --> 00:31:31,273 En het is fijn als dat niet in de voorhoede van je geest. 935 00:31:31,273 --> 00:31:32,420 Maar dit is inderdaad waar. 936 00:31:32,420 --> 00:31:34,449 Dat is gewoon een eenvoudigere manier van schrijven. 937 00:31:34,449 --> 00:31:36,240 En dan als je denkt terug naar de lagere school, 938 00:31:36,240 --> 00:31:38,698 als je gewoon beginnen te vermenigvuldigen dingen uit, dit natuurlijk 939 00:31:38,698 --> 00:31:41,820 is gewoon n kwadraat minus n gedeeld door 2. 940 00:31:41,820 --> 00:31:44,772 Alles wat ik heb gedaan is uit te breiden de uitdrukkingen daar. 941 00:31:44,772 --> 00:31:46,730 En dus laten herschrijven deze een beetje anders. 942 00:31:46,730 --> 00:31:49,780 Dat is n kwadraat gedeeld door 2 min n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Dus nogmaals, ik ben gewoon een soort van de toepassing wat rekenkunde regeert daar. 944 00:31:53,270 --> 00:31:57,140 Maar merk nu dat de grootste term in deze uitdrukking, zogezegd, 945 00:31:57,140 --> 00:31:58,540 dat n kwadraat. 946 00:31:58,540 --> 00:32:02,910 Dus ja, het is n kwadraat gedeeld door 2, verminderd met n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Maar over het algemeen, als n gaat een grote waarde, 948 00:32:05,080 --> 00:32:08,740 Ik ga om te beweren dat n kwadraat gaat de dominante factor. 949 00:32:08,740 --> 00:32:10,490 Het is gewoon gaat worden een grotere bijdrage 950 00:32:10,490 --> 00:32:12,877 het aantal stappen dan n / 2. 951 00:32:12,877 --> 00:32:13,960 Dus wat ik bedoel? 952 00:32:13,960 --> 00:32:16,795 Laten we proberen een eenvoudig voorbeeld, zelfs hoewel de wiskunde krijgt een beetje groot. 953 00:32:16,795 --> 00:32:20,210 >> Dus stel dat we hadden 1.000.000 mensen op het podium, of 1.000.000 dingen 954 00:32:20,210 --> 00:32:21,320 dat we willen afstand. 955 00:32:21,320 --> 00:32:23,730 Laten plug miljoen in precies die formule 956 00:32:23,730 --> 00:32:27,230 om te zien hoeveel stappen er nodig is in totaal tot een miljoen elementen te sorteren met behulp van laten we zeggen, 957 00:32:27,230 --> 00:32:28,560 selectie sorteren. 958 00:32:28,560 --> 00:32:30,760 >> Dus zouden we dezelfde formule als voorheen. 959 00:32:30,760 --> 00:32:34,120 Ik zou de stekker een miljoen, zodat ik krijg miljoen kwadraat gedeeld door 2, 960 00:32:34,120 --> 00:32:35,990 minus miljoen gedeeld door 2. 961 00:32:35,990 --> 00:32:40,180 Als ik dat doe wiskunde van tevoren Hier hebben we 500 miljard 962 00:32:40,180 --> 00:32:47,460 minus 500.000, waarvan geeft ons 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 dat is pretty darn groot. 964 00:32:49,270 --> 00:32:54,370 >> In feite, als je nu vergelijken 499.000.000.000, 999.000.000, 965 00:32:54,370 --> 00:33:01,210 500.000 tegen onze oorspronkelijke waarde, 500 miljard, het is zo verdomd dichtbij. 966 00:33:01,210 --> 00:33:06,850 Rechts? n kwadraat gedeeld door 2 geeft ons-- of liever, n kwadraat gedeeld door 2 967 00:33:06,850 --> 00:33:08,370 gaf ons 500 miljard. 968 00:33:08,370 --> 00:33:13,510 Dat is pretty darn dicht tot 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 dat wil zeggen het aftrekken af ​​500.000, of meer in het algemeen, af te trekken uit 970 00:33:17,970 --> 00:33:20,010 n kwadraat, niet echt een groot probleem. 971 00:33:20,010 --> 00:33:22,490 De n kwadraat maakt deze aantallen groeien echt snel. 972 00:33:22,490 --> 00:33:25,790 >> Nu is dit alleen van belang in zoverre zoals wij, als informatici, 973 00:33:25,790 --> 00:33:29,350 zijn over het algemeen niet van plan om zo veel schelen de nuances van deze formules 974 00:33:29,350 --> 00:33:31,400 en precies wat de precieze antwoorden zijn. 975 00:33:31,400 --> 00:33:33,390 We zorg alleen dat, weet je wat? 976 00:33:33,390 --> 00:33:37,810 Aan het eind van de dag, deze formule in de orde van n kwadraat. 977 00:33:37,810 --> 00:33:39,350 >> Ja, we delen door 2 in. 978 00:33:39,350 --> 00:33:41,360 Ja, we trekken uit n min 2. 979 00:33:41,360 --> 00:33:46,860 Maar aan het eind van de dag, de term die ons echt pijn doet en kost ons 980 00:33:46,860 --> 00:33:48,995 veel trappen is dat vierkant termijn. 981 00:33:48,995 --> 00:33:51,370 En zo wat een computer wetenschapper gaat meestal doen 982 00:33:51,370 --> 00:33:54,160 is negeren al die kleinere orde termen, 983 00:33:54,160 --> 00:33:56,900 en kijk maar naar degene die draagt ​​het meest bij aan de kosten. 984 00:33:56,900 --> 00:34:00,530 >> En dat is mooi, want we kunnen praten nu in veel grotere algemeenheid 985 00:34:00,530 --> 00:34:02,470 over algoritmen en kunnen ze vergelijken. 986 00:34:02,470 --> 00:34:04,550 En het feit dat ik ben het gebruik van deze O is weloverwogen. 987 00:34:04,550 --> 00:34:06,680 Als ik zeg in de orde van, ik ben speciaal 988 00:34:06,680 --> 00:34:09,560 verwijst iets riep grote O. En grote O 989 00:34:09,560 --> 00:34:14,090 is een notatie die een computer wetenschapper gebruikt om te beschrijven 990 00:34:14,090 --> 00:34:16,710 een bovengrens iets. 991 00:34:16,710 --> 00:34:21,150 >> Dus als je zegt dat een algoritme is in grote O n kwadraat, 992 00:34:21,150 --> 00:34:23,380 zoals ik voorgesteld slechts een daarnet, dat betekent 993 00:34:23,380 --> 00:34:27,710 dat in termen van de lopende tijd of de efficiëntie, 994 00:34:27,710 --> 00:34:30,090 zij neemt de bestelling n kwadraat stappen. 995 00:34:30,090 --> 00:34:31,420 Misschien meer, misschien minder. 996 00:34:31,420 --> 00:34:33,435 Maar het is in de orde van n kwadraat. 997 00:34:33,435 --> 00:34:34,560 En dat is de bovengrens. 998 00:34:34,560 --> 00:34:36,530 Het is niet van plan om pijnlijker dan dat. 999 00:34:36,530 --> 00:34:40,800 Het gaat niet n blokjes gesneden te zijn, of 2 de n of iets veel groter. 1000 00:34:40,800 --> 00:34:43,800 Dit is een bovengrens op wat die kosten is. 1001 00:34:43,800 --> 00:34:46,150 Dus gezien het feit dat, laten we overwegen slechts een paar voorbeelden. 1002 00:34:46,150 --> 00:34:49,820 En dit is slechts een eindige lijst van veel voorkomende looptijden 1003 00:34:49,820 --> 00:34:52,870 voor algoritmen die bedoeld is illustratief voor sommige dingen die we hebben 1004 00:34:52,870 --> 00:34:53,600 al gezien. 1005 00:34:53,600 --> 00:34:58,060 >> Dus bijvoorbeeld in het geval van selectie sorteren, wat ik hier beweren 1006 00:34:58,060 --> 00:35:02,250 is lopen dat soort selectie's tijd in de orde van n kwadraat. 1007 00:35:02,250 --> 00:35:06,260 In het ergste geval, ga ik heb een hele hoop willekeurige getallen hier. 1008 00:35:06,260 --> 00:35:08,600 En zoals we mathematisch gezien, als ik blijven lopen 1009 00:35:08,600 --> 00:35:11,310 door de lijst, door de lijst, het selecteren van de kleinste 1010 00:35:11,310 --> 00:35:14,410 weer element, als ik eigenlijk opschrijven alle stappen 1011 00:35:14,410 --> 00:35:18,750 Ik neem als ik voorgesteld formulaically voor, het is aan de orde van n kwadraat 1012 00:35:18,750 --> 00:35:20,370 stappen die ik neem. 1013 00:35:20,370 --> 00:35:24,520 >> En het blijkt dat bubble sorteren en insertion sort 1014 00:35:24,520 --> 00:35:27,370 zijn zo langzaam in het ergste geval. 1015 00:35:27,370 --> 00:35:32,040 Denk bijvoorbeeld, insertion sort, de laatste algoritme waarmee we, 1016 00:35:32,040 --> 00:35:35,500 die hadden we eens kijken naar het element, en steek hem vervolgens waar het thuishoort. 1017 00:35:35,500 --> 00:35:38,720 En dan hebben we gekeken naar het volgende element, en ingebracht waar het behoort. 1018 00:35:38,720 --> 00:35:40,990 >> Dus rekening houden met de best mogelijke scenario. 1019 00:35:40,990 --> 00:35:45,590 Stel dat ik had mijn vrijwilligers line-up dit letterlijk als één tot en met acht, 1020 00:35:45,590 --> 00:35:47,440 al naargelang. 1021 00:35:47,440 --> 00:35:51,300 Hoeveel stappen is insertion sort gaan nemen tot acht mensen te sorteren, 1022 00:35:51,300 --> 00:35:55,640 Als ze aankomen op het podium op zoek als dit? 1023 00:35:55,640 --> 00:35:57,410 >> Acht mensen al naargelang. 1024 00:35:57,410 --> 00:35:58,760 En ik gebruik insertion sort. 1025 00:35:58,760 --> 00:36:02,180 Die laatste van de algoritmen. 1026 00:36:02,180 --> 00:36:03,640 Nou, laten naspelen echt snel. 1027 00:36:03,640 --> 00:36:05,504 Dus als ik hier beginnen, zie ik een. 1028 00:36:05,504 --> 00:36:06,420 Waar komt men behoort? 1029 00:36:06,420 --> 00:36:07,730 Het behoort hier. 1030 00:36:07,730 --> 00:36:08,330 Ik zie twee. 1031 00:36:08,330 --> 00:36:09,660 Waar komt twee behoren? 1032 00:36:09,660 --> 00:36:10,260 Hier. 1033 00:36:10,260 --> 00:36:10,900 Ik zie drie. 1034 00:36:10,900 --> 00:36:11,920 Waar komt drie behoren? 1035 00:36:11,920 --> 00:36:12,480 Hier. 1036 00:36:12,480 --> 00:36:13,100 >> Ik zie vier. 1037 00:36:13,100 --> 00:36:13,600 Hier. 1038 00:36:13,600 --> 00:36:15,660 Vijf, zes, zeven, acht. 1039 00:36:15,660 --> 00:36:17,320 Er is geen reden om mezelf te herhalen. 1040 00:36:17,320 --> 00:36:21,260 En ja, hoeveel stappen is dat in termen van n? 1041 00:36:21,260 --> 00:36:23,870 Het is aan de orde van n stappen, toch? n minus 1. 1042 00:36:23,870 --> 00:36:27,567 Maar ik nam een ​​aantal lineaire stappen, en nu ben ik klaar. 1043 00:36:27,567 --> 00:36:28,900 Dus dat is het beste geval, dat wel. 1044 00:36:28,900 --> 00:36:29,983 Hoe zit het met het ergste geval? 1045 00:36:29,983 --> 00:36:32,730 Wat acht dan waren er, en zeven waren daar beneden, 1046 00:36:32,730 --> 00:36:35,840 en één en twee waren hier, dus dat de lijst echt werden teruggedraaid? 1047 00:36:35,840 --> 00:36:38,300 >> Nou, wat gebeurt er inderdaad als dit is het nummer? 1048 00:36:38,300 --> 00:36:41,300 En we zullen maar een paar voorbeelden te doen. 1049 00:36:41,300 --> 00:36:49,300 Wat als, inderdaad, de nummer acht is hier, en de number-- whoops. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Dus wat als, inderdaad, het aantal acht is helemaal hierheen, 1052 00:36:56,430 --> 00:36:57,790 en ik ben met behulp van een soort inbrengen? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Ik eis op dit moment is het op zijn plaats. 1055 00:37:00,280 --> 00:37:03,152 Maar nu, seven-- waar gaat zeven gaan? 1056 00:37:03,152 --> 00:37:04,360 Uiteraard gaat het hier. 1057 00:37:04,360 --> 00:37:06,760 Dus ik moet verhuizen acht meer dan één plaats. 1058 00:37:06,760 --> 00:37:08,554 Nu zes, waar gaat het heen? 1059 00:37:08,554 --> 00:37:09,220 Nou, oke. 1060 00:37:09,220 --> 00:37:13,150 Nu, ik moet verhuizen acht meer dan een plaats, en zeven meer dan een plaats, 1061 00:37:13,150 --> 00:37:14,440 en toen ik naar beneden plop zes. 1062 00:37:14,440 --> 00:37:16,870 >> Dus de eerste keer, het kost me een stap om dingen te repareren, 1063 00:37:16,870 --> 00:37:18,570 dan is het kostte me twee stappen om dingen te repareren. 1064 00:37:18,570 --> 00:37:20,370 Hoeveel stappen is er gaan nemen om vast te stellen 1065 00:37:20,370 --> 00:37:22,720 dingen tot vijf op de juiste plaats te zetten? 1066 00:37:22,720 --> 00:37:23,340 Drie. 1067 00:37:23,340 --> 00:37:29,520 Want nu moet ik bewegen een, twee, drie. 1068 00:37:29,520 --> 00:37:32,430 Hoeveel stappen gaat het te nemen vier op de juiste plaats te zetten? 1069 00:37:32,430 --> 00:37:36,040 4 plus 5, plus 6, plus 7. 1070 00:37:36,040 --> 00:37:40,260 >> En dus is het mathematisch identiek aan wat wij beschreven voor de selectie soort. 1071 00:37:40,260 --> 00:37:42,130 We hebben deze serie Dat is gewoon verhogen. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, of omgekeerd, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 voegt voor vandaag doeleinden in de orde van n kwadraat. 1074 00:37:52,610 --> 00:37:57,640 >> Dus laat me ook dat bepalen bubble sort is ook in n kwadraat. 1075 00:37:57,640 --> 00:38:01,340 Want met bubble sort, elk keer dat ik door de lijst, 1076 00:38:01,340 --> 00:38:03,100 Ik ben het nemen van ongeveer hoeveel stappen? 1077 00:38:03,100 --> 00:38:06,260 Elke keer dat ik letterlijk lopen vanaf daar naar daar? 1078 00:38:06,260 --> 00:38:07,960 Ruwweg n stappen. 1079 00:38:07,960 --> 00:38:12,650 Maar hoe vaak zou ik moeten gaan door de lijst? 1080 00:38:12,650 --> 00:38:13,920 >> Nou, ruwweg n tijd. 1081 00:38:13,920 --> 00:38:15,680 Misschien n min 1, maar ruwweg n keer. 1082 00:38:15,680 --> 00:38:16,430 Nou, waarom is dat? 1083 00:38:16,430 --> 00:38:19,560 Nou, met bubble sort, indien we beginnen met bubble sort, 1084 00:38:19,560 --> 00:38:23,570 de lijst in het slechtste situatie, die weer geheel 1085 00:38:23,570 --> 00:38:25,550 achteruit, wat er gaat gebeuren? 1086 00:38:25,550 --> 00:38:28,830 Ik ga door de lijst, en het aantal men behoort de hele weg daar. 1087 00:38:28,830 --> 00:38:33,280 >> Maar met bubble sort, hoe ver gaat men bewegen op mijn eerste passage door de lijst? 1088 00:38:33,280 --> 00:38:36,620 Hoeveel plekken krijgt hij dichter bij de juiste plaats? 1089 00:38:36,620 --> 00:38:37,240 Eentje maar. 1090 00:38:37,240 --> 00:38:40,281 Dus als je voor reden door dit, telkens via dit algoritme, 1091 00:38:40,281 --> 00:38:41,880 David's nemen ongeveer n stappen. 1092 00:38:41,880 --> 00:38:44,940 Maar hoeveel passes de lijst is deze 1093 00:38:44,940 --> 00:38:49,060 gaan nemen voor een te borrelen naar links waar het hoort? 1094 00:38:49,060 --> 00:38:51,840 >> Hij moet bewegen als, n ruimtes op deze manier. 1095 00:38:51,840 --> 00:38:57,960 Dus alleen maar om de sortering te doen van de lijst, Ik moet heen en weer te lopen n keer. 1096 00:38:57,960 --> 00:39:01,540 En elke keer, ik ben kijken n elementen. 1097 00:39:01,540 --> 00:39:05,410 Dus doe n dingen n keer op de volgorde van n kwadraat. 1098 00:39:05,410 --> 00:39:07,220 >> Nu, we zullen zien in een aantal van de korte broek die 1099 00:39:07,220 --> 00:39:10,440 zijn ingebed in CS50's volgende probleem set, een andere benadering deze, 1100 00:39:10,440 --> 00:39:13,490 maar voor nu, laten we maar eens kijken enkele andere looptijden, 1101 00:39:13,490 --> 00:39:16,840 vooral als de sortering die nemen een beetje tijd om te bezinken. 1102 00:39:16,840 --> 00:39:21,790 Wat is een algoritme dat we hebben al gezien dat neemt in de orde van n stappen? 1103 00:39:21,790 --> 00:39:27,560 >> Wat moet een lineaire aantal te nemen van de stappen die we tot nu toe hebben gezien? 1104 00:39:27,560 --> 00:39:29,350 Wat is dat? 1105 00:39:29,350 --> 00:39:30,480 Het telefoonboek zoeken. 1106 00:39:30,480 --> 00:39:31,390 Het eerste algoritme. 1107 00:39:31,390 --> 00:39:31,560 Rechts? 1108 00:39:31,560 --> 00:39:33,650 Waar we zijn lineair op zoek naar Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Inderdaad. 1110 00:39:34,150 --> 00:39:37,180 Vanaf week nul, toen ik begon het draaien van een pagina in een tijd, 1111 00:39:37,180 --> 00:39:40,095 en ik zei zelfs dat het was een beetje van een lineaire gevoel algoritme 1112 00:39:40,095 --> 00:39:42,720 en we hadden dat beeld op de bord met de rechte rode lijn 1113 00:39:42,720 --> 00:39:44,678 en de rechte gele lijn, die inderdaad waren 1114 00:39:44,678 --> 00:39:46,810 algoritmen die in grote O n. 1115 00:39:46,810 --> 00:39:50,680 >> Omdat Mike Smith vinden in een telefoon boek van n pagina's, in het ergste geval, 1116 00:39:50,680 --> 00:39:52,422 zou me n stappen te ondernemen. 1117 00:39:52,422 --> 00:39:53,630 Hoe zit het met het nemen van deelname? 1118 00:39:53,630 --> 00:39:55,790 Een twee drie vier vijf zes. 1119 00:39:55,790 --> 00:39:59,420 Wat is de looptijd van deze algoritme voor het nemen van het bijwonen? 1120 00:39:59,420 --> 00:40:03,070 Big O n, omdat in theorie I moet iedereen in de kamer te wijzen. 1121 00:40:03,070 --> 00:40:05,861 >> Nu als een terzijde, hoe zit het met de andere optimalisatie van week nul? 1122 00:40:05,861 --> 00:40:08,117 Twee, vier, zes, acht, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Een computer wetenschapper zou realiseren, wacht eens even, 1124 00:40:10,200 --> 00:40:12,320 dat is in de orde van n gedeeld door twee stappen. 1125 00:40:12,320 --> 00:40:12,820 Rechts? 1126 00:40:12,820 --> 00:40:14,444 Want ik ben bezig met twee personen tegelijk. 1127 00:40:14,444 --> 00:40:17,015 Maar we gaan om te negeren die lagere orde termen, 1128 00:40:17,015 --> 00:40:19,140 en we gaan gewoon gooi de kloof rijden met 2, 1129 00:40:19,140 --> 00:40:21,830 en gewoon zeggen, grote O n voor dat algoritme ook. 1130 00:40:21,830 --> 00:40:22,760 >> Wat dacht je van deze? 1131 00:40:22,760 --> 00:40:26,170 We zullen overslaan enkele van deze, maar wat was een algoritme dat log n was? 1132 00:40:26,170 --> 00:40:29,900 Dat duurde ongeveer log n stappen? 1133 00:40:29,900 --> 00:40:30,870 De verdeel en heers. 1134 00:40:30,870 --> 00:40:31,369 Precies. 1135 00:40:31,369 --> 00:40:33,900 Net als het telefoonboek voorbeeld week nul en eerder vandaag, 1136 00:40:33,900 --> 00:40:36,191 waar we verdeeld het probleem opnieuw en opnieuw en opnieuw. 1137 00:40:36,191 --> 00:40:39,070 We trokken het op het bord in de week nul als een gebogen groene lijn, 1138 00:40:39,070 --> 00:40:41,460 en we zeiden dat dag was een logaritmische algoritme. 1139 00:40:41,460 --> 00:40:44,970 >> Inderdaad, het aantal stappen te neemt om verdeel uit te voeren en te veroveren, 1140 00:40:44,970 --> 00:40:48,610 of binaire zoekopdracht als we beginnen noemde het, net als in het telefoonboek, 1141 00:40:48,610 --> 00:40:50,680 is in de orde van log en trappen. 1142 00:40:50,680 --> 00:40:52,470 En dit is een beetje een rare één. 1143 00:40:52,470 --> 00:40:54,910 >> Wat kost een stap, of specifieker 1144 00:40:54,910 --> 00:40:56,240 een constant aantal stappen? 1145 00:40:56,240 --> 00:40:58,865 Misschien is het twee, misschien is het drie, maar een computer wetenschapper net 1146 00:40:58,865 --> 00:41:01,423 vereenvoudigt het als grote O van 1, sommige constant aantal stappen. 1147 00:41:01,423 --> 00:41:04,256 Wat is iets wat je zou kunnen doen neemt een constant aantal stappen? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Wat is de looptijd van de klappen? 1150 00:41:10,930 --> 00:41:11,920 Constante tijd. 1151 00:41:11,920 --> 00:41:12,420 Rechts? 1152 00:41:12,420 --> 00:41:15,490 Zoals, wat is de looptijd van iets dat slechts één neemt doen 1153 00:41:15,490 --> 00:41:18,570 operatie, zoals afdrukken F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Die kunnen worden gezegd om een ​​constante tijd, tenzij minder hoek geval met print F, 1155 00:41:24,110 --> 00:41:28,260 Wat zou de looptijd print F eigenlijk? 1156 00:41:28,260 --> 00:41:28,790 En waarom? 1157 00:41:28,790 --> 00:41:30,550 Wat is n meten in dat geval? 1158 00:41:30,550 --> 00:41:32,251 >> PUBLIEK: [onverstaanbaar]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Precies. 1160 00:41:33,250 --> 00:41:34,900 Het aantal tekens we willen afdrukken. 1161 00:41:34,900 --> 00:41:36,191 Dus het is zeer context-gevoelig. 1162 00:41:36,191 --> 00:41:39,910 Vandaag hebben we ons vooral geconcentreerd veel op letters en cijfers hier op het bord. 1163 00:41:39,910 --> 00:41:43,540 Maar het kan ook zijn karakters in een feitelijke string. 1164 00:41:43,540 --> 00:41:46,420 Zo blijkt er een andere maatregel die zal beginnen zorgen te maken over, 1165 00:41:46,420 --> 00:41:48,530 en dat is het tegenovergestelde van grote O, om zo te zeggen. 1166 00:41:48,530 --> 00:41:50,120 >> Dat is omega notatie. 1167 00:41:50,120 --> 00:41:53,380 Terwijl grote O betekent wat is, de bovengrens op uw lopende tijd? 1168 00:41:53,380 --> 00:41:55,580 Maximaal, hoeveel tijd misschien iets te nemen? 1169 00:41:55,580 --> 00:41:59,250 Omega-- jammer dit blijft komen up-- is het tegenovergestelde van dat, 1170 00:41:59,250 --> 00:42:02,960 waarbij het een ondergrens aan de hoeveelheid tijd die iets zou kunnen nemen. 1171 00:42:02,960 --> 00:42:10,480 >> So. bijvoorbeeld wat een algoritme dat duurt altijd n kwadraat stappen? 1172 00:42:10,480 --> 00:42:15,600 Nou, een van de algoritmes die we hebben gezien Vandaag, in feite zou zijn dat ook. 1173 00:42:15,600 --> 00:42:16,720 Selectie soort. 1174 00:42:16,720 --> 00:42:18,270 Selectie soort is vrij dom. 1175 00:42:18,270 --> 00:42:21,760 Zelfs als de algorithm-- sorry, zelfs Als de matrix al gesorteerd, 1176 00:42:21,760 --> 00:42:24,150 selectie sorteren gaat blijven lopen door de lijst 1177 00:42:24,150 --> 00:42:28,907 om zeker te zijn heeft de kleinste element opnieuw en opnieuw en opnieuw. 1178 00:42:28,907 --> 00:42:31,740 En ook al heb je de mens in de publiek weet dat, wacht eens even, 1179 00:42:31,740 --> 00:42:33,948 je al voorbij de kleinste element, de computer 1180 00:42:33,948 --> 00:42:37,300 weet niet dat totdat het lijkt helemaal door de lijst. 1181 00:42:37,300 --> 00:42:40,240 Ook een ondergrens die Ook in aanmerking worden genomen 1182 00:42:40,240 --> 00:42:42,000 misschien lineaire tijd. 1183 00:42:42,000 --> 00:42:48,260 >> Hoeveel tijd kost het om sort n elementen in het beste 1184 00:42:48,260 --> 00:42:52,420 Bij het gebruik van iets als bubble sort? 1185 00:42:52,420 --> 00:42:54,280 Stel dat uw lijst is al opgelost. 1186 00:42:54,280 --> 00:42:56,696 We zeiden bubble sort neemt de volgorde van de n kwadraat stappen. 1187 00:42:56,696 --> 00:42:59,640 Maar wat als het al naargelang? 1188 00:42:59,640 --> 00:43:02,310 Wat als je je realiseert na één doorgang door de array 1189 00:43:02,310 --> 00:43:03,540 dat je geen swaps hebt gemaakt? 1190 00:43:03,540 --> 00:43:05,970 Heb je nodig om te blijven maken meer doorgangen? 1191 00:43:05,970 --> 00:43:06,470 >> Nee. 1192 00:43:06,470 --> 00:43:10,340 Dus een ondergrens op de bubble sort zou kunnen zeggen lineair. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 En we kunnen kijken anderen deze ook. 1195 00:43:14,450 --> 00:43:17,990 Dus laten we eens een snelle blik op slechts een visualisatie hier 1196 00:43:17,990 --> 00:43:20,790 om te zien hoe deze zich onderscheiden. 1197 00:43:20,790 --> 00:43:24,592 Ik ga hier naar beneden gaan in deze pagina die beschikbaar is op de website van C50's, 1198 00:43:24,592 --> 00:43:27,550 maar het zal een pijn aan het werken te krijgen, aangezien het gebruik maakt van een techniek genaamd 1199 00:43:27,550 --> 00:43:30,560 Java-applets, dat is een grotendeels ondersteund deze dagen, 1200 00:43:30,560 --> 00:43:32,730 op zijn minst door Chrome en enkele anderen. 1201 00:43:32,730 --> 00:43:37,070 >> En laat me gaan en versnellen dit en uit te leggen wat er gaande is. 1202 00:43:37,070 --> 00:43:40,840 Dit is een demonstratie van de zeepbel sorteren, het eerste algoritme hebben we gekeken. 1203 00:43:40,840 --> 00:43:43,950 En het is een weergave dat elk Deze staven een getal. 1204 00:43:43,950 --> 00:43:45,710 Hoe groter de bar, hoe groter het aantal. 1205 00:43:45,710 --> 00:43:47,520 Hoe kleiner de bar, hoe kleiner het getal. 1206 00:43:47,520 --> 00:43:50,353 En wat u kunt visueel te zien, zelfs hoewel dit gaat super snel, 1207 00:43:50,353 --> 00:43:53,699 is dat de rode balk is net als ik, heen en weer oplossen van problemen. 1208 00:43:53,699 --> 00:43:56,740 Je kunt zien dat de grotere elementen inderdaad borrelen naar rechts, 1209 00:43:56,740 --> 00:43:59,650 en kleinere elementen borrelen aan de linkerkant. 1210 00:43:59,650 --> 00:44:01,870 En hier beneden, als we eigenlijk kijken nauwer, 1211 00:44:01,870 --> 00:44:04,330 kunnen we eigenlijk tellen aantal vergelijkingen en swaps 1212 00:44:04,330 --> 00:44:05,350 die werden gemaakt. 1213 00:44:05,350 --> 00:44:07,360 >> Maar in plaats daarvan, laten we eens kijken bij de tweede algoritme 1214 00:44:07,360 --> 00:44:11,240 hebben we gekeken naar eerder met onze vrijwilligers, selectie sorteren. 1215 00:44:11,240 --> 00:44:13,500 Visueel, heeft een heel ander effect. 1216 00:44:13,500 --> 00:44:16,820 Maar het is, nogmaals, zeer intuïtief, in die houden we het selecteren van de kleinste 1217 00:44:16,820 --> 00:44:18,660 element, en we kregen een beetje geluk. 1218 00:44:18,660 --> 00:44:20,110 Dat voelde fundamenteel sneller. 1219 00:44:20,110 --> 00:44:22,840 Maar als we liepen dit opnieuw en opnieuw en wederom met veel ingangen, 1220 00:44:22,840 --> 00:44:26,680 zouden we zien dat het inderdaad nog steeds in grote O n kwadraat. 1221 00:44:26,680 --> 00:44:29,920 >> Laten we doen een laatste hier, insertion sort, 1222 00:44:29,920 --> 00:44:33,180 waarbij de derde algoritme was keken we naar, en terugroepen 1223 00:44:33,180 --> 00:44:36,700 dat deze zich bezighoudt met de elementen zoals het hen tegenkomt, 1224 00:44:36,700 --> 00:44:39,290 maar dan is het misschien wel verschuivingen over dingen om ruimte te maken, 1225 00:44:39,290 --> 00:44:41,660 invoegen van elementen waar ze thuishoren. 1226 00:44:41,660 --> 00:44:45,330 >> En ook dit eindigt het geven van de eindresultaat. Nu drie van die 1227 00:44:45,330 --> 00:44:46,490 voelde behoorlijk snel. 1228 00:44:46,490 --> 00:44:48,740 En inderdaad, ik liep ze bij een vrij goede clip. 1229 00:44:48,740 --> 00:44:52,510 Maar fundamenteel, ze zijn allemaal vrij verschrikkelijk, om eerlijk te zijn. 1230 00:44:52,510 --> 00:44:56,960 Al deze algoritmen dusver die worden uitgevoerd in grote O n kwadraat 1231 00:44:56,960 --> 00:44:59,270 neem nogal wat tijd om te draaien in het einde. 1232 00:44:59,270 --> 00:45:01,920 >> En inderdaad, kunnen we zien en het gevoel dat dit ten slotte 1233 00:45:01,920 --> 00:45:04,090 als ik trek dit derde en laatste demo. 1234 00:45:04,090 --> 00:45:05,840 Dit is een visualisatie dat gaat 1235 00:45:05,840 --> 00:45:08,500 bubbelen sorteren tonen links, selectie sorteren in het midden, 1236 00:45:08,500 --> 00:45:13,410 en iets als een van onze kant verhoogt eerder gesuggereerd, 1237 00:45:13,410 --> 00:45:15,020 samenvoegen sorteren aan de rechterkant. 1238 00:45:15,020 --> 00:45:16,937 Een verdeel en heers strategie aan de rechterkant. 1239 00:45:16,937 --> 00:45:19,520 En dat is in feite wat we gaan kijken naar woensdag. 1240 00:45:19,520 --> 00:45:21,990 Maar laten we de tijd om deze parallel lopen. 1241 00:45:21,990 --> 00:45:26,765 Het is ruwweg evenveel elementen, alle lopende tegelijk. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubble sort vs selectie sort vs merge sort. 1244 00:45:34,440 --> 00:45:36,760 >> Nu, ze zijn allemaal running in theorie tegelijkertijd. 1245 00:45:36,760 --> 00:45:39,830 De CPU draait op dezelfde snelheid, maar u 1246 00:45:39,830 --> 00:45:44,014 kan voelen hoe vervelend dit is zeer snel gaan worden, 1247 00:45:44,014 --> 00:45:45,930 en hoe snel bij We injecteren een beetje van de week 1248 00:45:45,930 --> 00:45:49,330 De zero-algoritmen kunnen we versnellen dingen. 1249 00:45:49,330 --> 00:45:51,760 >> En laten we nu vergelijken deze in een laatste vorm. 1250 00:45:51,760 --> 00:45:55,710 Ik ga om te gaan naar de website van CS50, waar 1251 00:45:55,710 --> 00:45:59,020 hebben we deze laatste schakel voor vandaag, waar iemand op het internet 1252 00:45:59,020 --> 00:46:03,960 vriendelijk samen een video, die een vangt wat anders sorteren 1253 00:46:03,960 --> 00:46:07,510 algoritmes klinken. 1254 00:46:07,510 --> 00:46:09,577 Dit is een soort inbrengen. 1255 00:46:09,577 --> 00:46:12,072 >> [Pieptoon] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Waarbij je solliciteert een frequentie op basis van de hoogte van de bar bar. 1258 00:46:16,850 --> 00:46:19,826 Dit is bubble sort. 1259 00:46:19,826 --> 00:46:21,822 >> [Warped piepen] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Coming up next is-- komen up next is-- selectie sorteren, 1262 00:46:45,774 --> 00:46:48,820 waarbij nogmaals, we selecteren het kleinste element, 1263 00:46:48,820 --> 00:46:51,820 en we kunnen zien groeien van links naar rechts. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Samenvoegen sorteren, onze winnaar tot nu toe vandaag. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Merk op hoe het verdelen van dingen in [onhoorbaar] helft en kwartalen. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome soort, die we niet hebben over gesproken, en visueel creëert 1270 00:47:21,660 --> 00:47:24,450 en audally een beetje een verschillende vorm en geluid. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Heen en weer, schoonmaken dingen. 1273 00:47:30,160 --> 00:47:32,230 Lees ook Heapsort op de website van deze kerel. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> En dat is het. 1276 00:47:36,810 --> 00:47:38,210 Wij zullen u de volgende keer. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Suizend EN MUZIEK] 1279 00:47:48,334 --> 00:50:24,839