[Powered by Google Translate] [Week 3, Vervolg] 

[David J. Malan - Harvard University] 

[Dit is CS50. - CS50.TV] 

Oke. Welkom terug. Dit is CS50 en dit het einde van week 3. 

Dus voor degenen die niet bekend, vorig jaar Harvard gelanceerd wat het Innovation Lab genaamd, of i-lab, dat is een prachtig gebouw aan de overkant van de rivier op de campus HBS's die open staat voor studenten, GSAS studenten, studenten uit heel de campus, waaronder faculteit, en het is een plek om samen te komen om te werken aan innovatieve dingen, in het bijzonder ondernemende dingen als u en 0 of meer vrienden denken om iets te doen ondernemende hetzij tijdens deze klasse na deze klasse, of verder. 

Dus een van de dingen die ze doen meer dan J termijn is deze reizen, waarvan is New York, waarvan is Silicon Valley. De ruimte is zeer beperkt, maar het is een kans om de schouders wrijven met MBA's en graduate studenten over de campus en eigenlijk tijd doorbrengen op deze respectieve gebieden chatten up startups, chatten ondernemers en dergelijke. Dus als geïnteresseerd, kijk op deze URL hier. Het is ook beschikbaar op de dia's online. 

Kunnen we de toon van het huis audio gewoon een beetje? Wilt u met ons mee voor de lunch deze vrijdag, 1:15 uur in Fire & Ice, ga dan daar. Excuses als het formulier is al ingevuld op het moment dat je er bent. Maar we zullen blijven deze traditie verder. 

Vandaag gaan we verder het hogere niveau bespreking van de verschillende problemen die we kunnen oplossen, richten veel minder, vandaag in ieder geval, op code en nog veel meer op ideeën. Dus denk terug naar week 0 als we een telefoonboek scheurde in tweeën, waarvan het doel was om iets te doen, toegegeven, een beetje dramatisch maar op het punt dat zoeken niet hoeft te zijn, noodzakelijkerwijs verzenden zo duidelijk op het eerste gezicht als je zou denken. En het oplossen van problemen in het algemeen er niet per se altijd de beste - De meest voor de hand liggende oplossing is misschien niet per se de beste. Dus we hadden deze telefoon boek en, eerlijk gezegd, ons allen in de kamer had de instincten, meest waarschijnlijk, om te beginnen in het midden bij het zoeken naar Mike Smith en ga dan naar links of rechts op basis van welke letter van het alfabet we toevallig om te eindigen op. 

Maar dat simpele idee dat wij mensen hebben vanzelfsprekend zo lang echt moeten beginnen om te komen tot de voorhoede van je geest want als de problemen komen veel complexer dan een telefoonboek, diezelfde eenvoudige, briljante inzichten zijn wat gaan ons in staat stellen veel ingewikkelder en interessante problemen oplossen, onder hen een aantal van de dingen die we nemen voor reeds verleende deze dagen. Miljarden webpagina's die er zijn, en toch Google en Bing en dergelijke zijn in staat om dingen te vinden voor ons als dat. Dat is niet gebeurt met behulp van een lineair zoeken, zoeken door alle mogelijke webpagina's. Facebook is in staat om u te vertellen wie al je vrienden zijn of vrienden van vrienden, en ook dat kan schijnbaar worden gedaan in een oogwenk deze dagen ook al hebben ze miljoenen gebruikers. 

En dus hoe we eigenlijk problemen op te lossen op die schaal zal uiteindelijk een vermindering van om de ideeën die we bekeken in week 0 en een beetje meer vandaag. We zullen niet dit algoritme opnieuw uit te voeren, maar herinneren we ook deden in week 0 deze oefening waar we iedereen opstaan, nemen op de nummer 1, en toen hadden we iedereen zelf-telling door het koppelen van af, het toevoegen van uw getallen met elkaar, dan de helft van de bende ging op elke iteratie. Dus gingen we van 500 leerlingen 250 tot 125 en enzovoort. Maar zoals we al zeiden op maandag, de krachtige idee dat er was dat als we een verdubbeling van dat probleem en al de kinderen van Justitie of EC 10 kwam terug in de kamer en bij ons, goed, konden we waarschijnlijk rekenen dat hele aggregaat groep met slechts 1 andere grote iteratie van de lus, omdat ze alleen misschien dubbel zo groot of in Ec 10's geval een beetje meer dan het dubbele van de grootte. En zo zouden we een beetje meer tijd, maar we zouden niets hebben om 400 of 700 meer stappen door te brengen. 

Gewoon om deze foto te schilderen op een manier die een beetje minder abstract, laten we niet iedereen hebben staan. Maar als degenen onder u die er voor kozen om te zitten in het orkest van vandaag zou het niet erg te staan, laten we eens kijken of we erachter te komen onder jullie die de langste persoon is door het doen van dezelfde soort vergelijkende algoritme. Dus als je zit in het orkest, mijn excuses, maar stap 1, opstaan; stap 2, paar uit met iedereen in de buurt u, erachter te komen wie is groter, en gaan zitten als je korter. Herhaal vervolgens. [Studenten murmelende] 

Oke. Oke. Een daarvan is blijven staan. Wat is je naam? >> Andrew. 

Andrew, je bent de hoogste persoon in het orkest deel vandaag. 

Gefeliciteerd. [Applaus en gejuich] Oke. Ga zitten. Dus vonden we Andrew. Maar hoe lang zou het me hebben genomen, bijvoorbeeld om Andrew vinden In dit orkest deel van 50 + of zo mensen? Ik had kunnen nemen een vrij eenvoudige aanpak en beginnen hier. En ik heb 2 personen opstaan ​​en ik vergelijk ze, en dan zeg ik tegen degene die iets korter, "Oke, je gaat zitten," en ik ga om te herinneren wie de langere persoon was. Daarna heb ik herhalen, herhalen, herhalen, en ik hangen aan de langste persoon tot ik iemand iets langer dan hen, op welk punt de iets kortere persoon moet dan gaan zitten. Maar in dat algoritme in dit orkest deel, als er n van u, hoeveel stappen is dat algoritme gaat duren? >> [Student] N. 

Het gaat om n te nemen, rechts, want in het ergste geval, bij wijze van spreken, de langste persoon is de laatste persoon die ik krijg gewoon door willekeurige pech. Dus in het ergste geval, de looptijd van dat algoritme lineair is, het is n, waarbij n het aantal mensen in de ruimte, de omvang van het probleem. Hoe zit het met dit algoritme? Het feit dat je alle opstond en dan weer de helft van jullie ging zitten, de helft van je ging zitten, de helft van jullie ging zitten. Hoeveel stappen moet die hebben als er n van jullie hier? [Student] N log n. >> Dat zou nog erger zijn. Meld u n. 

Dus log n, zelfs als je niet meer weet wat een logaritme is, voor nu, maar begrijpen dat het een of andere manier betrekking heeft op deze halvering en halveren en halveren. Het hoeft niet een factor 2. Het kan een factor 3 worden. Maar het is deze herhaling van dezelfde soort factor zodat de omvang van het probleem begint maar dan meteen gaat hier, dan hier, dan hier, dan hier. U bent niet kleine hapjes nemen van het probleem, je echt hakken weg bij het met een grote klap elke keer. Dus we hadden 50 mensen, dan 25, dan 12 ½ of 13 mensen staan, dan 6 ½ enzovoort totdat uiteindelijk gewoon Andrew was blijven staan. Dus we gaan met die log van n noemen, en je kunt visualiseren dit als volgt. Hier herinneren deze foto waar een lineair algoritme is als de rode lijn daar, de gele lijn was het tellen van 2s algoritme die we hebben gebruikt voor het tellen van studenten in het verleden, maar vandaag de heilige graal gaat deze groene lijn te blijven waar als we een verdubbeling van het aantal mensen in het orkest sectie of net zei, hel, laten we iedereen in de hele kamer staan, niet zo'n big deal omdat we ongeveer het dubbele van hoeveel mensen zijn hier beneden, 1 meer iteratie, geen probleem. 

We hebben geconstateerd Andrew of wie dan ook gebeurt te zijn groter dan Andrew in de mezzanine of op het balkon. Dus dit eenvoudige idee dat we zoveel namen als vanzelfsprekend in een telefoonboek, beseffen dat er zo veel verschillende plaatsen waar we kunnen toepassen. Eigenlijk, in plaats van jargon eerste, - gewoon om wat jargon klap laat me gaan hier om deze foto. Op dit moment hebben we gesproken over n en n / 2 en meldt u zich vervolgens van n, maar we kunnen zeker komen met, zoals we zullen in de loop van het semester, andere soort van wiskundige formules op deze algemene notie van de looptijd te beschrijven. Dit zijn uit hun context voor nu, want we zien het duurde niet lang algoritmen die deze daadwerkelijk vertegenwoordigen. 

Maar hier let op de lineaire lijn n, de rechte lijn, is eigenlijk heel laag naar rechts nu. Dat is een soort van een optische illusie in dat we gewoon veranderen wat de x-as geeft en de y-as, en kunnen we een rechte lijn punt in elke richting die we willen. Maar de reden dat het nu zo schijnbaar vlakke is omdat we moesten kamer op deze grafiek te maken voor veel langzamer looptijden. Voor nu, weet dat er een aantal vrij slecht algoritmen in het leven, waarvan sommige nemen geen n stappen of, beter nog, log n stappen, maar nog veel meer. Dus boven de lijn n hier aan de onderkant aankondiging is er n keer log van n, en we zullen zien wat dit betekent het duurde niet lang. Daarboven is n kwadraat, en we hebben niet gezien dat een n kwadraat algoritmes nog niet, maar we gaan. En dat ziet er echt slecht. Er zijn 2 de n iets exponentiële die voelt nog erger. En toch, vreemd genoeg, dan is er n in blokjes gesneden, die als je soort van vooruitdenken, als je soort van do the math, 2 tot de n daadwerkelijk wordt veel rechtere, veel hoger is dan n blokjes als je kijkt naar de assen ver genoeg uit. Dus ziet nu deze assen zijn willekeurig 2 tot 10 op de x-as. 

