1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [MUSIK SPELA] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> DAVID J. MALAN: Detta är CS50. 5 00:00:12,550 --> 00:00:14,612 Och detta är början på veckan tre. 6 00:00:14,612 --> 00:00:16,820 Så vi har en hel del spännande saker att täcka idag. 7 00:00:16,820 --> 00:00:20,160 En hel del möjligheter för volontärer upp på scenen. 8 00:00:20,160 --> 00:00:22,780 Och i slutändan, är idag inte om kod alls. 9 00:00:22,780 --> 00:00:24,820 Men det handlar om idéer, och det handlar om algoritmer, 10 00:00:24,820 --> 00:00:28,420 och faktiskt få tillbaka en del av de lärdomar som dragits från vecka noll, 11 00:00:28,420 --> 00:00:31,910 vari minns, vi infört denna monster. 12 00:00:31,910 --> 00:00:33,880 Och upplåning inspiration från detta, för att starta 13 00:00:33,880 --> 00:00:36,879 att lösa allt mer sofistikerade problem algoritmiskt. 14 00:00:36,879 --> 00:00:38,420 Men först, ett par meddelanden. 15 00:00:38,420 --> 00:00:42,020 Så en, om du vill gå CS50 personal och klasskamrater vid lunch 16 00:00:42,020 --> 00:00:44,670 denna fredag, både här och i Cambridge, och i New Haven, 17 00:00:44,670 --> 00:00:48,060 besök kursens webbplats där en URL kan hittas. 18 00:00:48,060 --> 00:00:50,390 Föreläsning denna onsdag kommer inte vara här i Sanders. 19 00:00:50,390 --> 00:00:53,610 Det blir bara på nätet, så lyssna på CS50: s hemsida, 20 00:00:53,610 --> 00:00:55,850 om här i Cambridge eller New Haven som också. 21 00:00:55,850 --> 00:00:58,110 >> Och sedan problem ställa in två är redan i dina händer. 22 00:00:58,110 --> 00:01:03,067 Om du inte har dykt ännu, låt mig att erbjuda skarpt förslag 23 00:01:03,067 --> 00:01:05,150 att, särskilt nu, som problemet sätter förväg, 24 00:01:05,150 --> 00:01:08,669 du verkligen vill börja nu, om inte dabble lite på helgen eller före 25 00:01:08,669 --> 00:01:10,710 när de först gå ut på Fredagar eftersom du kommer 26 00:01:10,710 --> 00:01:14,380 tycker att de är inte nödvändigtvis blir längre eller mer utmanande per 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Jag tror att du kommer att upptäcka att, i Generellt tenderar de att ta ungefär 29 00:01:17,575 --> 00:01:18,892 ungefär samma tid. 30 00:01:18,892 --> 00:01:20,850 Men det verkligen beror på eleven, och det 31 00:01:20,850 --> 00:01:22,880 beror på tänke med vilken du närmar dig det. 32 00:01:22,880 --> 00:01:24,910 Men alltid, du kommer att köra upp mot några väggen, 33 00:01:24,910 --> 00:01:26,350 och du kommer att träffa vissa programfel, och du är bara 34 00:01:26,350 --> 00:01:27,950 inte kommer att kunna komma över det någon gång. 35 00:01:27,950 --> 00:01:31,380 Och det är oerhört värdefullt att kunna att steg bort, kom tillbaka nästa dag, 36 00:01:31,380 --> 00:01:35,286 gå till kontorstid, inlägg på CS50 Diskutera eller liknande, för att faktiskt få hävs. 37 00:01:35,286 --> 00:01:36,160 Så ha det i åtanke. 38 00:01:36,160 --> 00:01:40,830 Starta tidigast som möjligt är det bästa du kan göra. 39 00:01:40,830 --> 00:01:44,160 Så här är där vi började klassen, över i vecka noll. 40 00:01:44,160 --> 00:01:47,441 Och kan vi få en volontär här för att hjälpa mig att hitta mikrofoner? 41 00:01:47,441 --> 00:01:47,940 OK. 42 00:01:47,940 --> 00:01:48,900 Stående upp redan. 43 00:01:48,900 --> 00:01:50,080 Kom upp. 44 00:01:50,080 --> 00:01:53,707 Antar att det är hur det kommer att fungera. 45 00:01:53,707 --> 00:01:54,415 Vad heter du? 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 upp. 49 00:01:57,910 --> 00:01:58,619 Trevligt att träffas. 50 00:01:58,619 --> 00:01:59,910 ALAN ESTRADA: Trevligt att träffas. 51 00:01:59,910 --> 00:02:02,772 DAVID J. MALAN: Och du var här med oss ​​i vecka noll, naturligtvis. 52 00:02:02,772 --> 00:02:03,028 ALAN ESTRADA: Jag var. 53 00:02:03,028 --> 00:02:03,160 Jag var. 54 00:02:03,160 --> 00:02:05,868 >> DAVID J. MALAN: Så kan du gå framåt och hitta för oss Mike Smith, 55 00:02:05,868 --> 00:02:08,639 så fort du kan? 56 00:02:08,639 --> 00:02:10,639 Så fort du kan. 57 00:02:10,639 --> 00:02:13,756 Bokstavligen riva problemet i hälften så du behöver. 58 00:02:13,756 --> 00:02:15,130 >> ALAN ESTRADA: Um. 59 00:02:15,130 --> 00:02:17,380 DAVID J. MALAN: Bokstavligen riva problemet i halv. 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 Väldigt bra. 64 00:02:23,300 --> 00:02:23,700 >> David J. MALAN: OK. 65 00:02:23,700 --> 00:02:24,200 God. 66 00:02:24,200 --> 00:02:24,701 Tack. 67 00:02:24,701 --> 00:02:25,700 ALAN ESTRADA: Mycket bra. 68 00:02:25,700 --> 00:02:26,210 OK. 69 00:02:26,210 --> 00:02:27,610 >> DAVID J. MALAN: Och så nu, du har skurit ner 70 00:02:27,610 --> 00:02:29,320 till halv storlek av problemet. 71 00:02:29,320 --> 00:02:31,267 Nu är vi ner till en fjärdedel. 72 00:02:31,267 --> 00:02:33,475 Är du uppmärksamma vilken sida vi håller? 73 00:02:33,475 --> 00:02:34,405 >> [Skrattar] 74 00:02:34,405 --> 00:02:35,970 >> ALAN ESTRADA: Ja, jag think-- 75 00:02:35,970 --> 00:02:37,594 >> DAVID J. MALAN: Vilka avsnitt är vi i? 76 00:02:37,594 --> 00:02:39,150 ALAN ESTRADA: Ljuddämpare, så. 77 00:02:39,150 --> 00:02:39,941 >> David J. MALAN: OK. 78 00:02:39,941 --> 00:02:42,810 Men Mike Smith går vara efter Ljuddämpare. 79 00:02:42,810 --> 00:02:44,130 So-- 80 00:02:44,130 --> 00:02:48,180 >> [Skrattar] 81 00:02:48,180 --> 00:02:48,742 >> Okej. 82 00:02:48,742 --> 00:02:50,200 ALAN ESTRADA: Vart är vi ser? 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, vi är i kirurgiskt. 86 00:02:54,760 --> 00:02:57,840 Nu, läkare. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> ALAN ESTRADA: Let's- låt oss gå med riktiga. 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 Om du behöver Real. 93 00:03:03,700 --> 00:03:05,250 Nu är vilken väg Mike Smith? 94 00:03:05,250 --> 00:03:06,250 >> ALAN ESTRADA: Detta sätt. 95 00:03:06,250 --> 00:03:07,333 >> DAVID J. MALAN: Vilken väg? 96 00:03:07,333 --> 00:03:08,240 ALAN ESTRADA: Vänta. 97 00:03:08,240 --> 00:03:08,790 M är-- rätt? 98 00:03:08,790 --> 00:03:09,110 Vi började with-- 99 00:03:09,110 --> 00:03:10,090 >> DAVID J. MALAN: Ja. 100 00:03:10,090 --> 00:03:10,650 De är kvar. 101 00:03:10,650 --> 00:03:11,430 Du har rätt. 102 00:03:11,430 --> 00:03:11,710 >> ALAN ESTRADA: Ja. 103 00:03:11,710 --> 00:03:13,126 >> DAVID J. MALAN: Så Mike här. 104 00:03:13,126 --> 00:03:13,990 ALAN ESTRADA: Vad? 105 00:03:13,990 --> 00:03:14,665 >> [Skrattar] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Dåligt exempel, killar. 108 00:03:18,330 --> 00:03:18,830 Förlåt. 109 00:03:18,830 --> 00:03:21,610 DAVID J. MALAN: Detta kommer att lära du att hoppa ur stolen. 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 Jag fick dig. 113 00:03:23,390 --> 00:03:24,670 Jag fick dig. 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 Detta är-- OK, jag har dig. 117 00:03:26,812 --> 00:03:27,520 Smith just här? 118 00:03:27,520 --> 00:03:28,894 >> DAVID J. MALAN: Smith, tack. 119 00:03:28,894 --> 00:03:30,535 Så jag ska fortsätta leta upp Smith? 120 00:03:30,535 --> 00:03:30,790 >> ALAN ESTRADA: Oh, ja. 121 00:03:30,790 --> 00:03:31,340 Nej nej nej. 122 00:03:31,340 --> 00:03:31,600 Å nej. 123 00:03:31,600 --> 00:03:31,940 Den här är min. 124 00:03:31,940 --> 00:03:32,580 >> DAVID J. MALAN: Åh, du fick Smith. 125 00:03:32,580 --> 00:03:33,415 OK. 126 00:03:33,415 --> 00:03:34,040 >> ALAN ESTRADA: Ja, jag fick Smith här. 127 00:03:34,040 --> 00:03:34,700 Ledsen, killar. 128 00:03:34,700 --> 00:03:35,860 Jag trodde Michael-- vi letade efter Michael. 129 00:03:35,860 --> 00:03:36,550 Förlåt. 130 00:03:36,550 --> 00:03:37,550 >> DAVID J. MALAN: Det är OK. 131 00:03:37,550 --> 00:03:39,950 Okej, nu är vi in Paccini and Sons. 132 00:03:39,950 --> 00:03:41,242 >> ALAN ESTRADA: Paccini och söner. 133 00:03:41,242 --> 00:03:43,158 DAVID J. MALAN: Bara du och jag är på den här. 134 00:03:43,158 --> 00:03:44,050 OK. 135 00:03:44,050 --> 00:03:45,130 Hitta hit 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 Vi är i forskning för sopor. 140 00:03:47,728 --> 00:03:48,644 ALAN ESTRADA: Skräp. 141 00:03:48,644 --> 00:03:50,096 Oh. 142 00:03:50,096 --> 00:03:52,480 Detta kommer att ta ett tag. 143 00:03:52,480 --> 00:03:54,340 >> [Skrattar] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 DAVID J. MALAN: Skor. 146 00:03:56,720 --> 00:03:58,080 Vi är i skor. 147 00:03:58,080 --> 00:04:00,210 >> ALAN ESTRADA: Nu är vi 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 [Skrattar] 151 00:04:03,620 --> 00:04:05,440 Åh, det här är bra. 152 00:04:05,440 --> 00:04:06,910 [Skrattar] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> DAVID J. MALAN: Det är OK. 155 00:04:09,390 --> 00:04:11,365 >> ALAN ESTRADA: Åh, det är bra. 156 00:04:11,365 --> 00:04:14,425 Jag tror inte att jag kommer att har PSAT kompisar efter detta. 157 00:04:14,425 --> 00:04:15,300 DAVID J. MALAN: Good. 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 Så låt oss riva det i hälften. 163 00:04:21,600 --> 00:04:22,270 Det är ok. 164 00:04:22,270 --> 00:04:25,606 Detta avslutar dåligt ändå, eftersom Mike Smith kommer inte att vara i gula sidorna. 165 00:04:25,606 --> 00:04:26,430 >> ALAN ESTRADA: Aw. 166 00:04:26,430 --> 00:04:27,140 >> DAVID J. MALAN: Nej, det är OK. 167 00:04:27,140 --> 00:04:28,930 Men låt oss låtsas som han är på denna sida. 168 00:04:28,930 --> 00:04:33,260 Så nu har du skurit problemet ner till en sida, och vi hittade Mike Smith. 169 00:04:33,260 --> 00:04:35,180 >> [GLÄDJANDE] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Okej tack så mycket. 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 Det var extra. 175 00:04:43,646 --> 00:04:45,954 Men det var fortfarande snabbare än linjär sökning, 176 00:04:45,954 --> 00:04:47,870 där vi börjar på början av boken, 177 00:04:47,870 --> 00:04:51,210 och vi flyttar vår väg från vänster till höger, småningom letar efter Mike Smith. 178 00:04:51,210 --> 00:04:53,540 Och så, om telefonboken hade kanske 1.000 sidor, 179 00:04:53,540 --> 00:04:56,300 Kanske skulle det ha tagit oss 10-tal sidan tårar. 180 00:04:56,300 --> 00:04:59,380 >> Men du kanske har belånade rörde ett antagande 181 00:04:59,380 --> 00:05:03,602 under allt detta, det vill säga att telefonboken i förväg var vad? 182 00:05:03,602 --> 00:05:04,310 PUBLIK: Sorterade. 183 00:05:04,310 --> 00:05:05,000 DAVID J. MALAN: Det sortering. 184 00:05:05,000 --> 00:05:05,160 Höger? 185 00:05:05,160 --> 00:05:07,909 Det är sorterade i bokstavsordning, så att alla dessa namn och nummer 186 00:05:07,909 --> 00:05:11,230 sorteras från A: s till Z: s, och i bokstavsordning i mellan. 187 00:05:11,230 --> 00:05:13,100 Men i dag, vi ber nu frågan, ja, 188 00:05:13,100 --> 00:05:16,170 Hur gjorde Verizon eller telefon företag få in detta tillstånd? 189 00:05:16,170 --> 00:05:19,560 >> Eftersom det är en sak att utnyttja detta antagande, och därför, 190 00:05:19,560 --> 00:05:22,570 lösa ett problem med en algoritm mer effektivt. 191 00:05:22,570 --> 00:05:24,900 Men vi aldrig riktigt frågade vecka noll, ja, 192 00:05:24,900 --> 00:05:27,790 hur mycket kostade det Verizon eller någon annan 193 00:05:27,790 --> 00:05:29,620 att få det telefonboken i sorterad ordning? 194 00:05:29,620 --> 00:05:29,780 >> Höger? 195 00:05:29,780 --> 00:05:31,529 Det spelar ingen roll om tittar upp Mike Smith 196 00:05:31,529 --> 00:05:35,190 är supersnabb, om det tar en år för att sortera sidorna först. 197 00:05:35,190 --> 00:05:35,690 Höger? 198 00:05:35,690 --> 00:05:38,620 Du kan lika gärna sålla genom en randomiserad telefonbok, 199 00:05:38,620 --> 00:05:40,690 om det kommer att bli super dyrt att sortera det. 200 00:05:40,690 --> 00:05:42,350 Så om vi kan ha en annan volontär. 201 00:05:42,350 --> 00:05:46,350 Låt oss ta en titta upp här på hur vi might-- komma på up-- hur 202 00:05:46,350 --> 00:05:48,100 vi kan gå till väga sortering dessa. 203 00:05:48,100 --> 00:05:51,990 >> Och om Jordanien kunde faktiskt ansluta sig till oss här uppe på scenen. 204 00:05:51,990 --> 00:05:55,100 Kom upp för bara ett ögonblick. 205 00:05:55,100 --> 00:05:56,359 Vad heter du? 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 upp. 208 00:05:58,691 --> 00:06:02,070 Och du kommer att få sällskap av mig och Jordanien här. 209 00:06:02,070 --> 00:06:03,800 Caroline, tack. 210 00:06:03,800 --> 00:06:04,300 Okej. 211 00:06:04,300 --> 00:06:08,330 Så vad vi har för här Caroline är 26 blå böcker 212 00:06:08,330 --> 00:06:10,747 att FAS använder för att administrera vissa slutprov. 213 00:06:10,747 --> 00:06:13,330 Dessa blir svårt att hitta, men vad vi har gjort i förväg 214 00:06:13,330 --> 00:06:15,800 är att vi har lagt någons namn på framsidan av var och en av dessa, 215 00:06:15,800 --> 00:06:18,133 men vi har hållit det enkelt genom sedan sätta ut fullständiga namn. 216 00:06:18,133 --> 00:06:22,720 Så vi skulle sätta den person med namnet L, M, J, B, hela vägen A till Z, 217 00:06:22,720 --> 00:06:24,090 men de är i slumpmässig ordning. 218 00:06:24,090 --> 00:06:26,890 Och så om du skulle prata din igenom problem som du 219 00:06:26,890 --> 00:06:31,620 gör det, kan du gå vidare och sortera dessa för oss, från A till Ö 220 00:06:31,620 --> 00:06:34,070 >> Målgrupp: OK, så L är som i mitten. 221 00:06:34,070 --> 00:06:35,050 C börjar. 222 00:06:35,050 --> 00:06:42,410 B. J före L. B, Q. 223 00:06:42,410 --> 00:06:45,140 >> DAVID J. MALAN: Håll att funderade en sekund. 224 00:06:45,140 --> 00:06:48,910 För annars är bara detta intressant för dig, mig och Jordanien. 225 00:06:48,910 --> 00:06:49,724 Det går vi. 226 00:06:49,724 --> 00:06:50,640 PUBLIK: [OHÖRBAR]. 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 Vad gör du? 230 00:06:59,310 --> 00:07:01,730 >> CAROLINE: M kommer efter 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, bra. 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. Ja. 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. Så det ser ut som du är making-- hålla igång. 238 00:07:10,689 --> 00:07:12,730 Det ser ut som du gör en stor hög hit, 239 00:07:12,730 --> 00:07:13,910 och slag av en stor hög därborta. 240 00:07:13,910 --> 00:07:16,230 Så den första halvan av alfabetet, andra halv av alfabetet. 241 00:07:16,230 --> 00:07:16,460 OK. 242 00:07:16,460 --> 00:07:16,960 God. 243 00:07:16,960 --> 00:07:19,680 Typ av att dela upp problemet i två. 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. Så du är typ att välja dem en efter en, 248 00:07:25,070 --> 00:07:27,620 sätta det antingen vänster eller höger, eller Z är det som händer på golvet. 249 00:07:27,620 --> 00:07:28,012 OK. 250 00:07:28,012 --> 00:07:29,190 >> CAROLINE: Z kommer på golvet. 251 00:07:29,190 --> 00:07:29,360 >> David J. MALAN: OK. 252 00:07:29,360 --> 00:07:30,920 Y går på golvet. 253 00:07:30,920 --> 00:07:31,735 Nu kan vi sätta X. 254 00:07:31,735 --> 00:07:32,409 >> CAROLINE: G. 255 00:07:32,409 --> 00:07:33,700 DAVID J. MALAN: G gå vänster. 256 00:07:33,700 --> 00:07:36,017 S går rätt. 257 00:07:36,017 --> 00:07:37,642 Okej, är A går hela vägen till vänster. 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, bra. 260 00:07:39,873 --> 00:07:43,260 Vi har A, B, C. W: s går där nere. 261 00:07:43,260 --> 00:07:45,566 Okej, 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 Bra. 264 00:07:47,860 --> 00:07:49,160 CAROLINE: I centrum, jag gonna-- 265 00:07:49,160 --> 00:07:50,000 David J. MALAN: OK. 266 00:07:50,000 --> 00:07:52,375 Så nu ska vi slag av samman dessa olika högar. 267 00:07:52,375 --> 00:08:00,730 Så A till C, då ser jag D, och E och F, och G och H, och I. Nice. 268 00:08:00,730 --> 00:08:05,540 J, K. Och sedan, är denna hög upp och ner, men det är OK. 269 00:08:05,540 --> 00:08:06,040 Visst. 270 00:08:06,040 --> 00:08:07,240 Vi kan klippa vissa hörn. 271 00:08:07,240 --> 00:08:07,950 OK. 272 00:08:07,950 --> 00:08:10,530 Och då behöver vi 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 Så ett stort tack till Caroline för sortering av dessa. 276 00:08:14,122 --> 00:08:15,030 >> [GLÄDJANDE] 277 00:08:15,030 --> 00:08:17,287 >> Tack. 278 00:08:17,287 --> 00:08:18,120 Tack så mycket. 279 00:08:18,120 --> 00:08:22,910 Så nu ska vi överväga för ett ögonblick hur Caroline gick om att göra det, 280 00:08:22,910 --> 00:08:26,040 och exakt vad vi kunde att-- hur vi 281 00:08:26,040 --> 00:08:28,409 kunde lösa det problem när vi var bara 282 00:08:28,409 --> 00:08:29,950 med tanke på en hel massa slumpmässiga ingångar. 283 00:08:29,950 --> 00:08:31,610 >> Det ser ut som det var lite av ett system där? 284 00:08:31,610 --> 00:08:32,110 Höger. 285 00:08:32,110 --> 00:08:34,495 Så de tidigare breven i alfabetet, hon 286 00:08:34,495 --> 00:08:37,120 var att sätta åt vänster, och senare bokstäver i alfabetet, 287 00:08:37,120 --> 00:08:38,270 Hon satte in höger. 288 00:08:38,270 --> 00:08:40,500 Och så snart hon hittade vissa proximala bokstäver, ettor 289 00:08:40,500 --> 00:08:43,124 som går bredvid varandra, hon skulle sätta dem i ordning. 290 00:08:43,124 --> 00:08:46,750 Och så vi hade typ av dessa små högar av sorterade ingångar inträffar. 291 00:08:46,750 --> 00:08:50,540 >> Och så det är ganska precis vad de flesta av oss människor skulle göra. 292 00:08:50,540 --> 00:08:53,530 Vi skulle sorts sålla bland det, och vi skulle slags ha en mekanism. 293 00:08:53,530 --> 00:08:56,930 Men det kan vara svårt att skriva ner i en formel i och för sig. 294 00:08:56,930 --> 00:08:59,010 Det kändes lite mer organiskt än så. 295 00:08:59,010 --> 00:09:02,560 Så låt oss se om vi kan nu bundet problemet med färre ingångar. 296 00:09:02,560 --> 00:09:05,170 >> I stället för 26, låt oss göra något betydligt färre 297 00:09:05,170 --> 00:09:09,890 med bara säga, sju, bakom dessa dörrar, så att säga. 298 00:09:09,890 --> 00:09:11,300 Finns det bara sju siffror? 299 00:09:11,300 --> 00:09:15,240 Och om målet nu hand är att finna ett värde, 300 00:09:15,240 --> 00:09:17,850 låt oss se hur effektivt vi kan gå om att göra detta. 301 00:09:17,850 --> 00:09:22,460 Och låt oss se om vi kan nu börja tillämpa några siffror, 302 00:09:22,460 --> 00:09:26,310 eller vissa formler som att beskriva effektiviteten i vår telefonbok 303 00:09:26,310 --> 00:09:31,060 algoritm, vår examen bok algoritm och mer allmänt, att hitta information. 304 00:09:31,060 --> 00:09:34,770 >> Så för detta, låt mig gå vidare och på pekskärmen över här, 305 00:09:34,770 --> 00:09:41,100 sätta upp en webbläsare som har just dessa sju dörrar. 306 00:09:41,100 --> 00:09:46,670 Och om vi kunde få en annan volontär att komma på hit, 307 00:09:46,670 --> 00:09:48,480 Jag har lagt samma dörrar hit. 308 00:09:48,480 --> 00:09:49,170 Snabb volontär. 309 00:09:49,170 --> 00:09:51,130 >> Denna en-- demos går till en snabbare och snabbare nu. 310 00:09:51,130 --> 00:09:51,600 Kom ner. 311 00:09:51,600 --> 00:09:52,308 Vad heter du? 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 Okej, Trevor, kom ner. 315 00:09:55,770 --> 00:09:59,212 Så Trevor har frivilligt för att göra ett liknande problem, men en som är 316 00:09:59,212 --> 00:10:02,170 mindre omfattning, och det kommer att tillåta oss att försöka formalisera nu 317 00:10:02,170 --> 00:10:03,970 processen för att sortera dessa nummer. 318 00:10:03,970 --> 00:10:05,500 >> Så Trevor, trevligt att träffas. 319 00:10:05,500 --> 00:10:08,720 Så här är en array, så att tala, en förteckning över sju dörrar. 320 00:10:08,720 --> 00:10:10,327 Gå vidare och hitta oss numret 50. 321 00:10:10,327 --> 00:10:12,410 Och sedan i efterhand, berätta för oss hur du hittade det. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Bör be-- okej. 324 00:10:20,040 --> 00:10:21,945 Ja, det här är en här? 325 00:10:21,945 --> 00:10:24,680 Hoppsan. 326 00:10:24,680 --> 00:10:25,560 OK. 327 00:10:25,560 --> 00:10:26,680 Du klickade att en. 328 00:10:26,680 --> 00:10:28,690 God. 329 00:10:28,690 --> 00:10:29,780 >> Och bra. 330 00:10:29,780 --> 00:10:30,970 Nu kan du klickade den. 331 00:10:30,970 --> 00:10:34,060 Och låt mig ge dig mikrofonen, så att du har det på bara ett ögonblick. 332 00:10:34,060 --> 00:10:37,000 Gå vidare och klicka på intill som du tänker. 333 00:10:37,000 --> 00:10:39,812 Ja bra. 334 00:10:39,812 --> 00:10:41,020 TREVOR: Kan jag avmarkerar en dörr? 335 00:10:41,020 --> 00:10:42,620 DAVID J. MALAN: Nej, du kan inte avmarkerar. 336 00:10:42,620 --> 00:10:43,119 TREVOR: OK. 337 00:10:43,119 --> 00:10:43,974 Den här. 338 00:10:43,974 --> 00:10:45,640 DAVID J. MALAN: Vart vill du åka? 339 00:10:45,640 --> 00:10:46,410 Vilken? 340 00:10:46,410 --> 00:10:47,230 >> TREVOR: Att en. 341 00:10:47,230 --> 00:10:48,042 >> DAVID J. MALAN: Nej 342 00:10:48,042 --> 00:10:48,450 >> TREVOR: OK. 343 00:10:48,450 --> 00:10:48,735 Den här. 344 00:10:48,735 --> 00:10:49,020 >> DAVID J. MALAN: Ja. 345 00:10:49,020 --> 00:10:49,700 Det var bra. 346 00:10:49,700 --> 00:10:50,380 Okej. 347 00:10:50,380 --> 00:10:53,900 Så vad var din algoritm eller förfarande för att göra detta, Trevor? 348 00:10:53,900 --> 00:10:56,149 >> TREVOR: Jag bara gick igenom dörrar tills jag hittade en 50. 349 00:10:56,149 --> 00:10:56,940 David J. MALAN: OK. 350 00:10:56,940 --> 00:10:58,150 Utmärkt algoritm. 351 00:10:58,150 --> 00:10:59,540 Så det är bra. 352 00:10:59,540 --> 00:11:03,120 För i själva verket om jag avslöjar vad som är bakom dessa två dörrar, vad 353 00:11:03,120 --> 00:11:06,954 vi hittar här är att Vi har bara slumpmässigt ingång. 354 00:11:06,954 --> 00:11:08,870 Så det var faktiskt så bra som du kan få. 355 00:11:08,870 --> 00:11:12,509 Och i själva verket har du bättre än uttömmande söka hela uppsättningen, 356 00:11:12,509 --> 00:11:15,300 eftersom det skulle ha varit riktigt otur om du hade träffat nummer 357 00:11:15,300 --> 00:11:16,604 50 i allra sista dörren. 358 00:11:16,604 --> 00:11:18,520 Men vad händer om vi istället gav dig ett antagande. 359 00:11:18,520 --> 00:11:20,630 Antar att jag sorterar alla dessa dörrar runt, 360 00:11:20,630 --> 00:11:23,500 så att du har siffror sorteras den här gången, 361 00:11:23,500 --> 00:11:29,730 men den här gången är det faktiskt en different-- den här gången, 362 00:11:29,730 --> 00:11:32,640 det är faktiskt sorterats för dig. 363 00:11:32,640 --> 00:11:35,380 Och nu målet till hands är att slå numret 50. 364 00:11:35,380 --> 00:11:36,090 >> TREVOR: OK. 365 00:11:36,090 --> 00:11:37,670 >> DAVID J. MALAN: Vad är din algoritm kommer att bli? 366 00:11:37,670 --> 00:11:39,628 >> TREVOR: Tja, om det är sorteras, är det antingen gå 367 00:11:39,628 --> 00:11:42,710 att be-- om störst till största, fallande, det blir den första, 368 00:11:42,710 --> 00:11:44,751 eller om det är tvärtom, det kommer att bli den sista. 369 00:11:44,751 --> 00:11:48,897 Så jag ska bara tryck på den här dörren, och sedan bara trycka på den sista dörren. 370 00:11:48,897 --> 00:11:49,980 DAVID J. MALAN: Excellent. 371 00:11:49,980 --> 00:11:50,270 Okej. 372 00:11:50,270 --> 00:11:51,150 Så fann vi nummer 50. 373 00:11:51,150 --> 00:11:52,970 Så snart som du visste de var sorteras, vi 374 00:11:52,970 --> 00:11:55,040 kunde utnyttja detta antagande. 375 00:11:55,040 --> 00:11:57,040 Så de är för mycket som telefonboken exempel. 376 00:11:57,040 --> 00:11:59,540 Så snart du har, även med ett litet problem som detta, 377 00:11:59,540 --> 00:12:02,380 ingångarna försorterade, vi kan faktiskt hitta värdet utan tvekan 378 00:12:02,380 --> 00:12:03,130 mer effektivt. 379 00:12:03,130 --> 00:12:05,800 >> Och jag ville inte berätta om det var sorterade små till stora eller stora till små, 380 00:12:05,800 --> 00:12:08,080 och så det var mycket rimliga att starta vid en eller den andra änden 381 00:12:08,080 --> 00:12:09,750 att faktiskt tycker att målvärdet. 382 00:12:09,750 --> 00:12:11,400 Så tack till Trevor också. 383 00:12:11,400 --> 00:12:13,260 Och jag ska propose-- snyggt gjort. 384 00:12:13,260 --> 00:12:16,960 Vi har en liten klämma, faktiskt, att är bland våra favoritögonblick i CS50, 385 00:12:16,960 --> 00:12:19,700 varigenom ibland dessa demos inte riktigt går enligt plan. 386 00:12:19,700 --> 00:12:22,050 Och faktiskt just nu, jag drog upp fel gränssnitt 387 00:12:22,050 --> 00:12:23,508 som man kan använda pekskärmen. 388 00:12:23,508 --> 00:12:24,660 Så det var mitt fel där. 389 00:12:24,660 --> 00:12:26,600 >> Så det här kommer att leda till nästa års klipp som 390 00:12:26,600 --> 00:12:28,570 varför jag var att klicka på min egen skärm. 391 00:12:28,570 --> 00:12:31,390 Men låt oss ta en snabb titt på vad som hände förra året 392 00:12:31,390 --> 00:12:34,770 med Jay, som kom upp, mycket som Trevor här, frivilligt, 393 00:12:34,770 --> 00:12:39,380 och i denna korta klipp ser du hur samma demo inte helt 394 00:12:39,380 --> 00:12:41,074 avslöjar samma lärdomar. 395 00:12:41,074 --> 00:12:41,740 [VIDEOAVSPELNING] 396 00:12:41,740 --> 00:12:45,360 -Alla Jag vill att du ska göra nu är att hitta för mig, och för oss, 397 00:12:45,360 --> 00:12:51,674 verkligen, antalet 50 ett steg i taget. 398 00:12:51,674 --> 00:12:52,450 >> -Den Nummer 50? 399 00:12:52,450 --> 00:12:53,190 >> -Den Nummer 50. 400 00:12:53,190 --> 00:12:55,356 Och du kan avslöja vad som är bakom vart och ett av dessa dörrar 401 00:12:55,356 --> 00:12:58,540 helt enkelt genom att trycka på den med ett finger. 402 00:12:58,540 --> 00:13:00,910 Jäklar. 403 00:13:00,910 --> 00:13:02,870 >> [Skrattar] 404 00:13:02,870 --> 00:13:03,806 >> [END SPELA] 405 00:13:03,806 --> 00:13:05,430 DAVID J. MALAN: Så det gick väldigt bra. 406 00:13:05,430 --> 00:13:06,796 De var de osorterade dörrar. 407 00:13:06,796 --> 00:13:08,670 Och Jay, naturligtvis, tyckte att det var alltför snabbt. 408 00:13:08,670 --> 00:13:12,910 Trevor gjorde ett mycket bättre jobb i termer av en teachable ögonblick, 409 00:13:12,910 --> 00:13:15,850 så att säga, i år i tar längre tid att hitta den. 410 00:13:15,850 --> 00:13:17,950 Naturligtvis, så vi gav Jay en andra chans, 411 00:13:17,950 --> 00:13:20,320 där vi sorterade dörrarna, precis som vi gjorde för Trevor, 412 00:13:20,320 --> 00:13:22,300 och Trevor gjorde super bra den här gången. 413 00:13:22,300 --> 00:13:26,124 Men Jay gjorde det hälften så snabbt. 414 00:13:26,124 --> 00:13:26,790 [VIDEOAVSPELNING] 415 00:13:26,790 --> 00:13:29,650 -Den Målet är nu att även hitta oss numret 50, 416 00:13:29,650 --> 00:13:33,030 men gör det algoritm, och berätta hur du går om det. 417 00:13:33,030 --> 00:13:33,660 >> -OK. 418 00:13:33,660 --> 00:13:35,604 >> -Och Om du tycker det, hålla dig filmen. 419 00:13:35,604 --> 00:13:37,228 Om du inte hittar det du ge det tillbaka. 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 >> - [OHÖRBAR] OK. 423 00:13:40,800 --> 00:13:46,236 Så jag kommer att kontrollera ändarna först för att avgöra om there's-- Oh. 424 00:13:46,236 --> 00:13:48,646 >> [Applåder] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [END SPELA] 427 00:13:55,729 --> 00:13:56,520 David J. MALAN: OK. 428 00:13:56,520 --> 00:13:59,760 Så sorterings dörrar klart leder till ökad effektivitet. 429 00:13:59,760 --> 00:14:01,680 Och så, dubbelt så snabbt är vad jag menade det. 430 00:14:01,680 --> 00:14:03,270 Och så Jay hade tur båda gångerna. 431 00:14:03,270 --> 00:14:06,685 Och han också hade tur i den sista år, jag beställde vissa Blu-ray-skivor 432 00:14:06,685 --> 00:14:07,560 att faktiskt ge ut. 433 00:14:07,560 --> 00:14:09,768 Jag är ledsen i år, vi hade inte samma, Trevor. 434 00:14:09,768 --> 00:14:11,540 Men ännu bättre var ett par år tillbaka. 435 00:14:11,540 --> 00:14:14,820 Och några av er kanske vet detta karl, Sean, som när han var i CS50, 436 00:14:14,820 --> 00:14:17,780 utmanades med den exakta Samma problem, om än i SD, 437 00:14:17,780 --> 00:14:19,360 eftersom du snart se, tillbaka i dag. 438 00:14:19,360 --> 00:14:22,622 Och du kommer att upptäcka att inte bara gjorde han ta lite längre tid än Jay, 439 00:14:22,622 --> 00:14:25,580 lite längre än Trevor, var det faktiskt denna underbara möjlighet 440 00:14:25,580 --> 00:14:29,820 att engagera sig nästan alla i Publiken a la priset är rätt, att uppmuntra 441 00:14:29,820 --> 00:14:31,889 honom att hitta numret vi sökte. 442 00:14:31,889 --> 00:14:32,930 Låt oss. ta en snabb titt. 443 00:14:32,930 --> 00:14:33,320 >> [VIDEOAVSPELNING] 444 00:14:33,320 --> 00:14:33,820 >> -OK. 445 00:14:33,820 --> 00:14:36,680 Så din uppgift här, Sean, är följande. 446 00:14:36,680 --> 00:14:40,860 Jag har gömt bakom dessa dörrar nummer sju. 447 00:14:40,860 --> 00:14:45,120 Men undanstoppad i en del av dessa dörrar liksom är andra negativa tal. 448 00:14:45,120 --> 00:14:47,500 Och ditt mål är att tänka av denna översta raden av siffror 449 00:14:47,500 --> 00:14:50,390 som bara en array, eller bara sekvens av bitar av papper 450 00:14:50,390 --> 00:14:51,510 med siffror bakom dem. 451 00:14:51,510 --> 00:14:55,540 Och ditt mål är, bara med hjälp toppen array här, hitta mig nummer sju. 452 00:14:55,540 --> 00:14:58,570 Och vi sedan kommer att kritisera hur du går om att göra det. 453 00:14:58,570 --> 00:14:59,070 -Okej. 454 00:14:59,070 --> 00:15:00,850 -Hitta Oss nummer sju, tack. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Nej. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 Fem, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Skrattar] 461 00:15:24,770 --> 00:15:25,910 >> Det är inte en kuggfråga. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 En. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Skrattar] 466 00:15:34,695 --> 00:15:37,861 Vid denna punkt, är din poäng inte mycket bra, så du kan lika gärna fortsätta. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Tre. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Skrattar] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Fortsätt. 473 00:15:47,774 --> 00:15:50,690 Ärligt talat, jag kan inte låta bli att undra vad du ens tänka på, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Skrattar] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Endast den översta raden, så du har tre kvar. 477 00:15:55,020 --> 00:15:56,200 Så hitta mig sju. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Skrattar] 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 Sju. 484 00:16:26,946 --> 00:16:28,780 >> [Applåder] 485 00:16:28,780 --> 00:16:29,426 >> Okej. 486 00:16:29,426 --> 00:16:30,360 >> [END SPELA] 487 00:16:30,360 --> 00:16:31,840 >> DAVID J. MALAN: Så vi kunde titta på dem hela dagen lång. 488 00:16:31,840 --> 00:16:34,090 Och naturligtvis, en del av årets demos kanske 489 00:16:34,090 --> 00:16:36,330 kommer nu att hamna i nästa Årets video också. 490 00:16:36,330 --> 00:16:39,040 Så nu ska vi faktiskt fokusera på de algoritmer 491 00:16:39,040 --> 00:16:42,140 här, och se om vi kan inte Nu börjar formalisera 492 00:16:42,140 --> 00:16:46,650 hur vi kan gå om att få våra data i detta tillstånd att det är sorteras, 493 00:16:46,650 --> 00:16:50,054 så som i slutändan, vi kan faktiskt sök det mer effektivt. 494 00:16:50,054 --> 00:16:52,470 Och även om vi ska att använda ganska små datamängder, 495 00:16:52,470 --> 00:16:54,511 som åtta siffror vi har här på bordet, 496 00:16:54,511 --> 00:16:58,230 i slutändan samma idéer skulle kunna tillämpas till 1.000 ingångar, en miljon ingångar, 497 00:16:58,230 --> 00:17:02,100 4 miljarder ingångar, eftersom algoritmerna kommer att vara i grunden densamma. 498 00:17:02,100 --> 00:17:05,359 >> Och så detta är vår sista möjlighet för volontärer i dag, 499 00:17:05,359 --> 00:17:09,790 men kanske den mest engagerade en, som vi behöver åtta frivilliga 500 00:17:09,790 --> 00:17:12,960 att komma upp och gå oss genom processen att sortera vad som kommer snart 501 00:17:12,960 --> 00:17:15,212 vara på dessa notställ här. 502 00:17:15,212 --> 00:17:16,170 Låt mig börja tillbaka hit. 503 00:17:16,170 --> 00:17:19,692 >> Så en i turquoise-- grönt är det? 504 00:17:19,692 --> 00:17:21,130 Är du begår? 505 00:17:21,130 --> 00:17:21,630 Två. 506 00:17:21,630 --> 00:17:23,069 Kom ner. 507 00:17:23,069 --> 00:17:23,569 OK. 508 00:17:23,569 --> 00:17:24,420 Tre. 509 00:17:24,420 --> 00:17:25,400 Fyra. 510 00:17:25,400 --> 00:17:27,247 Låt mig-- OK, fem. 511 00:17:27,247 --> 00:17:28,830 Du är nominerad av din vän. 512 00:17:28,830 --> 00:17:31,340 Sex, sju och åtta. 513 00:17:31,340 --> 00:17:32,130 Kom upp. 514 00:17:32,130 --> 00:17:32,630 Okej. 515 00:17:32,630 --> 00:17:33,190 Tack så mycket. 516 00:17:33,190 --> 00:17:33,689 Kom upp. 517 00:17:33,689 --> 00:17:34,790 Kom upp. 518 00:17:34,790 --> 00:17:35,330 >> Okej. 519 00:17:35,330 --> 00:17:38,890 Så vad vi har här-- och detta är bland de mer besvärliga sådana, 520 00:17:38,890 --> 00:17:42,390 eftersom detta kommer att kräva att du humor mig bara lite tid. 521 00:17:42,390 --> 00:17:43,442 Du ska vara nummer ett. 522 00:17:43,442 --> 00:17:44,150 Vad heter du? 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 Vad heter du? 527 00:17:46,800 --> 00:17:47,140 >> JOSEPH: Joseph. 528 00:17:47,140 --> 00:17:49,190 >> DAVID J. MALAN: Joseph, du är nummer två. 529 00:17:49,190 --> 00:17:52,260 >> Serena: Serena, nummer tre. 530 00:17:52,260 --> 00:17:53,722 Stefan, nummer fyra. 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 fem. 533 00:17:57,548 --> 00:17:58,452 [OHÖRBAR] 534 00:17:58,452 --> 00:17:59,618 David J. MALAN: [OHÖRBAR]. 535 00:17:59,618 --> 00:18:00,391 David, nummer sex. 536 00:18:00,391 --> 00:18:00,890 MATT: Matt. 537 00:18:00,890 --> 00:18:02,160 DAVID J. MALAN: Matt nummer sju. 538 00:18:02,160 --> 00:18:02,850 Och? 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 åtta. 541 00:18:04,470 --> 00:18:04,970 Okej. 542 00:18:04,970 --> 00:18:06,510 Om du could-- hoppsan. 543 00:18:06,510 --> 00:18:08,820 Om du allt, som din första utmaningen, det 544 00:18:08,820 --> 00:18:10,820 är åtta notställ här inför publiken. 545 00:18:10,820 --> 00:18:14,200 Om du kan sätta dina siffror på dessa notställ på ett sådant sätt 546 00:18:14,200 --> 00:18:16,560 att de ställer upp med samma siffror på tavlan. 547 00:18:16,560 --> 00:18:19,560 Så gör er ser ut att genom sätta dina nummer på dessa musik 548 00:18:19,560 --> 00:18:21,960 står här. 549 00:18:21,960 --> 00:18:25,980 Utmärkt hittills. 550 00:18:25,980 --> 00:18:26,600 >> Utmärkt. 551 00:18:26,600 --> 00:18:26,890 OK. 552 00:18:26,890 --> 00:18:29,556 Så nu ska vi be fråga i ett par olika sätt. 553 00:18:29,556 --> 00:18:31,610 Hur kan vi gå om sortering dessa folks här? 554 00:18:31,610 --> 00:18:34,500 Eftersom vi hade några metoder tidigare, där vi var 555 00:18:34,500 --> 00:18:36,360 typ av att göra två olika skopor. 556 00:18:36,360 --> 00:18:38,842 Och sedan var vi i allmänhet aktualiserat saker tillsammans. 557 00:18:38,842 --> 00:18:41,050 Så snart vi såg två siffror som tillhörde tillsammans, 558 00:18:41,050 --> 00:18:41,975 vi sätta ihop dem. 559 00:18:41,975 --> 00:18:43,350 Två bokstäver som hör ihop. 560 00:18:43,350 --> 00:18:45,058 >> Men låt oss se om vi kan inte formalisera detta, 561 00:18:45,058 --> 00:18:48,044 så att vi i slutändan har vissa pseudo-kod du vill, 562 00:18:48,044 --> 00:18:49,710 med vilken du kan lösa dessa problem. 563 00:18:49,710 --> 00:18:51,870 Så nu, jag tittar ut på dessa siffror här. 564 00:18:51,870 --> 00:18:55,030 Och jag ser en massa misstag. 565 00:18:55,030 --> 00:18:57,750 I slutändan, jag vill ha en på vänster och åtta på höger sida. 566 00:18:57,750 --> 00:19:00,650 >> Och så jag tittar på dessa två, fyra och två. 567 00:19:00,650 --> 00:19:02,930 Och vad är problemet, naturligtvis? 568 00:19:02,930 --> 00:19:04,261 Yeah. 569 00:19:04,261 --> 00:19:04,760 So. 570 00:19:04,760 --> 00:19:07,160 Två uppenbarligen kommer före fyra, så att du vet vad? 571 00:19:07,160 --> 00:19:10,210 Låt mig först ta en girig strategi om ni så vill, likt problem 572 00:19:10,210 --> 00:19:13,790 ställa en-- om du minns från Standard Edition Problem Set One, 573 00:19:13,790 --> 00:19:16,820 där jag bara lokalt lösa problemet det är just här framför mig 574 00:19:16,820 --> 00:19:17,690 och se vart det leder mig. 575 00:19:17,690 --> 00:19:17,870 >> OK. 576 00:19:17,870 --> 00:19:20,161 Så två och fyra, låt mig gå framåt och bara byta ni två. 577 00:19:20,161 --> 00:19:22,400 Om du fysiskt kan flytta er och dina papper, 578 00:19:22,400 --> 00:19:25,040 Jag verkar ha fått lista i ett bättre tillstånd. 579 00:19:25,040 --> 00:19:26,330 >> Nu, de är bra. 580 00:19:26,330 --> 00:19:28,480 Jag kommer att gå vidare, fyra och sex, ser bra ut. 581 00:19:28,480 --> 00:19:29,110 Inget problem. 582 00:19:29,110 --> 00:19:30,440 Sex och åtta, OK. 583 00:19:30,440 --> 00:19:31,860 Åtta och en, ett annat problem. 584 00:19:31,860 --> 00:19:34,750 För vad är sant om åtta och en? 585 00:19:34,750 --> 00:19:36,990 Man kommer före åtta, och så vad ska vi göra? 586 00:19:36,990 --> 00:19:38,090 Låt oss byta dessa två. 587 00:19:38,090 --> 00:19:39,316 En och åtta. 588 00:19:39,316 --> 00:19:40,690 Och nu kommer jag att fortsätta. 589 00:19:40,690 --> 00:19:42,030 Jag kommer att hålla blicken riktad framåt. 590 00:19:42,030 --> 00:19:42,840 Och låt oss se vad som händer. 591 00:19:42,840 --> 00:19:44,680 Åtta och tre, Naturligtvis i ordning. 592 00:19:44,680 --> 00:19:45,815 Låt oss swap. 593 00:19:45,815 --> 00:19:46,940 Åtta och sju, naturligtvis. 594 00:19:46,940 --> 00:19:47,481 Trasig. 595 00:19:47,481 --> 00:19:48,280 Låt oss swap. 596 00:19:48,280 --> 00:19:49,940 Åtta och fem, naturligtvis, låt oss byta. 597 00:19:49,940 --> 00:19:50,560 Okej. 598 00:19:50,560 --> 00:19:51,880 Listan sorteras. 599 00:19:51,880 --> 00:19:53,060 ja? 600 00:19:53,060 --> 00:19:54,280 >> OK, uppenbarligen inte. 601 00:19:54,280 --> 00:19:55,860 Men det är lite bättre, eller hur? 602 00:19:55,860 --> 00:19:57,270 Eftersom meddelande vad som hände. 603 00:19:57,270 --> 00:20:01,749 Varje gång vi utförde en swap, en mindre Antalet slags trängt det sättet, 604 00:20:01,749 --> 00:20:03,790 och ett större antal trängt detta sätt, eller vi ska 605 00:20:03,790 --> 00:20:06,880 börja säga bubblade till vänster eller bubblade till höger. 606 00:20:06,880 --> 00:20:10,080 >> Nu är det inte tillräckligt, eftersom i bästa fall ett antal kanske 607 00:20:10,080 --> 00:20:11,990 har flyttat en fläck framåt, eller i värsta fall, 608 00:20:11,990 --> 00:20:13,880 ett antal kan ha flyttas en fläck ytterligare. 609 00:20:13,880 --> 00:20:16,369 Så du vet vad denna typ av fungerat ganska bra hittills. 610 00:20:16,369 --> 00:20:17,410 Låt mig bara prova igen. 611 00:20:17,410 --> 00:20:18,880 Två och fyra, de är OK. 612 00:20:18,880 --> 00:20:20,180 Fyra och sex, de är OK. 613 00:20:20,180 --> 00:20:21,790 Sex och en, i ordning. 614 00:20:21,790 --> 00:20:23,007 Så låt oss byta er två. 615 00:20:23,007 --> 00:20:25,840 Och nu märker problemets börjar bli lite bättre igen. 616 00:20:25,840 --> 00:20:27,006 Sex och tre, i ordning. 617 00:20:27,006 --> 00:20:28,100 Låt oss byta er två. 618 00:20:28,100 --> 00:20:29,730 Sex och sju, du är bra. 619 00:20:29,730 --> 00:20:32,230 Sju och fem, naturligtvis, i ordning. 620 00:20:32,230 --> 00:20:33,920 Sju och åtta, i ordning. 621 00:20:33,920 --> 00:20:36,470 Och nu kan jag behöva gör detta några gånger. 622 00:20:36,470 --> 00:20:39,830 Och i själva verket tänka själva kanske hur många gånger maximalt 623 00:20:39,830 --> 00:20:41,330 jag kanske måste gå fram och tillbaka? 624 00:20:41,330 --> 00:20:42,390 >> Vi ska återkomma till det. 625 00:20:42,390 --> 00:20:43,700 Så två och fyra är fortfarande OK. 626 00:20:43,700 --> 00:20:44,940 Fyra och en, nix. 627 00:20:44,940 --> 00:20:45,747 Så, låt oss byta. 628 00:20:45,747 --> 00:20:47,830 Och återigen, märker visuellt en är typ av bubblande 629 00:20:47,830 --> 00:20:49,163 till vänster, där det ska vara. 630 00:20:49,163 --> 00:20:50,010 Fyra och tre swap. 631 00:20:50,010 --> 00:20:51,330 Fyra och sex. 632 00:20:51,330 --> 00:20:53,100 Sex och fem swap. 633 00:20:53,100 --> 00:20:53,959 Sex och sju. 634 00:20:53,959 --> 00:20:55,000 Sju och åtta är goda. 635 00:20:55,000 --> 00:20:55,500 >> God. 636 00:20:55,500 --> 00:20:58,460 Vi får ännu bättre. 637 00:20:58,460 --> 00:20:59,130 Så låt oss se. 638 00:20:59,130 --> 00:21:00,940 Nu har vi två och en. 639 00:21:00,940 --> 00:21:02,520 Naturligtvis, byta. 640 00:21:02,520 --> 00:21:07,520 Två och tre, tre och fyra, fyra och fem, sex och sju, sju och åtta. 641 00:21:07,520 --> 00:21:08,020 God. 642 00:21:08,020 --> 00:21:08,730 Och vet du vad? 643 00:21:08,730 --> 00:21:11,190 Eftersom jag gjorde en förändring där, Låt mig göra en sanity check. 644 00:21:11,190 --> 00:21:13,023 Låt mig gå hela vägen tillbaka till början. 645 00:21:13,023 --> 00:21:13,680 OK. 646 00:21:13,680 --> 00:21:14,750 En, two-- Japp, se? 647 00:21:14,750 --> 00:21:15,870 Något var fel. 648 00:21:15,870 --> 00:21:18,420 Tre, fyra, fem, sex, sju, åtta. 649 00:21:18,420 --> 00:21:21,920 Och i denna sista passet, är dig bekväm med min nu 650 00:21:21,920 --> 00:21:23,830 hävdar det sorteras? 651 00:21:23,830 --> 00:21:24,330 OK. 652 00:21:24,330 --> 00:21:25,880 Visuellt är det helt sant. 653 00:21:25,880 --> 00:21:28,410 Men funktionellt, vad gjorde också bara händer 654 00:21:28,410 --> 00:21:31,870 i det sista passet som låter dig bekräfta att denna lista är verkligen 655 00:21:31,870 --> 00:21:32,660 sorterat? 656 00:21:32,660 --> 00:21:34,477 >> Vad har jag gjort eller inte göra det sista passet? 657 00:21:34,477 --> 00:21:35,810 PUBLIK: Det fanns inga förändringar. 658 00:21:35,810 --> 00:21:36,120 DAVID J. MALAN: Förlåt? 659 00:21:36,120 --> 00:21:37,070 PUBLIK: Inga ändringar. 660 00:21:37,070 --> 00:21:38,653 DAVID J. MALAN: Det fanns inga förändringar. 661 00:21:38,653 --> 00:21:41,947 Så det skulle vara dumt av mig att gör samma algoritm igen 662 00:21:41,947 --> 00:21:43,780 om jag inte göra någon ändrar första gången. 663 00:21:43,780 --> 00:21:45,160 Och staten har inte förändrats. 664 00:21:45,160 --> 00:21:47,576 Visst, jag kommer inte att göra någon ändrar andra gången. 665 00:21:47,576 --> 00:21:49,820 Och så är det säkert nu att säga, är listan sorteras. 666 00:21:49,820 --> 00:21:52,069 >> Och faktiskt, är detta nu något som vi ska i allmänhet 667 00:21:52,069 --> 00:21:56,900 samtalsbubbelsortering, varvid parvis, du korrigera misstag igen, 668 00:21:56,900 --> 00:22:00,210 och igen, och igen, och du hålla gå fram och tillbaka, 669 00:22:00,210 --> 00:22:03,370 och fram och tillbaka, tills du gör inga sådana swappar, vid vilken tidpunkt 670 00:22:03,370 --> 00:22:07,089 du kan vara säker på, ja, jag korrigerat alla misstag. 671 00:22:07,089 --> 00:22:08,630 Låt oss återställa och prova en annan strategi. 672 00:22:08,630 --> 00:22:11,590 Om ni kunde gå tillbaka till den ordning du var för en stund sedan, 673 00:22:11,590 --> 00:22:13,780 som såg ut så här. 674 00:22:13,780 --> 00:22:17,640 Nu ska vi ta en strategi a lite mer som testet bok, 675 00:22:17,640 --> 00:22:21,122 där vi var ständigt välja bokstav i alfabetet 676 00:22:21,122 --> 00:22:22,830 att vi typ av ville att ta itu med nästa. 677 00:22:22,830 --> 00:22:26,420 Kanske var det en hög brev, som A, eller en låg bokstaven Z. 678 00:22:26,420 --> 00:22:28,170 >> Så alla är tillbaka i denna ordning. 679 00:22:28,170 --> 00:22:29,800 Och nu vill jag göra det här. 680 00:22:29,800 --> 00:22:34,880 Låt oss se Jag vet att jag har åtta siffror här. 681 00:22:34,880 --> 00:22:37,410 Jag kommer att gå vidare och bara medvetet väljer 682 00:22:37,410 --> 00:22:38,520 de minsta delarna. 683 00:22:38,520 --> 00:22:38,760 Höger? 684 00:22:38,760 --> 00:22:39,801 Detta verkar för intuitiv. 685 00:22:39,801 --> 00:22:42,560 Varför jag inte det minsta element, sätta det där det hör hemma, 686 00:22:42,560 --> 00:22:45,280 sedan få nästa minsta element, sätta det där det hör hemma, och bara upprepa. 687 00:22:45,280 --> 00:22:46,820 >> Eftersom intuitivt, som bör fungera också. 688 00:22:46,820 --> 00:22:48,441 Så fyra, det är ett ganska litet antal. 689 00:22:48,441 --> 00:22:49,940 Jag kommer att komma ihåg när det är. 690 00:22:49,940 --> 00:22:50,523 Vänta en minut. 691 00:22:50,523 --> 00:22:51,577 Två är mindre. 692 00:22:51,577 --> 00:22:53,910 Låt mig nu ihåg var två är, och glömma fyra. 693 00:22:53,910 --> 00:22:55,050 Vi tar hand om det senare. 694 00:22:55,050 --> 00:22:56,460 Sex, jag är inte intresserad. 695 00:22:56,460 --> 00:22:57,810 Åtta, jag är inte intresserad av. 696 00:22:57,810 --> 00:22:59,780 En är mitt nya litet antal. 697 00:22:59,780 --> 00:23:01,470 Så jag kommer att komma ihåg var man är. 698 00:23:01,470 --> 00:23:02,534 Tre, inte intresserad. 699 00:23:02,534 --> 00:23:03,450 Sju, inte intresserad. 700 00:23:03,450 --> 00:23:04,530 Fem, inte intresserad. 701 00:23:04,530 --> 00:23:07,390 >> Så utan att falla av scenen i år, 702 00:23:07,390 --> 00:23:09,890 Jag kommer att ta antal en-- och vad var ditt namn igen? 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 Och om du kunde gå med mig på början av listan, 706 00:23:13,540 --> 00:23:14,870 Låt oss sätta dig där du hör hemma. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- vad heter du? 708 00:23:16,080 --> 00:23:16,650 >> STEFAN: Stefan. 709 00:23:16,650 --> 00:23:18,191 >> DAVID J. MALAN: Stefan är i vägen. 710 00:23:18,191 --> 00:23:23,490 Så innan Stefan löser detta problem, vad ska vi göra? 711 00:23:23,490 --> 00:23:25,412 Vad gör vi med Stefan? 712 00:23:25,412 --> 00:23:27,269 >> PUBLIK: [OHÖRBAR]. 713 00:23:27,269 --> 00:23:28,060 David J. MALAN: OK. 714 00:23:28,060 --> 00:23:28,850 Så vi kunde göra det. 715 00:23:28,850 --> 00:23:31,730 Vi kunde sorts ta Stefan och hans fyra, och bara lägga den i en variabel 716 00:23:31,730 --> 00:23:33,530 och hålla fast vid det för viss tid, 717 00:23:33,530 --> 00:23:35,220 vilket gör utrymme för nummer ett. 718 00:23:35,220 --> 00:23:36,280 Och det är inte dåligt. 719 00:23:36,280 --> 00:23:39,270 Jag skulle kunna föreslå, varför inte vi bara sätta Stefan här? 720 00:23:39,270 --> 00:23:41,610 Varför kan detta strida mot ett av de idéer vi började 721 00:23:41,610 --> 00:23:44,830 talar om förra gången, förra veckan? 722 00:23:44,830 --> 00:23:45,330 Yeah? 723 00:23:45,330 --> 00:23:45,740 >> PUBLIK: [OHÖRBAR]. 724 00:23:45,740 --> 00:23:46,860 >> DAVID J. MALAN: Det finns inget index för det. 725 00:23:46,860 --> 00:23:49,735 Om du tänker på detta, faktiskt, som en array, är detta som negativt, 726 00:23:49,735 --> 00:23:52,900 så det finns inget minne faktiskt här om detta verkligen är en array, 727 00:23:52,900 --> 00:23:55,090 som vi förklarade förra veckan i föreläsningen. 728 00:23:55,090 --> 00:23:56,250 Så vi ska inte göra det. 729 00:23:56,250 --> 00:23:57,340 Vi kan förvara den i en variabel. 730 00:23:57,340 --> 00:23:57,820 >> Eller vet du vad? 731 00:23:57,820 --> 00:23:59,153 Jag hörde någon annan föreslå det. 732 00:23:59,153 --> 00:24:01,020 Vad kan vi göra med Stefan? 733 00:24:01,020 --> 00:24:03,770 Varför inte vi bara vräka honom och satte honom där nummer ett var. 734 00:24:03,770 --> 00:24:05,170 Så om du vill gå dit. 735 00:24:05,170 --> 00:24:07,300 Och faktiskt, är detta en ganska bra lösning. 736 00:24:07,300 --> 00:24:10,480 Nu å ena sidan, jag har typ av gjort problemet värre. 737 00:24:10,480 --> 00:24:13,650 Fyra är nu längre bort varifrån det ska vara. 738 00:24:13,650 --> 00:24:14,900 Det bör vara mot mitten. 739 00:24:14,900 --> 00:24:16,100 >> Men vet du vad? 740 00:24:16,100 --> 00:24:17,630 Det kunde ha varit otur. 741 00:24:17,630 --> 00:24:18,822 Kanske nummer åtta var här. 742 00:24:18,822 --> 00:24:20,530 Och så kanske vi skulle har fått tur, 743 00:24:20,530 --> 00:24:22,460 och sköt åtta närmare slutet. 744 00:24:22,460 --> 00:24:24,710 Så i slutet av dagen, det slags alla jämnar ut. 745 00:24:24,710 --> 00:24:26,085 Vi behöver inte bry sig om fyra. 746 00:24:26,085 --> 00:24:29,400 Allt jag bryr mig om just nu är välja det minsta elementet. 747 00:24:29,400 --> 00:24:32,030 >> Och nu, vad jag ska göra är att glömma nummer ett 748 00:24:32,030 --> 00:24:35,160 permanent, eftersom jag vet att Listan bakom mig nu sorteras. 749 00:24:35,160 --> 00:24:36,720 Så min lista var tidigare storlek åtta. 750 00:24:36,720 --> 00:24:37,720 Nu är det storlek sju. 751 00:24:37,720 --> 00:24:40,340 Så mitt problem är att få mindre, om än linjärt. 752 00:24:40,340 --> 00:24:43,022 Så nu kommer jag att välja nuvarande minsta elementet, två. 753 00:24:43,022 --> 00:24:46,520 Sex, åtta, fyra, tre, sju, fem. 754 00:24:46,520 --> 00:24:47,770 Det var det minsta elementet. 755 00:24:47,770 --> 00:24:49,416 Så vad jag ska göra with-- Vad var ditt namn igen? 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 Vi kommer att lämna Josef på plats. 759 00:24:52,000 --> 00:24:54,842 Nu, jag ska låtsas att dessa killar är-- väl, 760 00:24:54,842 --> 00:24:56,550 Jag vet att dessa två är redan sortering. 761 00:24:56,550 --> 00:24:58,424 Låt oss nu fokusera på resten av listan. 762 00:24:58,424 --> 00:25:00,080 Sex är den nuvarande minsta. 763 00:25:00,080 --> 00:25:01,190 Åtta är större. 764 00:25:01,190 --> 00:25:02,970 Fyra är nu aktuell minsta. 765 00:25:02,970 --> 00:25:04,762 Tre är nu den nuvarande minsta. 766 00:25:04,762 --> 00:25:07,720 Och så nu kommer jag att välja tre, som är-- vad heter du igen? 767 00:25:07,720 --> 00:25:08,190 Serena: Serena. 768 00:25:08,190 --> 00:25:10,620 DAVID J. MALAN: Serena, om du kunde ta ditt nummer och swap with-- 769 00:25:10,620 --> 00:25:11,550 Kalsang: kalsang. 770 00:25:11,550 --> 00:25:12,940 David J. MALAN: kalsang. 771 00:25:12,940 --> 00:25:15,220 Kom tillbaka, och vi är kommer att byta dem två. 772 00:25:15,220 --> 00:25:17,360 Och nu, låt oss sätta detta på autopilot. 773 00:25:17,360 --> 00:25:21,589 Jag ska gå och lämna det till er killar att välja nästa minsta beståndsdel. 774 00:25:21,589 --> 00:25:22,380 Dun, dun, dun, dun. 775 00:25:22,380 --> 00:25:24,560 Nummer fyra, vad ska du göra? 776 00:25:24,560 --> 00:25:26,261 Utmärkt. 777 00:25:26,261 --> 00:25:27,760 Nu, jag kommer att göra en annan passera. 778 00:25:27,760 --> 00:25:28,590 Dun, dun, dun, dun. 779 00:25:28,590 --> 00:25:31,465 Jag ser fem är den näst minsta. 780 00:25:31,465 --> 00:25:32,840 Nu ska jag ta en annan pass. 781 00:25:32,840 --> 00:25:33,631 Dun, dun, dun, dun. 782 00:25:33,631 --> 00:25:34,880 Sex är den minsta. 783 00:25:34,880 --> 00:25:35,520 God. 784 00:25:35,520 --> 00:25:36,585 Sju är den minsta. 785 00:25:36,585 --> 00:25:37,085 Ingen förändring. 786 00:25:37,085 --> 00:25:38,630 Åtta är den minsta. 787 00:25:38,630 --> 00:25:39,170 Klar. 788 00:25:39,170 --> 00:25:43,900 >> Så vad vi har just gjort av iterativt välja en del efter den andra 789 00:25:43,900 --> 00:25:47,230 är att genomföra något som vi är kommer att formalisera som val slag. 790 00:25:47,230 --> 00:25:49,120 Och det är kanske till och med enklare att förklara, 791 00:25:49,120 --> 00:25:51,310 att bokstavligen allt du vill göra är att bara hålla 792 00:25:51,310 --> 00:25:54,700 gå fram och tillbaka i listan val, nästa minsta elementet, 793 00:25:54,700 --> 00:25:55,720 tills du är klar. 794 00:25:55,720 --> 00:25:58,650 >> Så det är ännu enklare, kanske intuitivt, än sist. 795 00:25:58,650 --> 00:26:00,020 Låt oss försöka en sista. 796 00:26:00,020 --> 00:26:03,060 Om ni kunde återställa er i följande positioner 797 00:26:03,060 --> 00:26:08,600 en sista gång, låt oss se om vi kan inte nu formalisera ett annat tillvägagångssätt. 798 00:26:08,600 --> 00:26:12,857 I själva verket skulle någon ute vilja föreslå 799 00:26:12,857 --> 00:26:14,440 hur annat vi kan gå om att göra detta? 800 00:26:14,440 --> 00:26:17,439 Utan gungade ut slagord eller sortera svar som redan är kända, 801 00:26:17,439 --> 00:26:19,689 bara intuitivt, vad kan vi göra? 802 00:26:19,689 --> 00:26:21,635 >> PUBLIK: [OHÖRBAR]. 803 00:26:21,635 --> 00:26:22,510 DAVID J. MALAN: Ja. 804 00:26:22,510 --> 00:26:24,620 Så det finns några bra intuition där. 805 00:26:24,620 --> 00:26:28,020 Bra saker tycks hända hittills i datavetenskap när vi delar 806 00:26:28,020 --> 00:26:30,832 och erövra problemet att dela det i hälften och hälften och hälften. 807 00:26:30,832 --> 00:26:32,540 Och så faktiskt, vi kunde börja göra det. 808 00:26:32,540 --> 00:26:35,754 Och faktiskt, det kommer att bli, vi kommer se, en av våra bästa lösningarna ännu. 809 00:26:35,754 --> 00:26:37,420 Men låt oss återkomma till detta inom kort. 810 00:26:37,420 --> 00:26:40,500 I själva verket kommer vi att göra det lite senare i veckan. 811 00:26:40,500 --> 00:26:42,180 Vad kan vi göra för att lösa det här? 812 00:26:42,180 --> 00:26:44,647 Så alla här är i synes slumpmässig ordning. 813 00:26:44,647 --> 00:26:45,230 Du vet vad? 814 00:26:45,230 --> 00:26:48,320 Hellre än att gå fram och tillbaka, fram och tillbaka, fram och tillbaka 815 00:26:48,320 --> 00:26:50,624 varje gång, känns detta som Jag gör en hel del promenader. 816 00:26:50,624 --> 00:26:52,790 Varför jag inte bara börja på början av listan, 817 00:26:52,790 --> 00:26:54,960 och bara sätta fyra där den hör hemma? 818 00:26:54,960 --> 00:26:59,680 Så låt mig för ett ögonblick anta att min lista är endast denna första elementet. 819 00:26:59,680 --> 00:27:04,937 Är fyra sorteras vid denna tidpunkt, om allt jag bryr mig om är allt här? 820 00:27:04,937 --> 00:27:06,520 Detta är en slags trivialt sant, eller hur? 821 00:27:06,520 --> 00:27:10,000 Liksom förteckning ett nummer, och som nummer fyra är uppenbarligen för sortering. 822 00:27:10,000 --> 00:27:13,070 >> Så låt mig bara föreskriva att denna förteckning sortering. 823 00:27:13,070 --> 00:27:15,090 Men nu har jag resten av denna lista. 824 00:27:15,090 --> 00:27:17,240 Så nu, jag möter två. 825 00:27:17,240 --> 00:27:21,690 Var gör två uppenbarligen hör ihop med avseende på fyra? 826 00:27:21,690 --> 00:27:22,580 Före fyra. 827 00:27:22,580 --> 00:27:23,862 Så vad kan jag göra här? 828 00:27:23,862 --> 00:27:24,820 Vad heter du igen? 829 00:27:24,820 --> 00:27:25,090 >> JOSEPH: Joseph. 830 00:27:25,090 --> 00:27:26,030 >> DAVID J. MALAN: Joseph, om du kunde steg tillbaka 831 00:27:26,030 --> 00:27:27,790 för bara en stund med ditt nummer. 832 00:27:27,790 --> 00:27:31,130 Och nu vad ska Stefan göra här? 833 00:27:31,130 --> 00:27:33,720 Låt oss flytta Stefan hit. 834 00:27:33,720 --> 00:27:35,520 Och nu, låt Joseph komma hit. 835 00:27:35,520 --> 00:27:39,660 Och nu, låt mig hävdar att allt här sorteras. 836 00:27:39,660 --> 00:27:42,474 Så, liknande resultat, men en fundamentalt annorlunda tillvägagångssätt. 837 00:27:42,474 --> 00:27:44,140 Jag har inte ens tittat vad som finns där nere. 838 00:27:44,140 --> 00:27:46,310 Jag håller bara ta elementen eftersom de är överlämnades till mig, 839 00:27:46,310 --> 00:27:47,240 och ta itu med dem. 840 00:27:47,240 --> 00:27:48,330 >> Så nu ser jag nummer sex. 841 00:27:48,330 --> 00:27:51,110 Varifrån kommer nummer sex hör? 842 00:27:51,110 --> 00:27:53,250 Vi har två, fyra, sex. 843 00:27:53,250 --> 00:27:54,800 Exakt var hon är just nu. 844 00:27:54,800 --> 00:27:57,750 Så låt oss lämna det ensam, och nu hävdar att denna del av listan 845 00:27:57,750 --> 00:27:58,772 Nu sorteras. 846 00:27:58,772 --> 00:28:01,230 Och så känns det i grunden annorlunda eftersom jag bara 847 00:28:01,230 --> 00:28:05,230 rör sig genom listan här linjärt, och jag aldrig fördubbling tillbaka. 848 00:28:05,230 --> 00:28:05,730 Ja. 849 00:28:05,730 --> 00:28:06,230 Okej. 850 00:28:06,230 --> 00:28:08,190 Så åtta, där ni hör hemma? 851 00:28:08,190 --> 00:28:08,730 Precis här. 852 00:28:08,730 --> 00:28:09,310 Perfekt. 853 00:28:09,310 --> 00:28:10,210 Så nu en. 854 00:28:10,210 --> 00:28:10,900 Hoppsan. 855 00:28:10,900 --> 00:28:13,010 Det känns som det är kommer att bli dyrt. 856 00:28:13,010 --> 00:28:15,690 Nu, i den tidigare algoritmen, Jag bytte folk. 857 00:28:15,690 --> 00:28:18,648 Så jag skulle sätta honom hela vägen början, men sedan flyttade Joseph. 858 00:28:18,648 --> 00:28:21,450 Men om jag flyttar Joseph, nu vad som kommer att vara fel? 859 00:28:21,450 --> 00:28:24,250 >> Nu, jag har typ av undone-- jag har tagit ett steg framåt och sedan 860 00:28:24,250 --> 00:28:26,300 ett steg tillbaka, för nu Joseph skulle vara i ordning. 861 00:28:26,300 --> 00:28:26,830 Så låt oss göra detta. 862 00:28:26,830 --> 00:28:29,150 Om du kunde ta nummer ett och ett steg tillbaka för ett ögonblick. 863 00:28:29,150 --> 00:28:30,490 Hur kan vi put-- vad var ditt namn igen? 864 00:28:30,490 --> 00:28:31,130 >> ANNAN: Annan. 865 00:28:31,130 --> 00:28:32,610 >> DAVID J. MALAN: Annan på plats? 866 00:28:32,610 --> 00:28:36,091 Vad behöver hända med respekt till två, fyra, sex och åtta? 867 00:28:36,091 --> 00:28:37,570 De behöver alla att skifta. 868 00:28:37,570 --> 00:28:42,590 Så om åtta vill flytta först, sedan sex, sedan fyra, sedan två. 869 00:28:42,590 --> 00:28:45,380 Och sedan Annan, om du skulle vilja komma in här, bra. 870 00:28:45,380 --> 00:28:47,760 Men här, vi har bara sorts betalat ett pris 871 00:28:47,760 --> 00:28:49,510 vid en annan punkt i algoritmen. 872 00:28:49,510 --> 00:28:52,550 Medan förra gången med val sortera och även bubbelsortering, 873 00:28:52,550 --> 00:28:54,700 Jag går tillbaka och framåt, fram och tillbaka, 874 00:28:54,700 --> 00:28:58,360 vilket säkerligen är att lägga upp tidsmässigt, och bokstavligen stegvis. 875 00:28:58,360 --> 00:29:00,660 >> Insättningssortering, först anblicken ser ut som det är 876 00:29:00,660 --> 00:29:05,150 super smartare, eftersom jag bara går långsamt, små förbättringar, 877 00:29:05,150 --> 00:29:07,120 men jag tänker inte detta fram och tillbaka. 878 00:29:07,120 --> 00:29:09,410 Men om någon är verkligen out of order, meddelande 879 00:29:09,410 --> 00:29:10,840 allt arbete jag var bara tvungen att göra. 880 00:29:10,840 --> 00:29:14,750 Jag var tvungen att flytta hälften av listan bara för att göra plats för nummer ett. 881 00:29:14,750 --> 00:29:16,790 Så det är samma belopp arbete hittills det 882 00:29:16,790 --> 00:29:18,690 känns, bara en annan typ av arbete. 883 00:29:18,690 --> 00:29:19,370 >> Låt oss fortsätta. 884 00:29:19,370 --> 00:29:22,657 Så nu vet vi att alla mellan en och åtta sorteras. 885 00:29:22,657 --> 00:29:23,740 Här har jag nummer tre. 886 00:29:23,740 --> 00:29:25,864 Om du gillar att plocka upp nummer tre, ett steg tillbaka ett. 887 00:29:25,864 --> 00:29:28,260 Och vad gör ni behöver göra? 888 00:29:28,260 --> 00:29:28,760 Japp. 889 00:29:28,760 --> 00:29:33,070 Så det är en annan, två, tre steg. 890 00:29:33,070 --> 00:29:36,010 Tre tidsenheter som bara kostar mig, så att tre kan nu passa. 891 00:29:36,010 --> 00:29:37,460 Slutligen sju. 892 00:29:37,460 --> 00:29:39,730 >> Låt oss gå vidare och ha du tar ett steg tillbaka. 893 00:29:39,730 --> 00:29:42,780 Detta kommer bara att kosta oss en tidsenhet, men det är OK. 894 00:29:42,780 --> 00:29:44,170 Och nu, fem kommer att vara lite dyrare. 895 00:29:44,170 --> 00:29:45,340 Om du vill ta ett steg tillbaka. 896 00:29:45,340 --> 00:29:48,380 Vi måste gå åtta, och sju och sex. 897 00:29:48,380 --> 00:29:50,749 Och då alla nu sorteras. 898 00:29:50,749 --> 00:29:52,290 Så en stor hand till våra volontärer här. 899 00:29:52,290 --> 00:29:53,554 Tack så mycket. 900 00:29:53,554 --> 00:29:56,220 >> [Applåder] 901 00:29:56,220 --> 00:29:56,860 >> Tack alla ni. 902 00:29:56,860 --> 00:29:57,520 Tack alla ni. 903 00:29:57,520 --> 00:30:02,940 Så låt oss se nu hur kostsam allt detta var. 904 00:30:02,940 --> 00:30:06,210 Låt oss betrakta kanske enklaste av dessa, bubbelsortering. 905 00:30:06,210 --> 00:30:09,950 Och jag säger enklaste, bara för att Du kan lösa det girigt genom att bara 906 00:30:09,950 --> 00:30:11,660 åtgärda den parvisa problem här. 907 00:30:11,660 --> 00:30:13,720 Fäst den parvisa problemet här, igen och igen 908 00:30:13,720 --> 00:30:17,680 och igen, upprepa så många gånger som du faktiskt behöver. 909 00:30:17,680 --> 00:30:21,050 >> Så visar det sig att med en bubbelsortering, bra, 910 00:30:21,050 --> 00:30:25,820 hur många steg måste jag ta på det första passet av den algoritm? 911 00:30:25,820 --> 00:30:30,850 Jag kanske take-- låt oss see-- en, två, tre, fyra, fem, sex, sju. 912 00:30:30,850 --> 00:30:32,190 Och det finns åtta element här. 913 00:30:32,190 --> 00:30:35,280 Så det är som n minus 1 steg till får från början av listan 914 00:30:35,280 --> 00:30:36,380 till slutet av listan. 915 00:30:36,380 --> 00:30:41,350 >> Men med val sort, minns att jag är välja de element och om igen 916 00:30:41,350 --> 00:30:44,590 och återigen det är minsta, Jag sätter den på plats, 917 00:30:44,590 --> 00:30:46,616 men då är jag inte titta bakom mig igen. 918 00:30:46,616 --> 00:30:49,490 Så jag tycker det är lite mer tydlig då den första gången, kanske jag 919 00:30:49,490 --> 00:30:52,680 måste vidta alla n minus 1 steg att hitta det minsta elementet. 920 00:30:52,680 --> 00:30:55,920 Då ska jag sätta dem på plats, och jag vräka vem var här tidigare. 921 00:30:55,920 --> 00:30:57,500 >> Men då jag inte behöver hålla tittar på detta element, 922 00:30:57,500 --> 00:30:59,040 eftersom jag vet att det är redan den minsta. 923 00:30:59,040 --> 00:31:01,581 Så nu kan jag titta på bara sju element, sedan sex element, 924 00:31:01,581 --> 00:31:03,290 sedan fem elementen, sedan fyra element. 925 00:31:03,290 --> 00:31:06,900 Och så matematiskt, om n är antalet element eller siffror 926 00:31:06,900 --> 00:31:11,990 att vi började med, kan ni tänka er att detta är samma som n minus 1, 927 00:31:11,990 --> 00:31:14,250 plus n minus 2 steg, plus n minus 3 steg, 928 00:31:14,250 --> 00:31:16,780 plus n minus 4 steg, alla ända ner till bara ett steg. 929 00:31:16,780 --> 00:31:18,160 Och jag är på min sista personen. 930 00:31:18,160 --> 00:31:20,650 >> Och om ni minns att en hel del av statistik böcker eller matematiska böcker 931 00:31:20,650 --> 00:31:24,730 har dessa formler på inbundna tillbaka eller framför dem, 932 00:31:24,730 --> 00:31:27,690 det visar sig att denna serie kan uttryckas enklare 933 00:31:27,690 --> 00:31:28,857 som n gånger n minus 1 över 2. 934 00:31:28,857 --> 00:31:31,273 Och det är bra om det inte i spetsen för ditt sinne. 935 00:31:31,273 --> 00:31:32,420 Men det är sant. 936 00:31:32,420 --> 00:31:34,449 Det är bara ett enklare sätt att skriva det. 937 00:31:34,449 --> 00:31:36,240 Och sedan om du tror tillbaka till skolan, 938 00:31:36,240 --> 00:31:38,698 när du bara börja multiplicera saker, detta naturligtvis, 939 00:31:38,698 --> 00:31:41,820 bara n kvadrat minus n dividerat med två. 940 00:31:41,820 --> 00:31:44,772 Allt jag har gjort är att expandera uttrycken där. 941 00:31:44,772 --> 00:31:46,730 Och så låt oss skriva detta lite annorlunda. 942 00:31:46,730 --> 00:31:49,780 Det är n kvadrat delat med 2 minus n / 2. 943 00:31:49,780 --> 00:31:53,270 >> Så återigen, jag är bara slags tillämpa vissa aritmetiska regler där. 944 00:31:53,270 --> 00:31:57,140 Men märker nu att den största termen i detta uttryck, så att säga, 945 00:31:57,140 --> 00:31:58,540 är att n i kvadrat. 946 00:31:58,540 --> 00:32:02,910 Så ja, det är n kvadrat dividerat med två, minus n / 2. 947 00:32:02,910 --> 00:32:05,080 >> Men generellt, om n är kommer att bli en stor värde, 948 00:32:05,080 --> 00:32:08,740 Jag kommer att hävda att n kvadrat kommer att vara den dominerande faktorn. 949 00:32:08,740 --> 00:32:10,490 Det är bara kommer att bli en större bidragsgivare 950 00:32:10,490 --> 00:32:12,877 till det antal steg än n / 2. 951 00:32:12,877 --> 00:32:13,960 Så vad menar jag med det? 952 00:32:13,960 --> 00:32:16,795 Låt oss försöka ett enkelt exempel, även men matten blir lite stor. 953 00:32:16,795 --> 00:32:20,210 >> Så antar att vi hade 1 miljon människor på scen, eller 1 miljon saker 954 00:32:20,210 --> 00:32:21,320 att vi vill sortera. 955 00:32:21,320 --> 00:32:23,730 Låt oss ansluta en miljon i just den formeln 956 00:32:23,730 --> 00:32:27,230 för att se hur många steg det tar totalt att sortera en miljon element med hjälp av säg, 957 00:32:27,230 --> 00:32:28,560 urval slag. 958 00:32:28,560 --> 00:32:30,760 >> Så skulle vi ha samma formel som tidigare. 959 00:32:30,760 --> 00:32:34,120 Jag skulle koppla en miljon, så att jag får en miljon kvadrat delat med 2, 960 00:32:34,120 --> 00:32:35,990 minus en miljon dividerat med två. 961 00:32:35,990 --> 00:32:40,180 Om jag gör det matte i förväg Här har vi 500 miljarder 962 00:32:40,180 --> 00:32:47,460 minus 500 tusen, som ger oss 499.999.500.000, 963 00:32:47,460 --> 00:32:49,270 som är ganska stor. 964 00:32:49,270 --> 00:32:54,370 >> I själva verket, om man jämför nu 499 miljarder, 999 miljoner, 965 00:32:54,370 --> 00:33:01,210 500000 mot vår ursprungliga värde, 500 miljarder, det är så jävla nära. 966 00:33:01,210 --> 00:33:06,850 Höger? n kvadrat dividerat med 2 ger oss-- eller snarare n kvadrat delat med 2 967 00:33:06,850 --> 00:33:08,370 gav oss 500 miljarder. 968 00:33:08,370 --> 00:33:13,510 Det är ganska nära till 499.999.500.000, 969 00:33:13,510 --> 00:33:17,970 det vill säga att subtrahera bort 500.000, eller mer generellt, subtrahera bort 970 00:33:17,970 --> 00:33:20,010 n kvadrat, egentligen inte en big deal. 971 00:33:20,010 --> 00:33:22,490 N kvadrat gör dessa siffror växer riktigt snabbt. 972 00:33:22,490 --> 00:33:25,790 >> Nu är det bara viktigt i den mån som vi, som datavetare, 973 00:33:25,790 --> 00:33:29,350 i allmänhet inte kommer att bry sig så mycket om nyanserna i dessa formler 974 00:33:29,350 --> 00:33:31,400 och exakt vad den exakta svar är. 975 00:33:31,400 --> 00:33:33,390 Vi bryr oss bara det, vet du vad? 976 00:33:33,390 --> 00:33:37,810 Vid slutet av dagen, denna formel är i storleksordningen av n kvadrat. 977 00:33:37,810 --> 00:33:39,350 >> Ja, vi dividera med 2 där. 978 00:33:39,350 --> 00:33:41,360 Ja, vi subtrahera bort n minus 2. 979 00:33:41,360 --> 00:33:46,860 Men i slutet av dagen, termen som verkligen skadar oss och kostar oss 980 00:33:46,860 --> 00:33:48,995 en hel del steg är att fyrkantig sikt. 981 00:33:48,995 --> 00:33:51,370 Och så vad datavetare kommer att i allmänhet göra 982 00:33:51,370 --> 00:33:54,160 är ignorera alla de mindre ordningens termer, 983 00:33:54,160 --> 00:33:56,900 och bara titta på det som bidrar mest till kostnaden. 984 00:33:56,900 --> 00:34:00,530 >> Och det är trevligt, eftersom vi kan nu tala mycket större allmän 985 00:34:00,530 --> 00:34:02,470 om algoritmer, och kan jämföra dem. 986 00:34:02,470 --> 00:34:04,550 Och det faktum att jag är med hjälp av denna O är avsiktligt. 987 00:34:04,550 --> 00:34:06,680 När jag säger i storleksordningen av, jag är specifikt 988 00:34:06,680 --> 00:34:09,560 med hänvisning till något kallade stora O. Och stora O 989 00:34:09,560 --> 00:34:14,090 är en uppgift om att en dator forskare använder för att beskriva 990 00:34:14,090 --> 00:34:16,710 en övre gräns på något. 991 00:34:16,710 --> 00:34:21,150 >> Så om ni säger att en algoritm är i stort O n kvadrat, 992 00:34:21,150 --> 00:34:23,380 som jag föreslog bara en stund sedan, innebär att 993 00:34:23,380 --> 00:34:27,710 att när det gäller sin löpning tid eller dess effektivitet, 994 00:34:27,710 --> 00:34:30,090 Det tar i storleksordningen av n kvadrat steg. 995 00:34:30,090 --> 00:34:31,420 Kanske mer, kanske mindre. 996 00:34:31,420 --> 00:34:33,435 Men det är i storleksordningen n kvadrat. 997 00:34:33,435 --> 00:34:34,560 Och det är den övre gränsen. 998 00:34:34,560 --> 00:34:36,530 Det kommer inte att vara mer smärtsamt än så. 999 00:34:36,530 --> 00:34:40,800 Det kommer inte att vara n kubik, eller 2 till n, eller något mycket större. 1000 00:34:40,800 --> 00:34:43,800 Detta är en övre gräns på vad det kostar. 1001 00:34:43,800 --> 00:34:46,150 Så med tanke på att, låt oss överväga några exempel. 1002 00:34:46,150 --> 00:34:49,820 Och detta är bara en ändlig lista mycket vanliga drifttider 1003 00:34:49,820 --> 00:34:52,870 för algoritmer som är tänkt att vara illustrerar några saker vi har 1004 00:34:52,870 --> 00:34:53,600 sett redan. 1005 00:34:53,600 --> 00:34:58,060 >> Så till exempel, i fallet med val Sortera, vad jag påstår här 1006 00:34:58,060 --> 00:35:02,250 är att valet sortera vicepresident tiden är i storleksordningen n i kvadrat. 1007 00:35:02,250 --> 00:35:06,260 I värsta fall kommer jag att ha en hel massa slumptal här. 1008 00:35:06,260 --> 00:35:08,600 Och som vi såg matematiskt, om jag hålla walking 1009 00:35:08,600 --> 00:35:11,310 genom listan genom listan, välja nästa minsta 1010 00:35:11,310 --> 00:35:14,410 elementet och om igen, om jag faktiskt skriva ner alla steg 1011 00:35:14,410 --> 00:35:18,750 Jag tar som jag föreslog formulaically innan det är i storleksordningen n kvadrat 1012 00:35:18,750 --> 00:35:20,370 steg som jag tar. 1013 00:35:20,370 --> 00:35:24,520 >> Och det visar sig att bubblan sortera och insättningssortering 1014 00:35:24,520 --> 00:35:27,370 är lika långsamt i värsta fall. 1015 00:35:27,370 --> 00:35:32,040 Betänk till exempel, insättningssortering, den allra sista algoritm vi behandlat, 1016 00:35:32,040 --> 00:35:35,500 som hade oss titta på elementet, och sedan infoga det där det hör hemma. 1017 00:35:35,500 --> 00:35:38,720 Och sedan vi tittat på nästa element, och satt in den där det hör hemma. 1018 00:35:38,720 --> 00:35:40,990 >> Så överväga bästa möjliga scenario. 1019 00:35:40,990 --> 00:35:45,590 Anta att jag hade mina frivilliga ställer upp bokstavligen som detta, ett till åtta, 1020 00:35:45,590 --> 00:35:47,440 redan sortering. 1021 00:35:47,440 --> 00:35:51,300 Hur många steg är insättningssortering kommer att ta att sortera åtta personer, 1022 00:35:51,300 --> 00:35:55,640 om de anländer på scen ser ut så här? 1023 00:35:55,640 --> 00:35:57,410 >> Åtta människor redan sortering. 1024 00:35:57,410 --> 00:35:58,760 Och jag använder insättningssortering. 1025 00:35:58,760 --> 00:36:02,180 Det sista av algoritmer. 1026 00:36:02,180 --> 00:36:03,640 Nåväl, låt oss reenact riktigt snabbt. 1027 00:36:03,640 --> 00:36:05,504 Så om jag börjar här, jag ser en. 1028 00:36:05,504 --> 00:36:06,420 Var ska man tillhör? 1029 00:36:06,420 --> 00:36:07,730 Det tillhör just här. 1030 00:36:07,730 --> 00:36:08,330 Jag ser två. 1031 00:36:08,330 --> 00:36:09,660 Vart tar två hör? 1032 00:36:09,660 --> 00:36:10,260 Precis här. 1033 00:36:10,260 --> 00:36:10,900 Jag ser tre. 1034 00:36:10,900 --> 00:36:11,920 Vart tar tre tillhör? 1035 00:36:11,920 --> 00:36:12,480 Precis här. 1036 00:36:12,480 --> 00:36:13,100 >> Jag ser fyra. 1037 00:36:13,100 --> 00:36:13,600 Precis här. 1038 00:36:13,600 --> 00:36:15,660 Fem, sex, sju, åtta. 1039 00:36:15,660 --> 00:36:17,320 Det finns ingen anledning att upprepa mig. 1040 00:36:17,320 --> 00:36:21,260 Och i så fall hur många steg är att när det gäller n? 1041 00:36:21,260 --> 00:36:23,870 Det är i storleksordningen n steg, eller hur? N minus 1. 1042 00:36:23,870 --> 00:36:27,567 Men jag tog ett linjärt antal steg, och nu är jag klar. 1043 00:36:27,567 --> 00:36:28,900 Så det är bästa fall, dock. 1044 00:36:28,900 --> 00:36:29,983 Hur är det värsta fall? 1045 00:36:29,983 --> 00:36:32,730 Vilka åtta var borta, och sju var nere, 1046 00:36:32,730 --> 00:36:35,840 och ett och två var över här, så att listan verkligen var omvänd? 1047 00:36:35,840 --> 00:36:38,300 >> Tja, vad händer faktiskt om detta är numret? 1048 00:36:38,300 --> 00:36:41,300 Och vi kommer att göra bara ett par exempel. 1049 00:36:41,300 --> 00:36:49,300 Tänk om, ja, nummer åtta är här, och de number-- hoppsan. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Så vad händer om, ja, antalet åtta är hela vägen hit, 1052 00:36:56,430 --> 00:36:57,790 och jag använder insättningssortering? 1053 00:36:57,790 --> 00:36:58,290 >> OK. 1054 00:36:58,290 --> 00:37:00,280 Jag hävdar just nu är det på plats. 1055 00:37:00,280 --> 00:37:03,152 Men nu, seven-- vart tar sju gå? 1056 00:37:03,152 --> 00:37:04,360 Naturligtvis går det över här. 1057 00:37:04,360 --> 00:37:06,760 Så jag måste flytta åtta över en plats. 1058 00:37:06,760 --> 00:37:08,554 Nu sex, vart tar det vägen? 1059 00:37:08,554 --> 00:37:09,220 Tja, okej. 1060 00:37:09,220 --> 00:37:13,150 Nu måste jag flytta åtta över en plats, och sju över en plats, 1061 00:37:13,150 --> 00:37:14,440 och sedan jag plopp ner sex. 1062 00:37:14,440 --> 00:37:16,870 >> Så första gången det kostar mig en steg för att fixa saker, 1063 00:37:16,870 --> 00:37:18,570 då det kostade mig två steg för att fixa saker. 1064 00:37:18,570 --> 00:37:20,370 Hur många steg är det kommer att vidta för att åtgärda 1065 00:37:20,370 --> 00:37:22,720 saker att sätta fem på rätt plats? 1066 00:37:22,720 --> 00:37:23,340 Tre. 1067 00:37:23,340 --> 00:37:29,520 För nu har jag flytta en, två, tre. 1068 00:37:29,520 --> 00:37:32,430 Hur många steg kommer det att ta att sätta fyra på rätt plats? 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 >> Och så det är matematiskt identisk med vad vi beskrivits för val slag. 1071 00:37:40,260 --> 00:37:42,130 Vi har denna serie det är bara ökar. 1072 00:37:42,130 --> 00:37:45,650 1 plus 2 plus 3 plus 4, eller omvänt, 7 plus 6 1073 00:37:45,650 --> 00:37:52,610 plus 5 plus 4 lägger upp för dagens ändamål till i storleksordningen n kvadrat. 1074 00:37:52,610 --> 00:37:57,640 >> Så låt mig föreskriver också att bubbelsortering är också i n kvadrat. 1075 00:37:57,640 --> 00:38:01,340 Eftersom med bubbelsortering, varje gång jag går igenom listan, 1076 00:38:01,340 --> 00:38:03,100 Jag tar ungefär hur många steg? 1077 00:38:03,100 --> 00:38:06,260 Varje gång jag bokstavligen promenad därifrån till det? 1078 00:38:06,260 --> 00:38:07,960 Ungefär n steg. 1079 00:38:07,960 --> 00:38:12,650 Men hur många gånger kanske jag måste gå igenom listan? 1080 00:38:12,650 --> 00:38:13,920 >> Tja, ungefär n tid. 1081 00:38:13,920 --> 00:38:15,680 Kanske n minus 1, men ungefär n gånger. 1082 00:38:15,680 --> 00:38:16,430 Tja, varför är det? 1083 00:38:16,430 --> 00:38:19,560 Tja, med bubbelsortering, om vi börjar med bubbelsortering, 1084 00:38:19,560 --> 00:38:23,570 med listan i värsta möjliga situation, som återigen är helt 1085 00:38:23,570 --> 00:38:25,550 bakåt, vad som kommer att hända? 1086 00:38:25,550 --> 00:38:28,830 Jag går igenom listan och antal man tillhör hela vägen dit. 1087 00:38:28,830 --> 00:38:33,280 >> Men med bubbelsortering, gör hur långt man gå på min första passagen genom listan? 1088 00:38:33,280 --> 00:38:36,620 Hur många platser skulle bli han närmare till rätt ställe? 1089 00:38:36,620 --> 00:38:37,240 Bara en. 1090 00:38:37,240 --> 00:38:40,281 Så om du typ av anledning genom denna, varje gång genom denna algoritm, 1091 00:38:40,281 --> 00:38:41,880 Davids tar ungefär n steg. 1092 00:38:41,880 --> 00:38:44,940 Men hur många pass genom listan är det 1093 00:38:44,940 --> 00:38:49,060 kommer att ta en bubbla till vänster där det hör hemma? 1094 00:38:49,060 --> 00:38:51,840 >> Han har att röra sig som, n utrymmen på detta sätt. 1095 00:38:51,840 --> 00:38:57,960 Så bara för att göra sorteringen av listan, Jag måste gå fram och tillbaka n gånger. 1096 00:38:57,960 --> 00:39:01,540 Och varje gång jag är tittar på n element. 1097 00:39:01,540 --> 00:39:05,410 Så gör n saker n gånger i storleksordningen n i kvadrat. 1098 00:39:05,410 --> 00:39:07,220 >> Nu får vi se i vissa av shorts som 1099 00:39:07,220 --> 00:39:10,440 är inbäddade i CS50 nästa problem set, ett annat tillvägagångssätt på dessa, 1100 00:39:10,440 --> 00:39:13,490 men för nu, låt oss bara betrakta några andra drifttider, 1101 00:39:13,490 --> 00:39:16,840 särskilt om sorterings som tar lite tid att sjunka in. 1102 00:39:16,840 --> 00:39:21,790 Vad är en algoritm som vi har sett redan som tar i storleksordningen n steg? 1103 00:39:21,790 --> 00:39:27,560 >> Vad ska ta ett linjärt antal steg som vi har sett så här långt? 1104 00:39:27,560 --> 00:39:29,350 Vad är det? 1105 00:39:29,350 --> 00:39:30,480 Telefonen katalogsökning. 1106 00:39:30,480 --> 00:39:31,390 Den första algoritmen. 1107 00:39:31,390 --> 00:39:31,560 Höger? 1108 00:39:31,560 --> 00:39:33,650 Där vi är linjärt söka efter Mike Smith? 1109 00:39:33,650 --> 00:39:34,150 Verkligen. 1110 00:39:34,150 --> 00:39:37,180 Från vecka noll, när jag började vrida en sida i taget, 1111 00:39:37,180 --> 00:39:40,095 och jag sa till och med att det var typ av en linjär känsla algoritm 1112 00:39:40,095 --> 00:39:42,720 och vi hade att bilden på kartong med raka röda linjen 1113 00:39:42,720 --> 00:39:44,678 och den raka gul linje, de som faktiskt var 1114 00:39:44,678 --> 00:39:46,810 algoritmer som är i stort O n. 1115 00:39:46,810 --> 00:39:50,680 >> Eftersom att hitta Mike Smith i en telefon bok n sidor, i värsta fall, 1116 00:39:50,680 --> 00:39:52,422 kan ta mig n steg. 1117 00:39:52,422 --> 00:39:53,630 Vad sägs om att ta närvaro? 1118 00:39:53,630 --> 00:39:55,790 Ett två tre Fyra Fem Sex. 1119 00:39:55,790 --> 00:39:59,420 Vad är körtiden för denna algoritm för att ta närvaro? 1120 00:39:59,420 --> 00:40:03,070 Big O n, eftersom i teorin jag måste peka alla i rummet. 1121 00:40:03,070 --> 00:40:05,861 >> Nu som en sidoreplik, hur är det andra optimering från vecka noll? 1122 00:40:05,861 --> 00:40:08,117 Två, fyra, sex, åtta, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 En datavetare skulle inse, vänta en minut, 1124 00:40:10,200 --> 00:40:12,320 som är i storleksordningen n dividerat med två steg. 1125 00:40:12,320 --> 00:40:12,820 Höger? 1126 00:40:12,820 --> 00:40:14,444 Eftersom jag gör två personer åt gången. 1127 00:40:14,444 --> 00:40:17,015 Men vi ska ignorera de lägre ordningens termer, 1128 00:40:17,015 --> 00:40:19,140 och vi kommer bara att kasta bort klyftan med 2, 1129 00:40:19,140 --> 00:40:21,830 och bara säga, stort O n för den algoritm som också. 1130 00:40:21,830 --> 00:40:22,760 >> Vad sägs om den här? 1131 00:40:22,760 --> 00:40:26,170 Vi ska hoppa över några av dessa, men vad var en algoritm som var loggen av n? 1132 00:40:26,170 --> 00:40:29,900 Det tog ungefär log n steg? 1133 00:40:29,900 --> 00:40:30,870 Den söndra och härska. 1134 00:40:30,870 --> 00:40:31,369 Exakt. 1135 00:40:31,369 --> 00:40:33,900 Liksom telefonboken exemplet i vecka noll och tidigare i dag, 1136 00:40:33,900 --> 00:40:36,191 där vi delat problemet igen och igen och igen. 1137 00:40:36,191 --> 00:40:39,070 Vi drog det på tavlan i veckan noll som en böjd grön linje, 1138 00:40:39,070 --> 00:40:41,460 och vi sade att dagen var det en logaritmisk algoritm. 1139 00:40:41,460 --> 00:40:44,970 >> Och faktiskt, antalet steg det tar att utföra söndra och härska, 1140 00:40:44,970 --> 00:40:48,610 eller binär sökning som vi börjar kalla det, som i telefonboken, 1141 00:40:48,610 --> 00:40:50,680 är i storleksordningen av log och steg. 1142 00:40:50,680 --> 00:40:52,470 Och detta är lite av en konstig en. 1143 00:40:52,470 --> 00:40:54,910 >> Vad tar ett steg, eller mer specifikt 1144 00:40:54,910 --> 00:40:56,240 ett konstant antal steg? 1145 00:40:56,240 --> 00:40:58,865 Kanske är det två, kanske det är tre, men datavetare bara 1146 00:40:58,865 --> 00:41:01,423 förenklas så stor O 1, någon konstant antal steg. 1147 00:41:01,423 --> 00:41:04,256 Vad är något du kunde göra det tar ett konstant antal steg? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Vad är körtiden för klappar? 1150 00:41:10,930 --> 00:41:11,920 Konstant tid. 1151 00:41:11,920 --> 00:41:12,420 Höger? 1152 00:41:12,420 --> 00:41:15,490 Liksom, vad är gångtid göra något som tar bara en 1153 00:41:15,490 --> 00:41:18,570 drift, liksom ut F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Det kan sägas vara konstant tid, såvida mindre hörn fallet med tryck F, 1155 00:41:24,110 --> 00:41:28,260 Vad kan körtiden utskrifts F faktiskt vara? 1156 00:41:28,260 --> 00:41:28,790 Och varför? 1157 00:41:28,790 --> 00:41:30,550 Vad är n mätning i så fall? 1158 00:41:30,550 --> 00:41:32,251 >> PUBLIK: [OHÖRBAR]. 1159 00:41:32,251 --> 00:41:33,250 DAVID J. MALAN: Exakt. 1160 00:41:33,250 --> 00:41:34,900 Antalet tecken Vi vill skriva ut. 1161 00:41:34,900 --> 00:41:36,191 Så det är väldigt sammanhangsberoende. 1162 00:41:36,191 --> 00:41:39,910 Idag har vi fokuserat mycket på bokstäver och siffror här på tavlan. 1163 00:41:39,910 --> 00:41:43,540 Men det kan också vara tecken i en faktisk sträng. 1164 00:41:43,540 --> 00:41:46,420 Så det visar sig att det finns en annan åtgärd som kommer att börja bry sig om, 1165 00:41:46,420 --> 00:41:48,530 och det är motsatsen av stora O, så att säga. 1166 00:41:48,530 --> 00:41:50,120 >> Det är omega notation. 1167 00:41:50,120 --> 00:41:53,380 Medan stora O menar vad är det övre gräns på din gångtid? 1168 00:41:53,380 --> 00:41:55,580 Maximalt, hur mycket tid kanske något att ta? 1169 00:41:55,580 --> 00:41:59,250 Omega-- ledsen detta håller kommer up-- är motsatsen till det, 1170 00:41:59,250 --> 00:42:02,960 varigenom det är en nedre gräns på tid något kan ta. 1171 00:42:02,960 --> 00:42:10,480 >> So. till exempel, vad är en algoritm som tar alltid n kvadrat steg? 1172 00:42:10,480 --> 00:42:15,600 Tja, en av de algoritmer vi har sett idag, i själva verket kan vara det också. 1173 00:42:15,600 --> 00:42:16,720 Urval slag. 1174 00:42:16,720 --> 00:42:18,270 Val sort är ganska dumt. 1175 00:42:18,270 --> 00:42:21,760 Även om algorithm-- ledsen, även Om arrayen är redan sorterade, 1176 00:42:21,760 --> 00:42:24,150 val Sortera kommer att fortsätta att gå igenom listan 1177 00:42:24,150 --> 00:42:28,907 att se till att den har den minsta elementet igen och igen och igen. 1178 00:42:28,907 --> 00:42:31,740 Och även om du människor i Publiken vet att vänta en minut, 1179 00:42:31,740 --> 00:42:33,948 du redan passerat minsta elementet, varvid datorn 1180 00:42:33,948 --> 00:42:37,300 vet inte att tills det ser hela vägen igenom listan. 1181 00:42:37,300 --> 00:42:40,240 På liknande sätt, en lägre gräns som kan också beaktas 1182 00:42:40,240 --> 00:42:42,000 kan vara linjär tid. 1183 00:42:42,000 --> 00:42:48,260 >> Hur lång tid tar det att sort n element i bästa 1184 00:42:48,260 --> 00:42:52,420 fall genom att använda något som bubbelsortering? 1185 00:42:52,420 --> 00:42:54,280 Anta att din lista är redan sortering. 1186 00:42:54,280 --> 00:42:56,696 Vi sade bubbelsortering tar på ordningen n kvadrat steg. 1187 00:42:56,696 --> 00:42:59,640 Men vad händer om det redan sorteras? 1188 00:42:59,640 --> 00:43:02,310 Vad händer om du inser efter en passage genom matrisen 1189 00:43:02,310 --> 00:43:03,540 att du har gjort några swappar? 1190 00:43:03,540 --> 00:43:05,970 Behöver du fortsätta att göra mer passerar? 1191 00:43:05,970 --> 00:43:06,470 >> Nej. 1192 00:43:06,470 --> 00:43:10,340 Så en lägre gräns för bubbelsortering kan sägas vara linjär. 1193 00:43:10,340 --> 00:43:11,830 Omega n. 1194 00:43:11,830 --> 00:43:14,450 Och vi kan titta på andra av dessa också. 1195 00:43:14,450 --> 00:43:17,990 Så låt oss ta en snabb titt på bara en visualisering här 1196 00:43:17,990 --> 00:43:20,790 att se hur dessa utmärker sig. 1197 00:43:20,790 --> 00:43:24,592 Jag kommer att gå här nere i detta sida som är tillgänglig på C50: s hemsida, 1198 00:43:24,592 --> 00:43:27,550 men det kommer att bli jobbigt att få arbeta, eftersom den använder en teknik som kallas 1199 00:43:27,550 --> 00:43:30,560 Java applets, vilket är en till stor del stöds dessa dagar, 1200 00:43:30,560 --> 00:43:32,730 åtminstone genom Chrome och vissa andra. 1201 00:43:32,730 --> 00:43:37,070 >> Och låt mig gå vidare och påskynda detta upp och förklara vad som händer. 1202 00:43:37,070 --> 00:43:40,840 Detta är en demonstration av bubbla sortera, den första algoritmen som vi tittat på. 1203 00:43:40,840 --> 00:43:43,950 Och det är en visualisering av att varje av dessa stänger representerar ett tal. 1204 00:43:43,950 --> 00:43:45,710 Ju större baren, desto större numret. 1205 00:43:45,710 --> 00:43:47,520 Ju mindre baren, desto mindre antal. 1206 00:43:47,520 --> 00:43:50,353 Och vad du kan se visuellt, även även om detta går supersnabbt, 1207 00:43:50,353 --> 00:43:53,699 är att den röda stapeln är som jag, promenader och tillbaka åtgärda problem. 1208 00:43:53,699 --> 00:43:56,740 Du kan se att de större elementen är sannerligen bubblar upp till höger, 1209 00:43:56,740 --> 00:43:59,650 och de mindre elementen bubblar upp till vänster. 1210 00:43:59,650 --> 00:44:01,870 Och här nere, om vi faktiskt titta närmare, 1211 00:44:01,870 --> 00:44:04,330 vi kan faktiskt räkna antal jämförelser och swappar 1212 00:44:04,330 --> 00:44:05,350 som görs. 1213 00:44:05,350 --> 00:44:07,360 >> Men i stället, låt oss titta vid den andra algoritmen 1214 00:44:07,360 --> 00:44:11,240 vi tittat på tidigare med vår volontärer, val Sortera. 1215 00:44:11,240 --> 00:44:13,500 Visuellt har en helt annan effekt. 1216 00:44:13,500 --> 00:44:16,820 Men det är, återigen, mycket intuitivt, i att vi fortsätter att välja nästa mindre 1217 00:44:16,820 --> 00:44:18,660 element, och vi fick en lite tur. 1218 00:44:18,660 --> 00:44:20,110 Det kändes fundamentalt snabbare. 1219 00:44:20,110 --> 00:44:22,840 Men om vi sprang det igen och igen och igen med massor av insatsvaror, 1220 00:44:22,840 --> 00:44:26,680 skulle vi se att det är verkligen fortfarande i stor O n kvadrat. 1221 00:44:26,680 --> 00:44:29,920 >> Låt oss göra en sista här, insättningssortering, 1222 00:44:29,920 --> 00:44:33,180 vilket var den tredje algoritmen vi tittat på, och återkallelse 1223 00:44:33,180 --> 00:44:36,700 att detta en behandlar element som möter dem, 1224 00:44:36,700 --> 00:44:39,290 Men då kanske skift över saker att göra plats, 1225 00:44:39,290 --> 00:44:41,660 infoga element där de hör hemma. 1226 00:44:41,660 --> 00:44:45,330 >> Och även detta slutar ge slutresultatet. Nu alla tre av dem 1227 00:44:45,330 --> 00:44:46,490 kände ganska snabbt. 1228 00:44:46,490 --> 00:44:48,740 Och faktiskt, sprang jag dem på en ganska bra klipp. 1229 00:44:48,740 --> 00:44:52,510 Men i grund och botten, de är alla ganska hemskt, att vara ärlig. 1230 00:44:52,510 --> 00:44:56,960 Alla dessa algoritmer hittills som körs i stora O n kvadrat 1231 00:44:56,960 --> 00:44:59,270 ta en hel del tid att köra i slutet. 1232 00:44:59,270 --> 00:45:01,920 >> Och faktiskt, kan vi se och anser att detta slutligen 1233 00:45:01,920 --> 00:45:04,090 om jag drar upp denna tredje och sista demo. 1234 00:45:04,090 --> 00:45:05,840 Detta är en annan visualisering som händer 1235 00:45:05,840 --> 00:45:08,500 att visa bubbelsortering till vänster, val Sortera i mitten, 1236 00:45:08,500 --> 00:45:13,410 och något, som en av våra handen lyfter tidigare föreslagits, 1237 00:45:13,410 --> 00:45:15,020 merge sort till höger. 1238 00:45:15,020 --> 00:45:16,937 En söndra och härska strategi till höger. 1239 00:45:16,937 --> 00:45:19,520 Och det är i själva verket vad vi är kommer att titta på onsdagen. 1240 00:45:19,520 --> 00:45:21,990 Men låt oss tid dessa att löpa parallellt. 1241 00:45:21,990 --> 00:45:26,765 Det är ungefär lika många element, alla kör på samma gång. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Bubbelsortering vs val sortera vs merge sort. 1244 00:45:34,440 --> 00:45:36,760 >> Nu, de är alla kör i teorin samtidigt. 1245 00:45:36,760 --> 00:45:39,830 Processorn körs på samma hastighet, men du 1246 00:45:39,830 --> 00:45:44,014 kan känna hur tråkigt det är mycket snabbt kommer att bli, 1247 00:45:44,014 --> 00:45:45,930 och hur snabbt när vi injicerar lite vecka 1248 00:45:45,930 --> 00:45:49,330 noll algoritmer kan vi påskynda saker. 1249 00:45:49,330 --> 00:45:51,760 >> Och nu ska vi jämföra dessa i ett sista formen. 1250 00:45:51,760 --> 00:45:55,710 Jag kommer att gå vidare till CS50 hemsida, där 1251 00:45:55,710 --> 00:45:59,020 Vi har denna sista länken för idag, där någon på internet 1252 00:45:59,020 --> 00:46:03,960 vänligen sätta ihop en video som fångar vad olika sortering 1253 00:46:03,960 --> 00:46:07,510 algoritmer låter som. 1254 00:46:07,510 --> 00:46:09,577 Detta är insättningssortering. 1255 00:46:09,577 --> 00:46:12,072 >> [Pipande] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Där du applicera en frekvens baserat på höjden av bar bar. 1258 00:46:16,850 --> 00:46:19,826 Detta är bubbelsortering. 1259 00:46:19,826 --> 00:46:21,822 >> [Warped pipande] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Kommer upp nästa är-- kommande upp nästa är-- val sortera, 1262 00:46:45,774 --> 00:46:48,820 där återigen, vi väljer nästa minsta elementet, 1263 00:46:48,820 --> 00:46:51,820 och vi kan se det växa från vänster till höger. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Merge sort, vår vinnare hittills i dag. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Lägg märke till hur det dela saker i [OHÖRBAR] halv och kvartal. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Gnome sort, som vi inte har talade om, och skapar visuellt 1270 00:47:21,660 --> 00:47:24,450 och audally lite av en olika form och ljud. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Gå fram och tillbaka, städa upp saker. 1273 00:47:30,160 --> 00:47:32,230 Läs också heapsort På den här killen hemsida. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> Och det är allt. 1276 00:47:36,810 --> 00:47:38,210 Vi kommer att se dig nästa gång. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Whooshing OCH MUSIK] 1279 00:47:48,334 --> 00:50:24,839