1 00:00:00,000 --> 00:00:11,100 >> [Musikk spilles] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. MALAN: All right. 3 00:00:11,490 --> 00:00:12,170 Så velkommen tilbake. 4 00:00:12,170 --> 00:00:15,180 Dette er CS50, og det er slutten av uke tre. 5 00:00:15,180 --> 00:00:17,770 >> Så husker i de siste ukene, vi har vært å bruke ganske mye 6 00:00:17,770 --> 00:00:20,820 tid på C, på programmering, på syntaks. 7 00:00:20,820 --> 00:00:24,680 Og det er ganske vanlig, hvis du fremdeles sliter med Problem Set 2, for å være 8 00:00:24,680 --> 00:00:25,950 stanger hodet mot veggen. 9 00:00:25,950 --> 00:00:28,310 Det er kryptisk utseende feilmeldinger og bugs som du 10 00:00:28,310 --> 00:00:29,220 kan ikke helt jage ned. 11 00:00:29,220 --> 00:00:32,310 Fordi, være trygg, at i bare en par ukers tid vil du se tilbake på 12 00:00:32,310 --> 00:00:35,930 ting som Caesar, og [? V-genair,?] kanskje til og med sprekke, og 13 00:00:35,930 --> 00:00:40,050 innse hvor langt du har kommet i en kort periode. 14 00:00:40,050 --> 00:00:43,670 Så hvis det er noen trøst, henge der for nå. 15 00:00:43,670 --> 00:00:46,610 >> I dag, men vi begynner å overgang til ting høyere nivå. 16 00:00:46,610 --> 00:00:49,820 Og vi begynner å ta for gitt at dere vet hvordan man programmerer, eller i 17 00:00:49,820 --> 00:00:52,090 minst begynnelsen av at komfort nivå. 18 00:00:52,090 --> 00:00:56,520 Og vi begynner å tenke på hvordan vi kan gå om å designe programmer mer 19 00:00:56,520 --> 00:00:57,440 effektivt. 20 00:00:57,440 --> 00:01:01,090 Hvordan vi kan gå om å optimalisere effektiviteten av våre algoritmer, og 21 00:01:01,090 --> 00:01:03,110 vanligvis løse mer interessante problemstillinger. 22 00:01:03,110 --> 00:01:06,850 Og begynner å ta for gitt at hvis vi ville, kunne vi kode opp noe 23 00:01:06,850 --> 00:01:08,350 av eksemplene vi har i tankene. 24 00:01:08,350 --> 00:01:11,430 Så i dag har vi ikke tar på tastaturet for en hvilken som helst form for kode. 25 00:01:11,430 --> 00:01:15,150 Det vil være mye høyere nivå, og til slutt, om problemløsning. 26 00:01:15,150 --> 00:01:20,490 >> Så for å komme til det punktet, la meg foreslå at følgende syv 27 00:01:20,490 --> 00:01:24,290 rektangler representerer sju dører, bak som er en hel haug med 28 00:01:24,290 --> 00:01:26,340 tall, blant disse er tallet 50.. 29 00:01:26,340 --> 00:01:30,470 La meg projisere dette på denne skjermen her også. 30 00:01:30,470 --> 00:01:36,770 Og foreslå at vi trenger en frivillig til bidra til å finne meg et nummer foran 31 00:01:36,770 --> 00:01:38,140 internett her for å se. 32 00:01:38,140 --> 00:01:40,755 Kom opp i rosa. 33 00:01:40,755 --> 00:01:43,050 OK. 34 00:01:43,050 --> 00:01:43,930 Hva heter du? 35 00:01:43,930 --> 00:01:44,850 >> JENNIFER: [uhørlig] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. MALAN: Beklager? 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 Greit, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Hyggelig å treffe deg. 41 00:01:47,630 --> 00:01:48,370 Kom opp. 42 00:01:48,370 --> 00:01:52,430 Så disse her er sju dører, og hva Jeg vil at du skal gjøre for oss her, 43 00:01:52,430 --> 00:01:56,560 foran alle dine klassekamerater, er å finne oss nummeret, 50. 44 00:01:56,560 --> 00:02:00,860 For å finne et nummer, kan du titte bak noen av disse dørene ved å trykke 45 00:02:00,860 --> 00:02:03,030 på en av dørene, og den vil avsløre sin nummer. 46 00:02:03,030 --> 00:02:06,080 Og la oss se hvor raskt du finner oss 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 Pent gjort. 54 00:02:17,350 --> 00:02:18,040 OK. 55 00:02:18,040 --> 00:02:19,906 Applaus for Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [APPLAUSE] 57 00:02:21,530 --> 00:02:22,320 >> OK. 58 00:02:22,320 --> 00:02:25,254 Så hva var din strategi for finne nummeret, 50? 59 00:02:25,254 --> 00:02:27,222 >> JENNIFER: Um, jeg tenkte kanskje hvis - 60 00:02:27,222 --> 00:02:27,714 [Uhørlig] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. MALAN: Oh. 62 00:02:28,206 --> 00:02:29,630 Gi det ett sekund. 63 00:02:29,630 --> 00:02:32,420 Så var din strategi for finne nummeret, 50? 64 00:02:32,420 --> 00:02:34,760 >> JENNIFER: Så jeg bare starte på begynner å se hva det første tallet 65 00:02:34,760 --> 00:02:38,590 var, og så tenkte jeg, kanskje hvis de er sortert, vil jeg bare holde 66 00:02:38,590 --> 00:02:39,970 tappe høyere opp? 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 å ha funnet det å være tilfelle. 69 00:02:42,910 --> 00:02:45,670 Selv om, la oss skrelle tilbake lagene bare en liten bit, og du vil gå 70 00:02:45,670 --> 00:02:47,640 videre og avsløre de andre dørene du kunne ha valgt? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> JENNIFER: Åh, kjæ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 bare hadde flaks. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. MALAN: Så du hadde flaks. 76 00:02:55,270 --> 00:02:55,710 OK. 77 00:02:55,710 --> 00:02:56,795 Så ikke ille. 78 00:02:56,795 --> 00:02:58,750 Men det er en interessant innsikt, ikke sant? 79 00:02:58,750 --> 00:03:01,870 Hvis du antok, og du fikk, faktisk litt heldig der. 80 00:03:01,870 --> 00:03:05,350 Men hvis du antok at tallene var sorteres, kan du være mer presis 81 00:03:05,350 --> 00:03:08,750 om hvordan det påvirket din oppførsel? 82 00:03:08,750 --> 00:03:11,715 >> JENNIFER: Så hvis de ble sortert, jeg tenkte kanskje minst til størst. 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 dette endte opp med å bli virkelig stor, så største til minste. 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 minste, eller minste til største. 87 00:03:18,170 --> 00:03:21,990 Men la meg foreslå si at du hadde fått uheldig, og anta at de 88 00:03:21,990 --> 00:03:26,840 var ikke, faktisk, sortert, hvor mange av disse dørene har du kanskje måtte titte 89 00:03:26,840 --> 00:03:28,590 bak i det verste tilfellet? 90 00:03:28,590 --> 00:03:29,860 >> JENNIFER: Alle av dem. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. MALAN: Alle av dem. 92 00:03:30,420 --> 00:03:31,740 Så la oss generalisere det som n. 93 00:03:31,740 --> 00:03:34,790 Det skjer for å være 7, men la oss mer generelt si at det er n dører på 94 00:03:34,790 --> 00:03:35,650 skjermen her. 95 00:03:35,650 --> 00:03:40,110 Så i verste fall, ville du ha å se bak syv dører, eller n dører. 96 00:03:40,110 --> 00:03:44,140 Og så dette er virkelig, det er litt av flaks i dag, men det er egentlig en lineær 97 00:03:44,140 --> 00:03:46,440 algoritme slags, selv om du var slags hoppe rundt. 98 00:03:46,440 --> 00:03:47,080 Er det rettferdig? 99 00:03:47,080 --> 00:03:47,500 >> JENNIFER: Yeah. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. MALAN: Vel, la meg se om strategi endringer hvis jeg flytter oss til 101 00:03:50,000 --> 00:03:52,190 vår andre eksemplet her med 7 ulike dører. 102 00:03:52,190 --> 00:03:55,240 Samme tallene, men dette gang de er sortert. 103 00:03:55,240 --> 00:03:58,350 Hva er din strategi her kommer til å bli, prøver å sette ut av tankene dine hva 104 00:03:58,350 --> 00:03:59,310 de andre tallene var - 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: La oss starte med den første. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. MALAN: All right. 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 Nå hvor du skal gå, og hvorfor? 112 00:04:08,810 --> 00:04:10,040 >> JENNIFER: 4 er virkelig små. 113 00:04:10,040 --> 00:04:12,500 Så hvis de er liksom kanskje minste til største, bør det 114 00:04:12,500 --> 00:04:13,290 være 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 La oss se, som du tror? 117 00:04:15,990 --> 00:04:19,050 >> JENNIFER: Prøv den siste. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. MALAN: Veldig pent gjort. 120 00:04:20,880 --> 00:04:21,860 OK. 121 00:04:21,860 --> 00:04:23,010 >> [APPLAUSE] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. MALAN: OK. 123 00:04:24,310 --> 00:04:26,790 Så du faktisk gjør dette forferdelig, fordi du er 124 00:04:26,790 --> 00:04:27,700 gjør det veldig bra. 125 00:04:27,700 --> 00:04:31,150 Som etterlater oss i stand til å gjøre enkelte punkter. 126 00:04:31,150 --> 00:04:32,565 Så la oss prøve å rulle tilbake hit. 127 00:04:32,565 --> 00:04:34,560 >> JENNIFER: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. MALAN: Very well gjort, likevel. 129 00:04:35,980 --> 00:04:39,060 Så du startet i begynnelsen, du så at det var fire, så du 130 00:04:39,060 --> 00:04:40,240 flyttet til enden. 131 00:04:40,240 --> 00:04:42,320 Men antar at du ikke får heldig der, og antar 50 132 00:04:42,320 --> 00:04:42,890 var et annet sted. 133 00:04:42,890 --> 00:04:46,190 Hva din tredje trinnet har vært? 134 00:04:46,190 --> 00:04:47,680 >> JENNIFER: Gå tilbake til begynnelsen. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. MALAN: Gå tilbake til begynnelsen. 136 00:04:48,320 --> 00:04:51,320 OK, så du ville har rørt denne døren, som var åtte. 137 00:04:51,320 --> 00:04:51,660 OK. 138 00:04:51,660 --> 00:04:52,650 Så det er ikke 50. 139 00:04:52,650 --> 00:04:55,380 Hvor ville du ha sett neste? 140 00:04:55,380 --> 00:04:56,720 >> JENNIFER: Hvis jeg ikke vet de sortert. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. MALAN: Riktig. 142 00:04:57,005 --> 00:04:58,490 Vel, hvis du visste de ble sortert - 143 00:04:58,490 --> 00:04:58,700 >> JENNIFER: Oh, visste, ja. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. MALAN: - men det gjorde du ikke vet hvor 50 var ennå? 145 00:05:00,910 --> 00:05:01,785 >> JENNIFER: Bare fortsett. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. MALAN: All right. 147 00:05:02,130 --> 00:05:02,520 OK. 148 00:05:02,520 --> 00:05:03,800 Holde det gående. 149 00:05:03,800 --> 00:05:05,270 OK, at jeg kan jobbe med. 150 00:05:05,270 --> 00:05:05,610 >> JENNIFER: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. MALAN: Nå, hvis du bare kommer til å holde det gående, hva er din 152 00:05:07,210 --> 00:05:09,680 algoritme devolving støttet inn. 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 la meg foreslå, la me satt på stedet. 156 00:05:13,480 --> 00:05:14,900 La meg oppdatere siden. 157 00:05:14,900 --> 00:05:17,120 samme nummer, samme arrangement, samme dører. 158 00:05:17,120 --> 00:05:21,350 Men tenk tilbake til den første dagen i klasse når vi rev en telefonbok 159 00:05:21,350 --> 00:05:25,480 halvparten, liksom, og hva som var vår strategi der? 160 00:05:25,480 --> 00:05:26,450 >> JENNIFER: Start på 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 på midten. 163 00:05:27,610 --> 00:05:28,790 Så la oss gå videre og late som. 164 00:05:28,790 --> 00:05:30,720 Begynn på midten av avslørende at døren. 165 00:05:30,720 --> 00:05:31,660 Så tallet 16. 166 00:05:31,660 --> 00:05:35,290 Så hva ville den sterke fyren har gjort, som rev telefonboken i to, 167 00:05:35,290 --> 00:05:38,450 for å komme til neste gjetning? 168 00:05:38,450 --> 00:05:39,400 >> JENNIFER: Gå i denne omgangen. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. MALAN: Og hvorfor til høyre? 170 00:05:41,700 --> 00:05:43,900 >> JENNIFER: Hvis de var slags minste til største, så 50 bør være 171 00:05:43,900 --> 00:05:44,720 på at slutten. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. MALAN: Good. 173 00:05:44,920 --> 00:05:45,390 Helt rimelig. 174 00:05:45,390 --> 00:05:48,380 Så ut som en telefonkatalog, går du til rett i motsetning til venstre, men her 175 00:05:48,380 --> 00:05:49,500 er nøkkelen takeaway. 176 00:05:49,500 --> 00:05:53,930 Du kan nå kaste bort, eller rive av, halvparten av dette problemet, slik at du ikke 177 00:05:53,930 --> 00:05:55,970 med syv dører, men egentlig med tre like. 178 00:05:55,970 --> 00:05:57,870 Som er omtrent halvparten av Størrelsen av problemet. 179 00:05:57,870 --> 00:05:58,350 OK. 180 00:05:58,350 --> 00:06:01,890 Så nå hva du ville ha gjort etter at du går rett? 181 00:06:01,890 --> 00:06:05,870 >> JENNIFER: Så 16 er fortsatt ganske liten, i forhold til 50, så kanskje jeg skal prøve, 182 00:06:05,870 --> 00:06:06,700 som, en dette. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. MALAN: All right. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Ok, så nå hva er din instinkt som forteller deg? 186 00:06:10,830 --> 00:06:12,100 >> JENNIFER: Jeg kan kaste bort 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 Bra, kan du kaste bort venstre halvdel der. 189 00:06:14,212 --> 00:06:14,890 >> JENNIFER: - plukke dette. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. MALAN: Og høyre. 191 00:06:15,530 --> 00:06:15,760 >> JENNIFER: Yeah. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. MALAN: Så selv om det er vanskelig å se kanskje, når det er bare 193 00:06:17,820 --> 00:06:21,320 7 dører, tenk, nå, konsistensen av 194 00:06:21,320 --> 00:06:22,620 algoritme du bare søkt. 195 00:06:22,620 --> 00:06:24,510 I den forrige saken, gjorde du få heldige, som var stor. 196 00:06:24,510 --> 00:06:26,540 Men det gjorde du bruke en heuristisk, Jeg vil si. 197 00:06:26,540 --> 00:06:29,150 Du brukte slags instinktene dine, og å vite det sortert, hvis det er ganske 198 00:06:29,150 --> 00:06:31,600 små i begynnelsen, selvsagt, har vi må gå mer til høyre. 199 00:06:31,600 --> 00:06:34,990 Men på en måte, fikk du heldig, fordi kanskje dette var nummer 100, 200 00:06:34,990 --> 00:06:36,220 og kanskje 50 var mer i midten. 201 00:06:36,220 --> 00:06:37,910 Kanskje 50 var selv over her. 202 00:06:37,910 --> 00:06:40,960 >> Men hva du gjorde et litt annerledes denne gangen var, gjorde du det samme 203 00:06:40,960 --> 00:06:42,150 igjen og igjen. 204 00:06:42,150 --> 00:06:45,310 Og jeg vil påstå at det du nettopp gitt, enskjønt påvirket av telefonen 205 00:06:45,310 --> 00:06:48,100 bok eksempel, er noe mye mer algoritmisk, og mye 206 00:06:48,100 --> 00:06:49,930 mindre spesiell rettssak. 207 00:06:49,930 --> 00:06:51,620 Mye mindre instinktiv. 208 00:06:51,620 --> 00:06:57,160 Så i slutten av dagen, hvordan ville du beskriver effektiviteten til 209 00:06:57,160 --> 00:07:00,530 første algoritme, hvor du gikk venstre til høyre, kontra 210 00:07:00,530 --> 00:07:03,430 andre algoritmen her? 211 00:07:03,430 --> 00:07:06,460 >> JENNIFER: Det ene burde, som, kanskje halvere tiden, eller enda mer, ja. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. MALAN: OK, kanskje enda mer. 213 00:07:07,320 --> 00:07:10,150 La oss presse litt hardere på det. 214 00:07:10,150 --> 00:07:13,030 Hva egentlig, hvis vi fortsetter denne logikk, vi definitivt halvert 215 00:07:13,030 --> 00:07:15,830 kjøretid med denne andre algoritmen ved å kaste bort halvparten av 216 00:07:15,830 --> 00:07:18,470 tall, men hva gjorde vi på neste iterasjon, da Jennifer avslørt 217 00:07:18,470 --> 00:07:20,615 det andre tallet? 218 00:07:20,615 --> 00:07:22,830 >> Vi halvert numrene på dørene igjen. 219 00:07:22,830 --> 00:07:25,270 Og hva gjorde vi etter det, hvis det var flere dører for å spille med? 220 00:07:25,270 --> 00:07:27,520 Vi ville halvere dem, og igjen, og igjen og igjen. 221 00:07:27,520 --> 00:07:30,420 Og dette var akkurat som dere alle stå opp på den første uken av 222 00:07:30,420 --> 00:07:33,000 klasse, halvparten av dere sitte ned, halvparten av dere sitte ned, halvparten av dere 223 00:07:33,000 --> 00:07:35,440 sitte ned, helt til en ensom sjel sto. 224 00:07:35,440 --> 00:07:39,050 Og vi sa at kjøretiden det, var antall skritt som tok 225 00:07:39,050 --> 00:07:40,430 på rekkefølgen av hva? 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: Så log base 2 av n, eller bare enklere, logg av n. 228 00:07:43,970 --> 00:07:45,060 Så noe logaritmisk. 229 00:07:45,060 --> 00:07:48,380 Og grafen var ikke en rett linje som bare ble verre og verre, var det 230 00:07:48,380 --> 00:07:52,490 dette interessant kurve som ikke får så dårlig over tid. 231 00:07:52,490 --> 00:07:53,910 Så la oss holde fast på denne ideen. 232 00:07:53,910 --> 00:07:54,690 La oss takke Jennifer. 233 00:07:54,690 --> 00:07:56,150 Takk så mye for å komme videre opp. 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 i dag, men vi har CS50 stress baller. 237 00:08:02,925 --> 00:08:03,420 >> JENNIFER: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. MALAN: Greit, her. 239 00:08:04,410 --> 00:08:06,545 Takk for at du pådra stresset opp her. 240 00:08:06,545 --> 00:08:07,350 OK. 241 00:08:07,350 --> 00:08:10,620 Så la oss se om vi ikke kan nå formalisere dette litt mer. 242 00:08:10,620 --> 00:08:14,820 Så igjen, var det vi nettopp gjorde hovedsak det samme som vi gjorde 243 00:08:14,820 --> 00:08:16,660 i den første uken. 244 00:08:16,660 --> 00:08:23,780 Men heller enn å ende med bare en lineær algoritme, som vi avbildet 245 00:08:23,780 --> 00:08:27,210 som tidligere er denne rett linje, der, hvis vi legger enda en dør på 246 00:08:27,210 --> 00:08:29,610 skjermen, da Jennifer ville har måttet se, potensielt, 247 00:08:29,610 --> 00:08:30,600 bak en mer dør. 248 00:08:30,600 --> 00:08:33,490 Hvis vi setter to dører, kan hun ha å se bak to dører. 249 00:08:33,490 --> 00:08:35,990 >> Og så var det denne lineær Forholdet mellom størrelsen på 250 00:08:35,990 --> 00:08:39,059 problemet på, si, x-aksen, og hvor lang tid det tar å 251 00:08:39,059 --> 00:08:40,440 løse på y. 252 00:08:40,440 --> 00:08:43,330 Men bildet jeg hentydet til tidligere var denne grønne linjen. 253 00:08:43,330 --> 00:08:45,970 Grønn bevisst, fordi det bare føltes bedre. 254 00:08:45,970 --> 00:08:49,790 I teorien algoritmen, når vi gjorde det med telefonboken, når vi gjorde det 255 00:08:49,790 --> 00:08:52,420 med dere telle hverandre, og i det andre tilfellet, når Jennifer bare 256 00:08:52,420 --> 00:08:55,250 gjorde det opp her, var det liksom av fundamentalt bedre. 257 00:08:55,250 --> 00:08:57,180 Fordi det var ikke bare dobbelt så fort. 258 00:08:57,180 --> 00:08:58,870 Det var ikke selv fire ganger så fort. 259 00:08:58,870 --> 00:09:03,290 Det var fullstendig avhengig av hva Størrelsen på innspill var, om hvor mange 260 00:09:03,290 --> 00:09:05,220 trinnene det til slutt tok. 261 00:09:05,220 --> 00:09:08,040 >> Og så denne enkle ideen om at vi alle tok for gitt med telefonboken, 262 00:09:08,040 --> 00:09:10,200 På samme måte kan brukes til noe som dette. 263 00:09:10,200 --> 00:09:12,380 Og dette kan være mer tilfeldig kjent som, som du kanskje 264 00:09:12,380 --> 00:09:13,940 forestille seg, splitt og hersk. 265 00:09:13,940 --> 00:09:16,390 Ikke ulikt det vi gjorde, selvfølgelig, med telefonboken. 266 00:09:16,390 --> 00:09:18,300 >> Men pseudokode, husker, var dette. 267 00:09:18,300 --> 00:09:21,800 Så vi vil ikke gjøre dette igjen, men husker den første uken, sto oss alle opp 268 00:09:21,800 --> 00:09:25,140 og deretter halvparten av dere satte seg, halvparten av du satte meg ned, satte halvparten av dere ned. 269 00:09:25,140 --> 00:09:29,280 At algoritmen ble implementert i en litt av en utro måte, ved at det 270 00:09:29,280 --> 00:09:32,870 var ikke bare en av meg å telle, fundamentalt, mer effektivt. 271 00:09:32,870 --> 00:09:35,830 I så fall ble jeg utnytte en sekundær ressurs. 272 00:09:35,830 --> 00:09:39,470 Liksom, flere prosessorer, flere hjerner, flere smarte mennesker i 273 00:09:39,470 --> 00:09:42,740 Rommet var hjelpe meg å få fra noe lineær til noe 274 00:09:42,740 --> 00:09:45,190 logaritmisk, fra noe rød til noe grønt. 275 00:09:45,190 --> 00:09:48,650 >> Men i dette tilfellet, Jennifer alene kan fundamentalt forbedre den 276 00:09:48,650 --> 00:09:52,370 utførelsen av sitt første algoritme ved, igjen, bare tenke litt hardere. 277 00:09:52,370 --> 00:09:56,650 Og nå, når det gjelder tid til å implementere disse tingene, finne ut 278 00:09:56,650 --> 00:10:00,670 hva linjer med kode du kan skrive en slik at du kan gjenta dem igjen, og 279 00:10:00,670 --> 00:10:03,350 igjen og igjen, liksom i en looping mote. 280 00:10:03,350 --> 00:10:06,370 Fordi du ikke kommer til å ha luksus, som Jennifer gjorde i starten, til 281 00:10:06,370 --> 00:10:10,460 bare ha en hel haug med IFS og si: hmm, hvis dette første tallet er 4, 282 00:10:10,460 --> 00:10:11,800 la meg hoppe helt til slutten. 283 00:10:11,800 --> 00:10:14,180 Ooh, hvis det tallet er for stor, la meg flytte vilkårlig tilbake 284 00:10:14,180 --> 00:10:15,220 til det andre elementet. 285 00:10:15,220 --> 00:10:18,210 Du vil finne at det kommer til å være mye vanskeligere å formalisere hva vi mennesker 286 00:10:18,210 --> 00:10:21,270 tar for gitt som svært rimelig heuristikk, men en datamaskin er bare 287 00:10:21,270 --> 00:10:23,260 kommer til å gjøre det du ber den om. 288 00:10:23,260 --> 00:10:25,280 >> Nå har dette veldig interessant implikasjoner. 289 00:10:25,280 --> 00:10:29,950 Denne grafen er liksom ment å sortere av overvelde visuelt, men varsel, der 290 00:10:29,950 --> 00:10:32,230 er den rette linjen i denne grafen? 291 00:10:32,230 --> 00:10:35,330 Hvor er den lineære grafen som vi kaller n? 292 00:10:35,330 --> 00:10:37,580 Vel, det er liksom mot bunnen av dette bildet, ikke sant? 293 00:10:37,580 --> 00:10:40,500 Så alt vi har gjort er at vi har liksom zoomer ut til x-aksen og 294 00:10:40,500 --> 00:10:44,780 y-aksen for å prøve å få en oppfatning av hva andre typer kurver se ut. 295 00:10:44,780 --> 00:10:47,760 >> Og detaljene i den matematiske uttrykk i dag vil ikke saken så 296 00:10:47,760 --> 00:10:52,440 mye, men merker at det er mye algoritmer som er langt verre enn 297 00:10:52,440 --> 00:10:53,470 noe som er lineær. 298 00:10:53,470 --> 00:10:55,410 Faktisk ser n terninger ganske ille. 299 00:10:55,410 --> 00:10:58,400 2 til n ser ganske ille. n squared ser ganske ille. 300 00:10:58,400 --> 00:11:01,630 Og vi får se hva noen av dem kan være i virkeligheten i dag. 301 00:11:01,630 --> 00:11:05,430 Og log n føles ikke så ille, men bedre enn n er log base 2 av n. 302 00:11:05,430 --> 00:11:08,080 Men du vet, ville det ha vært enda mer fantastisk hvis Jennifer, eller hvis vi, 303 00:11:08,080 --> 00:11:12,910 den første uken, hadde kommet opp med noe som er logg over log n. 304 00:11:12,910 --> 00:11:15,880 >> Så med andre ord, det er hele denne utvalg av mulige løsninger på 305 00:11:15,880 --> 00:11:18,570 problemer, men selv her, varsel hva kommer til å skje. 306 00:11:18,570 --> 00:11:22,910 Når jeg zoome ut, hvilke av disse kurvene kommer til å vise seg å være den absolutt 307 00:11:22,910 --> 00:11:26,630 verste av de på skjermen nå? 308 00:11:26,630 --> 00:11:28,680 Så n terninger ser ganske dårlig i øyeblikket. 309 00:11:28,680 --> 00:11:32,470 Men hvis vi zoome ut og se mer av x og y-aksen, som kommer til å 310 00:11:32,470 --> 00:11:34,550 dominerer slutt? 311 00:11:34,550 --> 00:11:37,120 Så det faktisk viser seg at to til n, og du kan finne ut av dette bare ved 312 00:11:37,120 --> 00:11:39,990 plugge i noen stadig større tall, og du vil se at to til 313 00:11:39,990 --> 00:11:42,070 n, faktisk blir større mye raskere. 314 00:11:42,070 --> 00:11:45,530 Hvis vi virkelig zoome ut, en to til n algoritme suger absolutt. 315 00:11:45,530 --> 00:11:48,170 Jeg mener dette kommer til å ta ganske mye tid for 316 00:11:48,170 --> 00:11:49,460 datamaskin til churn gjennom. 317 00:11:49,460 --> 00:11:52,500 >> Men du får se over tid, spesielt med fremtidige oppgavesett og selv 318 00:11:52,500 --> 00:11:55,600 siste prosjekter, er dataene sett blir stor, ok? 319 00:11:55,600 --> 00:11:58,300 Selv i den første versjonen av Facebook, som antall par, og den 320 00:11:58,300 --> 00:12:01,840 antall registrerte brukere fikk store, du kan liksom telefonen det i og 321 00:12:01,840 --> 00:12:05,530 gjennomføre noe med lineær søk, eller en meget enkel sortering 322 00:12:05,530 --> 00:12:07,030 algoritme, som vi ser i dag. 323 00:12:07,030 --> 00:12:09,280 Du må begynne å tenke hardere og vanskeligere om disse problemene. 324 00:12:09,280 --> 00:12:12,070 Og hvilke typer problemer steder som Facebook og Google, og Microsoft, 325 00:12:12,070 --> 00:12:16,350 og andre arbeider på er akkurat disse slags stor data slags spørsmål 326 00:12:16,350 --> 00:12:18,530 stadig i disse dager. 327 00:12:18,530 --> 00:12:18,900 >> OK. 328 00:12:18,900 --> 00:12:23,800 Så Jennifer suksess i den andre algoritme, ærlig, gjorde hun utrolig 329 00:12:23,800 --> 00:12:26,110 Brønnen er den første gangen, men la oss skrive det som flaks slik at vi 330 00:12:26,110 --> 00:12:27,000 kan gjøre dette punktet. 331 00:12:27,000 --> 00:12:30,970 I det andre tilfellet, leveraged hun en algoritme som gjentas igjen og 332 00:12:30,970 --> 00:12:34,670 igjen, men hun tok for gitt en viss antakelse om at vi tillot 333 00:12:34,670 --> 00:12:39,370 henne, men hun utnyttet noen detalj andre gang at hun ikke har 334 00:12:39,370 --> 00:12:39,840 første gang. 335 00:12:39,840 --> 00:12:41,800 Som var det? 336 00:12:41,800 --> 00:12:43,050 >> At listen ble sortert. 337 00:12:43,050 --> 00:12:46,350 Så så snart listen ble sortert, vi hevder at Jennifer var i stand til å gjøre 338 00:12:46,350 --> 00:12:47,480 fundamentalt bedre. 339 00:12:47,480 --> 00:12:51,450 7 dører, ja, er ikke så interessant, men antar at det er vi 7 millioner dører. 340 00:12:51,450 --> 00:12:54,080 Logg av n er definitivt kommer til å utføre mye, mye 341 00:12:54,080 --> 00:12:55,610 raskere i det lange løp. 342 00:12:55,610 --> 00:12:58,880 Men hun måtte ha dører sortert for henne. 343 00:12:58,880 --> 00:13:02,320 Nå tok jeg meg den frihet å gjøre det på forhånd på dataskjermen 344 00:13:02,320 --> 00:13:05,160 her, men antar at Jennifer måtte gjøre det selv? 345 00:13:05,160 --> 00:13:10,120 Anta at dørene aktuelle representert data i en database, eller 346 00:13:10,120 --> 00:13:14,260 venner registrert for Facebook, eller noen nettsider på internett som 347 00:13:14,260 --> 00:13:16,880 ulike nettsteder kan trenge å indeksere eller søk over. 348 00:13:16,880 --> 00:13:20,940 >> Anta at du bare hadde en rådata satt, og det ble overlatt til deg, eller til 349 00:13:20,940 --> 00:13:23,010 Jennifer å gjøre at sorteringen? 350 00:13:23,010 --> 00:13:26,950 Det, snarere krever at vi svarer spørsmålet, vel, hvor mye tid 351 00:13:26,950 --> 00:13:31,080 ville ha tatt Jennifer, eller til og med meg, å sortere disse tallene på forhånd slik 352 00:13:31,080 --> 00:13:32,680 at hun kunne dra nytte av det? 353 00:13:32,680 --> 00:13:32,880 Høyre? 354 00:13:32,880 --> 00:13:36,620 Fordi implikasjon, selvfølgelig, er om det tar meg en stund å sortere 355 00:13:36,620 --> 00:13:40,800 tallene, hvem pokker bryr seg at du kan finne et tall som 50 så fort, 356 00:13:40,800 --> 00:13:44,850 som i Jennifer sak, hvis vi mer enn tatt over den totale mengden av tid 357 00:13:44,850 --> 00:13:46,920 det tok ved å sortere ting på forhånd? 358 00:13:46,920 --> 00:13:49,320 >> Så la oss se om vi kan ikke male bildet her. 359 00:13:49,320 --> 00:13:51,370 Jeg har en hel haug mer stress baller, hvis det hjelper 360 00:13:51,370 --> 00:13:52,270 bryte isen her. 361 00:13:52,270 --> 00:13:55,690 Og hvis du ikke har noe imot det vi trenger syv frivillig - 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 ikke trenger å bruke på skrivebord lamper, synes det. 365 00:13:59,250 --> 00:13:59,690 OK. 366 00:13:59,690 --> 00:14:01,530 Så hva med deg to foran. 367 00:14:01,530 --> 00:14:04,160 Hva med deg to gutta i ryggen. 368 00:14:04,160 --> 00:14:04,870 Så det er fire. 369 00:14:04,870 --> 00:14:09,890 Hva med deg foran fem, seks og sju. 370 00:14:09,890 --> 00:14:10,320 Akkurat der. 371 00:14:10,320 --> 00:14:13,260 Din venns peker deg ut, slik at du får premien. 372 00:14:13,260 --> 00:14:13,700 >> OK. 373 00:14:13,700 --> 00:14:14,410 Kom opp. 374 00:14:14,410 --> 00:14:17,120 Og hvorfor ikke vi har deg gutta kommer på over her. 375 00:14:17,120 --> 00:14:18,960 Jeg kommer til å gi deg hver et nummer. 376 00:14:18,960 --> 00:14:22,150 Og gå videre og ordne selv identisk til hva som er 377 00:14:22,150 --> 00:14:25,180 avbildet på skjermen. 378 00:14:25,180 --> 00:14:26,530 >> [Interposing STEMMER] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. MALAN: Oop, beklager. 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 Vel, her vi går. 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, sju. 386 00:14:37,770 --> 00:14:39,410 Å, dette er vanskelig. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Jeg skal 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 Takk for at du deltar. 391 00:14:44,611 --> 00:14:47,200 >> [APPLAUSE] 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, ett, tre, sju, fem. 395 00:14:51,970 --> 00:14:56,010 Perfeksjonere så vi har syv frivillige her som er lik i bredde til 396 00:14:56,010 --> 00:14:57,430 array som vi spiller med tidligere. 397 00:14:57,430 --> 00:14:59,470 Og jeg valgte syv grunner som vil være like 398 00:14:59,470 --> 00:15:00,840 praktisk i en liten bit. 399 00:15:00,840 --> 00:15:04,400 Og jeg kommer til å foreslå første som vi sorterer disse syv frivillige. 400 00:15:04,400 --> 00:15:06,786 Hvis du ønsker, først, for å si hei skjønt. 401 00:15:06,786 --> 00:15:08,970 Siden dette kommer til å bli en klosset flere minutter. 402 00:15:08,970 --> 00:15:10,370 Introdusere dere. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Hei, jeg er Grace. 404 00:15:10,980 --> 00:15:14,190 Jeg er en sophomore i Leverett House. 405 00:15:14,190 --> 00:15:14,620 >> Branson: Hei. 406 00:15:14,620 --> 00:15:15,620 Jeg er Branson. 407 00:15:15,620 --> 00:15:16,920 Jeg er en førsteårsstudent i Weld. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Hei. 410 00:15:20,230 --> 00:15:21,040 Jeg er Gabe. 411 00:15:21,040 --> 00:15:22,300 Jeg er en 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 en førsteårsstudent 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 en førsteårsstudent 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 en førsteårsstudent 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 en 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 Vel, takk til alle våre frivillige her så langt. 424 00:15:44,190 --> 00:15:47,110 Og utfordringen for hånden nå kommer å være å sortere av disse gutta, men da 425 00:15:47,110 --> 00:15:50,250 vi er nødt til å tenke litt hardt om hvor effektivt vi faktisk 426 00:15:50,250 --> 00:15:51,110 sortert dem. 427 00:15:51,110 --> 00:15:52,580 Så la oss først prøve dette. 428 00:15:52,580 --> 00:15:55,970 Dere kan se hverandres tall bare ved å plassere rundt hjørnene. 429 00:15:55,970 --> 00:15:59,380 Gå videre og ta noen sekunder, og sorter dere fra minste på 430 00:15:59,380 --> 00:16:01,240 igjen til største på høyre side. 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 Bra. 435 00:16:08,030 --> 00:16:09,370 Det var virkelig darn fort. 436 00:16:09,370 --> 00:16:14,040 Nå noen her, hva var algoritmen at disse gutta brukt? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: Minst 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 Minst til størst er liksom virkelig av objektiv, men jeg er ikke sikker på at det 440 00:16:18,070 --> 00:16:18,890 virkelig en algoritme. 441 00:16:18,890 --> 00:16:21,810 Minst til størst forteller ikke meg steg for steg hva du skal gjøre. 442 00:16:21,810 --> 00:16:22,833 Yeah? 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 enn nummeret ditt, og deretter flytte til 447 00:16:28,920 --> 00:16:29,680 til venstre for seg. 448 00:16:29,680 --> 00:16:32,800 Så det er nå får mer uttrykksfulle, mer som en algoritme, fordi du 449 00:16:32,800 --> 00:16:35,410 kan si, hvis dette, da. 450 00:16:35,410 --> 00:16:37,050 Så vi har en slags betinget konstruksjon. 451 00:16:37,050 --> 00:16:39,700 Og disse gutta syntes å gjøre at noen ganger, fordi noen av dere flyttet litt 452 00:16:39,700 --> 00:16:40,420 fra en avstand. 453 00:16:40,420 --> 00:16:43,410 Så det var antagelig en slags looping skjer i deres sinn. 454 00:16:43,410 --> 00:16:44,610 >> Men la oss prøve å formalisere det. 455 00:16:44,610 --> 00:16:47,540 Hvis dere kunne tilbakestille tilbake til denne ordningen. 456 00:16:47,540 --> 00:16:50,650 La oss se om vi ikke kan formalisere dette en bit, og deretter stille spørsmålet, bare 457 00:16:50,650 --> 00:16:51,580 hvor effektiv er dette? 458 00:16:51,580 --> 00:16:54,220 Selvfølgelig, når vi gjør dette saktere, det kommer til å føle seg så godt av 459 00:16:54,220 --> 00:16:57,210 en algoritme, men la oss se om vi kan sette våre fingre på den nøyaktige fremgangsmåten. 460 00:16:57,210 --> 00:16:58,670 >> Så dere to gutta er fire og to. 461 00:16:58,670 --> 00:17:01,020 Eller du riktig eller feil rekkefølge? 462 00:17:01,020 --> 00:17:01,900 Åpenbart feil. 463 00:17:01,900 --> 00:17:02,710 Så vi byttet. 464 00:17:02,710 --> 00:17:05,170 Nå skal jeg flytte på seg her og si, 05:56. 465 00:17:05,170 --> 00:17:06,240 Er du riktig eller gal? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Riktig. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. MALAN: Riktig. 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 Bytte. 471 00:17:09,630 --> 00:17:10,490 Så det er to swapper. 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 Bytte. 475 00:17:13,000 --> 00:17:13,930 Seks og sju? 476 00:17:13,930 --> 00:17:14,630 Ser bra ut. 477 00:17:14,630 --> 00:17:15,396 Syv og fem? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [uhørlig] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. MALAN: OK, bytte. 480 00:17:17,089 --> 00:17:19,770 Og sortert. 481 00:17:19,770 --> 00:17:19,980 OK. 482 00:17:19,980 --> 00:17:21,440 Så åpenbart ikke, ikke sant? 483 00:17:21,440 --> 00:17:22,470 Så det var mer å gå på. 484 00:17:22,470 --> 00:17:24,920 Men, ja, disse gutta, selv bare instinktivt. 485 00:17:24,920 --> 00:17:25,450 holdt flytte. 486 00:17:25,450 --> 00:17:27,710 De hadde ikke bare stoppe, når de korrigert ett problem. 487 00:17:27,710 --> 00:17:27,839 So. 488 00:17:27,839 --> 00:17:29,390 Ja, jeg kommer til å ha å gjøre det samme. 489 00:17:29,390 --> 00:17:32,720 Jeg er nødt til å sortere av spole tilbake til begynnelsen av dette problemet, 490 00:17:32,720 --> 00:17:35,630 eller begynnelsen av denne rekke mennesker, la oss begynne å kalle dem. 491 00:17:35,630 --> 00:17:38,366 >> Og nå hva skal min algoritme i andre omgang være? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Samme greia. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. MALAN: Samme greia. 494 00:17:39,940 --> 00:17:41,460 Og dette, jeg begynner å like, ikke sant? 495 00:17:41,460 --> 00:17:44,720 Så snart du kan finne deg selv gjør det samme igjen og igjen, det er 496 00:17:44,720 --> 00:17:47,890 bli mer lik en algoritme, og mindre menneskelig instinkt. 497 00:17:47,890 --> 00:17:48,680 >> Så nå er vi i gang igjen. 498 00:17:48,680 --> 00:17:49,870 To og fire? 499 00:17:49,870 --> 00:17:50,220 Nei. 500 00:17:50,220 --> 00:17:51,050 Fire og en? 501 00:17:51,050 --> 00:17:53,380 Ah, det var faktisk noen jobber fortsatt må gjøres. 502 00:17:53,380 --> 00:17:53,620 For og tre? 503 00:17:53,620 --> 00:17:54,572 Bra. 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 sju? 507 00:17:59,470 --> 00:18:00,970 OK, nå gjort. 508 00:18:00,970 --> 00:18:01,550 OK, nei. 509 00:18:01,550 --> 00:18:02,710 Jeg må gå tilbake. 510 00:18:02,710 --> 00:18:05,130 >> Så nå, igjen, vi gjør dette litt mer bevisst. 511 00:18:05,130 --> 00:18:08,700 Og nå er det bare én hjerne utførelse av denne algoritmen. 512 00:18:08,700 --> 00:18:10,290 En CPU, hvis du vil. 513 00:18:10,290 --> 00:18:13,090 Og ærlig talt, det er den eneste ressursen vi kommer til å ha tilgang til. 514 00:18:13,090 --> 00:18:16,280 Og når vi går tilbake til et tastatur og har noe sånt som C ved vår 515 00:18:16,280 --> 00:18:19,600 disposisjon, vi bare skriver et program som kan gjøre én ting om gangen. 516 00:18:19,600 --> 00:18:22,900 Mens disse gutta et øyeblikk siden, vi leveraged sin kollektive hjernekraft 517 00:18:22,900 --> 00:18:24,180 som dere gjorde i uke null. 518 00:18:24,180 --> 00:18:24,980 Så la oss fortsette å gjø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 sju. 525 00:18:30,510 --> 00:18:31,880 Ferdig? 526 00:18:31,880 --> 00:18:34,560 Så jeg er, men la meg spille djevelens advokat. 527 00:18:34,560 --> 00:18:37,950 Jeg gjør, hva slags datamaskin som bare gjort en pasning gjennom denne rekke 528 00:18:37,950 --> 00:18:40,225 mennesker, vet at jeg er ferdig? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: Nei. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. MALAN: Så hvorfor? 531 00:18:41,050 --> 00:18:46,900 Hva ville jeg trenger å gjøre for å konkludere avgjørende at jeg er ferdig? 532 00:18:46,900 --> 00:18:48,230 Sannsynligvis en mer pass. 533 00:18:48,230 --> 00:18:48,430 Høyre? 534 00:18:48,430 --> 00:18:51,760 Fordi alt jeg vet fra det forrige pass er at jeg rettet en feil. 535 00:18:51,760 --> 00:18:53,920 Og det betyr, kanskje det er fortsatt en annen feil 536 00:18:53,920 --> 00:18:54,840 at jeg trenger å korrigere. 537 00:18:54,840 --> 00:18:58,680 Så jeg kan bare være sikker ved å spole tilbake, og deretter sjekke, en til to, to og 538 00:18:58,680 --> 00:19:00,940 tre, tre og fire, fire og fem, fem og seks, seks og sju. 539 00:19:00,940 --> 00:19:02,510 OK, nå har jeg gjorde noe arbeid. 540 00:19:02,510 --> 00:19:05,990 >> Jeg kan sikkert huske at jeg gjorde ingen jobbe med noe som en variabel, 541 00:19:05,990 --> 00:19:06,975 liker en int. 542 00:19:06,975 --> 00:19:12,490 Kall det swapper, og hvis swapper er 0 når jeg komme hit, og det startet på 0, da 543 00:19:12,490 --> 00:19:15,520 Jeg ville bare være dumt å holde det gående frem og tilbake, kontrollerer på nytt, og 544 00:19:15,520 --> 00:19:16,450 igjen, og igjen, ikke sant? 545 00:19:16,450 --> 00:19:18,450 Fordi du sitter fast i noen slags uendelig loop. 546 00:19:18,450 --> 00:19:21,250 Så så snart det er 0 bytteavtaler, Vi kan hevde at dette 547 00:19:21,250 --> 00:19:23,810 algoritmen er faktisk ferdig. 548 00:19:23,810 --> 00:19:25,400 >> Nå, la oss sette et navn på dette. 549 00:19:25,400 --> 00:19:28,930 Algoritmen som jeg foreslår vi bare implementert er noe som heter boble 550 00:19:28,930 --> 00:19:32,800 slag, som er kjent som sådan i den forstand at tallene som er større type 551 00:19:32,800 --> 00:19:37,990 boble sin vei opp til toppen, eller opp til enden av rekken av tall. 552 00:19:37,990 --> 00:19:40,270 Men hvor effektiv var denne algoritmen? 553 00:19:40,270 --> 00:19:44,600 Hvor mange skritt jeg fysisk må ta for eksempel å sortere de 554 00:19:44,600 --> 00:19:45,850 sju 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 slutt kommer til å være svaret. 558 00:19:51,420 --> 00:19:54,960 Men selv da, det nøyaktige antall er ikke så interessant. 559 00:19:54,960 --> 00:19:56,670 La oss generalisere det som n. 560 00:19:56,670 --> 00:20:00,520 Så hvis jeg hadde n folk her oppe, og de var, liksom, i tilfeldig rekkefølge på 561 00:20:00,520 --> 00:20:02,180 begynnelse, i den opprinnelige bestillingen. 562 00:20:02,180 --> 00:20:04,910 Vel, hvor mange skritt jeg har å ta på 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 det er syv, seks -, så det er n minus ett trinn Første gang. 565 00:20:13,670 --> 00:20:16,280 >> Nå, hvor mange skritt jeg har å ta når jeg spoles tilbake? 566 00:20:16,280 --> 00:20:19,310 Vel, kunne vi faktisk dobbelt så høy som hvis vi virkelig ville, men for nå er jeg 567 00:20:19,310 --> 00:20:22,300 bare kommer til å si, all right, en annen n minus en. 568 00:20:22,300 --> 00:20:25,240 Så n minus 1 kommer til å få irriterende å holde styr på, så la oss 569 00:20:25,240 --> 00:20:26,400 bare runde opp litt. 570 00:20:26,400 --> 00:20:27,770 Så 2n trinn. 571 00:20:27,770 --> 00:20:29,310 Så 14 trinn, gi eller ta. 572 00:20:29,310 --> 00:20:31,930 >> Hvor mange ganger har jeg ta et skritt til neste gang? 573 00:20:31,930 --> 00:20:33,740 Vel, det er 3n. 574 00:20:33,740 --> 00:20:34,510 egentlig. 575 00:20:34,510 --> 00:20:37,920 Og nå, i verste fall, for eksempel, hvor mange ganger jeg har 576 00:20:37,920 --> 00:20:41,730 gått frem og tilbake, frem og tilbake, utførelse av denne algoritmen, bytte 577 00:20:41,730 --> 00:20:44,620 folk på hver passering, omtrent? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Det er faktisk n kvadrat, ikke sant? 580 00:20:50,010 --> 00:20:53,000 >> Fordi i verste fall, kan du typen av tenker om dette intuitivt, 581 00:20:53,000 --> 00:20:54,800 selv om det kan ta litt litt tid til å synke inn 582 00:20:54,800 --> 00:20:57,590 I verste fall, hva ville disse syv personer ha sett ut, i 583 00:20:57,590 --> 00:21:00,230 Når det gjelder arrangementet av sine tall? 584 00:21:00,230 --> 00:21:01,460 Helt baklengs, ikke sant? 585 00:21:01,460 --> 00:21:02,815 Og bare for å simulere det, hva var navnet ditt igjen? 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 bli med meg over her for bare ett sekund? 589 00:21:08,100 --> 00:21:08,880 Nei, faktisk ikke. 590 00:21:08,880 --> 00:21:10,150 Beklager Mike, la oss spole tilbake. 591 00:21:10,150 --> 00:21:10,910 Hva er navnet ditt igjen? 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, kommer du med meg, hvis du ikke tankene. 595 00:21:13,750 --> 00:21:17,150 Så jeg kommer til å foreslå, bare for enkelhet, at Neil er nå i sin 596 00:21:17,150 --> 00:21:18,510 verst tenkelige tilfelle. 597 00:21:18,510 --> 00:21:20,720 Men husker hvordan jeg implementert min algoritme. 598 00:21:20,720 --> 00:21:24,530 Jeg sammenlikne, sammenligne, sammenligne, sammenligne, sammenligne, oh. 599 00:21:24,530 --> 00:21:26,640 Nå er disse gutta er ute av orden, så jeg fikse. 600 00:21:26,640 --> 00:21:27,980 Så dere bytte. 601 00:21:27,980 --> 00:21:31,630 Men tenk nå, hvor mye lenger har Neil å gå? 602 00:21:31,630 --> 00:21:32,690 Det er omtrent n. 603 00:21:32,690 --> 00:21:33,570 Du vet, det er faktisk ikke n. 604 00:21:33,570 --> 00:21:36,040 Det er som, n minus en, men jeg får irritert holde styr på den lille 605 00:21:36,040 --> 00:21:37,550 nummer, så la oss bare kalle det n. 606 00:21:37,550 --> 00:21:42,860 >> Så hvis Neil beveger seg ett skritt maksimalt hver tid, og for å bevege Neil ett trinn, 607 00:21:42,860 --> 00:21:46,580 Jeg må gjøre dette veldig kjedelig pass frem og tilbake, er dette omtrent 608 00:21:46,580 --> 00:21:52,080 gjør dette, n trinn, totalt n ganger, fordi det kommer til å ta meg 609 00:21:52,080 --> 00:21:55,820 at mange tiltak for å få Neil alle veien til der han hører hjemme. 610 00:21:55,820 --> 00:21:58,620 Enn si alle andre hvis dere var alle mis-bestilles i tillegg. 611 00:21:58,620 --> 00:22:01,100 >> Så la oss kalle boble sortere n kvadrat. 612 00:22:01,100 --> 00:22:04,860 Kjøretiden til denne algoritmen, den utførelsen av denne algoritmen, den 613 00:22:04,860 --> 00:22:07,120 effektiviteten av denne algoritmen, vi skal bare beskrive mer 614 00:22:07,120 --> 00:22:08,800 generelt som n squared. 615 00:22:08,800 --> 00:22:11,650 Som er fint, fordi jeg kunne gjøre det samme eksempel med åtte personer, ni 616 00:22:11,650 --> 00:22:15,450 mennesker, en million mennesker, og at Svaret er ikke til å forandre seg. 617 00:22:15,450 --> 00:22:18,870 >> Så hvis dere ikke har noe imot, la oss tilbakestiller du til der du startet. 618 00:22:18,870 --> 00:22:22,510 Og la oss prøve to andre tilnærminger og se om vi ikke kan gjøre fundamentalt 619 00:22:22,510 --> 00:22:23,820 bedre enn dette. 620 00:22:23,820 --> 00:22:27,130 Så denne gangen, kommer jeg til å foreslå en slags annen algoritme. 621 00:22:27,130 --> 00:22:29,950 Det var veldig smart av oss sist, og dere hadde rett til å ha 622 00:22:29,950 --> 00:22:32,470 riktige instinkter bare slags å bytte parvis. 623 00:22:32,470 --> 00:22:36,500 Men hvis jeg virkelig ønsket å nærme seg dette enkelt, og mitt mål er å flytte 624 00:22:36,500 --> 00:22:39,800 alle de små tall denne måte, og skyve alle de store tallene at 625 00:22:39,800 --> 00:22:43,030 måte, hvorfor jeg ikke bare gjøre det i mest naiv måte mulig og se om jeg 626 00:22:43,030 --> 00:22:45,730 kan gjøre det bedre enn det som var en ganske kompleks algoritme? 627 00:22:45,730 --> 00:22:46,620 >> Så la oss se. 628 00:22:46,620 --> 00:22:48,940 Fire er et ganske lite antall, så jeg er kommer til å forlate deg dit øyeblikk. 629 00:22:48,940 --> 00:22:50,610 Ooh, er nummer to enda bedre. 630 00:22:50,610 --> 00:22:52,230 Så kan du bare gå fremover for et øyeblikk? 631 00:22:52,230 --> 00:22:55,670 Dette er tiden min minste nummerert kandidat, og jeg kommer til å huske 632 00:22:55,670 --> 00:22:57,000 at med, liker, en variabel. 633 00:22:57,000 --> 00:22:57,930 Men jeg kommer til å fortsette å se. 634 00:22:57,930 --> 00:22:59,890 Er det noen som har antallet er mindre? 635 00:22:59,890 --> 00:23:00,460 Seks, nei. 636 00:23:00,460 --> 00:23:01,390 Oh, det er Neil igjen. 637 00:23:01,390 --> 00:23:04,050 >> Så jeg kommer til å presse deg tilbake slags konseptuelt. 638 00:23:04,050 --> 00:23:05,120 Neil vil komme frem. 639 00:23:05,120 --> 00:23:08,440 Og nå, den variabelen som jeg bruker til holde styr på hvem som har den minste 640 00:23:08,440 --> 00:23:11,390 nummeret er oppdatert til å inneholde Neil beliggenhet. 641 00:23:11,390 --> 00:23:12,110 Vel, la oss se. 642 00:23:12,110 --> 00:23:13,960 Tre, sju, fem. 643 00:23:13,960 --> 00:23:15,590 OK, jeg vet Neil var den minste. 644 00:23:15,590 --> 00:23:18,110 Hva er den enkleste ting for meg å gjøre nå? 645 00:23:18,110 --> 00:23:21,410 Jeg har ikke tenkt å kaste bort tiden min ved å bare boblende Neil ett sted til venstre. 646 00:23:21,410 --> 00:23:25,350 Hvorfor kan jeg ikke bare sette Neil der han hører til, er som selvfølgelig der? 647 00:23:25,350 --> 00:23:26,160 >> Helt på begynnelsen. 648 00:23:26,160 --> 00:23:27,720 Så Neil, bli med meg. 649 00:23:27,720 --> 00:23:28,910 Og hva var navnet ditt igjen? 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, dessverre, du er slags i veien. 654 00:23:32,490 --> 00:23:34,290 Så hvordan løser vi dette problemet? 655 00:23:34,290 --> 00:23:34,490 Høyre? 656 00:23:34,490 --> 00:23:37,500 Hvis dette er en matrise, er det bare syv steder. 657 00:23:37,500 --> 00:23:40,830 Husker at, med Rob, vi snakket om erklære aldre, og vi hadde bare en 658 00:23:40,830 --> 00:23:41,740 endelig antall alder? 659 00:23:41,740 --> 00:23:42,535 Samme ideen her. 660 00:23:42,535 --> 00:23:44,300 Vi har kun et begrenset antall ints. 661 00:23:44,300 --> 00:23:47,590 Grace er slags i vår måte, så hvordan vi fikse? 662 00:23:47,590 --> 00:23:49,555 >> Den enkleste måten er like, Grace, beklager. 663 00:23:49,555 --> 00:23:51,870 Du er nødt til å gå over det slik at vi kan få plass. 664 00:23:51,870 --> 00:23:55,290 Nå, hvis du tenker på dette, kanskje vi bare gjort problemet verre. 665 00:23:55,290 --> 00:23:58,510 Og kanskje vi gjorde, fordi hva om Grace var på rett sted? 666 00:23:58,510 --> 00:24:01,730 Men vi vet hun ikke, fordi ellers, ville hun ha vært 667 00:24:01,730 --> 00:24:03,980 står frem i stedet for Neil på denne tiden, ikke sant? 668 00:24:03,980 --> 00:24:05,550 Vi har allerede sjekket nummeret hennes ut. 669 00:24:05,550 --> 00:24:05,770 >> OK. 670 00:24:05,770 --> 00:24:09,110 Så nå, Neil på rett sted, og Jeg kan gjøre en liten optimalisering. 671 00:24:09,110 --> 00:24:11,740 For det neste minuttet, kommer jeg til å ignorere Neil alt sammen, slik at de ikke 672 00:24:11,740 --> 00:24:15,280 kaste bort sin tid, eller ved et uhell bytte ham til feil sted. 673 00:24:15,280 --> 00:24:17,805 Så nå, hvordan kan jeg finne den neste element som er minste? 674 00:24:17,805 --> 00:24:18,480 To. 675 00:24:18,480 --> 00:24:20,225 Det er en ganske god del, hvis du ønsker å stå frem og 676 00:24:20,225 --> 00:24:21,100 Jeg vil huske deg. 677 00:24:21,100 --> 00:24:21,980 Seks, ikke bra. 678 00:24:21,980 --> 00:24:24,820 Fire, tre, sju, fem, ikke bra. 679 00:24:24,820 --> 00:24:26,800 Så la meg flytte deg til din rett sted. 680 00:24:26,800 --> 00:24:28,470 Og vi bare hadde flaks denne gangen. 681 00:24:28,470 --> 00:24:31,350 >> Nå kommer jeg til å ignorere disse to gutter, og nå gjør en mer 682 00:24:31,350 --> 00:24:32,260 passere gjennom dette. 683 00:24:32,260 --> 00:24:33,490 Seks, som en ganske lite antall. 684 00:24:33,490 --> 00:24:34,300 Kom frem. 685 00:24:34,300 --> 00:24:35,220 Oh, beklager. 686 00:24:35,220 --> 00:24:37,640 Grace nummer er bedre, så gå på fremover. 687 00:24:37,640 --> 00:24:38,260 Fire. 688 00:24:38,260 --> 00:24:39,120 Beklager, Grace. 689 00:24:39,120 --> 00:24:39,950 Gå tilbake igjen. 690 00:24:39,950 --> 00:24:41,550 Nummer tre er bedre. 691 00:24:41,550 --> 00:24:42,290 Seven. 692 00:24:42,290 --> 00:24:42,720 Fem. 693 00:24:42,720 --> 00:24:43,550 Og nå hva heter du igjen? 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 nå den minste element jeg har valgt. 697 00:24:47,050 --> 00:24:49,160 Hvor er han kommer til å gå? 698 00:24:49,160 --> 00:24:50,380 Så hvor seks er. 699 00:24:50,380 --> 00:24:51,210 Og navnet ditt er igjen? 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 veien. 703 00:24:53,220 --> 00:24:54,640 Hva er den enkleste tingen å gjøre? 704 00:24:54,640 --> 00:24:58,390 Bytt disse to gutta og fortsette. 705 00:24:58,390 --> 00:24:59,020 Så nå la oss se. 706 00:24:59,020 --> 00:25:00,170 Hvem er den minste? 707 00:25:00,170 --> 00:25:01,030 Fire. 708 00:25:01,030 --> 00:25:01,990 La meg bare slags jukse. 709 00:25:01,990 --> 00:25:03,090 Fem kommer til å være den minste. 710 00:25:03,090 --> 00:25:05,220 Jeg finner neste, hvis du ønsker å gå fremover, hva jeg har å gjøre med 711 00:25:05,220 --> 00:25:06,820 disse gutta, med Gabe? 712 00:25:06,820 --> 00:25:08,450 Bytte igjen. 713 00:25:08,450 --> 00:25:10,740 Så nå, fortsatt litt ute av drift. 714 00:25:10,740 --> 00:25:14,140 Jeg fant Gabe å være den minste, så Jeg pop ham ut, flytt dere over. 715 00:25:14,140 --> 00:25:15,190 Og gjort. 716 00:25:15,190 --> 00:25:17,200 >> Så svar er den samme. 717 00:25:17,200 --> 00:25:18,600 Sluttresultatet er det samme. 718 00:25:18,600 --> 00:25:22,730 Hvilken av disse to algoritmene er bedre? 719 00:25:22,730 --> 00:25:23,500 Den andre, hørte jeg. 720 00:25:23,500 --> 00:25:24,252 Hvorfor? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Det er n trinn [uhørlig]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. MALAN: Det er n trinn 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 om? 725 00:25:30,610 --> 00:25:33,630 Så hvordan jeg finner minste elementet? 726 00:25:33,630 --> 00:25:37,060 Hvor mange skritt jeg må ta den finner det minste elementet? 727 00:25:37,060 --> 00:25:39,220 Jeg hadde en ser hele veien i enden, til høyre? 728 00:25:39,220 --> 00:25:41,530 Fordi i det verste tilfellet, hva hvis Neil var over her? 729 00:25:41,530 --> 00:25:45,700 Så bare å finne det minste elementet tar meg n trinn, eller n minus en. 730 00:25:45,700 --> 00:25:46,100 Men, OK. 731 00:25:46,100 --> 00:25:46,980 Så fikse Neil. 732 00:25:46,980 --> 00:25:48,740 Husk at et minutt eller så siden. 733 00:25:48,740 --> 00:25:51,680 >> Men hvordan gjorde jeg finne neste minste elementet? 734 00:25:51,680 --> 00:25:54,830 Det er n 1 minus, eller n minus to egentlig, fra antall trinn. 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 to. 737 00:25:57,390 --> 00:25:57,600 OK. 738 00:25:57,600 --> 00:25:59,130 Så det føles litt bedre. 739 00:25:59,130 --> 00:25:59,730 OK. 740 00:25:59,730 --> 00:26:03,270 Hvor mange skritt neste gang å finne nummer tre? 741 00:26:03,270 --> 00:26:04,420 Så n minus fire. 742 00:26:04,420 --> 00:26:07,670 Så det er avtagende, en færre tråkke på hver iterasjon. 743 00:26:07,670 --> 00:26:08,740 Så dette føles bedre, ikke sant? 744 00:26:08,740 --> 00:26:13,450 Hvis siste gang var det omtrent n ganger n, denne gangen er det n en minus, pluss n minus 745 00:26:13,450 --> 00:26:16,500 2, pluss n minus tre, pluss n 4 minus, prikk, prikk, prikk. 746 00:26:16,500 --> 00:26:18,750 Men hvis du huske fra videregående skole lærebøker, den lille jukse 747 00:26:18,750 --> 00:26:24,380 ark på baksiden som har formler, hvis du legger opp denne serien av tall, 748 00:26:24,380 --> 00:26:31,280 det som er det totale antall skritt kommer til å være at jeg tar her? 749 00:26:31,280 --> 00:26:36,580 >> Dette er en av dem, som, n minus 1, ganger n, delt på to. 750 00:26:36,580 --> 00:26:39,040 Så la meg se om jeg kan trekke dette opp for bare et øyeblikk. 751 00:26:39,040 --> 00:26:42,230 Og igjen, jeg er litt avrunding noen tall bare for å holde våre liv enkelt, 752 00:26:42,230 --> 00:26:47,830 men som jeg husker, er det noe sånt hvis Jeg gjør n minus en ting, så n minus 753 00:26:47,830 --> 00:26:53,570 2, deretter n minus 3, er det omtrent noe sånt som dette over to, og hvis jeg 754 00:26:53,570 --> 00:26:55,510 multiplisere dette ut, det er faktisk n torget. 755 00:26:55,510 --> 00:26:58,940 Det er ikke følelsen bra. n minus n enn to. 756 00:26:58,940 --> 00:27:00,350 >> Men her er tingen. 757 00:27:00,350 --> 00:27:03,720 I informatikk, når problemene begynner å bli interessant er når n 758 00:27:03,720 --> 00:27:04,700 blir veldig stor. 759 00:27:04,700 --> 00:27:08,110 Og når n blir veldig store, som av disse verdiene kommer til å dominere hele 760 00:27:08,110 --> 00:27:09,750 av de andre? 761 00:27:09,750 --> 00:27:10,990 Det er slags n squared, ikke sant? 762 00:27:10,990 --> 00:27:13,340 Ja, dividere med 2 er ganske bra. 763 00:27:13,340 --> 00:27:16,740 Men hvis du snakker om milliarder biter av data, eller billioner av 764 00:27:16,740 --> 00:27:18,700 biter av data, ok, så du er dobbelt så rask. 765 00:27:18,700 --> 00:27:22,440 Men hvem bryr seg egentlig om det store antall, dersom denne faktoren er det som 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, gjør det mer av en forskjell enn denne fyren. 768 00:27:25,990 --> 00:27:29,120 Så selv om dere er rett, andre algoritme, kan vi kalle det 769 00:27:29,120 --> 00:27:32,970 utvalg sortere, er, i den virkelige verden, en litt raskere potensielt, fordi jeg er 770 00:27:32,970 --> 00:27:35,360 ta færre og færre trinn hver gang. 771 00:27:35,360 --> 00:27:37,340 >> Det er egentlig ikke fundamentalt raskere. 772 00:27:37,340 --> 00:27:41,430 Fordi hvis vi faktisk spille ut dette for store verdier av n, i enden av 773 00:27:41,430 --> 00:27:44,750 dagen, for stor nok n, er det fortsatt kommer til å føle seg ganske treg. 774 00:27:44,750 --> 00:27:46,770 Vel, la meg ta ett siste pass på det. 775 00:27:46,770 --> 00:27:48,920 Det er det jeg vil kalle utvalg slag. 776 00:27:48,920 --> 00:27:51,040 Kan dere nullstille dere en siste gang? 777 00:27:51,040 --> 00:27:53,550 Og i dette siste tilfellet, kommer jeg til å foreslå noe 778 00:27:53,550 --> 00:27:54,970 kalt innsetting slag. 779 00:27:54,970 --> 00:27:57,470 Innsetting slags vesen, konseptuelt, litt annerledes. 780 00:27:57,470 --> 00:28:00,980 >> Snarere enn å gå frem og tilbake og velge det minste elementet, jeg 781 00:28:00,980 --> 00:28:05,030 bare kommer til å håndtere hver av disse gutta som jeg møter dem, og sett 782 00:28:05,030 --> 00:28:06,850 dem inn i sin rette plass. 783 00:28:06,850 --> 00:28:10,160 Så jeg skal bare starte med Grace, og jeg ser at hun er nummer fire. 784 00:28:10,160 --> 00:28:11,720 Hvor hører nummer fire? 785 00:28:11,720 --> 00:28:14,940 Jeg har ikke begynt å sortere noe, så Grace får å bo der. 786 00:28:14,940 --> 00:28:18,355 Og nå skal jeg til å kreve, hvis du kunne ta et skritt til høyre, dette 787 00:28:18,355 --> 00:28:21,650 min sortert liste, dette er min usortert gjenværende listen. 788 00:28:21,650 --> 00:28:23,260 Så nå skal jeg fortsette neste, og hva heter du igjen? 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 kommer til å ta deg ut for en stund. 793 00:28:27,490 --> 00:28:30,940 Og nå trenger der du hører hjemme i denne matrisen? 794 00:28:30,940 --> 00:28:32,360 Så til høyre for Grace. 795 00:28:32,360 --> 00:28:35,670 Så igjen, er vi på en måte som gjør Grace gjøre mye arbeid her. 796 00:28:35,670 --> 00:28:37,290 Hvor plasserer vi deg? 797 00:28:37,290 --> 00:28:40,120 Så vi kommer til å skyve deg til igjen, og sett Branson der. 798 00:28:40,120 --> 00:28:41,680 Men nå har jeg hevder at dere er ferdig. 799 00:28:41,680 --> 00:28:43,240 Men legg merke til, jeg bruker ikke ekstra plass. 800 00:28:43,240 --> 00:28:45,130 Det er fortsatt to elementer her, fem over her. 801 00:28:45,130 --> 00:28:47,910 Total gitterstørrelse er 7, så jeg er ikke juks, ok? 802 00:28:47,910 --> 00:28:51,950 >> Så nå har vi, med Gabe her, den nummer seks, hvor hører du til? 803 00:28:51,950 --> 00:28:52,650 Du hadde flaks igjen. 804 00:28:52,650 --> 00:28:53,820 Så du får bo der. 805 00:28:53,820 --> 00:28:57,210 Bare ta en liten steg til høyre bare for å gjøre det klart at du er sortert. 806 00:28:57,210 --> 00:29:00,520 Og nå har vi Neil igjen, antall en, hvor går du? 807 00:29:00,520 --> 00:29:03,540 Og er nå der vi vil begynne å se at denne algoritmen, men på første 808 00:29:03,540 --> 00:29:05,950 øyekast, føles ganske smart, se hva som er i ferd med å skje. 809 00:29:05,950 --> 00:29:07,370 Hvis du kunne gå fremover. 810 00:29:07,370 --> 00:29:09,260 >> Hvor ønsker vi å sette Neil? 811 00:29:09,260 --> 00:29:11,830 Så åpenbart her, så hvordan får vi Neil der? 812 00:29:11,830 --> 00:29:12,970 La oss gjøre dette steg for steg. 813 00:29:12,970 --> 00:29:15,620 Gabe, der trenger du å reise? 814 00:29:15,620 --> 00:29:19,590 Jepp, så ta ett stort skritt, eller to halv-skritt for å gjøre 815 00:29:19,590 --> 00:29:20,820 ett skritt der borte. 816 00:29:20,820 --> 00:29:21,750 Grace, hvor du går? 817 00:29:21,750 --> 00:29:22,510 Bra. 818 00:29:22,510 --> 00:29:23,500 Så et annet trinn. 819 00:29:23,500 --> 00:29:24,960 Og til slutt, Branson? 820 00:29:24,960 --> 00:29:25,460 Et annet skritt. 821 00:29:25,460 --> 00:29:27,190 Og nå kan vi sette Neil på plass. 822 00:29:27,190 --> 00:29:28,440 >> Så nå, fortsetter denne logikken. 823 00:29:28,440 --> 00:29:32,420 Selv om vi ikke er skiftende Neil over, og over og over, for å sette ham 824 00:29:32,420 --> 00:29:36,420 hvor han går, i verste fall, neste nummer vi kan støte kunne 825 00:29:36,420 --> 00:29:42,220 være nummer, si, var det en rekke null, så vi kommer til å skifte alle 826 00:29:42,220 --> 00:29:42,730 disse gutta. 827 00:29:42,730 --> 00:29:44,950 Anta at det er et tall, negative en, så vi må skifte 828 00:29:44,950 --> 00:29:46,080 alle disse gutta. 829 00:29:46,080 --> 00:29:48,500 Så vi er egentlig bare slags bla problemet rundt, slik at vi er 830 00:29:48,500 --> 00:29:52,620 overføring bekostning fra utvelgelsesprosessen så innsetting 831 00:29:52,620 --> 00:29:56,930 prosessen, slik at dere bare hadde å flytte omtrent n minus noe 832 00:29:56,930 --> 00:29:57,940 antall trinn. 833 00:29:57,940 --> 00:30:01,200 Og at antall skritt er bare kommer å øke etter hvert som jeg velger flere numre, 834 00:30:01,200 --> 00:30:04,730 hvis jeg må holde dytter dere tilbake, og tilbake, og tilbake. 835 00:30:04,730 --> 00:30:08,320 >> Så det triste er nå alle disse algoritmer er n kvadrat. 836 00:30:08,320 --> 00:30:10,570 La oss gå videre og takket være disse gutter, og visualisere disse litt 837 00:30:10,570 --> 00:30:11,090 annerledes. 838 00:30:11,090 --> 00:30:12,312 Veldig godt gjort. 839 00:30:12,312 --> 00:30:14,120 >> [APPLAUSE] 840 00:30:14,120 --> 00:30:15,030 >> OK. 841 00:30:15,030 --> 00:30:16,280 Der du går. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Takk 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: Nei, det kan du holde tallene i tillegg. 846 00:30:21,990 --> 00:30:23,440 OK. 847 00:30:23,440 --> 00:30:24,100 Pent gjort. 848 00:30:24,100 --> 00:30:25,300 OK. 849 00:30:25,300 --> 00:30:30,510 Så la oss se om vi ikke kan nå oppsummere raskere, og mer visuelt, 850 00:30:30,510 --> 00:30:33,410 nøyaktig hva som skjedde her følger. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Jeg kommer til å gå videre og trekk opp Firefox. 853 00:30:38,770 --> 00:30:41,310 Vi vil knytte denne demonstrasjonen på kurset hjemmeside. 854 00:30:41,310 --> 00:30:43,870 Java er litt irriterende å få jobbe i enkelte nettlesere disse dager. 855 00:30:43,870 --> 00:30:46,760 Så hvis du kan leke med dette hjemme, skjønner du kanskje trenger å bruke Firefox 856 00:30:46,760 --> 00:30:47,990 for å få det til å fungere. 857 00:30:47,990 --> 00:30:50,440 Og hva jeg skal gjøre med dette demonstrasjon er følgende. 858 00:30:50,440 --> 00:30:54,875 >> Nederst har jeg en hel haug med menyvalg, inkludert en start og en 859 00:30:54,875 --> 00:30:55,840 stopp-knappen. 860 00:30:55,840 --> 00:30:59,450 Også, som en side, synes det å være en bug i disse programmene, der du 861 00:30:59,450 --> 00:31:03,720 kan faktisk ikke se starten eller stoppe knappen med mindre du nede Kommando eller Alt 862 00:31:03,720 --> 00:31:06,560 pluss og zoom inn, som merkelig nok viser deg flere knapper. 863 00:31:06,560 --> 00:31:09,090 Så bare så dere vet det hvis du spiller med dette hjemme. 864 00:31:09,090 --> 00:31:12,870 Nå skal jeg til å klikke på Start på bare en øyeblikk, etter å ha angitt en forsinkelse på, 865 00:31:12,870 --> 00:31:16,810 liker, 200 millisekunder her, bare så vi kan se hva som skjer. 866 00:31:16,810 --> 00:31:20,180 >> Så jeg påstå at dette er en visualisering av den første algoritmen 867 00:31:20,180 --> 00:31:23,730 disse gutta gjorde, boble sortere, der vi byttet folk parvis. 868 00:31:23,730 --> 00:31:27,490 Nøkkelen innsikt til denne visualiseringen er at høyden på stengene 869 00:31:27,490 --> 00:31:30,510 representerer størrelsen av nummeret. 870 00:31:30,510 --> 00:31:32,210 Så høyere søylen er, desto større antall. 871 00:31:32,210 --> 00:31:33,680 Kortere baren, mindre tall. 872 00:31:33,680 --> 00:31:38,630 Og hvis du legger merke til, vi går gjennom den første iterasjon av denne algoritmen, 873 00:31:38,630 --> 00:31:42,620 swapping store og små tall, slik at det lave antallet kommer først og 874 00:31:42,620 --> 00:31:44,280 det store antallet går til høyre. 875 00:31:44,280 --> 00:31:48,770 >> Og så snart vi får på slutten av matrise av mange flere tall enn syv, vi 876 00:31:48,770 --> 00:31:49,900 kommer til å gå tilbake til begynnelsen. 877 00:31:49,900 --> 00:31:51,140 Og forutse dette. 878 00:31:51,140 --> 00:31:54,860 Helt til venstre, er at lille fyren kommer å bytte til siden, og dette 879 00:31:54,860 --> 00:31:56,010 prosessen gjentas. 880 00:31:56,010 --> 00:31:59,450 Nå er denne visualiseringen blir raskt kjedelig, så la meg gå videre og stoppe 881 00:31:59,450 --> 00:32:04,170 det, endre forsinkelsen noe mye raskere bare for å få nå, en følelse for 882 00:32:04,170 --> 00:32:05,060 denne algoritmen. 883 00:32:05,060 --> 00:32:07,840 >> Så selv om jeg har sped det opp, er dette som å oppgradere min prosessor, kjøpe 884 00:32:07,840 --> 00:32:08,580 en ny datamaskin. 885 00:32:08,580 --> 00:32:12,980 Jeg har ikke fundamentalt forandret mitt algoritme, men du kan faktisk se mer 886 00:32:12,980 --> 00:32:16,800 tydelig enn med mennesker, at de store tall bobler opp til toppen, 887 00:32:16,800 --> 00:32:20,900 og de små tall bobler ned til bunnen. 888 00:32:20,900 --> 00:32:22,390 Og nå denne tingen her sortert. 889 00:32:22,390 --> 00:32:25,260 Og som en side, i rutene, er det bare noen bokføring der for å 890 00:32:25,260 --> 00:32:28,010 hjelpe deg å telle hvor mange sammenligninger, eller hvor mange swaps har 891 00:32:28,010 --> 00:32:28,950 faktisk blitt gjort. 892 00:32:28,950 --> 00:32:30,750 >> Vel, la oss prøve en av de andre vi så. 893 00:32:30,750 --> 00:32:37,116 La meg klikk på boble sortere her, og la meg velge, og hele denne nettsiden 894 00:32:37,116 --> 00:32:38,936 er litt buggy. 895 00:32:38,936 --> 00:32:41,155 La oss akseptere risikoen og kjøre den på nytt. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Det vi går. 898 00:32:45,030 --> 00:32:47,180 Så la oss gjøre utvalget slag. 899 00:32:47,180 --> 00:32:49,140 Jeg vet ikke hvorfor menyen vises der borte. 900 00:32:49,140 --> 00:32:54,070 La oss zoome inn for å fikse det bug, endre dette til 50 år. 901 00:32:54,070 --> 00:32:56,020 Ah, la oss faktisk gjør så mye raskere. 902 00:32:56,020 --> 00:32:59,160 Fem millisekunder eller så, og Start. 903 00:32:59,160 --> 00:33:00,470 >> Så dette er utvalget slag. 904 00:33:00,470 --> 00:33:03,070 Så igjen, tenke på hva vi gjorde med menneskene her oppe. 905 00:33:03,070 --> 00:33:08,490 Vi gikk gjennom matrisen og valgt det minste elementet igjen, 906 00:33:08,490 --> 00:33:09,250 og igjen og igjen. 907 00:33:09,250 --> 00:33:11,110 Nå har jeg hevder det var fortsatt ganske dårlig. 908 00:33:11,110 --> 00:33:15,010 Det var fortsatt n kvadrat, gi eller ta, men det var i den virkelige verden, litt 909 00:33:15,010 --> 00:33:18,280 raskere, fordi jeg var faktisk å ta litt færre trinn for hver gang. 910 00:33:18,280 --> 00:33:19,800 Men vi bare snakker hva? 911 00:33:19,800 --> 00:33:21,830 Kanskje 40 eller så barer her? 912 00:33:21,830 --> 00:33:23,200 Vi snakker ikke 40 millioner. 913 00:33:23,200 --> 00:33:27,430 Så det er ikke klart helt for meg at var faktisk en betydelig gevinst. 914 00:33:27,430 --> 00:33:32,530 >> La meg nå gå tilbake og endre til vår tredje algoritme, som ble velge 915 00:33:32,530 --> 00:33:33,180 innsetting slag. 916 00:33:33,180 --> 00:33:36,380 Og nå er det virkelig buggy fordi Menyen egentlig ikke burde være der nede. 917 00:33:36,380 --> 00:33:40,840 Så nå skal vi bla tilbake her og starte denne algoritmen. 918 00:33:40,840 --> 00:33:43,270 Whoop, start og stopp. 919 00:33:43,270 --> 00:33:47,160 Så denne typen har en pen mønster til det, der vi er igjen 920 00:33:47,160 --> 00:33:50,240 setter mennesker, eller i dette tilfellet, barene inn 921 00:33:50,240 --> 00:33:52,620 deres passende sted. 922 00:33:52,620 --> 00:33:55,430 Og det er allerede gjort før Jeg snudde meg rundt. 923 00:33:55,430 --> 00:33:58,940 Men dette også, i teorien, er fortsatt n kvadrat. 924 00:33:58,940 --> 00:34:01,430 >> Så la oss se om vi ikke kan oppsummere disse følger. 925 00:34:01,430 --> 00:34:04,750 Jeg kommer til å gå videre og bare for å gi oss liksom en vanlig måte å snakke 926 00:34:04,750 --> 00:34:08,489 om disse tingene, la meg introdusere bare litt av notasjon her. 927 00:34:08,489 --> 00:34:12,480 Du er i ferd med å se noe som kalles big O, fordi det er bokstavelig talt en stor 928 00:34:12,480 --> 00:34:16,320 O. Og dette er en måte som en datamaskin forsker eller en matematiker selv bruker 929 00:34:16,320 --> 00:34:19,230 å beskrive kjøretiden av noen algoritme. 930 00:34:19,230 --> 00:34:21,400 Hvor mange skritt betyr det egentlig ta? 931 00:34:21,400 --> 00:34:25,080 >> Nå skal jeg noe dumt med håndskriften min her i bare et øyeblikk. 932 00:34:25,080 --> 00:34:29,020 Men la meg gå videre og si at dette vil være stor O over her. 933 00:34:29,020 --> 00:34:33,610 Og la meg presentere en annen symbol, en kapital omega. 934 00:34:33,610 --> 00:34:37,080 Omega kommer til å være det motsatte, hovedsak, av stor O. Mens big O 935 00:34:37,080 --> 00:34:40,790 betyr, i verste fall, hvor mye tid kanskje noen algoritme ta i 936 00:34:40,790 --> 00:34:43,480 form av n, er omega skal være hvor mye tid kanskje det 937 00:34:43,480 --> 00:34:45,409 ta i beste fall. 938 00:34:45,409 --> 00:34:48,090 Og vi får se hva vi mener med beste fall på bare et øyeblikk. 939 00:34:48,090 --> 00:34:49,940 >> Så la oss starte noe enkelt. 940 00:34:49,940 --> 00:34:54,719 La meg starte med en lineær søk. 941 00:34:54,719 --> 00:34:55,679 Så ikke sortering. 942 00:34:55,679 --> 00:34:58,000 Vi kaller dette lineære søket. 943 00:34:58,000 --> 00:35:01,140 Og nå, gjøre litt tabell ut av dette. 944 00:35:01,140 --> 00:35:06,600 Og nå, i tilfelle av lineære søk, i verste fall, hvor mange skritt er 945 00:35:06,600 --> 00:35:11,770 det kommer til å ta meg med å finne en antall vilkårlig valg? 946 00:35:11,770 --> 00:35:14,540 Og det er n antall dører eller n totaltall. 947 00:35:14,540 --> 00:35:15,940 Worst case. 948 00:35:15,940 --> 00:35:18,800 Hvor mange skritt jeg nødt til å ta for å finne antall 50 i en matrise 949 00:35:18,800 --> 00:35:20,830 av n dører? 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 vei over på enden. 952 00:35:23,680 --> 00:35:27,120 Så mye som Jennifer møtte, den nummer 50 var helt over, så i 953 00:35:27,120 --> 00:35:30,760 verste fall lineær søk er big O n, vil vi si. 954 00:35:30,760 --> 00:35:33,430 >> Hva om beste fall, hvis du får virkelig heldig? 955 00:35:33,430 --> 00:35:36,200 Det er bare kommer til å ta ett skritt, eller et konstant antall skritt. 956 00:35:36,200 --> 00:35:37,830 Så vi vil beskrive det som en. 957 00:35:37,830 --> 00:35:39,010 Så dette er ganske bra. 958 00:35:39,010 --> 00:35:41,210 Hva nå hvis vi gjorde noe liker binære søk? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Så binære søk i verste tilfelle, tok hvor mye 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 på et par steder. 963 00:35:51,310 --> 00:35:56,390 Så det er logger faktisk n, gi eller ta, fordi som vi dele opp listen i to 964 00:35:56,390 --> 00:36:00,730 igjen, og igjen, og igjen, er vi i stand å finne, til slutt, verdien, 965 00:36:00,730 --> 00:36:04,750 hvis den er der, men det er en hake. 966 00:36:04,750 --> 00:36:08,590 Hva er antagelsen om at vi må ta for gitt for binære søk? 967 00:36:08,590 --> 00:36:09,700 Det må være sortert. 968 00:36:09,700 --> 00:36:12,770 Det er ikke sortert, kan du dele ting i to igjen og igjen, og du 969 00:36:12,770 --> 00:36:15,490 kan gå til venstre, og du kan gå rett, og du kan gå til venstre og høyre, men du er 970 00:36:15,490 --> 00:36:18,070 ikke kommer til å finne elementet hvis listen er ikke sortert, fordi 971 00:36:18,070 --> 00:36:18,790 du kan gå glipp av det. 972 00:36:18,790 --> 00:36:22,120 Fordi heuristisk din, for å gå til venstre eller høyre kommer til å være feil hvis det er 973 00:36:22,120 --> 00:36:23,420 faktisk ikke sortert. 974 00:36:23,420 --> 00:36:26,110 Så det er liksom en skjult kostnad å bruke noe sånt som dette. 975 00:36:26,110 --> 00:36:29,250 >> Nå, la oss gå inn sortering vår algoritmer ikke søker - 976 00:36:29,250 --> 00:36:31,140 oh, faktisk la oss gå i denne tomt. 977 00:36:31,140 --> 00:36:33,190 Binære søk i beste fall? 978 00:36:33,190 --> 00:36:36,290 Det er også en hvis det bare skjer for å være i selve midten av matrisen, eller 979 00:36:36,290 --> 00:36:37,810 midt i telefonkatalogen. 980 00:36:37,810 --> 00:36:39,710 Nå la oss gjøre boble slag. 981 00:36:39,710 --> 00:36:42,570 Så igjen, nå er vi inn i sorterer, ikke søk. 982 00:36:42,570 --> 00:36:47,220 >> I verste fall, gjorde hvor mange skritt vi krav boble sortere kommer til å ta? 983 00:36:47,220 --> 00:36:48,410 n squared. 984 00:36:48,410 --> 00:36:49,200 Så jeg kommer til å trekke det. 985 00:36:49,200 --> 00:36:51,710 Ooh, ser håndskriften min enda verre når det er anslått at stort. 986 00:36:51,710 --> 00:36:52,510 OK. 987 00:36:52,510 --> 00:36:53,570 Så det er n kvadrat. 988 00:36:53,570 --> 00:36:59,460 Og i beste fall av boble sortere, hvor mange skritt det kommer til å ta? 989 00:36:59,460 --> 00:37:00,980 1, hørte jeg. 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, hørte jeg. 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, hørte jeg. 994 00:37:05,010 --> 00:37:06,670 Hører jeg tre? 995 00:37:06,670 --> 00:37:07,080 OK. 996 00:37:07,080 --> 00:37:11,390 Så jeg har hørt en, n, to, men la oss plukke fra hverandre i det minste den første av disse 997 00:37:11,390 --> 00:37:12,330 forslag, en. 998 00:37:12,330 --> 00:37:15,370 Det er ikke et dårlig instinkt, fordi det slags følger et mønster her. 999 00:37:15,370 --> 00:37:19,670 Men hvis det tar bare ett trinn, hvordan i verden kunne jeg hevde at listen 1000 00:37:19,670 --> 00:37:22,900 sorteres, fordi hvis jeg bare lov å ta en trinn, hvor mange deler 1001 00:37:22,900 --> 00:37:25,230 kunne jeg faktisk sjekke for å være sikker? 1002 00:37:25,230 --> 00:37:28,270 Vel, bare en, noe som betyr at det er n minus 1 elementer som kan være ute av 1003 00:37:28,270 --> 00:37:31,310 orden, og jeg skal bare på tro etter ser på en del at 1004 00:37:31,310 --> 00:37:31,850 ting blir sortert. 1005 00:37:31,850 --> 00:37:33,930 Så en er ikke riktig her. 1006 00:37:33,930 --> 00:37:35,710 Så minimalt, hvor mange må jeg 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 en, eller egentlig, n, fordi jeg trenger å se på hver 1009 00:37:40,160 --> 00:37:42,190 element for å sikre at det er ikke ute av drift. 1010 00:37:42,190 --> 00:37:44,750 Men igjen, vi vil liksom bølge vår hendene på de mindre tall og 1011 00:37:44,750 --> 00:37:47,100 anta at, som n blir stor, er de uinteressant uansett. 1012 00:37:47,100 --> 00:37:48,380 Så det er boble slag. 1013 00:37:48,380 --> 00:37:49,830 Og nå, la oss gjøre disse to siste. 1014 00:37:49,830 --> 00:37:53,520 Utvalg sortere og så får vi gjøre innsetting slag. 1015 00:37:53,520 --> 00:37:57,160 Og så vil vi blåse sinn med noe mye 1016 00:37:57,160 --> 00:37:58,926 bedre enn alle disse. 1017 00:37:58,926 --> 00:38:00,410 OK. 1018 00:38:00,410 --> 00:38:04,700 >> Hva er det verste tilfellet kjører tidspunktet for valget slag? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n kvadrat. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. MALAN: n kvadrat, jeg hører. 1021 00:38:06,710 --> 00:38:09,790 Men hvorfor n kvadrerte, intuitivt? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Fordi vi bare gjorde det. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. MALAN: Fordi vi bare gjorde det. 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 utvalget sortere n kvadrat? 1027 00:38:16,660 --> 00:38:18,980 Hva gjorde vi har å gjøre igjen og igjen? 1028 00:38:18,980 --> 00:38:22,570 Vi måtte fortsette å søke gjennom, er du den minste, er du den 1029 00:38:22,570 --> 00:38:24,020 minste, du er den minste. 1030 00:38:24,020 --> 00:38:27,480 Og gitt, var vi i stand til å ta n trinn, deretter n 1 minus, da n minus to. 1031 00:38:27,480 --> 00:38:30,700 Men hvis du slags legge dem alle opp, eller ta det på tro at jeg har lagt 1032 00:38:30,700 --> 00:38:34,810 dem opp på forhånd, får vi omtrent n squared minus noen mindre tall. 1033 00:38:34,810 --> 00:38:36,730 Så jeg kommer til å kalle dette n kvadrat. 1034 00:38:36,730 --> 00:38:39,530 Men med valget sortere på best tilfelle, hvor mange skritt er det 1035 00:38:39,530 --> 00:38:40,632 kommer til å ta meg? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [uhørlig] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. MALAN: Det er dessverre fortsatt n kvadrat, ikke sant? 1038 00:38:44,350 --> 00:38:49,590 Fordi hvis jeg velger den minste element, og vi hadde syv personer her, 1039 00:38:49,590 --> 00:38:53,280 Jeg bare vet, når jeg kommer til selve slutt, at jeg har funnet den minste 1040 00:38:53,280 --> 00:38:55,670 nummer, uansett hvor han eller hun kan ha vært. 1041 00:38:55,670 --> 00:38:58,820 Men hvordan finner jeg den neste minste tallet? 1042 00:38:58,820 --> 00:39:00,160 Jeg må gjøre en annen pass. 1043 00:39:00,160 --> 00:39:04,810 Så i beste fall, hva er innspill til utvalget slag? 1044 00:39:04,810 --> 00:39:07,830 Det er en allerede sortere listen, nummer en, nummer to, for det tredje nummer fire. 1045 00:39:07,830 --> 00:39:08,600 Men jeg er en datamaskin. 1046 00:39:08,600 --> 00:39:10,190 Jeg kan bare se på en ting om gangen. 1047 00:39:10,190 --> 00:39:12,465 Jeg kan ikke liksom ta et skritt tilbake som et menneske og si: 1048 00:39:12,465 --> 00:39:14,030 ooh, dette ser riktig. 1049 00:39:14,030 --> 00:39:17,580 >> Jeg kan bare avgjøre riktigheten i utvalg sortere ved å velge 1050 00:39:17,580 --> 00:39:18,370 minste tallet. 1051 00:39:18,370 --> 00:39:21,390 Men selv om jeg finner nummer én første, hvis jeg ikke vet noe annet om 1052 00:39:21,390 --> 00:39:24,460 de andre tallene, som jeg ikke gjør det, alt jeg vet at jeg har blitt overlevert en matrise 1053 00:39:24,460 --> 00:39:27,930 eller et sett med dører bak som er tall, den eneste måten jeg vet at en 1054 00:39:27,930 --> 00:39:28,680 var den minste? 1055 00:39:28,680 --> 00:39:32,440 Hvis jeg får hele veien her og realisere, faen, var en faktisk den minste. 1056 00:39:32,440 --> 00:39:34,870 >> Men hvordan gjør jeg da bestemme at to er den neste, mindre? 1057 00:39:34,870 --> 00:39:38,350 Ved å gjøre det samme ineffektivitet igjen og igjen. 1058 00:39:38,350 --> 00:39:42,210 Så til slutt, med innsetting sortere, hvordan, i verste fall, 1059 00:39:42,210 --> 00:39:44,990 vi sier det utfører? 1060 00:39:44,990 --> 00:39:49,100 Det også er n kvadrat. 1061 00:39:49,100 --> 00:39:53,020 Og hva med den beste saken? 1062 00:39:53,020 --> 00:39:56,282 Vi vil forlate det som en cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Vi skal fylle ut en blank neste gang, men først la meg foreslå at vi 1064 00:40:00,090 --> 00:40:02,620 fundamentalt gjøre det bedre enn alle disse, ok? 1065 00:40:02,620 --> 00:40:05,220 >> Så tenk selv hva innsetting sortere kommer til å bli. 1066 00:40:05,220 --> 00:40:06,910 Vel, det var ikke veldig dramatisk, fordi jeg er den eneste 1067 00:40:06,910 --> 00:40:08,970 som så forandringen. 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 noe annen demonstrasjon. 1071 00:40:12,615 --> 00:40:16,580 Hvis jeg zoome inn her, vil du se at på venstre vi har boble sorter, i 1072 00:40:16,580 --> 00:40:20,740 midten har vi utvalg sortere og på helt til høyre, har vi noe vi 1073 00:40:20,740 --> 00:40:23,380 har ikke sett på ennå kalt flette slag. 1074 00:40:23,380 --> 00:40:26,080 Men tenk på hva vi har vært gjør her så langt i dag. 1075 00:40:26,080 --> 00:40:29,200 Når Jennifer først kom opp på scenen, vi gikk gjennom rekken av tall 1076 00:40:29,200 --> 00:40:33,750 igjen og igjen, med lineær søk, og vi fikk lineær kjøretid, big O 1077 00:40:33,750 --> 00:40:35,100 av N, så å si. 1078 00:40:35,100 --> 00:40:41,000 >> Når vi nå vurdere den første uken av klasse, da vi hadde splitt og hersk, 1079 00:40:41,000 --> 00:40:43,740 og vi hadde telefonboken rive, og Jennifer, og vi kollektivt 1080 00:40:43,740 --> 00:40:47,500 leveraged at viktig innsikt, som var å gjenta deg selv igjen og igjen av 1081 00:40:47,500 --> 00:40:50,930 en eller annen måte å kaste bort, kaste bort, kaster bort halvparten av problemet, eller 1082 00:40:50,930 --> 00:40:55,320 generelt, dele et problem i to, og deretter behandle mindre stykke av 1083 00:40:55,320 --> 00:40:59,630 problemet som konseptuelt tilsvarende til den annen, vi noe gjorde 1084 00:40:59,630 --> 00:41:00,910 fundamentalt bedre. 1085 00:41:00,910 --> 00:41:04,720 Men med boble sortere, med utvalg sortere, med innsetting sortere, vi har kanskje 1086 00:41:04,720 --> 00:41:06,560 ingen slike innsikt som Jennifer gjorde. 1087 00:41:06,560 --> 00:41:10,220 Vi har ganske mye bare gikk frem og frem en hel haug med ganger, og vi 1088 00:41:10,220 --> 00:41:12,650 forskjøvet ting litt, bytte i denne rekkefølgen, kanskje 1089 00:41:12,650 --> 00:41:13,730 innsetting eller velge. 1090 00:41:13,730 --> 00:41:16,950 Men på slutten av dagen, gjorde jeg mye av klosset vandre frem og tilbake. 1091 00:41:16,950 --> 00:41:21,160 Vi gjorde egentlig ikke utnytte noe smart som Jennifer gjorde som å dele 1092 00:41:21,160 --> 00:41:22,040 og erobre. 1093 00:41:22,040 --> 00:41:25,620 >> Så flette sortere, derimot, som vi vil ikke se før neste uke, kommer det til 1094 00:41:25,620 --> 00:41:29,540 å utnytte at nøkkelen ideen ved å dele input, og deretter å halvere, og deretter 1095 00:41:29,540 --> 00:41:30,580 halvere, og deretter halvere. 1096 00:41:30,580 --> 00:41:34,590 Og på hver gjentakelse av den bue, sortering venstre halvdel, og retten 1097 00:41:34,590 --> 00:41:38,200 halvparten, deretter den venstre halvdelen av venstre halvdel, og den høyre halvdel av den venstre, deretter 1098 00:41:38,200 --> 00:41:40,990 den venstre halvdel av den høyre halvdel, og den høyre halvdelen av den høyre halvdel. 1099 00:41:40,990 --> 00:41:42,840 Og gjenta igjen og igjen. 1100 00:41:42,840 --> 00:41:46,170 >> Så vil du se dette visuelt, men dette er hva som venter oss neste uke. 1101 00:41:46,170 --> 00:41:49,760 Og generelt, når vi tenker litt litt hardere på slike problem. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Vi har n kvadrat på venstre, n kvadrat i midten, og n 1104 00:41:57,970 --> 00:41:59,400 logge n til høyre. 1105 00:41:59,400 --> 00:42:00,590 Så det er ditt virkelige cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Vi ser deg på mandag. 1107 00:42:02,040 --> 00:42:05,163 >> [APPLAUSE]