En wat betekent dat? Dat betekent dat 2 personen tot 10 personen in de kamer. Dat is alles wat x betekent: grootte van het probleem, ongeacht de context. En een verticale as nu een aantal seconden of aantal stappen - een zekere eenheid van tijd. Maar merk dat is 0 tot 60 en 0 tot 10. Maar als we soort van uitzoomt, zoals je misschien in Excel of een kaart brengen van software, en wij gaan op naar 200.000, merken dat iets als 2 tot de n gaat volledig overweldigen de looptijden van n kwadraat, n blokjes, n log n - alles wat we hebben gesproken over tot nu toe. En toch is de vangst is wanneer je begint te praten over zaken als Facebook waar u vele, vele, vele mensen allemaal met elkaar verbonden, je hebt mensen n, zou elk van hen zo veel als n vrienden als iedereen is een soort van buddy-buddy in de wereld, nou, dat is n keer n al, dus dat is n kwadraat mogelijk vriendschappen, althans in 1 richting, n kwadraat mogelijk vriendschappen. Dus dat al doet vermoeden dat het zoeken sociale grafiek van Facebook, zo te zeggen, kan gaan worden uitgedrukt in dergelijke formules. 

We komen terug en maken dit veel concreter, maar voor nu, de doelstelling voor de komende vele weken gaat zeker niet om te gaan over het implementeren algoritmes of code die uiteindelijk het nemen van zo veel tijd als iets als dit. Maar het fascinerende van de informatica als u verder op in dit veld het nemen van lessen zoals CS121, CS124, die beide de theorie cursussen, is dat er eigenlijk een aantal problemen die er bestaan ​​in deze wereld dat fundamenteel zover we weten, kunnen niet sneller worden opgelost dan de ergste van deze grafieken suggereert eigenlijk. Dus er is veel open problemen in deze wereld te doen veel beter dan mensen hebben tot nu toe. 

Dus laten we dan beginnen met dit voorbeeld. We zagen Sean worstelen met dit op de camera, maar al te onhandig op video. Maar de werkelijkheid was toen Sean werd belast met het vinden op een bord als dit het getal 7, herinneren dat ik dat zei, "Er is ergens achter deze stukjes papier of witte deuren "Het getal 7. Sean, vinden het voor ons." En het was heerlijk lastig om naar te kijken want hij was echt worstelen met dit probleem. Maar de werkelijkheid was Sean deed als iemand in de kamer had kunnen doen. Hij nam een ​​beetje langer dan een typisch persoon zou kunnen hebben, maar hij ervan uit dat er een truc om dit probleem op, nam hij aan dat hij iets mist. En het hielp niet dat honderden ogen met naar beneden op hem. 

Maar de werkelijkheid was indien de ingang van het probleem is een bos van willekeurige getallen en u wordt gevraagd om een ​​dergelijk nummer te vinden, het beste wat je kunt doen is lineair zoeken. Begin aan de linkerkant, naar rechts, of start op het juiste, naar links. Met terugwerkende kracht, we kunnen denken, "Sean, waarom je niet gewoon starten vanaf de andere kant?" Nou, 7 hier net zo goed zijn willekeurig, maar ik opzettelijk het daar, omdat ik dacht dat hij niet van plan om te beginnen bij het einde. Dus ik soort van gemanipuleerd de situatie, maar door toeval 7 kan overal geweest zijn. Dus vanaf de rechterkant zou dan beter zijn geweest, maar wat als het volgende jaar ik verhuis 7 elders? Dat is niet een fundamenteel nieuwe oplossing voor het probleem - vanaf 1 kant of de andere - als je krijgt geen andere aannames. Dus Sean op zoek gegaan naar door de nummers en hij zei: "5. Dat is hier niet." Toen ging hij hier en zag 19, dan is hij pauzeerde gedurende ongeveer 20 seconden, toen opende hij dit voor 13, en toen werd het duidelijk dat er geen sprake lijkt een patroon te zijn. Het was niet 1, 2, 3, 4 of dergelijke. Er waren verschillen in het aantal, die niet helpen. En ook aan het feit dat ik deze goedkope stukjes papier gebruikt bedekken de getallen is eigenlijk bewust, want als ik verwijderde al deze stukjes papier, de meesten van ons, Sean inbegrepen, waarschijnlijk soort van macroscopisch hebben keek op het bord en zei: "O, 7 natuurlijk is daar." We hebben het meteen. 

En dat kan de manier waarop het menselijk brein werkt voor een deel, maar in werkelijkheid, zijn ogen of geest was waarschijnlijk het afromen van de nummers van rechts naar links, van links naar rechts, midden op uit - iets aan de hand was fysiologisch zodanig dat het voelde alsof het was meteen gebeurde, maar kansen zijn zelfs intern was er een soort van methodologie op het vinden van 7. En inderdaad, nu we het hebben over arrays en datastructuren en geheugen binnenkant van een computer, kan het enige wat wij mensen doen wordt naar afzonderlijke geheugenplaatsen 1 per keer. 

Dus elke andere locatie kan net zo goed worden afgedekt met een stukje papier omdat we toch niet zien. We kunnen een ding doen op een tijdstip. Dus in dit geval, in het geval van Sean, we gingen hier en toen gingen we hier en toen gingen we hier, hier, hier, hier, kreeg slim aan het eind en gewoon een soort van overgeslagen deze willekeurig en werden 7 daar. Deze was niet heel bijzonder. Het was ook in orde. Maar hij eindelijk gevonden 7. Maar nu is de meeneem is echt zo het beste wat je kunt doen als er geen informatie gegeven anders dan willekeurig gesorteerd getallen is om te beginnen van links of van rechts te beginnen. Of ach, kunt u willekeurig openen deuren, maar zelfs dan wat betekent het om willekeurig? Nou, we moeten een of andere manier formaliseren wat het betekent om hier te beginnen, dan hier te gaan, dan hier te gaan. Sean deed het geweldig, en het was gewoon leuk om te zien. Wat gebeurt er als we in plaats daarvan te veranderen het probleem een ​​beetje en brengen dit jaar Sean, als je wil? Zou iemand comfortabel komen op het podium en het oplossen van een iets ander probleem en het verschijnen voor de camera? 

Laten we verder gaan dan het orkest, omdat jullie zijn heel betrokken vandaag reeds. Hoe zit het in roze, in de hoed? Kom naar beneden. Wat is je naam? >> Alex. >> Alex. Oke. Dus Alex zal dit jaar Sean en zal verschijnen in de komende jaren waarde van CS50 lezingen. Alex, leuk je te ontmoeten. >> Leuk je te ontmoeten. De uitdaging bij de hand voor u is dat u het een beetje makkelijker in dat ik zeg je dezelfde nummers worden hier, maar ze zijn nu gesorteerd. Dus nu je doel is het vinden van het nummer 7. En eigenlijk moeten we echt maken dit - je bent soort van vals spelen, zoals een computer niet wil, door te kijken naar wat de nummers waren een ogenblik geleden. Met krijt dit is eigenlijk niet van plan om al te veel te helpen, maar laten we doen alsof je niet weet wat de oorspronkelijke array. Alles wat je nu weet is dat je een array van gesorteerd nummers hebben dat zou kunnen hebben openingen tussen hen, en je doel is het vinden van het nummer 7. Hoe zou u, een redelijke mens, gaan over het vinden van de nummer 7? 

Ga van laag naar hoog? >> Oke. Ga van laag naar hoog. En niet scheuren ze af. Laten we ze opheffen, zodat we kunnen hergebruiken. Oke, dus 1. Wacht. Voordat je door blijven gaan, dat was 1, duidelijk verkeerd. Dus wat gaat er door je hoofd nu? Wat is je volgende stap? De volgende. >> Oke. De volgende. Goed. 3, zodanig onjuist. Wat is je volgende stap? Keep on going. >> Oke. Keep on going. 5. Dus blijven gaan, en laat mij overhandigen je dit voor het nageslacht. 7. >> Excellent. Heel goed. Ik vond de nummer 7. [Applaus] Dus dat was goed, maar Sean ook gevonden het getal 7. En ik beweer dat je niet echt deze extra stukje informatie geëxploiteerd, namelijk dat deze nummers worden gesorteerd. Dus kunnen we beter doen? Eventuele suggesties hier? Ja, in de rug. [Student] Binary zoeken. >> Ik heb geen idee wat binair zoeken is. 

[Student] Start in het midden. >> Start in het midden. Oke. Dus laten we eens kijken of we er zijn. Dus als je in plaats daarvan verteld begin vanuit het midden, ga je gang en open de middelste deur. Er is 8 van hen, dus je gaat te hebben om willekeurig kiezen voor de een iets naar links of naar rechts. Oke. 7! [Applaus] Very nice. Oke, maar waar waren we met dit? Laten we aannemen dat alleen maar om de band u hier was begonnen te breken want dat even zou net zo goed kunnen gebeuren. We toevallig te weten dat 7 was er. Dit is dus 13. Dus als ze gesorteerd en we nog maar net begonnen in het midden, wat zou de optimale volgende stap zijn? Ga links. En dus hier komt het telefoonboek voorbeeld weer. Als 13 is hier en we weten dat de lijst is gesorteerd, dan al deze stukjes papier oninteressant voor ons nu omdat we al weten dat 7 moet zijn aan de linkerkant Indien deze nummers gesorteerd en vonden 13. 

