Spreker: Oke, dit is CS50. Dit is het einde van week drie, en als je hebt geen voordeel reeds genomen, weten dat er de lunch zal zijn deze vrijdag zoals gewoonlijk, waar u kunt genieten van een goed gesprek en eten bij Fire and Ice met enkele van CS50's personeel en klasgenoten. Ga naar deze URL hier. Nu u zich wellicht herinnert, of dat u kan binnenkort op de hoogte zijn, deze dingen hier, die worden gegeven aan het einde van het semester voor vele klassen. Zogenaamde examen blauw boeken, waarin je schrijft je antwoorden op examens. Nu heb ik hier 26 dergelijke blauw boeken, op elk van hen is geschreven een naam, A tot Z. En inderdaad de namen zijn zo simpel, A door Z. En een van de doelen bij de hand vandaag gaat worden om verder te gaan wat we begonnen op maandag, wat niet zozeer te kijken naar code, maar echt op zoek naar ideeën en het oplossen van problemen. Een van de doelen en beloften van deze cursus is om je te leren om meer te denken zorgvuldig, meer methodisch, en problemen efficiënter oplossen. En inderdaad, we kunnen dat echt doen zonder zelfs het aanraken van een regel code. Dus ik heb een paar van olifanten hier vandaag, oranje en blauw, Als we een vrijwilliger konden krijgen, misschien uit verder terug dan normaal. Hoe zit het daar, kom naar beneden. Waarvan het doel zal zijn om helpen plus beheren dit examen hier. Wat is je naam? PUBLIEK: Mary Beth. Spreker: Mary Beth, kom op. Laat me de microfoon hier voor jou. Leuk je te ontmoeten. PUBLIEK: Leuk je te ontmoeten. Spreker: Oke, dus ik heb hier blauw boeken A tot en met Z, en ik ga om te beweren dat Ik heb een van de studenten, en ze komen in enigszins willekeurig aan het einde van een drie uur examen blok, zodat ze uiteindelijk in sommige semi-willekeurige volgorde als deze. Nu je baan in slechts een moment gaat om be-- dit is eigenlijk hoe ze speelde eind de klasse, waarschijnlijk. Nu je baan gaat worden, heel gewoon, deze blauwe boeken voor ons gekozen afstand van A tot Z. PUBLIEK: Oh, dit is gaat een eeuwigheid te duren. SPEAKER: En we zullen kijken als je dit doet, geen druk. PUBLIEK: Nee, geen druk of iets. SPEAKER: En voor de lol, laten we een timer. PUBLIEK: Zo leuk, zo leuk. SPEAKER: Ik kan de microfoon te houden voor u. Oke, we hebben gewoon verdubbeld onze snelheid. Dus in de tussentijd, laat me stellen wat gaan op de vraag voor Mary Beth zijn is wat ze aan het doen, hoe is Ze gaan over het oplossen van deze? En in feite zou je niet hebben ooit nagedacht over iets zo eenvoudig als bij de overhandiging een stijging van 26 boeken als deze, die hebben een natuurlijke het bestellen van hen. Welke werkwijze dat je eigenlijk gebruiken? Is het redelijk willekeurig net het plukken van de eerste die je ziet en zetten het op zijn plaats? Heeft u eerst beweeg je handen rond op zoek naar A en dan op zoek naar B? Heeft u een kijkje nemen op een te nemen paar ze naast elkaar en gewoon zeggen, wacht eens even, dit is niet goed, en dan wisselen de orde? We zagen al op maandag dat er een aantal manieren waar kunnen we dit doen, en inderdaad nu we hier eind, Ik zou het briefje misschien nemen van wat Mary Beth doet. We hebben een paar palen naar het schijnt, een grotere, drie kleinere. Publiek: Ik ga ze bestellen toen ik twee brieven dat ik weet dat ze samen in een reeks, Ik zet ze samen, zodat ik niet zorgen te maken over het houden van spoor van een hele rij van boeken. Het is gewoon, oh, A is de eerste, Ik heb deze stack kreeg hier. SPEAKER: Dus, bijna als een puzzel stukken die het recht vorm overeenkomen met elkaar. PUBLIEK: Vrij veel, ja. SPEAKER: OK, uitstekend. En nu elk van deze palen is vermoedelijk naargelang? Publiek: Ja. Spreker: Oke, A tot en met Z. Alle rechts, van harte gefeliciteerd, het is je gelukt. Je hebt je keuze. Blue? Oke, bedankt voor dat. Dus Mary Beth heeft voorgesteld wat haar benadering, maar wat is een andere benadering van hoe je zou kunnen gaan over het sorteren van deze dingen? Wat zou jij gedaan hebben? Het record te verslaan zou zijn geweest een minuut en 50 seconden of zo, plus degenen die ik vergat te tellen. Wat zou jij gedaan hebben? Yeah? PUBLIEK: Neem de stapel. Begin bij het begin. Controleer uw papieren. Als de bovenste hoger dan misschien zijn ze, onderste is hoger, dan schakelen ze. SPEAKER: OK, dus het starten boven en beneden, en dan werk je weg naar binnen als dat, ruilt ze? OK, dus een beetje vergelijkbaar in de geest naar bubble sort, maar het kiezen van de extremen niet aangrenzende paren. Maar de korte daarvan is dat er zeker een heleboel verschillende manieren We konden dit doen, en eerlijk gezegd, denk ik dat je soort nam een ​​paar benaderingen, toch? Je maakte een soort van vier gesorteerde stapels, en dan effectief samengevoegd ze samen. En dat is, durf te zeggen, een ander techniek helemaal. Je deed het niet behandelen als een grote stapel, u het probleem opgedeeld in vier quads, als je wil, en dan een of andere manier fuseerde ze op het einde. Dus laten we eens kijken, uiteindelijk, hoe anders we dit zouden kunnen doen. We geformaliseerd de notie van bubble sort vorige keer, en bubble sort recall was een algoritme dat we gevisualiseerd met acht van je klasgenoten hier, schijnbaar willekeurig naargelang op het eerste. En we hebben toen besloten paarsgewijs, indien twee elementen zijn niet in orde, eenvoudig te verwisselen. Zo vier en twee uiteraard buiten de orde, dus die twee klasgenoten geschakelde posities. En dan herhaald we met vier en zes, dan zes en acht, op elke iteratie, naar rechts beweegt. Dus gegeven acht mensen, hoeveel paarsgewijze vergelijkingen heb ik gedaan tijdens het lopen van links naar rechts in een dergelijke iteratie? Hoeveel vergelijkingen? Zeven, toch? Want als er acht mensen, maar je hebt het paar ze en je blijven bewegen een hop naar rechts, je bent niet van plan om zijn acht vergelijkingen, want je kunt niet vergelijken een element dat tegen zichzelf, of het zou gewoon zinloos, dus je hebt zeven. Of meer in het algemeen, indien we hebben n mensen, we doe n minus 1 vergelijkingen met bubble sort. Dus laten we eens kijken nu hoe goed of slechte bubble sort eigenlijk was, en probeer om ons vocabulaire te geven met die aan kritiek algoritmes als dit, en binnenkort ons eigen. Dus de eerste passage door bubble sort, de eerste keer Ik liep van links naar rechts over de podium, nam me n minus 1 vergelijkingen. En dat gaat zijn mijn maateenheid, toch? Ik was een beetje praten en wandelen, wat snel, wat traag, dus tellen mijn aantal seconden is niet bijzonder te vertellen, maar het tellen van het aantal operaties die ik deed op maandag, vergelijken van twee mensen, dat voelt als een aardige maateenheid. Zo n minus 1 stap het eerst maar wat er daarna gebeurde? Wat is het een kop van een pas door middel van een anders ongesorteerde lijst? Wat kun je me vertellen over het element die de hele weg daar was? Yeah? Dat was de grootste element, toch? Nummer acht, hoewel ze begon hier, elke keer als ik vergeleek haar tegen een buurman, hield ze borrelen rechts kant van de lijst. En inderdaad, dat is waar het algoritme zijn naam krijgt. Nu door die logica, hoeveel vergelijkingen moet ik op de tweede keer Ik maak die pass van links naar rechts? n minus 2, toch? Het zou gewoon mijn tijd verspillen als ik houden het vergelijken acht tegen iemand anders omdat we al weten Ze was op de juiste plaats. Dus dat is een beetje een optimalisatie, dus de volgende pas gaat worden plus n min twee stappen, waarbij n het aantal mensen. Nu kun je soort extrapoleren, zelfs als je niet een computer wetenschapper, hoe dit afloopt. Aan het einde van dit algoritme, vermoedelijk je hebt slechts een vergelijking gelaten. Je moet soort vaststellen van de begin van de lijst in het geval van twee en men is niet in orde en moet een en twee, dus deze bodems uit bij plus 1 laatste vergelijking. Nu is de dot, dot, dot soort golven is het handen op een aantal van de sappiger details maar laten we gewoon doorgaan en te vereenvoudigen. Misschien herinner je je van de hoge school, eerlijk gezegd, veel van jullie had wiskunde boeken die had een klein spiekbriefje op de voorkant of de back cover die je liet zien wat serie sommaties zoals dit uiteindelijk tot toegevoegd aan. In het algemene geval, als u een variabele als n, en inderdaad deze, als u gekeken naar uw oude school wiskunde boek, zou je zien dat dit ook daadwerkelijk voegt tot dit bedrag hier, n keer n minus 1 alles gedeeld door 2. Dus voor nu laat ik gewoon bepalen dit waar is, dus op een sprong van het geloof, dat is wat dit vat tot, en we konden bewijzen dat een meer algemeen geval. Maar laten we nu uitbreiden dit uit. Dus laten we dit vermenigvuldigen, dus dat is n kwadraat, minus n, alles gedeeld door 2. Dat is echt n kwadraat, gedeeld door 2, minus n meer dan 2, dus dat is allemaal leuk en interessant. Maar wat gebeurt er als we plug-in een waarde? Stel dat ik niet heb acht mensen, maar laten we zeggen een miljoen. En omdat miljoen het is een vrij groot aantal, laten we de stekker die in en zie wat er gebeurt. Dus als ik de stekker van een miljoen in die formule Ik ga je een miljoen in het kwadraat, gedeeld door 2, minus een miljoen, gedeeld door 2. Nu wat dat gaat evenaren? Dus 500 miljard, minus 500.000. En als ik het eigenlijk doen dat wiskunde uit, dat betekent dat het sorteren van een miljoen mensen met de bubble sort zou me 499999500000 stappen of vergelijkingen in het einde, we zijn gewoon extrapoleren. Dat voelt vrij traag, maar eerlijk gezegd het meten van een bepaalde ingang als dit, is niet zo veelzeggend. Maar inderdaad het geeft wel aan dat als n groter en groter, dit algoritme soort voelt erger en erger, of je echt beginnen om de pijn die aanvoelen machtsverheffen, dat n het kwadraat, die voegt behoorlijk snel. En dit detail is niet verloren op mensen, in feite enkele jaren geleden een zekere senator die was campagne, ging zitten voor een interview met Google's Eric Schmidt, CEO op het moment, en werd uitgedaagd met een vraag net als die we vandaag verkennen. Laten we eens een kijkje nemen. [VIDEO AFSPELEN] -Senator, Je bent hier bij Google, en ik hou van te denken van het voorzitterschap als een sollicitatiegesprek. Nu, het is moeilijk te krijgen een baan als voorzitter, en je gaat door de ontberingen nu. Het is ook moeilijk om een ​​baan te krijgen bij Google. Wij hebben vragen, en we vragen onze kandidaten vragen, en deze is van Larry Schwimmer. Wat-- jullie denken dat ik grapje, het is hier. Wat is de meest efficiënte manier om sorteren miljoen 32-bits gehele getallen? -Well-- Het spijt me, maybe-- Nee, nee, nee. Ik denk dat de bubble sort zou de verkeerde weg te gaan. Kom op, die hem dit verteld? Ik zag geen computer wetenschap in je achtergrond. -We Onze spionnen in. -OK, Laten we vragen een andere interview vraag. [END VIDEO AFSPELEN] SPEAKER: Dus het over specifieke nummers wel, zal niet alles nuttig zijn. Het is niet een levensles die zeepbel sorteren, aangezien een miljoen ingangen, kan net zo veel als 500 miljard stappen ondernemen. Je kunt niet echt generaliseren Ook effectief uit dat en maak een goede ontwerpbeslissingen bij het schrijven van programma's. Dus laten we focussen wel op hoe We kunnen dit resultaat vereenvoudigen. Dus ik heb geel gemarkeerd hier het resultaat van n kwadraat gedeeld door 2, dus een miljoen in het kwadraat gedeeld door 2, en Ik heb gewezen op wat het ultieme antwoord was als we eenmaal afgetrokken off n gedeeld door 2. En de bewering ga ik nu te maken is, wie de heck cares als je aftrekken af een beetje oud n meer dan 2 bij de eerste onderdeel van deze formule is zo veel groter? Het domineert de andere termijn n kwadraat gedeeld door 2 is zo veel groter, duidelijk, als n groot wordt als een miljoen, dat is er echt een groot verschil in het einde van de dag tussen 500 miljard en 499.999.500.000? Niet echt. En dus wat we gaan doen als informatici is negeer die lagere orde termen en neem iets als dit en echt gewoon vereenvoudigen het aan de termijn dat gaat uit. Hoe groter onze datasets te krijgen, hoe groter onze databases te krijgen, hoe meer webpagina's we moeten zoeken, hoe meer vrienden je hebt op Facebook. Als n groter wordt, zijn we echt gaat om de zorg over de grootste termijn dergelijke analyse onze algoritmes prestaties. En ik ga zeggen, weet je wat, bubble sort is in de orde van grote O, in de orde van n kwadraat. Het is niet precies n kwadraat zoals we hebben gezien, maar die echt cares over die kleinere termen, en eerlijk gezegd, die echt cares als we delen door 2? Dat is slechts een constante factor. En is 500 miljard versus 250 miljard echt zo groot van een deal? Ik kon gewoon wachten een jaar, laat mijn laptop letterlijk krijgen twee keer zo snel in hardware, en dat soort verschil gewoon verdwijnt vanzelf na verloop van tijd. Wat we de zorg over is de uitdrukking, het deel van de uitdrukking dat gaat variëren als onze inbreng groter en groter. En inderdaad, in de echte wereld, dat is wat er gebeurt in toenemende mate is de input voor onze problemen en algoritmen worden steeds groter. Zo groot O gaat naar de notatie te zijn, de asymptotische notatie, dat we gewoon gebruiken als informatici te beschrijven de prestaties, of de looptijd, van een algoritme. Zodat we algoritmen kunnen vergelijken op verschillende computers geschreven door verschillende mensen, met sommige fundamenteel vergelijkbaar metrische zoals het aantal vergelijkingen dat je maken, of misschien het aantal swaps je maakt. Wat we niet van plan om telling is de hoeveelheid tijd dat gaat op de klok op de muur typisch. Wat we gaan niet te maken over is hoeveel geheugen je gebruikt vandaag op Tenminste, al is dat andere bron we kunnen meten. We gaan proberen om onze analyses te baseren op alleen de basishandelingen, degenen, eerlijk gezegd, dat kunt u de meeste visueel te zien. Dus met iets als grote O van n kwadraat, ik beweer dat de O van n kwadraat is een bovengrens aan de zogenaamde looptijd van de bubble sort. Met andere woorden, als je wilde beweren dat er deze bovengrens op het aantal stappen van een algoritme zou kunnen nemen, het gaat om in de grote O van n kwadraat in dit geval een bovengrens. Wat als ik in plaats daarvan veranderen de verhaal te zijn niet over bubble sort, maar over deze bovengrens. Kunt u denken aan een algoritme dat we hebben gekeken naar al waarvan de bovengrens maximum meten van tijd of operaties, moet gezegd worden begrensd door n, een lineaire functie, niet een kwadratische een die gebogen? Wat is een algoritme dat vindt altijd niet meer dan als n stappen, of 2n stappen of 3n stappen? Yeah? Publiek: Het vinden van de grootste aantal in een lijst? SPEAKER: Perfect, het vinden van het grootste aantal in een lijst. Als ik een lijst met mensen bijvoorbeeld ieder die houdt van een aantal, wat is het maximum aantal van de maatregelen die hij me moet nemen, een redelijk slimme persoon, tot de grootste persoon in die lijst vinden? n, toch? Omdat in het ergste geval, wanneer kan de grootste waarde? Rechts, helemaal aan het einde. Dus in het ergste geval bovengrens, zou ik moeten de hele weg te gaan hier en zijn als, oh, hier is nummer acht, of wat die waarde is. Nu zou het gewoon dom als ik bleef gaan, toch? Op zoek naar meer en meer elementen als de laatste van hen is daar? Dus zeker n is een bovengrens. Ik hoef niet te nemen meer stappen dan die. Dus wat als ik in plaats daarvan dat de voorgestelde zijn er algoritmes in deze wereld die hebben een looptijd die is begrensd door grote O van log n, log n? Waar hebben we dit eerder gezien? Yeah? PUBLIEK: In het telefoonboek probleem? SPEAKER: Net als het telefoonboek probleem. Wat was de maat voor hoe veel tijd of hoeveel tranen er nam me mee naar iemand als vinden Mike Smith in het telefoonboek? We beweerden het was log n, en zelfs indien het onbekende of het een beetje vaag wat een logaritme of exponent was, alleen niet vergeten dat log n verwijst in het algemeen naar het proces, in dit geval, verdelen iets in de helft opnieuw, en opnieuw, en opnieuw en opnieuw, zodat het krijgt steeds klein als je dat doet. Dus log n verwijst, zeker, om het telefoonboek bijvoorbeeld, voor binaire zoekactie in theorie, als we had de virtuele deuren op het bord, of wanneer Sean op zoek naar iets. Als hij binary search had gebruikt, log n zou de bovengrens van de hoeveelheid te tijd die nodig is. Maar die algoritmen die liep in log n veronderstelde wat belangrijke details? Dat de lijst gesorteerd was, toch? Algoritme is verkeerd als Uw inbreng wordt niet gesorteerd, en toch je gebruikt iets binary search want je zou kunnen springen rechts over het element zonder het te beseffen het is er inderdaad. Nu, wat kan dit betekenen, grote O van een? Dit betekent niet dat je algoritme draait een en slechts een stap Het betekent alleen maar dat het duurt een constant aantal stappen. Misschien is het 1, misschien is het 10, misschien is het 1000, maar het is onafhankelijk van de omvang van het probleem. Het maakt niet uit hoe groot n is, een constante tijd algoritme neemt altijd hetzelfde aantal stappen. Dus wat kan een algoritme We hebben gesproken over of gewoon intuïtief dat naar je toe komt, dat loopt altijd in zogenaamde constante tijd? Yeah? PUBLIEK: Voeg twee getallen. SPEAKER: Voeg twee getallen, 2 plus 2 is gelijk aan 4, gedaan. Dus dat zou kunnen werken, wat anders? Wat dacht je van meer echte wereld, ja? Publiek: Het vinden van de het eerste wat in een lijst. SPEAKER: Het vinden van de eerste element in een lijst, zeker. We hebben eigenlijk gesproken over arrays al, hoe krijg je bij de eerste element in een array, het maakt niet uit hoe lang de array in C code? Je gebruikt net als de beugel nul notatie, bam, je bent er. En inderdaad arrays, als een terzijde, support iets algemeen bekend als random access, random access geheugen, want je kunt letterlijk springen naar een bepaalde plaats. We kunnen gewoon dit nog meer te doen we kunnen terugspoelen tot week nul toen we Scratch. Hoeveel tijd heeft het geduurd voor de zeggen blok in Scratch uit te voeren? Net constante tijd, toch? Zeg iets, zeggen iets, maakt niet uit hoe groot Krassen wereld is, is het altijd naar dezelfde hoeveelheid tijd om gewoon iets te zeggen. Dus dat is een constante tijd, maar wat is de keerzijde? Als dat was hoger grenzen, wat als we willen de ondergrenzen beschrijven van onze algoritmen looptijd? Bijna een best case potentieel, als je wil, hoewel deze termen zou kunnen gelden voor beste gevallen, ergste gevallen, gemiddeld gevallen meer over het algemeen, maar laten we gewoon focussen op ondergrenzen meer in het algemeen. Wat is een algoritme dat is een ondergrens van n trappen, of 2n stappen of 3n stappen? Sommige factor n trappen, dat is de ondergrens. Yeah? PUBLIEK: Bubble soort? SPEAKER: Bubble sort neemt je minimaal n stappen, waarom? Waarom is dat? Waarom zou dat het begin tot het naar je toe komen intuïtief, zelfs als het niet alleen nog? Yeah? PUBLIEK: [onverstaanbaar]. SPEAKER: Precies. In de best mogelijke scenario van bubble sort, en een heleboel algoritmen, als ik geef je acht mensen die al zijn gesorteerd, Het zou dwaas zijn voor u, het algoritme, om heen en weer te gaan meer dan een keer, toch? Want zodra je loop door de lijst een keer, U dient zich te realiseren, oh, heb ik geen swaps, wordt deze lijst gesorteerd exit. Maar dat gaat je n stappen te ondernemen. En omgekeerd, wat is een andere manier van denken over het? Bubble sort is een omega, zo te zeggen, van n, want als je kijkt naar minder dan n elementen, welke is het fundamentele probleem daar? Je weet niet of het is gesorteerd rechts. Wij mensen macht blik op acht mensen en zijn als, oh, is het opgelost, dat heeft me n stappen niet te nemen, maar het deed. Je ogen, ook al heb je soort van een groot gezichtsveld, je keek naar acht elementen, je keek naar acht mensen, dat is acht stappen effectief. En alleen als ik door een hele lijst besef ik, ja, gesorteerd. Als ik halverwege stoppen denken, alle recht, het is mooi zo ver gesorteerd wat zijn de kansen dat het niet gesorteerd? Dat algoritmes niet van plan juist te zijn. Misschien sneller, maar onjuist. Dus nu hebben we een manier van het beschrijven van een ondergrenzen, en hoe zit het met constante tijd? Wat is een algoritme dat een lager is gebonden aan de looptijd van een? 1 stap, 2 stappen, 10 stappen, maar constant, onafhankelijk van n, de grootte van de input? Ja, in de rug. PUBLIEK: Printf? SPEAKER: Wat is dat? PUBLIEK: Printf? SPEAKER: Printf. OK, zeker. Zo draait vast aantal stappen. En ik zou nu dat nu-- we hebben het over de C-code en niet Scratch, iets zoals bijvoorbeeld met printf, we moeten beginnen om voorzichtig te krijgen. Omdat printf neemt ingang, het is een string, en snaren technisch hebben lengte. Dus als we nu willen halen op je, als je het niet erg vindt, technisch gezien konden we dat printf argumenteren ofwel een variabele lengte invoer vragen, en toch kan het langer duren tijd om een ​​string zo lang af te drukken, dan deze lang. Dus wat als we kijken naar alleen de het sorteren en zoeken voorbeelden? Hoe zit het met Mike Smith in de telefoon boek, of binaire zoeken meer in het algemeen? In het beste geval, wat er kan gebeuren? Ik het telefoonboek te openen en, bam, er is nummer Mike Smith. Ik kan hem meteen bellen. Deed een stap, misschien twee stappen, maar een constant aantal stappen als ik heb geluk gehad. En eerlijk gezegd, we zagen op Maandag jouw klasgenoot behoorlijk geluk twee keer op een rij. En dat was inderdaad constant tijd in een ondergrenzen aan het algoritme voor het vinden betrokken het nummer 50 achter die gesloten deuren. Nu, als een terzijde, als je ontdekt dat zowel grote O, de bovengrens en omega, de ondergrens, zijn een en hetzelfde, dat is dezelfde formule haakjes, kunt u ook zeggen, gewoon om te fancy, dat iets in theta van n of theta van een andere waarde. Dat betekent dat alleen wanneer grote O en omega zijn hetzelfde. Nu wat over selectie soort? Laten we gebruik maken van deze nieuwe woordenschat. In de selectie sorteren, wat waren we opnieuw doen, en opnieuw, en opnieuw? Ik werd heen en weer gaan door de lijst, op zoek naar wie? Het kleinste getal. Dus hoeveel stappen, hoe veel vergelijkingen heb ik moeten maken om erachter te komen wie het kleinste element in de lijst stond? n minus 1, toch? Want als ik gewoon beginnen met degene die ik ben gegeven en ik begin hem of haar te vergelijken, dan hem of haar, hem of haar, hem of haar, ik kan alleen elementen te koppelen samen n minus 1 keer. Dus selectie neemt soort op dezelfde manier n minus 1 stappen de eerste keer. Hoeveel stappen duurt het me te vind het op een na kleinste element? n minus 2, want ik ben dom Als ik blijf kijken naar dezelfde mensen weer als ik heb hem reeds geselecteerd of haar en zet ze op hun plaats. En de derde stap, n minus 3, dan is n minus 4. We hebben dit patroon gezien vóór en zelfs selectie sorteren op dezelfde manier heeft een bovengrens van n kwadraat als we dat doen tot dat sommatie. Wat is de ondergrens, selectie sorteren? Minimaal, hoeveel tijd moet selectie soort nemen, zoals we het gedefinieerd op maandag? Stellen twee opties. Misschien is het n, zoals voorheen. Misschien is het n kwadraat, zoals het is nu als de bovengrens. PUBLIEK: n kwadraat. Spreker: n kwadraat. Waarom? PUBLIEK: Omdat je om [onverstaanbaar] definiëren. SPEAKER: Precies. Tenminste als ik selectie soort gedefinieerd het was behoorlijk naïef, blijven gaan, voorbeeld de kleinste element. Ga weer, vind het kleinste element. Ga weer, vind het kleinste element. Er is geen soort van optimalisatie in dat er misschien laat me af te breken na gewoon n of zo stappen. Dus inderdaad selectie soort, omega van n kwadraat. Hoe zit het insertion sort, waar ik nam die ik kreeg, en vervolgens hem plofte ik of haar op de juiste plaats? Daarna ging ik naar de tweede persoon, plofte hem of haar op de juiste plek. Dan is de volgende persoon, plofte hem of haar op de juiste plek. Merk op dat dit zeer lineaire, zo te zeggen. Ik ben een rechte lijn, ik ben niet heen en weer gaan, Ik heb nooit terug te kijken echt, maar wat er gebeurt als ik hem in te voegen of haar in het begin van de lijst zoals wij deden op maandag? Wat gebeurt er? Yeah? PUBLIEK: [onverstaanbaar]. Spreker: Ja, dat was de vangst, toch? U herinnert zich nog wel uit je klasgenoten, indien zij maakten elke beweging met hun voeten, dat is een operatie. Dus als er drie mensen hier en de nieuwe persoon behoorde daar weg over, op een lange etappe als deze, zeker, hij of ze kon gewoon naar het einde. Maar als we denken over een computer en een reeks geheugencellen, deze mensen gaan moeten dan schudden om ruimte voor die persoon te maken. En zo dat n minus 1 uitvluchten, n minus 2 uitvluchten, n min 3 uitvluchten is gewoon een soort van er achter mij, niet voor mij zoals eerder, in zekere zin. Nu nog even terzijde, en als je zou online hebt gezien als je begint rondneuzen over soorten, er zijn zoveel verschillende degenen die er zijn, een aantal van hen beter dan anderen. Inderdaad, bogosort is een dat is wel leuk om te kijken. Bogosort neemt een set van nummers of zeggen een spel kaarten, willekeurig schudt hen, en controleert of ze gesorteerd worden. En zo niet, doet het weer. En zo niet, doet het weer. Zo niet, dan doet het weer. Ongelooflijk dom. En inderdaad, als je leest zoals het artikel van Wikipedia, zijn bijnaam is dom soort. Het zal uiteindelijk werken, hopelijk genoeg tijd, maar die tijd kan geruime tijd in beslag nemen. Dus als ik zou kunnen, laten we snel dingen up van Mary Beth's bijvoorbeeld eerder, Door een paar elementen, maar twee processors. Twee mensen, als je zou het niet erg mee me. Wat dacht je van 1 hier, en laten we gaan-- niemand daar? Niemand daar? OK. U met de zwarte shirt, ja, kom naar beneden. Oke, wat is uw naam? PUBLIEK: Peter. SPEAKER: Wat is dat? PUBLIEK: Peter. Spreker: Peter, David, leuk je te ontmoeten. Oke, we hebben Peter hier, als je wil op de tafel te komen hier. En wat is uw naam? PUBLIEK: Elena. SPEAKER: Elena. OK, leuk je te ontmoeten. Elena ontmoet Peter. Peter, Elena. En we zullen Andrew nodig hier ook, alstublieft. En uw uitdaging gaat te zijn om een ​​spel kaarten afstand. En als onbekende, dek kaarten moet uiteindelijk gesorteerd worden een beetje iets als dit waar we de clubs doen, dan het schoppen, dan de harten en diamanten, van aas als een een, helemaal tot aan de koning. De kaarten die ik je ga geven gaan worden 52 in kwantiteit. We gaan op dezelfde manier keer dat u, in slechts een moment. We gaan Andrew gooien up hier het scherm, om zo naar te kijken als je dit doet. En zodat alles is des te zichtbaarder Dit zijn de kaarten die ik kreeg op Amazon. Dus ze zijn al willekeurig gesorteerd zijn, en we zullen u tijd. En we gaan houd het echt deze keer, dus we gaan proberen om je onder druk te zetten omdat anders deze vervelende krijgt snel. Als je zou kunnen gaan om te sorteren 52 elementen aan elkaar gekoppeld via een middel, nu. En nogmaals, als we kijken naar deze jongens doen wat, in het einde gaat om een ​​voor de hand liggende te produceren resultaat, na te denken over echt hoe ze elkaar doen, hoe zou je het kunnen omschrijven. Omdat weer, deze alle processen, algoritmen die we voor lief nemen als mens. Maar je hebt waarschijnlijk al lang gehad intuïtie, al voordat u de nagedacht over het nemen van een computer science class u zou de intuïtie hebben gehad met die om dit soort problemen op te lossen. Maar als je eenmaal herkent de patronen en beginnen de stappen waarmee formaliseren u het oplossen van deze problemen, je zult zien dat je veel kunt oplossen interessanter en veel complexer problemen snel. Dus iemand uit het publiek, wat is tenminste een element van het algoritme dat ze hier gebruik van? PUBLIEK: [onverstaanbaar] SPEAKER: Wat is dat? Publiek: Door pak. Spreker: Door pak. Dus eerst zijn ze te clusteren alle diamanten samen Het lijkt alle harten samen zo lijkt het, enzovoort, zonder respect de enkele speelkaarten. En nu lijken ze, bijvoorbeeld, worden ze te sorteren op nummer. Zeer goed. Oke, dus wat er gaat zijn de laatste stap dan hier? Zodra we hebben vier gesorteerde pakken, wat doen wat we moeten doen om de vier palen teneinde een verwezenlijken naargelang dek, heel eenvoudig? Dus moeten we ze weer samen te voegen. Dus er is een interessant idee dat weer, durf te zeggen, is zeer intuïtief, zelfs als je nooit zou hebben geslagen dat soort label op. Deze fundamentele notie van te delen het probleem niet in de helft deze tijd, maar in ieder geval in vier stukken. Het oplossen van vrijwel fundamenteel identieke problemen los van elkaar, en dan is het samenvoegen van de resultaten. En, uitstekend, gedaan. Oke, een grote ronde applaus, als we konden. [Applaus] SPEAKER: Ik heb geen idee wat je zult doen met deze, maar hier ga je. Dank je wel. Dus laten we eens kijken, twee minuten en acht seconden, Indien u graag uw vrienden uit te dagen. Wat daarna gaat zijn een neem afstand van deze dat we meer in het algemeen kunnen benutten? Nou, denk terug aan Deze matrix van getallen, en denk nu terug naar een aantal van de pseudocode we in het verleden heb geschreven, en dit was de pseudocode voor het oplossen van het telefoonboek probleem. Waarbij in pseudocode I opgesomd een meer methodische manier beschrijven hoe ik het deed een zeer intuïtieve menselijke algoritme van de telefoon verdelen boek in de helft, herhalen, herhalen, herhalen, totdat ik vind iemand als Mike Smith, Als hij inderdaad in het telefoonboek. Maar ik soort gebruikt wat ik zal noemen een zeer iteratieve aanpak hier, met name indicatieregel 8 en regel 11. Die zijn het bewijs van een iteratief aanpak, een looping aanpak, want dat is precies het gedrag dat ze veroorzaken. Die lijnen beide zeggen ga naar lijn drie, en je kan soort denk aan die in uw geestesoog als een lus. Het vertelt je om terug te gaan tot stap drie en herhalen, opnieuw, en opnieuw, en weer. Maar wat als we benutten een belangrijke idee hier dat we niet de laatste keer, en vereenvoudiging van lijn 8 en lijn 11 en hun buren als alleen deze, in geel. Het is niet fundamenteel verkorten de pseudocode heel veel, maar het is fundamenteel veranderen de aard van mijn algoritme. Wat ik nu zeg in stap 7, in stap 10, is om te zoeken naar Mike op dezelfde manier, maar gewoon in de linker helft of de rechter helft. Dus in andere woorden, als Ik begin bij stap een, pick-up telefoonboek open voor midden van telefoonboek, kijk naar de namen, Als Smith is onder naam, bel Mike, anders Als Smith eerder in het boek is, stap zeven zoeken naar Mike in de linker helft van het boek. Maar dat soort voelt als het is laat me opknoping, toch? In geel, een instructie, maar hoe doe ik zoek Mike in de linker de helft van het telefoonboek? Waar heb ik een algoritme waarmee ik kunnen zoeken naar iemand als Mike Smith? Nou, het staren ons in het gezicht. Ik kan letterlijk exact dezelfde gebruiken programma effectief te gaan naar de top opnieuw en opnieuw te lopen dezelfde regels code. Dus hoewel dit moet voelen als een beetje een cyclische definitie waar je het beantwoorden van iemand is vraag door gewoon soort van vragen dezelfde vraag weer, zoals waarom, waarom, waarom? De realiteit is dat we moeilijk hebben gecodeerd een paar van de speciale lijnen, stap 4, die een als en stap 12, waarin is in feite een andere tak, want we hebben deze noodmaatregelen, Dit algoritme zal worden beëindigd als we vindt Mike, of als we dat niet doen. Maar in stap 7 en 10 nu, we hebben wat we een recursieve algoritme zullen noemen. En recursie is inderdaad een krachtig idee dat is een beetje geest buigen op het eerste, dat kunnen we nu als volgt toe. Merge soort is de laatste soort zijn dat we kijken, althans in klasse formeel. En het is fundamenteel verschillend van die laatste drie, en zeker laatste vier als we onder bogosort. Hier is de pseudocode voor merge sort. Wanneer op de ingang van n elementen, dus gegeven een array van grootte n, indien n kleiner is dan 2, terugkeren. Dus waarom moet ik dat sanity check eerst? Wat is de implicatie of ik geef je een array waarvan de lengte n minder dan 2? Het is al naargelang, natuurlijk, toch? Omdat de lijst heeft ofwel een element, dat is triviaal naargelang omdat het het enige wat er. Of, het is van size zero wat betekent er is niets om te sorteren, dus door de natuur wordt gesorteerd. Er is gewoon niets aan de hand daar. Dus dat is onze zogenaamde basisscenario. Dat is in dezelfde geest met wat we hebben gedaan met Mike. Als Mike's in het telefoonboek, bel hem. Als hij er niet is, op te geven. Het is een zogenaamde base case, ervoor zorgen Dit algoritme aan het eind van de dag stopt in bepaalde omstandigheden. Maar hier is de sprong van het geloof nu, anders, sorteren de linkerhelft van de elementen, Vervolgens sorteert de juiste helft van de elementen, en dan fuseren de gesorteerde helften. En hier is waar het voelt alsof we betrappen uit. Ik heb je gevraagd om te sorteren n elementen, en ik ben zeggen, OK, doe het door het sorteren de links en het sorteren van de juiste. Maar ik zeg een ander ding, en dit is het centrale thema lijkt in de intuïtie tot nu toe, er is deze derde stap van het samenvoegen. Welke ook al lijkt zo dom in de geest, als enkel dingen samenvoegen vormen, ligt het een belangrijke stap in de richting van de te montage van twee problemen die werden uiteindelijk in tweeën gedeeld. Dus samenvoegen soort, laten we dit doen, als U humor me, met nog een demonstratie, gewoon zo dat we een aantal nummers om mee te werken. Kan ik wisselen acht spanning ballen voor acht personen? Oke, wat dacht je van drie, je vier in deze sectie, vijf, zes, en laten we do 7, 8, kom op. OK, ja OK. Minus 8, daar gaan we, plus 1. Excellent. Oke kom op, laten we snel geef je nummers. Nummer twee, nummer drie, nummer vier, nummer vijf, zes, zeven en acht. Ik heb acht juist dit keer. OK, dus ga je gang als je kon, en laten we afstand in de oorspronkelijke volgorde dat we gisteren hadden die keek als dit, als je het niet erg. En we doen het in de voorkant van de tafel. Oke, dus samenvoegen soort. Dit is waar het gaat om vorm te krijgen van interessante, omdat ik lijken te geven van mezelf dus veel minder informatie vandaag. Dus samenvoegen soort allereerst de input van de n elementen, en is duidelijk niet minder dan twee, is het acht, dus ik heb nog wat werk te doen. Dus nu mentaal wij als klas zijn nu in de andere tak, wat betekent drie stappen. Allereerst, ik moet de afstand linkerhelft van de elementen. Dus hoe ga ik dat doen? Nou, ik ga soort hier mentaal verdelen de lijst, je hoeft niet te fysiek te verplaatsen, en ik ben zal zich op de linkerhelft van de elementen hier. Dus hoe ga ik over het sorteren nu van grootte vier een lijst? Wat is mijn algoritme? Eerst heb ik controleren is n minder dan twee, nee, dus ik ga naar de else blok weer. Sorteer linkerhelft van elementen. Dus nu opnieuw, mentaal, en dit is waar je moet heel veel ten goede mentale geschiedenis, als je wil. Nu ben ik het sorteren van de linker helft van de linkerhelft. Oke, dus nu noem ik mijn dezelfde merge sorteer-algoritme, is n minder dan twee? Nee, het is twee, dus ik heb om te sorteren de linker helft en de rechter helft. Dus hier gaan we, sorteert de linker helft. Waarom doe je niet zomaar een stap vooruit. Wat is je naam? PUBLIEK: Darren. SPEAKER: Dan. Dan is naar voren stapte. PUBLIEK: Darren. SPEAKER: Darren, gedaan. Wist u Darren of Dan zeggen? PUBLIEK: Darren. SPEAKER: Darren. OK, Darren is gestapt naar voren en hij wordt nu gesorteerd worden. En dit is bijna een zinloze claim, toch? Ik heb niet echt lijken te bereiken wat dan ook, maar laten we gaan. Laat me nu afstand van de juiste helft van de elementen. Wat is je naam? PUBLIEK: Luke. SPEAKER: Luke. Kom op, stap naar voren. Gedaan, heb ik Luke gesorteerd worden. De linkerhelft is nu gesorteerd en de rechterhelft is nu gesorteerd, maar nogmaals, er is een belangrijke stap hier. Wat heb ik naast moet doen? Merge de gesorteerde helften. Nu gaan we gewoon iedereen heen en weer op deze manier omdat ik soort nodig wat scratch space. Het is bijna alsof deze jongens zijn op een tafel, en ik heb wat ruimte om hen te bewegen op. Dus ik ga om te fuseren jullie door te kijken op de linker helft en de rechter helft. En die uiteraard het eerst komt, linkerhelft of de rechterhelft? Dus rechter helft, dus laten we verder gaan Luke boven hier in de oorspronkelijke stand Darren's. En nu aan hun linker helft fuseren, Darren gaat om daar te verplaatsen. Dus voelt bijna een zeepbel soort effect, maar mijn fundamentele algoritme, heel deze keer. Maar nu is waar de dingen een beetje vervelend, omdat je moeten mentaal terugspoelen waar heb ik ophouden. Ik heb net gefuseerd de gesorteerde helften, wat betekent dat ik ben waar in mijn algoritme? Ik moet de rechter helft te sorteren, toch? Als u terugspoelen, letterlijk op de video, dan heb je zien dat we op deze punt van Luke en Darren door het sorteren van de linker helft van de linkerhelft. Dan samengevoegd wij die gesorteerde helften, die : de volgende stap is het sorteren rechterhelft van de linkerhelft. Oke, dus laten we Dit doen sneller. Oke, zes, ik ga claimen U bent nu naargelang, kom op naar voren. Wat is je naam? PUBLIEK: Adriano. SPEAKER: Adriano. Adriano wordt nu gesorteerd worden. En wat is uw naam? PUBLIEK: Alex. Spreker: Alex is nu gesorteerd worden. Linkerhelft, rechterhelft, wat is de laatste stap? Samenvoegen. Vrij triviaal, dus ik ben gaan samenvoegen in zes, neem een ​​stap terug, acht, een stap terug. En let nu op dit een handig mee te nemen, wat is nu juist over de linker helft van de lijst, ongeacht hoe we begonnen? Het wordt gesorteerd. Nu is het niet gesorteerd in de grote regeling van dingen, maar wordt onafhankelijk gesorteerd van de andere helft. Nu, wat stap ben ik op als ik houden terugspoelen hoe het verhaal begon? Nu moet ik naar de rechter helft afstand. Dus nu zijn we helemaal terug bij het begin van het verhaal, en laten we dit sneller te doen. Dus ik ga naar de afstand rechterhelft van de hele lijst. Wat is de volgende stap? Sorteer de linker helft van de rechter helft. Sorteer de linker helft van de linkerhelft van de rechterhelft. En wat is uw naam? PUBLIEK: Omar. SPEAKER: Omar, stap voorwaarts, gedaan. Linkerhelft wordt gesorteerd. En wat is uw naam? PUBLIEK: Chris. Spreker: Chris, een stap vooruit, u bent nu gesorteerd worden. Wat is de belangrijkste stap nu? Samenvoegen. Dus men gaat samenvoegen in plaats hier, als je een stap terug zou kunnen nemen, en drie gaat neem een ​​stap terug, samen te voegen. Dus de linkerhelft van de rechterhelft, wordt nu gesorteerd worden. Eerlijk gezegd, dit algoritme voelt alsof we verspilt veel meer tijd dan voorheen, maar als we dit in real-time, zullen we zien wat de afhaalrestaurants gaat worden. Nu ben ik hier, rechts helft van de rechterhelft, laat me ga je gang en sorteren van de linker helft. Stap naar voren, wat is uw naam? PUBLIEK: Ramsey. SPEAKER: Ramsey wordt nu gesorteerd worden. Wat is je naam? PUBLIEK: Marina. SPEAKER: Marina is nu naargelang als Nou, als je een stap voorwaarts te zetten. Belangrijke stap hier nu samen te voegen, ben ik gaan plukken van mijn twee lijsten, links en rechts. Vijf gaat wie het eerst komt, en zeven gaat naar de volgende te komen. En nogmaals, dit is een bewuste keuze. Het feit dat ze nemen stappen vooruit en achteruit is bedoeld om te vertegenwoordigen dat we kunnen niet doen dit algoritme in plaats zo gemakkelijk als bubble sort, en selectie sorteren en insertion sort waar we net gehouden swapping mensen. Ik heb letterlijk een soort nodig van kladpapier waarin om deze mensen zetten terwijl ik de samenvoeging, en dan kan ik ze terug te plaatsen. En dat is belangrijk, want ik ben met behulp van een nieuwe bron, ruimte, niet alleen de tijd. OK, dit is geweldig. Linkerhelft wordt gesorteerd, rechter helft is gesorteerde, nu die sleutel samenvoegen stap. Hoe ga ik deze samenvoegen? Dus als je volg mijn linker en rechter, Ik ga mijn linkerhand wijzen op de linker helft, mijn rechterhand op de rechter helft, en nu moet ik beslissen stap voor stap wie te fuseren. Die uiteraard op de eerste plaats? Nummer een. Dus kom eens hier, hier is onze kladblok. Dus nu nummer een, en de mededeling wat ik ga doen met mijn rechterhand, Ik ga mijn rechterhand een bewegen stap over naar nummer drie wijzen, en nu heb ik te maken dezelfde beslissing. En eigenlijk sta recht in voorkant van Luke hier als u kon, want dit is onze kladblok. Dus wie komt er nu? We hebben Lucas met nummer twee of Chris met nummer drie. Uiteraard Luke, nummer twee, dus kom je hier. Maar mijn linkerhand nu gaat worden opgehoogd om te wijzen op Darren, en hier is de sleutel af te halen bij samenvoegen, ga ik blijven doen, Uiteraard, als je kind van de logica volgen. Maar mijn handen zijn nooit zal achteruitgaan, wat betekent dat ik altijd alleen maar verhuizen naar links mijn fusieproces, en dat gaat de sleutel tot zijn onze analyse in slechts een moment. Dus laten we nu snel afmaken up. Dus drie komt daarna, dan vier komt daarna, en nu vijf daarna komt, dan zes, en zeven, en dan uiteindelijk acht. Voelt als de langzaamste algoritme nog, maar niet als we eigenlijk voer het uit op hetzelfde soort van kloksnelheid, zo te spreken met dezelfde tikkende klok als voorheen. Waarom? Nou, laten we eens een kijken naar het eindresultaat. Laten we teruggaan naar hier, laat mij trek een demonstratie visueel van wat we net gedaan. Inzoomen hier, op deze pagina hier, vertellen Firefox dat willen we in de rij in dit vak, laten we zeggen bubble sort, waarmee we zijn nu goed bekend, selectie sorteren, wat een andere vrij eenvoudig is, en nu de huidige merge sort, die zal onze climax einde zijn. De reden dat het zo veel langer hier met mensen en mij mondeling is, uiteraard ben ik het uitleggen elke stap. Maar als je gewoon voer je dit, veel zoals we deden bubble sort en selectie soort niet alleen visueel, horloge hoe veel efficiënter Deze hefboomwerking van divisie en het veroveren kan worden wanneer toegepast op een dataset dat zelfs niet de grootte van acht, maar ook veel, veel groter. Ik geef je een soort samenvoegen, naast zijde met deze andere algoritmen. Dit gaat pijn krijgen snel, en het einde is niet bijzonder climax, ze alleen maar uiteindelijk gesorteerd worden. Maar de sleutel weg te nemen, is dat kijken hoeveel sneller soort fuseren was, tenzij je denkt dat ik ben gewoon een soort van knoeien met je. Als we dit nog een laatste keer, laat het verversen, laten we terug gaan en kies bubble sort, en gewoon voor de kick, Laten we kiezen voor het inbrengen soort, gewoon voor een goede maatregel. En deze keer weer, laten we kiezen merge sort en laten we daadwerkelijk gereden deze naast elkaar. En het is niet, in feite, een toevalstreffer. Wat ik heb gedaan is effectief Ik heb onderverdeeld mijn inbreng in half, weer, en opnieuw, en opnieuw. En er is maar een beperkt aantal keren dat u kunt verdeel uw inbreng in twee helften, links en rechts. Wat is de formule die we blijven zien dat beschrijft de verdeeldheid in de helft opnieuw, en opnieuw, en opnieuw, en opnieuw? PUBLIEK: Log n. SPEAKER: Log n. Maar dan is er nog een andere belangrijke stap, Dit algoritme is niet log n stappen. Als het alleen werden log n stappen, we hetzelfde probleem zou als voorheen, waar we niet kunnen ervoor dat alles is opgelost. Je moet minimaal kijken n elementen om zeker n elementen worden gesorteerd, anders is het een sprong in het diepe. Dus het is minimaal log n stappen, maar hoe zit het met deze toets samenvoegen stap waar ik samengevoegd mijn linker helft en rechts helft en liep over het podium? Hoeveel stappen is dat om te fuseren? Het is n, maar ik deed het niet alleen samenvoegen van de laatste tijd. Op elk van deze geneste gesprekken op elke van die geneste samenvoegingen, ik nog gesorteerd worden. Ik fuseerde deze twee jongens, dan zijn deze twee jongens, dan zijn deze twee jongens, enzovoort. Dus ik heb het samenvoegen opnieuw, en opnieuw. Hoe vaak? Dus elke keer als ik verdeelde de lijst in de helft, heb ik een merge. Verdeel de lijst in de helft, doe een merge. Als delen van de lijst kunnen log n keer worden gedaan, en de samenvoeging neemt uiteindelijk n stappen, wat zou nu het bovenste gebonden aan de lopende tijd van ons algoritme? n log n. En inderdaad, dat is wat we hier hebben bereikt. Dus het gevoel dat je ziet visueel als die drie dingen naast elkaar lopen is n kwadraat tegen n kwadraat tegen n log n. Die fundamenteel we zullen zien, niet alleen vandaag maar in de toekomst is veel, veel sneller. Een applaus voor deze jongens, Ik zal hen belonen met stress ballen. Laten we verdagen hier vandaag, en Wij zullen u op maandag.