1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Musikk spilles] 3 00:00:10,800 --> 00:00:13,500 DAVID MALAN: All right. 4 00:00:13,500 --> 00:00:14,670 Greit, velkommen tilbake. 5 00:00:14,670 --> 00:00:18,120 Så dette er Uke 4, begynnelsen derav, som allerede. 6 00:00:18,120 --> 00:00:21,320 Og du husker at forrige uke, setter vi kode til side for bare litt 7 00:00:21,320 --> 00:00:24,240 og vi begynte å snakke litt mer høyt nivå, om ting som 8 00:00:24,240 --> 00:00:28,130 søking og sortering, som selv noe enkle ideer, er 9 00:00:28,130 --> 00:00:31,840 representative for en klasse av problemene vil du begynne å løse spesielt 10 00:00:31,840 --> 00:00:34,820 som du begynner å tenke på finalen prosjekter og interessante løsninger du 11 00:00:34,820 --> 00:00:36,760 kanskje reelle problemer. 12 00:00:36,760 --> 00:00:39,490 Nå boble sort ble en av de enkleste slike algoritmer, og det 13 00:00:39,490 --> 00:00:42,900 arbeidet ved å ha disse små tall i en liste eller i en matrise slags 14 00:00:42,900 --> 00:00:46,530 boble sin vei opp til toppen, og den store tallene beveger seg ned til 15 00:00:46,530 --> 00:00:47,930 slutten av den listen. 16 00:00:47,930 --> 00:00:50,650 >> Og husker at vi kunne visualisere boble sortere litt 17 00:00:50,650 --> 00:00:52,310 noe sånt som dette. 18 00:00:52,310 --> 00:00:53,640 Så la meg gå videre og klikk på Start. 19 00:00:53,640 --> 00:00:55,350 Jeg har forhåndsvalgt boble slag. 20 00:00:55,350 --> 00:00:58,920 Og hvis du husker at høyere blå linjer representerer store tall, små 21 00:00:58,920 --> 00:01:03,300 blå linjene representerer små tall, som vi gå gjennom dette igjen og igjen og 22 00:01:03,300 --> 00:01:07,680 igjen, sammenligne to barer ved siden av hver andre i rødt, vi kommer til å bytte 23 00:01:07,680 --> 00:01:11,010 største og den minste hvis de er ute av drift. 24 00:01:11,010 --> 00:01:14,150 >> Så dette vil gå på og gå på og gå på, og vil du se at større 25 00:01:14,150 --> 00:01:16,700 elementer er på vei til høyre, og de mindre elementene er 26 00:01:16,700 --> 00:01:17,900 på vei til venstre. 27 00:01:17,900 --> 00:01:21,380 Men vi begynte å kvantifisere effektiviteten, den 28 00:01:21,380 --> 00:01:22,970 Kvaliteten på denne algoritmen. 29 00:01:22,970 --> 00:01:25,200 Og vi sa at i verste tilfelle, tok denne algoritmen 30 00:01:25,200 --> 00:01:27,940 omtrent hvor mange skritt? 31 00:01:27,940 --> 00:01:28,980 >> Så n kvadrat. 32 00:01:28,980 --> 00:01:30,402 Og hva var n? 33 00:01:30,402 --> 00:01:31,650 >> PUBLIKUM: Antall elementer. 34 00:01:31,650 --> 00:01:32,790 >> DAVID MALAN: Så n var antall elementer. 35 00:01:32,790 --> 00:01:33,730 Og så skal vi gjøre dette oftere. 36 00:01:33,730 --> 00:01:36,650 Hver gang vi ønsker å snakke om størrelsen av et problem eller størrelsen på en 37 00:01:36,650 --> 00:01:39,140 input, eller hvor lang tid det tar å produsere et resultat, vil vi bare 38 00:01:39,140 --> 00:01:41,610 generalisert uansett inngangen er som n. 39 00:01:41,610 --> 00:01:45,970 Så tilbake i uke 0, antall sider i telefonboken var n. 40 00:01:45,970 --> 00:01:47,550 Antallet studenter i rommet var n. 41 00:01:47,550 --> 00:01:49,630 Så også her, vi følger dette mønsteret. 42 00:01:49,630 --> 00:01:52,800 >> Nå n squared er ikke spesielt fort, så vi prøvde å gjøre det bedre. 43 00:01:52,800 --> 00:01:55,970 Og så har vi sett på et par andre algoritmer, blant annet 44 00:01:55,970 --> 00:01:57,690 var valget slag. 45 00:01:57,690 --> 00:01:59,180 Så valget slags var litt annerledes. 46 00:01:59,180 --> 00:02:03,130 Det var nesten enklere, jeg tør si, der jeg startet på begynnelsen av 47 00:02:03,130 --> 00:02:06,740 liste av våre frivillige, og jeg bare igjen og igjen og igjen gikk gjennom 48 00:02:06,740 --> 00:02:10,060 listen, plukker ut den minste element om gangen og sette ham eller 49 00:02:10,060 --> 00:02:13,040 henne på begynnelsen av listen. 50 00:02:13,040 --> 00:02:16,410 >> Men også dette, når vi begynte å tenke gjennom matematikk og større 51 00:02:16,410 --> 00:02:19,860 bilde, tenkt på hvor mange ganger Jeg går frem og tilbake og tilbake 52 00:02:19,860 --> 00:02:24,090 og tilbake, sa vi i verste fall utvalg sortere, også, var det? 53 00:02:24,090 --> 00:02:24,960 n squared. 54 00:02:24,960 --> 00:02:27,490 Nå i den virkelige verden, kan det faktisk være marginalt raskere. 55 00:02:27,490 --> 00:02:30,620 Fordi igjen, det gjorde jeg ikke å holde backtracking når jeg hadde sortert 56 00:02:30,620 --> 00:02:31,880 minste elementene. 57 00:02:31,880 --> 00:02:35,090 Men hvis vi tenker veldig stor n, og hvis du liksom gjøre ute regnestykket som 58 00:02:35,090 --> 00:02:39,170 Jeg gjorde i styret, med n kvadrat minus noe, alt annet 59 00:02:39,170 --> 00:02:41,850 foruten n kvadrat, når n blir veldig store, ikke 60 00:02:41,850 --> 00:02:42,850 virkelig betyr så mye. 61 00:02:42,850 --> 00:02:45,470 Så som dataforskere, sorterer vi av snu det blinde øyet til mindre 62 00:02:45,470 --> 00:02:49,220 faktorer og fokusere bare på den faktoren i et uttrykk som kommer til å gjøre 63 00:02:49,220 --> 00:02:50,330 den største forskjellen. 64 00:02:50,330 --> 00:02:52,840 >> Vel, til slutt, så vi ved innsetting slag. 65 00:02:52,840 --> 00:02:56,620 Og dette var lik i ånd, men heller enn å gå gjennom iterativt og 66 00:02:56,620 --> 00:03:01,250 velge den minste elementet en om tid, jeg i stedet tok hånd som jeg 67 00:03:01,250 --> 00:03:04,070 ble delt ut, og jeg bestemte meg, alle høyre, hører du her. 68 00:03:04,070 --> 00:03:06,160 Da flyttet jeg videre til neste element og bestemte seg for at han eller 69 00:03:06,160 --> 00:03:07,470 hun tilhørte her. 70 00:03:07,470 --> 00:03:08,810 Og så flyttet jeg videre og videre. 71 00:03:08,810 --> 00:03:11,780 Og jeg kan til, underveis, skifte disse gutta for å 72 00:03:11,780 --> 00:03:13,030 gjøre plass til dem. 73 00:03:13,030 --> 00:03:16,880 Så det var liksom den mentale reversering av utvalget typen som vi 74 00:03:16,880 --> 00:03:18,630 kalt innsetting slag. 75 00:03:18,630 --> 00:03:20,810 >> Så disse emnene å skje i den virkelige verden. 76 00:03:20,810 --> 00:03:23,640 Bare et par år siden, da en viss senator kjørte for president, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, på det tidspunkt administrerende direktør i Google, faktisk hadde muligheten 78 00:03:27,160 --> 00:03:28,040 å intervjue ham. 79 00:03:28,040 --> 00:03:32,010 Og vi tenkte vi skulle dele denne YouTube klipp for deg her, hvis vi kunne slå opp 80 00:03:32,010 --> 00:03:32,950 volumet. 81 00:03:32,950 --> 00:03:39,360 >> [VIDEOAVSPILLING] 82 00:03:39,360 --> 00:03:44,620 >> -Nå, Senator, du er her på Google, og jeg liker å tenke på formannskapet 83 00:03:44,620 --> 00:03:46,042 som et jobbintervju. 84 00:03:46,042 --> 00:03:47,770 >> [Latter] 85 00:03:47,770 --> 00:03:50,800 >> -Nå er det vanskelig å få en jobb som president. 86 00:03:50,800 --> 00:03:52,480 Og du går gjennom påkjenningene nå. 87 00:03:52,480 --> 00:03:54,330 Det er også vanskelig å få en jobb hos Google. 88 00:03:54,330 --> 00:03:59,610 Vi har spørsmål, og vi ber våre kandidater spørsmål. 89 00:03:59,610 --> 00:04:02,250 Og dette er fra Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Latter] 91 00:04:05,325 --> 00:04:06,400 -Dere tror jeg tuller? 92 00:04:06,400 --> 00:04:08,750 Det er rett her. 93 00:04:08,750 --> 00:04:12,110 Hva er den mest effektive måten å sortere en million to-bits heltall? 94 00:04:12,110 --> 00:04:15,810 >> [Latter] 95 00:04:15,810 --> 00:04:18,260 >> -Vel, uh - 96 00:04:18,260 --> 00:04:19,029 >> -Jeg er lei for det. 97 00:04:19,029 --> 00:04:19,745 Kanskje vi bør - 98 00:04:19,745 --> 00:04:21,000 >> -Nei, nei, nei, nei, nei. 99 00:04:21,000 --> 00:04:21,470 >> -Det er ikke en - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Jeg tror boblen slags ville være feil vei å gå. 102 00:04:25,328 --> 00:04:26,792 >> [Latter] 103 00:04:26,792 --> 00:04:28,510 >> [Heier og applauderer] 104 00:04:28,510 --> 00:04:31,211 >> -Kom igjen, som fortalte ham dette? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [END VIDEOAVSPILLING] 107 00:04:33,350 --> 00:04:35,070 >> DAVID MALAN: Så det du har det. 108 00:04:35,070 --> 00:04:39,600 Så vi begynte å kvantifisere disse kjører ganger, så å si, med noe 109 00:04:39,600 --> 00:04:43,480 kalles asymptotisk notasjon, som er bare henvise til vår form for å snu 110 00:04:43,480 --> 00:04:47,420 et blindt øye til de mindre faktorer og bare se på løpende tid, 111 00:04:47,420 --> 00:04:51,250 utførelsen av disse algoritmene, som n blir veldig stor over tid. 112 00:04:51,250 --> 00:04:55,110 Og så vi introduserte big O. Og big O representerte noe som vi trodde 113 00:04:55,110 --> 00:04:57,000 på som en øvre grense. 114 00:04:57,000 --> 00:04:59,570 Og faktisk, Barry, kan vi senke enn mic litt? 115 00:04:59,570 --> 00:05:01,040 >> Vi tenkte på dette er en øvre grense. 116 00:05:01,040 --> 00:05:04,710 Så stor O for n kvadrat betyr at i verste fall, noe som 117 00:05:04,710 --> 00:05:07,780 utvalg slags ville ta n kvadrat trinn. 118 00:05:07,780 --> 00:05:10,310 Eller noe sånt innsetting slags ville n kvadrat trinn. 119 00:05:10,310 --> 00:05:15,150 Nå for noe sånt innsetting sortere, hva var det verste tilfellet? 120 00:05:15,150 --> 00:05:18,200 Gitt en matrise, er det verste mulig scenario at du kan finne 121 00:05:18,200 --> 00:05:20,650 selv møtt med? 122 00:05:20,650 --> 00:05:21,860 >> Det er helt baklengs, ikke sant? 123 00:05:21,860 --> 00:05:24,530 Fordi hvis det er helt baklengs, du trenger å gjøre en hel masse arbeid. 124 00:05:24,530 --> 00:05:26,420 Fordi hvis du er helt baklengs, du kommer til å finne den 125 00:05:26,420 --> 00:05:28,840 største momentet her, selv om det hører hjemme der nede. 126 00:05:28,840 --> 00:05:31,140 Så du kommer til å si, all right, på dette øyeblikket i tid, hører du her, 127 00:05:31,140 --> 00:05:32,310 så du la det være. 128 00:05:32,310 --> 00:05:35,425 >> Så du skjønner, oh, faen, jeg må flytte denne litt mindre element til 129 00:05:35,425 --> 00:05:36,470 venstre for deg. 130 00:05:36,470 --> 00:05:38,770 Da må jeg gjøre det igjen og igjen og igjen. 131 00:05:38,770 --> 00:05:41,410 Og hvis jeg gikk frem og tilbake, du ville liksom føle ytelsen 132 00:05:41,410 --> 00:05:45,540 at algoritmen, fordi stadig er jeg shuffling alle andre ned i 133 00:05:45,540 --> 00:05:46,510 array å gjøre plass til det. 134 00:05:46,510 --> 00:05:47,750 Så det er det verste tilfellet. 135 00:05:47,750 --> 00:05:48,570 >> I motsetning - 136 00:05:48,570 --> 00:05:50,320 og dette var en cliffhanger siste gang - 137 00:05:50,320 --> 00:05:54,065 vi sa at innsetting sortere var en omega av hva? 138 00:05:54,065 --> 00:05:57,530 Hva er den best-case løping tidspunktet for innsetting slag? 139 00:05:57,530 --> 00:05:58,520 Så det er faktisk n. 140 00:05:58,520 --> 00:06:00,980 Det var tomt da vi forlot på brettet forrige gang. 141 00:06:00,980 --> 00:06:03,160 >> Og det er omega for n fordi hvorfor? 142 00:06:03,160 --> 00:06:06,630 Vel, i de aller beste fall, hva er innsetting sortere kommer til å bli levert? 143 00:06:06,630 --> 00:06:09,830 Vel, en liste som er helt sortert allerede, minimalt arbeid å gjøre. 144 00:06:09,830 --> 00:06:12,460 Men hva er ryddig om innsetting slags er det fordi det starter her og 145 00:06:12,460 --> 00:06:15,340 bestemmer, oh, du er antall en, hører du her. 146 00:06:15,340 --> 00:06:16,970 Oh, what a hell. 147 00:06:16,970 --> 00:06:17,740 >> Du er nummer to. 148 00:06:17,740 --> 00:06:19,030 Du hører også her. 149 00:06:19,030 --> 00:06:21,010 Nummer tre, enda bedre, du hører hjemme her. 150 00:06:21,010 --> 00:06:25,210 Så snart det blir til slutten av liste, per innsetting sortere sin pseudokode 151 00:06:25,210 --> 00:06:28,010 at vi gikk gjennom verbalt siste gang, er det gjort. 152 00:06:28,010 --> 00:06:32,790 Men utvalget sortere, derimot, holdt gjør hva? 153 00:06:32,790 --> 00:06:35,260 >> Holdt gjennom listen igjen og igjen og igjen. 154 00:06:35,260 --> 00:06:39,160 Fordi det viktig innsikt var det bare når du har sett hele veien til 155 00:06:39,160 --> 00:06:42,500 slutten av listen kan du være sikker at elementet du valgte var 156 00:06:42,500 --> 00:06:45,560 faktisk den tiden minste elementet. 157 00:06:45,560 --> 00:06:48,920 Så disse forskjellige mentale modeller slutten opp gir noen svært virkelige verden 158 00:06:48,920 --> 00:06:53,130 forskjeller for oss, samt disse teoretiske asymptotiske forskjeller. 159 00:06:53,130 --> 00:06:56,910 >> Så bare for å gjenerobre, da, big O n kvadrat, har vi sett noen slike 160 00:06:56,910 --> 00:06:58,350 algoritmer så langt. 161 00:06:58,350 --> 00:06:59,580 Big O av n? 162 00:06:59,580 --> 00:07:02,870 Hva er en algoritme som kunne sies å være big O av n? 163 00:07:02,870 --> 00:07:06,930 I verste fall, det tar en lineær rekke trinn. 164 00:07:06,930 --> 00:07:07,810 >> OK, lineær søk. 165 00:07:07,810 --> 00:07:10,470 Og i verste fall, hvor er element du leter etter når 166 00:07:10,470 --> 00:07:12,950 anvende lineær søk? 167 00:07:12,950 --> 00:07:14,680 >> OK, i verste fall, det er ikke engang der. 168 00:07:14,680 --> 00:07:17,000 Eller i det nest verste tilfelle, er det helt til slutt, noe som er 169 00:07:17,000 --> 00:07:18,880 pluss-eller-minus en ett-trinns forskjell. 170 00:07:18,880 --> 00:07:21,180 Slik på slutten av dagen, vi kan si at det er lineær. 171 00:07:21,180 --> 00:07:23,910 Big O n ville være lineær søk, fordi i verste fall den 172 00:07:23,910 --> 00:07:26,610 element er ikke engang der, eller det er helt på slutten. 173 00:07:26,610 --> 00:07:29,370 >> Vel, big O av log n. 174 00:07:29,370 --> 00:07:32,760 Vi snakket ikke i stor detalj om dette, men vi har sett dette før. 175 00:07:32,760 --> 00:07:36,840 Hva kjører i såkalt logaritmisk tid, i verste fall? 176 00:07:36,840 --> 00:07:38,500 >> Ja, så binære søk. 177 00:07:38,500 --> 00:07:42,930 Og binære søk i verste fall kan ha element et sted i 178 00:07:42,930 --> 00:07:45,640 midten, eller et sted inne i matrisen. 179 00:07:45,640 --> 00:07:48,040 Men du bare finne det når du dele opp listen i to, i 180 00:07:48,040 --> 00:07:48,940 halvparten, i to, i to. 181 00:07:48,940 --> 00:07:50,200 Og så voila, det er der. 182 00:07:50,200 --> 00:07:52,500 Eller igjen, verste fall det er ikke engang der. 183 00:07:52,500 --> 00:07:56,770 Men du vet ikke at den ikke er der til du liksom nå det siste 184 00:07:56,770 --> 00:08:00,470 nederste fleste elementene ved å halvere og halvere og halvere. 185 00:08:00,470 --> 00:08:01,400 >> Big O av en. 186 00:08:01,400 --> 00:08:03,540 Slik at vi kunne big O 2, big O av tre. 187 00:08:03,540 --> 00:08:06,260 Når du vil bare et konstant tall, vi bare liksom bare forenkle 188 00:08:06,260 --> 00:08:07,280 at så store O av en. 189 00:08:07,280 --> 00:08:10,440 Selv om hvis realistisk, tar det 2 eller 100 skritt, hvis det er en 190 00:08:10,440 --> 00:08:13,680 konstant antall skritt, vi bare si big O av en. 191 00:08:13,680 --> 00:08:15,930 Hva er en algoritme som er i big O av en? 192 00:08:15,930 --> 00:08:18,350 >> PUBLIKUM: Finne lengden av en variabel. 193 00:08:18,350 --> 00:08:21,090 >> DAVID MALAN: Finne Lengden av en variabel? 194 00:08:21,090 --> 00:08:23,870 >> PUBLIKUM: Nei, lengden hvis det er allerede sortert. 195 00:08:23,870 --> 00:08:24,160 >> DAVID MALAN: Good. 196 00:08:24,160 --> 00:08:27,850 OK, så å finne lengden på noe Hvis lengden av det noe i likhet 197 00:08:27,850 --> 00:08:30,020 en matrise, er lagret på en eller annen variabel. 198 00:08:30,020 --> 00:08:33,380 Fordi du kan bare lese variabel, eller skrive ut variabelen, eller 199 00:08:33,380 --> 00:08:34,960 bare generelt få tilgang til variabelen. 200 00:08:34,960 --> 00:08:37,299 Og voila, som tar konstant tid. 201 00:08:37,299 --> 00:08:38,909 >> Derimot, tenker tilbake til scratch. 202 00:08:38,909 --> 00:08:42,460 Tenk tilbake til den første uken i C, ringer bare printf og utskrift 203 00:08:42,460 --> 00:08:46,240 noe på skjermen er uten tvil konstant tid, fordi det tar bare 204 00:08:46,240 --> 00:08:50,880 noen antall CPU-sykluser for å vise som tekst på skjermen. 205 00:08:50,880 --> 00:08:52,720 Eller vent - gjør det? 206 00:08:52,720 --> 00:08:56,430 Hvordan ellers kan vi modellere utførelsen av printf? 207 00:08:56,430 --> 00:09:00,420 Vil noen liker å være uenige, at kanskje det er egentlig ikke konstant tid? 208 00:09:00,420 --> 00:09:03,600 På hvilken måte kan printf kjører tid, faktisk skrive en streng på 209 00:09:03,600 --> 00:09:05,580 skjermen, være noe annet enn konstant. 210 00:09:05,580 --> 00:09:07,860 >> PUBLIKUM: [uhørlig]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID MALAN: Yeah. 212 00:09:08,230 --> 00:09:09,300 Så det kommer an på vårt perspektiv. 213 00:09:09,300 --> 00:09:13,390 Hvis vi faktisk tenker på innspill til printf som strengen, og 214 00:09:13,390 --> 00:09:16,380 derfor vi måle størrelsen av det inngang med lengde - så la oss kalle 215 00:09:16,380 --> 00:09:17,780 at lengden n også - 216 00:09:17,780 --> 00:09:21,990 uten tvil, er printf seg stor O n fordi det kommer til å ta deg n trinn 217 00:09:21,990 --> 00:09:24,750 å skrive ut hver av de n tegn, mest sannsynlig. 218 00:09:24,750 --> 00:09:27,730 I det minste i den grad at vi antar at kanskje den bruker en for loop 219 00:09:27,730 --> 00:09:28,560 under hetten. 220 00:09:28,560 --> 00:09:30,860 >> Men vi må se på det kode for å forstå det bedre. 221 00:09:30,860 --> 00:09:33,650 Og ja, når dere starter analysere dine egne algoritmer, vil du 222 00:09:33,650 --> 00:09:34,900 bokstavelig talt gjøre nettopp det. 223 00:09:34,900 --> 00:09:37,765 Sortering av øyeeplet koden din og tenke om - all right, jeg har denne sløyfen 224 00:09:37,765 --> 00:09:41,870 her eller jeg har en nestede løkker her, som kommer til å gjøre n ting n ganger, 225 00:09:41,870 --> 00:09:46,050 og du kan sortere på grunn din måte gjennom koden, selv om den er 226 00:09:46,050 --> 00:09:47,980 pseudokode og ikke selve koden. 227 00:09:47,980 --> 00:09:49,730 >> Så hva med omega for n kvadrat? 228 00:09:49,730 --> 00:09:53,582 Det var en algoritme som i beste tilfelle, likevel tok n kvadrat trinn? 229 00:09:53,582 --> 00:09:54,014 Yeah? 230 00:09:54,014 --> 00:09:54,880 >> PUBLIKUM: [uhørlig]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID MALAN: Så utvalg slag. 232 00:09:55,900 --> 00:09:59,150 Fordi i det problemet virkelig redusert til det faktum at igjen, jeg vet ikke 233 00:09:59,150 --> 00:10:02,600 Jeg har funnet den nåværende minste inntil Jeg har sjekket alle darn elementer. 234 00:10:02,600 --> 00:10:08,050 Så omega, sier n, vi bare kom opp med en. 235 00:10:08,050 --> 00:10:09,300 Innsetting slag. 236 00:10:09,300 --> 00:10:12,370 Hvis listen skjer skal sorteres allerede, i beste fall bare har vi 237 00:10:12,370 --> 00:10:15,090 å gjøre en pasning gjennom det, på hvilket tidspunkt vi er sikker. 238 00:10:15,090 --> 00:10:17,890 Og deretter som kan sies å være lineær, for sikker. 239 00:10:17,890 --> 00:10:20,570 >> Hva med omega for en? 240 00:10:20,570 --> 00:10:23,790 Hva, i beste fall, kan ta en konstant antall trinn? 241 00:10:23,790 --> 00:10:27,220 Så lineær søk, hvis du bare få heldige og elementet du leter 242 00:10:27,220 --> 00:10:31,000 er helt i begynnelsen av listen, Hvis det er der du starter din 243 00:10:31,000 --> 00:10:33,070 lineær traversering av den listen. 244 00:10:33,070 --> 00:10:35,180 >> Og dette er sant for en rekke ting. 245 00:10:35,180 --> 00:10:37,660 For eksempel, selv binær Søket er omega for en. 246 00:10:37,660 --> 00:10:40,310 For hva hvis du får virkelig darn heldig og smack-DAB i midten av 247 00:10:40,310 --> 00:10:42,950 klyngen er antall du leter etter? 248 00:10:42,950 --> 00:10:45,730 Så du kan ha flaks der, også. 249 00:10:45,730 --> 00:10:49,190 >> Denne, til slutt, omega for n log n. 250 00:10:49,190 --> 00:10:52,573 Så n log n, gjorde vi egentlig ikke snakke om ennå, men - 251 00:10:52,573 --> 00:10:53,300 >> PUBLIKUM: Flett slag? 252 00:10:53,300 --> 00:10:53,960 >> DAVID MALAN: Merge slag. 253 00:10:53,960 --> 00:10:56,920 Det var den cliffhanger av siste gang, hvor vi foreslått, og vi viste 254 00:10:56,920 --> 00:10:58,600 visuelt, at det er algoritmer. 255 00:10:58,600 --> 00:11:02,470 Og flette liksom bare én slik algoritme som er fundamentalt raskere 256 00:11:02,470 --> 00:11:03,450 enn noen av disse andre gutta. 257 00:11:03,450 --> 00:11:07,800 Faktisk fusjonere kort er ikke bare i best case n log n, i verste 258 00:11:07,800 --> 00:11:09,460 Ved n log n. 259 00:11:09,460 --> 00:11:14,540 Og når du har denne sammentreff av omega og stor O er det samme? 260 00:11:14,540 --> 00:11:17,310 Vi kan faktisk beskrive det som det er kalles theta, om det er en 261 00:11:17,310 --> 00:11:18,220 litt mindre vanlig. 262 00:11:18,220 --> 00:11:21,730 Men det betyr bare de to grenser, I dette tilfellet er de samme. 263 00:11:21,730 --> 00:11:25,770 >> Så flette sortere, hva betyr dette egentlig koker ned til for oss? 264 00:11:25,770 --> 00:11:27,000 Vel, husker motivasjon. 265 00:11:27,000 --> 00:11:30,340 La meg trekke opp en annen animasjon som Vi så ikke på forrige gang. 266 00:11:30,340 --> 00:11:33,390 Denne, samme idé, men det er litt større. 267 00:11:33,390 --> 00:11:36,160 Og jeg kommer til å gå videre og påpeke første - vi har innsetting slag på 268 00:11:36,160 --> 00:11:39,410 øverst til venstre, deretter valg sortere, boble sortere, et par andre former - 269 00:11:39,410 --> 00:11:42,670 skall og rask - at vi ikke har snakket om, og heap og flette slag. 270 00:11:42,670 --> 00:11:47,090 >> Så i det minste prøve å fokusere blikket på topp tre på venstre og deretter 271 00:11:47,090 --> 00:11:49,120 flette slag når jeg klikker Dette grønn pil. 272 00:11:49,120 --> 00:11:51,900 Men jeg skal la alle av dem kjøre, bare for å gi deg en følelse av mangfoldet i 273 00:11:51,900 --> 00:11:53,980 algoritmer som finnes i verden. 274 00:11:53,980 --> 00:11:56,180 Jeg kommer til å la denne kjøre for bare noen få sekunder. 275 00:11:56,180 --> 00:11:59,640 Og hvis du fokuserer øynene dine - velg en algoritme, fokusere på det for bare en 276 00:11:59,640 --> 00:12:02,970 sekunder - du vil begynne å se mønster som det er å implementere. 277 00:12:02,970 --> 00:12:04,530 >> Flette sortere, varsel, er gjort. 278 00:12:04,530 --> 00:12:06,430 Heap sortere, rask sortering, shell - 279 00:12:06,430 --> 00:12:09,480 så det synes vi introduserte tre verste algoritmer forrige uke. 280 00:12:09,480 --> 00:12:12,960 Men det er bra at vi er her i dag for å se på merge slag, som er en av 281 00:12:12,960 --> 00:12:16,500 de enklere er å se på, selv selv om det trolig vil bøye sinn 282 00:12:16,500 --> 00:12:17,490 bare en liten bit. 283 00:12:17,490 --> 00:12:21,130 Her kan vi se hvor mye utvalg slags suger. 284 00:12:21,130 --> 00:12:24,600 >> Men på baksiden, er det veldig lett å implementere. 285 00:12:24,600 --> 00:12:28,160 Og kanskje for P Set 3, det er en av de algoritmer du valgte å implementere 286 00:12:28,160 --> 00:12:28,960 for standardutgaven. 287 00:12:28,960 --> 00:12:30,970 Helt greit, helt riktig. 288 00:12:30,970 --> 00:12:35,210 >> Men igjen, som n blir stor, hvis du velge å gjennomføre en raskere algoritmen 289 00:12:35,210 --> 00:12:39,020 liker flette sortere, oddsen er i større og større innganger, er koden bare 290 00:12:39,020 --> 00:12:39,800 kommer til å kjøre fortere. 291 00:12:39,800 --> 00:12:41,090 Ditt nettsted kommer til å fungere bedre. 292 00:12:41,090 --> 00:12:42,650 Brukerne kommer til å være fornøyde. 293 00:12:42,650 --> 00:12:45,280 Og så er det disse effektene av faktisk å gi 294 00:12:45,280 --> 00:12:47,350 oss noen dypere trodde. 295 00:12:47,350 --> 00:12:49,990 >> Så la oss ta en titt på hva fusjonere typen er faktisk handler om. 296 00:12:49,990 --> 00:12:52,992 Det kule er at fusjonere typen er nettopp dette. 297 00:12:52,992 --> 00:12:56,300 Dette er, igjen, det vi har kalt pseudokode, pseudokode vesen 298 00:12:56,300 --> 00:12:57,720 Norsk-lignende syntaks. 299 00:12:57,720 --> 00:12:59,890 Og enkelhet er slags fascinerende. 300 00:12:59,890 --> 00:13:02,840 >> Så på input av n elementer - slik at betyr bare, her er en matrise. 301 00:13:02,840 --> 00:13:04,000 Det har n ting i den. 302 00:13:04,000 --> 00:13:05,370 Det er alt vi sier der. 303 00:13:05,370 --> 00:13:07,560 >> Hvis n er mindre enn 2, tilbake. 304 00:13:07,560 --> 00:13:08,640 Så det er bare den trivielle tilfelle. 305 00:13:08,640 --> 00:13:12,580 Hvis n er mindre enn to, så åpenbart at det er 1 eller 0, i hvilket tilfelle tingen 306 00:13:12,580 --> 00:13:14,780 er allerede sortert eller ikke-eksisterende, så bare komme tilbake. 307 00:13:14,780 --> 00:13:15,900 Det er ingenting å gjøre. 308 00:13:15,900 --> 00:13:18,360 Så det er en enkel sak å plukke av. 309 00:13:18,360 --> 00:13:20,110 >> Else, vi har tre trinn. 310 00:13:20,110 --> 00:13:23,650 Sortere venstre halvdel av elementene, sortere den høyre halvdel av elementene, 311 00:13:23,650 --> 00:13:26,650 og deretter flette sortert halvdeler. 312 00:13:26,650 --> 00:13:29,400 Det som er interessant her er at Jeg er litt punting, ikke sant? 313 00:13:29,400 --> 00:13:32,300 Det er på en måte en sirkulær definisjon til denne algoritmen. 314 00:13:32,300 --> 00:13:35,986 På hvilken måte er denne algoritmen er definition rundskrivet? 315 00:13:35,986 --> 00:13:37,850 >> PUBLIKUM: [uhørlig]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID MALAN: Ja, min sortering algoritme, to av sine trinnene er "slag 317 00:13:41,670 --> 00:13:44,640 noe. "Og så trygler spørsmålet, vel, hva jeg kommer til å bruke 318 00:13:44,640 --> 00:13:46,460 å sortere venstre halvdel og høyre halvdel? 319 00:13:46,460 --> 00:13:49,600 Og det fine her er at selv om igjen, dette er mind-bending 320 00:13:49,600 --> 00:13:54,030 del potensielt, kan du bruke samme algoritme for å sortere venstre halvdel. 321 00:13:54,030 --> 00:13:54,700 >> Men vent litt. 322 00:13:54,700 --> 00:13:57,070 Når du får beskjed om å sortere venstre halvdel, hva er de to 323 00:13:57,070 --> 00:13:58,240 trinn kommer til å bli neste? 324 00:13:58,240 --> 00:14:00,550 Vi vil sortere venstre halvdel av venstre halvdel og rett 325 00:14:00,550 --> 00:14:01,420 halvparten av den venstre halvdel. 326 00:14:01,420 --> 00:14:04,430 Damn, hvordan jeg sorterer disse to halvdeler, eller kvartaler, nå? 327 00:14:04,430 --> 00:14:05,260 >> Men det er OK. 328 00:14:05,260 --> 00:14:07,830 Vi har en sortering algoritme her. 329 00:14:07,830 --> 00:14:10,660 Og selv om du kanskje bekymre deg i først dette er litt av en uendelig 330 00:14:10,660 --> 00:14:12,780 loop, er det en syklus som aldri er kommer til å ende - det kommer til å 331 00:14:12,780 --> 00:14:15,770 ende en gang hva som skjer? 332 00:14:15,770 --> 00:14:16,970 Når n er mindre enn 2. 333 00:14:16,970 --> 00:14:19,180 Som til slutt kommer til å skje, fordi hvis du holder halvere og 334 00:14:19,180 --> 00:14:23,020 halvering i halvere disse halvdeler, sikkert slutt du kommer til å ende 335 00:14:23,020 --> 00:14:25,350 opp med bare 1 eller 0 elementer. 336 00:14:25,350 --> 00:14:28,500 På hvilket tidspunkt, denne algoritmen sier du er ferdig. 337 00:14:28,500 --> 00:14:31,020 >> Så den virkelige magien i dette algoritmen synes å være i 338 00:14:31,020 --> 00:14:33,470 at siste trinnet, sammenslåing. 339 00:14:33,470 --> 00:14:37,190 Det enkle ideen bare sammenslåing to ting, det er det som til syvende og sist kommer 340 00:14:37,190 --> 00:14:40,920 å tillate oss å sortere en rekke, la oss si, åtte elementer. 341 00:14:40,920 --> 00:14:44,410 Så jeg har åtte stress baller opp her, åtte biter av papir, og en 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 som jeg kommer til å holde. 344 00:14:46,140 --> 00:14:46,960 >> [Latter] 345 00:14:46,960 --> 00:14:48,970 >> DAVID MALAN: Hvis vi kunne ta åtte frivillige, og la oss se om vi kan 346 00:14:48,970 --> 00:14:51,430 spille dette ut, så. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Informatikk blir gøy. 349 00:14:53,565 --> 00:14:54,320 OK. 350 00:14:54,320 --> 00:14:57,770 Så hva med deg tre, største hånden oppe. 351 00:14:57,770 --> 00:14:58,580 Fire i ryggen. 352 00:14:58,580 --> 00:15:02,220 Og hva vi vil gjøre deg tre i denne raden? 353 00:15:02,220 --> 00:15:03,390 Og fire i front. 354 00:15:03,390 --> 00:15:04,920 Så du åtte, kom igjen opp. 355 00:15:04,920 --> 00:15:12,060 >> [Latter] 356 00:15:12,060 --> 00:15:13,450 >> DAVID MALAN: Jeg er faktisk ikke sikker på hva det er. 357 00:15:13,450 --> 00:15:14,810 Er det stress baller? 358 00:15:14,810 --> 00:15:16,510 Skrivebord-lamper? 359 00:15:16,510 --> 00:15:18,650 Materialet? 360 00:15:18,650 --> 00:15:19,680 Internett? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Så kom igjen opp. 363 00:15:21,310 --> 00:15:22,310 Hvem ønsker - 364 00:15:22,310 --> 00:15:23,570 fortsette å komme opp. 365 00:15:23,570 --> 00:15:24,240 La oss se. 366 00:15:24,240 --> 00:15:26,460 Og dette setter deg i sted - 367 00:15:26,460 --> 00:15:27,940 du er i stedet en. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, vent litt. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - OH, god. 370 00:15:30,760 --> 00:15:31,310 Greit, vi er bra. 371 00:15:31,310 --> 00:15:35,130 All right, slik at alle har en plass, men ikke på Google Glass. 372 00:15:35,130 --> 00:15:36,475 La meg til kø opp disse. 373 00:15:36,475 --> 00:15:37,115 Hva heter du? 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID MALAN: Michelle? 376 00:15:38,090 --> 00:15:42,000 Greit, du kommer til å se ut geek, hvis det er OK. 377 00:15:42,000 --> 00:15:44,625 Vel, jeg gjør også, antar jeg, for bare et øyeblikk. 378 00:15:44,625 --> 00:15:45,875 All right, standby. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Vi har prøvd å komme opp med en bruke saken for Google Glass, og vi 381 00:15:50,950 --> 00:15:53,750 trodde det ville være morsomt å bare gjøre dette når folk er på scenen. 382 00:15:53,750 --> 00:15:57,120 Vi vil dokumentere verden fra deres perspektiv. 383 00:15:57,120 --> 00:15:58,410 OK. 384 00:15:58,410 --> 00:15:59,830 Ikke nok hva Google ment. 385 00:15:59,830 --> 00:16:02,260 Greit, hvis du ikke tankene iført dette for de neste pinlige minutter, 386 00:16:02,260 --> 00:16:03,150 det ville være fantastisk. 387 00:16:03,150 --> 00:16:08,620 >> Ok, så vi har her et utvalg av elementer, og at utvalg, som per 388 00:16:08,620 --> 00:16:11,480 papirlapper i disse folkene ' hender, er for tiden usortert. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Å, det er så rart. 390 00:16:12,050 --> 00:16:12,810 >> DAVID MALAN: Det er ganske mye tilfeldig. 391 00:16:12,810 --> 00:16:15,760 Og om en liten stund, kommer vi til å prøve å gjennomføre fusjonere slags sammen 392 00:16:15,760 --> 00:16:17,950 og se hvor det viktig innsikt er. 393 00:16:17,950 --> 00:16:21,970 Og trikset her med merge sort er noe som vi ikke har antatt ennå. 394 00:16:21,970 --> 00:16:24,030 Vi må faktisk noen ekstra plass. 395 00:16:24,030 --> 00:16:26,650 Så hva kommer til å være spesielt interessant med dette er at disse 396 00:16:26,650 --> 00:16:29,270 Gutta kommer til å bevege seg litt litt, fordi jeg kommer til å anta at 397 00:16:29,270 --> 00:16:31,880 det er et ekstra utvalg av plass, si, rett bak dem. 398 00:16:31,880 --> 00:16:34,570 >> Så hvis de er bak stolen sin, det er den sekundære array. 399 00:16:34,570 --> 00:16:36,960 Hvis de er satt her, er at den primære array. 400 00:16:36,960 --> 00:16:40,170 Men dette er en ressurs som vi har ikke utnyttes så langt med boble 401 00:16:40,170 --> 00:16:42,040 sortere, med utvalg sortere, med innsetting slag. 402 00:16:42,040 --> 00:16:44,600 Recall forrige uke, alle bare slags stokket på plass. 403 00:16:44,600 --> 00:16:46,840 De brukte ikke noe ekstra minne. 404 00:16:46,840 --> 00:16:49,310 Vi gjorde plass for folk med flytte folk rundt. 405 00:16:49,310 --> 00:16:50,580 >> Så dette er en viktig innsikt, også. 406 00:16:50,580 --> 00:16:53,410 Det er denne avveiingen, generelt i informatikk, av ressurser. 407 00:16:53,410 --> 00:16:55,800 Hvis du ønsker å fremskynde noe som tid, du kommer til 408 00:16:55,800 --> 00:16:56,900 må betale en pris. 409 00:16:56,900 --> 00:17:00,750 Og en av disse prisene er svært ofte plass, hvor mye minne eller hard 410 00:17:00,750 --> 00:17:01,700 diskplass som du bruker. 411 00:17:01,700 --> 00:17:03,640 Eller, ærlig talt, hvor mye av programmerer tid. 412 00:17:03,640 --> 00:17:06,700 Hvor mye tid det tar deg, det menneskelige, å faktisk gjennomføre noen mer 413 00:17:06,700 --> 00:17:07,829 komplisert algoritme. 414 00:17:07,829 --> 00:17:09,760 Men for i dag, bytteforholdet er tid og rom. 415 00:17:09,760 --> 00:17:11,930 >> Så hvis dere kunne bare holde opp tallene slik at vi kan se at du er 416 00:17:11,930 --> 00:17:15,839 faktisk matchende 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Utmerket. 418 00:17:16,599 --> 00:17:19,520 Så jeg kommer til å prøve å orkestrere ting, om dere kan bare 419 00:17:19,520 --> 00:17:21,800 følge min bly her. 420 00:17:21,800 --> 00:17:26,650 >> Så jeg kommer til å gjennomføre, først, første trinn i pseudokode, som er 421 00:17:26,650 --> 00:17:29,440 på input av n elementer, hvis n er mindre enn to, så tilbake. 422 00:17:29,440 --> 00:17:31,370 Selvfølgelig gjør det ikke lappeteppe, så vi går videre. 423 00:17:31,370 --> 00:17:33,340 Så sorterer den venstre halvdelen av elementene. 424 00:17:33,340 --> 00:17:36,220 Så det betyr at jeg kommer til å fokusere min oppmerksomhet for bare et øyeblikk på disse 425 00:17:36,220 --> 00:17:37,310 fire gutta her. 426 00:17:37,310 --> 00:17:39,774 Ok, hva gjør jeg neste gjøre? 427 00:17:39,774 --> 00:17:40,570 >> PUBLIKUM: Sorter venstre halvdel. 428 00:17:40,570 --> 00:17:42,780 >> DAVID MALAN: Så nå har jeg til å sortere den venstre halvdelen av disse gutta. 429 00:17:42,780 --> 00:17:45,580 Fordi igjen, antar deg selv Målet er å sortere venstre halvdel. 430 00:17:45,580 --> 00:17:46,440 Hvordan gjør dere det? 431 00:17:46,440 --> 00:17:49,140 Bare følg instruksjonene, selv selv om vi gjør det igjen. 432 00:17:49,140 --> 00:17:50,160 Så sorterer venstre halvdel. 433 00:17:50,160 --> 00:17:52,030 Nå er jeg sortere disse to gutta. 434 00:17:52,030 --> 00:17:53,563 Hva kommer etterpå? 435 00:17:53,563 --> 00:17:54,510 >> PUBLIKUM: Sorter venstre halvdel. 436 00:17:54,510 --> 00:17:55,460 >> DAVID MALAN: Sorter venstre halvdel. 437 00:17:55,460 --> 00:18:00,680 Så nå disse, dette setet her, er en liste over størrelse 1. 438 00:18:00,680 --> 00:18:01,365 Og hva heter du igjen? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Princess Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID MALAN: Princess Daisy er her. 441 00:18:03,690 --> 00:18:07,470 Og så er hun allerede sortert, fordi listen er av størrelse 1. 442 00:18:07,470 --> 00:18:09,490 Hva gjør jeg neste gjøre? 443 00:18:09,490 --> 00:18:13,680 OK, tilbake, fordi den listen er av størrelse 1, som er mindre enn 2. 444 00:18:13,680 --> 00:18:14,320 Så hva er neste steg? 445 00:18:14,320 --> 00:18:17,490 Og nå må du slags Backtrack i tankene dine. 446 00:18:17,490 --> 00:18:19,340 >> Sortere høyre halvdel, som er - 447 00:18:19,340 --> 00:18:19,570 hva heter du? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID MALAN: Linda. 450 00:18:20,980 --> 00:18:23,210 Og så hva gjør vi nå at Vi har en liste over størrelse 1? 451 00:18:23,210 --> 00:18:24,440 >> PUBLIKUM: Return. 452 00:18:24,440 --> 00:18:24,760 >> DAVID MALAN: Forsiktig. 453 00:18:24,760 --> 00:18:29,540 Vi kommer tilbake først, og nå den tredje trinn - og hvis jeg slags skildre det ved 454 00:18:29,540 --> 00:18:33,490 omfavner de to setene nå, nå er jeg nødt til å flette disse to elementene. 455 00:18:33,490 --> 00:18:35,530 Så nå dessverre, elementene er ute av drift. 456 00:18:35,530 --> 00:18:39,920 Men det er der fusjonsprosessen begynner å bli overbevisende. 457 00:18:39,920 --> 00:18:42,410 >> Så hvis dere kunne stå opp for bare et øyeblikk, jeg kommer til å trenge deg, i en 458 00:18:42,410 --> 00:18:44,170 øyeblikk, å gå bak stolen. 459 00:18:44,170 --> 00:18:46,480 Og hvis Linda, fordi to er mindre enn 4, hva 460 00:18:46,480 --> 00:18:48,130 du kommer rundt først? 461 00:18:48,130 --> 00:18:48,690 Bo der. 462 00:18:48,690 --> 00:18:50,520 Så Linda, kom deg rundt først. 463 00:18:50,520 --> 00:18:53,820 >> Nå i virkeligheten om det er bare en matrise vi kan bare flytte henne i sanntid 464 00:18:53,820 --> 00:18:55,360 fra denne stolen til dette stedet. 465 00:18:55,360 --> 00:18:57,770 Så tenk deg at tok noen konstant antall trinn: 1. 466 00:18:57,770 --> 00:18:58,480 Og nå - 467 00:18:58,480 --> 00:19:01,490 men vi trenger å sette deg i den første plasseringen her. 468 00:19:01,490 --> 00:19:03,930 >> Og nå hvis du kunne komme rundt, også, skal vi 469 00:19:03,930 --> 00:19:06,300 være på plass to. 470 00:19:06,300 --> 00:19:09,120 Og selv om dette føles som det er ta en stund, hva er fint nå er 471 00:19:09,120 --> 00:19:14,710 at den venstre halvdelen av venstre halvdelen er nå sortert. 472 00:19:14,710 --> 00:19:18,010 Så hva var neste skritt, hvis vi nå spole videre i historien? 473 00:19:18,010 --> 00:19:18,980 >> PUBLIKUM: Høyre halvdel. 474 00:19:18,980 --> 00:19:19,900 >> DAVID MALAN: Sortere høyre halvdel. 475 00:19:19,900 --> 00:19:21,320 Så dere må gjøre dette, også. 476 00:19:21,320 --> 00:19:23,510 Så hvis du kunne stå opp for bare et øyeblikk? 477 00:19:23,510 --> 00:19:25,192 Og hva heter du? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID MALAN: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, så Jess er nå den venstre halvdelen av den høyre halvdel. 481 00:19:29,720 --> 00:19:31,400 Og så er hun en liste med størrelse 1. 482 00:19:31,400 --> 00:19:32,380 Hun er åpenbart sortert. 483 00:19:32,380 --> 00:19:33,070 Og navnet ditt igjen? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID MALAN: Michelle er åpenbart en liste med størrelse 1. 486 00:19:35,340 --> 00:19:36,050 Hun har allerede sortert. 487 00:19:36,050 --> 00:19:38,690 Så nå magien skjer, fusjonsprosessen. 488 00:19:38,690 --> 00:19:39,790 Så hvem kommer til å komme først? 489 00:19:39,790 --> 00:19:41,560 Tydeligvis Michelle. 490 00:19:41,560 --> 00:19:43,280 Så hvis du kunne komme rundt ryggen. 491 00:19:43,280 --> 00:19:47,090 Plassen vi har tilgjengelig for henne nå er rett bak denne stolen her. 492 00:19:47,090 --> 00:19:51,580 Og nå hvis du kunne komme tilbake også, vi nå har, for å være klar, to 493 00:19:51,580 --> 00:19:53,810 halvdeler, hver på størrelse 2 - 494 00:19:53,810 --> 00:19:57,090 og bare for skildring skyld, hvis du kunne gjøre en liten bit av en plass - 495 00:19:57,090 --> 00:19:59,780 man forlot halvparten her, en høyre halvdel her. 496 00:19:59,780 --> 00:20:01,160 >> Spol tilbake videre i historien. 497 00:20:01,160 --> 00:20:02,270 Hva trinnet er neste? 498 00:20:02,270 --> 00:20:03,030 >> PUBLIKUM: Flett. 499 00:20:03,030 --> 00:20:04,160 >> DAVID MALAN: Så nå har vi å fusjonere. 500 00:20:04,160 --> 00:20:07,490 Så OK, så nå, heldigvis, vi bare frigjort fire stoler. 501 00:20:07,490 --> 00:20:11,480 Så vi har brukt dobbelt så mye minne, men vi kan gi flip-flopper mellom 502 00:20:11,480 --> 00:20:12,330 de to arrays. 503 00:20:12,330 --> 00:20:14,190 Så hvilke tall er å komme først? 504 00:20:14,190 --> 00:20:14,850 Så Michelle, selvsagt. 505 00:20:14,850 --> 00:20:16,680 Så kom rundt og ta ditt sete her. 506 00:20:16,680 --> 00:20:19,120 Og så nummer to er åpenbart neste, så du kommer hit. 507 00:20:19,120 --> 00:20:21,520 Nummer 4, nummer 6. 508 00:20:21,520 --> 00:20:23,390 Og igjen, selv om det er en liten bit av vandre involvert, 509 00:20:23,390 --> 00:20:26,010 egentlig, disse kunne skje umiddelbart, av en bevegelse - 510 00:20:26,010 --> 00:20:26,880 OK, godt spilt. 511 00:20:26,880 --> 00:20:28,350 >> [Latter] 512 00:20:28,350 --> 00:20:29,680 >> DAVID MALAN: Og nå er vi i ganske god form. 513 00:20:29,680 --> 00:20:34,910 Den venstre halvdel av hele innspill har nå blitt sortert. 514 00:20:34,910 --> 00:20:37,370 Ok, så disse gutta hadde fordelen av min - 515 00:20:37,370 --> 00:20:40,340 hvordan gikk det ender opp med alle jentene på venstre og alle guttene på høyre? 516 00:20:40,340 --> 00:20:42,450 >> OK, så gutta "snu nå. 517 00:20:42,450 --> 00:20:44,680 Så jeg vil ikke gå gjennom disse trinnene. 518 00:20:44,680 --> 00:20:46,550 Vi får se om vi kan bruke på nytt samme pseudokode. 519 00:20:46,550 --> 00:20:50,050 Hvis du ønsker å gå videre og stå opp, og dere, la meg gi deg mic. 520 00:20:50,050 --> 00:20:52,990 Se om du ikke kan gjenskape det vi nettopp gjorde her på 521 00:20:52,990 --> 00:20:53,880 andre enden av listen. 522 00:20:53,880 --> 00:20:59,530 Som trenger å snakke først, basert på algoritmen? 523 00:20:59,530 --> 00:21:03,210 Så forklare hva du gjør før du gjør noen fot bevegelser. 524 00:21:03,210 --> 00:21:05,930 >> SPEAKER 1: All right, så siden Jeg er den venstre halvdelen av 525 00:21:05,930 --> 00:21:07,790 venstre halvdel, jeg kommer tilbake. 526 00:21:07,790 --> 00:21:08,730 Høyre? 527 00:21:08,730 --> 00:21:09,250 >> DAVID MALAN: Good. 528 00:21:09,250 --> 00:21:10,350 >> SPEAKER 1: Og så - 529 00:21:10,350 --> 00:21:11,800 >> DAVID MALAN: Hvem gjør mic gå til neste? 530 00:21:11,800 --> 00:21:12,920 >> SPEAKER 1: Neste nummer. 531 00:21:12,920 --> 00:21:14,720 >> SPEAKER 2: Så jeg er høyre halvdel av den venstre halvdel av 532 00:21:14,720 --> 00:21:17,830 venstre halvdel, og jeg kommer tilbake. 533 00:21:17,830 --> 00:21:18,050 >> DAVID MALAN: Good. 534 00:21:18,050 --> 00:21:18,550 Du kommer tilbake. 535 00:21:18,550 --> 00:21:21,855 Så nå hva er neste opp for dere to? 536 00:21:21,855 --> 00:21:23,740 >> SPEAKER 2: Vi vil se hvem som er mindre. 537 00:21:23,740 --> 00:21:24,200 >> DAVID MALAN: Nettopp. 538 00:21:24,200 --> 00:21:24,940 Vi ønsker å slå seg sammen. 539 00:21:24,940 --> 00:21:27,590 Plassen vi skal bruke til å fusjonere deg inn, selv om de er 540 00:21:27,590 --> 00:21:30,250 åpenbart sortert allerede, vi skal å følge den samme algoritmen. 541 00:21:30,250 --> 00:21:31,560 Så hvem går inn bakerst først? 542 00:21:31,560 --> 00:21:35,720 Så tre, og deretter 7. 543 00:21:35,720 --> 00:21:38,570 Og nå mic går til disse gutta, OK? 544 00:21:38,570 --> 00:21:43,590 >> SPEAKER 3: Så jeg er den høyre halvdelen av venstre halvdel, og min n er mindre enn 545 00:21:43,590 --> 00:21:45,048 En, så jeg bare kommer til å passere - 546 00:21:45,048 --> 00:21:46,380 >> DAVID MALAN: Good. 547 00:21:46,380 --> 00:21:49,450 >> SPEAKER 4: Jeg er den høyre halvdelen av høyre halvdel av høyre halvdel, og jeg er 548 00:21:49,450 --> 00:21:51,740 man også person, så jeg er kommer til å returnere. 549 00:21:51,740 --> 00:21:52,990 Så nå er vi flette. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> SPEAKER 3: Så vi går tilbake. 552 00:21:56,150 --> 00:21:57,160 >> DAVID MALAN: Så du går inn på baksiden. 553 00:21:57,160 --> 00:21:59,200 Så 5 går først, deretter åtte. 554 00:21:59,200 --> 00:22:01,240 Og nå publikum, som er trinn må vi nå spole tilbake 555 00:22:01,240 --> 00:22:02,200 tilbake til i våre sinn? 556 00:22:02,200 --> 00:22:02,940 >> PUBLIKUM: Flett. 557 00:22:02,940 --> 00:22:07,270 >> DAVID MALAN: Sammenslåing venstre halvdel og høyre halvparten av den opprinnelige venstre halvdel. 558 00:22:07,270 --> 00:22:08,840 Så nå - 559 00:22:08,840 --> 00:22:10,520 og bare for å gjøre dette klart, gjøre en liten bit av plass 560 00:22:10,520 --> 00:22:11,690 mellom du to gutter. 561 00:22:11,690 --> 00:22:13,800 Så nå det er de to listene, venstre og høyre. 562 00:22:13,800 --> 00:22:18,320 Så hvordan skal vi nå slå sammen dere inn første rad av seter igjen? 563 00:22:18,320 --> 00:22:19,600 >> 3 går først. 564 00:22:19,600 --> 00:22:20,850 Deretter 5, selvsagt. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Deretter 7, og nå åtte. 567 00:22:27,330 --> 00:22:28,710 OK, og nå er vi? 568 00:22:28,710 --> 00:22:29,650 >> PUBLIKUM: Ikke gjort. 569 00:22:29,650 --> 00:22:32,440 >> DAVID MALAN: Ikke gjort, fordi åpenbart, det er ett skritt gjenstår. 570 00:22:32,440 --> 00:22:35,720 Men igjen, grunnen til at jeg bruker denne sjargong som "spole tilbake i tankene dine," 571 00:22:35,720 --> 00:22:37,160 det er fordi det er virkelig hva som skjer. 572 00:22:37,160 --> 00:22:39,610 Vi går gjennom alle disse trinnene, men vi er liksom pause for en 573 00:22:39,610 --> 00:22:42,480 øyeblikk, dykke dypere inn i algoritme, pause for et øyeblikk, 574 00:22:42,480 --> 00:22:45,840 dykking dypere inn i algoritmen, og nå må vi liksom bakover i vår 575 00:22:45,840 --> 00:22:49,430 sinn og angre alle disse lagene at vi har liksom satt på vent. 576 00:22:49,430 --> 00:22:51,790 >> Så nå har vi to lister med størrelse 4. 577 00:22:51,790 --> 00:22:54,790 Hvis dere kunne stå opp en siste gang og lage litt plass her til 578 00:22:54,790 --> 00:22:57,230 gjøre det klart at dette er venstre halvparten av den opprinnelige, jo 579 00:22:57,230 --> 00:22:58,620 høyre halvdel av den opprinnelige. 580 00:22:58,620 --> 00:23:01,060 Hvem er det første tallet som vi behov for å trekke inn i ryggen? 581 00:23:01,060 --> 00:23:01,870 Michelle, selvfølgelig. 582 00:23:01,870 --> 00:23:03,230 >> Så vi satt Michelle her. 583 00:23:03,230 --> 00:23:05,080 Og hvem har nummer to? 584 00:23:05,080 --> 00:23:06,440 Nummer to kommer på ryggen også. 585 00:23:06,440 --> 00:23:07,800 Nummer 3? 586 00:23:07,800 --> 00:23:08,510 Utmerket. 587 00:23:08,510 --> 00:23:16,570 Nummer 4, nummer fem, nummer 6, nummer 7, og nummer åtte. 588 00:23:16,570 --> 00:23:18,850 >> OK, så det føltes som mye trinn, for sikker. 589 00:23:18,850 --> 00:23:22,390 Men nå la oss se om vi ikke kan bekrefte slags intuitivt at dette 590 00:23:22,390 --> 00:23:26,190 algoritme fundamentalt, spesielt som n blir veldig store, som vi har sett 591 00:23:26,190 --> 00:23:29,170 med animasjoner, er fundamentalt raskere. 592 00:23:29,170 --> 00:23:33,400 Så jeg hevder denne algoritmen i verste tilfelle, og selv i de beste tilfeller 593 00:23:33,400 --> 00:23:36,160 er big O for n ganger log n. 594 00:23:36,160 --> 00:23:39,160 Det vil si, det er noen aspekter av dette algoritme som tar n trinn, men 595 00:23:39,160 --> 00:23:43,110 det er et annet aspekt sted i som iterasjon, som looping, som 596 00:23:43,110 --> 00:23:44,410 tar log n trinn. 597 00:23:44,410 --> 00:23:49,154 Kan vi sette vår fingeren på hva de to tallene henviser til? 598 00:23:49,154 --> 00:23:51,320 Vel, der - 599 00:23:51,320 --> 00:23:54,160 Hvor gikk mic reise? 600 00:23:54,160 --> 00:23:58,660 >> SPEAKER 1: Ville logge n være bryte oss opp i to - 601 00:23:58,660 --> 00:23:59,630 dividere med to, i det vesentlige. 602 00:23:59,630 --> 00:24:00,120 >> DAVID MALAN: Nettopp. 603 00:24:00,120 --> 00:24:03,000 Hver gang vi ser på noen algoritme dermed langt har det vært dette mønsteret av 604 00:24:03,000 --> 00:24:04,200 dele, dele, dele seg. 605 00:24:04,200 --> 00:24:05,700 Og det er vanligvis redusert til noe som er 606 00:24:05,700 --> 00:24:07,100 logaritmisk, log base 2. 607 00:24:07,100 --> 00:24:10,180 Men det kan egentlig være hva som helst, men logger base 2. 608 00:24:10,180 --> 00:24:11,330 >> Hva nå om den n? 609 00:24:11,330 --> 00:24:14,550 Jeg kan se at vi på en måte delt deg Gutta - delt deg, delt deg, 610 00:24:14,550 --> 00:24:15,910 delt deg, delt deg. 611 00:24:15,910 --> 00:24:18,760 Hvor kommer enden fra? 612 00:24:18,760 --> 00:24:19,810 >> Så det er en sammenslåing. 613 00:24:19,810 --> 00:24:20,610 Fordi tenke på det. 614 00:24:20,610 --> 00:24:25,420 Når du slår sammen åtte mennesker sammen, hvorved halvparten av dem er et sett av fire 615 00:24:25,420 --> 00:24:27,770 og den andre halvparten er en annen sett med fire, hvordan du går 616 00:24:27,770 --> 00:24:28,820 om å gjøre sammenslåing? 617 00:24:28,820 --> 00:24:30,830 Vel, det gjorde dere det ganske intuitivt. 618 00:24:30,830 --> 00:24:34,140 >> Men hvis jeg i stedet gjorde det litt mer metodisk, kanskje jeg har pekt på 619 00:24:34,140 --> 00:24:38,090 lengst til venstre personen først med min venstre hånd, pekte på leftmost person 620 00:24:38,090 --> 00:24:42,080 av at halvparten med min høyre hånd, og bare senere gikk gjennom 621 00:24:42,080 --> 00:24:46,990 listen, peker på det minste elementet hver gang, beveger fingeren over og 622 00:24:46,990 --> 00:24:48,970 enn etter behov i løpet listen. 623 00:24:48,970 --> 00:24:51,890 Men hva er nøkkelen om dette sammenslåing Prosessen er jeg sammenlikne disse parene 624 00:24:51,890 --> 00:24:53,460 av elementer. 625 00:24:53,460 --> 00:24:57,270 Fra høyre halvdel og fra venstre halvparten, jeg aldri en gang tilbakesporing. 626 00:24:57,270 --> 00:25:00,570 >> Så flettingen selv tar ikke mer enn n trinn. 627 00:25:00,570 --> 00:25:03,250 Og hvor mange ganger har jeg har å gjøre det sammenslåing? 628 00:25:03,250 --> 00:25:07,150 Vel, ikke mer enn n, og vi bare så at med den endelige flettingen. 629 00:25:07,150 --> 00:25:13,120 Og så hvis du gjør noe som tar log n trinn n ganger, eller vice versa, 630 00:25:13,120 --> 00:25:15,210 det kommer til å gi oss n ganger log n. 631 00:25:15,210 --> 00:25:16,310 >> Og hvorfor er dette bedre? 632 00:25:16,310 --> 00:25:19,600 Vel, hvis vi allerede vet at log n er bedre enn n - ikke sant? 633 00:25:19,600 --> 00:25:22,590 Vi så i binær søk, telefonboken eksempel var log n definitivt 634 00:25:22,590 --> 00:25:23,760 bedre enn lineær. 635 00:25:23,760 --> 00:25:28,420 Så det betyr n ganger log n er definitivt bedre enn n ganger en annen 636 00:25:28,420 --> 00:25:30,390 n, AKA n kvadrat. 637 00:25:30,390 --> 00:25:32,400 Og det er det vi til slutt føler. 638 00:25:32,400 --> 00:25:34,928 >> Så stor applaus, hvis vi kunne, for disse gutta. 639 00:25:34,928 --> 00:25:38,920 >> [APPLAUSE] 640 00:25:38,920 --> 00:25:41,550 >> DAVID MALAN: Og dine avskjeds gaver - du kan beholde tallene, 641 00:25:41,550 --> 00:25:44,010 hvis du ønsker. 642 00:25:44,010 --> 00:25:45,620 Og avskjedsgave, som vanlig. 643 00:25:45,620 --> 00:25:47,290 Oh, og vi vil sende deg opptakene, Michelle. 644 00:25:47,290 --> 00:25:48,343 Takk. 645 00:25:48,343 --> 00:25:49,250 OK. 646 00:25:49,250 --> 00:25:50,400 Forsyn deg med en stress ball. 647 00:25:50,400 --> 00:25:54,110 >> Og la meg trekke opp, i mellomtiden, vår venn Rob Bowden å tilby 648 00:25:54,110 --> 00:25:59,520 noe annet perspektiv på dette, siden du kan tenke på disse 649 00:25:59,520 --> 00:26:01,280 trinn som skjer i en noe annen måte. 650 00:26:01,280 --> 00:26:04,750 Faktisk oppsett for hva Rob handler om å vise oss forutsetter at vi har 651 00:26:04,750 --> 00:26:09,030 allerede gjort dele opp av stor liste i åtte små lister, 652 00:26:09,030 --> 00:26:10,570 hver av størrelse 1. 653 00:26:10,570 --> 00:26:13,350 >> Så vi endrer pseudokode en litt bare for å liksom få på 654 00:26:13,350 --> 00:26:15,320 kjernen ideen om hvordan sammenslåing fungerer. 655 00:26:15,320 --> 00:26:17,600 Men kjøretiden til hva han er i ferd med å gjøre er fortsatt 656 00:26:17,600 --> 00:26:19,110 kommer til å være den samme. 657 00:26:19,110 --> 00:26:23,540 Og igjen, er det satt opp her at han er begynt med åtte lister over størrelse 1. 658 00:26:23,540 --> 00:26:27,730 Så du har gått glipp av den delen hvor han er faktisk gjort log n, log n, log n 659 00:26:27,730 --> 00:26:31,205 delende på inngangen. 660 00:26:31,205 --> 00:26:32,120 >> [VIDEOAVSPILLING] 661 00:26:32,120 --> 00:26:33,615 >> -Det er det for trinn én. 662 00:26:33,615 --> 00:26:38,270 For to trinn, flere ganger flette par lister. 663 00:26:38,270 --> 00:26:39,210 >> DAVID MALAN: Hm. 664 00:26:39,210 --> 00:26:41,270 Bare lyden kommer ut av datamaskinen min. 665 00:26:41,270 --> 00:26:42,520 La oss prøve dette igjen. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Just vilkårlig plukke som - nå har vi fire lister. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Lære før. 670 00:26:52,120 --> 00:26:53,040 >> DAVID MALAN: Det vi går. 671 00:26:53,040 --> 00:27:00,510 >> -Sammenslåing 108 og 15, ender vi opp med listen 15, 108.. 672 00:27:00,510 --> 00:27:07,170 Sammenslåing 50 og 4, vi ende opp med 4, 50. 673 00:27:07,170 --> 00:27:12,990 Sammenslåing 8 og 42, vi ende opp med 8, 42. 674 00:27:12,990 --> 00:27:19,970 Og sammenslåing 23 og 16, vi ende opp med 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Nå er alle våre lister som er av størrelse 2. 676 00:27:23,270 --> 00:27:26,690 Legg merke til at hver av de fire listene er sortert. 677 00:27:26,690 --> 00:27:29,450 Så kan vi begynne å slå sammen par av listene igjen. 678 00:27:29,450 --> 00:27:38,420 Sammenslåing 15 og 108 og 4 og 50, vi først ta fire, deretter 15, deretter 679 00:27:38,420 --> 00:27:41,500 den 50, og den 108.. 680 00:27:41,500 --> 00:27:50,610 Sammenslåing 8, 42 og 16, 23, må vi først ta på 8, og deretter til 16, deretter 23 681 00:27:50,610 --> 00:27:52,700 Da den 42. 682 00:27:52,700 --> 00:27:57,600 >> Så nå har vi bare to lister med størrelse 4, er hver av disse sorteres. 683 00:27:57,600 --> 00:28:01,170 Så nå er vi slå sammen disse to listene. 684 00:28:01,170 --> 00:28:11,835 Først tar vi fire, så vi tar 8, og deretter tar vi 15, så 16, så 685 00:28:11,835 --> 00:28:19,456 23, så 42, ​​så 50, så 108. 686 00:28:19,456 --> 00:28:19,872 >> [END VIDEOAVSPILLING] 687 00:28:19,872 --> 00:28:23,430 >> DAVID MALAN: Igjen, varsel, aldri han rørt en gitt kopp mer enn én gang 688 00:28:23,430 --> 00:28:24,860 etter å gå forbi den. 689 00:28:24,860 --> 00:28:26,200 Så han aldri gjenta. 690 00:28:26,200 --> 00:28:29,850 Så han alltid beveger seg til siden, og det er der vi fikk vår n. 691 00:28:29,850 --> 00:28:33,290 >> Hvorfor ikke la meg trekke opp en animasjon som vi så tidligere, men denne gangen 692 00:28:33,290 --> 00:28:35,110 fokuserer bare på merge sort. 693 00:28:35,110 --> 00:28:38,030 La meg gå videre og zoome inn på dette her. 694 00:28:38,030 --> 00:28:42,530 Først la meg velge en tilfeldig input, foredle dette, og du kan liksom se 695 00:28:42,530 --> 00:28:46,600 hva vi tok for gitt, tidligere, flette sortere faktisk gjør. 696 00:28:46,600 --> 00:28:50,330 >> Så merke at du får disse halvdeler eller disse kvartaler eller disse åttendedeler av 697 00:28:50,330 --> 00:28:53,140 Problemet som plutselig begynner å ta god form. 698 00:28:53,140 --> 00:28:57,070 Og så til slutt, ser du på helt på slutten at bam, 699 00:28:57,070 --> 00:28:58,860 alt er flettet sammen. 700 00:28:58,860 --> 00:29:01,690 >> Så disse er bare tre forskjellige tar på den samme ideen. 701 00:29:01,690 --> 00:29:05,980 Men nøkkelen innsikt, akkurat som divide og hersk i den aller første klasse, 702 00:29:05,980 --> 00:29:10,640 var at vi bestemte oss for å liksom dele problemet til noe stort, inn 703 00:29:10,640 --> 00:29:14,760 noe slags identisk i ånd, men mindre og mindre og mindre 704 00:29:14,760 --> 00:29:15,660 og mindre. 705 00:29:15,660 --> 00:29:18,420 >> Nå er en annen morsom måte å sortere av tro om disse, selv om det ikke er 706 00:29:18,420 --> 00:29:20,520 kommer til å gi deg den samme intuitive forståelse, er 707 00:29:20,520 --> 00:29:21,640 følgende animasjon. 708 00:29:21,640 --> 00:29:25,400 Så dette er en video noen sette sammen den som er forbundet forskjellig 709 00:29:25,400 --> 00:29:29,970 lyder med ulike operasjoner for innsetting sortere, for flettingen sortere og 710 00:29:29,970 --> 00:29:31,150 for et par andre. 711 00:29:31,150 --> 00:29:32,330 Så i et øyeblikk, jeg kommer til å treffe Play. 712 00:29:32,330 --> 00:29:33,600 Det er omtrent et minutt lang. 713 00:29:33,600 --> 00:29:37,410 Og selv om du kan fortsatt se mønstre som skjer, denne gangen kan du 714 00:29:37,410 --> 00:29:41,420 også høre hvordan disse algoritmene er utfører annerledes og med 715 00:29:41,420 --> 00:29:43,950 noe ulike mønstre. 716 00:29:43,950 --> 00:29:45,830 >> Dette er innsetting slag. 717 00:29:45,830 --> 00:29:50,400 >> [TONES SPILLE] 718 00:29:50,400 --> 00:29:52,400 >> DAVID MALAN: Det igjen prøver å sette inn hvert element 719 00:29:52,400 --> 00:29:52,900 inn der det hører hjemme. 720 00:29:52,900 --> 00:29:54,628 Dette er boble slag. 721 00:29:54,628 --> 00:30:10,097 >> [TONES SPILLE] 722 00:30:10,097 --> 00:30:13,630 >> DAVID MALAN: Og du kan liksom følelsen hvor relativt lite arbeid den gjør 723 00:30:13,630 --> 00:30:15,834 ved hvert trinn. 724 00:30:15,834 --> 00:30:20,470 Dette er hva tediousness høres ut som. 725 00:30:20,470 --> 00:30:21,472 >> [TONES SPILLE] 726 00:30:21,472 --> 00:30:25,222 >> DAVID MALAN: Dette er valg sortere, hvor vi velger elementet vi ønsker ved 727 00:30:25,222 --> 00:30:28,845 gå gjennom igjen og igjen og igjen og setter den i begynnelsen. 728 00:30:28,845 --> 00:30:37,674 >> [TONES SPILLE] 729 00:30:37,674 --> 00:30:43,970 >> DAVID MALAN: Dette er fusjonere slag, som du kan virkelig begynne å føle. 730 00:30:43,970 --> 00:30:51,810 >> [TONES SPILLE] 731 00:30:51,810 --> 00:30:54,770 >> [Latter] 732 00:30:54,770 --> 00:30:58,395 >> DAVID MALAN: Noe som heter gnome sortere, som vi ikke har sett på. 733 00:30:58,395 --> 00:31:13,630 >> [TONES SPILLE] 734 00:31:13,630 --> 00:31:17,910 >> DAVID MALAN: Så la meg se, nå, distrahert som du forhåpentligvis er av 735 00:31:17,910 --> 00:31:21,110 musikk, hvis jeg kan skli litt litt matematikk her. 736 00:31:21,110 --> 00:31:24,850 Så det er en fjerde måte at vi kan tenke på hva det betyr disse 737 00:31:24,850 --> 00:31:29,210 funksjoner for å være raskere enn de som vi har sett før. 738 00:31:29,210 --> 00:31:32,470 Og hvis du kommer på kurset fra en matematikk bakgrunn, du 739 00:31:32,470 --> 00:31:36,030 faktisk vet kanskje allerede at du kan klapse et begrep på denne teknikken - 740 00:31:36,030 --> 00:31:40,400 nemlig rekursjon, en funksjon som kaller liksom seg selv. 741 00:31:40,400 --> 00:31:44,780 >> Og igjen, husker at flettingen slags pseudokode var rekursiv i den forstand 742 00:31:44,780 --> 00:31:48,460 at en av fusjonere sortere fotspor var å ringe sort - 743 00:31:48,460 --> 00:31:49,740 som er, i seg selv. 744 00:31:49,740 --> 00:31:52,480 Men heldigvis, fordi vi holdt ringer sorter eller flette sortere, 745 00:31:52,480 --> 00:31:55,880 Nærmere bestemt, på en mindre og mindre og mindre liste, til slutt vi 746 00:31:55,880 --> 00:32:00,005 bunnet ut takket være det vi kaller en base case, den hardkodet sak som 747 00:32:00,005 --> 00:32:04,270 sa dersom listen er liten, mindre enn 2 i så fall, bare returnere umiddelbart. 748 00:32:04,270 --> 00:32:07,550 Hvis vi ikke har den spesielle saken, algoritmen ville aldri bunnen ut, 749 00:32:07,550 --> 00:32:11,010 og du vil faktisk komme inn i en uendelig løkke virkelig evig. 750 00:32:11,010 --> 00:32:14,330 >> Men anta at vi ønsket å nå sette noen tall på dette, igjen, ved hjelp av n 751 00:32:14,330 --> 00:32:15,660 som størrelsen på inngangen. 752 00:32:15,660 --> 00:32:18,680 Og jeg ville spørre deg, hva er den totale tid involvert i 753 00:32:18,680 --> 00:32:19,800 kjører flettingen slag? 754 00:32:19,800 --> 00:32:22,960 Eller mer generelt, hva som er prisen for det i tide? 755 00:32:22,960 --> 00:32:24,730 >> Vel det er ganske lett å måle det. 756 00:32:24,730 --> 00:32:29,010 Hvis n er mindre enn 2, tiden involvert i sortering n elementer, 757 00:32:29,010 --> 00:32:30,480 hvor n er 2, er 0. 758 00:32:30,480 --> 00:32:31,410 Fordi vi bare tilbake. 759 00:32:31,410 --> 00:32:32,510 Det er ingen arbeid som må gjøres. 760 00:32:32,510 --> 00:32:35,660 Nå kanskje, kanskje det er et skritt eller to fremgangsmåten for å finne ut hvor mye 761 00:32:35,660 --> 00:32:38,420 fungere, men det er nært nok til 0 som Jeg skal bare si nei arbeid er 762 00:32:38,420 --> 00:32:40,940 nødvendig hvis listen er så liten å bli uinteressant. 763 00:32:40,940 --> 00:32:42,580 >> Men dette tilfellet er interessant. 764 00:32:42,580 --> 00:32:47,320 Den rekursive tilfellet var den grenen av den pseudokode som sagt annet, sortere 765 00:32:47,320 --> 00:32:52,000 venstre halvdel, sortere riktig halvparten, slå sammen de to halvdelene. 766 00:32:52,000 --> 00:32:55,530 Nå hvorfor dette uttrykket representerer det regning? 767 00:32:55,530 --> 00:32:58,690 Vel, betyr T n bare tid til å sortere n elementer. 768 00:32:58,690 --> 00:33:03,070 Og deretter på høyre side av likhetstegn der, delte T for n 769 00:33:03,070 --> 00:33:06,600 ved 2 refererer til kostnaden av det? 770 00:33:06,600 --> 00:33:07,570 Sortering venstre halvdel. 771 00:33:07,570 --> 00:33:10,990 Den andre T av N dividert med 2 er antagelig henvise til kostnadene til 772 00:33:10,990 --> 00:33:12,390 sortere den høyre halvdel. 773 00:33:12,390 --> 00:33:14,590 >> Og så pluss n? 774 00:33:14,590 --> 00:33:15,420 Er en sammenslåing. 775 00:33:15,420 --> 00:33:19,120 Fordi hvis du har to lister, en av størrelse n over 2 og en annen størrelse av n 776 00:33:19,120 --> 00:33:22,580 over 2, må du i hovedsak berøre hvert av disse elementer, i likhet Rob 777 00:33:22,580 --> 00:33:24,990 rørt hvert av begrene, og bare som vi har pekt på hver av de 778 00:33:24,990 --> 00:33:26,310 frivillige på scenen. 779 00:33:26,310 --> 00:33:28,790 Så n er bekostning av sammenslåing. 780 00:33:28,790 --> 00:33:31,780 >> Nå dessverre, denne formelen er også selv rekursiv. 781 00:33:31,780 --> 00:33:36,390 Så hvis spørsmålet, hvis n er, sier, 16, hvis det er 16 personer på scenen 782 00:33:36,390 --> 00:33:40,670 eller 16 kopper i videoen, hvor mange totalt trinn tar det å sortere dem 783 00:33:40,670 --> 00:33:41,550 med flette slag? 784 00:33:41,550 --> 00:33:45,790 Det er faktisk ikke et opplagt svar, fordi nå må du liksom 785 00:33:45,790 --> 00:33:48,500 rekursivt besvare denne formelen. 786 00:33:48,500 --> 00:33:51,190 >> Men det er OK, fordi la meg foreslå at vi gjør følgende. 787 00:33:51,190 --> 00:33:56,670 Tiden involvert for å sortere 16 personer eller 16 kopper kommer til å være representert 788 00:33:56,670 --> 00:33:58,020 generelt som T 16 av. 789 00:33:58,020 --> 00:34:01,400 Men det er lik, i henhold til våre tidligere formel, to ganger det beløpet 790 00:34:01,400 --> 00:34:04,780 av tiden det tar å sortere 8 kopper pluss 16. 791 00:34:04,780 --> 00:34:08,590 Og igjen, pluss 16 på tide å fusjonere, og to ganger T av 8 er 792 00:34:08,590 --> 00:34:10,790 tid til å sortere venstre halvdel og høyre halvdel. 793 00:34:10,790 --> 00:34:11,989 >> Men igjen, dette er ikke nok. 794 00:34:11,989 --> 00:34:13,210 Vi må dykke i dypere. 795 00:34:13,210 --> 00:34:16,409 Dette betyr at vi må svare på spørsmålet, hva er T av 8? 796 00:34:16,409 --> 00:34:19,610 Vel T av åtte er bare to ganger T av 4 pluss åtte. 797 00:34:19,610 --> 00:34:20,520 Vel, hva er T av fire? 798 00:34:20,520 --> 00:34:23,780 T av fire er bare to ganger T av to pluss fire. 799 00:34:23,780 --> 00:34:25,489 Vel, hva er T for to? 800 00:34:25,489 --> 00:34:29,030 T av to er bare to ganger T av en pluss to. 801 00:34:29,030 --> 00:34:31,940 >> Og igjen, er vi på en måte å få fast i denne syklusen. 802 00:34:31,940 --> 00:34:34,790 Men det handler om å treffe såkalt basen tilfelle. 803 00:34:34,790 --> 00:34:37,310 Fordi det er T for en, vi hevder? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Så nå endelig kan vi jobbe bakover. 806 00:34:39,730 --> 00:34:44,290 >> Hvis T på 1 er 0, kan jeg nå gå tilbake opp ett linje til denne fyren her, og jeg kan 807 00:34:44,290 --> 00:34:46,330 plugg inn 0 for T av en. 808 00:34:46,330 --> 00:34:51,770 Så det betyr at det tilsvarer to ganger null, ellers kjent som 0, pluss 2. 809 00:34:51,770 --> 00:34:53,739 Og så at hele uttrykket er to. 810 00:34:53,739 --> 00:34:58,740 >> Nå hvis jeg tar T av to, hvis svaret er 2, plugge den inn i midten linje, T 811 00:34:58,740 --> 00:35:02,740 av fire, som gir meg to ganger 2 pluss 4, så 8. 812 00:35:02,740 --> 00:35:07,080 Hvis jeg da plugge i åtte til forrige linjen, som gir meg to ganger 8, 16. 813 00:35:07,080 --> 00:35:12,470 Og hvis vi da fortsette som med 24, og legger i 16, vi endelig får en 814 00:35:12,470 --> 00:35:13,820 verdi av 64 år. 815 00:35:13,820 --> 00:35:18,480 >> Nå som i seg selv liksom snakker ingenting til n notasjon, den 816 00:35:18,480 --> 00:35:20,700 big O, omega at vi har vært snakket om. 817 00:35:20,700 --> 00:35:24,890 Men det viser seg at 64 er faktisk 16, størrelsen av tilførselen 818 00:35:24,890 --> 00:35:27,110 logg base 2 av 16 år. 819 00:35:27,110 --> 00:35:30,200 Og hvis dette er litt uvant, bare tenker tilbake, og det vil komme tilbake 820 00:35:30,200 --> 00:35:30,700 til du til slutt. 821 00:35:30,700 --> 00:35:33,775 Hvis dette er log base 2, det er som to hevet til det som gir deg 16? 822 00:35:33,775 --> 00:35:36,380 Å, det er fire, så det er 16 ganger fire. 823 00:35:36,380 --> 00:35:39,380 >> Og igjen, det er ikke en stor avtale hvis dette er liksom en disig minne nå. 824 00:35:39,380 --> 00:35:43,720 Men for nå, ta på tro at 16 log 16 er 64 år. 825 00:35:43,720 --> 00:35:46,590 Og så faktisk med denne enkle tilregnelighet sjekk, har vi bekreftet - 826 00:35:46,590 --> 00:35:48,250 men ikke bevist formelt - 827 00:35:48,250 --> 00:35:52,800 at kjøretiden til flettingen typen er faktisk n log n. 828 00:35:52,800 --> 00:35:53,790 >> Så ikke ille. 829 00:35:53,790 --> 00:35:57,260 Det er definitivt bedre enn den algoritmene vi har sett så langt, og 830 00:35:57,260 --> 00:36:00,710 det er fordi vi har belånt, en, en teknikk som kalles rekursjon. 831 00:36:00,710 --> 00:36:03,880 Men mer interessant enn det, at oppfatningen av å dele seg og erobre. 832 00:36:03,880 --> 00:36:07,460 Igjen, virkelig uke 0 ting som selv nå er tilbakevendende i en 833 00:36:07,460 --> 00:36:08,740 mer overbevisende måte. 834 00:36:08,740 --> 00:36:11,750 >> Nå er en morsom liten øvelse, hvis du har aldri gjort dette - og du sannsynligvis 835 00:36:11,750 --> 00:36:14,660 ville ikke ha, fordi liksom normal folk ikke tenker å gjøre dette. 836 00:36:14,660 --> 00:36:20,650 Men hvis jeg går til google.com og hvis Jeg ønsker å lære noe om 837 00:36:20,650 --> 00:36:22,356 rekursjon, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Latter] 840 00:36:29,058 --> 00:36:32,030 [Mer latter] 841 00:36:32,030 --> 00:36:33,385 DAVID MALAN: Bad joke sakte sprer seg. 842 00:36:33,385 --> 00:36:34,450 [Latter] 843 00:36:34,450 --> 00:36:36,970 DAVID MALAN: Bare i tilfelle, er det der. 844 00:36:36,970 --> 00:36:38,710 Jeg har ikke stave det galt, og det er spøk. 845 00:36:38,710 --> 00:36:40,810 OK. 846 00:36:40,810 --> 00:36:42,950 Forklare det til folk ved siden av deg hvis det har ikke helt klikket helt ennå. 847 00:36:42,950 --> 00:36:47,650 Men rekursjon, mer generelt, refererer til prosessen med en funksjon ringer 848 00:36:47,650 --> 00:36:51,430 seg selv, eller mer generelt, å dele en Problemet til noe som kan være 849 00:36:51,430 --> 00:36:56,220 løst stykkevis ved å løse identiske representative problemer. 850 00:36:56,220 --> 00:36:58,400 >> Vel, la oss endre tannhjul for bare et øyeblikk. 851 00:36:58,400 --> 00:37:00,840 Vi liker å ende på visse cliffhangers, så la oss begynne å sette 852 00:37:00,840 --> 00:37:05,870 scenen, i flere minutter, på en veldig enkel idé - 853 00:37:05,870 --> 00:37:07,620 som å bytte to elementer, ikke sant? 854 00:37:07,620 --> 00:37:10,040 Alle disse algoritmene vi har vært snakker om de siste par 855 00:37:10,040 --> 00:37:12,420 forelesninger innebære noen slags bytte. 856 00:37:12,420 --> 00:37:14,630 I dag ble det visualisert ved dem får opp av stolene sine og 857 00:37:14,630 --> 00:37:18,570 vandre rundt, men i koden, ville vi bare ta et element fra ett array 858 00:37:18,570 --> 00:37:20,370 og slenger den inn i en annen. 859 00:37:20,370 --> 00:37:21,880 >> Så hvordan kan vi gå om du gjør dette? 860 00:37:21,880 --> 00:37:24,850 Vel, la meg gå videre og skrive en rask program her. 861 00:37:24,850 --> 00:37:31,600 Jeg kommer til å gå videre og gjøre dette følger nedenfor. 862 00:37:31,600 --> 00:37:33,910 La oss kalle dette - 863 00:37:33,910 --> 00:37:38,070 hva gjør vi ønsker å kalle dette en? 864 00:37:38,070 --> 00:37:38,650 >> Nei, faktisk ikke. 865 00:37:38,650 --> 00:37:39,420 La meg spole tilbake. 866 00:37:39,420 --> 00:37:41,220 Jeg ønsker ikke å gjøre det cliffhanger ennå. 867 00:37:41,220 --> 00:37:42,270 Det vil ødelegge moroa. 868 00:37:42,270 --> 00:37:43,600 La oss gjøre dette i stedet. 869 00:37:43,600 --> 00:37:47,430 >> Anta at jeg ønsker å skrive litt program og som omfavner nå dette 870 00:37:47,430 --> 00:37:48,700 Ideen om rekursjon. 871 00:37:48,700 --> 00:37:50,370 Jeg typen har foran meg selv der. 872 00:37:50,370 --> 00:37:51,420 Jeg kommer til å gjøre følgende. 873 00:37:51,420 --> 00:38:00,220 >> Først en rask inkluderer av standard io.h, samt et inkluder av cs50.h. 874 00:38:00,220 --> 00:38:03,200 Og så jeg kommer til å gå videre og erklære int main ugyldig 875 00:38:03,200 --> 00:38:04,360 på vanlig måte. 876 00:38:04,360 --> 00:38:07,920 Jeg innså at jeg har misnamed filen, så la meg bare legge til en. c utvidelse her så 877 00:38:07,920 --> 00:38:09,510 at vi kan kompilere den riktig. 878 00:38:09,510 --> 00:38:10,970 Start denne funksjonen. 879 00:38:10,970 --> 00:38:13,290 >> Og funksjonen jeg ønsker å skrive, ganske enkelt, er en som ber 880 00:38:13,290 --> 00:38:16,210 bruker for et nummer og deretter legger opp alle tallene mellom at 881 00:38:16,210 --> 00:38:19,920 nummer og, si, 0. 882 00:38:19,920 --> 00:38:22,510 Så første jeg kommer til å gå videre og erklære int n. 883 00:38:22,510 --> 00:38:24,760 Da jeg kopiere noen kode som vi har brukt på en stund. 884 00:38:24,760 --> 00:38:26,660 Mens noe er sant. 885 00:38:26,660 --> 00:38:28,000 Jeg skal komme tilbake til det i et øyeblikk. 886 00:38:28,000 --> 00:38:29,010 >> Hva ønsker jeg å gjøre? 887 00:38:29,010 --> 00:38:33,460 Jeg ønsker å si printf positive heltall behage. 888 00:38:33,460 --> 00:38:36,130 Og så skal jeg si n får bli int. 889 00:38:36,130 --> 00:38:38,800 Så igjen, noen standardtekst kode at vi har brukt før. 890 00:38:38,800 --> 00:38:40,810 Og jeg kommer til å gjøre dette mens n er mindre enn 1. 891 00:38:40,810 --> 00:38:44,120 Så dette vil sikre at brukeren gir meg et positivt heltall. 892 00:38:44,120 --> 00:38:45,490 >> Og nå skal jeg gjøre følgende. 893 00:38:45,490 --> 00:38:51,020 Jeg ønsker å legge opp alle tallene mellom 1 og og N eller 0 og n, 894 00:38:51,020 --> 00:38:52,570 ekvivalent, for å få den totale summen. 895 00:38:52,570 --> 00:38:55,100 Så det store sigma symbol som du kanskje husker. 896 00:38:55,100 --> 00:38:59,050 Så jeg kommer til å gjøre dette ved første kall en funksjon som heter sigma, 897 00:38:59,050 --> 00:39:06,030 passerer det i n, og da jeg kommer til å si printf, er svaret der. 898 00:39:06,030 --> 00:39:08,180 >> Så kort sagt, får jeg og int fra brukeren. 899 00:39:08,180 --> 00:39:09,280 Jeg sikre at det er positivt. 900 00:39:09,280 --> 00:39:12,700 Jeg erklærer en variabel kalt svar på type int og butikk i den avkastningen 901 00:39:12,700 --> 00:39:15,610 Verdien av sigma, passerer n som input. 902 00:39:15,610 --> 00:39:17,060 Og da jeg skrive ut det svaret. 903 00:39:17,060 --> 00:39:19,550 >> Dessverre, selv om sigma lyder som noe som kan være i 904 00:39:19,550 --> 00:39:24,040 den math.h fil, sin erklæring, det er faktisk ikke. 905 00:39:24,040 --> 00:39:24,690 Så det er OK. 906 00:39:24,690 --> 00:39:26,170 Jeg kan implementere dette selv. 907 00:39:26,170 --> 00:39:29,160 Jeg kommer til å implementere en funksjon som heter sigma, og det kommer til å ta en 908 00:39:29,160 --> 00:39:29,900 parameter - 909 00:39:29,900 --> 00:39:32,100 la oss bare kalle det m, bare så er det annerledes. 910 00:39:32,100 --> 00:39:35,910 Og deretter opp her, kommer jeg til å si, vel, hvis m er mindre enn 1 - Dette er et 911 00:39:35,910 --> 00:39:38,180 svært uinteressant program. 912 00:39:38,180 --> 00:39:41,700 Så jeg kommer til å gå videre og umiddelbart returnere 0. 913 00:39:41,700 --> 00:39:45,920 Det gir bare ikke mening å legge opp alle tallene mellom 1 og m hvis m 914 00:39:45,920 --> 00:39:48,470 i seg selv er 0 eller negativ. 915 00:39:48,470 --> 00:39:50,900 >> Og så jeg kommer til å gå videre og gjøre dette veldig iterativt. 916 00:39:50,900 --> 00:39:53,090 Jeg kommer til å gjøre denne typen old-school, og jeg kommer til å gå videre 917 00:39:53,090 --> 00:39:57,150 og si at jeg kommer til å erklære en sum for å være 0.. 918 00:39:57,150 --> 00:39:59,630 Så jeg kommer til å ha en for løkke av int - 919 00:39:59,630 --> 00:40:02,820 og la meg gjøre det for å matche vår distribusjon kode, slik at du har en kopi 920 00:40:02,820 --> 00:40:07,500 hjemme. int i får en på opptil i er mindre enn eller lik m. 921 00:40:07,500 --> 00:40:09,430 Jeg pluss pluss. 922 00:40:09,430 --> 00:40:11,430 Og så innsiden av dette for loop - 923 00:40:11,430 --> 00:40:12,440 vi er nesten der - 924 00:40:12,440 --> 00:40:15,810 Summen blir sum pluss en. 925 00:40:15,810 --> 00:40:17,670 Og så jeg kommer til å returnere summen. 926 00:40:17,670 --> 00:40:19,420 >> Så jeg gjorde dette raskt, ganske riktignok. 927 00:40:19,420 --> 00:40:22,775 Men igjen, er den viktigste funksjonen pen grei, basert på koden vi har 928 00:40:22,775 --> 00:40:23,190 skrevet så langt. 929 00:40:23,190 --> 00:40:25,610 Bruker den doble loopen å få en positiv int fra brukeren. 930 00:40:25,610 --> 00:40:29,870 Jeg så pass at int til en ny funksjon kalt sigma, kaller det, igjen, n.. 931 00:40:29,870 --> 00:40:33,100 Og jeg lagre returverdien, svaret fra den svarte boksen i dag 932 00:40:33,100 --> 00:40:35,460 kjent som sigma, i en variabel kalt svaret. 933 00:40:35,460 --> 00:40:36,580 Så jeg skriver det ut. 934 00:40:36,580 --> 00:40:39,090 >> Hvis vi nå fortsette historien, hvordan er sigma implementert? 935 00:40:39,090 --> 00:40:40,840 Jeg foreslår å implementere som følger. 936 00:40:40,840 --> 00:40:43,560 Først, en liten bit av feil-sjekking å sørge for at brukeren ikke er 937 00:40:43,560 --> 00:40:46,480 rote med meg og passerer noen negativ eller 0 verdi. 938 00:40:46,480 --> 00:40:49,710 Så jeg erklære en variabel kalt oppsummere og sette den til 0. 939 00:40:49,710 --> 00:40:55,910 >> Og nå begynner jeg å flytte fra jeg lik 1 hele veien opp til og med m, 940 00:40:55,910 --> 00:41:00,130 fordi jeg ønsker å inkludere alle tall fra en gjennom m, inkluderende. 941 00:41:00,130 --> 00:41:04,350 Og inne i dette for loop, jeg bare gjøre Summen blir uansett det er nå, pluss 942 00:41:04,350 --> 00:41:08,900 Verdien av jeg. 943 00:41:08,900 --> 00:41:10,370 Pluss verdien av i. 944 00:41:10,370 --> 00:41:14,090 >> Som en side, hvis du ikke har sett denne før, er det noen syntaktisk sukker 945 00:41:14,090 --> 00:41:14,870 for denne linjen. 946 00:41:14,870 --> 00:41:21,120 Jeg kan skrive dette som pluss er lik i, bare for å redde meg selv noen få tastetrykk 947 00:41:21,120 --> 00:41:22,570 og å se litt kjøligere. 948 00:41:22,570 --> 00:41:23,140 Men det er alt. 949 00:41:23,140 --> 00:41:24,660 Det er funksjonelt det samme. 950 00:41:24,660 --> 00:41:26,710 >> Dessverre, denne koden er ikke kommer til å kompilere ennå. 951 00:41:26,710 --> 00:41:31,600 Hvis jeg kjører gjør 0 sigma, hvordan er Jeg kommer til å bli skreket til? 952 00:41:31,600 --> 00:41:33,473 Hva kommer det til å ikke like? 953 00:41:33,473 --> 00:41:35,740 >> PUBLIKUM: [uhørlig]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID MALAN: Ja, det gjorde jeg ikke erklære funksjonen opp topp, ikke sant? 955 00:41:37,800 --> 00:41:40,590 C er litt dumt, ved at den kun gjør det du ber den om, og du 956 00:41:40,590 --> 00:41:41,880 nødt til å gjøre det i den rekkefølgen. 957 00:41:41,880 --> 00:41:45,910 Og så hvis jeg treffer Skriv inn her, kommer jeg til å får en advarsel om sigma implisitt 958 00:41:45,910 --> 00:41:46,860 erklæring. 959 00:41:46,860 --> 00:41:48,120 >> Oh, ikke et problem. 960 00:41:48,120 --> 00:41:50,370 Jeg kan gå opp til toppen, og jeg kan si, ok, vent litt. 961 00:41:50,370 --> 00:41:54,240 Sigma er en funksjon som returnerer en int og det forventer en 962 00:41:54,240 --> 00:41:56,620 int som input, semikolon. 963 00:41:56,620 --> 00:41:59,550 Eller jeg kunne sette hele funksjonen ovenfor viktigste, men generelt, ville jeg 964 00:41:59,550 --> 00:42:02,260 anbefaler mot dette, fordi det er hyggelig å alltid ha viktigste på toppen så 965 00:42:02,260 --> 00:42:06,310 du kan hoppe rett inn og vet hva en Programmet gjør ved å lese viktigste først. 966 00:42:06,310 --> 00:42:07,930 >> Så nå la meg tømme skjermen. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Alt ser ut til å sjekke ut. 969 00:42:10,340 --> 00:42:11,970 La meg kjøre sigma 0. 970 00:42:11,970 --> 00:42:12,770 Positiv inter. 971 00:42:12,770 --> 00:42:15,580 Jeg skal gi det antall 3 å holde det enkelt. 972 00:42:15,580 --> 00:42:18,710 Så det burde gi meg 3 pluss 2 pluss 1, slik 6.. 973 00:42:18,710 --> 00:42:20,750 Enter, og faktisk jeg får seks. 974 00:42:20,750 --> 00:42:21,820 >> Jeg kan gjøre noe større - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Akkurat som en tangent, jeg kommer til å gjøre noe latterlig som en virkelig stor 977 00:42:27,690 --> 00:42:30,375 nummer, Å, det fungerte faktisk - 978 00:42:30,375 --> 00:42:31,600 eh, jeg tror ikke det er rett. 979 00:42:31,600 --> 00:42:32,810 La oss se. 980 00:42:32,810 --> 00:42:34,060 La oss virkelig rotet med det. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Det er et problem. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Hva skjer? 985 00:42:44,970 --> 00:42:46,050 Koden er ikke så ille. 986 00:42:46,050 --> 00:42:48,470 Det er fortsatt lineær. 987 00:42:48,470 --> 00:42:50,810 Plystring er en god effekt, skjønt. 988 00:42:50,810 --> 00:42:52,060 Hva skjer? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Ikke sikker på om jeg hørte det. 991 00:42:55,620 --> 00:42:57,620 Så det viser seg - og Dette er som en side. 992 00:42:57,620 --> 00:42:59,400 Dette er ikke kjernen til Ideen om rekursjon. 993 00:42:59,400 --> 00:43:02,480 Det viser seg, fordi jeg prøver å representerer et så stort antall, mest 994 00:43:02,480 --> 00:43:06,980 sannsynlig det blir feiltolket av C som ikke positivt tall, 995 00:43:06,980 --> 00:43:09,980 men negativt tall. 996 00:43:09,980 --> 00:43:12,690 >> Vi har ikke snakket om dette, men det viser seg at det er negative tall 997 00:43:12,690 --> 00:43:14,210 i verden i tillegg til positive tall. 998 00:43:14,210 --> 00:43:16,290 Og de midler som du kan representerer et negativt tall 999 00:43:16,290 --> 00:43:19,530 egentlig er, bruker du en spesiell bit for å indikere 1000 00:43:19,530 --> 00:43:20,400 positivt enn negativt. 1001 00:43:20,400 --> 00:43:22,950 Det er litt mer komplisert enn det, men det er den grunnleggende ideen. 1002 00:43:22,950 --> 00:43:26,740 >> Så dessverre, hvis C er forvirrende ett av de bitene som faktisk betyr, 1003 00:43:26,740 --> 00:43:30,790 oh, dette er et negativt tall, min sløyfe her, for eksempel, er faktisk aldri 1004 00:43:30,790 --> 00:43:31,740 kommer til å avslutte. 1005 00:43:31,740 --> 00:43:33,850 Så hvis jeg var faktisk å skrive noe igjen og igjen, ville vi 1006 00:43:33,850 --> 00:43:34,650 se en hel masse. 1007 00:43:34,650 --> 00:43:36,220 Men igjen, er dette i tillegg til punktet. 1008 00:43:36,220 --> 00:43:38,590 Dette er egentlig bare en slags intellektuell nysgjerrighet som vi vil komme 1009 00:43:38,590 --> 00:43:39,550 tilbake til slutt. 1010 00:43:39,550 --> 00:43:43,400 Men for nå, er dette en riktig implementering hvis vi antar at 1011 00:43:43,400 --> 00:43:45,970 Brukeren vil gi ints som passer innenfor ints. 1012 00:43:45,970 --> 00:43:49,370 >> Men jeg hevder at denne koden, ærlig, kunne gjøres så mye enklere måte. 1013 00:43:49,370 --> 00:43:54,060 Hvis målet på hånden, er å ta en rekke som m og legg opp alle 1014 00:43:54,060 --> 00:43:59,510 tall mellom den og en, eller motsatt mellom 1 og det, hevder jeg 1015 00:43:59,510 --> 00:44:03,380 at jeg kan låne denne ideen om at fusjonere slag hadde, som ble tatt et problem 1016 00:44:03,380 --> 00:44:05,660 av denne størrelse og den delende til noe mindre. 1017 00:44:05,660 --> 00:44:09,875 Kanskje ikke halvparten, men mindre, men representativ det samme. 1018 00:44:09,875 --> 00:44:12,130 Samme idé, men et mindre problem. 1019 00:44:12,130 --> 00:44:15,470 >> Så jeg er faktisk - la meg lagre denne filen med en annen versjon nummer. 1020 00:44:15,470 --> 00:44:17,670 Vi kaller denne versjonen En i stedet for 0. 1021 00:44:17,670 --> 00:44:20,790 Og jeg påstår at jeg faktisk kan reimplement dette i denne typen 1022 00:44:20,790 --> 00:44:22,160 mind-bending måte. 1023 00:44:22,160 --> 00:44:23,710 >> Jeg kommer til å forlate en del av det alene. 1024 00:44:23,710 --> 00:44:27,710 Jeg kommer til å si hvis m er mindre enn eller lik 0 - 1025 00:44:27,710 --> 00:44:29,280 Jeg skal bare være litt mer anal denne gangen 1026 00:44:29,280 --> 00:44:30,520 med min feilsjekking - 1027 00:44:30,520 --> 00:44:33,190 Jeg kommer til å gå videre og returnere 0. 1028 00:44:33,190 --> 00:44:34,490 Dette er vilkårlig. 1029 00:44:34,490 --> 00:44:37,500 Jeg er bare rett og slett avgjøre om brukeren gir meg et negativt tall, er jeg 1030 00:44:37,500 --> 00:44:41,490 returnere 0, og de burde ha lest dokumentasjonen nærmere. 1031 00:44:41,490 --> 00:44:42,170 >> Else - 1032 00:44:42,170 --> 00:44:44,070 legge merke til hva jeg skal gjøre. 1033 00:44:44,070 --> 00:44:49,260 Annet jeg kommer til å returnere m plus - 1034 00:44:49,260 --> 00:44:51,010 hva er sigma av m? 1035 00:44:51,010 --> 00:44:56,710 Vel, sigma av m plus m minus 1, pluss m 2 minus, pluss m minus tre. 1036 00:44:56,710 --> 00:44:58,030 Jeg ønsker ikke å skrive alt dette ut. 1037 00:44:58,030 --> 00:44:59,120 Hvorfor gjør jeg ikke bare punt? 1038 00:44:59,120 --> 00:45:05,080 Rekursivt kalle meg selv med en litt mindre problem, semikolon 1039 00:45:05,080 --> 00:45:06,840 og kalle det en dag? 1040 00:45:06,840 --> 00:45:07,040 >> Høyre? 1041 00:45:07,040 --> 00:45:10,980 Nå også her kan du føle eller bekymre at dette er en uendelig loop som jeg er 1042 00:45:10,980 --> 00:45:15,450 inducing, der jeg implementere sigma ved å ringe sigma. 1043 00:45:15,450 --> 00:45:20,342 Men det er helt OK, fordi jeg trodde fremover en ekstra hvilke linjer? 1044 00:45:20,342 --> 00:45:22,600 >> PUBLIKUM: [uhørlig]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID MALAN: 23 til 26, som er mitt hvis tilstanden. 1046 00:45:25,430 --> 00:45:28,390 Fordi det er fint om subtraksjon her, fordi jeg holder 1047 00:45:28,390 --> 00:45:31,180 overlate sigma mindre problemer, mindre problemer, mindre - det er ikke 1048 00:45:31,180 --> 00:45:31,870 halve størrelsen. 1049 00:45:31,870 --> 00:45:34,380 Det er bare en baby skritt mindre, men det er OK. 1050 00:45:34,380 --> 00:45:38,050 Fordi til slutt, vil vi jobbe vei ned til 1 eller 0. 1051 00:45:38,050 --> 00:45:41,630 Og når vi treffer 0, er sigma ikke kommer til å kalle seg selv lenger. 1052 00:45:41,630 --> 00:45:43,590 Det kommer til å umiddelbart returnere 0. 1053 00:45:43,590 --> 00:45:47,960 >> Så effekten, hvis du liksom vinden denne opp i tankene dine, er å legge m pluss 1054 00:45:47,960 --> 00:45:52,740 m en minus, pluss m minus 2, pluss m minus 3, pluss prikk, prikk, prikk, m minus 1055 00:45:52,740 --> 00:45:57,820 m, til slutt gir deg 0, og Effekten er i siste instans å legge til alle 1056 00:45:57,820 --> 00:45:59,070 disse tingene sammen. 1057 00:45:59,070 --> 00:46:02,380 Så vi har ikke, med rekursjon, løste problemet at vi 1058 00:46:02,380 --> 00:46:03,470 kunne ikke løse før. 1059 00:46:03,470 --> 00:46:06,840 Faktisk versjon 0 av dette, og hvert Problemet i år har vært løsbar 1060 00:46:06,840 --> 00:46:09,980 med bare å bruke for sløyfer eller mens løkker eller lignende konstruksjoner. 1061 00:46:09,980 --> 00:46:13,150 >> Men rekursjon, jeg påstår at gir oss en annen måte å tenke på 1062 00:46:13,150 --> 00:46:17,010 problemer, der hvis vi kan ta en problem, dele det fra noe 1063 00:46:17,010 --> 00:46:22,340 noe stort til noe litt mindre, hevder jeg at vi kan løse det 1064 00:46:22,340 --> 00:46:26,040 kanskje litt mer elegant i form av design, med mindre kode, 1065 00:46:26,040 --> 00:46:30,980 og kanskje løse problemer som ville være vanskeligere, som vi vil til slutt 1066 00:46:30,980 --> 00:46:33,280 se, løse rent iterativt. 1067 00:46:33,280 --> 00:46:35,980 >> Men cliffhanger som jeg gjorde ønsker å forlate oss på var dette. 1068 00:46:35,980 --> 00:46:40,720 La meg gå videre og åpne opp en fil fra - 1069 00:46:40,720 --> 00:46:44,300 faktisk, la meg gå og gjøre dette virkelig rask. 1070 00:46:44,300 --> 00:46:46,875 La meg gå videre og foreslå følgende. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Blant dagens kode er denne filen her. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Denne her, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Så dette er et dumt lite program som Jeg pisket opp som hevder å gjøre 1076 00:47:06,260 --> 00:47:06,940 følgende. 1077 00:47:06,940 --> 00:47:10,140 I hovedsak erklærer det første en int kalt x og tildeler den 1078 00:47:10,140 --> 00:47:11,100 verdien 1. 1079 00:47:11,100 --> 00:47:13,520 Da er det erklærer en int y og tildeler den verdien 2. 1080 00:47:13,520 --> 00:47:15,310 Skriver den ut ut hva x og y er. 1081 00:47:15,310 --> 00:47:17,781 Da sier, bytte, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Så det hevder å være å kalle en funksjon kalles swap, passerer x og 1083 00:47:21,670 --> 00:47:24,290 y, ideen om hvilken er som forhåpentligvis x og y vil komme tilbake 1084 00:47:24,290 --> 00:47:25,620 annen, motsatt. 1085 00:47:25,620 --> 00:47:27,110 Så det hevder byttet! 1086 00:47:27,110 --> 00:47:28,420 med et utropstegn. 1087 00:47:28,420 --> 00:47:30,190 Skriver den ut ut x og y. 1088 00:47:30,190 --> 00:47:33,480 >> Men det viser seg at dette svært enkel demonstrasjon ned 1089 00:47:33,480 --> 00:47:35,570 her er faktisk buggy. 1090 00:47:35,570 --> 00:47:38,870 Selv om jeg erklære en midlertidig variable og midlertidig sette en i 1091 00:47:38,870 --> 00:47:42,010 det, så jeg reassigning et verdien av b - 1092 00:47:42,010 --> 00:47:45,080 som føles rimelig, fordi jeg har lagret en kopi av en i temp. 1093 00:47:45,080 --> 00:47:48,410 Da jeg oppdatere b til lik hva som var i temp. 1094 00:47:48,410 --> 00:47:51,610 Denne typen skall spillet med å flytte en i b og b inn i en ved hjelp av denne 1095 00:47:51,610 --> 00:47:54,360 middelaldrende mann som heter temp føler helt rimelig. 1096 00:47:54,360 --> 00:47:57,270 >> Men jeg hevder at når jeg kjører denne kode, som jeg skal gjøre nå - 1097 00:47:57,270 --> 00:47:59,490 la meg gå videre og lim den inn her. 1098 00:47:59,490 --> 00:48:01,995 Jeg vil kalle dette noswap.c. 1099 00:48:01,995 --> 00:48:05,630 Og som navnet antyder, er dette ikke kommer til å være et riktig program. 1100 00:48:05,630 --> 00:48:09,460 Gjør noswap. / Nei swap. 1101 00:48:09,460 --> 00:48:12,110 x er 1, y er 2, bytte, byttes om. 1102 00:48:12,110 --> 00:48:14,220 x er 1, y er 2. 1103 00:48:14,220 --> 00:48:16,920 Dette er fundamentalt galt, selv om dette virker perfekt 1104 00:48:16,920 --> 00:48:17,730 fornuftig for meg. 1105 00:48:17,730 --> 00:48:21,330 Og det er en grunn, men vi er ikke kommer til å avsløre årsaken ennå. 1106 00:48:21,330 --> 00:48:24,610 >> For nå den nest cliffhanger jeg ønsket å forlate deg med dette, en 1107 00:48:24,610 --> 00:48:27,120 utlysing av former på kupongkoder. 1108 00:48:27,120 --> 00:48:31,590 Vår innovasjon med sene dager i år har provosert en ikke-triviell antall 1109 00:48:31,590 --> 00:48:33,830 spørsmål, som var ikke vår intensjon. 1110 00:48:33,830 --> 00:48:36,590 Intensjonen med disse kupongkoder, der hvis du gjør en del av problemet 1111 00:48:36,590 --> 00:48:39,850 satt tidlig, og dermed får en ekstra dag, var egentlig for å hjelpe dere hjelpe 1112 00:48:39,850 --> 00:48:42,420 selv starte tidlig, liksom om av incentivizing deg. 1113 00:48:42,420 --> 00:48:44,880 Hjelper oss fordele belastningen over kontortid bedre slik at 1114 00:48:44,880 --> 00:48:45,740 det er liksom vinn-vinn. 1115 00:48:45,740 --> 00:48:48,860 >> Dessverre tror jeg mine instrukser har ikke vært til dags dato, veldig klar, så 1116 00:48:48,860 --> 00:48:52,230 Jeg gikk tilbake denne helgen og oppdatert spec i større, dristigere tekst til 1117 00:48:52,230 --> 00:48:53,600 forklare kuler som disse. 1118 00:48:53,600 --> 00:48:56,900 Og bare for å si det mer offentlig, etter standard, oppgavesett skyldes torsdag 1119 00:48:56,900 --> 00:48:58,400 midt på dagen, per pensum. 1120 00:48:58,400 --> 00:49:02,030 Hvis du starter tidlig, etterbehandling del av problemet satt av onsdag klokken 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, den delen som vedrører en kupong koden, er ideen om at du kan utvide 1122 00:49:05,170 --> 00:49:07,710 din fristen for P satt til fredag. 1123 00:49:07,710 --> 00:49:10,890 Det vil si, bet av en liten del av det P satt i forhold til hva som vanligvis er 1124 00:49:10,890 --> 00:49:13,200 større problem, og du kan kjøpe selv en ekstra dag. 1125 00:49:13,200 --> 00:49:15,190 Igjen, det blir du planlegger å oppgavesettet, får deg til 1126 00:49:15,190 --> 00:49:16,380 kontortid før. 1127 00:49:16,380 --> 00:49:20,670 Men kupongen koden problemet er fortsatt nødvendig, selv om du ikke sender det. 1128 00:49:20,670 --> 00:49:23,340 >> Men mer overbevisende er denne. 1129 00:49:23,340 --> 00:49:26,520 (STAGE STILLE) Og de folkene forlater tidlig er skal angre. 1130 00:49:26,520 --> 00:49:28,620 Som er folk på balkongen. 1131 00:49:28,620 --> 00:49:32,510 Jeg beklager på forhånd til folk på balkongen for grunner som vil være 1132 00:49:32,510 --> 00:49:33,920 klart i løpet av et øyeblikk. 1133 00:49:33,920 --> 00:49:37,050 >> Så vi er heldige som har en av CS50 er tidligere leder undervisning stipendiater ved 1134 00:49:37,050 --> 00:49:39,302 et firma som heter dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 De har svært sjenerøst donert en kupong koden her for så mye plass, 1136 00:49:45,500 --> 00:49:48,180 som er opp fra vanlig 2 gigabyte. 1137 00:49:48,180 --> 00:49:51,740 Så det jeg tenkte vi skulle gjøre på denne endelig notat er å gjøre litt av en giveaway, 1138 00:49:51,740 --> 00:49:55,380 der i bare et øyeblikk, vil vi avsløre vinneren og som har en kupong 1139 00:49:55,380 --> 00:49:57,980 kode som du kan deretter gå til deres nettside, skriv det inn, og voila, få en 1140 00:49:57,980 --> 00:50:01,370 hel masse mer Dropbox plass for din apparatet og for dine personlige filer. 1141 00:50:01,370 --> 00:50:05,690 >> Og først, som ønsker å delta i denne tegningen? 1142 00:50:05,690 --> 00:50:09,630 OK, nå som gjør det enda mer moro. 1143 00:50:09,630 --> 00:50:14,010 Den som mottar denne 25-gigabyte kupong kode - som er langt 1144 00:50:14,010 --> 00:50:16,150 mer overbevisende enn sent dager nå, kanskje - 1145 00:50:16,150 --> 00:50:20,620 er den som sitter på toppen av en seteputen under hvilken det finnes 1146 00:50:20,620 --> 00:50:21,620 at kupongkode. 1147 00:50:21,620 --> 00:50:23,480 Du kan nå se under din seteputen. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [VIDEOAVSPILLING] 1150 00:50:29,680 --> 00:50:31,620 >> -En, to, tre. 1151 00:50:31,620 --> 00:50:35,015 >> [SKRIKING] 1152 00:50:35,015 --> 00:50:35,985 >> -Du får en bil! 1153 00:50:35,985 --> 00:50:36,670 Du får en bil! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID MALAN: Vi vil se deg på onsdag. 1155 00:50:37,970 --> 00:50:38,904 >> -Du får en bil! 1156 00:50:38,904 --> 00:50:39,371 Du får en bil! 1157 00:50:39,371 --> 00:50:40,305 Du får en bil! 1158 00:50:40,305 --> 00:50:41,706 Du får en bil! 1159 00:50:41,706 --> 00:50:43,107 Du får en bil! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID MALAN: Balkong folkens, kommer ned her til fronten, 1161 00:50:45,530 --> 00:50:46,866 hvor vi har statister. 1162 00:50:46,866 --> 00:50:50,282 >> -Alle får en bil! 1163 00:50:50,282 --> 00:50:52,234 Alle får en bil! 1164 00:50:52,234 --> 00:50:52,722 >> [END VIDEOAVSPILLING] 1165 00:50:52,722 --> 00:50:54,590 >> FORTELLER: Ved neste CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> SPEAKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh - 1167 00:51:00,374 --> 00:51:02,106 >> [Ukelele SKUESPILL]