Dus wat is je volgende zet hier? >> Ga naar links. >> Oke, goed. Dus ga naar links, en - wacht, hey, hey, hey. Dat is vals spelen. Dus u gevonden 7, maar wat was het algoritme we gewoon toegepast? Begin in het midden. >> Goed. Dus wat is de logische uitbreiding van datzelfde idee? O, alleen deze. >> Precies. >> Dus ik begin hier. >> Goed. Dus nu zijn we iets naar links weer. Het is 3. Maar het interessante afhaalrestaurant is nu welke heb je geen zorgen te maken over? Deze 2. >> Deze 2. Dus nu deze weg kan gaan, kan deze weg te gaan. Nu is het probleem dat was 8 toen maat 4 nu is maat 2. We krijgen aardig in de buurt. Nogmaals, ga naar het midden van deze 2 elementen. 

Oke. Dus het is een soort van jammer dat we nu altijd gaan verlaten omdat we afronding naar beneden. Maar dat is prima, want nu gooien we deze weg en al het andere, waardoor we met slechts 7. Laten we een applaus. We hebben 7 opnieuw. [Applaus] Oke. Tuurlijk. Wacht voor slechts 1 seconde. Hoewel dat volgende proces soort duurde wat langer dan we voelden dat het zou, eerlijk gezegd, je eerste instinct was de beste, toch? We hebben 7 ogenblikkelijk. Maar we zouden hebben gevonden 7 sneller, wat er ook gebeurt, in dit voorbeeld ten opzichte van deze want als de nummers zijn allemaal gesorteerd, net als de pagina's in een telefoonboek, kun je inderdaad hakken de helft van het probleem er weer uit en opnieuw en opnieuw. En het is niet zo gemakkelijk te zien, met slechts 8 nummers in tegenstelling tot een 1.000-pagina telefoonboek waar je echt visueel zien, maar in dit geval hier toen Sean op zoek was naar 7, hoeveel stappen in het ergste geval zou het hebben genomen hem? >> [Student] 7. 7 in het ergste geval. Nou ja, in het ergste geval niet 7 als er 8 deuren hier. Het zou hebben hem 8 stappen. 

Dus als er n deuren, zou het hebben genomen Sean een paar jaar geleden n stappen. Nu, in uw geval, Alex, gezien het feit dat deze nummers worden gesorteerd - en we kunnen soort afleiden deze van waar we tot nu toe in dit verhaal - wat is de looptijd van meer intelligent algoritme Alex van het starten van het midden en dan herhalen? [Student] 3. >> Dus het gaat worden 3, ruwweg, als je 8-4 naar 2 naar 1. Dus 3 stappen of, meer in het algemeen, dat is log n weer. Elke keer dat je de halvering en halveren en halveren en halveren, Dat is een uitdrukking van dit idee van log n. En dus dat zou hebben genomen u slechts 3 stappen, en inderdaad het deed zodra we de deuren geopend halveren en halveren, overwegende dat dit zou hebben genomen Sean ongeveer 7 of 8 stappen. Dus dank u voor uw aanwezigheid bij ons dit jaar. >> Dank je wel. Leuk je te ontmoeten. Bedankt aan Alex. >> Ook. [Applaus] 

Wat is dan de echte implicatie van deze? Stel je nu voor dat het niet 8 deuren, die, eerlijk gezegd, ieder van ons kan iets vinden achter 8 deuren vrij snel gewoon door het scheuren van de stukjes papier en gaan met onze instincten. Maar wat als het een miljoen deuren? Wat als het 4 miljard deuren? In het geval van 4 miljard deuren, je echt gaat te willen gaan met algoritme van Alex, binair zoeken als we beginnen noemde het of verdeel en heers, meer in het algemeen, waar je blijft halveren en halvering van het probleem, want als je 4 miljard deuren, hoe vaak je hakken 4 miljard in de helft? [Student] 32. >> Het is eigenlijk 32. Je kunt werken dit uit op een stuk papier of in je hoofd. Je gaat 4 miljard tot 2 miljard to 1 miljard tot een half miljard, tot 250 miljoen, puntje, puntje, puntje. En als je uit de wiskunde, zul je inderdaad krijgen 32, en die betrekking heeft daadwerkelijk de informatica, omdat we meestal rekenen in machten van 2. 2 van de 32 toevallig 4 miljard. Dus er is een hoop die relevant zijn voor dit soort van machten van 2 in de informatica. 

Maar wat ongeveer 8 miljard? Hoeveel stappen is dat duren als er 8 miljard deuren? [Student] 33. >> So 33. Wat als er 16 miljard deuren? Hoeveel stappen is dat nog duren? [Student] 34. >> 34. We konden soort blijven dit tot vervelens toe. Maar dat is een krachtig ding. U kunt introduceren miljarden meer ingangen om uw probleem op, maar geen big deal, je gewoon een extra hap van te maken en dus geeft ons iets als binaire zoekopdracht of verdeel en heers, meer in het algemeen. Maar ik ben een beetje vals spelen hier, toch? In het geval van algoritme Alex, had ze een voordeel ten opzichte van Sean. Ze wist dat deze nummers werden gesorteerd, maar Alex hoefde niet te sorteren ze zelf. Ik op voorhand kwam naar het bord en de aard van zorgde ervoor dat ik ze allemaal haalde in de gesorteerde volgorde, dan heb ik bedekt ze met papier. Maar hoeveel werk heeft dat me? Als we hadden begonnen met deze nummers in een aantal schijnbaar willekeurige volgorde - Deze middelen eenvoudiger getallen 1 tot 8 hier - hoe kunnen we gaan over het sorteren van deze waarden? Als je een mens gegeven deze taak, zou wat voor soort intuïtieve benadering neemt u om het sorteren van een hele hoop nummers? Deze dingen werden aangelegd als puzzelstukjes. Ja. 

[Student] Ik zou elk nummer en vergelijk het met een ieder en ga naar links. >> Oke, goed. Dus neem elk nummer, het vergelijken met de ernaast, en dan gewoon blijven bewegen langs de lijst, een soort van rejiggering dingen als je gaat. Hier hebben we dus een kans voor misschien een paar meer mensen om mee te doen. Hebben we nog 8 vrijwilligers die graag komen? Een beetje minder druk, omdat je bent niet de enige. 1, 2, 3, 4, 5, 6, 7, 8. Kom naar beneden. Jullie gaan de nummers 1 tot en met 8 zijn. Laten we eens kijken of we dit sortering niet veel voor Alex op dezelfde manier waarop ik het deed op voorhand. 1, 2, 3, 4. Ga je gang en als je wilt, line-up op het podium tussen de muziekstandaard en mij hier in dezelfde volgorde als de dia op het scherm. Uh-oh. We werken je in het volgende voorbeeld. Oh, wacht, wacht. Daar gaan we. Wacht. Het volgende voorbeeld is nu. Hier ga je. Nummer 8. Kom op. Oke. Sorteren gelijkvormig aan deze. Schuif gewoon een beetje aan de zijkant van de muziek staan ​​hier. We hebben dus 4, 2, 6 - naar binnen, hier, daar - 3. Ja. Oke. Je gaat hier. Nee, blijf daar. Ja, precies daar. Nee, ik ben verkeerd. Precies daar. Oke, heel goed. Oke. Dus nu laten we ze te sorteren in stijgende volgorde. 

Hoe kan ik dat doen? Het algoritme dat werd even geleden voorgesteld was de reden waarom we niet gewoon vergelijken de mensen die zijn soort van naast elkaar en vervolgens vast te stellen eventuele fouten, van links naar rechts. Hier hebben we dus 4 en 2, uiteraard buiten de orde. Laten we ruilen u. Oke. Dus nu ga ik naar beneden de lijn. 4 en 6, nope. [Gelach] 6 en 8, vrij goed. 8 en 1, laat me ruilen jullie. Oke. Dus 8 en 3, wisselen jullie. 8 en 7, laat me ruilen jullie. 5 en 8 uitstekend. Ik geef je een gesorteerde lijst. Oke. Dus niet helemaal. Maar het is beter, omdat de grotere aantallen - geval in punt 8 - hebben soort borrelen van links naar rechts. Dus ik heb 1 van hen recht, maar het voelt alsof dit niet helemaal het probleem oplossen. 

Dus wat zou u voorstellen dat we nu doen? >> [Student] blijven doen. >> We blijven doen. En nogmaals te realiseren, zetten we dingen door gewoon met alle mensen soort van intelligente zelf te regelen op basis van die foto, maar nu moeten we veel meer methodisch. We moeten algoritmische erover alsof we het schrijven van code - in dit geval verbale pseudocode. Dus laat me gewoon dat nog eens proberen. Dat werkte heel goed. Het heeft niet oplossen. Maar als het twijfelen, gewoon proberen en probeer het opnieuw. Zo 2 en 4 niet meer helpen. 4 en 6. Ah! 6 en 1, iets beter. 6 en 3, goed. 6 en 7, 7 en 5, 7 en 8, goed. En weet je, ik kan nu waarschijnlijk negeren 8, omdat hij aan het einde van de lijst. Misschien hebben we geen zorgen te maken over iemand die voorbij hem. Maar laten we eens kijken of dat is een veilige aanname. Nu lijst is - verdomde - niet gesorteerd. Laten we het opnieuw proberen. Zo 2 en 4, 4 en 1, 4 en 3. 4 en 6, goed. 6 en 5, goed. 6, 7 en 8, goed. Maar let op, kan ik gewoon nu stoppen hier en nu hier te stoppen? [Student] Ja. >> Ja? Wat als een van u was de nummer 9 helemaal daar? Het zou zijn gesorteerd. >> Goed. Het zou zijn gesorteerd de eerste keer. Goed. Dus laten we terug te gaan. We zijn er bijna. 1 en 2, 2 en 3, 3 en 4, 4 en 5, 5 en 6, 6 en 7, 7 en 8. 

