1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [MUSIC Playing] 3 00:00:10,800 --> 00:00:13,500 DAVID MALAN: Okay. 4 00:00:13,500 --> 00:00:14,670 Okay, velkommen tilbage. 5 00:00:14,670 --> 00:00:18,120 Så dette er uge 4, begyndelsen , og allerede. 6 00:00:18,120 --> 00:00:21,320 Og du vil huske, at i sidste uge, vi sætter kode afsat til bare en lille smule 7 00:00:21,320 --> 00:00:24,240 og vi begyndte at tale lidt mere højt niveau, omkring ting som 8 00:00:24,240 --> 00:00:28,130 søgning og sortering, som selv noget enkle idéer, er 9 00:00:28,130 --> 00:00:31,840 repræsenterer en klasse af problemer vil du begynde at løse særligt 10 00:00:31,840 --> 00:00:34,820 som du begynder at tænke på den endelige projekter og interessante løsninger, du 11 00:00:34,820 --> 00:00:36,760 måske nødt til virkelige verdens problemer. 12 00:00:36,760 --> 00:00:39,490 Nu boble slags var en af ​​de enkleste sådanne algoritmer, og det 13 00:00:39,490 --> 00:00:42,900 arbejdet ved at have disse små tal på en liste eller i et array slags 14 00:00:42,900 --> 00:00:46,530 boble deres vej op til toppen, og store tal flytter deres vej ned til 15 00:00:46,530 --> 00:00:47,930 i slutningen af ​​denne liste. 16 00:00:47,930 --> 00:00:50,650 >> Og huske, at vi kunne visualisere boble sortere lidt 17 00:00:50,650 --> 00:00:52,310 noget som dette. 18 00:00:52,310 --> 00:00:53,640 Så lad mig gå videre og klik på Start. 19 00:00:53,640 --> 00:00:55,350 Jeg har forvalgt boble slags. 20 00:00:55,350 --> 00:00:58,920 Og hvis du husker at højere blå linjer repræsenterer store tal, små 21 00:00:58,920 --> 00:01:03,300 blå linjer repræsenterer små tal, som vi går gennem dette igen og igen, og 22 00:01:03,300 --> 00:01:07,680 igen, sammenligne to søjler ved siden af ​​hinanden anden i rødt, vi kommer til at skifte 23 00:01:07,680 --> 00:01:11,010 største og den mindste hvis de er ude af drift. 24 00:01:11,010 --> 00:01:14,150 >> Så dette vil gå på og gå på og gå videre, og du vil se, at de større 25 00:01:14,150 --> 00:01:16,700 elementer gør deres vej til højre, og de mindre elementer er 26 00:01:16,700 --> 00:01:17,900 gøre deres vej til venstre. 27 00:01:17,900 --> 00:01:21,380 Men vi begyndte at kvantificere effektivitet, at 28 00:01:21,380 --> 00:01:22,970 kvaliteten af ​​denne algoritme. 29 00:01:22,970 --> 00:01:25,200 Og vi sagde, at i værste tilfælde, denne algoritme tog 30 00:01:25,200 --> 00:01:27,940 nogenlunde hvor mange skridt? 31 00:01:27,940 --> 00:01:28,980 >> Så n potens. 32 00:01:28,980 --> 00:01:30,402 Og hvad var n? 33 00:01:30,402 --> 00:01:31,650 >> PUBLIKUM: Antal elementer. 34 00:01:31,650 --> 00:01:32,790 >> DAVID MALAN: So n var række elementer. 35 00:01:32,790 --> 00:01:33,730 Og så vil vi gøre det ofte. 36 00:01:33,730 --> 00:01:36,650 Helst vi ønsker at tale om størrelsen af et problem eller størrelsen af ​​en 37 00:01:36,650 --> 00:01:39,140 input, eller den tid, det tager at producere output, vi bare 38 00:01:39,140 --> 00:01:41,610 generaliseret uanset input er så n. 39 00:01:41,610 --> 00:01:45,970 Så tilbage i uge 0, antallet sider i telefonbogen var n. 40 00:01:45,970 --> 00:01:47,550 Antallet af elever i værelset var n. 41 00:01:47,550 --> 00:01:49,630 Så også her, vi følger dette mønster. 42 00:01:49,630 --> 00:01:52,800 >> Nu n kvadreret er ikke særlig hurtigt, så vi forsøgte at gøre det bedre. 43 00:01:52,800 --> 00:01:55,970 Og så vi kiggede på et par andre algoritmer, blandt hvilke 44 00:01:55,970 --> 00:01:57,690 var valg slags. 45 00:01:57,690 --> 00:01:59,180 Så udvælgelse sortere var lidt anderledes. 46 00:01:59,180 --> 00:02:03,130 Det var næsten enklere, jeg tør sige, hvorefter jeg begyndte i begyndelsen af 47 00:02:03,130 --> 00:02:06,740 Listen over vores frivillige, og jeg bare igen og igen og igen gik igennem 48 00:02:06,740 --> 00:02:10,060 listen, plukning ud den mindste element på et tidspunkt og sætte ham eller 49 00:02:10,060 --> 00:02:13,040 hende i starten af ​​listen. 50 00:02:13,040 --> 00:02:16,410 >> Men også dette når vi begyndte at tænke gennem matematik og større 51 00:02:16,410 --> 00:02:19,860 billede, tænkt over, hvor mange gange Jeg gik frem og tilbage og tilbage igen 52 00:02:19,860 --> 00:02:24,090 og tilbage, vi sagde i værste fald, udvælgelse sortere, var også hvad? 53 00:02:24,090 --> 00:02:24,960 n squared. 54 00:02:24,960 --> 00:02:27,490 Nu i den virkelige verden, kan det blive faktisk være marginalt hurtigere. 55 00:02:27,490 --> 00:02:30,620 Fordi igen, havde jeg ikke nødt til at holde tilbageskridt når jeg havde sorteres 56 00:02:30,620 --> 00:02:31,880 mindste elementer. 57 00:02:31,880 --> 00:02:35,090 Men hvis vi tænker meget store n, og hvis du slags gøre ud matematik som 58 00:02:35,090 --> 00:02:39,170 Jeg gjorde på brættet, med n kvadreret minus noget, alt andet 59 00:02:39,170 --> 00:02:41,850 foruden n kvadreret, når n bliver rigtig stort, ikke 60 00:02:41,850 --> 00:02:42,850 virkelig noget så meget. 61 00:02:42,850 --> 00:02:45,470 Så som dataloger, sortere vi om vende det blinde øje til den mindre 62 00:02:45,470 --> 00:02:49,220 faktorer og kun fokusere på den faktor i et udtryk, der kommer til at gøre 63 00:02:49,220 --> 00:02:50,330 den største forskel. 64 00:02:50,330 --> 00:02:52,840 >> Nå, endelig, så vi ved indsættelse slags. 65 00:02:52,840 --> 00:02:56,620 Og dette var ens i ånden, men snarere end at gå gennem iterativt og 66 00:02:56,620 --> 00:03:01,250 vælge den mindste element én ad gang, jeg tog i stedet den hånd, jeg 67 00:03:01,250 --> 00:03:04,070 blev behandlet, og jeg besluttede, alt Okay, du hører til her. 68 00:03:04,070 --> 00:03:06,160 Så jeg flyttede til det næste element og besluttede, at han eller 69 00:03:06,160 --> 00:03:07,470 hun hørte her. 70 00:03:07,470 --> 00:03:08,810 Og så flyttede jeg på og. 71 00:03:08,810 --> 00:03:11,780 Og jeg kunne til undervejs, flytte disse fyre for at 72 00:03:11,780 --> 00:03:13,030 gøre plads til dem. 73 00:03:13,030 --> 00:03:16,880 Så det var en slags mental vending af udvælgelse slags, vi 74 00:03:16,880 --> 00:03:18,630 kaldet indsættelse slags. 75 00:03:18,630 --> 00:03:20,810 >> Så disse emner for at forekomme i den virkelige verden. 76 00:03:20,810 --> 00:03:23,640 Bare et par år siden, da en vis senator kørte til formand, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, på det tidspunkt, den administrerende direktør for Google faktisk haft mulighed 78 00:03:27,160 --> 00:03:28,040 at interviewe ham. 79 00:03:28,040 --> 00:03:32,010 Og vi troede, vi ville dele denne YouTube klip for dig her, hvis vi kunne slå op 80 00:03:32,010 --> 00:03:32,950 lydstyrken. 81 00:03:32,950 --> 00:03:39,360 >> [VIDEO AFSPIL] 82 00:03:39,360 --> 00:03:44,620 >> -Nu, senator, er du her på Google, og jeg kan lide at tænke på formandskabet 83 00:03:44,620 --> 00:03:46,042 som en jobsamtale. 84 00:03:46,042 --> 00:03:47,770 >> [Latter] 85 00:03:47,770 --> 00:03:50,800 >> -Nu er det svært at få et job som præsident. 86 00:03:50,800 --> 00:03:52,480 Og du går igennem rigor nu. 87 00:03:52,480 --> 00:03:54,330 Det er også svært at få et job hos Google. 88 00:03:54,330 --> 00:03:59,610 Vi har spørgsmål, og vi beder vores kandidater spørgsmål. 89 00:03:59,610 --> 00:04:02,250 Og denne er fra Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Latter] 91 00:04:05,325 --> 00:04:06,400 -Du fyre tror jeg kidding? 92 00:04:06,400 --> 00:04:08,750 Det er lige her. 93 00:04:08,750 --> 00:04:12,110 Hvad er den mest effektive måde at sortere en million to-bit heltal? 94 00:04:12,110 --> 00:04:15,810 >> [Latter] 95 00:04:15,810 --> 00:04:18,260 >> -Jamen, øh - 96 00:04:18,260 --> 00:04:19,029 >> -Undskyld. 97 00:04:19,029 --> 00:04:19,745 Måske burde vi - 98 00:04:19,745 --> 00:04:21,000 >> -Nej, nej, nej, nej, nej. 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, ​​at boblen slags ville være den forkerte vej at gå. 102 00:04:25,328 --> 00:04:26,792 >> [Latter] 103 00:04:26,792 --> 00:04:28,510 >> [Jubler og klapper] 104 00:04:28,510 --> 00:04:31,211 >> -Kom nu, der fortalte ham det her? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [END VIDEOAFSPILNING] 107 00:04:33,350 --> 00:04:35,070 >> DAVID MALAN: Så der har du det. 108 00:04:35,070 --> 00:04:39,600 Så vi begyndte at kvantificere disse kørende gange, så at sige, med noget 109 00:04:39,600 --> 00:04:43,480 kaldet asymptotisk notation, som er bare at henvise til vores slags drejning 110 00:04:43,480 --> 00:04:47,420 det blinde øje til de mindre faktorer, kun at se på den løbende tid, 111 00:04:47,420 --> 00:04:51,250 udførelsen af ​​disse algoritmer, da n får virkelig store over tid. 112 00:04:51,250 --> 00:04:55,110 Og så vi introducerede big O. Og big O repræsenterede noget, som vi troede 113 00:04:55,110 --> 00:04:57,000 på som en øvre grænse. 114 00:04:57,000 --> 00:04:59,570 Og faktisk, Barry, kan vi sænke end mic lidt? 115 00:04:59,570 --> 00:05:01,040 >> Vi troede på dette er en øvre grænse. 116 00:05:01,040 --> 00:05:04,710 Så store O i n kvadreret betyder, at i værste fald noget lignende 117 00:05:04,710 --> 00:05:07,780 udvælgelse sortere ville tage n kvadreret trin. 118 00:05:07,780 --> 00:05:10,310 Eller noget lignende indsættelse slags ville n kvadreret trin. 119 00:05:10,310 --> 00:05:15,150 Nu til noget som indsættelse sortere, hvad der var det værste tilfælde? 120 00:05:15,150 --> 00:05:18,200 Givet et array, er hvad det værste mulige scenario, som du kan finde 121 00:05:18,200 --> 00:05:20,650 dig selv konfronteret med? 122 00:05:20,650 --> 00:05:21,860 >> Det er helt bagud, right? 123 00:05:21,860 --> 00:05:24,530 For hvis det er helt bagud, du nødt til at gøre en hel masse arbejde. 124 00:05:24,530 --> 00:05:26,420 Fordi hvis du er helt bagud, du kommer til at finde den 125 00:05:26,420 --> 00:05:28,840 største element her, selvom det hører dernede. 126 00:05:28,840 --> 00:05:31,140 Så du kommer til at sige, okay, ved dette tidspunkt, du hører til her, 127 00:05:31,140 --> 00:05:32,310 så du lader det alene. 128 00:05:32,310 --> 00:05:35,425 >> Så du er klar, åh, damn, jeg er nødt til flytte dette lidt mindre element 129 00:05:35,425 --> 00:05:36,470 venstre dig. 130 00:05:36,470 --> 00:05:38,770 Så jeg er nødt til at gøre det igen og igen og igen. 131 00:05:38,770 --> 00:05:41,410 Og hvis jeg gik frem og tilbage, du ville sortere i føler udførelsen af 132 00:05:41,410 --> 00:05:45,540 denne algoritme, fordi tiden er jeg blander alle andre nede i 133 00:05:45,540 --> 00:05:46,510 matrix at gøre plads til det. 134 00:05:46,510 --> 00:05:47,750 Så det er det værste tilfælde. 135 00:05:47,750 --> 00:05:48,570 >> Derimod - 136 00:05:48,570 --> 00:05:50,320 og dette var en cliffhanger sidste gang - 137 00:05:50,320 --> 00:05:54,065 Vi sagde, at indsættelse sortere var en omega af hvad? 138 00:05:54,065 --> 00:05:57,530 Hvad er det bedst tænkelige drift tidspunktet for anbringelsen slags? 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 forlod på tavlen sidste gang. 141 00:06:00,980 --> 00:06:03,160 >> Og det er omega n fordi hvorfor? 142 00:06:03,160 --> 00:06:06,630 Tja, i de allerbedste fald, hvad er indsættelse sortere kommer til at blive afleveret? 143 00:06:06,630 --> 00:06:09,830 Tja, en liste, der er helt sorteres allerede minimal arbejde at gøre. 144 00:06:09,830 --> 00:06:12,460 Men hvad er pæne om indsættelse sortere er, at fordi det starter her og 145 00:06:12,460 --> 00:06:15,340 beslutter, åh, du er nummer en, du hører til her. 146 00:06:15,340 --> 00:06:16,970 Åh, sikke en god formue. 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, endnu bedre, du hører her. 150 00:06:21,010 --> 00:06:25,210 Så snart det bliver til slutningen af liste, pr indsættelse slags s pseudokode 151 00:06:25,210 --> 00:06:28,010 at vi gik gennem verbalt sidste gang, er det gjort. 152 00:06:28,010 --> 00:06:32,790 Men udvælgelse sortere, derimod, holdes gør hvad? 153 00:06:32,790 --> 00:06:35,260 >> Holdes i gang gennem listen igen og igen og igen. 154 00:06:35,260 --> 00:06:39,160 Fordi nøglen indsigt var der kun når du har kigget hele vejen til 155 00:06:39,160 --> 00:06:42,500 slutningen af ​​listen kan du være sikker at det element, du valgte var 156 00:06:42,500 --> 00:06:45,560 faktisk den aktuelt mindste element. 157 00:06:45,560 --> 00:06:48,920 Så disse forskellige mentale modeller ende up giver nogle meget virkelige verden 158 00:06:48,920 --> 00:06:53,130 forskelle for os, samt disse teoretiske asymptotiske forskelle. 159 00:06:53,130 --> 00:06:56,910 >> Så bare for at opsummere, så big O n kvadreret, vi har set et par sådanne 160 00:06:56,910 --> 00:06:58,350 algoritmer hidtil. 161 00:06:58,350 --> 00:06:59,580 Big O n? 162 00:06:59,580 --> 00:07:02,870 Hvad er en algoritme, der kunne siges at være stor O n? 163 00:07:02,870 --> 00:07:06,930 I værste tilfælde tager det en lineær række trin. 164 00:07:06,930 --> 00:07:07,810 >> OK, lineær søgning. 165 00:07:07,810 --> 00:07:10,470 Og i værste fald er hvor element, du leder efter, når 166 00:07:10,470 --> 00:07:12,950 anvende lineær søgning? 167 00:07:12,950 --> 00:07:14,680 >> OK, i værste fald, det er ikke engang der. 168 00:07:14,680 --> 00:07:17,000 Eller i det andet værste tilfælde er det hele vejen i sidste ende, hvilket er 169 00:07:17,000 --> 00:07:18,880 plus-eller-minus en et-trins forskel. 170 00:07:18,880 --> 00:07:21,180 Så i slutningen af ​​dagen, kan vi sige, det er lineær. 171 00:07:21,180 --> 00:07:23,910 Big O n ville være lineær søgning, fordi i værste fald 172 00:07:23,910 --> 00:07:26,610 element er ikke engang der, eller det er hele vejen i slutningen. 173 00:07:26,610 --> 00:07:29,370 >> Nå, big O log n. 174 00:07:29,370 --> 00:07:32,760 Vi talte ikke meget detaljeret om dette, men vi har set det før. 175 00:07:32,760 --> 00:07:36,840 Hvad kører i såkaldt logaritmisk tid, i værste fald? 176 00:07:36,840 --> 00:07:38,500 >> Yeah, så binær søgning. 177 00:07:38,500 --> 00:07:42,930 Og binær søgning i værste fald kan have elementet sted i 178 00:07:42,930 --> 00:07:45,640 midten, eller et andet sted inde i array. 179 00:07:45,640 --> 00:07:48,040 Men du kun finde den, når du opdele listen i halve, i 180 00:07:48,040 --> 00:07:48,940 halvdelen i halve. i halve 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 igen, værste fald, det er ikke engang der. 183 00:07:52,500 --> 00:07:56,770 Men du ved ikke, at det ikke er der indtil du slags nå at sidste 184 00:07:56,770 --> 00:08:00,470 bottom-de fleste elementer ved at halvere og en halvering og en halvering. 185 00:08:00,470 --> 00:08:01,400 >> Big O 1.. 186 00:08:01,400 --> 00:08:03,540 Så vi kunne big O på 2, big O på 3. 187 00:08:03,540 --> 00:08:06,260 Når du vil bare et konstant antal, vi bare sortere for bare forenkle 188 00:08:06,260 --> 00:08:07,280 at så stor O i 1.. 189 00:08:07,280 --> 00:08:10,440 Selvom om realistisk, det tager 2 eller endda 100 trin, hvis det er en 190 00:08:10,440 --> 00:08:13,680 konstant antal trin, siger vi bare big O i 1.. 191 00:08:13,680 --> 00:08:15,930 Hvad er en algoritme, der er i big O af 1? 192 00:08:15,930 --> 00:08:18,350 >> PUBLIKUM: Finde længden af en variabel. 193 00:08:18,350 --> 00:08:21,090 >> DAVID MALAN: at finde den Længden af ​​en variabel? 194 00:08:21,090 --> 00:08:23,870 >> PUBLIKUM: Nej, længden hvis den allerede er sorteret. 195 00:08:23,870 --> 00:08:24,160 >> DAVID MALAN: Godt. 196 00:08:24,160 --> 00:08:27,850 OK, så at finde længden af ​​noget hvis længden af, at noget, som 197 00:08:27,850 --> 00:08:30,020 et array, lagres i nogle variabel. 198 00:08:30,020 --> 00:08:33,380 Fordi du kan bare læse den variable, eller udskrive variabel eller 199 00:08:33,380 --> 00:08:34,960 bare generelt få adgang til denne variabel. 200 00:08:34,960 --> 00:08:37,299 Og voila, der tager konstant tid. 201 00:08:37,299 --> 00:08:38,909 >> Derimod tænker tilbage til bunden. 202 00:08:38,909 --> 00:08:42,460 Tænk tilbage til den første uge af C, ringer bare printf og udskrivning 203 00:08:42,460 --> 00:08:46,240 noget på skærmen er velsagtens konstant tid, fordi det tager bare 204 00:08:46,240 --> 00:08:50,880 vist antal af CPU cycles at vise denne tekst på skærmen. 205 00:08:50,880 --> 00:08:52,720 Eller vent - hvad betyder det? 206 00:08:52,720 --> 00:08:56,430 Hvor ellers kan vi modellere udførelse af printf? 207 00:08:56,430 --> 00:09:00,420 Skulle nogen gerne være uenige, at måske er det ikke rigtig konstant tid? 208 00:09:00,420 --> 00:09:03,600 I hvilken forstand kan printf kører tid, faktisk udskrive en streng på 209 00:09:03,600 --> 00:09:05,580 skærmen, være noget bortset konstant. 210 00:09:05,580 --> 00:09:07,860 >> PUBLIKUM: [uhørlig]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID MALAN: Ja. 212 00:09:08,230 --> 00:09:09,300 Så det afhænger af vores perspektiv. 213 00:09:09,300 --> 00:09:13,390 Hvis vi tror faktisk af input til printf som strengen, og 214 00:09:13,390 --> 00:09:16,380 derfor har vi måle størrelsen af ​​denne input fra dens længde - så lad os kalde 215 00:09:16,380 --> 00:09:17,780 denne længde n samt - 216 00:09:17,780 --> 00:09:21,990 velsagtens, printf selv store O n fordi det kommer til at tage dig n skridt 217 00:09:21,990 --> 00:09:24,750 at udskrive hver af disse n tegn, mest sandsynlige. 218 00:09:24,750 --> 00:09:27,730 I det mindste i det omfang, at vi antager at måske er det ved hjælp af en for-løkke 219 00:09:27,730 --> 00:09:28,560 under hætten. 220 00:09:28,560 --> 00:09:30,860 >> Men vi ville have til at se på det kode til at forstå det bedre. 221 00:09:30,860 --> 00:09:33,650 Og ja, når du fyre starter analysere dine egne algoritmer, vil du 222 00:09:33,650 --> 00:09:34,900 bogstaveligt gøre netop det. 223 00:09:34,900 --> 00:09:37,765 Sort of øjeæblet din kode og tænke om - okay, jeg har denne løkke 224 00:09:37,765 --> 00:09:41,870 her eller jeg har en indlejret sløjfer her der kommer til at gøre n ting n gange, 225 00:09:41,870 --> 00:09:46,050 og du kan sortere fornuftens vej gennem koden, det, selvom 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å hvad med omega n kvadreret? 228 00:09:49,730 --> 00:09:53,582 Hvad var en algoritme, der i den bedste tilfælde stadig tog n kvadreret trin? 229 00:09:53,582 --> 00:09:54,014 Ja? 230 00:09:54,014 --> 00:09:54,880 >> PUBLIKUM: [uhørlig]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID MALAN: So udvælgelse slags. 232 00:09:55,900 --> 00:09:59,150 Fordi i dette problem virkelig reduceret det faktum, at igen, ved jeg ikke 233 00:09:59,150 --> 00:10:02,600 Jeg har fundet den nuværende mindste indtil Jeg har tjekket alle darn elementer. 234 00:10:02,600 --> 00:10:08,050 Så omega, siger, n, vi bare kom op med én. 235 00:10:08,050 --> 00:10:09,300 Insertion slags. 236 00:10:09,300 --> 00:10:12,370 Hvis listen sker for at blive sorteret allerede i bedste fald vi bare 237 00:10:12,370 --> 00:10:15,090 at gøre en pass gennem det, på hvilket tidspunkt vi er sikre. 238 00:10:15,090 --> 00:10:17,890 Og så der kunne siges at være lineær, for sikker. 239 00:10:17,890 --> 00:10:20,570 >> Hvad omega af 1? 240 00:10:20,570 --> 00:10:23,790 Hvad i bedste fald tage måske en konstant antal trin? 241 00:10:23,790 --> 00:10:27,220 Så lineær søgning, hvis du bare heldig og elementet du søger 242 00:10:27,220 --> 00:10:31,000 er lige ved starten af ​​listen, hvis det er, hvor du starter din 243 00:10:31,000 --> 00:10:33,070 lineær traversal af listen. 244 00:10:33,070 --> 00:10:35,180 >> Og dette er sandt for en række ting. 245 00:10:35,180 --> 00:10:37,660 For eksempel, binære selv søgning er omega på 1. 246 00:10:37,660 --> 00:10:40,310 For hvad hvis du får virkelig pokkers heldig og smack-dab i midten af 247 00:10:40,310 --> 00:10:42,950 dit array er antallet du leder efter? 248 00:10:42,950 --> 00:10:45,730 Så du kan få heldige der, så godt. 249 00:10:45,730 --> 00:10:49,190 >> Denne ene endelig omega n log n. 250 00:10:49,190 --> 00:10:52,573 Så n log n, vi virkelig ikke tale om endnu, men - 251 00:10:52,573 --> 00:10:53,300 >> PUBLIKUM: Flet slags? 252 00:10:53,300 --> 00:10:53,960 >> DAVID MALAN: Merge slags. 253 00:10:53,960 --> 00:10:56,920 Det var cliffhanger sidste gang, hvor vi foreslog, og vi viste 254 00:10:56,920 --> 00:10:58,600 visuelt, at der er algoritmer. 255 00:10:58,600 --> 00:11:02,470 Og flette slags blot en sådan algoritme, der er fundamentalt hurtigere 256 00:11:02,470 --> 00:11:03,450 end nogle af de andre fyre. 257 00:11:03,450 --> 00:11:07,800 Faktisk fusionere kort er ikke kun i bedste fald n log n, i værste 258 00:11:07,800 --> 00:11:09,460 tilfælde n log n. 259 00:11:09,460 --> 00:11:14,540 Og når du har dette sammenfald af omega og store O er den samme? 260 00:11:14,540 --> 00:11:17,310 Vi kan faktisk beskrive det som hvad der er kaldet theta, selvom det er en 261 00:11:17,310 --> 00:11:18,220 lidt mindre almindelige. 262 00:11:18,220 --> 00:11:21,730 Men det betyder bare de to grænser, i dette tilfælde, er de samme. 263 00:11:21,730 --> 00:11:25,770 >> Så fusionere sortere, hvad betyder dette virkelig koges ned til os? 264 00:11:25,770 --> 00:11:27,000 Nå, genkalde motivation. 265 00:11:27,000 --> 00:11:30,340 Lad mig trække op en anden animation, vi ikke se på sidste gang. 266 00:11:30,340 --> 00:11:33,390 Denne ene, samme idé, men det er lidt større. 267 00:11:33,390 --> 00:11:36,160 Og jeg har tænkt mig at gå videre og påpege første - vi har indsættelse sortere på 268 00:11:36,160 --> 00:11:39,410 øverst til venstre, derefter valg sortere, boble sortere, et par andre former - 269 00:11:39,410 --> 00:11:42,670 shell og hurtigt - at vi ikke har talt om, og heap og flette slags. 270 00:11:42,670 --> 00:11:47,090 >> Så i det mindste forsøge at fokusere dine øjne på top tre på den venstre og derefter 271 00:11:47,090 --> 00:11:49,120 fusionere slags når jeg klikker denne grønne pil. 272 00:11:49,120 --> 00:11:51,900 Men jeg vil lade dem alle køre, bare for at give dig en fornemmelse af mangfoldigheden af 273 00:11:51,900 --> 00:11:53,980 algoritmer, der findes i verden. 274 00:11:53,980 --> 00:11:56,180 Jeg har tænkt mig at lade dette løbe for blot et par sekunder. 275 00:11:56,180 --> 00:11:59,640 Og hvis du fokusere dine øjne - vælg et algoritme, fokus på det for bare en 276 00:11:59,640 --> 00:12:02,970 sekunder - du vil begynde at se mønster, at det er at gennemføre. 277 00:12:02,970 --> 00:12:04,530 >> Flet sortere, varsel, er gjort. 278 00:12:04,530 --> 00:12:06,430 Heap sortere, hurtig sortere, shell - 279 00:12:06,430 --> 00:12:09,480 så det synes vi introducerede tre værste algoritmer sidste uge. 280 00:12:09,480 --> 00:12:12,960 Men det er godt, at vi er her i dag for at se på sammenfletning slags, som er en af 281 00:12:12,960 --> 00:12:16,500 de lettere dem er at se på, selv selv om det sandsynligvis vil bøje dit sind 282 00:12:16,500 --> 00:12:17,490 bare en lille smule. 283 00:12:17,490 --> 00:12:21,130 Her kan vi se, hvor meget udvælgelse sortere stinker. 284 00:12:21,130 --> 00:12:24,600 >> Men på bagsiden, er det virkelig nemt at implementere. 285 00:12:24,600 --> 00:12:28,160 Og måske for P Set 3, er, at en af algoritmer du har valgt at implementere 286 00:12:28,160 --> 00:12:28,960 for standard edition. 287 00:12:28,960 --> 00:12:30,970 Helt fint, helt korrekt. 288 00:12:30,970 --> 00:12:35,210 >> Men igen, da n bliver store, hvis du vælger at gennemføre en hurtigere algoritme 289 00:12:35,210 --> 00:12:39,020 gerne fusionere sortere, odds er i større og større input, din kode er bare 290 00:12:39,020 --> 00:12:39,800 kommer til at løbe hurtigere. 291 00:12:39,800 --> 00:12:41,090 Din hjemmeside kommer til at fungere bedre. 292 00:12:41,090 --> 00:12:42,650 Dine brugere vil være gladere. 293 00:12:42,650 --> 00:12:45,280 Og så der er disse effekter for rent faktisk at give 294 00:12:45,280 --> 00:12:47,350 os nogle dybere tanke. 295 00:12:47,350 --> 00:12:49,990 >> Så lad os tage et kig på, hvad fusionere sortere er faktisk handler om. 296 00:12:49,990 --> 00:12:52,992 Det fede er, at fusionere slags er netop dette. 297 00:12:52,992 --> 00:12:56,300 Dette er, igen, hvad vi har kaldt pseudokode, pseudokode væsen 298 00:12:56,300 --> 00:12:57,720 Engelsk-lignende syntaks. 299 00:12:57,720 --> 00:12:59,890 Og enkelheden er slags fascinerende. 300 00:12:59,890 --> 00:13:02,840 >> Så på input med n elementer - således at betyder bare, her er et array. 301 00:13:02,840 --> 00:13:04,000 Det har fået n ting i det. 302 00:13:04,000 --> 00:13:05,370 Det er alt, vi siger der. 303 00:13:05,370 --> 00:13:07,560 >> Hvis n er mindre end 2, vende tilbage. 304 00:13:07,560 --> 00:13:08,640 Så det er bare den trivielle sagen. 305 00:13:08,640 --> 00:13:12,580 Hvis n er mindre end 2, så selvfølgelig er det 1 eller 0, i hvilket tilfælde ting 306 00:13:12,580 --> 00:13:14,780 er allerede sorteret eller ikke-eksisterende, så bare vende tilbage. 307 00:13:14,780 --> 00:13:15,900 Der er intet at gøre. 308 00:13:15,900 --> 00:13:18,360 Så det er en enkel sag at plukke fra. 309 00:13:18,360 --> 00:13:20,110 >> Else, vi har tre trin. 310 00:13:20,110 --> 00:13:23,650 Sortere den venstre halvdel af de elementer, sortere den højre halvdel af elementerne, 311 00:13:23,650 --> 00:13:26,650 og derefter flette de sorterede halvdele. 312 00:13:26,650 --> 00:13:29,400 Det interessante her er, at Jeg er lidt punting, right? 313 00:13:29,400 --> 00:13:32,300 Der er lidt af en cirkulær definition til denne algoritme. 314 00:13:32,300 --> 00:13:35,986 I hvilken forstand er denne algoritme s definition cirkulære? 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 af sine trin er "slags 317 00:13:41,670 --> 00:13:44,640 noget ". Og så rejser Spørgsmålet, ja, hvad skal jeg bruge 318 00:13:44,640 --> 00:13:46,460 at sortere den venstre halvdel og den højre halvdel? 319 00:13:46,460 --> 00:13:49,600 Og skønhed her er, at selvom igen, det er den hjernevridende 320 00:13:49,600 --> 00:13:54,030 del potentielt, kan du bruge samme algoritme til at sortere den venstre halvdel. 321 00:13:54,030 --> 00:13:54,700 >> Men vent et øjeblik. 322 00:13:54,700 --> 00:13:57,070 Når du får at vide at sortere venstre halvdel, hvad er de to 323 00:13:57,070 --> 00:13:58,240 skridt kommer til at være den næste? 324 00:13:58,240 --> 00:14:00,550 Vi sortere venstre halvdel af venstre halvdel og højre 325 00:14:00,550 --> 00:14:01,420 halvdelen af ​​den venstre halvdel. 326 00:14:01,420 --> 00:14:04,430 Damn, hvordan jeg sorterer de to halvdele, eller kvarte, nu? 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 sorteringsalgoritme her. 329 00:14:07,830 --> 00:14:10,660 Og selvom du måske bekymre sig på først det er lidt en uendelig 330 00:14:10,660 --> 00:14:12,780 loop, det er en cyklus, der er aldrig vil ende - det vil 331 00:14:12,780 --> 00:14:15,770 ende, når det sker? 332 00:14:15,770 --> 00:14:16,970 Når n er mindre end 2. 333 00:14:16,970 --> 00:14:19,180 Som i sidste ende kommer til at ske, fordi hvis du holder halvere og 334 00:14:19,180 --> 00:14:23,020 halvering at halvere disse halvdele, helt sikkert sidst du kommer til at ende 335 00:14:23,020 --> 00:14:25,350 op med kun 1 eller 0 elementer. 336 00:14:25,350 --> 00:14:28,500 På hvilket punkt, denne algoritme siger, at du er færdig. 337 00:14:28,500 --> 00:14:31,020 >> Så den virkelige magi i denne algoritme synes at være i 338 00:14:31,020 --> 00:14:33,470 at sidste trin, sammenlægning. 339 00:14:33,470 --> 00:14:37,190 Denne enkle idé bare at fusionere to ting, det er, hvad der i sidste ende kommer 340 00:14:37,190 --> 00:14:40,920 at tillade os at sortere et array af, lad os sige, otte elementer. 341 00:14:40,920 --> 00:14:44,410 Så jeg har otte mere stress bolde op her otte stykker papir, og en 342 00:14:44,410 --> 00:14:45,500 Google Glas - 343 00:14:45,500 --> 00:14:46,140 som jeg kommer til at 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 tage otte frivillige, og lad os se om vi kan 346 00:14:48,970 --> 00:14:51,430 spille dette ud, så. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Datalogi bliver sjovt. 349 00:14:53,565 --> 00:14:54,320 Ok. 350 00:14:54,320 --> 00:14:57,770 Så hvad med jer tre, største hånd deroppe. 351 00:14:57,770 --> 00:14:58,580 Fire i ryggen. 352 00:14:58,580 --> 00:15:02,220 Og hvad vi vil gøre dig tre i denne række? 353 00:15:02,220 --> 00:15:03,390 Og fire i front. 354 00:15:03,390 --> 00:15:04,920 Så du otte, kom op. 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å, hvad det er. 357 00:15:13,450 --> 00:15:14,810 Er det stress bolde? 358 00:15:14,810 --> 00:15:16,510 De bordlamper? 359 00:15:16,510 --> 00:15:18,650 Materialet? 360 00:15:18,650 --> 00:15:19,680 Internettet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Så kom op. 363 00:15:21,310 --> 00:15:22,310 Hvem vil gerne - 364 00:15:22,310 --> 00:15:23,570 at komme op. 365 00:15:23,570 --> 00:15:24,240 Lad os se. 366 00:15:24,240 --> 00:15:26,460 Og det sætter dig i placering - 367 00:15:26,460 --> 00:15:27,940 du er i location én. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, vent et øjeblik. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - Åh, godt. 370 00:15:30,760 --> 00:15:31,310 Okay, vi er gode. 371 00:15:31,310 --> 00:15:35,130 Okay, så alle har et sæde, men ikke på Google Glass. 372 00:15:35,130 --> 00:15:36,475 Lad mig til kø disse op. 373 00:15:36,475 --> 00:15:37,115 Hvad er dit navn? 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 Okay, du kommer til at ligne nørd, hvis det er OK. 377 00:15:42,000 --> 00:15:44,625 Tja, det gør jeg også, jeg formoder, for bare et øjeblik. 378 00:15:44,625 --> 00:15:45,875 Okay, standby. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Vi har forsøgt at komme med en use case for Google Glass, og vi 381 00:15:50,950 --> 00:15:53,750 troede det ville være sjovt at bare gøre dette, når folk er på scenen. 382 00:15:53,750 --> 00:15:57,120 Vi registrerer 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, hvad Google hensigten. 385 00:15:59,830 --> 00:16:02,260 Okay, hvis du ikke har noget imod at bære dette for de næste akavede minutter, 386 00:16:02,260 --> 00:16:03,150 det ville være vidunderligt. 387 00:16:03,150 --> 00:16:08,620 >> Okay, så vi har her en vifte af elementer, og at matrix, som pr 388 00:16:08,620 --> 00:16:11,480 stykker papir i disse folk ' hænder, er i øjeblikket usorteret. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Åh, det er så underligt. 390 00:16:12,050 --> 00:16:12,810 >> DAVID MALAN: Det er temmelig tilfældigt. 391 00:16:12,810 --> 00:16:15,760 Og på bare et øjeblik, vi kommer til at prøve at gennemføre fusionere slags sammen 392 00:16:15,760 --> 00:16:17,950 og se, hvor det centrale indsigt er. 393 00:16:17,950 --> 00:16:21,970 Og det trick her med merge slags er noget, vi ikke har antaget endnu. 394 00:16:21,970 --> 00:16:24,030 Vi har faktisk brug for nogle ekstra plads. 395 00:16:24,030 --> 00:16:26,650 Så hvad kommer til at være særligt interessante ved dette er, at disse 396 00:16:26,650 --> 00:16:29,270 fyre kommer til at bevæge sig lidt rundt bit, fordi jeg har tænkt mig at antage, at 397 00:16:29,270 --> 00:16:31,880 der er en ekstra række af rum, sige, lige bag dem. 398 00:16:31,880 --> 00:16:34,570 >> Så hvis de er bag deres stol, det er den sekundære array. 399 00:16:34,570 --> 00:16:36,960 Hvis de er siddende her, det er den primære array. 400 00:16:36,960 --> 00:16:40,170 Men det er en ressource, som vi har ikke gearede hidtil med boble 401 00:16:40,170 --> 00:16:42,040 sortere, med udvælgelse sortere, med indsættelse slags. 402 00:16:42,040 --> 00:16:44,600 Recall i sidste uge, alle bare slags blandes på plads. 403 00:16:44,600 --> 00:16:46,840 De havde ikke bruge nogen ekstra hukommelse. 404 00:16:46,840 --> 00:16:49,310 Vi gjorde plads til folk med flytte folk rundt. 405 00:16:49,310 --> 00:16:50,580 >> Så dette er en vigtig indsigt, også. 406 00:16:50,580 --> 00:16:53,410 Der er denne afvejning, i almindelighed i datalogi, af ressourcer. 407 00:16:53,410 --> 00:16:55,800 Hvis du ønsker at fremskynde noget som om tiden, er du nødt til 408 00:16:55,800 --> 00:16:56,900 nødt til at betale en pris. 409 00:16:56,900 --> 00:17:00,750 Og en af ​​disse priser er meget ofte rum, mængden af ​​hukommelse eller hård 410 00:17:00,750 --> 00:17:01,700 diskplads, du bruger. 411 00:17:01,700 --> 00:17:03,640 Eller ærligt, beløbet programmør tid. 412 00:17:03,640 --> 00:17:06,700 Hvor meget tid det tager dig, det menneskelige, til rent faktisk at gennemføre nogle mere 413 00:17:06,700 --> 00:17:07,829 kompliceret algoritme. 414 00:17:07,829 --> 00:17:09,760 Men i dag, det trade-off er tid og rum. 415 00:17:09,760 --> 00:17:11,930 >> Så hvis du fyre bare kunne holde din tal, så 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 Excellent. 418 00:17:16,599 --> 00:17:19,520 Så jeg har tænkt mig at forsøge at orkestrere ting, hvis du fyre kan bare 419 00:17:19,520 --> 00:17:21,800 følge mit bly her. 420 00:17:21,800 --> 00:17:26,650 >> Så jeg vil gennemføre det første, at første trin af pseudokode, som er 421 00:17:26,650 --> 00:17:29,440 på input med n elementer, hvis n er mindre end 2, og derefter vende tilbage. 422 00:17:29,440 --> 00:17:31,370 Det er klart, at der ikke finder anvendelse, så vi videre. 423 00:17:31,370 --> 00:17:33,340 Så sortere den venstre halvdel af elementerne. 424 00:17:33,340 --> 00:17:36,220 Så det betyder, at jeg har tænkt mig at fokusere min opmærksomhed for bare et øjeblik på disse 425 00:17:36,220 --> 00:17:37,310 fire fyre her. 426 00:17:37,310 --> 00:17:39,774 Okay, hvad skal jeg næste gøre? 427 00:17:39,774 --> 00:17:40,570 >> PUBLIKUM: Sortere den venstre halvdel. 428 00:17:40,570 --> 00:17:42,780 >> DAVID MALAN: Så nu har jeg til at sortere den venstre halvdel af disse fyre. 429 00:17:42,780 --> 00:17:45,580 Fordi igen, påtager dig selv det Målet er at sortere den venstre halvdel. 430 00:17:45,580 --> 00:17:46,440 Hvordan gør du det? 431 00:17:46,440 --> 00:17:49,140 Bare følg instruktionerne, selv selvom vi gør det igen. 432 00:17:49,140 --> 00:17:50,160 Så sortere den venstre halvdel. 433 00:17:50,160 --> 00:17:52,030 Nu er jeg sortere disse to fyre. 434 00:17:52,030 --> 00:17:53,563 Hvad bliver det næste? 435 00:17:53,563 --> 00:17:54,510 >> PUBLIKUM: Sortere den venstre halvdel. 436 00:17:54,510 --> 00:17:55,460 >> DAVID MALAN: Sortere den venstre halvdel. 437 00:17:55,460 --> 00:18:00,680 Så nu disse, denne plads her, er en liste over størrelse 1. 438 00:18:00,680 --> 00:18:01,365 Og hvad er dit navn igen? 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 sorteret, fordi listen er over størrelse 1. 442 00:18:07,470 --> 00:18:09,490 Hvad gør jeg næste gøre? 443 00:18:09,490 --> 00:18:13,680 OK, tilbage, fordi denne liste er str. 1, hvilket er mindre end 2. 444 00:18:13,680 --> 00:18:14,320 Så hvad er næste skridt? 445 00:18:14,320 --> 00:18:17,490 Og nu er du nødt til at slags bakke i dit sind. 446 00:18:17,490 --> 00:18:19,340 >> Sortere den højre halvdel, som er - 447 00:18:19,340 --> 00:18:19,570 hvad er dit navn? 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å hvad gør vi nu, 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: Forsigtig. 453 00:18:24,760 --> 00:18:29,540 Vi vender tilbage først, og nu er den tredje skridt - og hvis jeg slags skildre det ved 454 00:18:29,540 --> 00:18:33,490 omfavne de to pladser nu, nu er jeg nødt til at flette disse to elementer. 455 00:18:33,490 --> 00:18:35,530 Så nu desværre elementerne er ude af drift. 456 00:18:35,530 --> 00:18:39,920 Men det er, hvor de fusionerende proces begynder at få overbevisende. 457 00:18:39,920 --> 00:18:42,410 >> Så hvis du fyrene kunne stå op for netop et øjeblik, jeg får brug for dig, i en 458 00:18:42,410 --> 00:18:44,170 øjeblik at træde bag din stol. 459 00:18:44,170 --> 00:18:46,480 Og hvis Linda, fordi 2 er mindre end 4, hvorfor ikke 460 00:18:46,480 --> 00:18:48,130 du kommer rundt først? 461 00:18:48,130 --> 00:18:48,690 Bliv der. 462 00:18:48,690 --> 00:18:50,520 Så Linda, du kommer rundt først. 463 00:18:50,520 --> 00:18:53,820 >> Nu i virkeligheden, hvis det er bare et array Vi kunne bare flytte hende i realtid 464 00:18:53,820 --> 00:18:55,360 fra denne stol til dette sted. 465 00:18:55,360 --> 00:18:57,770 Så forestil dig, der tog nogle konstante Antallet af trin 1. 466 00:18:57,770 --> 00:18:58,480 Og nu - 467 00:18:58,480 --> 00:19:01,490 men vi er nødt til at sætte dig i den første placering her. 468 00:19:01,490 --> 00:19:03,930 >> Og nu, hvis du kunne komme rundt, så godt, vi kommer til at 469 00:19:03,930 --> 00:19:06,300 være i placering to. 470 00:19:06,300 --> 00:19:09,120 Og selvom det føles som om det er tage et stykke tid, er det dejligt nu 471 00:19:09,120 --> 00:19:14,710 at den venstre halvdel af venstre halvdel er nu sorteret. 472 00:19:14,710 --> 00:19:18,010 Så hvad var det næste skridt, hvis vi nu spole videre i historien? 473 00:19:18,010 --> 00:19:18,980 >> PUBLIKUM: Right halvdel. 474 00:19:18,980 --> 00:19:19,900 >> DAVID MALAN: Sortere højre halvdel. 475 00:19:19,900 --> 00:19:21,320 Så du fyre nødt til at gøre dette, så godt. 476 00:19:21,320 --> 00:19:23,510 Så hvis du kunne stå op for bare et øjeblik? 477 00:19:23,510 --> 00:19:25,192 Og hvad er dit navn? 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 nu den venstre halvdelen af ​​den højre halvdel. 481 00:19:29,720 --> 00:19:31,400 Og så er hun en liste over størrelse 1. 482 00:19:31,400 --> 00:19:32,380 Hun er tydeligvis sorteres. 483 00:19:32,380 --> 00:19:33,070 Og dit navn igen? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID MALAN: Michelle er naturligvis en liste over størrelse 1. 486 00:19:35,340 --> 00:19:36,050 Hun har allerede ordnet. 487 00:19:36,050 --> 00:19:38,690 Så nu magien sker, de fusionerende proces. 488 00:19:38,690 --> 00:19:39,790 Så hvem kommer til at komme først? 489 00:19:39,790 --> 00:19:41,560 Naturligvis Michelle. 490 00:19:41,560 --> 00:19:43,280 Så hvis du kunne komme rundt igen. 491 00:19:43,280 --> 00:19:47,090 Den plads, vi har til rådighed for hende nu er lige bag denne stol her. 492 00:19:47,090 --> 00:19:51,580 Og nu, hvis du kunne komme tilbage så godt, vi nu har, for at være klar, to 493 00:19:51,580 --> 00:19:53,810 halvdele, hver af størrelse 2 - 494 00:19:53,810 --> 00:19:57,090 og bare for skildring skyld, hvis du kunne gøre en lille smule af et rum - 495 00:19:57,090 --> 00:19:59,780 man forlod halvdelen her, en højre halvdel her. 496 00:19:59,780 --> 00:20:01,160 >> Spol tilbage yderligere i historien. 497 00:20:01,160 --> 00:20:02,270 Hvilken trin er det næste? 498 00:20:02,270 --> 00:20:03,030 >> PUBLIKUM: Flet. 499 00:20:03,030 --> 00:20:04,160 >> DAVID MALAN: Så nu har vi at fusionere. 500 00:20:04,160 --> 00:20:07,490 Så OK, så nu, heldigvis, vi netop frigjort fire stole. 501 00:20:07,490 --> 00:20:11,480 Så vi har brugt dobbelt så meget hukommelse, men vi kan give flip-floppe mellem 502 00:20:11,480 --> 00:20:12,330 de to arrays. 503 00:20:12,330 --> 00:20:14,190 Så hvilket nummer der skal komme først? 504 00:20:14,190 --> 00:20:14,850 Så Michelle, naturligvis. 505 00:20:14,850 --> 00:20:16,680 Så kom rundt og tage din plads her. 506 00:20:16,680 --> 00:20:19,120 Og derefter nummer 2 er naturligvis næste, så du kommer her. 507 00:20:19,120 --> 00:20:21,520 Nummer 4, nummer 6. 508 00:20:21,520 --> 00:20:23,390 Og igen, selvom der er en lidt Walking involveret, 509 00:20:23,390 --> 00:20:26,010 virkelig kunne disse ske med det samme, ved at flytte en - 510 00:20:26,010 --> 00:20:26,880 OK, godt spillet. 511 00:20:26,880 --> 00:20:28,350 >> [Latter] 512 00:20:28,350 --> 00:20:29,680 >> DAVID MALAN: Og nu er vi i temmelig god figur. 513 00:20:29,680 --> 00:20:34,910 Den venstre halvdel af hele input er nu blevet sorteret. 514 00:20:34,910 --> 00:20:37,370 Okay, så disse fyre havde den fordel min - 515 00:20:37,370 --> 00:20:40,340 hvordan gik det ender alle pigerne på venstre og alle drengene til højre? 516 00:20:40,340 --> 00:20:42,450 >> OK, så fyre 'Slå nu. 517 00:20:42,450 --> 00:20:44,680 Så jeg vil ikke gå dig gennem disse trin. 518 00:20:44,680 --> 00:20:46,550 Vi vil se, om vi kan genanvende samme pseudokode. 519 00:20:46,550 --> 00:20:50,050 Hvis du ønsker at gå videre og stå op, og jer, lad mig give dig mikrofonen. 520 00:20:50,050 --> 00:20:52,990 Se om du ikke kan kopiere, hvad Vi gjorde bare her på 521 00:20:52,990 --> 00:20:53,880 anden ende af listen. 522 00:20:53,880 --> 00:20:59,530 Hvem har brug for at tale først, baseret på algoritmen? 523 00:20:59,530 --> 00:21:03,210 Så forklare, hvad du laver, før du foretager nogen mund bevægelser. 524 00:21:03,210 --> 00:21:05,930 >> SPEAKER 1: Okay, så da Jeg er venstre halvdel af 525 00:21:05,930 --> 00:21:07,790 venstre halvdel, jeg vender tilbage. 526 00:21:07,790 --> 00:21:08,730 Right? 527 00:21:08,730 --> 00:21:09,250 >> DAVID MALAN: Godt. 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 gør mic gå til det næste? 530 00:21:11,800 --> 00:21:12,920 >> SPEAKER 1: Næste nummer. 531 00:21:12,920 --> 00:21:14,720 >> SPEAKER 2: Så jeg er den højre halvdel Den venstre halvdel af 532 00:21:14,720 --> 00:21:17,830 venstre halvdel, og jeg vender tilbage. 533 00:21:17,830 --> 00:21:18,050 >> DAVID MALAN: Godt. 534 00:21:18,050 --> 00:21:18,550 Du vender tilbage. 535 00:21:18,550 --> 00:21:21,855 Så nu, hvad er det næste op for jer to? 536 00:21:21,855 --> 00:21:23,740 >> SPEAKER 2: Vi ønsker se, hvem der er mindre. 537 00:21:23,740 --> 00:21:24,200 >> DAVID MALAN: Præcis. 538 00:21:24,200 --> 00:21:24,940 Vi ønsker at fusionere. 539 00:21:24,940 --> 00:21:27,590 Den plads, vi vil bruge til at fusionere dig ind, selvom de er 540 00:21:27,590 --> 00:21:30,250 naturligvis sorteres allerede, vi vil at følge den samme algoritme. 541 00:21:30,250 --> 00:21:31,560 Så der går i tilbage først? 542 00:21:31,560 --> 00:21:35,720 Så 3 og derefter 7.. 543 00:21:35,720 --> 00:21:38,570 Og nu mic går til disse gutter, OK? 544 00:21:38,570 --> 00:21:43,590 >> SPEAKER 3: Så jeg er den højre halvdel af venstre halvdel, og min n er mindre end 545 00:21:43,590 --> 00:21:45,048 1, så jeg bare kommer til at passere - 546 00:21:45,048 --> 00:21:46,380 >> DAVID MALAN: Godt. 547 00:21:46,380 --> 00:21:49,450 >> SPEAKER 4: Jeg er den rigtige halvdel af højre halvdel af den højre halvdel, og jeg er 548 00:21:49,450 --> 00:21:51,740 også en person, så jeg er vil vende tilbage. 549 00:21:51,740 --> 00:21:52,990 Så nu 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å tilbage. 552 00:21:56,150 --> 00:21:57,160 >> DAVID MALAN: Så du går ind i ryggen. 553 00:21:57,160 --> 00:21:59,200 Så 5 går først, derefter 8.. 554 00:21:59,200 --> 00:22:01,240 Og nu publikum, der er den trin er vi nødt til nu tilbage 555 00:22:01,240 --> 00:22:02,200 tilbage til i vores sind? 556 00:22:02,200 --> 00:22:02,940 >> PUBLIKUM: Flet. 557 00:22:02,940 --> 00:22:07,270 >> DAVID MALAN: Sammenlægning venstre halvdel og højre halvdelen af ​​den oprindelige venstre halvdel. 558 00:22:07,270 --> 00:22:08,840 Så nu - 559 00:22:08,840 --> 00:22:10,520 og bare for at gøre dette klart, gøre en lille smule plads 560 00:22:10,520 --> 00:22:11,690 mellem jer to. 561 00:22:11,690 --> 00:22:13,800 Så nu, er de to lister, venstre og højre. 562 00:22:13,800 --> 00:22:18,320 Så hvordan kan vi nu flette jer ind forreste sæderække igen? 563 00:22:18,320 --> 00:22:19,600 >> 3. går først. 564 00:22:19,600 --> 00:22:20,850 Derefter 5, naturligvis. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Derefter 7 og nu 8. 567 00:22:27,330 --> 00:22:28,710 OK, og nu er vi? 568 00:22:28,710 --> 00:22:29,650 >> PUBLIKUM: Ikke færdig. 569 00:22:29,650 --> 00:22:32,440 >> DAVID MALAN: Ikke gjort, fordi selvfølgelig er der et skridt tilbage. 570 00:22:32,440 --> 00:22:35,720 Men igen, grunden jeg bruger dette jargon som "tilbage i dit sind," 571 00:22:35,720 --> 00:22:37,160 det er fordi det er virkelig hvad der sker. 572 00:22:37,160 --> 00:22:39,610 Vi går igennem alle disse trin, men vi er en slags pause efter en 573 00:22:39,610 --> 00:22:42,480 øjeblik, dykning dybere ind i algoritme, pause et øjeblik, 574 00:22:42,480 --> 00:22:45,840 dykning dybere ind i algoritmen, og nu er vi nødt til at sortere i tilbagespoling i vores 575 00:22:45,840 --> 00:22:49,430 sind og fortryde alle disse lag at vi har slags sat på hold. 576 00:22:49,430 --> 00:22:51,790 >> Så nu har vi to lister over str. 4. 577 00:22:51,790 --> 00:22:54,790 Hvis du fyre kunne stå op en sidste gang og gøre lidt plads her 578 00:22:54,790 --> 00:22:57,230 gøre det klart, at dette er den venstre halvdelen af ​​den oprindelige, den 579 00:22:57,230 --> 00:22:58,620 højre halvdel af originalen. 580 00:22:58,620 --> 00:23:01,060 Hvem er det første nummer, som vi nødt til at trække ind 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 sætter Michelle her. 583 00:23:03,230 --> 00:23:05,080 Og hvem har nummer 2? 584 00:23:05,080 --> 00:23:06,440 Nummer 2 kommer tilbage samt. 585 00:23:06,440 --> 00:23:07,800 Nummer 3? 586 00:23:07,800 --> 00:23:08,510 Excellent. 587 00:23:08,510 --> 00:23:16,570 Nummer 4, nummer 5, nummer 6, nummer 7, og nummer 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, så det følte ligesom en masse af trin. sikker 589 00:23:18,850 --> 00:23:22,390 Men lad os nu se, om vi ikke kan bekræfte slags intuitivt at dette 590 00:23:22,390 --> 00:23:26,190 algoritme fundamentalt, især da n bliver rigtig stort, som vi har set 591 00:23:26,190 --> 00:23:29,170 med animationer, er fundamentalt hurtigere. 592 00:23:29,170 --> 00:23:33,400 Så jeg hævder denne algoritme i værste sag og selv i bedste fald, 593 00:23:33,400 --> 00:23:36,160 er stort O n gange log n. 594 00:23:36,160 --> 00:23:39,160 Det vil sige, at der er nogle aspekter af dette algoritme, der tager n trin, men 595 00:23:39,160 --> 00:23:43,110 Der er et andet aspekt et sted i at iteration at looping, der 596 00:23:43,110 --> 00:23:44,410 tager log n trin. 597 00:23:44,410 --> 00:23:49,154 Kan vi sætte fingeren på, hvad de to tal taler om? 598 00:23:49,154 --> 00:23:51,320 Tja, hvor - 599 00:23:51,320 --> 00:23:54,160 Hvor blev mikrofonen hen? 600 00:23:54,160 --> 00:23:58,660 >> SPEAKER 1: Ville log n være bryde os op i to - 601 00:23:58,660 --> 00:23:59,630 dividere med to, hovedsagelig. 602 00:23:59,630 --> 00:24:00,120 >> DAVID MALAN: Præcis. 603 00:24:00,120 --> 00:24:03,000 Helst ser vi i enhver algoritme dermed langt, har der været dette mønster af 604 00:24:03,000 --> 00:24:04,200 dividere, dividere, dividere. 605 00:24:04,200 --> 00:24:05,700 Og det er typisk reduceret til noget, der er 606 00:24:05,700 --> 00:24:07,100 logaritmisk, log basis 2. 607 00:24:07,100 --> 00:24:10,180 Men det kunne virkelig være noget, men log base 2. 608 00:24:10,180 --> 00:24:11,330 >> Nu hvad n? 609 00:24:11,330 --> 00:24:14,550 Jeg kan se, at vi slags delt dig fyre - delt dig, delt dig, 610 00:24:14,550 --> 00:24:15,910 delt dig, delt dig. 611 00:24:15,910 --> 00:24:18,760 Hvor kommer enden komme fra? 612 00:24:18,760 --> 00:24:19,810 >> Så det er de fusionerende. 613 00:24:19,810 --> 00:24:20,610 Fordi tænke over det. 614 00:24:20,610 --> 00:24:25,420 Når du fletter otte mennesker sammen, hvorved halvdelen af ​​dem er et sæt af fire 615 00:24:25,420 --> 00:24:27,770 og den anden halvdel er en anden sæt af fire, hvordan kan du gå 616 00:24:27,770 --> 00:24:28,820 om at gøre de fusionerende? 617 00:24:28,820 --> 00:24:30,830 Nå, du fyre gjorde det forholdsvis intuitivt. 618 00:24:30,830 --> 00:24:34,140 >> Men hvis jeg i stedet gjorde det lidt mere metodisk, jeg måske har peget på 619 00:24:34,140 --> 00:24:38,090 længst til venstre person først med min venstre hånd, pegede på den yderste venstre persons 620 00:24:38,090 --> 00:24:42,080 af det halve med min højre hånd, og bare efterfølgende gik gennem 621 00:24:42,080 --> 00:24:46,990 liste, der peger på det mindste element hver gang, flytte min finger over og 622 00:24:46,990 --> 00:24:48,970 løbet efter behov i listen. 623 00:24:48,970 --> 00:24:51,890 Men hvad er nøglen om dette fusionerende proces er jeg sammenligne disse par 624 00:24:51,890 --> 00:24:53,460 elementer. 625 00:24:53,460 --> 00:24:57,270 Fra den højre halvdel og fra venstre halvdelen, jeg aldrig når tilbageskridt. 626 00:24:57,270 --> 00:25:00,570 >> Så sammenfletningen selv tager ikke mere end n trin. 627 00:25:00,570 --> 00:25:03,250 Og hvor mange gange har jeg har at gøre det fusionerende? 628 00:25:03,250 --> 00:25:07,150 Nå, ikke mere end n, og vi bare så, at med den endelige fusionere. 629 00:25:07,150 --> 00:25:13,120 Og så hvis du gør noget, der tager log n trin n gange, eller omvendt, 630 00:25:13,120 --> 00:25:15,210 det kommer til at give os n gange log n. 631 00:25:15,210 --> 00:25:16,310 >> Og hvorfor er det bedre? 632 00:25:16,310 --> 00:25:19,600 Tja, hvis vi allerede ved, at log n er bedre end n - right? 633 00:25:19,600 --> 00:25:22,590 Vi så i binær søgning, telefonbogen Eksempelvis var log n absolut 634 00:25:22,590 --> 00:25:23,760 bedre end lineær. 635 00:25:23,760 --> 00:25:28,420 Så det betyder n gange log n er absolut bedre end n gange en anden 636 00:25:28,420 --> 00:25:30,390 n, AKA n potens. 637 00:25:30,390 --> 00:25:32,400 Og det er, hvad vi i sidste ende føler. 638 00:25:32,400 --> 00:25:34,928 >> Så stor runde af bifald, hvis vi kunne, for disse fyre. 639 00:25:34,928 --> 00:25:38,920 >> [Applaus] 640 00:25:38,920 --> 00:25:41,550 >> DAVID MALAN: Og jeres afskedsord gaver - kan du holde antallet, 641 00:25:41,550 --> 00:25:44,010 hvis du gerne vil. 642 00:25:44,010 --> 00:25:45,620 Og din afskedsgave, som sædvanlig. 643 00:25:45,620 --> 00:25:47,290 Åh, og vi vil sende dig optagelserne, Michelle. 644 00:25:47,290 --> 00:25:48,343 Tak. 645 00:25:48,343 --> 00:25:49,250 Ok. 646 00:25:49,250 --> 00:25:50,400 Hjælp dig selv til en stress bold. 647 00:25:50,400 --> 00:25:54,110 >> Og lad mig trække op i mellemtiden, vores ven Rob Bowden at tilbyde 648 00:25:54,110 --> 00:25:59,520 noget anderledes perspektiv på dette, da du kan tænke om disse 649 00:25:59,520 --> 00:26:01,280 trin sker i en noget anderledes måde. 650 00:26:01,280 --> 00:26:04,750 Faktisk set-up for, hvad Rob handler om at vise os antager, at vi har 651 00:26:04,750 --> 00:26:09,030 allerede gjort opdeling af stor liste i otte små lister 652 00:26:09,030 --> 00:26:10,570 hver af størrelse 1. 653 00:26:10,570 --> 00:26:13,350 >> Så vi ændrer pseudokoden en lidt bare for at sortere i komme på 654 00:26:13,350 --> 00:26:15,320 centrale idé om, hvordan de fusionerende værker. 655 00:26:15,320 --> 00:26:17,600 Men køretiden for hvad han er ved at gøre, er stadig 656 00:26:17,600 --> 00:26:19,110 vil være den samme. 657 00:26:19,110 --> 00:26:23,540 Og igen, set-up er, at han er begyndt med otte lister over størrelse 1. 658 00:26:23,540 --> 00:26:27,730 Så du har savnet den del, hvor han er faktisk gjort log n, log n, log n 659 00:26:27,730 --> 00:26:31,205 dividere af input. 660 00:26:31,205 --> 00:26:32,120 >> [VIDEO AFSPIL] 661 00:26:32,120 --> 00:26:33,615 >> -Det er det for trin et. 662 00:26:33,615 --> 00:26:38,270 For trin to, gentagne gange fusionere par lister. 663 00:26:38,270 --> 00:26:39,210 >> DAVID MALAN: Hm. 664 00:26:39,210 --> 00:26:41,270 Kun lyd kommer ud af min computer. 665 00:26:41,270 --> 00:26:42,520 Lad os prøve det igen. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Just vilkårligt vælge hvilken - nu har vi fire lister. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Lær før. 670 00:26:52,120 --> 00:26:53,040 >> DAVID MALAN: Der går vi. 671 00:26:53,040 --> 00:27:00,510 >> -Fletning 108 og 15, vi ender op med listen 15, 108. 672 00:27:00,510 --> 00:27:07,170 Fletning 50 og 4, vi ender med 4, 50. 673 00:27:07,170 --> 00:27:12,990 Fletning 8 og 42, vi ender med 8, 42. 674 00:27:12,990 --> 00:27:19,970 Og sammenlægning 23 og 16 vi ender med 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Nu er alle vores lister er af størrelse 2. 676 00:27:23,270 --> 00:27:26,690 Bemærk, at hver af de fire lister er sorteret. 677 00:27:26,690 --> 00:27:29,450 Så vi kan begynde at fusionere par lister igen. 678 00:27:29,450 --> 00:27:38,420 Fletning 15 og 108 og 4 og 50, vi først tage 4 og derefter 15, derefter 679 00:27:38,420 --> 00:27:41,500 50, så de 108. 680 00:27:41,500 --> 00:27:50,610 Fletning 8, 42 og 16, 23, vi først tage den 8., derefter 16, derefter 23, 681 00:27:50,610 --> 00:27:52,700 derefter 42.. 682 00:27:52,700 --> 00:27:57,600 >> Så nu har vi kun to lister over størrelsen 4 er hver især sorteret. 683 00:27:57,600 --> 00:28:01,170 Så nu er vi flette disse to lister. 684 00:28:01,170 --> 00:28:11,835 Først tager vi de 4, så vi tager 8, så tager vi de 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 VIDEOAFSPILNING] 687 00:28:19,872 --> 00:28:23,430 >> DAVID MALAN: Igen, varsel, han aldrig rørt en given kop mere end én gang 688 00:28:23,430 --> 00:28:24,860 efter at fremme ud over det. 689 00:28:24,860 --> 00:28:26,200 Så han har aldrig gentage. 690 00:28:26,200 --> 00:28:29,850 Så han er altid at flytte til den side, og det er, hvor vi fik vores n. 691 00:28:29,850 --> 00:28:33,290 >> Hvorfor ikke lade mig trække op en animation at vi så tidligere, men denne gang 692 00:28:33,290 --> 00:28:35,110 kun at fokusere på merge slags. 693 00:28:35,110 --> 00:28:38,030 Lad mig gå videre og zoome ind på dette her. 694 00:28:38,030 --> 00:28:42,530 Først lad mig vælge en tilfældig indgang, forstørre det, og du kan sortere i se 695 00:28:42,530 --> 00:28:46,600 hvad vi tog for givet, tidligere, fusionere slags faktisk gør. 696 00:28:46,600 --> 00:28:50,330 >> Så bemærke, at du får disse halve eller disse kvartaler eller disse ottendedele af den 697 00:28:50,330 --> 00:28:53,140 problem, at alle pludselig begynde at tage god form. 698 00:28:53,140 --> 00:28:57,070 Og så endelig, kan du se på allersidst, at bam, 699 00:28:57,070 --> 00:28:58,860 alt er slået sammen. 700 00:28:58,860 --> 00:29:01,690 >> Så disse er blot tre forskellige tager på den samme idé. 701 00:29:01,690 --> 00:29:05,980 Men nøglen indsigt, ligesom kløft og erobre i den allerførste klasse, 702 00:29:05,980 --> 00:29:10,640 var, at vi besluttede at en eller anden måde opdele problemet til noget stort, ind 703 00:29:10,640 --> 00:29:14,760 noget slags identiske i ånden, 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 >> Nu er en anden sjov måde at sortere i tænke om disse, det, selvom det ikke 706 00:29:18,420 --> 00:29:20,520 kommer til at give dig den samme intuitive forståelse, er 707 00:29:20,520 --> 00:29:21,640 Følgende animation. 708 00:29:21,640 --> 00:29:25,400 Så dette er en video nogen sætte sammen der er knyttet forskellige 709 00:29:25,400 --> 00:29:29,970 lyde med de forskellige operationer for indsættelse sortere, for merge 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 øjeblik, jeg kommer til at ramme Play. 712 00:29:32,330 --> 00:29:33,600 Det handler om et minut lang. 713 00:29:33,600 --> 00:29:37,410 Og selvom du kan stadig se mønstre sker, denne gang kan du 714 00:29:37,410 --> 00:29:41,420 også høre, hvordan disse algoritmer er udfører forskelligt og med 715 00:29:41,420 --> 00:29:43,950 noget forskellige mønstre. 716 00:29:43,950 --> 00:29:45,830 >> Dette er indsættelse slags. 717 00:29:45,830 --> 00:29:50,400 >> [TONER AFSPILNING] 718 00:29:50,400 --> 00:29:52,400 >> DAVID MALAN: Det igen forsøger at indsætte hvert element 719 00:29:52,400 --> 00:29:52,900 i, hvor det hører hjemme. 720 00:29:52,900 --> 00:29:54,628 Dette er boble slags. 721 00:29:54,628 --> 00:30:10,097 >> [TONER AFSPILNING] 722 00:30:10,097 --> 00:30:13,630 >> DAVID MALAN: Og du kan sortere i føler hvor relativt lidt arbejde det laver 723 00:30:13,630 --> 00:30:15,834 på hvert trin. 724 00:30:15,834 --> 00:30:20,470 Dette er, hvad tediousness lyder. 725 00:30:20,470 --> 00:30:21,472 >> [TONER AFSPILNING] 726 00:30:21,472 --> 00:30:25,222 >> DAVID MALAN: Dette er valg sortere, hvor vi vælger det element, vi ønsker, ved 727 00:30:25,222 --> 00:30:28,845 gå igennem igen og igen og igen og sætte det i begyndelsen. 728 00:30:28,845 --> 00:30:37,674 >> [TONER AFSPILNING] 729 00:30:37,674 --> 00:30:43,970 >> DAVID MALAN: Dette er flette sortere, hvilket kan du virkelig begynde at føle. 730 00:30:43,970 --> 00:30:51,810 >> [TONER AFSPILNING] 731 00:30:51,810 --> 00:30:54,770 >> [Latter] 732 00:30:54,770 --> 00:30:58,395 >> DAVID MALAN: Noget, der hedder gnome sortere, som vi ikke har kigget på. 733 00:30:58,395 --> 00:31:13,630 >> [TONER AFSPILNING] 734 00:31:13,630 --> 00:31:17,910 >> DAVID MALAN: Så lad mig nu se, distraheret som du forhåbentlig er ved 735 00:31:17,910 --> 00:31:21,110 musik, hvis jeg kan smutte lidt bit math her. 736 00:31:21,110 --> 00:31:24,850 Så der er en fjerde måde at vi kan tænke over, hvad det betyder, at disse 737 00:31:24,850 --> 00:31:29,210 funktioner til at være hurtigere end dem at vi har set før. 738 00:31:29,210 --> 00:31:32,470 Og hvis du kommer på kurset fra en matematik baggrund, du 739 00:31:32,470 --> 00:31:36,030 faktisk kender måske allerede, at du kan smække en periode på denne teknik - 740 00:31:36,030 --> 00:31:40,400 nemlig rekursion, en funktion der på en måde kalder sig. 741 00:31:40,400 --> 00:31:44,780 >> Og igen, minde om, at merge sortere pseudokode var rekursive i den forstand 742 00:31:44,780 --> 00:31:48,460 at en af ​​merge sortere taget skridt var at kalde slags - 743 00:31:48,460 --> 00:31:49,740 det er, selv. 744 00:31:49,740 --> 00:31:52,480 Men heldigvis, fordi vi holdt ringer sortere, eller flette sortere, 745 00:31:52,480 --> 00:31:55,880 specifikt på en mindre og mindre og mindre liste, vi i sidste ende 746 00:31:55,880 --> 00:32:00,005 bundede takket være det, vi vil kalde en base tilfælde hard-coded sag, 747 00:32:00,005 --> 00:32:04,270 sagde, at hvis listen er lille, mindre end 2 i så fald vende tilbage lige med det samme. 748 00:32:04,270 --> 00:32:07,550 Hvis vi ikke havde denne særlige tilfælde algoritme ville aldrig bunden, 749 00:32:07,550 --> 00:32:11,010 og du ville faktisk komme ind i en uendelig løkke virkelig evigt. 750 00:32:11,010 --> 00:32:14,330 >> Men formoder, at vi ønskede at nu sætte nogle numre på denne igen, ved hjælp af n 751 00:32:14,330 --> 00:32:15,660 som størrelsen af ​​input. 752 00:32:15,660 --> 00:32:18,680 Og jeg ville gerne spørge dig, hvad er den samlede tid involveret i 753 00:32:18,680 --> 00:32:19,800 kører merge slags? 754 00:32:19,800 --> 00:32:22,960 Eller mere generelt, hvad er omkostningerne ved det i tide? 755 00:32:22,960 --> 00:32:24,730 >> Jamen det er ret nemt at måle det. 756 00:32:24,730 --> 00:32:29,010 Hvis n er mindre end 2, hvor lang tid sagen 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 vende tilbage. 759 00:32:31,410 --> 00:32:32,510 Der er ikke noget arbejde, der skal gøres. 760 00:32:32,510 --> 00:32:35,660 Nu velsagtens, måske er det et skridt eller to skridt til at finde ud af mængden af 761 00:32:35,660 --> 00:32:38,420 arbejde, men det er tæt nok på 0, at Jeg skal bare sige nej arbejde 762 00:32:38,420 --> 00:32:40,940 påkrævet, hvis listen er så lille at være uinteressant. 763 00:32:40,940 --> 00:32:42,580 >> Men denne sag er interessant. 764 00:32:42,580 --> 00:32:47,320 Den rekursive tilfælde var den gren af pseudokoden der sagde andet, sortere 765 00:32:47,320 --> 00:32:52,000 den venstre halvdel, sortere højre halvdelen, flette de to halvdele. 766 00:32:52,000 --> 00:32:55,530 Nu hvorfor dette udtryk repræsenterer denne udgift? 767 00:32:55,530 --> 00:32:58,690 Nå, T n betyder bare tid til at sortere n elementer. 768 00:32:58,690 --> 00:33:03,070 Og derefter på den højre side af lighedstegn der, T n delte 769 00:33:03,070 --> 00:33:06,600 med 2 hentyder til udgifterne til hvad? 770 00:33:06,600 --> 00:33:07,570 Sortering den venstre halvdel. 771 00:33:07,570 --> 00:33:10,990 Den anden T fra n divideret med 2 er antages at referere til omkostningerne til 772 00:33:10,990 --> 00:33:12,390 sortere højre halvdel. 773 00:33:12,390 --> 00:33:14,590 >> Og så plus n? 774 00:33:14,590 --> 00:33:15,420 Er sammenlægning. 775 00:33:15,420 --> 00:33:19,120 Fordi hvis du har to lister, en af size n over 2 og en anden af ​​størrelse n 776 00:33:19,120 --> 00:33:22,580 over 2, er du nødt til hovedsageligt berøre hver af disse bestanddele, ligesom Rob 777 00:33:22,580 --> 00:33:24,990 rørte hver af kopper, og bare som vi pegede på hvert af 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 på bekostning af sammenlægning. 780 00:33:28,790 --> 00:33:31,780 >> Nu desværre denne formel er også selv rekursiv. 781 00:33:31,780 --> 00:33:36,390 Så hvis stillede spørgsmålet, hvis n er, siger, 16. Hvis der er 16 personer på scenen 782 00:33:36,390 --> 00:33:40,670 eller 16 kopper i videoen, hvor mange i alt skridt tager det at sortere dem 783 00:33:40,670 --> 00:33:41,550 med merge slags? 784 00:33:41,550 --> 00:33:45,790 Det er faktisk ikke et indlysende svar, fordi du nu nødt til at sortere i 785 00:33:45,790 --> 00:33:48,500 rekursivt besvare denne formel. 786 00:33:48,500 --> 00:33:51,190 >> Men det er OK, fordi lad mig foreslå at vi gør følgende. 787 00:33:51,190 --> 00:33:56,670 Den tid, der til at sortere 16 personer eller 16 kopper vil være repræsenteret 788 00:33:56,670 --> 00:33:58,020 generelt som T 16. 789 00:33:58,020 --> 00:34:01,400 Men der er lig med, i henhold til vores foregående formel, 2 gange den mængde 790 00:34:01,400 --> 00:34:04,780 tid det tager at sortere 8 kopper plus 16. 791 00:34:04,780 --> 00:34:08,590 Og igen, plus 16 er det tid til at fusionere, og to gange T på 8 er 792 00:34:08,590 --> 00:34:10,790 tid til at sortere venstre halvdel og højre halvdel. 793 00:34:10,790 --> 00:34:11,989 >> Men igen, det er ikke nok. 794 00:34:11,989 --> 00:34:13,210 Vi er nødt til at dykke dybere. 795 00:34:13,210 --> 00:34:16,409 Det betyder, at vi er nødt til at besvare spørgsmål, hvad er T på 8? 796 00:34:16,409 --> 00:34:19,610 Nå T på 8 er blot 2 gange T på 4 plus 8. 797 00:34:19,610 --> 00:34:20,520 Jamen, hvad er T på 4? 798 00:34:20,520 --> 00:34:23,780 T på 4 er kun 2 gange T på 2 plus 4. 799 00:34:23,780 --> 00:34:25,489 Jamen, hvad er T af 2? 800 00:34:25,489 --> 00:34:29,030 T på 2 er kun 2 gange T på 1 plus 2. 801 00:34:29,030 --> 00:34:31,940 >> Og igen, vi er sådan at få fast i denne cyklus. 802 00:34:31,940 --> 00:34:34,790 Men det handler om at ramme såkaldt base case. 803 00:34:34,790 --> 00:34:37,310 For hvad er T på 1, vi hævder? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Så nu endelig kan vi arbejde baglæns. 806 00:34:39,730 --> 00:34:44,290 >> Hvis T på 1 er 0, kan jeg nu gå tilbage op en Line til denne fyr her, og jeg kan 807 00:34:44,290 --> 00:34:46,330 plug in 0 for T 1.. 808 00:34:46,330 --> 00:34:51,770 Så det betyder, at det er lig med 2 gange nul, ellers kendt som 0, plus 2. 809 00:34:51,770 --> 00:34:53,739 Og så hele udtrykket er 2.. 810 00:34:53,739 --> 00:34:58,740 >> Hvis jeg nu tager T på 2, hvis svar er 2, sæt det i den midterste linie, T 811 00:34:58,740 --> 00:35:02,740 af 4, giver det mig 2 gange 2 plus 4, så 8. 812 00:35:02,740 --> 00:35:07,080 Hvis jeg derefter sætte i 8 til den forrige linje, der giver mig 2 gange 8, 16. 813 00:35:07,080 --> 00:35:12,470 Og hvis vi derefter fortsætte at med 24, tilføjer i 16, vi endelig får en 814 00:35:12,470 --> 00:35:13,820 værdi af 64. 815 00:35:13,820 --> 00:35:18,480 >> Nu, i sig selv slags taler intet til n notation, den 816 00:35:18,480 --> 00:35:20,700 big O, omega, at vi har talt om. 817 00:35:20,700 --> 00:35:24,890 Men det viser sig, at 64 er faktisk 16, størrelsen af ​​input, 818 00:35:24,890 --> 00:35:27,110 log base 2 af 16 år. 819 00:35:27,110 --> 00:35:30,200 Og hvis dette er en lille ukendt, bare tænke tilbage, og det vil komme tilbage 820 00:35:30,200 --> 00:35:30,700 til dig sidst. 821 00:35:30,700 --> 00:35:33,775 Hvis dette er log base 2, det er ligesom 2 hævet til hvad der giver dig 16? 822 00:35:33,775 --> 00:35:36,380 Åh, det er 4, så det er 16 gange 4. 823 00:35:36,380 --> 00:35:39,380 >> Og igen, det er ikke en big deal, hvis det er en slags tåget hukommelse nu. 824 00:35:39,380 --> 00:35:43,720 Men for nu, tage på tro at 16 log 16 er 64. 825 00:35:43,720 --> 00:35:46,590 Og så ja, med denne enkle tilregnelighed tjek, vi har bekræftet - 826 00:35:46,590 --> 00:35:48,250 men ikke bevist formelt - 827 00:35:48,250 --> 00:35:52,800 at køretiden for merge sortere er faktisk n log n. 828 00:35:52,800 --> 00:35:53,790 >> Så ikke dårligt. 829 00:35:53,790 --> 00:35:57,260 Det er helt sikkert bedre end den algoritmer, vi har set hidtil, og 830 00:35:57,260 --> 00:36:00,710 Det er fordi vi har gearede, en, en teknik, der kaldes rekursion. 831 00:36:00,710 --> 00:36:03,880 Men mere interessant end det, der begrebet dividere og erobre. 832 00:36:03,880 --> 00:36:07,460 Igen, virkelig uge 0 ting, selv nu er tilbagevendende i en 833 00:36:07,460 --> 00:36:08,740 mere overbevisende måde. 834 00:36:08,740 --> 00:36:11,750 >> Nu er en sjov lille øvelse, hvis du har aldrig gjort det - og du sandsynligvis 835 00:36:11,750 --> 00:36:14,660 ville ikke have, fordi slags normal folk tror ikke at gøre dette. 836 00:36:14,660 --> 00:36:20,650 Men hvis jeg går til google.com, og hvis Jeg ønsker at lære noget om 837 00:36:20,650 --> 00:36:22,356 rekursion 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 [Mere latter] 841 00:36:32,030 --> 00:36:33,385 DAVID MALAN: Bad joke langsomt breder sig. 842 00:36:33,385 --> 00:36:34,450 [Latter] 843 00:36:34,450 --> 00:36:36,970 DAVID MALAN: Just in case, det er der. 844 00:36:36,970 --> 00:36:38,710 Jeg havde ikke stave det forkert, og der er joke. 845 00:36:38,710 --> 00:36:40,810 Ok. 846 00:36:40,810 --> 00:36:42,950 Forklar det til mennesker ud for dig, hvis Det har ikke helt klikket endnu. 847 00:36:42,950 --> 00:36:47,650 Men rekursion, mere generelt, henvises til processen for en funktion ringer 848 00:36:47,650 --> 00:36:51,430 selv, eller mere generelt, dividere en problem til noget, der kan være 849 00:36:51,430 --> 00:36:56,220 løst stykkevis ved at løse identiske repræsentative problemer. 850 00:36:56,220 --> 00:36:58,400 >> Nå, lad os skifte gear for bare et øjeblik. 851 00:36:58,400 --> 00:37:00,840 Vi vil gerne slutte på visse cliffhangers, så lad os begynde at sætte 852 00:37:00,840 --> 00:37:05,870 scenen, i flere minutter, på en meget enkel idé - 853 00:37:05,870 --> 00:37:07,620 der at bytte to elementer, right? 854 00:37:07,620 --> 00:37:10,040 Alle disse algoritmer vi har været taler om de sidste par 855 00:37:10,040 --> 00:37:12,420 foredrag indebærer en vis slags swapping. 856 00:37:12,420 --> 00:37:14,630 Dag blev visualiseret ved dem at få op af deres stole og 857 00:37:14,630 --> 00:37:18,570 gå rundt, men i koden, ville vi bare tage et element fra en matrix 858 00:37:18,570 --> 00:37:20,370 og plop det i en anden. 859 00:37:20,370 --> 00:37:21,880 >> Så hvordan kan vi gå om at gøre dette? 860 00:37:21,880 --> 00:37:24,850 Nå, lad mig gå videre og skrive en hurtig program her. 861 00:37:24,850 --> 00:37:31,600 Jeg har tænkt mig at gå videre og gøre dette som følgende. 862 00:37:31,600 --> 00:37:33,910 Lad os kalde det - 863 00:37:33,910 --> 00:37:38,070 Hvad ønsker vi at kalde denne ene? 864 00:37:38,070 --> 00:37:38,650 >> Faktisk, nej. 865 00:37:38,650 --> 00:37:39,420 Lad mig spole tilbage. 866 00:37:39,420 --> 00:37:41,220 Jeg ønsker ikke at gøre det cliffhanger endnu. 867 00:37:41,220 --> 00:37:42,270 Det vil ødelægge det sjove. 868 00:37:42,270 --> 00:37:43,600 Lad os gøre det i stedet. 869 00:37:43,600 --> 00:37:47,430 >> Antag, at jeg vil skrive lidt program, og at det nu omfatter det 870 00:37:47,430 --> 00:37:48,700 idé rekursion. 871 00:37:48,700 --> 00:37:50,370 Jeg slags fik forud for mig der. 872 00:37:50,370 --> 00:37:51,420 Jeg har tænkt mig at gøre følgende. 873 00:37:51,420 --> 00:38:00,220 >> Først en hurtig omfatter i standard io.h, samt en include af cs50.h. 874 00:38:00,220 --> 00:38:03,200 Og så jeg har tænkt mig at gå videre og erklære int main void 875 00:38:03,200 --> 00:38:04,360 på sædvanlig måde. 876 00:38:04,360 --> 00:38:07,920 Jeg indså, at jeg har misnamed filen, så lad mig lige tilføje et. c udvidelse her, så 877 00:38:07,920 --> 00:38:09,510 at vi kan kompilere det ordentligt. 878 00:38:09,510 --> 00:38:10,970 Start denne funktion fra. 879 00:38:10,970 --> 00:38:13,290 >> Og den funktion jeg vil skrive, helt enkelt, er en, der spørger 880 00:38:13,290 --> 00:38:16,210 brugeren for en række, og derefter tilføjer op alle de numre mellem denne 881 00:38:16,210 --> 00:38:19,920 nummer og, siger, 0. 882 00:38:19,920 --> 00:38:22,510 Så først vil jeg tænkt mig at gå videre og erklærer, int n. 883 00:38:22,510 --> 00:38:24,760 Så jeg kopiere noget kode, der Vi har brugt et stykke tid. 884 00:38:24,760 --> 00:38:26,660 Mens noget er sandt. 885 00:38:26,660 --> 00:38:28,000 Jeg kommer tilbage til om et øjeblik. 886 00:38:28,000 --> 00:38:29,010 >> Hvad ønsker jeg at gøre? 887 00:38:29,010 --> 00:38:33,460 Jeg vil gerne sige printf positive integer venligst. 888 00:38:33,460 --> 00:38:36,130 Og så vil jeg sige n får få int. 889 00:38:36,130 --> 00:38:38,800 Så igen, nogle standardtekst kode at vi har brugt før. 890 00:38:38,800 --> 00:38:40,810 Og jeg har tænkt mig at gøre dette mens n er mindre end 1. 891 00:38:40,810 --> 00:38:44,120 Så dette vil sikre, at brugeren giver mig et positivt heltal. 892 00:38:44,120 --> 00:38:45,490 >> Og nu vil jeg gøre følgende. 893 00:38:45,490 --> 00:38:51,020 Jeg ønsker at tilføje op alle de numre mellem 1 og og n eller 0 og n, 894 00:38:51,020 --> 00:38:52,570 ækvivalent, for at få den totale sum. 895 00:38:52,570 --> 00:38:55,100 Så det store sigma symbolet som du måske husker. 896 00:38:55,100 --> 00:38:59,050 Så jeg har tænkt mig at gøre dette ved første kald en funktion kaldet sigma 897 00:38:59,050 --> 00:39:06,030 passerer den i n, og så vil jeg siger printf, er svaret lige der. 898 00:39:06,030 --> 00:39:08,180 >> Så kort sagt, jeg får, og int fra brugeren. 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 kaldet svar typen int og butik i det afkastet 901 00:39:12,700 --> 00:39:15,610 værdi af sigma, passerer i n som input. 902 00:39:15,610 --> 00:39:17,060 Og så kan jeg udskrive det svar. 903 00:39:17,060 --> 00:39:19,550 >> Desværre, selvom sigma lyde som noget, der kan være i 904 00:39:19,550 --> 00:39:24,040 Den math.h filen 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 gennemføre denne selv. 907 00:39:26,170 --> 00:39:29,160 Jeg har tænkt mig at gennemføre en funktion kaldet sigma, og det kommer til at tage et 908 00:39:29,160 --> 00:39:29,900 parameter - 909 00:39:29,900 --> 00:39:32,100 lad os bare kalde det m, bare så det er anderledes. 910 00:39:32,100 --> 00:39:35,910 Og så op her, vil jeg sige, Tja, hvis m er mindre end 1 - dette er en 911 00:39:35,910 --> 00:39:38,180 meget uinteressant program. 912 00:39:38,180 --> 00:39:41,700 Så jeg har tænkt mig at gå videre og øjeblikkeligt returnere 0. 913 00:39:41,700 --> 00:39:45,920 Det bare ikke giver mening at tilføje op alle tallene mellem 1 og m, hvis m 914 00:39:45,920 --> 00:39:48,470 er selv 0 eller negativ. 915 00:39:48,470 --> 00:39:50,900 >> Og så jeg har tænkt mig at gå videre og gøre det meget iterativt. 916 00:39:50,900 --> 00:39:53,090 Jeg har tænkt mig at gøre denne form for old-school, og jeg har tænkt mig at gå videre 917 00:39:53,090 --> 00:39:57,150 og sige, at jeg har tænkt mig at erklære en sum til at være 0. 918 00:39:57,150 --> 00:39:59,630 Så jeg har tænkt mig at have en for-løkke af int - 919 00:39:59,630 --> 00:40:02,820 og lad mig gøre det til at matche vores fordeling kode, så du har en kopi 920 00:40:02,820 --> 00:40:07,500 derhjemme. int i får 1 på op til i er mindre end eller lig med ca. 921 00:40:07,500 --> 00:40:09,430 Jeg plus plus. 922 00:40:09,430 --> 00:40:11,430 Og så på indersiden af ​​dette for loop - 923 00:40:11,430 --> 00:40:12,440 Vi er der næsten - 924 00:40:12,440 --> 00:40:15,810 sum får sum plus 1. 925 00:40:15,810 --> 00:40:17,670 Og så jeg har tænkt mig at returnere beløbet. 926 00:40:17,670 --> 00:40:19,420 >> Så jeg gjorde det hurtigt, ganske ganske. 927 00:40:19,420 --> 00:40:22,775 Men igen, hvis hovedfunktion er temmelig ligetil, er baseret på kode, vi har 928 00:40:22,775 --> 00:40:23,190 skrevet hidtil. 929 00:40:23,190 --> 00:40:25,610 Bruger den dobbelte loop til at få en positiv int fra brugeren. 930 00:40:25,610 --> 00:40:29,870 Jeg så videregive denne int til en ny funktion kaldet sigma, kalder det, igen, n. 931 00:40:29,870 --> 00:40:33,100 Og jeg gemmer returværdien, svaret fra den sorte boks i øjeblikket 932 00:40:33,100 --> 00:40:35,460 kendt som sigma, i en variabel kaldet svar. 933 00:40:35,460 --> 00:40:36,580 Så jeg udskrive det. 934 00:40:36,580 --> 00:40:39,090 >> Hvis vi nu fortsætte historien, hvordan sigma gennemført? 935 00:40:39,090 --> 00:40:40,840 Jeg foreslår at gennemføre som følger. 936 00:40:40,840 --> 00:40:43,560 Først en lille smule af fejlkontrol for at sikre, at brugeren ikke er 937 00:40:43,560 --> 00:40:46,480 rode med mig og passerer nogle negative eller 0 værdi. 938 00:40:46,480 --> 00:40:49,710 Så jeg erklære en kaldet variabel opsummere og sæt den til 0. 939 00:40:49,710 --> 00:40:55,910 >> Og nu begynder jeg at flytte fra jeg lig 1 hele vejen op til og med m, 940 00:40:55,910 --> 00:41:00,130 fordi jeg ønsker at medtage alle de tal fra en gennem m, inklusive. 941 00:41:00,130 --> 00:41:04,350 Og inde i dette for loop, jeg bare gøre sum får hvad det nu er, plus 942 00:41:04,350 --> 00:41:08,900 værdi af i. 943 00:41:08,900 --> 00:41:10,370 Plus værdien af ​​jeg. 944 00:41:10,370 --> 00:41:14,090 >> Som en sidebemærkning, hvis du ikke har set det før, er der nogle syntaktiske sukker 945 00:41:14,090 --> 00:41:14,870 for denne linje. 946 00:41:14,870 --> 00:41:21,120 Jeg kan omskrive dette som plus lig i, bare for at spare mig selv et par tastetryk 947 00:41:21,120 --> 00:41:22,570 og til at se en smule kø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 funktionelt det samme. 950 00:41:24,660 --> 00:41:26,710 >> Desværre denne kode er ikke kommer til at kompilere endnu. 951 00:41:26,710 --> 00:41:31,600 Hvis jeg kører gør sigma 0, hvordan am Jeg kommer til at få råbte på? 952 00:41:31,600 --> 00:41:33,473 Hvad går det ikke at lide? 953 00:41:33,473 --> 00:41:35,740 >> PUBLIKUM: [uhørlig]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID MALAN: Ja, havde jeg ikke erklære funktionen op øverst, right? 955 00:41:37,800 --> 00:41:40,590 C er en slags dum, at den kun gør hvad du fortæller det til at gøre, og du 956 00:41:40,590 --> 00:41:41,880 nødt til at gøre det i den rækkefølge. 957 00:41:41,880 --> 00:41:45,910 Og så hvis jeg ramte Skriv her, vil jeg får en advarsel om sigma implicit 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å op til toppen, og jeg kan sige, okay, vent et øjeblik. 961 00:41:50,370 --> 00:41:54,240 Sigma er en funktion, der 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 sætte hele funktionen over main, men i almindelighed, ville jeg 964 00:41:59,550 --> 00:42:02,260 anbefale mod det, fordi det er rart altid at have main øverst, så 965 00:42:02,260 --> 00:42:06,310 du kan dykke lige ind og vide, hvad en Programmet laver ved at læse main først. 966 00:42:06,310 --> 00:42:07,930 >> Så lad mig rydde skærmen. 967 00:42:07,930 --> 00:42:09,330 Remake sigma 0. 968 00:42:09,330 --> 00:42:10,340 Alt ser ud til at tjekke ud. 969 00:42:10,340 --> 00:42:11,970 Lad mig køre sigma 0. 970 00:42:11,970 --> 00:42:12,770 Positiv indbyrdes. 971 00:42:12,770 --> 00:42:15,580 Jeg vil give det et nummer 3 for at holde det simpelt. 972 00:42:15,580 --> 00:42:18,710 Så det skulle give mig 3 plus 2 plus 1, så 6.. 973 00:42:18,710 --> 00:42:20,750 Indtast, og faktisk får jeg 6. 974 00:42:20,750 --> 00:42:21,820 >> Jeg kan gøre noget større - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Ligesom en tangent, jeg kommer til at gøre noget latterligt som en virkelig stor 977 00:42:27,690 --> 00:42:30,375 nummer, Åh, der faktisk arbejdede ud - 978 00:42:30,375 --> 00:42:31,600 eh, tror jeg ikke, det er rigtigt. 979 00:42:31,600 --> 00:42:32,810 Lad os se. 980 00:42:32,810 --> 00:42:34,060 Lad os virkelig rodet 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 Hvad sker der? 985 00:42:44,970 --> 00:42:46,050 Koden er ikke så slemt. 986 00:42:46,050 --> 00:42:48,470 Det er stadig lineær. 987 00:42:48,470 --> 00:42:50,810 Whistling er en god effekt, selv om. 988 00:42:50,810 --> 00:42:52,060 Hvad sker der? 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 sig - og dette er som en sidebemærkning. 992 00:42:57,620 --> 00:42:59,400 Dette er ikke core til idé rekursion. 993 00:42:59,400 --> 00:43:02,480 Det viser sig, fordi jeg forsøger at repræsenterer sådan et stort tal, de fleste 994 00:43:02,480 --> 00:43:06,980 sandsynligt er det at blive misforstået af C som en ikke positivt tal, 995 00:43:06,980 --> 00:43:09,980 men negativt tal. 996 00:43:09,980 --> 00:43:12,690 >> Vi har ikke talt om det, men det viser sig at der er negative tal 997 00:43:12,690 --> 00:43:14,210 i verden desuden til positive tal. 998 00:43:14,210 --> 00:43:16,290 Og de midler, som du kan repræsentere et negativt tal 999 00:43:16,290 --> 00:43:19,530 det væsentlige, du bruger en særlig bit at angive 1000 00:43:19,530 --> 00:43:20,400 positive end negative. 1001 00:43:20,400 --> 00:43:22,950 Det er lidt mere kompliceret end som så, men det er den grundlæggende idé. 1002 00:43:22,950 --> 00:43:26,740 >> Så desværre hvis C er forvirrende én af disse bits som rent faktisk betyder, 1003 00:43:26,740 --> 00:43:30,790 Åh, det er et negativt tal, min loop her, for eksempel, er faktisk aldrig 1004 00:43:30,790 --> 00:43:31,740 vil afslutte. 1005 00:43:31,740 --> 00:43:33,850 Så hvis jeg var faktisk udskrivning noget igen og igen, 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 igen, dette er ud over punktet. 1008 00:43:36,220 --> 00:43:38,590 Dette er egentlig bare en slags intellektuelle nysgerrighed, som vi vil komme 1009 00:43:38,590 --> 00:43:39,550 tilbage til sidst. 1010 00:43:39,550 --> 00:43:43,400 Men for nu, er dette en korrekt implementering, hvis vi antager, at 1011 00:43:43,400 --> 00:43:45,970 Brugeren vil give int'er der passer inden int'er. 1012 00:43:45,970 --> 00:43:49,370 >> Men jeg hævder, at denne kode, helt ærligt, kunne gøres så meget mere simpelt. 1013 00:43:49,370 --> 00:43:54,060 Hvis målet ved hånden er at tage en række Ligesom m og tilføje op alle de 1014 00:43:54,060 --> 00:43:59,510 tal mellem det og 1, eller omvendt mellem 1 og det hævder jeg 1015 00:43:59,510 --> 00:44:03,380 at jeg kan låne denne idé at fusionere sortere havde, som tog et problem 1016 00:44:03,380 --> 00:44:05,660 af denne størrelse og dividere det til noget mindre. 1017 00:44:05,660 --> 00:44:09,875 Måske ikke halvt, men mindre, men repræsentativt den 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 faktisk - lad mig gemme denne fil med en anden version nummer. 1020 00:44:15,470 --> 00:44:17,670 Vi kalder denne udgave 1 i stedet for 0. 1021 00:44:17,670 --> 00:44:20,790 Og jeg hævder, at jeg rent faktisk kan reimplement dette i denne form for 1022 00:44:20,790 --> 00:44:22,160 hjernevridende måde. 1023 00:44:22,160 --> 00:44:23,710 >> Jeg har tænkt mig at lade en del af det alene. 1024 00:44:23,710 --> 00:44:27,710 Jeg har tænkt mig at sige, hvis m er mindre end eller endda lig med 0 - 1025 00:44:27,710 --> 00:44:29,280 Jeg skal bare være lidt mere anal denne gang 1026 00:44:29,280 --> 00:44:30,520 med min fejlkontrol - 1027 00:44:30,520 --> 00:44:33,190 Jeg har tænkt mig at 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 blot at beslutte, hvis brugeren giver mig et negativt tal, jeg er 1030 00:44:37,500 --> 00:44:41,490 returnere 0, og de bør have læst dokumentationen nærmere. 1031 00:44:41,490 --> 00:44:42,170 >> Else - 1032 00:44:42,170 --> 00:44:44,070 mærke til, hvad jeg har tænkt mig at gøre. 1033 00:44:44,070 --> 00:44:49,260 Else jeg kommer til at vende tilbage m plus - 1034 00:44:49,260 --> 00:44:51,010 hvad er sigma af m? 1035 00:44:51,010 --> 00:44:56,710 Nå, sigma af m plus m minus 1, plus m minus 2, plus m minus 3. 1036 00:44:56,710 --> 00:44:58,030 Jeg ønsker ikke at skrive alt det ud. 1037 00:44:58,030 --> 00:44:59,120 Hvorfor kan jeg ikke bare punt? 1038 00:44:59,120 --> 00:45:05,080 Rekursivt kalde mig selv med en lidt mindre problem, semikolon, 1039 00:45:05,080 --> 00:45:06,840 og kalder det en dag? 1040 00:45:06,840 --> 00:45:07,040 >> Right? 1041 00:45:07,040 --> 00:45:10,980 Nu også her, kan du føler eller bekymre at dette er en uendelig løkke, som jeg 1042 00:45:10,980 --> 00:45:15,450 overtalelse, hvorved jeg gennemføre sigma ved at kalde sigma. 1043 00:45:15,450 --> 00:45:20,342 Men det er helt OK, fordi jeg troede forude 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, hvilket er min hvis tilstand. 1046 00:45:25,430 --> 00:45:28,390 For hvad er rart om de subtraktion her, for jeg holder 1047 00:45:28,390 --> 00:45:31,180 afleverer sigma mindre problemer, mindre problemer, mindre - det er ikke 1048 00:45:31,180 --> 00:45:31,870 halv størrelse. 1049 00:45:31,870 --> 00:45:34,380 Det er kun en baby skridt mindre, men det er OK. 1050 00:45:34,380 --> 00:45:38,050 Fordi i sidste ende, vil vi arbejde vores vej ned til 1 eller 0. 1051 00:45:38,050 --> 00:45:41,630 Og når vi ramte 0, sigma er ikke kommer til at kalde sig selv længere. 1052 00:45:41,630 --> 00:45:43,590 Det kommer til at øjeblikkeligt returnere 0. 1053 00:45:43,590 --> 00:45:47,960 >> Så effekten, hvis du slags vind dette op i dit sind, er at tilføje m plus 1054 00:45:47,960 --> 00:45:52,740 m minus 1 plus m minus 2, plus m minus 3, plus dot, dot, dot, m minus 1055 00:45:52,740 --> 00:45:57,820 m, i sidste ende giver dig 0 og effekt er i sidste ende at tilføje alle 1056 00:45:57,820 --> 00:45:59,070 disse ting sammen. 1057 00:45:59,070 --> 00:46:02,380 Så vi har ikke med rekursion, løste det problem, som 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 udg.0 af dette, og hver problem til dato har været løselige 1060 00:46:06,840 --> 00:46:09,980 med blot bruger til loops, eller mens løkker eller lignende konstruktioner. 1061 00:46:09,980 --> 00:46:13,150 >> Men rekursion, jeg tør sige, giver os en anden måde at tænke på 1062 00:46:13,150 --> 00:46:17,010 problemer, hvor hvis vi kan tage en problem, opdele det fra noget 1063 00:46:17,010 --> 00:46:22,340 noget stort til noget lidt mindre, jeg påstå, at vi kan løse det 1064 00:46:22,340 --> 00:46:26,040 måske lidt mere elegant i form af design, med mindre kode 1065 00:46:26,040 --> 00:46:30,980 og måske endda løse problemer, der ville være sværere, da vi vil i sidste ende 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 at forlade os på var dette. 1068 00:46:35,980 --> 00:46:40,720 Lad mig gå videre og åbne en fil fra - 1069 00:46:40,720 --> 00:46:44,300 faktisk, lad mig gå, og gøre dette virkelig hurtigt. 1070 00:46:44,300 --> 00:46:46,875 Lad mig gå videre og foreslå følgende. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Blandt dagens kode er denne fil her. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Denne ene her noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Så dette er en dum lille program, Jeg pisket op, der hævder at gøre 1076 00:47:06,260 --> 00:47:06,940 følgende. 1077 00:47:06,940 --> 00:47:10,140 I main, først den erklærer en int kaldet x og tildeler den 1078 00:47:10,140 --> 00:47:11,100 værdien af ​​1.. 1079 00:47:11,100 --> 00:47:13,520 Så erklærer en int y og tildeler den værdien 2. 1080 00:47:13,520 --> 00:47:15,310 Så udskriver hvad x og y er. 1081 00:47:15,310 --> 00:47:17,781 Så det siger, bytte, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Så er det hævder at være at kalde en funktion kaldet swap, der passerer i x-og 1083 00:47:21,670 --> 00:47:24,290 y, tanken om at der, som forhåbentlig x og y vil komme tilbage 1084 00:47:24,290 --> 00:47:25,620 anderledes, det modsatte. 1085 00:47:25,620 --> 00:47:27,110 Så er det hævder byttet! 1086 00:47:27,110 --> 00:47:28,420 med et udråbstegn. 1087 00:47:28,420 --> 00:47:30,190 Så den udskriver x og y. 1088 00:47:30,190 --> 00:47:33,480 >> Men det viser sig, at denne meget simple demonstration ned 1089 00:47:33,480 --> 00:47:35,570 her er faktisk buggy. 1090 00:47:35,570 --> 00:47:38,870 Selvom jeg erklære en midlertidig variabel og midlertidigt at sætte en i 1091 00:47:38,870 --> 00:47:42,010 det, så er jeg omfordeling en værdien af ​​b - 1092 00:47:42,010 --> 00:47:45,080 som føles rimelige, fordi jeg har gemt en kopi af en i temp. 1093 00:47:45,080 --> 00:47:48,410 Så jeg opdatere b til lige uanset var i temp. 1094 00:47:48,410 --> 00:47:51,610 Denne form for shell spil at flytte en i b og b til en ved hjælp af denne 1095 00:47:51,610 --> 00:47:54,360 midt-mand kaldet temp føler helt rimeligt. 1096 00:47:54,360 --> 00:47:57,270 >> Men jeg hævder, at når jeg kører denne kode, som jeg vil gøre nu - 1097 00:47:57,270 --> 00:47:59,490 lad mig gå videre og indsætte det her. 1098 00:47:59,490 --> 00:48:01,995 Jeg ringer denne noswap.c. 1099 00:48:01,995 --> 00:48:05,630 Og som navnet antyder, er dette ikke kommer til at være et korrekt program. 1100 00:48:05,630 --> 00:48:09,460 Gør noswap. / Nej swap. 1101 00:48:09,460 --> 00:48:12,110 x er 1, y er 2, swapping, byttes. 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 forkert, selv selvom dette synes perfekt 1104 00:48:16,920 --> 00:48:17,730 rimeligt for mig. 1105 00:48:17,730 --> 00:48:21,330 Og der er en grund, men vi er ikke vil afsløre årsagen endnu. 1106 00:48:21,330 --> 00:48:24,610 >> For nu anden cliffhanger jeg ønskede at efterlade dig med, er dette en 1107 00:48:24,610 --> 00:48:27,120 annonceringen af ​​sorterer på kupon koder. 1108 00:48:27,120 --> 00:48:31,590 Vores innovation med sene dage i år har fremprovokeret en ikke-triviel nummer 1109 00:48:31,590 --> 00:48:33,830 spørgsmål, som var ikke vores hensigt. 1110 00:48:33,830 --> 00:48:36,590 Hensigten med disse kupon koder, hvorved, hvis du gør en del af problemet 1111 00:48:36,590 --> 00:48:39,850 sætte tidligt, og derved få en ekstra dag, var virkelig til at hjælpe jer hjælpe 1112 00:48:39,850 --> 00:48:42,420 selv starte tidligt, sort af ved incentivizing dig. 1113 00:48:42,420 --> 00:48:44,880 Hjælper os distribuere belastningen over kontortid bedre, så 1114 00:48:44,880 --> 00:48:45,740 Det er en slags win-win. 1115 00:48:45,740 --> 00:48:48,860 >> Jeg tror desværre, mine anvisninger har ikke været til dato, meget klar, så 1116 00:48:48,860 --> 00:48:52,230 Jeg gik tilbage denne weekend og opdateret spec i større, federe tekst til 1117 00:48:52,230 --> 00:48:53,600 forklare kugler som disse. 1118 00:48:53,600 --> 00:48:56,900 Og bare for at sige det mere offentligt, ved standard, problemløsning sæt skyldes torsdag 1119 00:48:56,900 --> 00:48:58,400 ved middagstid, pr. pensum 1120 00:48:58,400 --> 00:49:02,030 Hvis du starter tidligt, efterbehandling en del af det problem fastsat senest onsdag kl 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, den del, der vedrører en kupon kode, ideen er, at du kan udvide 1122 00:49:05,170 --> 00:49:07,710 din deadline for P sæt til fredag. 1123 00:49:07,710 --> 00:49:10,890 Det vil sige, lidt fra en meget lille del af P sæt i forhold til hvad typisk er 1124 00:49:10,890 --> 00:49:13,200 større problem, og du kan købe selv en ekstra dag. 1125 00:49:13,200 --> 00:49:15,190 Igen, det får du tænker problemet sæt, får dig til 1126 00:49:15,190 --> 00:49:16,380 kontortid før. 1127 00:49:16,380 --> 00:49:20,670 Men kuponkode problemet stadig påkrævet, selvom du ikke sende det. 1128 00:49:20,670 --> 00:49:23,340 >> Men mere uimodståelig er dette. 1129 00:49:23,340 --> 00:49:26,520 (Teaterhvisken) Og disse folk forlader tidligt er gonna fortryde det. 1130 00:49:26,520 --> 00:49:28,620 Da er de folk på balkonen. 1131 00:49:28,620 --> 00:49:32,510 Jeg undskylder på forhånd til folk på balkonen grunde, der vil være 1132 00:49:32,510 --> 00:49:33,920 klart på bare et øjeblik. 1133 00:49:33,920 --> 00:49:37,050 >> Så vi er heldige at have en af CS50 tidligere hoved undervisning stipendiater på 1134 00:49:37,050 --> 00:49:39,302 et firma kaldet dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 De har meget generøst doneret en kuponkode her for denne meget plads, 1136 00:49:45,500 --> 00:49:48,180 der er op fra sædvanlige 2 gigabyte. 1137 00:49:48,180 --> 00:49:51,740 Så hvad jeg troede, vi ville gøre på dette afsluttende bemærkning er at gøre lidt af en foræring, 1138 00:49:51,740 --> 00:49:55,380 hvorved i bare et øjeblik, vil vi afsløre vinderen og som har en kupon 1139 00:49:55,380 --> 00:49:57,980 kode, som du derefter kan gå til deres website, skal du skrive det i, og voila, få en 1140 00:49:57,980 --> 00:50:01,370 hel masse mere Dropbox plads til dine apparat og til dine personlige filer. 1141 00:50:01,370 --> 00:50:05,690 >> Og først, hvem ville gerne deltage i denne tegning? 1142 00:50:05,690 --> 00:50:09,630 OK, nu gør det endnu sjovere. 1143 00:50:09,630 --> 00:50:14,010 Den person, der modtager denne 25-gigabyte kuponkode - hvilket er langt 1144 00:50:14,010 --> 00:50:16,150 mere overbevisende end den sene dage nu, måske - 1145 00:50:16,150 --> 00:50:20,620 er den, der sidder på toppen af ​​en siddepude hvorunder der er 1146 00:50:20,620 --> 00:50:21,620 at kuponkode. 1147 00:50:21,620 --> 00:50:23,480 Du kan nu se nedenunder Deres sædehynden. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [VIDEO AFSPIL] 1150 00:50:29,680 --> 00:50:31,620 >> -En, to, tre. 1151 00:50:31,620 --> 00:50:35,015 >> [SCREAMING] 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, dig 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: Balcony folkens, kom hernede til fronten, 1161 00:50:45,530 --> 00:50:46,866 hvor vi har ekstramateriale. 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 VIDEOAFSPILNING] 1165 00:50:52,722 --> 00:50:54,590 >> Fortæller: På det næste 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 PLAYS]