1 00:00:00,000 --> 00:00:11,100 >> [MUSIC Playing] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: Okay. 3 00:00:11,490 --> 00:00:12,170 Så velkommen tilbage. 4 00:00:12,170 --> 00:00:15,180 Dette er CS50 og er slutningen af ​​uge tre. 5 00:00:15,180 --> 00:00:17,770 >> Så huske i de sidste mange uger, vi har tilbragt en hel del af 6 00:00:17,770 --> 00:00:20,820 tid på C, om programmering, om syntaks. 7 00:00:20,820 --> 00:00:24,680 Og det er helt normalt, hvis du stadig kæmper med Problem Set 2, for at være 8 00:00:24,680 --> 00:00:25,950 banke hovedet mod muren. 9 00:00:25,950 --> 00:00:28,310 Det er kryptisk udseende fejlmeddelelser og bugs, som du 10 00:00:28,310 --> 00:00:29,220 kan ikke helt jagte. 11 00:00:29,220 --> 00:00:32,310 Fordi, forvisset, at på bare et nogle få uger vil du se tilbage på 12 00:00:32,310 --> 00:00:35,930 ting som Cæsar, og [? V-genair,?] måske endda Knæk og 13 00:00:35,930 --> 00:00:40,050 indse, hvor langt du er kommet i en kort periode. 14 00:00:40,050 --> 00:00:43,670 Så hvis det er nogen trøst, hænge der for nu. 15 00:00:43,670 --> 00:00:46,610 >> Men i dag begynder vi at overgangen til ting højere niveau. 16 00:00:46,610 --> 00:00:49,820 Og vi begynder at tage for givet, at jer vide hvordan man programmerer, eller i 17 00:00:49,820 --> 00:00:52,090 mindst en begyndende at komfort niveau. 18 00:00:52,090 --> 00:00:56,520 Og vi vil begynde at overveje, hvordan vi kan gå om at designe programmer mere 19 00:00:56,520 --> 00:00:57,440 effektivt. 20 00:00:57,440 --> 00:01:01,090 Hvordan vi kan gå om at optimere effektiviteten af ​​vores algoritmer, og 21 00:01:01,090 --> 00:01:03,110 generelt løse mere interessante problemer. 22 00:01:03,110 --> 00:01:06,850 Og begynder at tage for givet, at Hvis vi ville, kunne vi kode op i ethvert 23 00:01:06,850 --> 00:01:08,350 af de eksempler, vi har i tankerne. 24 00:01:08,350 --> 00:01:11,430 Så i dag, vi ikke rører tastaturet for enhver form for kode. 25 00:01:11,430 --> 00:01:15,150 Det vil være langt højere niveau, og i sidste ende, om problemløsning. 26 00:01:15,150 --> 00:01:20,490 >> Så for at komme til det punkt, så lad mig foreslå at følgende syv 27 00:01:20,490 --> 00:01:24,290 rektangler repræsenterer syv døre, bag der er en hel bunke af 28 00:01:24,290 --> 00:01:26,340 numre, blandt hvilke er tallet 50. 29 00:01:26,340 --> 00:01:30,470 Lad mig projicere dette på dette skærmen her. 30 00:01:30,470 --> 00:01:36,770 Og foreslår, at vi har brug for en frivillig til at hjælpe med at finde mig et tal foran 31 00:01:36,770 --> 00:01:38,140 Internettet her for at se. 32 00:01:38,140 --> 00:01:40,755 Kom op i pink. 33 00:01:40,755 --> 00:01:43,050 Ok. 34 00:01:43,050 --> 00:01:43,930 Hvad er dit navn? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [uhørlig] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Undskyld? 37 00:01:45,170 --> 00:01:45,860 >> JENNIFER: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. MALAN: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Okay, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Hyggeligt at møde dig. 41 00:01:47,630 --> 00:01:48,370 Kom op. 42 00:01:48,370 --> 00:01:52,430 Så disse her er syv døre, og hvad Jeg vil gerne have dig til at gøre for os her, 43 00:01:52,430 --> 00:01:56,560 foran alle dine klassekammerater, er at finde os nummeret, 50. 44 00:01:56,560 --> 00:02:00,860 For at finde et nummer, du kan peek bag nogen af ​​disse døre ved blot at trykke 45 00:02:00,860 --> 00:02:03,030 på en af ​​dørene, og det vil afsløre sit nummer. 46 00:02:03,030 --> 00:02:06,080 Og lad os se, hvor hurtigt du kan finde os nummeret, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15.. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16.. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50.. 53 00:02:16,530 --> 00:02:17,350 Pænt gjort. 54 00:02:17,350 --> 00:02:18,040 Ok. 55 00:02:18,040 --> 00:02:19,906 Runde af bifald til Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Applaus] 57 00:02:21,530 --> 00:02:22,320 >> Ok. 58 00:02:22,320 --> 00:02:25,254 Så hvad var din strategi for finde nummeret, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Øh, jeg troede måske, hvis - 60 00:02:27,222 --> 00:02:27,714 [Uhørligt] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Giv det et sekund. 63 00:02:29,630 --> 00:02:32,420 Så var din strategi for finde nummeret, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Så jeg bare starte på begynder at se, hvad det første nummer 65 00:02:34,760 --> 00:02:38,590 var og så tænkte jeg, måske hvis de er sorteret, vil jeg bare holde 66 00:02:38,590 --> 00:02:39,970 aflytning højere op? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. MALAN: OK. 68 00:02:40,140 --> 00:02:42,910 Og vi synes at have fundet at være tilfældet. 69 00:02:42,910 --> 00:02:45,670 Selv, lad os skrælle lagene bare en lille smule, og du ønsker at gå 70 00:02:45,670 --> 00:02:47,640 videre og afsløre de andre døre du kunne have valgt? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Åh, kære. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. MALAN: Ah. 74 00:02:53,128 --> 00:02:54,280 >> JENNIFER: Så jeg har lige fået heldig. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: Så du fik heldig. 76 00:02:55,270 --> 00:02:55,710 Ok. 77 00:02:55,710 --> 00:02:56,795 Så ikke dårligt. 78 00:02:56,795 --> 00:02:58,750 Men det er et interessant indsigt, right? 79 00:02:58,750 --> 00:03:01,870 Hvis du antaget, og du fik, ja, lidt heldig der. 80 00:03:01,870 --> 00:03:05,350 Men hvis du antages, at de tal var sorteret, kan du være mere præcis 81 00:03:05,350 --> 00:03:08,750 til, hvordan der påvirkede din adfærd? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Så hvis de blev sorteret, jeg tænkte måske mindste til største. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. MALAN: OK. 84 00:03:11,970 --> 00:03:15,260 >> JENNIFER: Eller hvis det endte med at blive virkelig stor, så største til mindste. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. MALAN: OK. 86 00:03:15,540 --> 00:03:18,170 Så største til mindste, eller mindste til den største. 87 00:03:18,170 --> 00:03:21,990 Men lad mig foreslå antage, at du havde fået uheldig, og antage, at de 88 00:03:21,990 --> 00:03:26,840 blev ikke i virkeligheden, sorteres, hvor mange af disse døre måske du har haft til peek 89 00:03:26,840 --> 00:03:28,590 bagud i det værste tilfælde? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Alle af dem. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Alle af dem. 92 00:03:30,420 --> 00:03:31,740 Så lad os generalisere det som n. 93 00:03:31,740 --> 00:03:34,790 Der sker for at være 7, men lad os mere generelt sige at der er n døre på 94 00:03:34,790 --> 00:03:35,650 skærm her. 95 00:03:35,650 --> 00:03:40,110 Så i værste fald ville du have at se bag 7 døre, eller n døre. 96 00:03:40,110 --> 00:03:44,140 Og så dette virkelig er, det er lidt af held i dag, men det er virkelig en lineær 97 00:03:44,140 --> 00:03:46,440 algoritme slags, selvom du blev slags springe rundt. 98 00:03:46,440 --> 00:03:47,080 Er det fair? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Ja. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Nå, lad mig se, om din strategiændringer, hvis jeg flytter os til 101 00:03:50,000 --> 00:03:52,190 vores andet eksempel her med 7 forskellige døre. 102 00:03:52,190 --> 00:03:55,240 Samme tal, men dette tid, de er sorteret. 103 00:03:55,240 --> 00:03:58,350 Hvad er din strategi her kommer til at være, forsøger at sætte ud af dit sind, hvad 104 00:03:58,350 --> 00:03:59,310 de andre tal blev - 105 00:03:59,310 --> 00:03:59,930 >> JENNIFER: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. MALAN: - tidligere? 107 00:04:02,290 --> 00:04:03,180 >> JENNIFER: Lad os starte med den første. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: Okay. 109 00:04:03,540 --> 00:04:05,190 Start med den første. 110 00:04:05,190 --> 00:04:05,960 4.. 111 00:04:05,960 --> 00:04:08,810 Nu hvor du kommer til at gå, og hvorfor? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 er virkelig lille. 113 00:04:10,040 --> 00:04:12,500 Så hvis de er en slags måske mindste til største, skulle det 114 00:04:12,500 --> 00:04:13,290 det dobbelte, og -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. MALAN: OK. 116 00:04:13,670 --> 00:04:15,990 Lad os se, hvor du tror? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Prøv den sidste. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: Meget pænt gjort. 120 00:04:20,880 --> 00:04:21,860 Ok. 121 00:04:21,860 --> 00:04:23,010 >> [Applaus] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Så du rent faktisk gør det grueligt, fordi du er 124 00:04:26,790 --> 00:04:27,700 gør det meget godt. 125 00:04:27,700 --> 00:04:31,150 Hvilket efterlader os i stand til at foretage visse punkter. 126 00:04:31,150 --> 00:04:32,565 Så lad os prøve at rulle tilbage her. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: Meget godt gjort, alligevel. 129 00:04:35,980 --> 00:04:39,060 Så du startede i starten, du så, at det var 4, så du 130 00:04:39,060 --> 00:04:40,240 flyttes til slutningen. 131 00:04:40,240 --> 00:04:42,320 Men formoder du ikke heldig der, og antag 50 132 00:04:42,320 --> 00:04:42,890 var et andet sted. 133 00:04:42,890 --> 00:04:46,190 Hvad dit tredje skridt have været? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Gå tilbage til begyndelsen. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Gå tilbage til begyndelsen. 136 00:04:48,320 --> 00:04:51,320 OK, så du ville have rørt denne dør, som var 8. 137 00:04:51,320 --> 00:04:51,660 Ok. 138 00:04:51,660 --> 00:04:52,650 Så det er ikke 50 år. 139 00:04:52,650 --> 00:04:55,380 Hvor ville du have set det næste? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Hvis jeg ikke gjorde kender de sorteret. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Korrekt. 142 00:04:57,005 --> 00:04:58,490 Tja, hvis du vidste de blev sorteret - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Åh, vidste, ja. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - men du gjorde ikke vide, hvor 50 blev endnu? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Bare fortsæt. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: Okay. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Holde ud. 149 00:05:03,800 --> 00:05:05,270 OK, at jeg kan arbejde med. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Nu, hvis du bare kommer til at holde ud, hvad er din 152 00:05:07,210 --> 00:05:09,680 algoritme overdraget bakkede ind. 153 00:05:09,680 --> 00:05:10,740 >> JENNIFER: Den lineære -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. MALAN: Det er slags lineær. 155 00:05:11,820 --> 00:05:13,480 Men lad mig foreslå, lad mig til at sætte på stedet. 156 00:05:13,480 --> 00:05:14,900 Lad mig opdatere siden. 157 00:05:14,900 --> 00:05:17,120 samme nummer, samme arrangement, samme døre. 158 00:05:17,120 --> 00:05:21,350 Men tænk tilbage til den første dag i klasse, når vi rev en telefonbog i 159 00:05:21,350 --> 00:05:25,480 halvdelen, en slags, og hvad var vores strategi der? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Start ved midten. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. MALAN: OK. 162 00:05:26,690 --> 00:05:27,610 Så starter i midten. 163 00:05:27,610 --> 00:05:28,790 Så lad os gå videre og simulere det. 164 00:05:28,790 --> 00:05:30,720 Start ved midten afslører, at døren. 165 00:05:30,720 --> 00:05:31,660 Så antallet 16. 166 00:05:31,660 --> 00:05:35,290 Så hvad ville den stærke fyr har gjort, der rev telefonbogen i halve, 167 00:05:35,290 --> 00:05:38,450 for at komme til den næste gæt? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Gå i denne halve. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: Og hvorfor til højre? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Hvis de var slags mindste til den største, 50 så skal være 171 00:05:43,900 --> 00:05:44,720 at enden. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Godt. 173 00:05:44,920 --> 00:05:45,390 Fuldstændig rimelig. 174 00:05:45,390 --> 00:05:48,380 Så som en telefonbog, går du til ret i modsætning til venstre, men her 175 00:05:48,380 --> 00:05:49,500 er nøglen takeaway. 176 00:05:49,500 --> 00:05:53,930 Du kan nu smide væk eller rive, halvdelen af ​​dette problem, så du ikke 177 00:05:53,930 --> 00:05:55,970 med 7 døre, men rigtig med kun 3. 178 00:05:55,970 --> 00:05:57,870 Hvilket er omtrent halvdelen af problemets omfang. 179 00:05:57,870 --> 00:05:58,350 Ok. 180 00:05:58,350 --> 00:06:01,890 Så nu, hvad du ville have gøres efter du går ret? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: So 16 er stadig temmelig små, i forhold til 50, så måske jeg vil prøve, 182 00:06:05,870 --> 00:06:06,700 ligesom, denne ene. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: Okay. 184 00:06:07,890 --> 00:06:08,720 42.. 185 00:06:08,720 --> 00:06:10,830 Okay, så nu, hvad er din instinkt fortæller dig? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Jeg kan smide dette og så bare - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. MALAN: OK. 188 00:06:12,360 --> 00:06:14,212 Godt, du kan smide væk den venstre halvdel der. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - pluk denne ene. 190 00:06:14,890 --> 00:06:15,530 >> David J. MALAN: Og den rigtige. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Ja. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Så selvom det er svært at se måske når der er kun 193 00:06:17,820 --> 00:06:21,320 7 døre, så tænk nu, sammenhængen i 194 00:06:21,320 --> 00:06:22,620 algoritme netop anvendt. 195 00:06:22,620 --> 00:06:24,510 I den tidligere sag, har du få heldige, som var stor. 196 00:06:24,510 --> 00:06:26,540 Men du gjorde bruge en heuristisk, Jeg ville sige. 197 00:06:26,540 --> 00:06:29,150 Du brugte slags dine instinkter, og vide det sorteres, hvis det er temmelig 198 00:06:29,150 --> 00:06:31,600 lille i begyndelsen, naturligvis, vi har kom til at gå mere til højre. 199 00:06:31,600 --> 00:06:34,990 Men i en vis forstand, du fik heldig, fordi måske dette var nummer 100, 200 00:06:34,990 --> 00:06:36,220 og måske 50 var mere i midten. 201 00:06:36,220 --> 00:06:37,910 Måske 50 var endda herovre. 202 00:06:37,910 --> 00:06:40,960 >> Men hvad du gjorde lidt anderledes denne gang var, du gjorde det samme 203 00:06:40,960 --> 00:06:42,150 igen og igen. 204 00:06:42,150 --> 00:06:45,310 Og jeg vil hævde, at hvad du lige gjorde, omend påvirket af telefonen 205 00:06:45,310 --> 00:06:48,100 bog eksempel, er noget meget mere algoritmisk og meget 206 00:06:48,100 --> 00:06:49,930 mindre specielle hylstre. 207 00:06:49,930 --> 00:06:51,620 Meget mindre instinktive. 208 00:06:51,620 --> 00:06:57,160 Så i slutningen af ​​dagen, hvordan ville du beskrive effektiviteten af 209 00:06:57,160 --> 00:07:00,530 første algoritme, hvor du gik venstre til højre, versus 210 00:07:00,530 --> 00:07:03,430 anden algoritme her? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Denne ene bør ligesom, måske halvere den tid, eller endnu mere, ja. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, måske endda mere. 213 00:07:07,320 --> 00:07:10,150 Lad os skubbe lidt hårdere på det. 214 00:07:10,150 --> 00:07:13,030 Hvad der virkelig, hvis vi fortsætter dette logik, vi helt sikkert halveret 215 00:07:13,030 --> 00:07:15,830 køretid med denne anden algoritme ved at smide halvdelen af 216 00:07:15,830 --> 00:07:18,470 tal, men hvad gjorde vi den næste iteration, når Jennifer afslørede 217 00:07:18,470 --> 00:07:20,615 det andet nummer? 218 00:07:20,615 --> 00:07:22,830 >> Vi halveret antallet af døre igen. 219 00:07:22,830 --> 00:07:25,270 Og hvad gjorde vi efter det, hvis der var flere døre for at lege med? 220 00:07:25,270 --> 00:07:27,520 Vi ville halvere dem, og igen, og igen og igen. 221 00:07:27,520 --> 00:07:30,420 Og dette var ligesom jer alle stående op på den første uge af 222 00:07:30,420 --> 00:07:33,000 klasse, halvdelen af ​​jer sidder ned, halvt af jer sidder ned, halvdelen af ​​dig 223 00:07:33,000 --> 00:07:35,440 sidder ned, indtil en enlig sjæl stod. 224 00:07:35,440 --> 00:07:39,050 Og vi sagde, at køretiden for at antallet af trin tog det var 225 00:07:39,050 --> 00:07:40,430 på rækkefølgen af ​​hvad? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [uhørlig] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. MALAN: So log base 2 n, eller bare mere simpelt, skal du logge på n. 228 00:07:43,970 --> 00:07:45,060 Så noget logaritmisk. 229 00:07:45,060 --> 00:07:48,380 Og grafen var ikke en lige linje der bare blev værre og værre, det var 230 00:07:48,380 --> 00:07:52,490 denne interessante kurve, der ikke komme så slemt over tid. 231 00:07:52,490 --> 00:07:53,910 Så lad os holde fast i denne idé. 232 00:07:53,910 --> 00:07:54,690 Lad os takke Jennifer. 233 00:07:54,690 --> 00:07:56,150 Tak så meget for at komme videre op. 234 00:07:56,150 --> 00:07:57,400 Og en sek. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Ingen bordlamper dag, men vi har CS50 stress bolde. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: Okay, her. 239 00:08:04,410 --> 00:08:06,545 Tak for at pådrage stress heroppe. 240 00:08:06,545 --> 00:08:07,350 Ok. 241 00:08:07,350 --> 00:08:10,620 Så lad os se om vi kan ikke nu formalisere det en smule mere. 242 00:08:10,620 --> 00:08:14,820 Så igen, hvad vi lige gjorde var set de samme ting, som vi gjorde 243 00:08:14,820 --> 00:08:16,660 i det første uge. 244 00:08:16,660 --> 00:08:23,780 Men i stedet ende med blot en lineær algoritme, som vi afbildet 245 00:08:23,780 --> 00:08:27,210 tidligere som denne lige linje, hvorved hvis vi sætter endnu en dør på 246 00:08:27,210 --> 00:08:29,610 på skærmen, og Jennifer ville har måttet se, potentielt 247 00:08:29,610 --> 00:08:30,600 bag en mere dør. 248 00:08:30,600 --> 00:08:33,490 Hvis vi sætter to flere døre, kan hun have at se bag to døre. 249 00:08:33,490 --> 00:08:35,990 >> Og så var der denne lineære forholdet mellem størrelsen af ​​den 250 00:08:35,990 --> 00:08:39,059 problem på, siger, x-aksen, og den tid det tager at 251 00:08:39,059 --> 00:08:40,440 løse på y. 252 00:08:40,440 --> 00:08:43,330 Men det billede, jeg hentydede til tidligere var denne grønne linje. 253 00:08:43,330 --> 00:08:45,970 Grøn bevidst, fordi det føltes bare bedre. 254 00:08:45,970 --> 00:08:49,790 I teorien, da algoritmen, vi gjorde det med telefonbogen, vi når gjorde det 255 00:08:49,790 --> 00:08:52,420 med jer tælle hinanden, og i det andet tilfælde, hvor Jennifer bare 256 00:08:52,420 --> 00:08:55,250 gjorde det op her, det var en slags af fundamentalt bedre. 257 00:08:55,250 --> 00:08:57,180 Fordi det ikke kun var dobbelt så hurtigt. 258 00:08:57,180 --> 00:08:58,870 Det var ikke engang fire gange så hurtigt. 259 00:08:58,870 --> 00:09:03,290 Det var helt afhængig af, hvad størrelse af input var, hvor mange 260 00:09:03,290 --> 00:09:05,220 skridt det i sidste ende tog. 261 00:09:05,220 --> 00:09:08,040 >> Og så denne simple idé, at vi alle tog for givet med telefonbogen, 262 00:09:08,040 --> 00:09:10,200 kan ligeledes anvendes til noget som dette. 263 00:09:10,200 --> 00:09:12,380 Og det kan være mere afslappet kendt som som du måske 264 00:09:12,380 --> 00:09:13,940 forestille del og hersk. 265 00:09:13,940 --> 00:09:16,390 Ikke ulig hvad vi gjorde, naturligvis, med telefonbogen. 266 00:09:16,390 --> 00:09:18,300 >> Men pseudokode, tilbagekaldelse, var dette. 267 00:09:18,300 --> 00:09:21,800 Så vi vil ikke gøre det igen, men husker den første uge, vi alle stod op 268 00:09:21,800 --> 00:09:25,140 og derefter halvdelen af ​​du sad halvdelen af du sad halvdelen af ​​du sad. 269 00:09:25,140 --> 00:09:29,280 Denne algoritme blev gennemført på en lidt af en snyd måde, idet det 270 00:09:29,280 --> 00:09:32,870 var ikke blot en af ​​mig optælling, fundamentalt, mere effektivt. 271 00:09:32,870 --> 00:09:35,830 I dette tilfælde var jeg udnytte en sekundær ressource. 272 00:09:35,830 --> 00:09:39,470 Sorter af, flere CPU'er, flere hjerner, flere smarte folk i 273 00:09:39,470 --> 00:09:42,740 værelse var at hjælpe mig med at komme fra noget lineær til noget 274 00:09:42,740 --> 00:09:45,190 logaritmisk, fra noget rød til noget grøn. 275 00:09:45,190 --> 00:09:48,650 >> Men i dette tilfælde, kan Jennifer alene fundamentalt forbedre den 276 00:09:48,650 --> 00:09:52,370 udførelsen af ​​hendes første algoritme ved, igen, bare at tænke lidt hårdere. 277 00:09:52,370 --> 00:09:56,650 Og nu, når det drejer sig tid til at gennemføre disse ting, regne ud, 278 00:09:56,650 --> 00:10:00,670 hvilke linjer kode, kan du skrive sådan at du kan gentage dem igen, og 279 00:10:00,670 --> 00:10:03,350 igen og igen, en slags i en looping måde. 280 00:10:03,350 --> 00:10:06,370 Fordi du ikke kommer til at have den luksus, ligesom Jennifer gjorde i første omgang, at 281 00:10:06,370 --> 00:10:10,460 bare have en hel masse hvis'er og sige, Hmm, hvis det første tal er 4, 282 00:10:10,460 --> 00:10:11,800 lad mig hoppe hele vejen til enden. 283 00:10:11,800 --> 00:10:14,180 Ooh, hvis dette antal er for stort, lad mig gå vilkårligt tilbage 284 00:10:14,180 --> 00:10:15,220 til det andet element. 285 00:10:15,220 --> 00:10:18,210 Du vil opdage, at det kommer til at være en masse sværere at formalisere hvad vi mennesker 286 00:10:18,210 --> 00:10:21,270 tager for givet som meget rimelig heuristik, men en computer er kun 287 00:10:21,270 --> 00:10:23,260 kommer til at gøre, hvad du fortæller det at gøre. 288 00:10:23,260 --> 00:10:25,280 >> Nu har dette meget interessant implikationer. 289 00:10:25,280 --> 00:10:29,950 Denne graf slags beregnet til at sortere i overvælde visuelt, men varsel, hvor 290 00:10:29,950 --> 00:10:32,230 er den lige linje i denne graf? 291 00:10:32,230 --> 00:10:35,330 Hvor er den lineære graf som vi kalder n? 292 00:10:35,330 --> 00:10:37,580 Tja, det er en slags mod bunden af dette billede, right? 293 00:10:37,580 --> 00:10:40,500 Så alt, hvad vi har gjort, er vi har slags zoomet til x-aksen og 294 00:10:40,500 --> 00:10:44,780 y-aksen for at forsøge at få en fornemmelse af, hvad andre typer af kurver ligner. 295 00:10:44,780 --> 00:10:47,760 >> Og detaljerne i den matematiske udtryk i dag, vil ikke så 296 00:10:47,760 --> 00:10:52,440 meget, men bemærke, at der er en masse algoritmer, der er langt værre end 297 00:10:52,440 --> 00:10:53,470 noget, der er lineær. 298 00:10:53,470 --> 00:10:55,410 Faktisk kubik n ser temmelig dårlig. 299 00:10:55,410 --> 00:10:58,400 2 til n ser temmelig dårlig. n kvadreret ser temmelig dårlig. 300 00:10:58,400 --> 00:11:01,630 Og vi vil se, hvad nogle af dem kan være i virkeligheden i dag. 301 00:11:01,630 --> 00:11:05,430 Og log n ikke føler så slemt, men bedre end n er log base 2 n. 302 00:11:05,430 --> 00:11:08,080 Men du ved, det ville have været endnu mere fantastisk, hvis Jennifer, eller hvis vi, 303 00:11:08,080 --> 00:11:12,910 den første uge, var kommet op med noget, der er log af log n. 304 00:11:12,910 --> 00:11:15,880 >> Så med andre ord, er der hele denne vifte af mulige løsninger 305 00:11:15,880 --> 00:11:18,570 problemer, men selv her, varsel hvad der kommer til at ske. 306 00:11:18,570 --> 00:11:22,910 Når jeg zoome ud, hvilke af disse kurver vil vise sig at være den absolutte 307 00:11:22,910 --> 00:11:26,630 værste af dem på skærmen nu? 308 00:11:26,630 --> 00:11:28,680 Så n kubik ser temmelig dårlig i øjeblikket. 309 00:11:28,680 --> 00:11:32,470 Men hvis vi zoome ud og se mere af x og y-aksen, som kommer til at 310 00:11:32,470 --> 00:11:34,550 dominere i sidste ende? 311 00:11:34,550 --> 00:11:37,120 Så det faktisk viser sig, at 2 til n, og du kan finde ud af dette ved blot at 312 00:11:37,120 --> 00:11:39,990 tilslutte nogle stadig større numre, og du vil se, at 2 til 313 00:11:39,990 --> 00:11:42,070 n, faktisk bliver større meget hurtigere. 314 00:11:42,070 --> 00:11:45,530 Hvis vi virkelig zoome ud, en 2 til n algoritme absolut stinker. 315 00:11:45,530 --> 00:11:48,170 Jeg mener, dette kommer til at tage ganske lidt tid til 316 00:11:48,170 --> 00:11:49,460 computer til at kværne igennem. 317 00:11:49,460 --> 00:11:52,500 >> Men du vil se over tid, især med kommende problemområder sæt og endda 318 00:11:52,500 --> 00:11:55,600 afgangsprojekter, er dine data sæt får store, okay? 319 00:11:55,600 --> 00:11:58,300 Selv i den første version af Facebook, som antallet af venner og 320 00:11:58,300 --> 00:12:01,840 Antallet af registrerede brugere fik store, du kan sortere telefon det og 321 00:12:01,840 --> 00:12:05,530 gennemføre noget med lineær søgning, eller en meget simpel sortering 322 00:12:05,530 --> 00:12:07,030 algoritme, som vi skal se i dag. 323 00:12:07,030 --> 00:12:09,280 Du er nødt til at begynde at tænke hårdere og hårdere om disse problemer. 324 00:12:09,280 --> 00:12:12,070 Og de typer af problemer steder som Facebook og Google og Microsoft, 325 00:12:12,070 --> 00:12:16,350 , og andre arbejder på er netop disse slags big data slags spørgsmål 326 00:12:16,350 --> 00:12:18,530 stigende i disse dage. 327 00:12:18,530 --> 00:12:18,900 >> Ok. 328 00:12:18,900 --> 00:12:23,800 Så Jennifers succes i denne anden algoritme, helt ærligt, hun gjorde forbavsende 329 00:12:23,800 --> 00:12:26,110 godt første gang, men lad os skrive det som held, så vi 330 00:12:26,110 --> 00:12:27,000 kan gøre dette punkt. 331 00:12:27,000 --> 00:12:30,970 I det andet tilfælde, gearede hun en algoritme, der gentages igen og 332 00:12:30,970 --> 00:12:34,670 igen, men hun tog for givet en vis antagelse, at vi tillod 333 00:12:34,670 --> 00:12:39,370 hende, men hun udnyttede nogle detaljer anden gang, at hun ikke har den 334 00:12:39,370 --> 00:12:39,840 første gang. 335 00:12:39,840 --> 00:12:41,800 Hvilket var hvad? 336 00:12:41,800 --> 00:12:43,050 >> At listen blev sorteret. 337 00:12:43,050 --> 00:12:46,350 Så så snart listen er sorteret, vi hævder, at Jennifer var i stand til at gøre 338 00:12:46,350 --> 00:12:47,480 fundamentalt bedre. 339 00:12:47,480 --> 00:12:51,450 7 døre, ja, er det ikke interessant, men formoder, det er vi 7 millioner døre. 340 00:12:51,450 --> 00:12:54,080 Log n er helt sikkert vil til at udføre meget, meget 341 00:12:54,080 --> 00:12:55,610 hurtigere i det lange løb. 342 00:12:55,610 --> 00:12:58,880 Men hun skulle have døre sorteret for hende. 343 00:12:58,880 --> 00:13:02,320 Nu tog jeg mig den frihed at gøre det i forvejen på computerskærmen 344 00:13:02,320 --> 00:13:05,160 her, men formoder, at Jennifer havde at gøre det selv? 345 00:13:05,160 --> 00:13:10,120 Antag, at dørene pågældende repræsenterede data i en database, eller 346 00:13:10,120 --> 00:13:14,260 venner registreret for Facebook, eller eventuelle web-sider på internettet, der 347 00:13:14,260 --> 00:13:16,880 forskellige hjemmesider muligvis til indeks eller søge over. 348 00:13:16,880 --> 00:13:20,940 >> Antag, at du lige havde et rådata indstillet, og det blev overladt til dig, eller til at 349 00:13:20,940 --> 00:13:23,010 Jennifer at gøre at sortering? 350 00:13:23,010 --> 00:13:26,950 Det snarere, kræver, at vi besvarer spørgsmålet, ja, hvor meget tid 351 00:13:26,950 --> 00:13:31,080 ville have taget Jennifer, eller endda mig, at sortere disse tal i forvejen, så 352 00:13:31,080 --> 00:13:32,680 at hun kunne drage fordel af det? 353 00:13:32,680 --> 00:13:32,880 Right? 354 00:13:32,880 --> 00:13:36,620 Fordi konsekvenserne, selvfølgelig, er hvis det tager mig lang tid at sortere 355 00:13:36,620 --> 00:13:40,800 numrene, hvem dælen bekymrer, at du kan finde en række lignende 50 så hurtigt, 356 00:13:40,800 --> 00:13:44,850 som i Jennifers tilfælde, hvis vi mere end overvældet af mængden af ​​den samlede tid 357 00:13:44,850 --> 00:13:46,920 det tog ved at sortere ting i forvejen? 358 00:13:46,920 --> 00:13:49,320 >> Så lad os se om vi ikke kan det male billedet her. 359 00:13:49,320 --> 00:13:51,370 Jeg har en hel bunke mere stress bolde, hvis det hjælper 360 00:13:51,370 --> 00:13:52,270 bryde isen her. 361 00:13:52,270 --> 00:13:55,690 Og hvis du ikke har noget imod, vi brug syv frivillige - 362 00:13:55,690 --> 00:13:57,060 på, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Så vi behøver ikke at bruge på bordlamper, synes det. 365 00:13:59,250 --> 00:13:59,690 Ok. 366 00:13:59,690 --> 00:14:01,530 Så hvad med jer to i front. 367 00:14:01,530 --> 00:14:04,160 Hvad med dig to fyre i ryggen. 368 00:14:04,160 --> 00:14:04,870 Så det er fire. 369 00:14:04,870 --> 00:14:09,890 Hvad med dig foran fem, seks og syv. 370 00:14:09,890 --> 00:14:10,320 Lige der. 371 00:14:10,320 --> 00:14:13,260 Din vens pege dig ud, så du får præmie. 372 00:14:13,260 --> 00:14:13,700 >> Ok. 373 00:14:13,700 --> 00:14:14,410 Kom op. 374 00:14:14,410 --> 00:14:17,120 Og hvorfor gør vi ikke have dig fyre kom herover. 375 00:14:17,120 --> 00:14:18,960 Jeg har tænkt mig at give dig hver et nummer. 376 00:14:18,960 --> 00:14:22,150 Og gå videre og arrangere jer identisk med, hvad der er 377 00:14:22,150 --> 00:14:25,180 afbildet på skærmen. 378 00:14:25,180 --> 00:14:26,530 >> [Interposing STEMMER] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, undskyld. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Ok. 382 00:14:32,180 --> 00:14:32,750 Nå, her går vi. 383 00:14:32,750 --> 00:14:34,180 Nummer fem. 384 00:14:34,180 --> 00:14:35,136 Nummer seks. 385 00:14:35,136 --> 00:14:37,770 En, to, tre, fire, fem, seks, syv. 386 00:14:37,770 --> 00:14:39,410 Åh, det er akavet. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Jeg vil bare få en -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. MALAN: Good deal. 389 00:14:41,900 --> 00:14:43,130 Ok. 390 00:14:43,130 --> 00:14:44,611 Tak for din deltagelse. 391 00:14:44,611 --> 00:14:47,200 >> [Applaus] 392 00:14:47,200 --> 00:14:48,580 >> OK. 393 00:14:48,580 --> 00:14:48,860 Ok. 394 00:14:48,860 --> 00:14:51,970 Så vi har fire, to, seks, et, tre, syv, fem. 395 00:14:51,970 --> 00:14:56,010 Perfekt, så vi har syv frivillige her der er lige i bredden til 396 00:14:56,010 --> 00:14:57,430 array, vi spiller med tidligere. 397 00:14:57,430 --> 00:14:59,470 Og jeg valgte syv grunde der vil være lige 398 00:14:59,470 --> 00:15:00,840 praktisk i en lille smule. 399 00:15:00,840 --> 00:15:04,400 Og jeg har tænkt mig at foreslå først at vi sortere disse syv frivillige. 400 00:15:04,400 --> 00:15:06,786 Hvis du gerne vil for det første, at sige hej selv. 401 00:15:06,786 --> 00:15:08,970 Da dette vil være en akavede flere minutter. 402 00:15:08,970 --> 00:15:10,370 Indføre selv. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hej, jeg er Grace. 404 00:15:10,980 --> 00:15:14,190 Jeg er sophomore i Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hej. 406 00:15:14,620 --> 00:15:15,620 Jeg Branson. 407 00:15:15,620 --> 00:15:16,920 Jeg er freshman i Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> GABE: Hej. 410 00:15:20,230 --> 00:15:21,040 Jeg er Gabe. 411 00:15:21,040 --> 00:15:22,300 Jeg er junior i Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> NEIL: Jeg er Neil. 414 00:15:25,980 --> 00:15:29,090 Jeg er freshman i Matthews. 415 00:15:29,090 --> 00:15:29,550 >> JASON: Jeg er Jason. 416 00:15:29,550 --> 00:15:32,816 Jeg er freshman i Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Jeg er Mike. 418 00:15:33,700 --> 00:15:37,360 Jeg er freshman i Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Jeg er Jess. 420 00:15:37,990 --> 00:15:40,313 Jeg er sophomore i Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. MALAN: Excellent. 422 00:15:41,300 --> 00:15:41,850 Ok. 423 00:15:41,850 --> 00:15:44,190 Nå, tak til alle vores frivillige her hidtil. 424 00:15:44,190 --> 00:15:47,110 Og udfordringen ved hånden nu går at være at sortere i disse fyre, men så 425 00:15:47,110 --> 00:15:50,250 vi nødt til at tænke lidt hårdt om, hvor effektivt vi faktisk 426 00:15:50,250 --> 00:15:51,110 sorteret dem. 427 00:15:51,110 --> 00:15:52,580 Så lad os først prøve dette. 428 00:15:52,580 --> 00:15:55,970 Du fyre kan se hinandens numre blot ved at placere omkring hjørner. 429 00:15:55,970 --> 00:15:59,380 Gå videre og tage et par sekunder, og sortere jer fra mindste på 430 00:15:59,380 --> 00:16:01,240 overlades til største til højre. 431 00:16:01,240 --> 00:16:02,490 Go. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> OK. 434 00:16:07,530 --> 00:16:08,030 Godt. 435 00:16:08,030 --> 00:16:09,370 Det var virkelig darn hurtigt. 436 00:16:09,370 --> 00:16:14,040 Nu nogen her, hvad der var den algoritme at disse fyre anvendt? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: Færrest til størst. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. MALAN: OK. 439 00:16:15,000 --> 00:16:18,070 Færrest til størst virkelig sortere i mål, men jeg er ikke sikker på det er 440 00:16:18,070 --> 00:16:18,890 virkelig en algoritme. 441 00:16:18,890 --> 00:16:21,810 Færrest til størst fortæller ikke mig trin-for-trin, hvad de skal gøre. 442 00:16:21,810 --> 00:16:22,833 Ja? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [uhørlig] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. MALAN: OK. 446 00:16:26,280 --> 00:16:28,920 Så hvis du ser en person mindre end dit nummer, derefter flytte til 447 00:16:28,920 --> 00:16:29,680 ret af dem. 448 00:16:29,680 --> 00:16:32,800 Så det er nu at få mere udtryksfulde, mere som en algoritme, fordi du 449 00:16:32,800 --> 00:16:35,410 kan sige, hvis dette, så det. 450 00:16:35,410 --> 00:16:37,050 Så vi har en form for betinget konstrukt. 451 00:16:37,050 --> 00:16:39,700 Og disse fyre syntes at gøre, at et par gange, fordi nogle af jer flyttede lidt 452 00:16:39,700 --> 00:16:40,420 af en afstand. 453 00:16:40,420 --> 00:16:43,410 Så der var formentlig en slags looping foregår i deres sind. 454 00:16:43,410 --> 00:16:44,610 >> Men lad os prøve at formalisere det. 455 00:16:44,610 --> 00:16:47,540 Hvis du fyre kunne nulstille tilbage til dette arrangement. 456 00:16:47,540 --> 00:16:50,650 Lad os se om vi ikke kan formalisere en bit, og derefter stille spørgsmålet, bare 457 00:16:50,650 --> 00:16:51,580 hvor effektiv er det? 458 00:16:51,580 --> 00:16:54,220 Selvfølgelig, når vi gør det langsommere det kommer til at føle sig så godt af 459 00:16:54,220 --> 00:16:57,210 en algoritme, men lad os se om vi kan sætte vores fingre på de præcise trin. 460 00:16:57,210 --> 00:16:58,670 >> Så du to fyre er fire og to. 461 00:16:58,670 --> 00:17:01,020 Eller du korrekt eller forkert rækkefølge? 462 00:17:01,020 --> 00:17:01,900 Naturligvis forkert. 463 00:17:01,900 --> 00:17:02,710 Så vi byttes. 464 00:17:02,710 --> 00:17:05,170 Nu vil jeg til at flytte bort her og sige, fire til seks. 465 00:17:05,170 --> 00:17:06,240 Er du korrekt eller ukorrekt? 466 00:17:06,240 --> 00:17:06,599 >> GABE: Korrekt. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Korrekt. 468 00:17:07,180 --> 00:17:08,300 Seks og en? 469 00:17:08,300 --> 00:17:08,609 Nope. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Så det er to swaps. 472 00:17:10,490 --> 00:17:11,710 Seks og tre? 473 00:17:11,710 --> 00:17:11,980 Nope. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Seks og syv? 476 00:17:13,930 --> 00:17:14,630 Ser godt ud. 477 00:17:14,630 --> 00:17:15,396 Syv og fem? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [uhørligt] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, swap. 480 00:17:17,089 --> 00:17:19,770 Og sorteres. 481 00:17:19,770 --> 00:17:19,980 Ok. 482 00:17:19,980 --> 00:17:21,440 Så selvfølgelig ikke, vel? 483 00:17:21,440 --> 00:17:22,470 Så der var flere foregår. 484 00:17:22,470 --> 00:17:24,920 Men, ja, disse fyre, selv bare instinktivt. 485 00:17:24,920 --> 00:17:25,450 holdes i bevægelse. 486 00:17:25,450 --> 00:17:27,710 De havde ikke bare stoppe, når de korrigeret et problem. 487 00:17:27,710 --> 00:17:27,839 Så. 488 00:17:27,839 --> 00:17:29,390 Faktisk vil jeg have at gøre det samme. 489 00:17:29,390 --> 00:17:32,720 Jeg nødt til at sortere i spole tilbage til begyndelsen af ​​dette problem, 490 00:17:32,720 --> 00:17:35,630 eller begyndelsen af ​​denne række af mennesker, lad os begynde at kalde dem. 491 00:17:35,630 --> 00:17:38,366 >> Og nu, hvad skal min algoritme på den anden pass være? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Samme ting. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Samme ting. 494 00:17:39,940 --> 00:17:41,460 Og det, jeg begynder at lide, right? 495 00:17:41,460 --> 00:17:44,720 Så snart du kan finde dig selv gøre det samme igen og igen, det er 496 00:17:44,720 --> 00:17:47,890 blive mere som en algoritme, og mindre menneskeligt instinkt. 497 00:17:47,890 --> 00:17:48,680 >> Så nu, her går vi igen. 498 00:17:48,680 --> 00:17:49,870 To og fire? 499 00:17:49,870 --> 00:17:50,220 Nej. 500 00:17:50,220 --> 00:17:51,050 Fire og en? 501 00:17:51,050 --> 00:17:53,380 Ah, var der faktisk nogle arbejde stadig skal gøres. 502 00:17:53,380 --> 00:17:53,620 For og tre? 503 00:17:53,620 --> 00:17:54,572 Godt. 504 00:17:54,572 --> 00:17:56,000 Fire og seks? 505 00:17:56,000 --> 00:17:58,380 Seks og fem? 506 00:17:58,380 --> 00:17:59,470 Seks og syv? 507 00:17:59,470 --> 00:18:00,970 OK, nu færdig. 508 00:18:00,970 --> 00:18:01,550 OK, nej. 509 00:18:01,550 --> 00:18:02,710 Jeg er nødt til at gå tilbage. 510 00:18:02,710 --> 00:18:05,130 >> Så nu, igen, vi gør dette lidt mere bevidst. 511 00:18:05,130 --> 00:18:08,700 Og nu er der kun én hjerne udføre denne algoritme. 512 00:18:08,700 --> 00:18:10,290 Én CPU, hvis du vil. 513 00:18:10,290 --> 00:18:13,090 Og helt ærligt, det er den eneste ressource vi kommer til at have adgang til. 514 00:18:13,090 --> 00:18:16,280 Og når vi går tilbage til et tastatur og har noget som C på vores 515 00:18:16,280 --> 00:18:19,600 bortskaffelse, vi kun skrive et program der kan gøre én ting ad gangen. 516 00:18:19,600 --> 00:18:22,900 Betragtninger, disse fyre et øjeblik siden, vi gearede deres kollektive hjernekraft 517 00:18:22,900 --> 00:18:24,180 ligesom du fyre gjorde i uge nul. 518 00:18:24,180 --> 00:18:24,980 Så lad os holde gøre dette. 519 00:18:24,980 --> 00:18:26,260 >> To og en. 520 00:18:26,260 --> 00:18:26,945 To og tre. 521 00:18:26,945 --> 00:18:27,460 Tre og fire. 522 00:18:27,460 --> 00:18:28,310 Fire og fem. 523 00:18:28,310 --> 00:18:28,620 Fem og seks. 524 00:18:28,620 --> 00:18:30,510 Seks og syv. 525 00:18:30,510 --> 00:18:31,880 Done? 526 00:18:31,880 --> 00:18:34,560 Så jeg er, men lad mig spille djævelens advokat. 527 00:18:34,560 --> 00:18:37,950 Har jeg, den slags computer, der bare gjorde en passerer gennem denne række af 528 00:18:37,950 --> 00:18:40,225 mennesker, ved, at jeg er færdig? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: Nej 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: Så hvorfor? 531 00:18:41,050 --> 00:18:46,900 Hvad ville jeg nødt til at gøre for at konkludere beslutsomt at jeg er færdig? 532 00:18:46,900 --> 00:18:48,230 Sandsynligvis en mere pass. 533 00:18:48,230 --> 00:18:48,430 Right? 534 00:18:48,430 --> 00:18:51,760 Fordi alle jeg kender fra at tidligere pass er, at jeg rettet en fejl. 535 00:18:51,760 --> 00:18:53,920 Og det betyder, måske er der endnu en fejltagelse 536 00:18:53,920 --> 00:18:54,840 at jeg er nødt til at korrigere. 537 00:18:54,840 --> 00:18:58,680 Så jeg kan kun være sikker ved tilbagespoling og derefter kontrollere, 1-2, to og 538 00:18:58,680 --> 00:19:00,940 tre, tre og fire, fire og fem, fem og seks, seks og syv. 539 00:19:00,940 --> 00:19:02,510 OK, nu jeg gjorde intet arbejde. 540 00:19:02,510 --> 00:19:05,990 >> Jeg kan helt sikkert huske, at jeg gjorde noget arbejde med noget som en variabel, 541 00:19:05,990 --> 00:19:06,975 gerne en int. 542 00:19:06,975 --> 00:19:12,490 Kald det swaps, og hvis swaps er 0 når jeg komme her, og det startede ved 0, så 543 00:19:12,490 --> 00:19:15,520 Jeg ville bare være dumt at holde ud frem og tilbage, kontrol igen, og 544 00:19:15,520 --> 00:19:16,450 igen og igen, ikke? 545 00:19:16,450 --> 00:19:18,450 Fordi du sidder fast i nogle slags uendelig løkke. 546 00:19:18,450 --> 00:19:21,250 Så så snart der er 0 swaps, Vi kan hævde, at dette 547 00:19:21,250 --> 00:19:23,810 algoritme er faktisk fuldstændig. 548 00:19:23,810 --> 00:19:25,400 >> Lad os nu sætte et navn på dette. 549 00:19:25,400 --> 00:19:28,930 Den algoritme, jeg foreslår vi bare implementeret er noget der hedder boble 550 00:19:28,930 --> 00:19:32,800 sortere, kendt som sådan i den forstand, at De tal, der er større slags 551 00:19:32,800 --> 00:19:37,990 bubble deres vej op til toppen, eller op til slutningen af ​​rækken af ​​tal. 552 00:19:37,990 --> 00:19:40,270 Men hvor effektiv var denne algoritme? 553 00:19:40,270 --> 00:19:44,600 Hvor mange skridt har jeg rent fysisk at tager for eksempel at sortere disse 554 00:19:44,600 --> 00:19:45,850 syv mennesker? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Fire til fem? 557 00:19:49,550 --> 00:19:51,420 OK, for mange er i sidste ende kommer til at være svaret. 558 00:19:51,420 --> 00:19:54,960 Men selv da, det specifikke antal er ikke så interessant. 559 00:19:54,960 --> 00:19:56,670 Lad os generalisere det som n. 560 00:19:56,670 --> 00:20:00,520 Så hvis jeg havde n folk op her, og de var slags, i tilfældig rækkefølge på 561 00:20:00,520 --> 00:20:02,180 begynder i den oprindelige rækkefølge. 562 00:20:02,180 --> 00:20:04,910 Nå, hvor mange skridt, jeg har at tage på den første pass? 563 00:20:04,910 --> 00:20:09,810 Det var en, to, tre, fire, fem, seks, og de er syv personer, så 564 00:20:09,810 --> 00:20:13,670 der er syv, seks -, så det er n minus en trin for første gang. 565 00:20:13,670 --> 00:20:16,280 >> Nu, hvor mange skridt, jeg har tage, når jeg spoles? 566 00:20:16,280 --> 00:20:19,310 Nå, kunne vi faktisk fordoblet, at hvis vi virkelig ønskede at, men for nu, jeg 567 00:20:19,310 --> 00:20:22,300 bare sige, okay, anden n minus 1. 568 00:20:22,300 --> 00:20:25,240 Så n minus 1 vil få irriterende at holde styr på, så lad os 569 00:20:25,240 --> 00:20:26,400 lige rundt lidt op. 570 00:20:26,400 --> 00:20:27,770 Så 2n trin. 571 00:20:27,770 --> 00:20:29,310 Så 14 trin, give eller tage. 572 00:20:29,310 --> 00:20:31,930 >> Hvor mange gange har jeg tager et skridt, næste gang? 573 00:20:31,930 --> 00:20:33,740 Tja, det er 3n. 574 00:20:33,740 --> 00:20:34,510 rigtig. 575 00:20:34,510 --> 00:20:37,920 Og nu, i værste fald, for Eksempelvis ville hvor mange gange jeg har 576 00:20:37,920 --> 00:20:41,730 gået frem og tilbage, frem og tilbage, udføre denne algoritme, bytte 577 00:20:41,730 --> 00:20:44,620 folk på hver pass, groft? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Det er faktisk n kvadreret, right? 580 00:20:50,010 --> 00:20:53,000 >> Fordi der i værste fald kan du slags af tænke over dette intuitivt, 581 00:20:53,000 --> 00:20:54,800 selvom det kan tage lidt lidt tid til at synke i. 582 00:20:54,800 --> 00:20:57,590 I værste fald, hvad ville disse syv mennesker har set ud, i 583 00:20:57,590 --> 00:21:00,230 ordningens vilkår deres antal? 584 00:21:00,230 --> 00:21:01,460 Helt baglæns, right? 585 00:21:01,460 --> 00:21:02,815 Og blot at simulere, hvad var dit navn igen? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. MALAN: Mike? 588 00:21:03,640 --> 00:21:08,100 OK, Mike, kan du bare slutte mig over her blot én sekund? 589 00:21:08,100 --> 00:21:08,880 Faktisk, nej. 590 00:21:08,880 --> 00:21:10,150 Undskyld Mike, lad os spole tilbage. 591 00:21:10,150 --> 00:21:10,910 Hvad er dit navn igen? 592 00:21:10,910 --> 00:21:11,180 >> NEIL: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. MALAN: Neil. 594 00:21:11,640 --> 00:21:13,750 OK, Neil, du kommer med mig, hvis du ikke har noget imod. 595 00:21:13,750 --> 00:21:17,150 Så jeg har tænkt mig at foreslå, bare for enkelhed, at Neil er nu i sin 596 00:21:17,150 --> 00:21:18,510 værst tænkelige tilfælde. 597 00:21:18,510 --> 00:21:20,720 Men huske, hvordan jeg implementeret min algoritme. 598 00:21:20,720 --> 00:21:24,530 Jeg sammenligne, sammenligne, sammenligne, sammenligne, sammenligne, oh. 599 00:21:24,530 --> 00:21:26,640 Nu er disse fyre er ude af orden, så jeg løse. 600 00:21:26,640 --> 00:21:27,980 Så du fyre bytte. 601 00:21:27,980 --> 00:21:31,630 Men nu overveje, hvor meget længere behøver Neil nødt til at gå? 602 00:21:31,630 --> 00:21:32,690 Det er nogenlunde n. 603 00:21:32,690 --> 00:21:33,570 Du ved, det er faktisk ikke n. 604 00:21:33,570 --> 00:21:36,040 Det er ligesom, n minus 1, men jeg får irriteret holde styr på den lille 605 00:21:36,040 --> 00:21:37,550 nummer, så lad os bare kalde det n. 606 00:21:37,550 --> 00:21:42,860 >> Så hvis Neil flytter et skridt maksimalt hver tid, og at flytte Neil ét trin, 607 00:21:42,860 --> 00:21:46,580 Jeg er nødt til at gøre dette virkelig kedelig pass frem og tilbage, dette er groft 608 00:21:46,580 --> 00:21:52,080 at gøre dette, n trin, i alt n gange, fordi det kommer til at tage mig 609 00:21:52,080 --> 00:21:55,820 at mange skridt til at få Neil alle vejen til, hvor han hører til. 610 00:21:55,820 --> 00:21:58,620 Endsige alle andre hvis du fyre blev alle mis-bestilt så godt. 611 00:21:58,620 --> 00:22:01,100 >> Så lad os kalde boble sortere n potens. 612 00:22:01,100 --> 00:22:04,860 Køretiden for denne algoritme, den udførelsen af ​​denne algoritme, den 613 00:22:04,860 --> 00:22:07,120 effektivitet af denne algoritme, Vi skal bare beskrive mere 614 00:22:07,120 --> 00:22:08,800 generelt som n kvadreret. 615 00:22:08,800 --> 00:22:11,650 Hvilket er rart, fordi jeg kunne gøre det samme eksempel med otte personer, ni 616 00:22:11,650 --> 00:22:15,450 mennesker, en million mennesker, og det Svaret er ikke til at ændre. 617 00:22:15,450 --> 00:22:18,870 >> Så hvis du fyre ville huske, lad os nulstille dig til hvor du startede. 618 00:22:18,870 --> 00:22:22,510 Og lad os prøve to andre tilgange og se, om vi ikke kan gøre fundamentalt 619 00:22:22,510 --> 00:22:23,820 bedre end dette. 620 00:22:23,820 --> 00:22:27,130 Så denne gang, vil jeg foreslå en slags anden algoritme. 621 00:22:27,130 --> 00:22:29,950 Det var meget klog af os sidste gang, og du fyre var ret til at få 622 00:22:29,950 --> 00:22:32,470 rigtige instinkter bare lidt at bytte parvis. 623 00:22:32,470 --> 00:22:36,500 Men hvis jeg virkelig ønskede at nærme sig dette simpelthen, og mit mål er at flytte 624 00:22:36,500 --> 00:22:39,800 alle de små numre på denne måde, og skubbe alle de store tal, 625 00:22:39,800 --> 00:22:43,030 måde, hvorfor jeg ikke bare gøre det i mest naive måde som muligt og se om jeg 626 00:22:43,030 --> 00:22:45,730 kan gøre det bedre end det, der var en temmelig kompliceret algoritme? 627 00:22:45,730 --> 00:22:46,620 >> Så lad os se. 628 00:22:46,620 --> 00:22:48,940 Fire er en temmelig lille antal, så jeg er kommer til at forlade dig der øjeblik. 629 00:22:48,940 --> 00:22:50,610 Ooh, nummer to er endnu bedre. 630 00:22:50,610 --> 00:22:52,230 Så kan du bare træde frem et øjeblik? 631 00:22:52,230 --> 00:22:55,670 Dette er i øjeblikket mit mindste nummererede kandidat, og jeg har tænkt mig at huske 632 00:22:55,670 --> 00:22:57,000 at med, ligesom, en variabel. 633 00:22:57,000 --> 00:22:57,930 Men jeg har tænkt mig at holde kontrol. 634 00:22:57,930 --> 00:22:59,890 Er der en person, hvis nummer er mindre? 635 00:22:59,890 --> 00:23:00,460 Seks, nej. 636 00:23:00,460 --> 00:23:01,390 Åh, der er Neil igen. 637 00:23:01,390 --> 00:23:04,050 >> Så jeg har tænkt mig at skubbe dig tilbage slags konceptuelt. 638 00:23:04,050 --> 00:23:05,120 Neil vil komme frem. 639 00:23:05,120 --> 00:23:08,440 Og nu, den variabel, jeg bruger til at holde styr på, hvem der har den mindste 640 00:23:08,440 --> 00:23:11,390 nummer er opdateret til at indeholde Neil placering. 641 00:23:11,390 --> 00:23:12,110 Nå, lad os se. 642 00:23:12,110 --> 00:23:13,960 Tre, syv, fem. 643 00:23:13,960 --> 00:23:15,590 OK, jeg kender Neil var den mindste. 644 00:23:15,590 --> 00:23:18,110 Hvad er den enkleste ting for mig at gøre nu? 645 00:23:18,110 --> 00:23:21,410 Jeg vil ikke spilde min tid ved blot boblende Neil en plet til venstre. 646 00:23:21,410 --> 00:23:25,350 Hvorfor kan jeg ikke bare sætte Neil, hvor han tilhører, hvilket selvfølgelig er hvor? 647 00:23:25,350 --> 00:23:26,160 >> Hele vejen i begyndelsen. 648 00:23:26,160 --> 00:23:27,720 Så Neil, kom med mig. 649 00:23:27,720 --> 00:23:28,910 Og hvad var dit navn igen? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. MALAN: Grace. 652 00:23:29,710 --> 00:23:29,920 OK. 653 00:23:29,920 --> 00:23:32,490 Så Grace, desværre, du er slags i vejen. 654 00:23:32,490 --> 00:23:34,290 Så hvordan kan vi løse dette problem? 655 00:23:34,290 --> 00:23:34,490 Right? 656 00:23:34,490 --> 00:23:37,500 Hvis dette er et array, der er kun syv placeringer. 657 00:23:37,500 --> 00:23:40,830 Husk på, at med Rob, vi talte om erklære aldre, og vi havde kun en 658 00:23:40,830 --> 00:23:41,740 endeligt antal aldre? 659 00:23:41,740 --> 00:23:42,535 Samme idé her. 660 00:23:42,535 --> 00:23:44,300 Vi har kun et begrænset antal int'er. 661 00:23:44,300 --> 00:23:47,590 Nåde er slags i vores måde, så hvordan vi løser? 662 00:23:47,590 --> 00:23:49,555 >> Den enkleste måde er ligesom, Grace, undskyld. 663 00:23:49,555 --> 00:23:51,870 Du er nødt til at gå over der, så vi kan få mere plads. 664 00:23:51,870 --> 00:23:55,290 Nu, hvis du tænker over det, måske vi bare gjort problemet værre. 665 00:23:55,290 --> 00:23:58,510 Og måske vi gjorde det, fordi det, hvis Grace var på det rigtige sted? 666 00:23:58,510 --> 00:24:01,730 Men vi ved, hun er ikke, fordi ellers ville hun have været 667 00:24:01,730 --> 00:24:03,980 stående fremad i stedet for Neil på dette tidspunkt, right? 668 00:24:03,980 --> 00:24:05,550 Vi har allerede tjekket hendes nummer ud. 669 00:24:05,550 --> 00:24:05,770 >> Ok. 670 00:24:05,770 --> 00:24:09,110 Så nu, Neil er på rette sted, og Jeg kan gøre en lille optimering. 671 00:24:09,110 --> 00:24:11,740 For det næste øjeblik, vil jeg ignorere Neil alle sammen, så der ikke 672 00:24:11,740 --> 00:24:15,280 spilde sin tid, eller ved et uheld bytte ham til det forkerte sted. 673 00:24:15,280 --> 00:24:17,805 Så nu, hvordan finder jeg den næste element, der er mindst? 674 00:24:17,805 --> 00:24:18,480 Two. 675 00:24:18,480 --> 00:24:20,225 Det er en temmelig god del, hvis du ønsker at træde frem og 676 00:24:20,225 --> 00:24:21,100 Jeg vil huske dig. 677 00:24:21,100 --> 00:24:21,980 Six, ikke godt. 678 00:24:21,980 --> 00:24:24,820 Fire, tre, syv, fem, noget godt. 679 00:24:24,820 --> 00:24:26,800 Så lad mig flytte dig til Deres rigtige sted. 680 00:24:26,800 --> 00:24:28,470 Og vi har lige fået heldig denne gang. 681 00:24:28,470 --> 00:24:31,350 >> Nu vil jeg til at ignorere disse to fyre, og nu gør en mere 682 00:24:31,350 --> 00:24:32,260 passere gennem denne. 683 00:24:32,260 --> 00:24:33,490 Six, at en temmelig lille antal. 684 00:24:33,490 --> 00:24:34,300 Kom fremad. 685 00:24:34,300 --> 00:24:35,220 Åh, undskyld. 686 00:24:35,220 --> 00:24:37,640 Grace nummer er bedre, så træde på fremad. 687 00:24:37,640 --> 00:24:38,260 Four. 688 00:24:38,260 --> 00:24:39,120 Beklager, Grace. 689 00:24:39,120 --> 00:24:39,950 Gå tilbage igen. 690 00:24:39,950 --> 00:24:41,550 Nummer tre er bedre. 691 00:24:41,550 --> 00:24:42,290 Syv. 692 00:24:42,290 --> 00:24:42,720 Five. 693 00:24:42,720 --> 00:24:43,550 Og nu, hvad er dit navn igen? 694 00:24:43,550 --> 00:24:44,000 >> JASON: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. MALAN: Jason. 696 00:24:44,420 --> 00:24:47,050 Så Jason er nu den mindste element, jeg har valgt. 697 00:24:47,050 --> 00:24:49,160 Hvor skal han hen? 698 00:24:49,160 --> 00:24:50,380 Så hvor seks er. 699 00:24:50,380 --> 00:24:51,210 Og dit navn er igen? 700 00:24:51,210 --> 00:24:51,710 >> GABE: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. MALAN: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe er i vejen. 703 00:24:53,220 --> 00:24:54,640 Hvad er den letteste ting at gøre? 704 00:24:54,640 --> 00:24:58,390 Swap disse to fyre og fortsætte. 705 00:24:58,390 --> 00:24:59,020 Så lad os nu se. 706 00:24:59,020 --> 00:25:00,170 Hvem er den mindste? 707 00:25:00,170 --> 00:25:01,030 Four. 708 00:25:01,030 --> 00:25:01,990 Lad mig lige slags snyde. 709 00:25:01,990 --> 00:25:03,090 Fem bliver den mindste. 710 00:25:03,090 --> 00:25:05,220 Jeg finder næste hvis du ønsker at træde frem, hvad jeg har at gøre med 711 00:25:05,220 --> 00:25:06,820 disse fyre, med Gabe? 712 00:25:06,820 --> 00:25:08,450 Swap igen. 713 00:25:08,450 --> 00:25:10,740 Så nu, stadig en smule ude af drift. 714 00:25:10,740 --> 00:25:14,140 Jeg fandt Gabe at være den mindste, så Jeg pop ham ud, flytter jer over. 715 00:25:14,140 --> 00:25:15,190 Og gjort. 716 00:25:15,190 --> 00:25:17,200 >> Så svaret er det samme. 717 00:25:17,200 --> 00:25:18,600 Slutresultatet er det samme. 718 00:25:18,600 --> 00:25:22,730 Hvilken af ​​disse to algoritmer er bedre? 719 00:25:22,730 --> 00:25:23,500 Den anden, jeg hørte. 720 00:25:23,500 --> 00:25:24,252 Hvorfor? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Det n trin [uhørlig]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: Det er n trin på de fleste. 723 00:25:27,600 --> 00:25:28,490 Interessant. 724 00:25:28,490 --> 00:25:30,610 Så er det dog? 725 00:25:30,610 --> 00:25:33,630 Så hvordan har jeg finde mindste element? 726 00:25:33,630 --> 00:25:37,060 Hvor mange skridt jeg nødt til at tage Den finder det mindste element? 727 00:25:37,060 --> 00:25:39,220 Jeg havde et kig hele vejen i slutningen, right? 728 00:25:39,220 --> 00:25:41,530 Fordi i det værste tilfælde, hvad hvis Neil var herovre? 729 00:25:41,530 --> 00:25:45,700 Så bare at finde det mindste element tager mig n trin, eller n minus 1. 730 00:25:45,700 --> 00:25:46,100 Men OK. 731 00:25:46,100 --> 00:25:46,980 Så fix Neil. 732 00:25:46,980 --> 00:25:48,740 Husk, et minut eller deromkring siden. 733 00:25:48,740 --> 00:25:51,680 >> Men hvordan finder jeg det næste mindste element? 734 00:25:51,680 --> 00:25:54,830 Det er n minus 1 eller n minus 2 rigtig, fra antallet af trin. 735 00:25:54,830 --> 00:25:55,440 Så OK. 736 00:25:55,440 --> 00:25:57,390 Så jeg gjorde n minus 2. 737 00:25:57,390 --> 00:25:57,600 Ok. 738 00:25:57,600 --> 00:25:59,130 Så det føles lidt bedre. 739 00:25:59,130 --> 00:25:59,730 Ok. 740 00:25:59,730 --> 00:26:03,270 Hvor mange skridt, næste gang at finde nummer tre? 741 00:26:03,270 --> 00:26:04,420 Så n minus 4. 742 00:26:04,420 --> 00:26:07,670 Så det er faldende, én færre trin på hver iteration. 743 00:26:07,670 --> 00:26:08,740 Så det betyder at føle sig bedre, right? 744 00:26:08,740 --> 00:26:13,450 Hvis sidste gang det var nogenlunde n gange n, denne gang er det n minus 1 plus n minus 745 00:26:13,450 --> 00:26:16,500 2, plus n minus 3, plus n minus 4, prik, prik, prik. 746 00:26:16,500 --> 00:26:18,750 Men hvis du husker fra din high school lærebøger, den lille snyde 747 00:26:18,750 --> 00:26:24,380 ark på bagsiden, der har formler, medmindre du tilføje op denne serie af tal, 748 00:26:24,380 --> 00:26:31,280 hvad er det totale antal trin kommer til at være, at jeg tager her? 749 00:26:31,280 --> 00:26:36,580 >> Dette er en af ​​dem, ligesom, n minus 1, gange n, divideret med 2. 750 00:26:36,580 --> 00:26:39,040 Så lad mig se om jeg kan trække dette op for bare et øjeblik. 751 00:26:39,040 --> 00:26:42,230 Og igen, jeg er slags afrunding nogle tal bare for at holde vores liv simpelt, 752 00:26:42,230 --> 00:26:47,830 men så vidt jeg husker, det er noget ligesom hvis Jeg gør n minus 1 ting, så n minus 753 00:26:47,830 --> 00:26:53,570 2, er n minus 3, det er groft noget som dette over 2, og hvis jeg 754 00:26:53,570 --> 00:26:55,510 formere det ud, det er faktisk n square. 755 00:26:55,510 --> 00:26:58,940 Det er ikke føler også godt. n minus n over 2. 756 00:26:58,940 --> 00:27:00,350 >> Men her er de ting. 757 00:27:00,350 --> 00:27:03,720 I datalogi, når problemerne begynder at blive interessant, er, når n 758 00:27:03,720 --> 00:27:04,700 bliver rigtig stort. 759 00:27:04,700 --> 00:27:08,110 Og når n bliver rigtig stort, hvilke af disse værdier kommer til at dominere hele 760 00:27:08,110 --> 00:27:09,750 af de andre? 761 00:27:09,750 --> 00:27:10,990 Det er lidt af n kvadreret, right? 762 00:27:10,990 --> 00:27:13,340 Ja, dividere med 2 er temmelig godt. 763 00:27:13,340 --> 00:27:16,740 Men hvis du taler om milliarder af stykker af data eller trillioner af 764 00:27:16,740 --> 00:27:18,700 stykker af data, OK, så du dobbelt så hurtigt. 765 00:27:18,700 --> 00:27:22,440 Men der virkelig bekymrer sig om hvis det store antal, hvis denne faktor er, hvad får 766 00:27:22,440 --> 00:27:23,040 større og større. 767 00:27:23,040 --> 00:27:25,990 Og sikkert, det gør mere en forskel end denne fyr. 768 00:27:25,990 --> 00:27:29,120 Så selvom du fyre er rigtige, anden algoritme, vi kalder det 769 00:27:29,120 --> 00:27:32,970 udvælgelse sortere, er i den virkelige verden, en smule hurtigere potentielt fordi jeg er 770 00:27:32,970 --> 00:27:35,360 tager færre og færre trin hver gang. 771 00:27:35,360 --> 00:27:37,340 >> Det er egentlig ikke fundamentalt hurtigere. 772 00:27:37,340 --> 00:27:41,430 For hvis vi rent faktisk spiller det ud for store værdier af n, i slutningen af 773 00:27:41,430 --> 00:27:44,750 dag, for store nok n, er det stadig kommer til at føle sig temmelig langsomme. 774 00:27:44,750 --> 00:27:46,770 Nå, lad mig tage et sidste pass på det. 775 00:27:46,770 --> 00:27:48,920 Det er, hvad jeg ville kalde udvælgelse slags. 776 00:27:48,920 --> 00:27:51,040 Kan du fyre nulstille jer en sidste gang? 777 00:27:51,040 --> 00:27:53,550 Og i dette sidste tilfælde, vil jeg at foreslå noget 778 00:27:53,550 --> 00:27:54,970 kaldet indsættelse slags. 779 00:27:54,970 --> 00:27:57,470 Indsættelse slags væsen, begrebsmæssigt, en smule anderledes. 780 00:27:57,470 --> 00:28:00,980 >> Snarere end at gå frem og tilbage, og vælge den mindste element, jeg er 781 00:28:00,980 --> 00:28:05,030 bare at beskæftige sig med hver af disse fyre, som jeg støder på dem, og indsæt 782 00:28:05,030 --> 00:28:06,850 dem ind i deres rette plads. 783 00:28:06,850 --> 00:28:10,160 Så jeg bare kommer til at starte med Grace, og jeg kan se, at hun er nummer fire. 784 00:28:10,160 --> 00:28:11,720 Hvor kommer nummer fire tilhører? 785 00:28:11,720 --> 00:28:14,940 Jeg har ikke startet sortering noget, så Grace får at bo lige der. 786 00:28:14,940 --> 00:28:18,355 Og nu vil jeg påstå, hvis du kunne tage et skridt til højre, dette 787 00:28:18,355 --> 00:28:21,650 min sorteret liste, dette er min usorteret resterende liste. 788 00:28:21,650 --> 00:28:23,260 Så nu har jeg tænkt mig at fortsætte næste, og hvad er dit navn igen? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. MALAN: Branson. 791 00:28:24,150 --> 00:28:25,375 Så Branson er nummer to. 792 00:28:25,375 --> 00:28:27,490 Så jeg har tænkt mig at tage dig ud et øjeblik. 793 00:28:27,490 --> 00:28:30,940 Og nu, hvor du hører i dette array? 794 00:28:30,940 --> 00:28:32,360 Så til højre for Grace. 795 00:28:32,360 --> 00:28:35,670 Så igen er vi slags at gøre Grace gøre en masse arbejde her. 796 00:28:35,670 --> 00:28:37,290 Hvor skal vi sætte dig? 797 00:28:37,290 --> 00:28:40,120 Så vi kommer til at skubbe dig til den tilbage, og indsæt Branson der. 798 00:28:40,120 --> 00:28:41,680 Men nu er jeg hævder, at du fyre er færdig. 799 00:28:41,680 --> 00:28:43,240 Men varsel, jeg bruger ikke ekstra plads. 800 00:28:43,240 --> 00:28:45,130 Det er stadig 2 elementer her, 5 herovre. 801 00:28:45,130 --> 00:28:47,910 Samlet array-størrelse er 7, så jeg er ikke snyd, okay? 802 00:28:47,910 --> 00:28:51,950 >> Så nu har vi med Gabe her, de nummer seks, hvor hører du? 803 00:28:51,950 --> 00:28:52,650 Du fik heldig igen. 804 00:28:52,650 --> 00:28:53,820 Så får du til at bo lige der. 805 00:28:53,820 --> 00:28:57,210 Bare tage et lille skridt i den rigtige bare for at gøre det klart, at du er sorteret. 806 00:28:57,210 --> 00:29:00,520 Og nu har vi Neil igen, tal en, hvor vil du hen? 807 00:29:00,520 --> 00:29:03,540 Og nu hvor vi vil begynde at se, at denne algoritme, selvom på første 808 00:29:03,540 --> 00:29:05,950 øjekast føles temmelig smart, se hvad der er ved at ske. 809 00:29:05,950 --> 00:29:07,370 Hvis du kunne træde frem. 810 00:29:07,370 --> 00:29:09,260 >> Hvor vil vi sætte Neil? 811 00:29:09,260 --> 00:29:11,830 Så selvfølgelig her, så hvordan får vi Neil der? 812 00:29:11,830 --> 00:29:12,970 Lad os gøre det trin-for-trin. 813 00:29:12,970 --> 00:29:15,620 Gabe, hvor vil du nødt til at gå? 814 00:29:15,620 --> 00:29:19,590 Jep, så tager et stort skridt, eller to halve skridt til at gøre 815 00:29:19,590 --> 00:29:20,820 et skridt derovre. 816 00:29:20,820 --> 00:29:21,750 Grace, hvor du går? 817 00:29:21,750 --> 00:29:22,510 Godt. 818 00:29:22,510 --> 00:29:23,500 Så endnu et skridt. 819 00:29:23,500 --> 00:29:24,960 Og endelig, Branson? 820 00:29:24,960 --> 00:29:25,460 Et andet skridt. 821 00:29:25,460 --> 00:29:27,190 Og nu kan vi sætte Neil plads. 822 00:29:27,190 --> 00:29:28,440 >> Så nu, fortsætte denne logik. 823 00:29:28,440 --> 00:29:32,420 Selvom vi ikke flytte Neil overstået, og igen, og igen, for at sætte ham 824 00:29:32,420 --> 00:29:36,420 hvor han går, i værste fald næste nummer, vi kan støde kunne 825 00:29:36,420 --> 00:29:42,220 være nummer, siger, at der var en række nul, så vi kommer til at flytte alle 826 00:29:42,220 --> 00:29:42,730 disse fyre. 827 00:29:42,730 --> 00:29:44,950 Antag, at der er et tal, negativ én, så er vi nødt til at flytte 828 00:29:44,950 --> 00:29:46,080 alle disse fyre. 829 00:29:46,080 --> 00:29:48,500 Så vi er egentlig bare slags spejlvende problemet omkring, således at vi er 830 00:29:48,500 --> 00:29:52,620 overføre bekostning fra udvælgelsesprocessen, så indføringen 831 00:29:52,620 --> 00:29:56,930 proces, således at du fyre lige haft at bevæge groft n minus noget 832 00:29:56,930 --> 00:29:57,940 antal trin. 833 00:29:57,940 --> 00:30:01,200 Og at antallet af trin er kun vil at stige som jeg vælger flere numre, 834 00:30:01,200 --> 00:30:04,730 hvis jeg nødt til at holde skubbede jer tilbage, og ryg, og ryg. 835 00:30:04,730 --> 00:30:08,320 >> Så den triste ting er nu alle disse algoritmer er n potens. 836 00:30:08,320 --> 00:30:10,570 Lad os gå videre og tak til dem gutter, og visualisere dem lidt 837 00:30:10,570 --> 00:30:11,090 forskelligt. 838 00:30:11,090 --> 00:30:12,312 Meget godt klaret. 839 00:30:12,312 --> 00:30:14,120 >> [Applaus] 840 00:30:14,120 --> 00:30:15,030 >> Ok. 841 00:30:15,030 --> 00:30:16,280 Værsgo. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Tak for - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [uhørlig] holde tallene. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. MALAN: Nej, du må holde antallet samt. 846 00:30:21,990 --> 00:30:23,440 Ok. 847 00:30:23,440 --> 00:30:24,100 Pænt gjort. 848 00:30:24,100 --> 00:30:25,300 Ok. 849 00:30:25,300 --> 00:30:30,510 Så lad os se, om vi ikke nu kan opsummere hurtigere og mere visuelt, 850 00:30:30,510 --> 00:30:33,410 præcis, hvad der lige er sket her som følger. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Jeg har tænkt mig at gå videre og trække op Firefox. 853 00:30:38,770 --> 00:30:41,310 Vi linker denne demonstration på kursets hjemmeside. 854 00:30:41,310 --> 00:30:43,870 Java er en smule irriterende at få arbejde i nogle browsere disse dage. 855 00:30:43,870 --> 00:30:46,760 Så hvis du leger med det derhjemme, indser du måske nødt til at bruge Firefox 856 00:30:46,760 --> 00:30:47,990 at få det arbejder. 857 00:30:47,990 --> 00:30:50,440 Og hvad jeg har tænkt mig at gøre med dette demonstration er det følgende. 858 00:30:50,440 --> 00:30:54,875 >> Nederst har jeg en hel masse menupunkter, herunder en start-og en 859 00:30:54,875 --> 00:30:55,840 stop knap. 860 00:30:55,840 --> 00:30:59,450 Også, som en sidebemærkning, synes der at være en fejl i disse programmer, hvor du 861 00:30:59,450 --> 00:31:03,720 kan faktisk ikke se start eller stop knappen, medmindre du holder Kommando eller Alt 862 00:31:03,720 --> 00:31:06,560 plus og zoome ind, hvilket mærkeligt nok viser dig flere knapper. 863 00:31:06,560 --> 00:31:09,090 Så bare FYI, hvis du spiller med dette derhjemme. 864 00:31:09,090 --> 00:31:12,870 Nu vil jeg til at klikke på Start på bare et øjeblik, efter angivelse af en forsinkelse på, 865 00:31:12,870 --> 00:31:16,810 ligesom, 200 millisekunder her, bare så vi kan se hvad der sker. 866 00:31:16,810 --> 00:31:20,180 >> Så jeg hævder, at dette er en visualisering Den første algoritme 867 00:31:20,180 --> 00:31:23,730 disse fyre gjorde, boble sortere, hvorved vi byttes folk parvise. 868 00:31:23,730 --> 00:31:27,490 Nøglen indblik i denne visualisering er, at højden af ​​søjlerne 869 00:31:27,490 --> 00:31:30,510 repræsenterer størrelsen af ​​nummeret. 870 00:31:30,510 --> 00:31:32,210 Så højere søjlen er, jo højere tal. 871 00:31:32,210 --> 00:31:33,680 Kortere baren, mindre tal. 872 00:31:33,680 --> 00:31:38,630 Og hvis du bemærker, vi går igennem den første iteration af denne algoritme, 873 00:31:38,630 --> 00:31:42,620 swapping store og små tal, så det lille antal kommer først og 874 00:31:42,620 --> 00:31:44,280 det store antal går til højre. 875 00:31:44,280 --> 00:31:48,770 >> Og så snart vi får i slutningen af ​​matrix mange flere tal end syv, er vi 876 00:31:48,770 --> 00:31:49,900 kommer til at gå tilbage til begyndelsen. 877 00:31:49,900 --> 00:31:51,140 Og forudse dette. 878 00:31:51,140 --> 00:31:54,860 Længst til venstre, er den lille fyr går at bytte til siden, og dette 879 00:31:54,860 --> 00:31:56,010 Processen gentages. 880 00:31:56,010 --> 00:31:59,450 Nu er denne visualisering får hurtigt kedeligt, så lad mig gå videre og stoppe 881 00:31:59,450 --> 00:32:04,170 det, ændre forsinkelsen noget meget hurtigere bare for at komme nu, en fornemmelse for 882 00:32:04,170 --> 00:32:05,060 denne algoritme. 883 00:32:05,060 --> 00:32:07,840 >> Så selvom jeg har drønede den op, det er ligesom opgradering af min processor, køb 884 00:32:07,840 --> 00:32:08,580 en ny computer. 885 00:32:08,580 --> 00:32:12,980 Jeg har ikke fundamentalt ændret min algoritme, men du kan faktisk se mere 886 00:32:12,980 --> 00:32:16,800 tydeligt end med mennesker, at de store tal gennemstrømning op til toppen, 887 00:32:16,800 --> 00:32:20,900 og de små tal boblende ned til bunden. 888 00:32:20,900 --> 00:32:22,390 Og nu denne ting her sorteres. 889 00:32:22,390 --> 00:32:25,260 Og som en sidebemærkning på pladserne, er der blot nogle bogholderi der til 890 00:32:25,260 --> 00:32:28,010 hjælpe dig med at tælle, hvor mange sammenligninger, eller hvor mange swaps har 891 00:32:28,010 --> 00:32:28,950 rent faktisk er blevet gjort. 892 00:32:28,950 --> 00:32:30,750 >> Nå, lad os prøve en af de andre vi så. 893 00:32:30,750 --> 00:32:37,116 Lad mig klikke på boble sortere her og lad mig vælge, og det hele websiden 894 00:32:37,116 --> 00:32:38,936 er en lille buggy. 895 00:32:38,936 --> 00:32:41,155 Lad os acceptere risikoen og køre det igen. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Der går vi. 898 00:32:45,030 --> 00:32:47,180 Så lad os gøre udvælgelsen slags. 899 00:32:47,180 --> 00:32:49,140 Jeg ved ikke, hvorfor menuen vises derovre. 900 00:32:49,140 --> 00:32:54,070 Lad os zoome ind for at fastsætte, at bug, ændre dette til 50 år. 901 00:32:54,070 --> 00:32:56,020 Ah, lad os rent faktisk gør at meget hurtigere. 902 00:32:56,020 --> 00:32:59,160 Fem millisekunder eller deromkring, og Start. 903 00:32:59,160 --> 00:33:00,470 >> Så dette er valg slags. 904 00:33:00,470 --> 00:33:03,070 Så igen tænke over, hvad vi gjorde med mennesker heroppe. 905 00:33:03,070 --> 00:33:08,490 Vi gik gennem rækken, og udvalgte det mindste element igen, 906 00:33:08,490 --> 00:33:09,250 og igen og igen. 907 00:33:09,250 --> 00:33:11,110 Nu er jeg hævder, at stadig var temmelig dårlig. 908 00:33:11,110 --> 00:33:15,010 Det var stadig n kvadreret, give eller tage, men det var i den virkelige verden, en smule 909 00:33:15,010 --> 00:33:18,280 hurtigere, fordi jeg faktisk tog lidt færre trin hver gang. 910 00:33:18,280 --> 00:33:19,800 Men vi kun taler hvad? 911 00:33:19,800 --> 00:33:21,830 Måske 40 eller så barer herinde? 912 00:33:21,830 --> 00:33:23,200 Vi taler ikke 40 mio. 913 00:33:23,200 --> 00:33:27,430 Så det er ikke helt klart for mig, at var en væsentlig gevinst. 914 00:33:27,430 --> 00:33:32,530 >> Lad mig nu gå tilbage og ændre vores tredje algoritme, der blev vælge 915 00:33:32,530 --> 00:33:33,180 indsættelse slags. 916 00:33:33,180 --> 00:33:36,380 Og nu er det virkelig buggy, fordi Menuen burde virkelig ikke være dernede. 917 00:33:36,380 --> 00:33:40,840 Så nu vil vi rulle tilbage op her og starte denne algoritme. 918 00:33:40,840 --> 00:33:43,270 Whoop, start og stop. 919 00:33:43,270 --> 00:33:47,160 Så dette en slags har en smuk mønster til det, vi hvorved er igen 920 00:33:47,160 --> 00:33:50,240 indsætte mennesker, eller i denne sag, søjlerne i 921 00:33:50,240 --> 00:33:52,620 deres passende placering. 922 00:33:52,620 --> 00:33:55,430 Og det er allerede gjort før Jeg vendte mig om. 923 00:33:55,430 --> 00:33:58,940 Men denne ene, også i teorien stadig n potens. 924 00:33:58,940 --> 00:34:01,430 >> Så lad os se om vi ikke kan opsummere disse som følger. 925 00:34:01,430 --> 00:34:04,750 Jeg har tænkt mig at gå videre og bare for at give os en slags fælles måde at tale 926 00:34:04,750 --> 00:34:08,489 om disse ting, så lad mig introducere bare en smule notation her. 927 00:34:08,489 --> 00:34:12,480 Du er ved at se noget, der hedder stort O, fordi det er bogstaveligt talt en stor 928 00:34:12,480 --> 00:34:16,320 O. Og det er en måde, at en computer videnskabsmand eller en matematiker bruger endda 929 00:34:16,320 --> 00:34:19,230 at beskrive køretiden af nogle algoritme. 930 00:34:19,230 --> 00:34:21,400 Hvor mange skridt betyder det egentlig tage? 931 00:34:21,400 --> 00:34:25,080 >> Nu vil jeg genere mig med min håndskrift her i bare et øjeblik. 932 00:34:25,080 --> 00:34:29,020 Men lad mig gå videre og sige, at dette vil være store O herovre. 933 00:34:29,020 --> 00:34:33,610 Og lad mig introducere et andet symbol, et kapital omega. 934 00:34:33,610 --> 00:34:37,080 Omega bliver det modsatte, væsentlige for big O. betragtninger big O 935 00:34:37,080 --> 00:34:40,790 midler, i værste fald, hvor meget tid kan nogle algoritme tage i 936 00:34:40,790 --> 00:34:43,480 form af n er omega vil være, hvor meget tid ville det måske 937 00:34:43,480 --> 00:34:45,409 tager i bedste fald. 938 00:34:45,409 --> 00:34:48,090 Og vi vil se, hvad vi mener med bedste fald på bare et øjeblik. 939 00:34:48,090 --> 00:34:49,940 >> Så lad os starte noget simpelt. 940 00:34:49,940 --> 00:34:54,719 Lad mig starte med en lineær søgning. 941 00:34:54,719 --> 00:34:55,679 Så ikke sortering. 942 00:34:55,679 --> 00:34:58,000 Vi kalder denne lineære søgning. 943 00:34:58,000 --> 00:35:01,140 Og nu, gøre en lille tabel ud af dette. 944 00:35:01,140 --> 00:35:06,600 Og nu, i tilfælde af lineære søgning, i værste fald, er, hvor mange skridt 945 00:35:06,600 --> 00:35:11,770 Det kommer til at tage mig at finde en Antallet af vilkårlige valg? 946 00:35:11,770 --> 00:35:14,540 Og der er n samlede døre eller n samlede antal. 947 00:35:14,540 --> 00:35:15,940 Worst case. 948 00:35:15,940 --> 00:35:18,800 Hvor mange skridt jeg nødt til at tage for at finde nummeret 50 i et array 949 00:35:18,800 --> 00:35:20,830 af n døre? 950 00:35:20,830 --> 00:35:21,410 Og hvorfor? 951 00:35:21,410 --> 00:35:23,680 Fordi det kan være alle de vej over på enden. 952 00:35:23,680 --> 00:35:27,120 Så meget som Jennifer stødt på, at nummer 50 var hele vejen over, så i 953 00:35:27,120 --> 00:35:30,760 worst case lineær søgning er big O n, vil vi sige. 954 00:35:30,760 --> 00:35:33,430 >> Hvad bedste fald hvis du får virkelig heldig? 955 00:35:33,430 --> 00:35:36,200 Det er bare at tage et skridt, eller et konstant antal trin. 956 00:35:36,200 --> 00:35:37,830 Så vi vil beskrive det som 1. 957 00:35:37,830 --> 00:35:39,010 Så dette er temmelig godt. 958 00:35:39,010 --> 00:35:41,210 Hvad nu hvis vi gjorde noget lide binær søgning? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Så binær søgning i værste tilfælde tog, hvor meget tid? 961 00:35:47,846 --> 00:35:49,250 >> [Interposing STEMMER] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. MALAN: Så egentlig, jeg hørte det i et par steder. 963 00:35:51,310 --> 00:35:56,390 Så det er faktisk logge n, give eller tage, fordi som vi deler listen i halve 964 00:35:56,390 --> 00:36:00,730 igen og igen, og igen, vi er i stand at finde i sidste ende værdi, 965 00:36:00,730 --> 00:36:04,750 hvis det er der, men der er en fangst. 966 00:36:04,750 --> 00:36:08,590 Hvad er den antagelse, at vi er nødt til tager for givet for binær søgning? 967 00:36:08,590 --> 00:36:09,700 Det skal sorteres. 968 00:36:09,700 --> 00:36:12,770 Det er ikke sorteret, kan du opdele ting i halve igen og igen, og du 969 00:36:12,770 --> 00:36:15,490 kan gå til venstre, og du kan gå til højre, og du kan gå til venstre og højre, men du er 970 00:36:15,490 --> 00:36:18,070 ikke kommer til at finde det element, hvis listen er ikke sorteret, fordi 971 00:36:18,070 --> 00:36:18,790 du måske glip af det. 972 00:36:18,790 --> 00:36:22,120 Fordi din heuristisk, for at gå til venstre eller højre vil være behæftet med fejl, hvis det er 973 00:36:22,120 --> 00:36:23,420 faktisk ikke er sorteret. 974 00:36:23,420 --> 00:36:26,110 Så der er en slags skjult omkostning at bruge noget som dette. 975 00:36:26,110 --> 00:36:29,250 >> Nu, lad os gå ind i vores sortering algoritmer ikke søger - 976 00:36:29,250 --> 00:36:31,140 åh, faktisk Lad os gå i denne tomt. 977 00:36:31,140 --> 00:36:33,190 Binær søgning i bedste fald? 978 00:36:33,190 --> 00:36:36,290 Det er også 1, hvis det bare sker for at være i den meget midterste af array, eller 979 00:36:36,290 --> 00:36:37,810 midten af ​​telefonbogen. 980 00:36:37,810 --> 00:36:39,710 Nu lad os gøre boble slags. 981 00:36:39,710 --> 00:36:42,570 Så igen, nu er vi ind i sorterer, ikke de søgninger. 982 00:36:42,570 --> 00:36:47,220 >> I værste fald, hvor mange skridt, vi fordring boble sortere kommer til at tage? 983 00:36:47,220 --> 00:36:48,410 n squared. 984 00:36:48,410 --> 00:36:49,200 Så jeg har tænkt mig at trække det. 985 00:36:49,200 --> 00:36:51,710 Ooh, min håndskrift ser endnu værre når det er forventes, at store. 986 00:36:51,710 --> 00:36:52,510 Ok. 987 00:36:52,510 --> 00:36:53,570 Så det n potens. 988 00:36:53,570 --> 00:36:59,460 Og i bedste tilfælde af boble sortere, hvor mange skridt vil det tage? 989 00:36:59,460 --> 00:37:00,980 1, jeg hørte. 990 00:37:00,980 --> 00:37:01,760 >> SPEAKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. MALAN: n, jeg hørte. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. MALAN: 2, jeg hørte. 994 00:37:05,010 --> 00:37:06,670 Må jeg hører 3? 995 00:37:06,670 --> 00:37:07,080 Ok. 996 00:37:07,080 --> 00:37:11,390 Så jeg har hørt 1, n, 2, men lad os samle bortset mindst den første af disse 997 00:37:11,390 --> 00:37:12,330 forslag, 1.. 998 00:37:12,330 --> 00:37:15,370 Det er ikke en dårlig instinkt, fordi det slags følger et mønster her. 999 00:37:15,370 --> 00:37:19,670 Men hvis det tager kun 1 trin, hvordan i verden kunne jeg påstå, at listen 1000 00:37:19,670 --> 00:37:22,900 sorteres, fordi hvis jeg kun tillades at tage 1 skridt, hvor mange elementer 1001 00:37:22,900 --> 00:37:25,230 kunne jeg faktisk tjekke for at være sikker? 1002 00:37:25,230 --> 00:37:28,270 Nå, bare 1, hvilket betyder, at der er n minus 1 elementer, der kan være ude af 1003 00:37:28,270 --> 00:37:31,310 orden, og jeg bare på tro efter ser på 1 element, at 1004 00:37:31,310 --> 00:37:31,850 ting er sorteret. 1005 00:37:31,850 --> 00:37:33,930 Så 1 er ikke korrekt her. 1006 00:37:33,930 --> 00:37:35,710 Så minimalt, hvor mange skal jeg til at se på? 1007 00:37:35,710 --> 00:37:36,680 >> [Interposing STEMMER] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. MALAN: n minus 1, eller virkelig, n, fordi jeg har brug for at se på alle 1009 00:37:40,160 --> 00:37:42,190 element til at sikre, at det er ikke i orden. 1010 00:37:42,190 --> 00:37:44,750 Men igen, vil vi sortere i wave vores hænder på de mindre tal og 1011 00:37:44,750 --> 00:37:47,100 antage, at n bliver store, de er uinteressant alligevel. 1012 00:37:47,100 --> 00:37:48,380 Så det er boble slags. 1013 00:37:48,380 --> 00:37:49,830 Og nu, lad os gøre disse to sidste. 1014 00:37:49,830 --> 00:37:53,520 Valg sortere, og så vil vi gøre indsættelse slags. 1015 00:37:53,520 --> 00:37:57,160 Og så vil vi blæse din sind med noget meget 1016 00:37:57,160 --> 00:37:58,926 bedre end alle disse. 1017 00:37:58,926 --> 00:38:00,410 Ok. 1018 00:38:00,410 --> 00:38:04,700 >> Hvad er det værste tilfælde kører tidspunktet for udvælgelsen slags? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n potens. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n square, jeg hører. 1021 00:38:06,710 --> 00:38:09,790 Men hvorfor n kvadreret, intuitivt? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Fordi vi gjorde det bare. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Fordi vi gjorde det bare. 1024 00:38:12,260 --> 00:38:12,550 OK. 1025 00:38:12,550 --> 00:38:13,380 Godt svar. 1026 00:38:13,380 --> 00:38:16,660 Men intuitivt, hvorfor er valg sortere n kvadreret? 1027 00:38:16,660 --> 00:38:18,980 Hvad gjorde vi nødt til at gøre igen og igen? 1028 00:38:18,980 --> 00:38:22,570 Vi har måttet holde scanning gennem, er dig den mindste, er du den 1029 00:38:22,570 --> 00:38:24,020 mindste, er du den mindste. 1030 00:38:24,020 --> 00:38:27,480 Og indrømmet, vi var i stand til at tage n trin, så n minus 1, og derefter n minus 2. 1031 00:38:27,480 --> 00:38:30,700 Men hvis du slags tilføje dem alle op, eller tage det på tro, som jeg har tilføjet 1032 00:38:30,700 --> 00:38:34,810 dem op på forhånd, får vi nogenlunde n kvadreret minus nogle mindre tal. 1033 00:38:34,810 --> 00:38:36,730 Så jeg har tænkt mig at kalde denne n potens. 1034 00:38:36,730 --> 00:38:39,530 Men med valget slags i den bedste fald hvor mange skridt det er 1035 00:38:39,530 --> 00:38:40,632 kommer til at tage mig? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [uhørligt] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: Det er desværre stadig n kvadreret, right? 1038 00:38:44,350 --> 00:38:49,590 Fordi hvis jeg vælger den mindste element, og vi havde syv personer her, 1039 00:38:49,590 --> 00:38:53,280 Jeg kender kun, når jeg kommer til de meget ende, at jeg har fundet den mindste 1040 00:38:53,280 --> 00:38:55,670 nummer, hvor han eller hun kan have været. 1041 00:38:55,670 --> 00:38:58,820 Men hvordan finder jeg det næste mindste tal? 1042 00:38:58,820 --> 00:39:00,160 Jeg er nødt til at gøre en anden pass. 1043 00:39:00,160 --> 00:39:04,810 Så i bedste fald, hvad er input til udvælgelse sortere? 1044 00:39:04,810 --> 00:39:07,830 Det er en allerede sortere listen, nummer et, nummer to, nummer tre, nummer fire. 1045 00:39:07,830 --> 00:39:08,600 Men jeg er en computer. 1046 00:39:08,600 --> 00:39:10,190 Jeg kan kun se på en ting ad gangen. 1047 00:39:10,190 --> 00:39:12,465 Jeg kan ikke sortere i at tage et skridt tilbage som et menneske og sige, 1048 00:39:12,465 --> 00:39:14,030 ooh, det ser korrekt. 1049 00:39:14,030 --> 00:39:17,580 >> Jeg kan kun træffe afgørelse korrekthed udvælgelse sortere ved at vælge 1050 00:39:17,580 --> 00:39:18,370 mindste tal. 1051 00:39:18,370 --> 00:39:21,390 Men selv hvis jeg finder nummer et første, hvis jeg ikke kender noget andet om 1052 00:39:21,390 --> 00:39:24,460 de andre numre, som jeg ikke, alt hvad jeg vide, at jeg har været afleveret et array 1053 00:39:24,460 --> 00:39:27,930 eller et sæt af døre bag hvilke tal, den eneste måde jeg ved, at en 1054 00:39:27,930 --> 00:39:28,680 var den mindste? 1055 00:39:28,680 --> 00:39:32,440 Hvis jeg får hele vejen her og indse, damn, den ene var faktisk den mindste. 1056 00:39:32,440 --> 00:39:34,870 >> Men hvordan kan jeg så afgøre, at to er den næstmindste? 1057 00:39:34,870 --> 00:39:38,350 Ved at gøre det samme ineffektivitet igen og igen. 1058 00:39:38,350 --> 00:39:42,210 Så til sidst, med indsættelse slags, hvordan, i værste fald, 1059 00:39:42,210 --> 00:39:44,990 vi siger det udfører? 1060 00:39:44,990 --> 00:39:49,100 Det er for n potens. 1061 00:39:49,100 --> 00:39:53,020 Og hvad med den bedste sag? 1062 00:39:53,020 --> 00:39:56,282 Vi vil overlade som en cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Vi vil fylde i den tomme næste gang, men lad mig først foreslå, at vi 1064 00:40:00,090 --> 00:40:02,620 fundamentalt gøre det bedre end alle disse, okay? 1065 00:40:02,620 --> 00:40:05,220 >> Så tænk selv, hvad indsættelse sortere kommer til at være. 1066 00:40:05,220 --> 00:40:06,910 Nå, det var ikke meget dramatisk, fordi jeg er den eneste 1067 00:40:06,910 --> 00:40:08,970 der så ændringen. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 OK. 1070 00:40:10,420 --> 00:40:12,615 Så her har vi en noget anderledes demonstration. 1071 00:40:12,615 --> 00:40:16,580 Hvis jeg zoome ind her, vil du se, at der på venstre vi har boble sortere, i 1072 00:40:16,580 --> 00:40:20,740 midten har vi valg sortere og på længst til højre, vi har noget, vi 1073 00:40:20,740 --> 00:40:23,380 har ikke kigget på endnu kaldet fusionere slags. 1074 00:40:23,380 --> 00:40:26,080 Men overveje, hvad vi har været gør her hidtil i dag. 1075 00:40:26,080 --> 00:40:29,200 Da Jennifer først kom op på scenen, vi gik gennem rækken af ​​numre 1076 00:40:29,200 --> 00:40:33,750 igen og igen, med lineær søgning, og vi fik lineær køretid, big O 1077 00:40:33,750 --> 00:40:35,100 n, så at sige. 1078 00:40:35,100 --> 00:40:41,000 >> Når vi nu overveje den første uge af klasse, da vi havde del og hersk, 1079 00:40:41,000 --> 00:40:43,740 og vi havde telefonbogen tåreflåd, og Jennifer, og vi kollektivt 1080 00:40:43,740 --> 00:40:47,500 gearede at centrale indsigt, som var at gentage dig selv igen og igen af 1081 00:40:47,500 --> 00:40:50,930 en eller anden måde at smide væk, smide, smide halvdelen af ​​problemet, eller 1082 00:40:50,930 --> 00:40:55,320 generelt, dividere et problem i halve, og derefter behandle den mindre stykke af 1083 00:40:55,320 --> 00:40:59,630 problemet så begrebsmæssigt ækvivalente til den anden, en eller anden måde gjorde vi 1084 00:40:59,630 --> 00:41:00,910 fundamentalt bedre. 1085 00:41:00,910 --> 00:41:04,720 Men med boble slags, med udvælgelse sortere, med indsættelse sortere, vi har måske 1086 00:41:04,720 --> 00:41:06,560 ingen sådanne indsigter, Jennifer gjorde. 1087 00:41:06,560 --> 00:41:10,220 Vi temmelig blot gik tilbage og frem en hel masse gange, og vi 1088 00:41:10,220 --> 00:41:12,650 sammenknebne tingene lidt, bytte i denne rækkefølge, måske 1089 00:41:12,650 --> 00:41:13,730 indsætter eller vælge. 1090 00:41:13,730 --> 00:41:16,950 Men i slutningen af ​​dagen, gjorde jeg en masse akavet walking frem og tilbage. 1091 00:41:16,950 --> 00:41:21,160 Vi gjorde ikke rigtig udnytte noget Smart ligesom Jennifer gjorde ligesom at dividere 1092 00:41:21,160 --> 00:41:22,040 og erobre. 1093 00:41:22,040 --> 00:41:25,620 >> Så fusionere sortere, derimod, som vi vil ikke se til næste uge, går det 1094 00:41:25,620 --> 00:41:29,540 at udnytte, at centrale idé ved at dividere input, og derefter halvering, og derefter 1095 00:41:29,540 --> 00:41:30,580 halvering, og derefter halveret. 1096 00:41:30,580 --> 00:41:34,590 Og på hver iteration af denne løkke, sortering af venstre halvdel og højre 1097 00:41:34,590 --> 00:41:38,200 halvdel, så den venstre halvdel af venstre halvdel, og den højre halvdel af den venstre, så 1098 00:41:38,200 --> 00:41:40,990 den venstre halvdel af den højre halvdel, og den højre halvdel af den højre halvdel. 1099 00:41:40,990 --> 00:41:42,840 Og gentage igen og igen. 1100 00:41:42,840 --> 00:41:46,170 >> Så du vil se denne visuelt, men dette er, hvad der venter os i næste uge. 1101 00:41:46,170 --> 00:41:49,760 Og generelt, når vi tænker lidt lidt hårdere på en sådan problem. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Vi har n kvadreret på venstre side, n kvadreret i midten, og n 1104 00:41:57,970 --> 00:41:59,400 log n til højre. 1105 00:41:59,400 --> 00:42:00,590 Så der er din rigtige cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Vi vil se dig på mandag. 1107 00:42:02,040 --> 00:42:05,163 >> [Applaus]