Ik ben nu klaar, maar, nogmaals, ik ben een computer die alleen kan doen wat ik vertelde te doen, en mijn enige herinnering is nu dat ik eigenlijk alleen maar een beetje werk deed. Iets veranderd hier. Dus ik heb niet technisch visueel of algoritmisch dat deze lijst wel degelijk gesorteerd bevestigd. Dus gewoon voor een goede maatregel, alleen maar om anale over dit, laten we dit doen nog 1 keer. Dus 1 en 2, 2 en 3, 3 en 4. En weet je wat? Gewoon voor een goede maatregel, ik ga om bij te houden op mijn hand deze keer hoeveel swaps ik gewoon zo dat ik weet hoeveel werk ik heb eigenlijk gedaan. 3 en 4, 4 en 5, 5 en 6, 6 en 7, 7 en 8. Geen swaps. Dus nu zou ik legitiem een ​​idioot weer doen want als ik geen werk door middel van deze pas van de mens, dan is het duidelijk dat gaat weer gebeuren als geen van hen is een soort van willekeurig adversarially bewegen zich rond. Dus nu kan ik stoppen. Laten we nu de vraag stellen, dit was hoeveel werk eigenlijk me? Hoeveel stappen heb dat duren? >> N kwadraat. Ja, dus n kwadraat. Waar haal je n kwadraat van? Je moet elk num check - Er is n getallen, en je moet elk nummer op met de andere n getallen. Goed. >> Dus het is n kwadraat. >> Goed. 

Dus het voelt alsof het zou heel goed n kwadraat, toch? Er is n van deze jongens, 8 in het bijzonder in dit geval, maar elke keer als ik ging door deze lijst Ik was het vergelijken van de eerste persoon ten opzichte van de tweede, de tweede tegen de derde keer op keer op keer, en toen ik tot het einde, deed wat ik doe? I redid het. Dus als we generaliseren deze uitleg hebben we n mensen en ik ben het maken van, uiteraard, 8 stappen, n stappen, elke keer als ik door dit algoritme. Maar hoe vaak in het ergste geval moet ik gaan door deze lijst van mensen? [Student] N keer. >> Waarschijnlijk n, rechts, want in het ergste geval, wat is waarschijnlijk het ergste geval opstelling van deze jongens uit de get-go? Als ze volledig omgekeerde volgorde want net mentaal veronderstellen, let's - Hoe heet je? >> Bowen. Bowen. Oke. Dus Bowen, kom hier voor slechts een moment. 

Stel dat Bowen hier aan het begin van het algoritme, en we weten niet wat iedereen is, maar Bowen hier, volgens dit algoritme - en als je wilt gewoon een wandeling met mij - gaat borrelen, zoals hij deed de eerste keer, helemaal naar het einde. Maar stel dat de persoon naast Bowen was het getal 7. Ik moet teruggaan en nummer 7, wat betekent dat ik de hele weg terug hier te komen. Nu heb ik diezelfde wandeling hebben met de persoon die is nummer 7. Maar wat als dan nummer 6 was naast hem ook? Dan moet ik om terug te gaan en 6 te krijgen. Dus nogmaals, op elke iteratie van deze lus Ik heb het aan elk van de n volk, en ik zou kunnen hebben om n te maken van deze wandelingen om ervoor te zorgen Ik trek alle grootste elementen heen en terug en terug naar het einde van de lijst. Dus n dingen n keer is slechts n keer n of n in het kwadraat. 

Dus hier al hebben we een algoritme dat is niet meer n, dat is niet meer log n, het is eigenlijk nog erger dan alles wat we hebben gedaan. Dus Alex soort van geluk hebben gehad in dat ik al het werk blijkbaar van te voren voor haar deed, alle van de dure werken, zodat ze kon genieten van deze binaire zoekalgoritme, die log van n. Maar dit is in overeenstemming met het thema van maandag. We gaven een beetje meer ruimte, gebruikten we meer bits, om te versnellen onze lopende tijd. Zoveel alsof er deze trade-off tussen tijd en ruimte, er misschien ook gewoon afwegingen tussen tijd besteed aan de voorkant soort van om dingen klaar om te gaan en eigenlijk het uitvoeren van een algoritme zoals zoeken. Laten we proberen een andere. Als jullie het niet erg gewoon snel herschikken jezelf weer overeenkomen dat, laten we iets anders waar het te proberen niet zo eenvoudig als vast gewoon alle paarsgewijze fouten, dat is super intuïtief. Laten we in plaats daarvan een beetje meer bewust en doen. Deze ook ik zou voorstellen is waarschijnlijk vrij intuïtief. 

Laten we de kleinste persoon uit de lijst te selecteren opnieuw en opnieuw. Dus hier gaan we dan. 4, jij bent de kleinste persoon die ik dus tot nu toe heb gezien, dus ik ga mentaal herinneren dat door alleen maar te wijzen op je voor nu. 2. Ooh! Vergeet nummer 4. Ik vond de nieuwe kleinste element in deze lijst. Ik ga voor soort onthouden. 6, 8. Ooh! 1. Tot ziens. Dus nu ga ik nummer 1 onthouden. We weten dat 1 is de kleinste, maar ik ben de computer. Wat als er een 0? Wat als er een -1? Ik heb om door te gaan. Dus 3, 7, 5, nope. Oke. Dus nummer 1 was de kleinste. Laat me je kiezen uit de lijst - we zullen gaan op deze manier - en willekeurig zet je aan het begin van de lijst. Nu, wacht eens even. Ik soort van bedrogen. Als deze jongens vertegenwoordigen niet een lijst van 8 mensen, maar een array, 8 stukken aaneengesloten geheugen - vind je het erg, stap achter voor slechts een moment? Er is eigenlijk geen ruimte voor u hier. Dus hoe kunnen we ruimte maken voor - wat is je naam? >> Sammy. >> Sammy. Hoe maken we ruimte voor Sammy? 

We gaan de n die voor mij. >> Oke. Dus we konden verhuizen de n mensen die voor hem, dus als jullie willen een bewuste, dramatische stap naar links te nemen. Ze hebben allemaal deed dat in koor, maar laatste keer dat ik schreef enkele code, je kunt niet sorteren van bewegen veel dingen in een keer. We kunnen doen in een lus, bewegende iedereen keer op keer. Dus als jullie het niet erg een stap terug in de juiste, en Sammy, als je een stap terug, want er is nog steeds geen plaats voor u, nu laten we dit doen. Waar was Sammy even geleden? Precies daar. Dus er is een kloof bestaat. Dus je zou kunnen verhuizen naar plek Sammy's. Nu volgende persoon en nu volgende persoon, nu volgende persoon. Nu hebben we ruimte voor Sammy. Nu, iemand uit het publiek - dat was goed, dat was juist, het voelde een beetje tijd in beslag - wat is sneller? Ja. [Student] Een nieuwe array? >> Wat is dat? >> [Student] Een nieuwe array? >> Oke, goed. 

Dus in overeenstemming met dit thema van slechts trade-offs, waarom ik niet gewoon een nieuwe array  en dan Sammy wordt zwemmen in de ruimte in de voorkant van deze mensen, bijvoorbeeld, en we kunnen gewoon beginnen met het vullen van een nieuwe array helemaal. Ook dat zou werken. Maar ik ben niet geïnteresseerd in het besteden van meer ruimte vandaag. Wat is een andere benadering? [Student] Swap. >> Oke. We konden gewoon ruilen deze 2 jongens. Wat is je naam? Mario. >> Mario. Dus Mario, je was op dit moment hier. Sammy, kunt u een back-up voor een moment? Mario was hier. We niet meer ruimte hebben voor u, dus als je het niet erg te gaan naar de plaats waar Sammy is, zullen we hier plaatsen Sammy, en nu zou ik zeggen dat swappen operatie Sammy's was veel sneller. We hebben een operatie om deze jongens te wisselen, of misschien 2 tot deze jongens ruilen, maar we hebben niet 1, 2, 3, 4, zodat zich beter voelt. Nu, wacht eens even. Ik soort van maakte het probleem groter, omdat nummer 4 was een soort van dicht bij het begin. Nu nummer 4 is een beetje dichter bij dit doel, maar ik heb niet echt weet of schelen. Dus dit is gewoon pech dat nummer 4 is een beetje verder weg van zijn voorbestemde plaats. Dus laten we nu herhalen dit algoritme. 

Om samen te vatten, zolang dat verhaal was, alles wat we hadden was lopen door de lijst op zoek naar de kleinste genummerde persoon. Dus laten we nu nog een keer doen. We hebben geen zorgen meer te maken over Sammy. We kunnen gewoon hier. Ooh! Nummer 2. Dat is een vrij klein aantal. 6, 8, 4, 3, 7, 5. Oke, goed. En gelukkig, bij toeval, ik niet te verplaatsen - >> Willie. Willie omdat hij in zijn juiste plaats nu. Laten we dit opnieuw en negeren deze 2 jongens. 6. Dat is een vrij klein aantal. Ooh! 8 is zeker groter. 4. Laten we focussen op 4. Ooh! 3 is nog beter. 7 en 5. Dus wat doen we nu met - >> Roger. >> Roger? Laten we hem ruilen met nummer 6. Dus als 6 en 3 zou willen ruilen, we hebben nu soort van gekregen geluk dat 6 is dichter bij waar ze zou moeten zijn, maar het is gewoon toeval hier. Dus laten we nu hier. 8 is een vrij klein aantal. Ooh! 4 is kleiner. 6, 7, 5. Wat moeten we nu doen? >> Swap. >> Precies. Dus nu laten we dit soort sneller. 8, 6, 7, 5. Waar komt 5 te gaan? Goed. Oke. 6, 7, 8. 6 krijgt om te blijven waar ze is. Wat is je naam? >> Rosalie. Rosalie krijgt om te blijven waar ze is. 7 krijgt om - Laten we eens kijken. 7, 8. Oke. Dus 7 krijgt om te blijven waar ze is. Wat is je naam? >> Amna. >> Amna. 

