1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> Spreker: Oke, dit is CS50. 3 00:00:14,910 --> 00:00:19,020 Dit is het einde van week drie, en als je hebt geen voordeel reeds genomen, 4 00:00:19,020 --> 00:00:21,790 weten dat er de lunch zal zijn deze vrijdag zoals gewoonlijk, waar 5 00:00:21,790 --> 00:00:25,430 u kunt genieten van een goed gesprek en eten bij Fire and Ice 6 00:00:25,430 --> 00:00:27,980 met enkele van CS50's personeel en klasgenoten. 7 00:00:27,980 --> 00:00:30,170 Ga naar deze URL hier. 8 00:00:30,170 --> 00:00:33,420 >> Nu u zich wellicht herinnert, of dat u kan binnenkort op de hoogte zijn, 9 00:00:33,420 --> 00:00:35,970 deze dingen hier, die worden gegeven aan het einde 10 00:00:35,970 --> 00:00:37,850 van het semester voor vele klassen. 11 00:00:37,850 --> 00:00:40,870 Zogenaamde examen blauw boeken, waarin je schrijft je antwoorden op examens. 12 00:00:40,870 --> 00:00:44,240 Nu heb ik hier 26 dergelijke blauw boeken, op elk van hen 13 00:00:44,240 --> 00:00:47,580 is geschreven een naam, A tot Z. En inderdaad de namen zijn zo simpel, A 14 00:00:47,580 --> 00:00:50,490 door Z. En een van de doelen bij de hand vandaag 15 00:00:50,490 --> 00:00:53,910 gaat worden om verder te gaan wat we begonnen op maandag, wat niet 16 00:00:53,910 --> 00:00:57,830 zozeer te kijken naar code, maar echt op zoek naar ideeën en het oplossen van problemen. 17 00:00:57,830 --> 00:01:00,170 Een van de doelen en beloften van deze cursus 18 00:01:00,170 --> 00:01:02,985 is om je te leren om meer te denken zorgvuldig, meer methodisch, 19 00:01:02,985 --> 00:01:05,400 en problemen efficiënter oplossen. 20 00:01:05,400 --> 00:01:09,526 En inderdaad, we kunnen dat echt doen zonder zelfs het aanraken van een regel code. 21 00:01:09,526 --> 00:01:12,150 Dus ik heb een paar van olifanten hier vandaag, oranje en blauw, 22 00:01:12,150 --> 00:01:15,780 Als we een vrijwilliger konden krijgen, misschien uit verder terug dan normaal. 23 00:01:15,780 --> 00:01:18,070 Hoe zit het daar, kom naar beneden. 24 00:01:18,070 --> 00:01:24,180 Waarvan het doel zal zijn om helpen plus beheren dit examen hier. 25 00:01:24,180 --> 00:01:24,935 Wat is je naam? 26 00:01:24,935 --> 00:01:25,768 >> PUBLIEK: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 Spreker: Mary Beth, kom op. 28 00:01:27,560 --> 00:01:29,560 Laat me de microfoon hier voor jou. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Leuk je te ontmoeten. 31 00:01:32,880 --> 00:01:34,005 >> PUBLIEK: Leuk je te ontmoeten. 32 00:01:34,005 --> 00:01:36,790 Spreker: Oke, dus ik heb hier blauw boeken A tot en met Z, 33 00:01:36,790 --> 00:01:41,680 en ik ga om te beweren dat Ik heb een van de studenten, 34 00:01:41,680 --> 00:01:45,770 en ze komen in enigszins willekeurig aan het einde van een drie uur examen blok, 35 00:01:45,770 --> 00:01:49,400 zodat ze uiteindelijk in sommige semi-willekeurige volgorde als deze. 36 00:01:49,400 --> 00:01:54,510 Nu je baan in slechts een moment gaat om be-- dit is eigenlijk hoe ze 37 00:01:54,510 --> 00:01:56,820 speelde eind de klasse, waarschijnlijk. 38 00:01:56,820 --> 00:02:01,120 Nu je baan gaat worden, heel gewoon, deze blauwe boeken voor ons gekozen afstand 39 00:02:01,120 --> 00:02:05,220 van A tot Z. 40 00:02:05,220 --> 00:02:08,400 >> PUBLIEK: Oh, dit is gaat een eeuwigheid te duren. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: En we zullen kijken als je dit doet, geen druk. 42 00:02:13,747 --> 00:02:15,330 PUBLIEK: Nee, geen druk of iets. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: En voor de lol, laten we een timer. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PUBLIEK: Zo leuk, zo leuk. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Ik kan de microfoon te houden voor u. 49 00:02:38,574 --> 00:02:40,240 Oke, we hebben gewoon verdubbeld onze snelheid. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Dus in de tussentijd, laat me stellen wat gaan op de vraag voor Mary Beth zijn 52 00:02:49,060 --> 00:02:51,540 is wat ze aan het doen, hoe is Ze gaan over het oplossen van deze? 53 00:02:51,540 --> 00:02:54,040 En in feite zou je niet hebben ooit nagedacht over iets 54 00:02:54,040 --> 00:02:57,440 zo eenvoudig als bij de overhandiging een stijging van 26 boeken als deze, 55 00:02:57,440 --> 00:02:59,350 die hebben een natuurlijke het bestellen van hen. 56 00:02:59,350 --> 00:03:01,335 Welke werkwijze dat je eigenlijk gebruiken? 57 00:03:01,335 --> 00:03:03,770 Is het redelijk willekeurig net het plukken van de eerste die je ziet 58 00:03:03,770 --> 00:03:05,250 en zetten het op zijn plaats? 59 00:03:05,250 --> 00:03:09,680 Heeft u eerst beweeg je handen rond op zoek naar A en dan op zoek naar B? 60 00:03:09,680 --> 00:03:11,722 Heeft u een kijkje nemen op een te nemen paar ze naast elkaar 61 00:03:11,722 --> 00:03:14,680 en gewoon zeggen, wacht eens even, dit is niet goed, en dan wisselen de orde? 62 00:03:14,680 --> 00:03:16,960 We zagen al op maandag dat er een aantal manieren 63 00:03:16,960 --> 00:03:22,140 waar kunnen we dit doen, en inderdaad nu we hier eind, 64 00:03:22,140 --> 00:03:26,360 Ik zou het briefje misschien nemen van wat Mary Beth doet. 65 00:03:26,360 --> 00:03:30,040 We hebben een paar palen naar het schijnt, een grotere, drie kleinere. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> Publiek: Ik ga ze bestellen toen ik twee brieven 68 00:03:36,415 --> 00:03:39,540 dat ik weet dat ze samen in een reeks, Ik zet ze samen, zodat ik niet 69 00:03:39,540 --> 00:03:42,915 zorgen te maken over het houden van spoor van een hele rij van boeken. 70 00:03:42,915 --> 00:03:45,706 Het is gewoon, oh, A is de eerste, Ik heb deze stack kreeg hier. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Dus, bijna als een puzzel stukken die 72 00:03:47,580 --> 00:03:49,860 het recht vorm overeenkomen met elkaar. 73 00:03:49,860 --> 00:03:51,026 PUBLIEK: Vrij veel, ja. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, uitstekend. 75 00:03:55,320 --> 00:03:59,850 En nu elk van deze palen is vermoedelijk naargelang? 76 00:03:59,850 --> 00:04:00,990 >> Publiek: Ja. 77 00:04:00,990 --> 00:04:09,900 >> Spreker: Oke, A tot en met Z. Alle rechts, van harte gefeliciteerd, het is je gelukt. 78 00:04:09,900 --> 00:04:11,461 Je hebt je keuze. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Oke, bedankt voor dat. 81 00:04:13,530 --> 00:04:16,679 Dus Mary Beth heeft voorgesteld wat haar benadering, 82 00:04:16,679 --> 00:04:19,720 maar wat is een andere benadering van hoe je zou kunnen gaan over het sorteren van deze dingen? 83 00:04:19,720 --> 00:04:21,130 Wat zou jij gedaan hebben? 84 00:04:21,130 --> 00:04:24,060 Het record te verslaan zou zijn geweest een minuut en 50 seconden of zo, 85 00:04:24,060 --> 00:04:26,039 plus degenen die ik vergat te tellen. 86 00:04:26,039 --> 00:04:27,080 Wat zou jij gedaan hebben? 87 00:04:27,080 --> 00:04:27,579 Yeah? 88 00:04:27,579 --> 00:04:28,735 PUBLIEK: Neem de stapel. 89 00:04:28,735 --> 00:04:29,776 Begin bij het begin. 90 00:04:29,776 --> 00:04:32,284 Controleer uw papieren. 91 00:04:32,284 --> 00:04:36,586 Als de bovenste hoger dan misschien zijn ze, 92 00:04:36,586 --> 00:04:38,980 onderste is hoger, dan schakelen ze. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: OK, dus het starten boven en beneden, 94 00:04:41,300 --> 00:04:43,716 en dan werk je weg naar binnen als dat, ruilt ze? 95 00:04:43,716 --> 00:04:46,580 OK, dus een beetje vergelijkbaar in de geest naar bubble sort, 96 00:04:46,580 --> 00:04:49,160 maar het kiezen van de extremen niet aangrenzende paren. 97 00:04:49,160 --> 00:04:52,080 Maar de korte daarvan is dat er zeker een heleboel verschillende manieren 98 00:04:52,080 --> 00:04:54,210 We konden dit doen, en eerlijk gezegd, denk ik dat je soort 99 00:04:54,210 --> 00:04:55,700 nam een ​​paar benaderingen, toch? 100 00:04:55,700 --> 00:05:00,567 Je maakte een soort van vier gesorteerde stapels, en dan effectief samengevoegd ze samen. 101 00:05:00,567 --> 00:05:02,650 En dat is, durf te zeggen, een ander techniek helemaal. 102 00:05:02,650 --> 00:05:06,950 Je deed het niet behandelen als een grote stapel, u het probleem opgedeeld in vier quads, 103 00:05:06,950 --> 00:05:09,820 als je wil, en dan een of andere manier fuseerde ze op het einde. 104 00:05:09,820 --> 00:05:13,410 >> Dus laten we eens kijken, uiteindelijk, hoe anders we dit zouden kunnen doen. 105 00:05:13,410 --> 00:05:15,860 We geformaliseerd de notie van bubble sort vorige keer, 106 00:05:15,860 --> 00:05:18,780 en bubble sort recall was een algoritme dat we gevisualiseerd 107 00:05:18,780 --> 00:05:22,640 met acht van je klasgenoten hier, schijnbaar willekeurig naargelang op het eerste. 108 00:05:22,640 --> 00:05:26,110 En we hebben toen besloten paarsgewijs, indien twee elementen zijn niet in orde, 109 00:05:26,110 --> 00:05:26,950 eenvoudig te verwisselen. 110 00:05:26,950 --> 00:05:28,930 Zo vier en twee uiteraard buiten de orde, 111 00:05:28,930 --> 00:05:31,080 dus die twee klasgenoten geschakelde posities. 112 00:05:31,080 --> 00:05:35,390 En dan herhaald we met vier en zes, dan zes en acht, op elke iteratie, 113 00:05:35,390 --> 00:05:36,980 naar rechts beweegt. 114 00:05:36,980 --> 00:05:42,590 >> Dus gegeven acht mensen, hoeveel paarsgewijze vergelijkingen heb ik gedaan tijdens het lopen van 115 00:05:42,590 --> 00:05:45,220 links naar rechts in een dergelijke iteratie? 116 00:05:45,220 --> 00:05:48,410 Hoeveel vergelijkingen? 117 00:05:48,410 --> 00:05:49,197 Zeven, toch? 118 00:05:49,197 --> 00:05:51,405 Want als er acht mensen, maar je hebt het paar 119 00:05:51,405 --> 00:05:53,880 ze en je blijven bewegen een hop naar rechts, 120 00:05:53,880 --> 00:05:56,060 je bent niet van plan om zijn acht vergelijkingen, want je kunt niet vergelijken 121 00:05:56,060 --> 00:05:59,226 een element dat tegen zichzelf, of het zou gewoon zinloos, dus je hebt zeven. 122 00:05:59,226 --> 00:06:01,290 Of meer in het algemeen, indien we hebben n mensen, we 123 00:06:01,290 --> 00:06:04,300 doe n minus 1 vergelijkingen met bubble sort. 124 00:06:04,300 --> 00:06:08,150 >> Dus laten we eens kijken nu hoe goed of slechte bubble sort eigenlijk was, en probeer 125 00:06:08,150 --> 00:06:13,570 om ons vocabulaire te geven met die aan kritiek algoritmes als dit, 126 00:06:13,570 --> 00:06:14,430 en binnenkort ons eigen. 127 00:06:14,430 --> 00:06:16,970 Dus de eerste passage door bubble sort, de eerste keer 128 00:06:16,970 --> 00:06:20,909 Ik liep van links naar rechts over de podium, nam me n minus 1 vergelijkingen. 129 00:06:20,909 --> 00:06:22,950 En dat gaat zijn mijn maateenheid, toch? 130 00:06:22,950 --> 00:06:26,170 Ik was een beetje praten en wandelen, wat snel, wat traag, 131 00:06:26,170 --> 00:06:29,300 dus tellen mijn aantal seconden is niet bijzonder te vertellen, 132 00:06:29,300 --> 00:06:32,260 maar het tellen van het aantal operaties die ik deed op maandag, 133 00:06:32,260 --> 00:06:35,900 vergelijken van twee mensen, dat voelt als een aardige maateenheid. 134 00:06:35,900 --> 00:06:40,980 >> Zo n minus 1 stap het eerst maar wat er daarna gebeurde? 135 00:06:40,980 --> 00:06:46,610 Wat is het een kop van een pas door middel van een anders ongesorteerde lijst? 136 00:06:46,610 --> 00:06:49,840 Wat kun je me vertellen over het element die de hele weg daar was? 137 00:06:49,840 --> 00:06:51,300 Yeah? 138 00:06:51,300 --> 00:06:52,870 Dat was de grootste element, toch? 139 00:06:52,870 --> 00:06:55,710 Nummer acht, hoewel ze begon hier, elke keer als ik 140 00:06:55,710 --> 00:06:57,860 vergeleek haar tegen een buurman, hield ze 141 00:06:57,860 --> 00:07:00,480 borrelen rechts kant van de lijst. 142 00:07:00,480 --> 00:07:02,710 En inderdaad, dat is waar het algoritme zijn naam krijgt. 143 00:07:02,710 --> 00:07:07,630 >> Nu door die logica, hoeveel vergelijkingen moet ik op de tweede keer 144 00:07:07,630 --> 00:07:09,800 Ik maak die pass van links naar rechts? 145 00:07:09,800 --> 00:07:10,730 n minus 2, toch? 146 00:07:10,730 --> 00:07:14,297 Het zou gewoon mijn tijd verspillen als ik houden het vergelijken acht tegen iemand 147 00:07:14,297 --> 00:07:16,630 anders omdat we al weten Ze was op de juiste plaats. 148 00:07:16,630 --> 00:07:19,760 Dus dat is een beetje een optimalisatie, dus de volgende pas 149 00:07:19,760 --> 00:07:23,899 gaat worden plus n min twee stappen, waarbij n het aantal mensen. 150 00:07:23,899 --> 00:07:26,940 Nu kun je soort extrapoleren, zelfs als je niet een computer wetenschapper, 151 00:07:26,940 --> 00:07:27,680 hoe dit afloopt. 152 00:07:27,680 --> 00:07:31,259 Aan het einde van dit algoritme, vermoedelijk je hebt slechts een vergelijking gelaten. 153 00:07:31,259 --> 00:07:33,800 Je moet soort vaststellen van de begin van de lijst in het geval van twee 154 00:07:33,800 --> 00:07:36,540 en men is niet in orde en moet een en twee, 155 00:07:36,540 --> 00:07:40,330 dus deze bodems uit bij plus 1 laatste vergelijking. 156 00:07:40,330 --> 00:07:44,500 >> Nu is de dot, dot, dot soort golven is het handen op een aantal van de sappiger details 157 00:07:44,500 --> 00:07:46,452 maar laten we gewoon doorgaan en te vereenvoudigen. 158 00:07:46,452 --> 00:07:48,660 Misschien herinner je je van de hoge school, eerlijk gezegd, veel van jullie 159 00:07:48,660 --> 00:07:50,340 had wiskunde boeken die had een klein spiekbriefje 160 00:07:50,340 --> 00:07:52,550 op de voorkant of de back cover die je liet zien 161 00:07:52,550 --> 00:07:56,400 wat serie sommaties zoals dit uiteindelijk tot toegevoegd aan. 162 00:07:56,400 --> 00:07:59,600 In het algemene geval, als u een variabele als n, en inderdaad deze, 163 00:07:59,600 --> 00:08:01,634 als u gekeken naar uw oude school wiskunde boek, 164 00:08:01,634 --> 00:08:04,050 zou je zien dat dit ook daadwerkelijk voegt tot dit bedrag hier, 165 00:08:04,050 --> 00:08:07,970 n keer n minus 1 alles gedeeld door 2. 166 00:08:07,970 --> 00:08:11,172 Dus voor nu laat ik gewoon bepalen dit waar is, dus op een sprong van het geloof, 167 00:08:11,172 --> 00:08:12,880 dat is wat dit vat tot, en we konden 168 00:08:12,880 --> 00:08:14,341 bewijzen dat een meer algemeen geval. 169 00:08:14,341 --> 00:08:15,590 Maar laten we nu uitbreiden dit uit. 170 00:08:15,590 --> 00:08:19,920 Dus laten we dit vermenigvuldigen, dus dat is n kwadraat, minus n, alles gedeeld door 2. 171 00:08:19,920 --> 00:08:23,200 Dat is echt n kwadraat, gedeeld door 2, minus n meer dan 2, 172 00:08:23,200 --> 00:08:25,010 dus dat is allemaal leuk en interessant. 173 00:08:25,010 --> 00:08:27,060 Maar wat gebeurt er als we plug-in een waarde? 174 00:08:27,060 --> 00:08:29,724 Stel dat ik niet heb acht mensen, maar laten we zeggen een miljoen. 175 00:08:29,724 --> 00:08:31,890 En omdat miljoen het is een vrij groot aantal, 176 00:08:31,890 --> 00:08:34,039 laten we de stekker die in en zie wat er gebeurt. 177 00:08:34,039 --> 00:08:39,039 Dus als ik de stekker van een miljoen in die formule Ik ga je een miljoen in het kwadraat, 178 00:08:39,039 --> 00:08:42,868 gedeeld door 2, minus een miljoen, gedeeld door 2. 179 00:08:42,868 --> 00:08:44,159 Nu wat dat gaat evenaren? 180 00:08:44,159 --> 00:08:47,354 Dus 500 miljard, minus 500.000. 181 00:08:47,354 --> 00:08:49,270 En als ik het eigenlijk doen dat wiskunde uit, dat betekent 182 00:08:49,270 --> 00:08:53,920 dat het sorteren van een miljoen mensen met de bubble sort 183 00:08:53,920 --> 00:09:01,800 zou me 499999500000 stappen of vergelijkingen in het einde, 184 00:09:01,800 --> 00:09:02,900 we zijn gewoon extrapoleren. 185 00:09:02,900 --> 00:09:06,860 >> Dat voelt vrij traag, maar eerlijk gezegd het meten van een bepaalde ingang 186 00:09:06,860 --> 00:09:09,160 als dit, is niet zo veelzeggend. 187 00:09:09,160 --> 00:09:14,050 Maar inderdaad het geeft wel aan dat als n groter en groter, dit algoritme 188 00:09:14,050 --> 00:09:16,280 soort voelt erger en erger, of je echt 189 00:09:16,280 --> 00:09:20,450 beginnen om de pijn die aanvoelen machtsverheffen, dat n het kwadraat, 190 00:09:20,450 --> 00:09:21,770 die voegt behoorlijk snel. 191 00:09:21,770 --> 00:09:25,340 En dit detail is niet verloren op mensen, in feite 192 00:09:25,340 --> 00:09:29,640 enkele jaren geleden een zekere senator die was campagne, ging zitten voor een interview 193 00:09:29,640 --> 00:09:32,180 met Google's Eric Schmidt, CEO op het moment, 194 00:09:32,180 --> 00:09:36,380 en werd uitgedaagd met een vraag net als die we vandaag verkennen. 195 00:09:36,380 --> 00:09:38,468 Laten we eens een kijkje nemen. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO AFSPELEN] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Je bent hier bij Google, en ik hou van 198 00:09:48,560 --> 00:09:53,382 te denken van het voorzitterschap als een sollicitatiegesprek. 199 00:09:53,382 --> 00:09:56,434 Nu, het is moeilijk te krijgen een baan als voorzitter, 200 00:09:56,434 --> 00:09:58,100 en je gaat door de ontberingen nu. 201 00:09:58,100 --> 00:10:01,860 Het is ook moeilijk om een ​​baan te krijgen bij Google. 202 00:10:01,860 --> 00:10:05,490 Wij hebben vragen, en we vragen onze kandidaten vragen, 203 00:10:05,490 --> 00:10:09,770 en deze is van Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 Wat-- jullie denken dat ik grapje, het is hier. 205 00:10:14,760 --> 00:10:17,930 Wat is de meest efficiënte manier om sorteren miljoen 32-bits gehele getallen? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> Het spijt me, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Nee, nee, nee. 210 00:10:27,400 --> 00:10:30,700 Ik denk dat de bubble sort zou de verkeerde weg te gaan. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Kom op, die hem dit verteld? 213 00:10:38,180 --> 00:10:40,590 Ik zag geen computer wetenschap in je achtergrond. 214 00:10:40,590 --> 00:10:42,130 >> -We Onze spionnen in. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Laten we vragen een andere interview vraag. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEO AFSPELEN] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Dus het over specifieke nummers wel, 219 00:10:52,290 --> 00:10:53,890 zal niet alles nuttig zijn. 220 00:10:53,890 --> 00:10:56,810 Het is niet een levensles die zeepbel sorteren, aangezien een miljoen ingangen, 221 00:10:56,810 --> 00:10:58,590 kan net zo veel als 500 miljard stappen ondernemen. 222 00:10:58,590 --> 00:11:01,120 Je kunt niet echt generaliseren Ook effectief uit dat 223 00:11:01,120 --> 00:11:03,560 en maak een goede ontwerpbeslissingen bij het schrijven van programma's. 224 00:11:03,560 --> 00:11:07,070 Dus laten we focussen wel op hoe We kunnen dit resultaat vereenvoudigen. 225 00:11:07,070 --> 00:11:11,780 >> Dus ik heb geel gemarkeerd hier het resultaat van n kwadraat gedeeld door 2, 226 00:11:11,780 --> 00:11:14,330 dus een miljoen in het kwadraat gedeeld door 2, en 227 00:11:14,330 --> 00:11:16,710 Ik heb gewezen op wat het ultieme antwoord was 228 00:11:16,710 --> 00:11:20,180 als we eenmaal afgetrokken off n gedeeld door 2. 229 00:11:20,180 --> 00:11:24,850 En de bewering ga ik nu te maken is, wie de heck cares als je aftrekken af 230 00:11:24,850 --> 00:11:30,060 een beetje oud n meer dan 2 bij de eerste onderdeel van deze formule is zo veel groter? 231 00:11:30,060 --> 00:11:33,910 Het domineert de andere termijn n kwadraat gedeeld door 2 232 00:11:33,910 --> 00:11:37,510 is zo veel groter, duidelijk, als n groot wordt als een miljoen, 233 00:11:37,510 --> 00:11:41,450 dat is er echt een groot verschil in het einde van de dag tussen 500 miljard 234 00:11:41,450 --> 00:11:45,730 en 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Niet echt. 236 00:11:46,349 --> 00:11:48,640 En dus wat we gaan doen als informatici is 237 00:11:48,640 --> 00:11:53,270 negeer die lagere orde termen en neem iets als dit en echt 238 00:11:53,270 --> 00:11:56,050 gewoon vereenvoudigen het aan de termijn dat gaat uit. 239 00:11:56,050 --> 00:12:00,315 Hoe groter onze datasets te krijgen, hoe groter onze databases te krijgen, hoe meer webpagina's 240 00:12:00,315 --> 00:12:02,690 we moeten zoeken, hoe meer vrienden je hebt op Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Als n groter wordt, zijn we echt gaat om de zorg over de grootste 242 00:12:07,340 --> 00:12:11,560 termijn dergelijke analyse onze algoritmes prestaties. 243 00:12:11,560 --> 00:12:16,230 En ik ga zeggen, weet je wat, bubble sort is in de orde van grote O, 244 00:12:16,230 --> 00:12:18,060 in de orde van n kwadraat. 245 00:12:18,060 --> 00:12:20,090 Het is niet precies n kwadraat zoals we hebben gezien, 246 00:12:20,090 --> 00:12:22,060 maar die echt cares over die kleinere termen, 247 00:12:22,060 --> 00:12:24,390 en eerlijk gezegd, die echt cares als we delen door 2? 248 00:12:24,390 --> 00:12:25,870 Dat is slechts een constante factor. 249 00:12:25,870 --> 00:12:29,480 En is 500 miljard versus 250 miljard echt zo groot van een deal? 250 00:12:29,480 --> 00:12:32,190 Ik kon gewoon wachten een jaar, laat mijn laptop letterlijk 251 00:12:32,190 --> 00:12:34,810 krijgen twee keer zo snel in hardware, en dat soort verschil 252 00:12:34,810 --> 00:12:36,650 gewoon verdwijnt vanzelf na verloop van tijd. 253 00:12:36,650 --> 00:12:39,300 >> Wat we de zorg over is de uitdrukking, het deel 254 00:12:39,300 --> 00:12:42,489 van de uitdrukking dat gaat variëren als onze inbreng groter en groter. 255 00:12:42,489 --> 00:12:45,280 En inderdaad, in de echte wereld, dat is wat er gebeurt in toenemende mate 256 00:12:45,280 --> 00:12:48,330 is de input voor onze problemen en algoritmen worden steeds groter. 257 00:12:48,330 --> 00:12:53,470 Zo groot O gaat naar de notatie te zijn, de asymptotische notatie, dat we gewoon 258 00:12:53,470 --> 00:12:57,160 gebruiken als informatici te beschrijven de prestaties, of de looptijd, 259 00:12:57,160 --> 00:12:58,130 van een algoritme. 260 00:12:58,130 --> 00:13:00,800 Zodat we algoritmen kunnen vergelijken op verschillende computers geschreven 261 00:13:00,800 --> 00:13:04,170 door verschillende mensen, met sommige fundamenteel vergelijkbaar metrische 262 00:13:04,170 --> 00:13:07,557 zoals het aantal vergelijkingen dat je maken, of misschien het aantal swaps 263 00:13:07,557 --> 00:13:08,140 je maakt. 264 00:13:08,140 --> 00:13:11,910 >> Wat we niet van plan om telling is de hoeveelheid tijd 265 00:13:11,910 --> 00:13:13,981 dat gaat op de klok op de muur typisch. 266 00:13:13,981 --> 00:13:16,230 Wat we gaan niet te maken over is hoeveel geheugen 267 00:13:16,230 --> 00:13:17,820 je gebruikt vandaag op Tenminste, al is dat 268 00:13:17,820 --> 00:13:19,370 andere bron we kunnen meten. 269 00:13:19,370 --> 00:13:23,610 We gaan proberen om onze analyses te baseren op alleen de basishandelingen, degenen, 270 00:13:23,610 --> 00:13:25,930 eerlijk gezegd, dat kunt u de meeste visueel te zien. 271 00:13:25,930 --> 00:13:30,700 Dus met iets als grote O van n kwadraat, ik beweer dat de O van n kwadraat 272 00:13:30,700 --> 00:13:35,820 is een bovengrens aan de zogenaamde looptijd van de bubble sort. 273 00:13:35,820 --> 00:13:38,820 Met andere woorden, als je wilde beweren dat er 274 00:13:38,820 --> 00:13:41,370 deze bovengrens op het aantal stappen van een algoritme zou kunnen nemen, 275 00:13:41,370 --> 00:13:46,240 het gaat om in de grote O van n kwadraat in dit geval een bovengrens. 276 00:13:46,240 --> 00:13:49,710 >> Wat als ik in plaats daarvan veranderen de verhaal te zijn niet over bubble sort, 277 00:13:49,710 --> 00:13:50,910 maar over deze bovengrens. 278 00:13:50,910 --> 00:13:54,030 Kunt u denken aan een algoritme dat we hebben gekeken naar al 279 00:13:54,030 --> 00:13:59,530 waarvan de bovengrens maximum meten van tijd of operaties, 280 00:13:59,530 --> 00:14:04,300 moet gezegd worden begrensd door n, een lineaire functie, 281 00:14:04,300 --> 00:14:07,260 niet een kwadratische een die gebogen? 282 00:14:07,260 --> 00:14:10,780 Wat is een algoritme dat vindt altijd niet meer 283 00:14:10,780 --> 00:14:12,860 dan als n stappen, of 2n stappen of 3n stappen? 284 00:14:12,860 --> 00:14:13,360 Yeah? 285 00:14:13,360 --> 00:14:15,030 >> Publiek: Het vinden van de grootste aantal in een lijst? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Perfect, het vinden van het grootste aantal in een lijst. 287 00:14:16,930 --> 00:14:18,940 Als ik een lijst met mensen bijvoorbeeld 288 00:14:18,940 --> 00:14:21,440 ieder die houdt van een aantal, wat is het maximum aantal 289 00:14:21,440 --> 00:14:23,770 van de maatregelen die hij me moet nemen, een redelijk slimme persoon, 290 00:14:23,770 --> 00:14:27,530 tot de grootste persoon in die lijst vinden? 291 00:14:27,530 --> 00:14:28,100 n, toch? 292 00:14:28,100 --> 00:14:31,320 Omdat in het ergste geval, wanneer kan de grootste waarde? 293 00:14:31,320 --> 00:14:32,700 Rechts, helemaal aan het einde. 294 00:14:32,700 --> 00:14:34,575 Dus in het ergste geval bovengrens, zou ik 295 00:14:34,575 --> 00:14:36,450 moeten de hele weg te gaan hier en zijn als, 296 00:14:36,450 --> 00:14:39,170 oh, hier is nummer acht, of wat die waarde is. 297 00:14:39,170 --> 00:14:41,330 Nu zou het gewoon dom als ik bleef gaan, toch? 298 00:14:41,330 --> 00:14:43,840 Op zoek naar meer en meer elementen als de laatste van hen is daar? 299 00:14:43,840 --> 00:14:45,340 Dus zeker n is een bovengrens. 300 00:14:45,340 --> 00:14:47,420 Ik hoef niet te nemen meer stappen dan die. 301 00:14:47,420 --> 00:14:51,580 >> Dus wat als ik in plaats daarvan dat de voorgestelde zijn er algoritmes in deze wereld die 302 00:14:51,580 --> 00:14:57,750 hebben een looptijd die is begrensd door grote O van log n, log n? 303 00:14:57,750 --> 00:15:00,390 Waar hebben we dit eerder gezien? 304 00:15:00,390 --> 00:15:00,890 Yeah? 305 00:15:00,890 --> 00:15:03,309 >> PUBLIEK: In het telefoonboek probleem? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Net als het telefoonboek probleem. 307 00:15:04,850 --> 00:15:07,754 Wat was de maat voor hoe veel tijd of hoeveel tranen er 308 00:15:07,754 --> 00:15:10,170 nam me mee naar iemand als vinden Mike Smith in het telefoonboek? 309 00:15:10,170 --> 00:15:13,212 We beweerden het was log n, en zelfs indien het onbekende of het 310 00:15:13,212 --> 00:15:15,170 een beetje vaag wat een logaritme of exponent was, 311 00:15:15,170 --> 00:15:17,650 alleen niet vergeten dat log n verwijst in het algemeen naar het proces, 312 00:15:17,650 --> 00:15:20,790 in dit geval, verdelen iets in de helft opnieuw, en opnieuw, 313 00:15:20,790 --> 00:15:25,790 en opnieuw en opnieuw, zodat het krijgt steeds klein als je dat doet. 314 00:15:25,790 --> 00:15:28,470 >> Dus log n verwijst, zeker, om het telefoonboek bijvoorbeeld, 315 00:15:28,470 --> 00:15:32,662 voor binaire zoekactie in theorie, als we had de virtuele deuren op het bord, 316 00:15:32,662 --> 00:15:34,370 of wanneer Sean op zoek naar iets. 317 00:15:34,370 --> 00:15:37,374 Als hij binary search had gebruikt, log n zou de bovengrens van de hoeveelheid te 318 00:15:37,374 --> 00:15:38,040 tijd die nodig is. 319 00:15:38,040 --> 00:15:44,027 Maar die algoritmen die liep in log n veronderstelde wat belangrijke details? 320 00:15:44,027 --> 00:15:45,360 Dat de lijst gesorteerd was, toch? 321 00:15:45,360 --> 00:15:47,789 Algoritme is verkeerd als Uw inbreng wordt niet gesorteerd, 322 00:15:47,789 --> 00:15:49,830 en toch je gebruikt iets binary search 323 00:15:49,830 --> 00:15:51,704 want je zou kunnen springen rechts over het element 324 00:15:51,704 --> 00:15:53,600 zonder het te beseffen het is er inderdaad. 325 00:15:53,600 --> 00:15:55,600 >> Nu, wat kan dit betekenen, grote O van een? 326 00:15:55,600 --> 00:15:59,117 Dit betekent niet dat je algoritme draait een en slechts een stap 327 00:15:59,117 --> 00:16:01,200 Het betekent alleen maar dat het duurt een constant aantal stappen. 328 00:16:01,200 --> 00:16:04,060 Misschien is het 1, misschien is het 10, misschien is het 1000, 329 00:16:04,060 --> 00:16:07,750 maar het is onafhankelijk van de omvang van het probleem. 330 00:16:07,750 --> 00:16:10,850 Het maakt niet uit hoe groot n is, een constante tijd algoritme 331 00:16:10,850 --> 00:16:12,747 neemt altijd hetzelfde aantal stappen. 332 00:16:12,747 --> 00:16:15,080 Dus wat kan een algoritme We hebben gesproken over of gewoon 333 00:16:15,080 --> 00:16:20,418 intuïtief dat naar je toe komt, dat loopt altijd in zogenaamde constante tijd? 334 00:16:20,418 --> 00:16:20,918 Yeah? 335 00:16:20,918 --> 00:16:22,001 >> PUBLIEK: Voeg twee getallen. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Voeg twee getallen, 2 plus 2 is gelijk aan 4, gedaan. 337 00:16:25,320 --> 00:16:27,227 Dus dat zou kunnen werken, wat anders? 338 00:16:27,227 --> 00:16:28,560 Wat dacht je van meer echte wereld, ja? 339 00:16:28,560 --> 00:16:30,686 >> Publiek: Het vinden van de het eerste wat in een lijst. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Het vinden van de eerste element in een lijst, zeker. 341 00:16:32,810 --> 00:16:34,540 We hebben eigenlijk gesproken over arrays al, 342 00:16:34,540 --> 00:16:36,540 hoe krijg je bij de eerste element in een array, 343 00:16:36,540 --> 00:16:40,465 het maakt niet uit hoe lang de array in C code? 344 00:16:40,465 --> 00:16:43,090 Je gebruikt net als de beugel nul notatie, bam, je bent er. 345 00:16:43,090 --> 00:16:46,120 En inderdaad arrays, als een terzijde, support iets algemeen bekend 346 00:16:46,120 --> 00:16:49,240 als random access, random access geheugen, want je kunt letterlijk 347 00:16:49,240 --> 00:16:50,284 springen naar een bepaalde plaats. 348 00:16:50,284 --> 00:16:52,700 We kunnen gewoon dit nog meer te doen we kunnen terugspoelen tot week nul 349 00:16:52,700 --> 00:16:53,900 toen we Scratch. 350 00:16:53,900 --> 00:16:59,707 Hoeveel tijd heeft het geduurd voor de zeggen blok in Scratch uit te voeren? 351 00:16:59,707 --> 00:17:00,790 Net constante tijd, toch? 352 00:17:00,790 --> 00:17:03,960 Zeg iets, zeggen iets, maakt niet uit 353 00:17:03,960 --> 00:17:07,359 hoe groot Krassen wereld is, is het altijd naar dezelfde hoeveelheid tijd 354 00:17:07,359 --> 00:17:08,490 om gewoon iets te zeggen. 355 00:17:08,490 --> 00:17:11,089 >> Dus dat is een constante tijd, maar wat is de keerzijde? 356 00:17:11,089 --> 00:17:13,030 Als dat was hoger grenzen, wat als we willen 357 00:17:13,030 --> 00:17:17,089 de ondergrenzen beschrijven van onze algoritmen looptijd? 358 00:17:17,089 --> 00:17:19,852 Bijna een best case potentieel, als je wil, 359 00:17:19,852 --> 00:17:23,060 hoewel deze termen zou kunnen gelden voor beste gevallen, ergste gevallen, gemiddeld gevallen meer 360 00:17:23,060 --> 00:17:26,359 over het algemeen, maar laten we gewoon focussen op ondergrenzen meer in het algemeen. 361 00:17:26,359 --> 00:17:31,920 Wat is een algoritme dat is een ondergrens van n trappen, 362 00:17:31,920 --> 00:17:33,350 of 2n stappen of 3n stappen? 363 00:17:33,350 --> 00:17:36,241 Sommige factor n trappen, dat is de ondergrens. 364 00:17:36,241 --> 00:17:36,740 Yeah? 365 00:17:36,740 --> 00:17:37,910 >> PUBLIEK: Bubble soort? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble sort neemt je minimaal n stappen, waarom? 367 00:17:41,610 --> 00:17:42,279 Waarom is dat? 368 00:17:42,279 --> 00:17:45,320 Waarom zou dat het begin tot het naar je toe komen intuïtief, zelfs als het niet alleen 369 00:17:45,320 --> 00:17:46,530 nog? 370 00:17:46,530 --> 00:17:47,030 Yeah? 371 00:17:47,030 --> 00:17:47,990 >> PUBLIEK: [onverstaanbaar]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Precies. 374 00:17:52,360 --> 00:17:55,810 In de best mogelijke scenario van bubble sort, en een heleboel algoritmen, 375 00:17:55,810 --> 00:17:58,769 als ik geef je acht mensen die al zijn gesorteerd, 376 00:17:58,769 --> 00:18:00,560 Het zou dwaas zijn voor u, het algoritme, 377 00:18:00,560 --> 00:18:02,202 om heen en weer te gaan meer dan een keer, toch? 378 00:18:02,202 --> 00:18:04,285 Want zodra je loop door de lijst een keer, 379 00:18:04,285 --> 00:18:08,090 U dient zich te realiseren, oh, heb ik geen swaps, wordt deze lijst gesorteerd exit. 380 00:18:08,090 --> 00:18:09,700 Maar dat gaat je n stappen te ondernemen. 381 00:18:09,700 --> 00:18:12,033 >> En omgekeerd, wat is een andere manier van denken over het? 382 00:18:12,033 --> 00:18:15,240 Bubble sort is een omega, zo te zeggen, van n, 383 00:18:15,240 --> 00:18:19,050 want als je kijkt naar minder dan n elementen, welke 384 00:18:19,050 --> 00:18:23,009 is het fundamentele probleem daar? 385 00:18:23,009 --> 00:18:24,550 Je weet niet of het is gesorteerd rechts. 386 00:18:24,550 --> 00:18:26,800 Wij mensen macht blik op acht mensen en zijn als, oh, is het opgelost, 387 00:18:26,800 --> 00:18:28,430 dat heeft me n stappen niet te nemen, maar het deed. 388 00:18:28,430 --> 00:18:30,810 Je ogen, ook al heb je soort van een groot gezichtsveld, 389 00:18:30,810 --> 00:18:33,184 je keek naar acht elementen, je keek naar acht mensen, 390 00:18:33,184 --> 00:18:34,610 dat is acht stappen effectief. 391 00:18:34,610 --> 00:18:38,612 En alleen als ik door een hele lijst besef ik, ja, gesorteerd. 392 00:18:38,612 --> 00:18:41,320 Als ik halverwege stoppen denken, alle recht, het is mooi zo ver gesorteerd 393 00:18:41,320 --> 00:18:42,520 wat zijn de kansen dat het niet gesorteerd? 394 00:18:42,520 --> 00:18:44,186 Dat algoritmes niet van plan juist te zijn. 395 00:18:44,186 --> 00:18:46,250 Misschien sneller, maar onjuist. 396 00:18:46,250 --> 00:18:48,500 >> Dus nu hebben we een manier van het beschrijven van een ondergrenzen, 397 00:18:48,500 --> 00:18:49,710 en hoe zit het met constante tijd? 398 00:18:49,710 --> 00:18:54,565 Wat is een algoritme dat een lager is gebonden aan de looptijd van een? 399 00:18:54,565 --> 00:18:58,350 1 stap, 2 stappen, 10 stappen, maar constant, onafhankelijk van n, 400 00:18:58,350 --> 00:18:59,310 de grootte van de input? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Ja, in de rug. 403 00:19:04,600 --> 00:19:05,309 >> PUBLIEK: Printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Wat is dat? 405 00:19:06,183 --> 00:19:07,184 PUBLIEK: Printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: Printf. 407 00:19:07,850 --> 00:19:08,400 OK, zeker. 408 00:19:08,400 --> 00:19:10,720 Zo draait vast aantal stappen. 409 00:19:10,720 --> 00:19:13,170 En ik zou nu dat nu-- we hebben het over de C-code 410 00:19:13,170 --> 00:19:16,040 en niet Scratch, iets zoals bijvoorbeeld met printf, 411 00:19:16,040 --> 00:19:17,710 we moeten beginnen om voorzichtig te krijgen. 412 00:19:17,710 --> 00:19:21,090 Omdat printf neemt ingang, het is een string, 413 00:19:21,090 --> 00:19:23,220 en snaren technisch hebben lengte. 414 00:19:23,220 --> 00:19:25,530 Dus als we nu willen halen op je, als je het niet erg vindt, 415 00:19:25,530 --> 00:19:29,430 technisch gezien konden we dat printf argumenteren ofwel een variabele lengte invoer vragen, 416 00:19:29,430 --> 00:19:32,270 en toch kan het langer duren tijd om een ​​string zo lang af te drukken, 417 00:19:32,270 --> 00:19:33,560 dan deze lang. 418 00:19:33,560 --> 00:19:36,570 >> Dus wat als we kijken naar alleen de het sorteren en zoeken voorbeelden? 419 00:19:36,570 --> 00:19:40,450 Hoe zit het met Mike Smith in de telefoon boek, of binaire zoeken meer in het algemeen? 420 00:19:40,450 --> 00:19:42,220 In het beste geval, wat er kan gebeuren? 421 00:19:42,220 --> 00:19:45,577 Ik het telefoonboek te openen en, bam, er is nummer Mike Smith. 422 00:19:45,577 --> 00:19:46,660 Ik kan hem meteen bellen. 423 00:19:46,660 --> 00:19:49,390 >> Deed een stap, misschien twee stappen, maar een constant aantal stappen 424 00:19:49,390 --> 00:19:50,230 als ik heb geluk gehad. 425 00:19:50,230 --> 00:19:52,570 En eerlijk gezegd, we zagen op Maandag jouw klasgenoot 426 00:19:52,570 --> 00:19:54,710 behoorlijk geluk twee keer op een rij. 427 00:19:54,710 --> 00:19:57,050 En dat was inderdaad constant tijd in een ondergrenzen 428 00:19:57,050 --> 00:20:01,280 aan het algoritme voor het vinden betrokken het nummer 50 achter die gesloten 429 00:20:01,280 --> 00:20:01,830 deuren. 430 00:20:01,830 --> 00:20:06,400 >> Nu, als een terzijde, als je ontdekt dat zowel grote O, de bovengrens 431 00:20:06,400 --> 00:20:09,310 en omega, de ondergrens, zijn een en hetzelfde, dat 432 00:20:09,310 --> 00:20:11,830 is dezelfde formule haakjes, kunt u ook 433 00:20:11,830 --> 00:20:15,170 zeggen, gewoon om te fancy, dat iets in theta 434 00:20:15,170 --> 00:20:18,270 van n of theta van een andere waarde. 435 00:20:18,270 --> 00:20:20,661 Dat betekent dat alleen wanneer grote O en omega zijn hetzelfde. 436 00:20:20,661 --> 00:20:21,910 Nu wat over selectie soort? 437 00:20:21,910 --> 00:20:23,400 Laten we gebruik maken van deze nieuwe woordenschat. 438 00:20:23,400 --> 00:20:27,407 In de selectie sorteren, wat waren we opnieuw doen, en opnieuw, en opnieuw? 439 00:20:27,407 --> 00:20:29,990 Ik werd heen en weer gaan door de lijst, op zoek naar wie? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Het kleinste getal. 442 00:20:34,730 --> 00:20:37,560 >> Dus hoeveel stappen, hoe veel vergelijkingen heb ik 443 00:20:37,560 --> 00:20:43,250 moeten maken om erachter te komen wie het kleinste element in de lijst stond? 444 00:20:43,250 --> 00:20:44,437 n minus 1, toch? 445 00:20:44,437 --> 00:20:47,770 Want als ik gewoon beginnen met degene die ik ben gegeven en ik begin hem of haar te vergelijken, 446 00:20:47,770 --> 00:20:49,519 dan hem of haar, hem of haar, hem of haar, ik 447 00:20:49,519 --> 00:20:52,010 kan alleen elementen te koppelen samen n minus 1 keer. 448 00:20:52,010 --> 00:20:55,630 Dus selectie neemt soort op dezelfde manier n minus 1 stappen de eerste keer. 449 00:20:55,630 --> 00:20:59,540 >> Hoeveel stappen duurt het me te vind het op een na kleinste element? 450 00:20:59,540 --> 00:21:02,920 n minus 2, want ik ben dom Als ik blijf kijken naar dezelfde mensen 451 00:21:02,920 --> 00:21:06,280 weer als ik heb hem reeds geselecteerd of haar en zet ze op hun plaats. 452 00:21:06,280 --> 00:21:09,270 En de derde stap, n minus 3, dan is n minus 4. 453 00:21:09,270 --> 00:21:11,020 We hebben dit patroon gezien vóór en zelfs 454 00:21:11,020 --> 00:21:13,460 selectie sorteren op dezelfde manier heeft een bovengrens 455 00:21:13,460 --> 00:21:16,210 van n kwadraat als we dat doen tot dat sommatie. 456 00:21:16,210 --> 00:21:19,790 Wat is de ondergrens, selectie sorteren? 457 00:21:19,790 --> 00:21:25,350 Minimaal, hoeveel tijd moet selectie soort nemen, zoals we het gedefinieerd op maandag? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Stellen twee opties. 460 00:21:30,490 --> 00:21:32,360 Misschien is het n, zoals voorheen. 461 00:21:32,360 --> 00:21:35,040 Misschien is het n kwadraat, zoals het is nu als de bovengrens. 462 00:21:35,040 --> 00:21:35,874 >> PUBLIEK: n kwadraat. 463 00:21:35,874 --> 00:21:36,664 Spreker: n kwadraat. 464 00:21:36,664 --> 00:21:37,368 Waarom? 465 00:21:37,368 --> 00:21:40,060 >> PUBLIEK: Omdat je om [onverstaanbaar] definiëren. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Precies. 467 00:21:41,510 --> 00:21:45,077 Tenminste als ik selectie soort gedefinieerd het was behoorlijk naïef, blijven gaan, 468 00:21:45,077 --> 00:21:46,160 voorbeeld de kleinste element. 469 00:21:46,160 --> 00:21:47,770 Ga weer, vind het kleinste element. 470 00:21:47,770 --> 00:21:49,490 Ga weer, vind het kleinste element. 471 00:21:49,490 --> 00:21:51,700 Er is geen soort van optimalisatie in dat er 472 00:21:51,700 --> 00:21:54,350 misschien laat me af te breken na gewoon n of zo stappen. 473 00:21:54,350 --> 00:21:57,080 Dus inderdaad selectie soort, omega van n kwadraat. 474 00:21:57,080 --> 00:22:00,667 >> Hoe zit het insertion sort, waar ik nam die ik kreeg, en vervolgens hem plofte ik 475 00:22:00,667 --> 00:22:01,750 of haar op de juiste plaats? 476 00:22:01,750 --> 00:22:04,958 Daarna ging ik naar de tweede persoon, plofte hem of haar op de juiste plek. 477 00:22:04,958 --> 00:22:07,910 Dan is de volgende persoon, plofte hem of haar op de juiste plek. 478 00:22:07,910 --> 00:22:10,537 Merk op dat dit zeer lineaire, zo te zeggen. 479 00:22:10,537 --> 00:22:12,620 Ik ben een rechte lijn, ik ben niet heen en weer gaan, 480 00:22:12,620 --> 00:22:16,080 Ik heb nooit terug te kijken echt, maar wat er gebeurt als ik hem in te voegen 481 00:22:16,080 --> 00:22:20,302 of haar in het begin van de lijst zoals wij deden op maandag? 482 00:22:20,302 --> 00:22:21,010 Wat gebeurt er? 483 00:22:21,010 --> 00:22:21,510 Yeah? 484 00:22:21,510 --> 00:22:23,122 PUBLIEK: [onverstaanbaar]. 485 00:22:23,122 --> 00:22:24,830 Spreker: Ja, dat was de vangst, toch? 486 00:22:24,830 --> 00:22:26,746 U herinnert zich nog wel uit je klasgenoten, indien zij 487 00:22:26,746 --> 00:22:29,670 maakten elke beweging met hun voeten, dat is een operatie. 488 00:22:29,670 --> 00:22:33,610 Dus als er drie mensen hier en de nieuwe persoon behoorde daar weg over, 489 00:22:33,610 --> 00:22:37,360 op een lange etappe als deze, zeker, hij of ze kon gewoon naar het einde. 490 00:22:37,360 --> 00:22:40,074 Maar als we denken over een computer en een reeks geheugencellen, 491 00:22:40,074 --> 00:22:41,990 deze mensen gaan moeten dan schudden 492 00:22:41,990 --> 00:22:43,260 om ruimte voor die persoon te maken. 493 00:22:43,260 --> 00:22:46,930 En zo dat n minus 1 uitvluchten, n minus 2 uitvluchten, n 494 00:22:46,930 --> 00:22:50,660 min 3 uitvluchten is gewoon een soort van er achter mij, niet voor mij 495 00:22:50,660 --> 00:22:52,710 zoals eerder, in zekere zin. 499 00:22:52,557 --> 00:22:54,640 Nu nog even terzijde, en als je zou online hebt gezien 500 00:22:54,640 --> 00:22:57,699 als je begint rondneuzen over soorten, er zijn zoveel verschillende degenen 501 00:22:57,699 --> 00:22:59,490 die er zijn, een aantal van hen beter dan anderen. 502 00:22:59,490 --> 00:23:02,200 Inderdaad, bogosort is een dat is wel leuk om te kijken. 503 00:23:02,200 --> 00:23:06,650 Bogosort neemt een set van nummers of zeggen een spel kaarten, 504 00:23:06,650 --> 00:23:09,870 willekeurig schudt hen, en controleert of ze gesorteerd worden. 505 00:23:09,870 --> 00:23:12,130 En zo niet, doet het weer. 506 00:23:12,130 --> 00:23:14,140 En zo niet, doet het weer. 507 00:23:14,140 --> 00:23:15,440 Zo niet, dan doet het weer. 508 00:23:15,440 --> 00:23:17,060 Ongelooflijk dom. 509 00:23:17,060 --> 00:23:19,520 >> En inderdaad, als je leest zoals het artikel van Wikipedia, 510 00:23:19,520 --> 00:23:21,200 zijn bijnaam is dom soort. 511 00:23:21,200 --> 00:23:25,180 Het zal uiteindelijk werken, hopelijk genoeg tijd, 512 00:23:25,180 --> 00:23:28,240 maar die tijd kan geruime tijd in beslag nemen. 513 00:23:28,240 --> 00:23:31,650 Dus als ik zou kunnen, laten we snel dingen up van Mary Beth's bijvoorbeeld eerder, 514 00:23:31,650 --> 00:23:35,150 Door een paar elementen, maar twee processors. 515 00:23:35,150 --> 00:23:37,100 Twee mensen, als je zou het niet erg mee me. 516 00:23:37,100 --> 00:23:40,972 Wat dacht je van 1 hier, en laten we gaan-- niemand daar? 517 00:23:40,972 --> 00:23:41,722 Niemand daar? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 U met de zwarte shirt, ja, kom naar beneden. 520 00:23:44,190 --> 00:23:45,000 Oke, wat is uw naam? 521 00:23:45,000 --> 00:23:45,720 >> PUBLIEK: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Wat is dat? 523 00:23:46,100 --> 00:23:46,766 >> PUBLIEK: Peter. 524 00:23:46,766 --> 00:23:49,450 Spreker: Peter, David, leuk je te ontmoeten. 525 00:23:49,450 --> 00:23:53,670 Oke, we hebben Peter hier, als je wil op de tafel te komen hier. 526 00:23:53,670 --> 00:23:54,550 En wat is uw naam? 527 00:23:54,550 --> 00:23:55,216 >> PUBLIEK: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, leuk je te ontmoeten. 530 00:23:57,030 --> 00:23:58,060 Elena ontmoet Peter. 531 00:23:58,060 --> 00:23:59,170 Peter, Elena. 532 00:23:59,170 --> 00:24:02,290 En we zullen Andrew nodig hier ook, alstublieft. 533 00:24:02,290 --> 00:24:06,107 En uw uitdaging gaat te zijn om een ​​spel kaarten afstand. 534 00:24:06,107 --> 00:24:08,190 En als onbekende, dek kaarten moet uiteindelijk 535 00:24:08,190 --> 00:24:11,064 gesorteerd worden een beetje iets als dit waar we de clubs doen, dan 536 00:24:11,064 --> 00:24:13,660 het schoppen, dan de harten en diamanten, van aas als een een, 537 00:24:13,660 --> 00:24:15,570 helemaal tot aan de koning. 538 00:24:15,570 --> 00:24:20,890 >> De kaarten die ik je ga geven gaan worden 52 in kwantiteit. 539 00:24:20,890 --> 00:24:23,160 We gaan op dezelfde manier keer dat u, in slechts een moment. 540 00:24:23,160 --> 00:24:26,410 We gaan Andrew gooien up hier het scherm, 541 00:24:26,410 --> 00:24:28,170 om zo naar te kijken als je dit doet. 542 00:24:28,170 --> 00:24:31,070 En zodat alles is des te zichtbaarder 543 00:24:31,070 --> 00:24:33,490 Dit zijn de kaarten die ik kreeg op Amazon. 544 00:24:33,490 --> 00:24:42,861 Dus ze zijn al willekeurig gesorteerd zijn, en we zullen u tijd. 545 00:24:42,861 --> 00:24:44,610 En we gaan houd het echt deze keer, 546 00:24:44,610 --> 00:24:47,820 dus we gaan proberen om je onder druk te zetten omdat anders deze vervelende krijgt 547 00:24:47,820 --> 00:24:48,460 snel. 548 00:24:48,460 --> 00:24:53,860 Als je zou kunnen gaan om te sorteren 52 elementen aan elkaar gekoppeld via een middel, nu. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> En nogmaals, als we kijken naar deze jongens doen wat, in het einde 551 00:25:07,180 --> 00:25:10,200 gaat om een ​​voor de hand liggende te produceren resultaat, na te denken over echt 552 00:25:10,200 --> 00:25:12,962 hoe ze elkaar doen, hoe zou je het kunnen omschrijven. 553 00:25:12,962 --> 00:25:15,045 Omdat weer, deze alle processen, algoritmen 554 00:25:15,045 --> 00:25:17,090 die we voor lief nemen als mens. 555 00:25:17,090 --> 00:25:22,349 Maar je hebt waarschijnlijk al lang gehad intuïtie, al voordat u de 556 00:25:22,349 --> 00:25:24,390 nagedacht over het nemen van een computer science class u 557 00:25:24,390 --> 00:25:27,223 zou de intuïtie hebben gehad met die om dit soort problemen op te lossen. 558 00:25:27,223 --> 00:25:29,560 Maar als je eenmaal herkent de patronen en beginnen 559 00:25:29,560 --> 00:25:32,407 de stappen waarmee formaliseren u het oplossen van deze problemen, 560 00:25:32,407 --> 00:25:35,490 je zult zien dat je veel kunt oplossen interessanter en veel complexer 561 00:25:35,490 --> 00:25:39,190 problemen snel. 562 00:25:39,190 --> 00:25:42,351 Dus iemand uit het publiek, wat is tenminste een element van het algoritme 563 00:25:42,351 --> 00:25:43,350 dat ze hier gebruik van? 564 00:25:43,350 --> 00:25:44,275 >> PUBLIEK: [onverstaanbaar] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Wat is dat? 566 00:25:45,150 --> 00:25:47,062 Publiek: Door pak. 567 00:25:47,062 --> 00:25:47,770 Spreker: Door pak. 568 00:25:47,770 --> 00:25:50,630 Dus eerst zijn ze te clusteren alle diamanten samen 569 00:25:50,630 --> 00:25:52,560 Het lijkt alle harten samen zo lijkt het, 570 00:25:52,560 --> 00:25:56,520 enzovoort, zonder respect de enkele speelkaarten. 571 00:25:56,520 --> 00:26:00,900 En nu lijken ze, bijvoorbeeld, worden ze te sorteren op nummer. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Zeer goed. 574 00:26:08,910 --> 00:26:12,370 >> Oke, dus wat er gaat zijn de laatste stap dan hier? 575 00:26:12,370 --> 00:26:16,950 Zodra we hebben vier gesorteerde pakken, wat doen wat we moeten doen om de vier palen 576 00:26:16,950 --> 00:26:20,059 teneinde een verwezenlijken naargelang dek, heel eenvoudig? 577 00:26:20,059 --> 00:26:21,350 Dus moeten we ze weer samen te voegen. 578 00:26:21,350 --> 00:26:25,160 >> Dus er is een interessant idee dat weer, durf te zeggen, is zeer intuïtief, zelfs 579 00:26:25,160 --> 00:26:28,140 als je nooit zou hebben geslagen dat soort label op. 580 00:26:28,140 --> 00:26:31,900 Deze fundamentele notie van te delen het probleem niet in de helft deze tijd, 581 00:26:31,900 --> 00:26:33,410 maar in ieder geval in vier stukken. 582 00:26:33,410 --> 00:26:36,810 Het oplossen van vrijwel fundamenteel identieke problemen 583 00:26:36,810 --> 00:26:40,480 los van elkaar, en dan is het samenvoegen van de resultaten. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 En, uitstekend, gedaan. 586 00:26:50,140 --> 00:26:52,140 Oke, een grote ronde applaus, als we konden. 587 00:26:52,140 --> 00:26:56,480 >> [Applaus] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Ik heb geen idee wat je zult doen met deze, maar hier ga je. 589 00:26:59,740 --> 00:27:01,690 Dank je wel. 590 00:27:01,690 --> 00:27:04,660 Dus laten we eens kijken, twee minuten en acht seconden, 591 00:27:04,660 --> 00:27:07,490 Indien u graag uw vrienden uit te dagen. 592 00:27:07,490 --> 00:27:12,160 Wat daarna gaat zijn een neem afstand van deze 593 00:27:12,160 --> 00:27:13,830 dat we meer in het algemeen kunnen benutten? 594 00:27:13,830 --> 00:27:16,080 Nou, denk terug aan Deze matrix van getallen, 595 00:27:16,080 --> 00:27:19,060 en denk nu terug naar een aantal van de pseudocode we in het verleden heb geschreven, 596 00:27:19,060 --> 00:27:22,080 en dit was de pseudocode voor het oplossen van het telefoonboek probleem. 597 00:27:22,080 --> 00:27:25,150 Waarbij in pseudocode I opgesomd een meer methodische manier 598 00:27:25,150 --> 00:27:28,400 beschrijven hoe ik het deed een zeer intuïtieve menselijke algoritme van de telefoon verdelen 599 00:27:28,400 --> 00:27:31,650 boek in de helft, herhalen, herhalen, herhalen, totdat ik vind iemand als Mike Smith, 600 00:27:31,650 --> 00:27:33,790 Als hij inderdaad in het telefoonboek. 601 00:27:33,790 --> 00:27:37,610 >> Maar ik soort gebruikt wat ik zal noemen een zeer iteratieve aanpak hier, 602 00:27:37,610 --> 00:27:42,160 met name indicatieregel 8 en regel 11. 603 00:27:42,160 --> 00:27:46,750 Die zijn het bewijs van een iteratief aanpak, een looping aanpak, 604 00:27:46,750 --> 00:27:49,040 want dat is precies het gedrag dat ze veroorzaken. 605 00:27:49,040 --> 00:27:52,910 Die lijnen beide zeggen ga naar lijn drie, en je kan soort 606 00:27:52,910 --> 00:27:55,140 denk aan die in uw geestesoog als een lus. 607 00:27:55,140 --> 00:27:59,080 Het vertelt je om terug te gaan tot stap drie en herhalen, opnieuw, en opnieuw, 608 00:27:59,080 --> 00:28:00,010 en weer. 609 00:28:00,010 --> 00:28:04,410 >> Maar wat als we benutten een belangrijke idee hier dat we niet de laatste keer, 610 00:28:04,410 --> 00:28:10,280 en vereenvoudiging van lijn 8 en lijn 11 en hun buren 611 00:28:10,280 --> 00:28:12,840 als alleen deze, in geel. 612 00:28:12,840 --> 00:28:16,480 Het is niet fundamenteel verkorten de pseudocode heel veel, 613 00:28:16,480 --> 00:28:20,530 maar het is fundamenteel veranderen de aard van mijn algoritme. 614 00:28:20,530 --> 00:28:24,220 Wat ik nu zeg in stap 7, in stap 10, 615 00:28:24,220 --> 00:28:29,140 is om te zoeken naar Mike op dezelfde manier, 616 00:28:29,140 --> 00:28:31,580 maar gewoon in de linker helft of de rechter helft. 617 00:28:31,580 --> 00:28:33,420 >> Dus in andere woorden, als Ik begin bij stap een, 618 00:28:33,420 --> 00:28:36,150 pick-up telefoonboek open voor midden van telefoonboek, kijk naar de namen, 619 00:28:36,150 --> 00:28:39,010 Als Smith is onder naam, bel Mike, anders 620 00:28:39,010 --> 00:28:44,340 Als Smith eerder in het boek is, stap zeven zoeken naar Mike in de linker helft van het boek. 621 00:28:44,340 --> 00:28:47,130 Maar dat soort voelt als het is laat me opknoping, toch? 622 00:28:47,130 --> 00:28:49,240 In geel, een instructie, maar hoe doe ik 623 00:28:49,240 --> 00:28:51,870 zoek Mike in de linker de helft van het telefoonboek? 624 00:28:51,870 --> 00:28:54,210 Waar heb ik een algoritme waarmee ik 625 00:28:54,210 --> 00:28:57,100 kunnen zoeken naar iemand als Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Nou, het staren ons in het gezicht. 627 00:28:58,980 --> 00:29:03,090 Ik kan letterlijk exact dezelfde gebruiken programma effectief te gaan naar de top 628 00:29:03,090 --> 00:29:06,490 opnieuw en opnieuw te lopen dezelfde regels code. 629 00:29:06,490 --> 00:29:10,610 >> Dus hoewel dit moet voelen als een beetje een cyclische definitie 630 00:29:10,610 --> 00:29:13,480 waar je het beantwoorden van iemand is vraag door gewoon soort van vragen 631 00:29:13,480 --> 00:29:15,990 dezelfde vraag weer, zoals waarom, waarom, waarom? 632 00:29:15,990 --> 00:29:21,580 De realiteit is dat we moeilijk hebben gecodeerd een paar van de speciale lijnen, stap 4, 633 00:29:21,580 --> 00:29:25,320 die een als en stap 12, waarin is in feite een andere tak, 634 00:29:25,320 --> 00:29:30,120 want we hebben deze noodmaatregelen, Dit algoritme zal worden beëindigd als we 635 00:29:30,120 --> 00:29:32,050 vindt Mike, of als we dat niet doen. 636 00:29:32,050 --> 00:29:36,810 Maar in stap 7 en 10 nu, we hebben wat we een recursieve algoritme zullen noemen. 637 00:29:36,810 --> 00:29:40,420 En recursie is inderdaad een krachtig idee dat is een beetje geest buigen op het eerste, 638 00:29:40,420 --> 00:29:42,500 dat kunnen we nu als volgt toe. 639 00:29:42,500 --> 00:29:46,600 >> Merge soort is de laatste soort zijn dat we kijken, althans in klasse formeel. 640 00:29:46,600 --> 00:29:50,040 En het is fundamenteel verschillend van die laatste drie, en zeker 641 00:29:50,040 --> 00:29:52,140 laatste vier als we onder bogosort. 642 00:29:52,140 --> 00:29:54,810 Hier is de pseudocode voor merge sort. 643 00:29:54,810 --> 00:30:00,170 Wanneer op de ingang van n elementen, dus gegeven een array van grootte n, indien n kleiner is dan 2, 644 00:30:00,170 --> 00:30:01,040 terugkeren. 645 00:30:01,040 --> 00:30:03,610 Dus waarom moet ik dat sanity check eerst? 646 00:30:03,610 --> 00:30:09,477 Wat is de implicatie of ik geef je een array waarvan de lengte n minder dan 2? 647 00:30:09,477 --> 00:30:11,060 Het is al naargelang, natuurlijk, toch? 648 00:30:11,060 --> 00:30:13,640 Omdat de lijst heeft ofwel een element, dat is triviaal 649 00:30:13,640 --> 00:30:15,180 naargelang omdat het het enige wat er. 650 00:30:15,180 --> 00:30:18,138 Of, het is van size zero wat betekent er is niets om te sorteren, dus door de natuur 651 00:30:18,138 --> 00:30:18,720 wordt gesorteerd. 652 00:30:18,720 --> 00:30:20,410 Er is gewoon niets aan de hand daar. 653 00:30:20,410 --> 00:30:22,310 Dus dat is onze zogenaamde basisscenario. 654 00:30:22,310 --> 00:30:24,440 >> Dat is in dezelfde geest met wat we hebben gedaan met Mike. 655 00:30:24,440 --> 00:30:26,023 Als Mike's in het telefoonboek, bel hem. 656 00:30:26,023 --> 00:30:27,740 Als hij er niet is, op te geven. 657 00:30:27,740 --> 00:30:31,240 Het is een zogenaamde base case, ervoor zorgen Dit algoritme aan het eind van de dag 658 00:30:31,240 --> 00:30:33,540 stopt in bepaalde omstandigheden. 659 00:30:33,540 --> 00:30:37,890 >> Maar hier is de sprong van het geloof nu, anders, sorteren de linkerhelft van de elementen, 660 00:30:37,890 --> 00:30:39,740 Vervolgens sorteert de juiste helft van de elementen, 661 00:30:39,740 --> 00:30:41,189 en dan fuseren de gesorteerde helften. 662 00:30:41,189 --> 00:30:43,230 En hier is waar het voelt alsof we betrappen uit. 663 00:30:43,230 --> 00:30:46,900 Ik heb je gevraagd om te sorteren n elementen, en ik ben 664 00:30:46,900 --> 00:30:50,712 zeggen, OK, doe het door het sorteren de links en het sorteren van de juiste. 665 00:30:50,712 --> 00:30:52,420 Maar ik zeg een ander ding, en dit 666 00:30:52,420 --> 00:30:55,530 is het centrale thema lijkt in de intuïtie tot nu toe, 667 00:30:55,530 --> 00:30:57,380 er is deze derde stap van het samenvoegen. 668 00:30:57,380 --> 00:31:00,430 Welke ook al lijkt zo dom in de geest, 669 00:31:00,430 --> 00:31:02,320 als enkel dingen samenvoegen vormen, ligt het 670 00:31:02,320 --> 00:31:05,380 een belangrijke stap in de richting van de te montage van twee problemen die 671 00:31:05,380 --> 00:31:07,330 werden uiteindelijk in tweeën gedeeld. 672 00:31:07,330 --> 00:31:12,090 >> Dus samenvoegen soort, laten we dit doen, als U humor me, met nog een demonstratie, 673 00:31:12,090 --> 00:31:14,730 gewoon zo dat we een aantal nummers om mee te werken. 674 00:31:14,730 --> 00:31:19,470 Kan ik wisselen acht spanning ballen voor acht personen? 675 00:31:19,470 --> 00:31:29,320 Oke, wat dacht je van drie, je vier in deze sectie, vijf, zes, en laten we 676 00:31:29,320 --> 00:31:30,720 do 7, 8, kom op. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, ja OK. 679 00:31:36,520 --> 00:31:38,640 Minus 8, daar gaan we, plus 1. 680 00:31:38,640 --> 00:31:39,150 Excellent. 681 00:31:39,150 --> 00:31:42,000 Oke kom op, laten we snel geef je nummers. 682 00:31:42,000 --> 00:31:50,800 Nummer twee, nummer drie, nummer vier, nummer vijf, zes, zeven en acht. 683 00:31:50,800 --> 00:31:52,140 Ik heb acht juist dit keer. 684 00:31:52,140 --> 00:31:56,390 >> OK, dus ga je gang als je kon, en laten we afstand in de oorspronkelijke volgorde 685 00:31:56,390 --> 00:31:59,810 dat we gisteren hadden die keek als dit, als je het niet erg. 686 00:31:59,810 --> 00:32:03,620 En we doen het in de voorkant van de tafel. 687 00:32:03,620 --> 00:32:06,510 Oke, dus samenvoegen soort. 688 00:32:06,510 --> 00:32:08,820 Dit is waar het gaat om vorm te krijgen van interessante, 689 00:32:08,820 --> 00:32:12,800 omdat ik lijken te geven van mezelf dus veel minder informatie vandaag. 690 00:32:12,800 --> 00:32:15,149 >> Dus samenvoegen soort allereerst de input van de n elementen, 691 00:32:15,149 --> 00:32:18,440 en is duidelijk niet minder dan twee, is het acht, dus ik heb nog wat werk te doen. 692 00:32:18,440 --> 00:32:21,140 Dus nu mentaal wij als klas zijn nu in de andere tak, 693 00:32:21,140 --> 00:32:22,540 wat betekent drie stappen. 694 00:32:22,540 --> 00:32:25,017 Allereerst, ik moet de afstand linkerhelft van de elementen. 695 00:32:25,017 --> 00:32:26,350 Dus hoe ga ik dat doen? 696 00:32:26,350 --> 00:32:28,950 Nou, ik ga soort hier mentaal verdelen de lijst, 697 00:32:28,950 --> 00:32:30,700 je hoeft niet te fysiek te verplaatsen, en ik ben 698 00:32:30,700 --> 00:32:33,180 zal zich op de linkerhelft van de elementen hier. 699 00:32:33,180 --> 00:32:36,770 Dus hoe ga ik over het sorteren nu van grootte vier een lijst? 700 00:32:36,770 --> 00:32:38,730 Wat is mijn algoritme? 701 00:32:38,730 --> 00:32:42,580 Eerst heb ik controleren is n minder dan twee, nee, dus ik ga naar de else blok weer. 702 00:32:42,580 --> 00:32:43,900 Sorteer linkerhelft van elementen. 703 00:32:43,900 --> 00:32:45,608 >> Dus nu opnieuw, mentaal, en dit is waar 704 00:32:45,608 --> 00:32:49,550 je moet heel veel ten goede mentale geschiedenis, als je wil. 705 00:32:49,550 --> 00:32:51,940 Nu ben ik het sorteren van de linker helft van de linkerhelft. 706 00:32:51,940 --> 00:32:57,000 Oke, dus nu noem ik mijn dezelfde merge sorteer-algoritme, is n minder dan twee? 707 00:32:57,000 --> 00:33:00,590 Nee, het is twee, dus ik heb om te sorteren de linker helft en de rechter helft. 708 00:33:00,590 --> 00:33:02,042 Dus hier gaan we, sorteert de linker helft. 709 00:33:02,042 --> 00:33:03,750 Waarom doe je niet zomaar een stap vooruit. 710 00:33:03,750 --> 00:33:04,415 Wat is je naam? 711 00:33:04,415 --> 00:33:04,860 >> PUBLIEK: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan is naar voren stapte. 714 00:33:06,040 --> 00:33:06,748 >> PUBLIEK: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, gedaan. 716 00:33:09,000 --> 00:33:10,090 Wist u Darren of Dan zeggen? 717 00:33:10,090 --> 00:33:10,550 >> PUBLIEK: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren is gestapt naar voren en hij wordt nu gesorteerd worden. 720 00:33:14,422 --> 00:33:16,130 En dit is bijna een zinloze claim, toch? 721 00:33:16,130 --> 00:33:18,862 Ik heb niet echt lijken te bereiken wat dan ook, maar laten we gaan. 722 00:33:18,862 --> 00:33:20,820 Laat me nu afstand van de juiste helft van de elementen. 723 00:33:20,820 --> 00:33:21,200 Wat is je naam? 724 00:33:21,200 --> 00:33:21,690 >> PUBLIEK: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Luke. 726 00:33:22,273 --> 00:33:23,400 Kom op, stap naar voren. 727 00:33:23,400 --> 00:33:25,640 Gedaan, heb ik Luke gesorteerd worden. 728 00:33:25,640 --> 00:33:28,570 De linkerhelft is nu gesorteerd en de rechterhelft is nu gesorteerd, 729 00:33:28,570 --> 00:33:30,770 maar nogmaals, er is een belangrijke stap hier. 730 00:33:30,770 --> 00:33:32,940 Wat heb ik naast moet doen? 731 00:33:32,940 --> 00:33:33,941 Merge de gesorteerde helften. 732 00:33:33,941 --> 00:33:36,648 Nu gaan we gewoon iedereen heen en weer op deze manier 733 00:33:36,648 --> 00:33:38,620 omdat ik soort nodig wat scratch space. 734 00:33:38,620 --> 00:33:40,411 Het is bijna alsof deze jongens zijn op een tafel, 735 00:33:40,411 --> 00:33:42,460 en ik heb wat ruimte om hen te bewegen op. 736 00:33:42,460 --> 00:33:44,170 Dus ik ga om te fuseren jullie door te kijken 737 00:33:44,170 --> 00:33:45,960 op de linker helft en de rechter helft. 738 00:33:45,960 --> 00:33:48,740 En die uiteraard het eerst komt, linkerhelft of de rechterhelft? 739 00:33:48,740 --> 00:33:52,710 Dus rechter helft, dus laten we verder gaan Luke boven hier in de oorspronkelijke stand Darren's. 740 00:33:52,710 --> 00:33:57,640 En nu aan hun linker helft fuseren, Darren gaat om daar te verplaatsen. 741 00:33:57,640 --> 00:33:59,750 >> Dus voelt bijna een zeepbel soort effect, 742 00:33:59,750 --> 00:34:02,482 maar mijn fundamentele algoritme, heel deze keer. 743 00:34:02,482 --> 00:34:04,815 Maar nu is waar de dingen een beetje vervelend, omdat je 744 00:34:04,815 --> 00:34:06,810 moeten mentaal terugspoelen waar heb ik ophouden. 745 00:34:06,810 --> 00:34:09,893 Ik heb net gefuseerd de gesorteerde helften, wat betekent dat ik ben waar in mijn algoritme? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Ik moet de rechter helft te sorteren, toch? 748 00:34:13,770 --> 00:34:15,910 >> Als u terugspoelen, letterlijk op de video, dan heb je 749 00:34:15,910 --> 00:34:18,339 zien dat we op deze punt van Luke en Darren 750 00:34:18,339 --> 00:34:21,370 door het sorteren van de linker helft van de linkerhelft. 751 00:34:21,370 --> 00:34:23,430 Dan samengevoegd wij die gesorteerde helften, die 752 00:34:23,430 --> 00:34:27,941 : de volgende stap is het sorteren rechterhelft van de linkerhelft. 753 00:34:27,941 --> 00:34:29,649 Oke, dus laten we Dit doen sneller. 754 00:34:29,649 --> 00:34:33,282 Oke, zes, ik ga claimen U bent nu naargelang, kom op naar voren. 755 00:34:33,282 --> 00:34:33,990 Wat is je naam? 756 00:34:33,990 --> 00:34:34,589 >> PUBLIEK: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano wordt nu gesorteerd worden. 759 00:34:36,010 --> 00:34:36,450 En wat is uw naam? 760 00:34:36,450 --> 00:34:37,080 >> PUBLIEK: Alex. 761 00:34:37,080 --> 00:34:38,379 >> Spreker: Alex is nu gesorteerd worden. 762 00:34:38,379 --> 00:34:40,750 Linkerhelft, rechterhelft, wat is de laatste stap? 763 00:34:40,750 --> 00:34:41,250 Samenvoegen. 764 00:34:41,250 --> 00:34:44,310 Vrij triviaal, dus ik ben gaan samenvoegen in zes, 765 00:34:44,310 --> 00:34:46,930 neem een ​​stap terug, acht, een stap terug. 766 00:34:46,930 --> 00:34:49,530 En let nu op dit een handig mee te nemen, wat 767 00:34:49,530 --> 00:34:53,930 is nu juist over de linker helft van de lijst, ongeacht hoe we begonnen? 768 00:34:53,930 --> 00:34:55,090 Het wordt gesorteerd. 769 00:34:55,090 --> 00:34:57,750 >> Nu is het niet gesorteerd in de grote regeling van dingen, 770 00:34:57,750 --> 00:35:00,250 maar wordt onafhankelijk gesorteerd van de andere helft. 771 00:35:00,250 --> 00:35:04,100 Nu, wat stap ben ik op als ik houden terugspoelen hoe het verhaal begon? 772 00:35:04,100 --> 00:35:05,680 Nu moet ik naar de rechter helft afstand. 773 00:35:05,680 --> 00:35:07,630 Dus nu zijn we helemaal terug bij het begin van het verhaal, 774 00:35:07,630 --> 00:35:08,921 en laten we dit sneller te doen. 775 00:35:08,921 --> 00:35:11,320 Dus ik ga naar de afstand rechterhelft van de hele lijst. 776 00:35:11,320 --> 00:35:13,060 Wat is de volgende stap? 777 00:35:13,060 --> 00:35:15,840 Sorteer de linker helft van de rechter helft. 778 00:35:15,840 --> 00:35:18,715 Sorteer de linker helft van de linkerhelft van de rechterhelft. 779 00:35:18,715 --> 00:35:19,590 En wat is uw naam? 780 00:35:19,590 --> 00:35:20,230 >> PUBLIEK: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, stap voorwaarts, gedaan. 782 00:35:21,970 --> 00:35:22,860 Linkerhelft wordt gesorteerd. 783 00:35:22,860 --> 00:35:23,330 En wat is uw naam? 784 00:35:23,330 --> 00:35:23,820 >> PUBLIEK: Chris. 785 00:35:23,820 --> 00:35:25,620 >> Spreker: Chris, een stap vooruit, u bent nu gesorteerd worden. 786 00:35:25,620 --> 00:35:27,010 Wat is de belangrijkste stap nu? 787 00:35:27,010 --> 00:35:27,510 Samenvoegen. 788 00:35:27,510 --> 00:35:30,509 Dus men gaat samenvoegen in plaats hier, als je een stap terug zou kunnen nemen, 789 00:35:30,509 --> 00:35:32,930 en drie gaat neem een ​​stap terug, samen te voegen. 790 00:35:32,930 --> 00:35:38,080 Dus de linkerhelft van de rechterhelft, wordt nu gesorteerd worden. 791 00:35:38,080 --> 00:35:41,747 Eerlijk gezegd, dit algoritme voelt alsof we verspilt veel meer tijd dan voorheen, 792 00:35:41,747 --> 00:35:44,830 maar als we dit in real-time, zullen we zien wat de afhaalrestaurants gaat worden. 793 00:35:44,830 --> 00:35:47,970 Nu ben ik hier, rechts helft van de rechterhelft, 794 00:35:47,970 --> 00:35:50,170 laat me ga je gang en sorteren van de linker helft. 795 00:35:50,170 --> 00:35:51,482 Stap naar voren, wat is uw naam? 796 00:35:51,482 --> 00:35:52,190 PUBLIEK: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: Ramsey wordt nu gesorteerd worden. 798 00:35:53,210 --> 00:35:53,570 Wat is je naam? 799 00:35:53,570 --> 00:35:54,200 >> PUBLIEK: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: Marina is nu naargelang als Nou, als je een stap voorwaarts te zetten. 801 00:35:57,033 --> 00:36:00,690 Belangrijke stap hier nu samen te voegen, ben ik gaan plukken van mijn twee lijsten, 802 00:36:00,690 --> 00:36:01,720 links en rechts. 803 00:36:01,720 --> 00:36:05,150 Vijf gaat wie het eerst komt, en zeven gaat naar de volgende te komen. 804 00:36:05,150 --> 00:36:06,410 En nogmaals, dit is een bewuste keuze. 805 00:36:06,410 --> 00:36:08,535 Het feit dat ze nemen stappen vooruit en achteruit 806 00:36:08,535 --> 00:36:12,997 is bedoeld om te vertegenwoordigen dat we kunnen niet doen dit algoritme in plaats zo gemakkelijk 807 00:36:12,997 --> 00:36:15,830 als bubble sort, en selectie sorteren en insertion sort waar we net 808 00:36:15,830 --> 00:36:16,960 gehouden swapping mensen. 809 00:36:16,960 --> 00:36:19,940 Ik heb letterlijk een soort nodig van kladpapier waarin 810 00:36:19,940 --> 00:36:21,827 om deze mensen zetten terwijl ik de samenvoeging, 811 00:36:21,827 --> 00:36:23,410 en dan kan ik ze terug te plaatsen. 812 00:36:23,410 --> 00:36:27,260 En dat is belangrijk, want ik ben met behulp van een nieuwe bron, ruimte, niet alleen de tijd. 813 00:36:27,260 --> 00:36:28,270 >> OK, dit is geweldig. 814 00:36:28,270 --> 00:36:32,050 Linkerhelft wordt gesorteerd, rechter helft is gesorteerde, nu die sleutel samenvoegen stap. 815 00:36:32,050 --> 00:36:33,450 Hoe ga ik deze samenvoegen? 816 00:36:33,450 --> 00:36:35,470 Dus als je volg mijn linker en rechter, 817 00:36:35,470 --> 00:36:38,930 Ik ga mijn linkerhand wijzen op de linker helft, mijn rechterhand 818 00:36:38,930 --> 00:36:42,680 op de rechter helft, en nu moet ik beslissen stap voor stap wie te fuseren. 819 00:36:42,680 --> 00:36:44,650 Die uiteraard op de eerste plaats? 820 00:36:44,650 --> 00:36:45,150 Nummer een. 821 00:36:45,150 --> 00:36:47,327 Dus kom eens hier, hier is onze kladblok. 822 00:36:47,327 --> 00:36:49,910 Dus nu nummer een, en de mededeling wat ik ga doen met mijn rechterhand, 823 00:36:49,910 --> 00:36:54,152 Ik ga mijn rechterhand een bewegen stap over naar nummer drie wijzen, 824 00:36:54,152 --> 00:36:55,860 en nu heb ik te maken dezelfde beslissing. 825 00:36:55,860 --> 00:36:58,387 En eigenlijk sta recht in voorkant van Luke hier als u kon, 826 00:36:58,387 --> 00:36:59,720 want dit is onze kladblok. 827 00:36:59,720 --> 00:37:00,610 Dus wie komt er nu? 828 00:37:00,610 --> 00:37:05,000 We hebben Lucas met nummer twee of Chris met nummer drie. 829 00:37:05,000 --> 00:37:07,460 Uiteraard Luke, nummer twee, dus kom je hier. 830 00:37:07,460 --> 00:37:11,270 >> Maar mijn linkerhand nu gaat worden opgehoogd om te wijzen op Darren, 831 00:37:11,270 --> 00:37:15,160 en hier is de sleutel af te halen bij samenvoegen, ga ik blijven doen, 832 00:37:15,160 --> 00:37:17,340 Uiteraard, als je kind van de logica volgen. 833 00:37:17,340 --> 00:37:19,670 Maar mijn handen zijn nooit zal achteruitgaan, 834 00:37:19,670 --> 00:37:23,861 wat betekent dat ik altijd alleen maar verhuizen naar links mijn fusieproces, 835 00:37:23,861 --> 00:37:26,360 en dat gaat de sleutel tot zijn onze analyse in slechts een moment. 836 00:37:26,360 --> 00:37:27,859 >> Dus laten we nu snel afmaken up. 837 00:37:27,859 --> 00:37:31,650 Dus drie komt daarna, dan vier komt daarna, 838 00:37:31,650 --> 00:37:38,750 en nu vijf daarna komt, dan zes, en zeven, en dan uiteindelijk acht. 839 00:37:38,750 --> 00:37:42,960 Voelt als de langzaamste algoritme nog, maar niet als we eigenlijk 840 00:37:42,960 --> 00:37:45,510 voer het uit op hetzelfde soort van kloksnelheid, zo te 841 00:37:45,510 --> 00:37:48,106 spreken met dezelfde tikkende klok als voorheen. 842 00:37:48,106 --> 00:37:48,605 Waarom? 843 00:37:48,605 --> 00:37:51,100 Nou, laten we eens een kijken naar het eindresultaat. 844 00:37:51,100 --> 00:37:56,990 >> Laten we teruggaan naar hier, laat mij trek een demonstratie visueel 845 00:37:56,990 --> 00:37:59,030 van wat we net gedaan. 846 00:37:59,030 --> 00:38:06,110 Inzoomen hier, op deze pagina hier, vertellen Firefox 847 00:38:06,110 --> 00:38:08,200 dat willen we in de rij in dit vak, laten we 848 00:38:08,200 --> 00:38:11,260 zeggen bubble sort, waarmee we zijn nu goed bekend, 849 00:38:11,260 --> 00:38:14,130 selectie sorteren, wat een andere vrij eenvoudig is, 850 00:38:14,130 --> 00:38:18,250 en nu de huidige merge sort, die zal onze climax einde zijn. 851 00:38:18,250 --> 00:38:21,530 De reden dat het zo veel langer hier met mensen en mij mondeling is, 852 00:38:21,530 --> 00:38:23,480 uiteraard ben ik het uitleggen elke stap. 853 00:38:23,480 --> 00:38:26,920 Maar als je gewoon voer je dit, veel zoals we deden bubble sort en selectie 854 00:38:26,920 --> 00:38:30,890 soort niet alleen visueel, horloge hoe veel efficiënter 855 00:38:30,890 --> 00:38:33,330 Deze hefboomwerking van divisie en het veroveren 856 00:38:33,330 --> 00:38:39,150 kan worden wanneer toegepast op een dataset dat zelfs niet de grootte van acht, maar ook veel, 857 00:38:39,150 --> 00:38:39,970 veel groter. 858 00:38:39,970 --> 00:38:44,585 Ik geef je een soort samenvoegen, naast zijde met deze andere algoritmen. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Dit gaat pijn krijgen snel, en het einde 861 00:38:58,530 --> 00:39:00,890 is niet bijzonder climax, ze alleen maar uiteindelijk gesorteerd worden. 862 00:39:00,890 --> 00:39:05,280 Maar de sleutel weg te nemen, is dat kijken hoeveel sneller soort fuseren 863 00:39:05,280 --> 00:39:08,110 was, tenzij je denkt dat ik ben gewoon een soort van knoeien met je. 864 00:39:08,110 --> 00:39:13,100 Als we dit nog een laatste keer, laat het verversen, laten we terug gaan 865 00:39:13,100 --> 00:39:14,960 en kies bubble sort, en gewoon voor de kick, 866 00:39:14,960 --> 00:39:17,330 Laten we kiezen voor het inbrengen soort, gewoon voor een goede maatregel. 867 00:39:17,330 --> 00:39:20,020 En deze keer weer, laten we kiezen merge sort en laten we 868 00:39:20,020 --> 00:39:21,595 daadwerkelijk gereden deze naast elkaar. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> En het is niet, in feite, een toevalstreffer. 871 00:39:26,930 --> 00:39:31,140 Wat ik heb gedaan is effectief Ik heb onderverdeeld mijn inbreng in half, weer, 872 00:39:31,140 --> 00:39:32,240 en opnieuw, en opnieuw. 873 00:39:32,240 --> 00:39:35,590 En er is maar een beperkt aantal keren dat u kunt verdeel uw inbreng in twee helften, links 874 00:39:35,590 --> 00:39:36,240 en rechts. 875 00:39:36,240 --> 00:39:39,425 Wat is de formule die we blijven zien dat beschrijft de verdeeldheid in de helft 876 00:39:39,425 --> 00:39:41,050 opnieuw, en opnieuw, en opnieuw, en opnieuw? 877 00:39:41,050 --> 00:39:41,890 >> PUBLIEK: Log n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: Log n. 879 00:39:42,760 --> 00:39:46,300 Maar dan is er nog een andere belangrijke stap, Dit algoritme is niet log n stappen. 880 00:39:46,300 --> 00:39:48,992 Als het alleen werden log n stappen, we hetzelfde probleem zou 881 00:39:48,992 --> 00:39:51,200 als voorheen, waar we niet kunnen ervoor dat alles is opgelost. 882 00:39:51,200 --> 00:39:54,480 Je moet minimaal kijken n elementen om zeker n elementen worden gesorteerd, 883 00:39:54,480 --> 00:39:55,950 anders is het een sprong in het diepe. 884 00:39:55,950 --> 00:39:59,810 >> Dus het is minimaal log n stappen, maar hoe zit het met deze toets samenvoegen stap 885 00:39:59,810 --> 00:40:04,370 waar ik samengevoegd mijn linker helft en rechts helft en liep over het podium? 886 00:40:04,370 --> 00:40:06,980 Hoeveel stappen is dat om te fuseren? 887 00:40:06,980 --> 00:40:10,150 Het is n, maar ik deed het niet alleen samenvoegen van de laatste tijd. 888 00:40:10,150 --> 00:40:15,089 Op elk van deze geneste gesprekken op elke van die geneste samenvoegingen, ik nog gesorteerd worden. 889 00:40:15,089 --> 00:40:18,380 Ik fuseerde deze twee jongens, dan zijn deze twee jongens, dan zijn deze twee jongens, enzovoort. 890 00:40:18,380 --> 00:40:19,955 >> Dus ik heb het samenvoegen opnieuw, en opnieuw. 891 00:40:19,955 --> 00:40:20,580 Hoe vaak? 892 00:40:20,580 --> 00:40:23,510 Dus elke keer als ik verdeelde de lijst in de helft, heb ik een merge. 893 00:40:23,510 --> 00:40:25,460 Verdeel de lijst in de helft, doe een merge. 894 00:40:25,460 --> 00:40:28,570 Als delen van de lijst kunnen log n keer worden gedaan, 895 00:40:28,570 --> 00:40:33,880 en de samenvoeging neemt uiteindelijk n stappen, wat zou nu het bovenste 896 00:40:33,880 --> 00:40:37,000 gebonden aan de lopende tijd van ons algoritme? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> En inderdaad, dat is wat we hier hebben bereikt. 899 00:40:40,560 --> 00:40:44,650 Dus het gevoel dat je ziet visueel als die drie dingen naast elkaar lopen 900 00:40:44,650 --> 00:40:47,930 is n kwadraat tegen n kwadraat tegen n log n. 901 00:40:47,930 --> 00:40:51,010 Die fundamenteel we zullen zien, niet alleen vandaag maar in de toekomst 902 00:40:51,010 --> 00:40:52,760 is veel, veel sneller. 903 00:40:52,760 --> 00:40:56,010 Een applaus voor deze jongens, Ik zal hen belonen met stress ballen. 904 00:40:56,010 --> 00:41:00,260 Laten we verdagen hier vandaag, en Wij zullen u op maandag. 905 00:41:00,260 --> 00:41:02,255