Dus Amna krijgt om te blijven waar ze is, en nummer 8 is nu al waar hij nu zou moeten zijn. Oke, goed. Voelen we gewoon het creëren van werk voor ons hier, dat wel. Wat is uiteindelijk de looptijd van dit algoritme? Als we denken over deze mensen niet als 8, maar als n? >> Het is n. Het is n stappen, maar we controleren elke keer weer. Oke. N maar je controleert elke keer? Oke, maar als het n stappen, zou ik niet in staat zijn geweest om u te sorteren op gewoon 1, 2, 3, 4? Oh! Oke, dat is een groot verschil. Dus n kwadraat waarom? Wat is er echt aan de hand? Er is n mensen in deze lijst, maar het vinden van de kleinste persoon in de lijst in het ergste geval, hoeveel stappen moet ik nemen? >> N. 

N, rechts, want in het ergste geval, nummer 1 is helemaal daar, dus ik moet gaan hem of haar. En toen ik eindelijk beseffen 1 was de kleinste, dan is het vrij snel om te wisselen zijn. Maar nu moet ik bij het begin beginnen en voor die op zoek zijn? De volgende kleinste persoon, dat is 2. Waar in het ergste geval is 2? Oh, mijn God. Het is helemaal hier aan het eind. Dus nu heb ik net gedaan een andere n stappen, een andere n stappen. En als we hebben n volk en in het ergste geval de kleinste persoon is n steenworp afstand, dat is weer n keer n, en dus hebben we weer hebben n kwadraat. Dit is niet zo goed voelde. En in feite, zelfs in het beste geval - veronderstellen dat ze beginnen gesorteerd - hoeveel stappen duurt het voor mij het gebruik van dit algoritme om deze n mensen sorteren? N kwadraat. >> Ik hoorde n kwadraat. Waarom n kwadraat? Omdat je nog steeds elke keer te controleren. >> Ja. En je moet om ze te verwisselen. >> Ook al zijn we mensen zijn een soort van alwetend in de zin visueel dat we kunnen gewoon een soort van te zien dat dit wordt gesorteerd, een computer is niet zo slim. Het zal hier en hier en hier kijken, maar als wat het zoekt, is het kleinste element, je weet alleen dat je het kleinste element van welk punt gevonden? Als je bij het einde. Maar op dat moment heb je alleen te vinden de huidige kleinste element. Je hoeft niet per se weten iets anders over de toestand van de wereld. Dus je moet opnieuw en opnieuw en opnieuw gaan. 

Dus deze keer heb ik echt kijk dom omdat ik het controleren, oke, 2, jij bent de kleinste, maar ik denk niet dat nog niet in totaal. 3, 4, 5, 6, 7, 8. Oke, goed. 2 was inderdaad de kleinste. Laten we nu vinden van de volgende kleinste. Oke. 3, je bent momenteel de kleinste. Laten we eens kijken. 4, 5, 6, 7, 8. Oke, ik heb weer geluk. 3 was inderdaad op de juiste plaats. Maar ik ga blijven doen opnieuw en opnieuw en opnieuw. Hoe kunnen we dat doen toch net iets beter? In plaats van het hebben van mensen borrelen paarsgewijze van klein naar groot en in plaats van heen en weer door de lijst selecteren de toenmalige kleinste persoon, waarom gaan we niet in plaats daarvan plaatst deze mensen in een nieuwe lijst stap voor stap? Laten we proberen dit. Laat me nu noemen dit ding insertion sort. Dus hier zijn we hier. Nummer 1. Ik geef niet om iemand anders in deze lijst. Mijn doel op dit moment is om nummer 1 zetten aan het begin van een gesorteerde lijst. En ik ga voor te stellen omdat ik maar 8 delen van het geheugen, willekeurig moment ben ik de muur tussen mijn zogenaamd ongesorteerde lijst, en iedereen die achter me ik ga om te beweren wordt gesorteerd. Dus nu hebben we nummer 1. Ik wil hem in te voegen in mijn gesorteerde lijst, dus ik ga gewoon mijn muur te bewegen hier, en nu heb ik beweren deze lijst wordt gesorteerd, wordt deze lijst ongesorteerd - althans voor zover ik weet. Ik kan niet alle nummers in een keer. 

Nu heb ik toevallig nummer 2 tegenkomen. Wat moet ik met hem doen? Ik heb nu steek je in de gesorteerde lijst. Maar merk hoe gemakkelijk dat was. Ik heb alleen maar om te kijken. Nummer 1 is er. Oh natuurlijk 2 naar de zijkant van nummer 1. Nu, wat doe ik met 3? Ik steek je in de gesorteerde lijst. Maar dat was super makkelijk. Dit is super eenvoudig, dit is super eenvoudig, dit is super makkelijk, super makkelijk, super eenvoudig. En nu is alles gesorteerd achter me, en hoeveel stappen heeft dat duren? [Studenten] N. >> Dus het is alleen maar n. We hebben geluk gehad. Het was slechts n waarom? >> [Student] Omdat de lijst is gesorteerd. De lijst is al gesorteerd. Dus we hebben geluk gehad. Maar we ontwierp een algoritme deze tijd dat dat soort van geluk maakt gebruik, die het best case scenario, door niet te verspillen onnodig veel tijd. Dus we hebben nu wat we bubble soorten bel waar mensen soort borrelen paarsgewijze. We hebben nu selection sort waar we rukken uit de kleinste persoon opnieuw en opnieuw. En nu hebben we insertion sort waar we soort van pro-actief zetten mensen waar ze horen in een steeds gesorteerde lijst. Als we konden, een applaus voor deze jongens hier. [Applaus] Laten we hier nemen onze 5-minuten pauze. En als we terug komen, zullen we blazen al deze algoritmen uit het water met iets beters. Oke. Heel erg bedankt. U kunt die bewaren als souvenir. Oke. We zijn weer terug. 

En om heel snel samen te vatten, we deze 3 verschillende benaderingen moesten sorteren, het hele punt van die was om tot het punt waar iemand als Alex kunnen zoeken in een lijst met getallen sneller dan iemand als Sean kon. En ook al hebben we zo'n eenvoudige voorbeelden met 8 cijfers, je zou kunnen extrapoleren gemakkelijk tot 8 webpagina's, 8 miljard webpagina's, of 800 miljoen vrienden op Facebook. Dus deze algoritmen kan zeker schalen naar dat soort waarden, en de ideeën zijn uiteindelijk hetzelfde. Dus bubble sort was de eerste waar we soort van borrelde de grootste persoon helemaal naar rechts door het omwisselen van mensen paarsgewijze. Dan hadden we wat we selection sort noemen waar ik een beetje meer bewust keek door de lijst, het selecteren van het kleinste getal opnieuw en opnieuw en opnieuw, het logische resultaat daarvan is dat de lijst uiteindelijk wordt gesorteerd. Toen in de derde, ik gestoken mensen in hun juiste plaats, en we hebben een zeer gekunsteld voorbeeld in dat de lijst al gesorteerd, maar dat was om het bericht te verzenden dat in insertion sort's geval, kun je je geluk. Als de nummers zijn al gesorteerd, is het alleen maar om u te n stappen te ondernemen om zo veel te bevestigen, terwijl selection sort je een beetje meer tunnelvisie en je hoeft niet eens beseffen dat de lijst al is gesorteerd. Dus laten we hier bubble sort in actie. In het volgende voorbeeld, zijn we op het punt om verticale balken te zien wiens hoogten vertegenwoordigen nummers, zodat we kunnen sorteren van visualiseren sorteren gebeuren. Hoe kleiner de bar, hoe kleiner het getal, hoe groter de balk, des te groter het getal. 

En spelen we het op dit standaard snelheid. Het zal een beetje snel bewegen voor nu, maar rood is wat er met 2 bars worden vergeleken naast elkaar. En als je goed kijkt, wat er gebeurt is dat als de bars zijn niet in orde, de kleinste wordt naar links bewogen, de grotere naar rechts en dan houdt u vooruit. Dus als we dit doen opnieuw en opnieuw, merken dat de kleinste bars zullen blijven tippen hun weg naar links en de grootste bars zijn gaan houden tippen hun weg naar rechts. En inderdaad, we beginnen een patroon te zien helemaal aan de rechterkant net zoals we zagen 8 en dan op 7 uiteindelijk opborrelt naar het einde van onze menselijke lijst. Dus dit gaat zeer snel een beetje vervelend, dus laat me dit te stoppen voor een moment. Laat ik de snelheid om veel sneller. Ik ben niet het algoritme te veranderen, ik ben gewoon het maken van de animatie gebeurt sneller. Toch bubble sort, hetzelfde algoritme, maar nu zie je veel sneller dan onze verbale demonstratie dat de grootste elementen inderdaad borrelen naar de top. 

Even terzijde, deze kleine vierkantjes op de bodem links-en rechtsonder zijn net kleine herinneringen aan hoeveel vergelijkingen je doet. Maar voor nu, kunnen we ons richten op de piramide die is vorm aan te nemen, en daar gaat het. Het kleinste element is aan de linkerkant, de grootste aan de rechterkant, en alles wat daar tussen zit. Laten we nu eens in plaats daarvan een kijkje op selectie sorteren nemen. Ik ga om verder te gaan en stop raken. We gaan een nieuwe willekeurige reeks tralies te krijgen. Selectie sorteren, recall, gaat door de lijst opnieuw en opnieuw en opnieuw, het plukken van de kleinste element. Dus hier is selectie sorteren. Het lijkt erop dat er minder werk gebeurt nu omdat we niet vergelijken paarsgewijze maar we gewoon soort van kersen plukken van de kleinste elementen van rechts naar links. Dat heeft heel weinig tijd, dus er is al een tweedeling. Alleen maar omdat een algoritme wordt gezegd dat n kwadraat tijd in beslag nemen, zoals bubble sort en net als selectie sorteren, die zijn echt het ergste geval looptijden. Bijvoorbeeld, in het geval van, laten we zeggen, selectie sorteren, Ik heb eigenlijk ben het selecteren van de kleinste mens en zetten hem of haar hier, dan doe ik het weer, dan doe ik het weer, maar er was een lichte optimalisatie ik kon maken. 

Zodra ik verhuisd nummer 1 hier - Sammy in dat geval - wat heb ik nodig om daarna met hem doen? >> [Student] Laat hem. Laat hem, toch? Niets. Ik heb niet meer nodig om ooit praten Sammy, want als ik had gekozen voor de kleinste element en hier zette hem, waarom tijd verspillen gaan aan het einde van mijn hele lijst? Op de volgende iteratie laat me eigenlijk alleen verhuizen naar nummer 2, alleen voor nummer 3. Dus in werkelijkheid, was ik niet te doen n dingen n keer. Ik deed n dingen, dan n - 1 dingen, dan n - 2 dingen, dan is n - 3 dingen, dan n - 4, puntje, puntje, puntje. We hebben een beetje een geometrische reeks, die gewoon betekent je bent het optellen van steeds kleinere aantallen. Niet n + n + n + n maar n + 7 + 6 + 5 + 4 + 3 + 2 + 1. En wat die over het algemeen werkt zijn om - Ik ga verknoeien mijn board hier voor slechts een moment - dat gaat werken aan iets als n (n - 1) zijn / 2 als we gewoon een soort van blik op de achterkant van een wiskunde boek waar je alle spiekbriefjes voor de formules. Als je net iets toe te voegen n + n - 1 + n - 2, het werkt te zijn iets als dit. En als we gewoon een soort van vermenigvuldigen dit uit, dat is n kwadraat min n / 2. Ik bleef maar zeggen n kwadraat, maar, en dat komt omdat ik was een soort van het nemen van een mentale snelkoppeling omdat in werkelijkheid n squared minus n gedeeld door 2 is inderdaad het werkelijke aantal stappen dat een algoritme zoals selection sort zou nemen als we echt geteld al die vergelijkingen en alle kleine drukke werk dat we aan het doen waren. Maar eerlijk gezegd, een keer n krijgt om als een miljoen of een miljard, die de heck cares als je doet een miljard kwadraat min een miljard gedeeld door 2? Een miljard kwadraat is een enorm aantal. U kunt nog eens een miljard af van het met - n. Het is niet zo'n big deal. Dus hoe groter de getallen, hoe minder belangrijk deze lagere geordende termen zijn. Who cares als je delen door 2 als je het hebt over quadriljoenen van aantal stappen? 

Dus in het algemeen, computer wetenschappers hebben de neiging om weg te gooien alles maar de grootste term, en we gewoon een soort van vereenvoudiging van de wereld en zeggen dat dat algoritme duurde ongeveer vierkant n stappen. Dat is de looptijd van een algoritme. Dus we zullen terugkeren naar dit in slechts een ogenblik met een aantal concrete voorbeelden, maar voor nu, dat is een soort van de intuïtieve motivatie achter net vereenvoudiging van onze wereld en praten over de belangrijkste termen in plaats van het krijgen in al deze mooie formules. Dus dat was selectie sorteren, en we kregen een beetje geluk hebt. Laten we eens kijken naar insertion sort. Laat me ga je gang en beginnen deze ook. Let nu op het patroon dat er gebeurt is een beetje anders, en zijn we begonnen met willekeurige getallen, maar als we echt tellen het aantal stappen in het ergste geval, Als de lijst begonnen volledig in de juiste volgorde, we alleen n stappen zoveel realiseren. 

Als de lijst waren eigenlijk achteruit - bijvoorbeeld in dit geval - dan merken we eigenlijk moeten veel meer werk in dit geval te doen. En het moet soort van gevoel voor u als deze is een soort van harder werken om die kleinere elementen te krijgen aan de linkerkant, en dat komt omdat we pech. De lijst werd per ongeluk gesorteerd in omgekeerde volgorde. In tegenstelling met insertion sort, als we na te bootsen wat we hebben gedaan met onze mensen hier door te beginnen met gesorteerd iedereen en dan beginnen, is het een vrij goed algoritme, toch? Het is al, in feite, gesorteerd. Dus laten we proberen samen te vatten precies hoeveel tijd deze dingen nemen ons door de invoering van een beetje van jargon of notatie die eigenlijk veel eenvoudiger dan de fanciness soort suggereert. Dit ding hier, dit grote O op het scherm, is wat een computer wetenschapper zal in het algemeen gebruik maken van de worst case looptijd van een algoritme beschrijven. 

Nogmaals, door het ergste geval, het is helemaal context-afhankelijk. Wat bedoelen we met het ergste geval volledig afhankelijk van het probleem waar we het over. Maar in het geval van sortering, wat is het slechtst mogelijke scenario? Alles is naar achteren omdat het gewoon voelt als dat betekent een hoop werk voor ons. Ik heb noteerde een paar van de algoritmen die we tot nu toe gezien: lineair zoeken, binair zoeken zoals bij het telefoonboek of de stukjes papier, dan bubble sort, selectie sorteren en insertion sort, zoals we zagen met onze mensen, en dan 1 andere dat is uiteindelijk gaan heten sorteren samen te voegen. Dus in lineair zoeken in het ergste geval, hoeveel stappen die zij nemen om de nummer 7 vinden Als er n deuren zoals Sean faced? >> [Student] N. N. Dus we gaan naar grote O van n te schrijven. Ik ga gewoon in te vullen in een aantal spaties. Dit is slechts een raster van losse flodders. Maar in het beste geval met lineaire zoeken, zou 7 zijn geweest aan het begin van de lijst, en Sean zou kunnen zijn begonnen naar het begin van de lijst. Dus als u gebruik maakt van lineair zoeken en een controle van links naar rechts of misschien rechts naar links - ze zijn gelijkwaardig - in het beste geval hoeveel stappen zou lineair zoeken, achtig algoritme Sean's, nemen? Slechts 1 stap. 

Dus ik ga zeggen is dat de omega notatie. Dit is gewoon hoofdstad omega. Omega is gewoon de sexy manier om te zeggen beste geval looptijd. Dus in het beste geval de looptijd is een enkele stap of constante aantal stappen - 1 in dit geval - maar in het ergste geval, big O, is het eigenlijk n stappen. En deze hier, theta, we eigenlijk niet van plan om te kijken naar dit moment. Het is niet relevant voor dit specifieke voorbeeld. Maar laten we nu proberen binaire zoekopdracht. In het ergste geval met binair zoeken, wordt het aantal stappen die zij gaan nemen om het getal 7 vinden of wat we zoeken? >> [Student] Inloggen n. Nog steeds te log n te nemen want net als Alex kreeg pech als we echt gewerkt door het probleem methodisch en ze had het getal 7 niet vinden tot de laatste deur keek ze, ook al, in alle eerlijkheid, kreeg ze weg te gooien bepaalde deuren langs de weg, binair zoeken in het ergste geval heeft een looptijd van log n. En nogmaals, dat spreekt tot deze delen en het veroveren. Maar hoe zit het in het beste geval? En Alex daadwerkelijk ervaren dat het beste geval gelijk als ze kwam op het podium. Hoeveel stappen heb die rekening in binaire zoeken? >> [Student] 1. 1, alleen maar omdat ze geluk hebben gehad. Maar dat is prima, want omega verwijst naar beste geval scenario's, beste geval ingangen, zelfs als het is gewoon willekeurig stom geluk. 

Nu, ook dit gaan we gewoon een soort van verlof leeg voor nu. Hoe zit het nu bubble sort? In het ergste geval met bubble sort, iedereen is in omgekeerde volgorde, dus we hebben een hoop borrelende doen. Maar hoeveel stappen is dat duren in het ergste geval? >> [Student] N kwadraat. Dit was de n kwadraat, want als je erover nadenkt, als de lijst volledig naar achteren - 8 is hier, 1 is hier - als ding begint te borrelen, wordt het getal 8 naar deze wijze zo verplaatsen op deze manier, op deze manier, maar waar is de nummer 7 in het ergste geval? Hier is ze nog steeds daar. Dus we moeten het doen opnieuw en opnieuw. En dat is waar we n stappen, dan is n - 1 stappen, dan is n - 2 stappen. En als je op mijn woord te geloven - dat als je soort vermenigvuldigen het uit, het is ongeveer n vierkant op het einde met een aantal andere termen die we zullen negeren voor nu - dan in het ergste geval bubble sort is n kwadraat, geven of te nemen. Maar hoe zit het beste geval met bubble sort? Wat is de beste case scenario? Alle getallen al gesorteerd. En wat was de heuristische ik gebruikte, de truc die ik gebruikte, om te beseffen dat ik geen werk gedaan en kon daarom vroeg stoppen? [Student] Bekijk het eens. >> Een keer controleren het. Maar wat deed ik langs de weg? Ik was het bijhouden van hoeveel swaps ik heb gemaakt. En ik realiseerde me als ik niet gerekend een swaps op mijn vingers, dan heb ik geen werk gedaan. Ik zou zeker niet proberen om geen werk opnieuw te doen, dus ik kan gewoon stoppen. 

Dus in het beste geval van bubble sort wanneer de lijst wordt al gesorteerd, wat zou je zeggen dat de omega-notatie is, het beste geval looptijd? Het is gewoon n. We moeten wat werk te doen, maar we moeten een wandeling is de moeite waard van het werk te doen. En ook hier ga ik dit deel leeg laten. En nu selectie sorteren. Selectie soort had ik het plukken van de kleinste persoon opnieuw en opnieuw. En wat hebben we zeggen dat de looptijd van dat was? Dat was n kwadraat in het ergste geval. En helaas, in het beste geval het is ook n kwadraat omdat ik niet de soort alwetende oog van de hele wereld; Ik weet alleen dat op een volledige iteratie dat ik inderdaad heb de kleinste persoon gevonden. Dus selectie soort soort zuigt in die zin, maar de kop is het is een soort van intuïtief. Het is vrij gemakkelijk om te coderen op, omdat alles wat je hoeft te doen is schrijven een paar geneste for-lussen, typisch, dat doorloopt naar het kleinste element en plaatst het kleinste element waar het hoort aan het einde van de lijst. Dus ook hier zal een trade-off te zijn. De hoeveelheid tijd die het neemt je mee te denken en om daadwerkelijk iets te ontwikkelen door het schrijven van code zou heel goed kost meer tijd als je wilt een beter algoritme en snellere prestaties. 

Maar als je echt gewoon een soort van code iets op snelle en vuile en gewoon een soort van te nemen de domste mogelijk beeld je maar kunt bedenken, dat zou kunnen nemen je een paar minuten om de code, maar met grote gegevenssets uw algoritme kan uren te lopen. En zelfs ik in graduate school zou soms maken deze trade-offs. Het zou 3am zijn, probeerde ik een aantal zeer grote dataset te analyseren met betrekking tot de veiligheid onderzoek dat ik aan het doen was, en het was ofwel besteden 5 minuten tweaken mijn programma om de gegevens te analyseren en te gaan slapen of breng 8 uur krijgen van het precies goed, zodat het draait direct en niet gaan slapen. En dus is er ook het is een soort van een bewuste beslissing. Minder ontwikkelingstijd, meer slaap. Achteraf heb ik waarschijnlijk niet aan te moedigen dat wanneer het doel hier is om de kwaliteit te optimaliseren van de code, maar dat ook in de echte wereld is een zeer redelijke trade-off. Minder tijd, minder prestaties of vice versa. Dus hier zijn we eindelijk de kans krijgen om te praten over theta. Theta notatie is iets informatici kunnen brengen in een gesprek wanneer grote O en omega toevallig hetzelfde. U zegt theta om echt de boodschap sturen dat dit is een soort van een strakke gebonden. Het maakt niet uit of het scenario is goed of slecht, het is n kwadraat. Dus het is gewoon niet relevant in deze verhalen hier. Insertion sort is de laatste hebben we gekeken naar, waar ik was gewoon het plaatsen van iedereen op de juiste plaats. In het beste geval wat was de looptijd van insertion sort zoals we zagen het hier? [Student] De beste geval? >> De beste geval. 

Het werd n, omdat in het beste geval iedereen gesorteerd, en Sammy en niemand anders moest echt helemaal te verplaatsen. Ze waren al in hun juiste plaats. Dus insertion sort in het beste geval is, in dit geval, n. Maar in het ergste geval het is een soort van n in het kwadraat. Waarom? Als mijn lijst van de mens is in omgekeerde volgorde, Ik voor het eerst beginnen met het cijfer 8 en ik steek hem of haar in de juiste positie, dat is hier. Ik soort van verhuizing naar de kant. Deze jongens zijn ongesorteerd, hij of zij wordt gesorteerd. Maar nu ik toevallig te vinden wie nu? >> [Student] 7. 7 in het ergste geval omdat het in omgekeerde volgorde. 

Dus hier is 7. Waar komt 7 thuis? Zeker achter me. Maar nu 7 hoort eigenlijk niet direct achter me maar achter nummer 8, dus ik moet zeggen: "Neem me niet kwalijk, nummer 8, kunt u alstublieft gaan op deze manier "Te maken voor 7?" Nu ik tegenkom 6. "O, neem me niet kwalijk, nummer 8 en nummer 7, kunt u om plaats te maken voor 6?" Dus met andere woorden, met insertion sort, ook al doe ik niet veel beweging, de mensen achter mij doen veel meer werk, en dat moet iemand zijn tijd kosten. Het gaat om de computer tijd kosten. Dus in het geval van insertion sort we nog steeds lijden. Als je begint te tellen het totaal aantal stappen, hebben we uiteindelijk raakt ongeveer n kwadraat omdat deze jongens moeten maken voor de mens te voegen terug in die lijst. En dus in dit geval theta is niet alleen van toepassing op de bijzondere verhaal bij de hand. Dat is allemaal mooi en goed. We hebben deze 3 verschillende manieren van praten over de looptijd. Maar wat betekent dit eigenlijk in reële termen, als we echt proberen te coderen van een algoritme? 

Laat me voorstellen dat er een nog betere algoritme die er zijn dat zelf heeft een aantal afwegingen. We gaan noemen samenvoegen sorteren, en het is een soort van deze magische algoritme dat werkt gewoon sneller een of andere manier, en het is zo makkelijk om, drukken op zijn minst in pseudocode. De implementatie van dit algoritme merge sort gaat als volgt. Als je krijgt n elementen - n getallen, n mensen, wat dan ook - eerst is er een sanity check. Als n kleiner is dan 2, samenvoegen sorteren gewoon stopt. Het geeft, zo te zeggen. Waarom zou je stoppen als n kleiner is dan 2? >> [Onverstaanbaar student reactie] Juist. En voorts, n niet het aantal in de lijst, n is de grootte van de lijst. Als n kleiner is dan 2, dat betekent lijst ofwel 1, waar je natuurlijk gesorteerd als het 1 nummer, of 0, in welk geval er niets te sorteren, dus we moeten dit soort base case. Als de lijst is zo kort dat er gewoon niets te doen, letterlijk niets doen. Return. Anders sorteren de linker helft van de elementen, vervolgens sorteren de rechter helft van de elementen, Vervolgens voegt u de 2 helften gesorteerd. 

Dit soort lijkt een beetje cheat waarbij ik vraag u hoe u elementen sorteren en je zegt me dat, 'Sorteer de linker helft, sorteren de rechter helft. " Ik heb zoiets van, 'Oke. Hoe ga je de linker helft sorteren? " "Sorteer de linker helft van de linker helft, sorteren de rechter helft van de linker helft, en dan gedaan." Je bent nogal cyclisch te definiëren wat het betekent sorteren om, maar het blijkt dat is eigenlijk briljant in dit geval. Het is niet echt deze vicieuze cirkel die nooit eindigt omdat het niet eindigt wanneer? >> [Student] Wanneer u 1 ding te bereiken. Wanneer u 1 ding te bereiken. Dus hoewel je zou kunnen beginnen met 8 personen en ik zeg: "Sorteer de linker helft van deze mensen, deze 4 mensen, "dan zeg ik:" Hoe sorteert u de linker helft? " "Nou, hier sorteren de 2 personen." En dan ben je als: "Oke, prima." "Hoe sorteert u de linker helft van die mensen? ' "Gewoon hier sorteren deze 1 persoon." Wat is de briljante openbaring nu? Ik moet 1 persoon te sorteren. Gereed. Ik heb niet aan een werk te doen. Maar nu heb ik deze persoon te sorteren, maar ze zijn een enkele persoon, niets te doen. 

Dus de magie is blijkbaar in deze derde stap: het samenvoegen van de gesorteerd helften. Dus samenvoegen soort neemt deze briljante inzicht dat als je breekt een groot probleem naar beneden in 2 kleinere, identieke-en kleinbedrijf problemen en dan gewoon een soort van lijm de kleinere oplossingen aan het eind, Ik stel voor dat we veel kunnen doen, veel beter [tikkend geluid] dan elk van selection sort of insertion sort. Ik heb eigenlijk genegeerd dat een half uur, maar ik weet echt niet wat er gaande is vandaag buiten. [Zoemend geluid] [gelach] Dus laten we eens kijken of we dit zien met een beetje hulp van onze vriend Rob Bowden. Er zijn 2 grote stappen in het proces van merge sort. Ten eerste, continu splitsing van de lijst van de kopjes in twee helften totdat we een heleboel lijsten met slechts 1 kopje in hen. Maak je geen zorgen als er een lijst bevat een oneven aantal en je kunt niet een perfect zuivere snede tussen hen. Gewoon willekeurig kiezen welke lijst om de extra kop binnen zijn Dus laten we splitsen deze lijsten. Nu hebben we 2 lijsten. Nu hebben we 4 lijsten. Nu hebben we 8-lijsten met een kopje in elke lijst. Dus dat is het voor stap 1. Voor stap 2 hebben we herhaaldelijk samenvoegen paren van lijsten met behulp van de merge algoritme we leerden voorheen. Het samenvoegen van 108 en 15 eindigen we met de lijst 15, 108. Het samenvoegen van 50 en 4 hebben we uiteindelijk met 4, 50. Het samenvoegen van 8 en 42 we eindigen met 8, 42. En samenvoegen 23 en 16 eindigen we met 16, 23. Nu zijn alle onze lijsten zijn van maat 2. Merk op dat elk van de 4 lijsten gesorteerd, zodat we kunnen beginnen met het samenvoegen paar lijsten weer. Het samenvoegen van 15 en 108 en 4 en 50 nemen we eerst de 4, dan de 15, dan 50, dan 108. Samenvoegen 8, 42 en 16, 23 nemen we eerst de 8, dan de 16, dan de 23 dan de 42. Dus nu hebben we slechts 2 lijsten van maat 4 hebben, is elk van die gesorteerd. Dus nu hebben we samenvoegen van deze 2 lijsten. Eerst hebben we de 4 te nemen, dan kunnen we de 8 nemen, dan nemen we de 15 en 16 en 23 en 42 en 50 en 108. En we zijn klaar. We hebben nu een gesorteerde lijst. 

Rob was een soort van gebruik te maken van iets dat we nog niet hebben gedaan. Er werd gesuggereerd, maar we hebben niet echt te doen. Hij deed iets fysiek met de kopjes die suggereert dat hij werd het stadje een bron naast de tijd. >> [Student] Space. >> Het was ruimte. Het feit dat hij dit soort bi-level tafel had waar hij de ruimte hier en ruimte hier beneden was eigenlijk implicerend dat hij twee keer zo veel ruimte met behulp van als een van onze algoritmen tot nu toe - insertion sort, bubble sort, of selectie sorteren - maar hij was gebruik te maken van deze extra ruimte om soort van verhuizing dingen heen en weer en tegelijk zo in orde is. En ook al voelt het alsof we in een gesorteerde lijst, die aanvoelde als het duurde een tijdje. In werkelijkheid, wat Rob deed was precies dit algoritme. Hij voor het eerst nam het probleem van de grootte n, opgesplitst in een linker helft en een rechterhelft. Dat is toen hij verhuisde de cups. Toen herhaalde hij dat proces. Hij verdeelde 4 in 2 sets van 2 hier en hier. Toen dit proces herhaald en verdeeld 2 in 2 sets van 1 voor elk van deze verschillende koppen. En dat is waar de briljante gelegenheid zich voordoet. Op dat punt in het verhaal, Rob had 8 lijsten van maat 1, die alle reeds gesorteerd. 

Dus wat deed hij gaan doen? Paarsgewijze hij nam deze gesorteerde lijst en deze gesorteerde lijst en samengevoegd hen. Toen nam hij deze en samengevoegd hen, dan is dit een en samengevoegd hen, dan is dit een en samengevoegd hen. En wat deed hij nu? Hij vervolgens opnieuw samengevoegd de grotere lijsten en vervolgens weer samengevoegd de grotere lijsten. En als u denkt over dit gewoon intuïtief voor nu, was wat hij echt aan het doen? Hij verdeelde het probleem in half in half in half in half om deze super kleine lijsten te krijgen. En hij was een soort van combinatie van dubbel,, dubbel,. Dus hij werd twee keer doen zo veel werk als we tot nu toe gezien met alles wat met verdeel en heers, maar geen groot probleem. Twee keer zo veel werk is niet zo'n big deal. Het is gewoon een constante factor. En net als onze rekenkundige uitdrukking voor, ik ga even te strepen constante factoren zoals maal 2. Who cares? Als het 2 miljard keer 2, dat is nog steeds veel trappen. Dus dit samenvoegen stap lijkt te zijn de sleutel inzicht. Laten we een wandeling door dit net numeriek voor - Oh, dat is nog niet te worden voortgezet. Laten we een wandeling door dit numeriek alleen maar om daadwerkelijk te zien hoe dit zich afspeelt. Dit is meestal gewoon een beetje slecht man animatie. Laten we stellen dit. De looptijd van de merge sort - we hoeven alleen maar een manier van praten over dit. Dit is geen wiskunde, dit is gewoon een soort van een beknopte manier van uitdrukken onszelf. Dus t de tijd voorstelt en n staat voor wat? >> [Student] De grootte van de - 

[Malan] De omvang van het probleem, het aantal mensen. Dus ik te beweren dat de looptijd tot en met n volk sorteren gaat op 0 hoeveelheid tijd Als n kleiner is dan 2, want als je 1 kopje of geen bekers, heb je niets te sorteren. Maar meer in het algemeen, ik ga voor te stellen dat de looptijd tot en met n elementen sorteren zal de tijd voor het sorteren linkerhelft plus rechts helft plus - wat is dit extra + n? >> [Student] Merge soort. [Malan] Het is eigenlijk het samenvoegen, want als je n / 2 elementen hier en je hebt hier n / 2 elementen, het maakt hoeveel tijd nemen om ze samen te voegen? Net als Rob, moet je deze plukken hier, misschien hier plukken over, Hier plukken dan, hier plukken dan, hier plukken over. Je moet een keer raken elk van de cups. En als er 4 kopjes plus 4 kopjes, dat is 8 kopjes of, meer algemeen, 8 n cups. Dus de samenvoeging stap die we kunnen uitdrukken als n, en daarbij speelt letterlijk het aantal keren Rob fysiek aangeraakt een van die piepschuim bekers. Dus laten we nu doen een willekeurige voorbeeld. Als er 16 kopjes, wat is de looptijd van het sorteren, met behulp van Rob's algoritme, 16 kopjes? Het is 2 keer de hoeveelheid tijd die het kost om 8 kopjes sorteren omdat we 8 koppen hier hebben, 8 kopjes hier. Ik weet niet hoe lang dat duurt, dus we generaliseren het als T voor het moment. Wie weet wat het is? Maar nu kan ik sorteren van recursief of herhaaldelijk dezelfde vraag. Hoeveel tijd is er nodig om 8 kopjes sorteren? 8 koppen Ik ga zeggen neemt de hoeveelheid tijd die het kost om te sorteren 4 kopjes plus 4 kopjes, vervolgens samen te voegen ze samen. Fijn. We krijgen in een cyclus reeds. Hoe lang duurt het om 4 kopjes sorteren? De tijd die nodig is om te sorteren 4 kopjes is 2 kopjes en 2 kopjes sorteren plus de fusie proces. Fijn. Hoe lang duurt het om 2 kopjes sorteren? 2 kopjes is de hoeveelheid tijd die het kost om te sorteren 1 kop plus de tijd die nodig is om te sorteren nog een kopje vermeerderd met het bedrag van de tijd die nodig is om te fuseren, dat op slechts 2. 

Fijn. Laatste vraag. Hoe lang duurt het om 1 kop sorteren? Hier is de base case die we voorspelden we eerder te raken. Het feit dat het geen werk neemt ook de volgorde van de kleinste van de problemen betekent dat nu, een soort van lagere school stijl, kunnen we gewoon gaan beginnen met het aansluiten van deze nummers opnieuw We weten nu wat T van 1 is, dus ik kan aansluiten 0 voor T van 1. Dat geeft mij het antwoord op T van 2, die dan kan ik aansluiten hogerop. Dat geeft me T van 4, die ik kan aansluiten hogerop. Dat geeft me T van 8, die ik kan aansluiten hogerop. En als ik eigenlijk dat wiskunde door het aansluiten van deze antwoorden, Ik dan T van 16 is 64. En wat doet 64 voorstellen? Als T is 16, ja, het is 16 keer 4. Dus ik beweren nu dat de looptijd van dit ding heet samenvoegen sorteren - en dit gaat worden de chicste van de opties die we hebben tot nu toe gezien - zal worden genoemd n log n want hoe vaak kan Rob splitsen van een heleboel kopjes in de helft? Meld u n. Het is hetzelfde als het telefoonboek voorbeeld is hetzelfde als de zelf tellen voorbeeld. 

Hoe vaak kun je verdelen iets in de helft? Echter, er is dit samenvoegen stap. Je zou kunnen hebben om de kopjes te verdelen in half opnieuw en opnieuw en opnieuw, maar elke keer als je gaat te hebben om samen te voegen. En wij zeiden eerder dat het samenvoegen n kopjes n stappen neemt want je moet rukken uit een beker, ruk het uit een beker, en je moet elke kop een keer aan te raken, net als Rob deed. Dus als we iets log n keer en we doen n dingen op elk van deze iteraties, elk van deze halvings hebben we n keer log n. Als we aansluiten 16 in dit voorbeeld 16 keer log van 16 - maak je geen zorgen over de reden waarom dit het geval is voor nu, want ik heb niet getekend de basis - maar log van de basis 2 van 16 is 4, 16 maal 4 is 64. Maar daarentegen, als we hadden gebruikt bubble sort of selectie sorteren of insertion sort met 16 nummers, wat zou de looptijd zijn als n 16? Het zou 16 kwadraat, dat is 256, dat zelfs als je nog niet helemaal volgde alle wiskunde, 256 is groter dan 64. Dat is echt de magische afhaalmaaltijden hier. En beseffen dat het werken door middel van deze in kleinere voorbeelden als je wilt op een PSET maakt het allemaal veel intuïtiever. Wat dat echt betekent in termen van het gevoel van dit algoritme is: Als we echt kijken naar merge sort hier - laat me trek het hier in dit venster - Dit is een iets ander voorbeeld, waarbij we alle 3 van deze algoritmen - bel, selectie en samenvoegen - net naast elkaar. 

Ze zijn allemaal begonnen met willekeurige bars, en dat is goed. Niemand heeft een fundamentele voordeel boven de andere. Ik ga in een moment op elk van deze animaties - Start, Start, Start - zo snel ik kan zodat ruwweg ze beginnen op hetzelfde moment, en laten we van mening zijn dat bubble sort's ergste geval looptijd is wat? >> [Student] N kwadraat. N kwadraat. Selectie soort ergste geval looptijd is? N kwadraat. En merge sort is blijkbaar - zelfs als je niet helemaal volg alle wiskunde nu, het zal nu veel intuïtiever na verloop van tijd - is, we beweren, n keer log n. En omdat log n is strikt kleiner is dan n keer hebben we grote getallen, n log n maal kleiner is dan n maal n n of vierkant. Dus wat is het om daadwerkelijk een beter algoritme in termen van looptijd, n keer log n tegenover n kwadraat Daar gaan we. Klik, klik, klik. 

Dat is wat het betekent om te gebruiken iets als merge sort. We hebben een moment. Laten we eens kijken wat er hier gebeurt. [Grinnikt] Wiens geld is op bubble sort? Het hangt nogal van de input soms. Laten we eens kijken. Kom op. Het voelt alsof hij een inhaalslag. >> [Student] Ga, bubble sort! [Studenten murmelende] [Malan] Ja, ja. [Studenten morren] Ga, ga, ga! [Alle gejuich] [applaus] Dus nu met 1 laatste, laatste demo, als het een beetje lastig om je geest te wikkelen rond de wiskunde of soort van de visualisatie daar, kun je eigenlijk horen de snelheden van verschillende algoritmes verschillend. Dit is een animatie iemand gemaakt die daadwerkelijk associeert klinkt met het proces van verwisselen en de hoogte van de staven. Zoals we hier zien, is er een paar meer sorteren algoritmen die er zijn die mensen gedacht hebben. Deze eerste gaat insertion sort te zijn, en dit zal vliegen door en geven u een hoorbare gevoel van hoe deze verschillende algoritmen werken. Hier is insertion sort. [Elektronische piepen] [Malan] Bubble soort. [Snellere elektronische piepen] [Malan] Selectie sorteren. [Snellere elektronische piepen] [Malan] Merge soort. [Elektronische piepen] [Piepen vertraagt] [gelach] [Malan] Gnome soort. [Elektronische piepen] 

Dit is CS50. We zien je volgende week. [Applaus en gejuich] 

[CS50.TV]