[Muziek] DAVID J. Malan: Oke. Dus welkom terug. Dit is CS50, en het is het einde van de week drie. Dus herinneren in de afgelopen weken, we zijn uitgaven nogal een beetje tijd op C, op de programmering, op syntax. En het is heel normaal, als je nog bent worstelen met Probleemverzameling 2, te zijn bonken met je hoofd tegen de muur. Het is cryptisch ogende foutmeldingen en bugs die je kan niet helemaal achterna te zitten. Want, er zeker van zijn, dat in slechts een tijd enkele weken zult u terugkijken op dingen zoals Caesar, en [? V-Genair,?] misschien zelfs Crack, en beseffen hoe ver je bent gekomen in een korte tijd. Dus als dat een troost, hangen daar voor nu. Vandaag, echter, beginnen we aan de overgang om dingen hoger niveau. En we beginnen om voor lief nemen dat jullie weten hoe te programmeren, of op minste het begin van dat comfort niveau. En we beginnen na te gaan hoe we kunnen gaan over het ontwerpen van programma's meer effectief. Hoe we kunnen gaan over het optimaliseren van de efficiency van algoritmes, en over het algemeen het oplossen van meer interessante problemen. En beginnen om voor lief nemen dat, als we wilden, konden we coderen up van alle van de voorbeelden die we in gedachten hebben. Dus vandaag hebben we niet het toetsenbord aanraken voor enige vorm van code. Het zal veel hoger niveau, en uiteindelijk, over het oplossen van problemen. Dus om naar dat punt, laat me voorstellen de volgende zeven rechthoeken geven zeven deuren, achter die een hele hoop van zijn getallen, waaronder het getal 50. Laat mij projecteren dit op deze scherm hier ook. En stel dat we een vrijwilliger om helpen bij het vinden me een aantal voor het internet hier te zien. Kom maar naar boven, in de roze. Oke. Wat is je naam? JENNIFER: [onverstaanbaar] DAVID J. Malan: Sorry? JENNIFER: Jennifer. DAVID J. Malan: Jennifer. Oke, Jennifer. Leuk u te ontmoeten. Kom maar naar boven. Dus deze hier zijn zeven deuren, en wat Ik wil graag dat je hier voor ons doen, voor al je klasgenoten, is het vinden van ons het nummer, 50. Om een ​​nummer te vinden, kunt u kijkje achter een van deze deuren door simpelweg te tikken op een van de deuren, en wordt het nummer onthullen. En laten we zien hoe snel je kunt ons vinden het nummer, 50. 15. 16. 50. Mooi gedaan. Oke. Applaus voor Jennifer. [Applaus] Oke. Dus wat was uw strategie voor het vinden van het nummer, 50? JENNIFER: Um, ik dacht misschien als - [Onverstaanbaar] DAVID J. Malan: Oh. Geef het een seconde. Dus was uw strategie voor het vinden van het nummer, 50? JENNIFER: Dus ik beginnen bij de beginnen te zien wat het eerste nummer was, en toen dacht ik, misschien als ze gesorteerd, zal ik gewoon blijven hogere tikken up? DAVID J. Malan: OK. En we lijken te hebben gevonden dat voor het geval. Hoewel, laten we afpellen van de lagen gewoon een beetje, en je wilt gaan vooruit en onthullen de andere deuren je had kunnen kiezen? JENNIFER: Oh, dear. DAVID J. Malan: Ah. JENNIFER: Dus ik heb gewoon geluk gehad. DAVID J. Malan: Dus je hebt geluk. Oke. Dus niet slecht. Maar dat is een interessante inzicht, toch? Als je aangenomen, en je kreeg, inderdaad, een beetje geluk daar. Maar als je aangenomen dat de aantallen waren gesorteerd, kunt u preciezer hoe die beïnvloed je gedrag? JENNIFER: Dus als ze gesorteerd waren, ik dacht misschien klein naar groot. DAVID J. Malan: OK. JENNIFER: Of als deze eindigde als echt groot, dan is groot naar klein. DAVID J. Malan: OK. Zo groot naar klein, of kleinste tot de grootste. Maar laat me stellen, stel dat je had gekregen pech, en veronderstellen dat zij niet, in feite, gesorteerd, hoeveel die deuren zou je hebt gehad te gluren achter in dat ergste geval? JENNIFER: Allemaal. DAVID J. Malan: Allemaal. Dus laten we generaliseren dat als n. Er gebeurt te zijn 7, maar laten we meer over het algemeen zeggen dat er is n deuren op de scherm hier. Dus in het ergste geval, zou je moeten om een ​​kijkje achter 7 deuren, of n deuren. En dus dit is echt, het is een beetje geluk vandaag, maar het is echt een lineaire algoritme van soorten, ook al heb je waren soort overslaan rond. Is dat eerlijk? JENNIFER: Yeah. DAVID J. MALAN: Nou, laat me zien of uw strategie verandert als ik ons ​​om te verhuizen onze tweede voorbeeld hier met 7 verschillende deuren. Dezelfde nummers, maar moment dat ze worden gesorteerd. Wat is uw strategie hier gaat worden, proberen te zetten van je geest wat de andere nummers waren - JENNIFER: OK. DAVID J. Malan: - eerder? JENNIFER: Laten we beginnen met de eerste. DAVID J. Malan: Oke. Beginnen met de eerste. 4. Nu waar je heen te gaan, en waarom? JENNIFER: 4 is echt klein. Dus als ze sorteren misschien kleinste het grootste, het moet twee keer dat en -. DAVID J. Malan: OK. Laten we eens kijken, wat je denkt? JENNIFER: Probeer de laatste. Leuk. DAVID J. Malan: Zeer mooi gedaan. Oke. [Applaus] DAVID J. Malan: OK. Dus je bent eigenlijk dit doen verschrikkelijk, want je bent doet het heel goed. Die laat ons niet in staat om maken bepaalde punten. Dus laten we proberen om hier terug te rollen. JENNIFER: OK. DAVID J. Malan: Zeer goed gedaan, toch. Dus je begon bij het begin, je zag dat het 4, dan heb je verplaatst naar het einde. Maar stel dat je niet krijgen geluk daar, en veronderstellen 50 ergens anders was. Wat uw derde stap zijn geweest? JENNIFER: Ga terug naar het begin. DAVID J. Malan: Ga terug aan het begin. OK, dus je zou hebben aangeraakt deze deur, die was 8. Oke. Dus dat is niet 50. Waar zou u de volgende keer hebt gekeken? JENNIFER: Als ik niet weten ze losten. DAVID J. Malan: Correct. Nou, als je dat deed weet ze gesorteerd - JENNIFER: Oh, wist, ja. DAVID J. Malan: - maar je deed niet weet nog niet waar 50 was? JENNIFER: Gewoon doorgaan. DAVID J. Malan: Oke. OK. Blijven gaan. OK, dat ik kan werken. JENNIFER: OK. DAVID J. MALAN: Nu, als je gewoon gaan om door te gaan, wat is uw algoritme delegeren gesteund in. JENNIFER: De lineaire -. DAVID J. Malan: Het is soort van lineair. Maar laat me voorstellen, laat me voor het blok gezet. Laat ik vernieuw de pagina. hetzelfde nummer, dezelfde opstelling, Dezelfde deuren. Maar denk terug aan die eerste dag in klas toen we scheurde een telefoonboek in helft, soort van, en wat was onze strategie daar? JENNIFER: Begin bij het midden. DAVID J. Malan: OK. Dus beginnen bij het midden. Dus laten we verder gaan en simuleren dat. Begin in het midden van onthullend die deur. Dus het nummer 16. Dus wat zou de sterke man hebben gedaan, wie het telefoonboek scheurde in tweeën, om naar de volgende gok? JENNIFER: Ga heen in deze helft. DAVID J. Malan: En waarom naar rechts? JENNIFER: Als ze soort van kleinste het grootste, dan 50 moet aan dat uiteinde. DAVID J. Malan: Good. Volstrekt redelijk. Dus als een telefoonboek, ga je naar de recht tegenover links, maar hier is de sleutel mee te nemen. U kunt nu weggooien, of scheuren, helft van dit probleem, zodat u niet met 7 deuren, maar echt met slechts 3. Dat is ongeveer de helft van de grootte van het probleem. Oke. Dus nu wat je zou moeten gedaan nadat je goed gaan? JENNIFER: Dus 16 is nog vrij klein, ten opzichte van 50, dus misschien zal ik proberen, zoals, deze. DAVID J. Malan: Oke. 42. Oke, dus nu wat is uw instinct vertelt je? JENNIFER: Ik kan weggooien dit en dan gewoon - DAVID J. Malan: OK. Goed, je kunt weggooien de linkerhelft daar. JENNIFER: - kies deze. DAVID J. Malan: En de rechter. JENNIFER: Yeah. DAVID J. Malan: Dus ook al is het moeilijk tot misschien zien, als er alleen 7 deuren, denken, nu, de consistentie van de -algoritme je gewoon toegepast. In het vorige geval, je deed geluk, wat geweldig was. Maar je hebt gebruikt een heuristische, Ik zou zeggen. Je gebruikte soort van je instincten, en weten gesorteerd, als het is vrij klein in het begin, natuurlijk, we hebben moet meer naar rechts. Maar in zekere zin, heb je geluk, want misschien was dit het nummer 100, en misschien 50 was meer in het midden. Misschien 50 was zelfs hier. Maar wat je anders een beetje deed deze keer was, je hetzelfde deed weer. En ik zou zeggen dat wat je net heeft, hoewel beïnvloed door de telefoon boek bijvoorbeeld, is iets veel meer algoritmische, en veel minder bijzonder ingesloten. Veel minder instinctief. Dus in het einde van de dag, hoe zou u de efficiëntie van de beschreven eerste algoritme, waar je ging links naar rechts ten opzichte van de tweede algoritme hier? JENNIFER: Dit moet men, net als, misschien halveren van de tijd, of zelfs meer, ja. DAVID J. MALAN: OK, misschien zelfs meer. Laten we duwen een beetje harder op dat. Wat echt, als we dit voortzetten logica, we zeker gehalveerd het lopende tijd met dit tweede algoritme door het weggooien van de helft van de getallen, maar wat hebben we gedaan op de volgende iteratie, wanneer Jennifer onthulde het tweede nummer? We halveerde het aantal deuren weer. En wat hebben we gedaan na dat, indien er waren meer deuren te spelen? We zouden hen halveren, en opnieuw, en opnieuw, en opnieuw. En dit was net als jullie allemaal staan ​​in de eerste week van klasse, de helft van je zitten, de helft van je zitten, de helft van je zitten, totdat een eenzame ziel stond. En we zeiden dat de looptijd van de dat, het aantal stappen duurde het was in de orde van wat? LUIDSPREKER 1: [onverstaanbaar] DAVID J. Malan: Dus log basis 2 van n, of gewoon meer gewoon, log van n. Zo iets logaritmische. En de grafiek is geen rechte lijn die net erger en erger, het was deze interessante curve die dat niet deden krijg zo slecht in de tijd. Dus laten we vasthouden aan dit idee. Laten we danken Jennifer. Hartelijk dank voor uw komst op maximaal. En, een sec. Geen bureaulampen vandaag, maar we hebben CS50 stress ballen. JENNIFER: Yay. DAVID J. Malan: Oke, hier. Dank u voor het aangaan van de stress hier boven. Oke. Dus laten we kijken of we kunnen nu niet formaliseren dit een beetje meer. Dus nogmaals, wat we net deden was in wezen hetzelfde als we deden in die eerste week. Maar eerder dan eind met slechts een lineaire algoritme dat we afgebeeld eerder als deze rechte lijn, waarbij, als we nog een deur aan het scherm en Jennifer zou hebben gehad om te kijken, potentieel, achter nog een deur. Als we nog twee deuren, zou ze hebben naar achter kijken nog twee deuren. En ja, er was deze lineaire relatie tussen de grootte van de probleem, bijvoorbeeld de x-as, en de hoeveelheid tijd die het kost om lossen op de y. Maar het beeld dat ik werd gezinspeeld op eerder was deze groene lijn. Groene opzet, omdat het voelde gewoon beter. In theorie, het algoritme, toen we deden het met het telefoonboek, toen we deden het met jullie tellen van elkaar, en in het tweede geval, wanneer Jennifer net deed het hier, het was een soort van fundamenteel beter. Want het was niet alleen twee keer zo snel. Het was zelfs vier maal zo snel. Het was volledig afhankelijk van wat de grootte van de ingang was, aan hoeveel stappen het uiteindelijk duurde. En dus dit eenvoudige idee dat we alle namen voor verleend met het telefoonboek, kunnen eveneens worden toegepast om iets als dit. En dit zou meer terloops zijn bekend als, zoals je misschien stel, verdeel en heers. Niet in tegenstelling tot wat we gedaan hebben, natuurlijk, met het telefoonboek. Maar de pseudocode, rappel, was dit. Zodat we niet weer doen, maar herinneren die eerste week, van ons allemaal opgestaan en dan de helft van je ging zitten, de helft van je ging zitten, de helft van je ging zitten. Dit algoritme is in een uitvoering beetje een vals manier, in dat, het was niet alleen een van mij tellen, fundamenteel, efficiënter. In dat geval werd ik hefboomwerking een secundaire bron. Soort, meerdere CPU's, meerdere hersenen, meerdere slimme mensen in de kamer hielpen me van iets lineaire iets logaritmische, van iets rood naar iets groens. Maar in dit geval, Jennifer alleen kan fundamenteel verbeteren van de prestaties van haar eerste algoritme door, nogmaals, net te denken een beetje harder. En nu, wanneer het tijd is om te implementeren deze dingen, uitzoeken welke regels code u dergelijke kan schrijven dat u ze weer kunt herhalen, en opnieuw, en opnieuw, soort in een looping mode. Want je bent niet van plan om het hebben luxe, net als Jennifer deed in eerste instantie, om gewoon een hele hoop mitsen en zeggen: hmm, als dit eerste getal is 4, laat me springen helemaal tot het einde. Ooh, als dat aantal is te groot, laat me willekeurig terug te gaan het tweede element. Je zult zien dat het gaat om een ​​stuk te zijn moeilijker te formaliseren wat wij mensen voor lief nemen als zeer redelijk heuristiek, maar een computer is slechts gaat doen wat je hem vertelt wat te doen. Nu heeft deze zeer interessante implicaties. Deze grafiek is soort bedoeld om een ​​soort van overweldigen visueel, maar mededeling, waar is de rechte lijn in deze grafiek? Waar is de lineaire grafiek dat noemen we n? Nou, het is een soort van naar de onderkant van deze foto, toch? Dus alles wat we hebben gedaan is we hebben soort van hebt om de x-as en de y-as om te proberen een gevoel van wat krijgen andere soorten bochten eruit. En de details van de wiskundige uitdrukkingen vandaag zal niet zo toe veel, maar merken dat er veel algoritmen die zijn veel erger dan iets dat lineair. Inderdaad, n blokjes ziet er vrij slecht. 2 tot de n ziet er vrij slecht. n kwadraat ziet er vrij slecht. En we zullen zien wat sommige van die misschien wel in de werkelijkheid van vandaag. En log n voelt zich niet zo slecht, maar beter dan n log basis van 2 n. Maar weet je, het zou zijn zelfs meer verbazingwekkend als Jennifer, of als we, die eerste week, was met gekomen iets dat log van log van n. Dus met andere woorden, er is een hele scala aan mogelijke oplossingen voor problemen, maar zelfs hier, bericht wat er gaat gebeuren. Toen ik uit te zoomen, welke van deze curven zal blijken te zijn de absolute ergste van degenen die op het scherm nu? Zo n blokjes ziet er vrij slecht op het moment. Maar als we uitzoomen en zie meer van de x en de y-as, wie gaat domineren uiteindelijk? Zodat het eigenlijk blijkt dat 2 de n, en u kunt dit uit door gewoon inpluggen in een aantal steeds groter nummers, en je zult zien dat 2 op de n inderdaad groter wordt veel sneller. Als we echt uit te zoomen, een 2 om de n algoritme absoluut zuigt. Ik bedoel dit gaat duren heel wat tijd voor de computer om churn door. Maar je zult zien in de tijd, met name met toekomstige probleem sets en zelfs afstudeerprojecten, is uw gegevens set krijgt grote, oke? Zelfs in de eerste versie van Facebook, als het aantal vrienden, en de aantal geregistreerde gebruikers heeft grote, u kunt sorteren van de telefoon in en implementeren iets met lineaire zoeken, of een zeer eenvoudige sortering algoritme, zoals we zullen zien vandaag. Je moet gaan denken harder en harder over deze problemen. En de aard van de problemen plaatsen als Facebook en Google en Microsoft, en anderen werken aan precies deze soort van big data soort vragen steeds meer van deze dagen. Oke. Dus succes van Jennifer's in die tweede algoritme, eerlijk gezegd, deed ze verbazingwekkend ook de eerste keer, maar laten we schrijf het uit als geluk, zodat we kan dit punt te maken. In het tweede geval, ze leveraged een algoritme dat nog eens herhaald en weer, maar ze nam voor verleend een bepaalde veronderstelling dat we mogen haar, maar ze uitgebuit enig detail de tweede keer dat ze niet over de eerste keer. Die was wat? Dat de lijst gesorteerd was. Dus zodra de lijst gesorteerd was, we beweren dat Jennifer in staat was om te doen fundamenteel beter. 7 deuren, ja, is dat niet interessant, maar veronderstel dat we zijn 7 miljoen deuren. Logboek van n is zeker gaat te veel, veel te voeren sneller op de lange termijn. Maar ze moest het hebben deuren gesorteerd voor haar. Nu, nam ik de vrijheid om dat te doen vooraf op het computerscherm hier, maar stel dat Jennifer moest dat zelf doen? Stel dat de deuren betrokken vertegenwoordigd gegevens in een database, of vrienden geregistreerd voor Facebook, of alle webpagina's op het internet die verschillende websites zou kunnen hebben te indexeren of zoek voorbij. Stel dat je net een ruwe data ingesteld en werd het aan u, of om Jennifer dat sortering doen? Dat, in plaats van, vereist dat we beantwoorden de vraag, nou ja, hoeveel tijd zou Jennifer, of zelfs mij, hebben genomen om die nummers te sorteren op voorhand, zodat dat ze konden profiteren van dat? Rechts? Omdat de implicatie, natuurlijk als het duurt me een tijdje om te sorteren de cijfers, die de heck cares dat u kan een getal als 50 vinden zo snel, zoals in het geval Jennifer, indien we meer dan overweldigd het bedrag van de totale tijd het duurde door het sorteren dingen op voorhand? Dus laten we kijken of we kunnen niet de verf hier de foto. Ik heb een hele hoop meer spanning ballen, als dat helpt het ijs te breken hier. En als je het niet erg zou vinden, we moet zeven vrijwilliger - op, OK. Wow. Zodat we niet hoeven te besteden op bureaulampen, lijkt het. Oke. Dus hoe zit je twee aan de voorkant. Hoe zit het met jullie twee aan de achterkant. Dus dat is vier. Hoe zit je aan de voorkant vijf, zes en zeven. Daar. Je vriend heeft wijzen je uit, dus je krijgt de prijs. Oke. Kom maar naar boven. En waarom niet wij u jongens kom eens hier. Ik ga u elk een nummer te geven. En ga je gang en leg uzelf identiek aan wat er afgebeeld op het scherm. [Onderbreekt hem VOICES] DAVID J. MALAN: Oop, sorry. Bug. Oke. Nou, daar gaan we. Nummer vijf. Nummer zes. Een, twee, drie, vier, vijf, zes, zeven. Oh, dit is onhandig. SPEAKER 2: Ik zal gewoon een -. DAVID J. Malan: Good deal. Oke. Bedankt voor uw deelname. [Applaus] OK. Oke. Dus hebben we vier, twee, zes, een, drie, zeven, vijf. Perfect dus we hebben zeven vrijwilligers Hier die even breed de array die we spelen met de eerdere. En ik koos zeven redenen dat zal net handig in een klein beetje. En ik ga eerst voor te stellen dat We sorteren van deze zeven vrijwilligers. Als je wilt, de eerste, om hallo wel. zeggen Aangezien dit gaat worden een onhandige enkele minuten. Introduceer jezelf. GRACE: Hoi, ik ben Grace. Ik ben een tweedejaars in Leverett House. BRANSON: Hi. Ik ben Branson. Ik ben een eerstejaars in Weld. GABE: Hi. Ik ben Gabe. Ik ben een junior in Cabot. NEIL: Ik ben Neil. Ik ben een eerstejaars in Matthews. JASON: Ik ben Jason. Ik ben een eerstejaars in Greenough. MIKE: Ik ben Mike. Ik ben een eerstejaars in Grays. JESS: Ik ben Jess. Ik ben een tweedejaars in Leverett. DAVID J. Malan: Excellent. Oke. Nou, bedankt voor al onze vrijwilligers hier tot nu toe. En de uitdaging bij de hand nu gaat om te sorteren van deze jongens, maar dan We gaan te hebben om een ​​beetje denken hard over hoe efficiënt we eigenlijk geordend. Dus laten we eerst proberen dit. Jullie kunnen elkaars nummers te zien , alleen maar door in de hoeken. Ga je gang en neem een ​​paar seconden, en sorteer zelven uit kleinste op de links naar grootste aan de rechterkant. Gaan. OK. Goed. Dat was echt darn snel. Nu iemand hier, wat was het algoritme dat deze jongens toegepast? LUIDSPREKER 1: minst naar grootst. DAVID J. Malan: OK. Minst naar meest is echt soort van de doelstelling, maar ik ben niet zeker dat is echt een algoritme. Minst naar meest vertelt niet me stap-voor-stap wat te doen. Yeah? LUIDSPREKER 1: [onverstaanbaar] DAVID J. Malan: OK. Dus als je een persoon kleiner dan uw nummer, ga dan naar Rechts er. Dus dat is nu steeds meer expressief, meer als een algoritme, omdat u kan zeggen, als dit, dan dat. Dus we hebben een soort van conditionele construct. En deze jongens leek dat een paar doen tijden, omdat sommige van jullie bewogen een beetje van een afstand. Dus er was vermoedelijk een soort van looping gaande is in hun gedachten. Maar laten we proberen te formaliseren dat. Als jullie terug kon resetten deze regeling. Laten we eens kijken of we niet kunnen formaliseren dit een beetje, en dan de vraag stellen, maar hoe efficiënt is dit? Natuurlijk, wanneer we dit doen langzamer, het gaat zo goed van te voelen een algoritme, maar laten we eens kijken of we kunnen zetten onze vingers op de precieze stappen. Zodat je twee jongens zijn vier en twee. Of je juist of onjuist orde? Uiteraard ingevuld. Dus we verwisseld. Nu ga ik opzij bewegen hier en zeg, 4-6. Bent u juist of onjuist? GABE: Correct. DAVID J. Malan: Correct. Zes en een? Nope. Swap. Dus dat is twee swaps. Zes en drie? Nope. Swap. Zes en zeven? Ziet er goed uit. Zeven en vijf? JESS: [onverstaanbaar] DAVID J. MALAN: OK, swap. En gesorteerd. Oke. Dus natuurlijk niet, toch? Dus er meer aan de hand is op. Maar, inderdaad, deze jongens, zelfs gewoon instinctief. beweging gehouden. Ze hebben niet alleen te stoppen, als ze eenmaal gecorrigeerd een probleem. So. Inderdaad, ik ga moeten om hetzelfde te doen. Ik ga te hebben om een ​​soort van terugspoelen terug aan het begin van dit probleem, of het begin van deze reeks van mensen, laten we beginnen ze te roepen. En nu, wat moet mijn algoritme Bij de tweede beweging zijn? LUIDSPREKER 1: Hetzelfde. DAVID J. Malan: Hetzelfde. En dit, ik ben beginnen te vinden, toch? Zodra u merkt dat je doet hetzelfde opnieuw en opnieuw, dat is steeds meer als een algoritme, en minder menselijk instinct. Dus nu, daar gaan we weer. Twee en vier? Nee. Vier en een? Ah, was er inderdaad een aantal werk nog gedaan moet worden. Voor en drie? Goed. Vier en zes? Zes en vijf? Zes en zeven? OK, nu, gedaan. OK, nee. Ik heb om terug te gaan. Dus nu, nogmaals, dat we dit doen een beetje meer bewust. En nu, er is gewoon een brein uitvoeren van dit algoritme. Een CPU, als je wil. En eerlijk gezegd, dat is de enige bron gaan we toegang tot hebben. En zodra we terug gaan naar een toetsenbord en hebben iets als C bij ons verwijdering, we alleen maar het schrijven van een programma dat een ding kan doen op een moment. Overwegende dat deze jongens een moment geleden, hebben we leveraged hun collectieve denkkracht zoals jullie deden in week nul. Dus laten we dit blijven doen. Twee en een. Twee en drie. Drie en vier. Vier en vijf. Vijf en zes. Zes en zeven. Gedaan? Dus ik ben, maar laat me spelen advocaat van de duivel. Heb ik, het soort computer die net maakte een pass door deze array van mensen, weten dat ik klaar ben? LUIDSPREKER 1: No DAVID J. Malan: Waarom? Wat zou ik moeten doen om concluderen resoluut dat ik klaar ben? Waarschijnlijk een meer door. Rechts? Want alles wat ik weet van die eerdere pas is dat ik gecorrigeerd een fout. En dat betekent, misschien is er nog een andere fout die ik moet corrigeren. Dus ik kan alleen zeker zijn door terugspoelen, en dan controleren, 1-2, twee en drie, drie en vier, vier en vijf, vijf en zes, zes en zeven. OK, nu heb ik geen werk. Ik kan zeker herinneren dat ik deed geen werken met iets als een variabele, als een int. Noem het swaps, en als swaps is 0 keer I krijgen hier, en het begon op 0, dan Ik zou gewoon dom zijn om door te gaan heen en weer, opnieuw controleren, en opnieuw, en opnieuw, toch? Omdat je vastzit in een aantal soort van oneindige lus. Dus zodra er 0 swaps, we kunnen beweren dat dit algoritme is inderdaad voltooid. Nu, laten we een naam op deze. Het algoritme dat ik voorstel dat we gewoon geïmplementeerd is iets genaamd bubble soort, als zodanig bekend in de zin dat de getallen die groter zijn soort bubble hun weg naar de top, of maximaal aan het einde van de reeks getallen. Maar hoe efficiënt was dit algoritme? Hoeveel stappen heb ik fysiek moet nemen, bijvoorbeeld om deze te sorteren zeven mensen? Vier tot vijf? OK, te veel is uiteindelijk gaan naar het antwoord. Maar zelfs dan, het specifieke nummer is niet zo interessant. Laten we generaliseren het als n. Dus als ik had n mensen hier, en ze waren, soort van, in willekeurige volgorde op de beginnen, in die oorspronkelijke volgorde. Nou, hoeveel stappen moest ik te nemen op de eerste pas? Het was een, twee, drie, vier, vijf, zes, en ze zijn zeven mensen, dus dat is zeven, zes -, dus dat is n min een stappen de eerste keer. Nu, hoeveel stappen moest ik te nemen wanneer ik teruggespoeld? Nou, we konden eigenlijk verdubbelen dat als we echt wilden, maar voor nu, ben ik gewoon om te zeggen, oke, andere n minus 1. Zodat het n minus 1 gaat krijgen vervelend om bij te houden, dus laten we net om iets omhoog. Dus 2n stappen. Dus 14 stappen, geven of te nemen. Hoe vaak heb ik een stap de volgende keer? Nou, het is 3n. echt. Nu, in het slechtste geval voor Bijvoorbeeld, hoe vaak zou ik gegaan heen en weer, heen en weer, uitvoeren van dit algoritme swapping mensen op elke pas, ruwweg? Het is eigenlijk n kwadraat, toch? Want in het ergste geval, je kan soort van denken over dit intuïtief, ook al is het een beetje zou kunnen nemen beetje tijd om te bezinken In het slechtste geval, wat zou deze zeven mensen gekeken hebben als, in voorwaarden van de overeenkomst van hun nummers? Volledig achteruit, toch? En alleen te simuleren dat, Wat was je naam ook alweer? MIKE: Mike. DAVID J. Malan: Mike? OK, Mike, kun je gewoon bij me over hier voor slechts een seconde? Eigenlijk niet. Sorry Mike, laten we terugspoelen. Hoe heet je ook alweer? NEIL: Neil. DAVID J. Malan: Neil. OK, Neil, kom je met me, als je het niet erg vindt. Dus ik ga voorstellen, alleen voor eenvoud, dat Neil nu in zijn slechtst denkbare geval. Maar herinneren hoe ik geïmplementeerd mijn algoritme. Ik vergelijk, vergelijken vergelijken vergelijken, vergelijken, oh. Nu zijn deze jongens uit van orde, dus ik fix. Dus jullie ruilen. Maar denk nu, hoe veel verder hoeft Neil moeten gaan? Het is ruwweg n. Je weet wel, het is niet echt n. Het is als, n minus 1, maar ik krijg geërgerd bijhouden van de kleine nummer, dus laten we gewoon noemen het n. Dus als Neil beweegt een stap maximaal elkaar tijd, en Neil een stap te verplaatsen, Ik moet dit echt vervelend pas maken heen en weer, wat ruwweg Daarbij n stappen in totaal n maal, want het gaat me te nemen dat vele stappen naar Neil allemaal de weg waar hij behoort. Laat staan ​​iedereen anders als jullie waren allemaal verkeerd bestelde ook. Dus laten we noemen bubble sort n kwadraat. De looptijd van dit algoritme, de prestaties van dit algoritme, de efficiëntie van dit algoritme, we zullen gewoon beschrijven meer algemeen als n kwadraat. Dat is leuk, want ik kon doen het Hetzelfde voorbeeld met acht mensen, negen mensen, een miljoen mensen, en dat antwoord is niet van plan om te veranderen. Dus als jullie het niet erg vindt, laten we reset je naar waar je begon. En laten we proberen twee andere benaderingen en zien of we niet fundamenteel kunnen doen beter dan deze. Dus deze keer, ga ik voorstellen een soort ander algoritme. Dat was heel slim van ons vorige keer, en jullie hadden gelijk aan het hebben juiste instincten van gewoon een soort van swapping paarsgewijze. Maar als ik echt wilde deze te benaderen gewoon, en mijn doel is om te bewegen alle kleine aantallen deze manier, en Duw alle van de grote getallen die Trouwens, waarom niet ik dat alleen in de meest naïeve manier mogelijk te maken en te zien of ik kan beter dan wat was doen vrij complex algoritme? Dus laten we eens kijken. Vier is een vrij klein aantal, dus ik ben ga je daar laten ogenblik. Ooh, nummer twee is nog beter. Zo kunt u gewoon stap voorwaarts voor een moment? Dit is momenteel mijn kleinste genummerde kandidaat, en ik ga om te onthouden dat met, zoals, een variabele. Maar ik ga blijven controleren. Is er iemand wiens getal is kleiner? Six, nee. Oh, is er Neil weer. Dus ik ga u terug te duwen soort conceptueel. Neil zal naar voren komen. En nu, de variabele die ik gebruik om bijhouden wie de kleinste heeft nummer wordt bijgewerkt om bevatten Locatie Neil's. Nou, laten we eens kijken. Drie, zeven, vijf. OK, ik weet dat Neil was de kleinste. Wat is de eenvoudigste zaak voor mij om nu te doen? Ik ben niet van plan om mijn tijd te verspillen door gewoon borrelende Neil ene plek naar links. Waarom heb ik niet gewoon Neil waar hij behoort, die natuurlijk Abuse Helemaal aan het begin. Dus Neil, kom met me mee. En wat was je naam ook alweer? GRACE: Grace. DAVID J. Malan: Grace. OK. Dus Grace, helaas, je bent soort in de weg. Dus hoe kunnen we dit probleem oplossen? Rechts? Indien een array, er slechts zeven locaties. Bedenk dat, met Rob, we spraken over verklaren leeftijden, en we hadden alleen een eindig aantal leeftijden? Hetzelfde idee hier. We hebben slechts een eindig aantal ints. Grace is een soort van in onze manier, dus hoe kunnen we oplossen? De eenvoudigste manier is als, Genade, sorry. Je gaat te hebben om over te gaan daar dus kunnen we ruimte maken. Nu, als je van deze, misschien we net het probleem erger. En misschien hebben we gedaan, want wat als Genade waren op de juiste plaats? Maar we weten dat ze niet, want anders, zou ze zijn geweest staande vooruit in plaats van Neil in deze tijd, toch? We hebben al controleerde haar nummer uit. Oke. Dus nu, Neil is op de juiste plaats, en Ik kan een lichte optimalisatie te doen. Voor de volgende minuut, ga ik negeer Neil allemaal samen, zodat geen zijn tijd verdoen, of per ongeluk swap hem naar de verkeerde plaats. Dus nu, hoe krijg ik het volgende te vinden element dat is kleinst? Twee. Dat is een vrij goed nummer, indien je wilt naar voren en Ik zal je niet vergeten. Zes, niet goed. Vier, drie, zeven, vijf, niet goed. Dus laat me bewegen om uw juiste plek. En we zijn net geluk dit keer. Nu, ik ga deze negeren twee jongens, en nu doen een meer passeren dit. Zes, dat een vrij klein aantal. Kom op vooruit. Oh, sorry. Grace's nummer is beter, dus stap op vooruit. Four. Sorry, Grace. Ga weer terug. Nummer drie is beter. Zeven. Vijf. En wat nu heet je ook alweer? JASON: Jason. DAVID J. Malan: Jason. Dus Jason is nu de kleinste element dat ik heb geselecteerd. Waar gaat hij heen? Dus waar zes is. En uw naam is weer? GABE: Gabe. DAVID J. Malan: Gabe. Gabe is in de weg. Wat is de makkelijkste om te doen? Verwissel deze twee jongens en doorgaan. Dus laten we nu zien. Wie is de kleinste? Four. Laat me gewoon een soort cheat. Vijf gaat om de kleinste te zijn. Ik vind de volgende, als je wilt stappen vooruit, wat heb ik te maken met deze jongens, met Gabe? Opnieuw wisselen. Dus nu, nog steeds licht buiten de orde. Ik vond Gabe het laagste is, zo Ik pop hem uit, beweeg je jongens overgenomen. En gedaan. Dus antwoord is hetzelfde. Het eindresultaat is hetzelfde. Welke van deze twee algoritmen is beter? De tweede, hoorde ik. Waarom? SPEAKER 3: Het is n stappen [onverstaanbaar]. DAVID J. Malan: Het is n stappen bij de meeste. Interessant. Dus is het wel? Dus hoe vind ik de kleinste element? Hoeveel stappen heb ik moeten nemen het het kleinste element vinden? Ik had een kijk helemaal op het einde, toch? Want dan worst case, welke Als Neil waren hierheen? Dus gewoon het vinden van het kleinste element neemt me n stappen, of n minus 1. Maar, OK. Dus fix Neil. Vergeet niet dat, een minuut of zo geleden. Maar hoe heb ik het volgende te vinden kleinste element? Het is n minus 1, of n min 2 echt, van het aantal stappen. Nou ja. Dus ik heb n minus 2. Oke. Dus dat voelt een beetje beter. Oke. Hoeveel stappen de volgende keer naar nummer drie vinden? Zo n min 4. Dus het is dalende, een minder stap op elke iteratie. Dus dit voelt beter, toch? Als laatste keer was ongeveer n keer n, dit keer is het n min 1, plus n minus 2, plus n min 3, plus n min 4, puntje, puntje, puntje. Maar als u zich herinneren van je middelbare school leerboeken, de kleine cheat plaat aan de achterkant die formules heeft, indien je optelt deze reeks getallen, wat het totale aantal stappen gaat zijn dat ik hier? Dit is een van die, als, n minus 1 maal n, gedeeld door 2. Dus laat me zien of ik kan trekken dit voor slechts een moment. En nogmaals, ik ben soort van afronding sommige aantallen alleen maar om ons leven eenvoudig te houden, maar als ik me goed herinner, het is zoiets als Ik doe n minus 1 dingen, dan n minus 2, dan is n min 3, het is grofweg zoiets als dit dan 2, en als ik vermenigvuldig dit uit, dat is eigenlijk n plein. Dat is niet al te goed voelen. n minus n meer dan 2. Maar hier is het ding. In de informatica, toen de problemen beginnen te krijgen interessant is wanneer n wordt echt groot. En als n wordt echt groot, die van deze waarden gaat alles domineren van de anderen? Het is een soort van de n kwadraat, toch? Ja, delen door 2 is vrij goed. Maar als je praat over miljarden van stukjes data, of triljoenen stukken gegevens, OK, dus je bent twee keer zo snel. Maar die echt cares als dat groot getal, Als deze factor is wat krijgt groter en groter. En voorwaar, het maakt meer van een verschil dan deze man. Dus zelfs al jullie hebben gelijk, de tweede algoritme, zullen we het noemen selectie sorteren, is in de echte wereld, een iets sneller potentieel, want ik ben nemen steeds minder stappen elke keer. Het is niet echt fundamenteel sneller. Want als we daadwerkelijk deze spelen uit voor grote waarden van n, eind de dag, voor groot genoeg n, het is nog steeds gaat vrij traag te voelen. Nou, laat me een laatste pas op dat. Dat is wat ik zou noemen selectie sorteren. Kunnen jullie resetten jezelf een laatste keer? En in dit laatste geval, ik ga om iets voor te stellen riep insertion sort. Insertion sort zijnde, conceptueel, een beetje anders. In plaats van heen en weer en selecteren van het kleinste element, ik ben gewoon om te gaan met elk van deze jongens zoals ik ze tegenkomt, en steek ze in hun juiste plaats. Dus ik ga gewoon beginnen met Grace, en ik zie dat ze is nummer vier. Waar komt nummer vier behoort? Ik heb niet begonnen iets te sorteren, dus Grace krijgt om daar te blijven. En nu ga ik te beweren, als je kon neem een ​​stap naar rechts, dit mijn gesorteerde lijst, dit is mijn ongesorteerde resterende lijst. Dus nu ga ik volgende gaan, en wat is je naam ook alweer? Branson:. DAVID J. Malan: Branson. Dus Branson is nummer twee. Dus ik ga om u te nemen uit voor een moment. En nu, waar moet je horen in deze array? Dus om het recht van genade. Dus nogmaals, we zijn soort van het maken Grace doet een hoop werk hier. Waar laten we u? Dus we gaan je schuiven naar de links, en steek Branson daar. Maar nu beweren dat ik jullie zijn klaar. Maar let op, ik ben niet met behulp van extra ruimte. Het is nog steeds 2 elementen hier, 5 dan hier. Totale array size is 7, dus ik ben niet bedriegen, oke? Dus nu hebben we, met Gabe hier, het nummer zes, waar hoor je thuis? Je hebt weer geluk. Dus je krijgt om daar te blijven. Neem gewoon een lichte stap naar rechts alleen maar om duidelijk te maken dat je naargelang bent. En nu hebben we Neil weer, nummer men, waar ga je heen? En nu is waar we zullen beginnen om dat te zien Dit algoritme, maar in het eerste blik, voelt behoorlijk slim, kijken wat er gaat gebeuren. Als je vooruit kon stappen. Waar willen we naar Neil zetten? Zo duidelijk hier, dus hoe komen we daar Neil? Laten we deze stap-voor-stap. Gabe, waar heb je nodig om te gaan? Yep, dus neem een ​​grote stap, of twee halve stappen om ervoor te een stap daar. Genade, waar je heen gaat? Goed. Dus weer een stap. Tenslotte Branson? Een andere stap. En nu kunnen we Neil zetten in plaats. Dus nu, blijft deze logica. Ook al zijn we niet verschuiven Neil over, en dan, en dan, om hem waar hij gaat, in het ergste geval, de volgende nummer we zouden tegenkomen konden 'het aantal, zeg, was er een aantal nul, dan gaan we allemaal verschuiven deze jongens. Stel dat er een aantal, negatieve men, dan hebben we te verschuiven al deze jongens. Dus we zijn eigenlijk gewoon een soort van flippen het probleem rond, zodanig dat we het overbrengen van de lasten van de selectieproces zodat het inbrengen proces, zodanig dat jullie net aan ruwweg n minus iets bewegen aantal stappen. En dat aantal stappen is alleen maar te verhogen als ik meer nummers te selecteren, als ik moet blijven duwen jullie terug, en weer terug, en weer terug. Dus het trieste is nu al deze algoritmen zijn n kwadraat. Laten we verder gaan en dankzij deze jongens, en visualiseer deze een beetje anders. Zeer goed gedaan. [Applaus] Oke. Daar ga je. Bedankt voor het - BRANSON: [onverstaanbaar] houden de nummers. DAVID J. MALAN: Nee, dat mag je houden de nummers ook. Oke. Mooi gedaan. Oke. Dus laten we kijken of we kunnen nu niet samenvatten sneller en meer visueel, precies wat er net gebeurd hier volgt. Ik ga om te gaan en trek Firefox. We zullen deze demonstratie koppelen op de website van de cursus. Java is een beetje vervelend om te werken in sommige browsers deze dagen. Dus als je het spelen met deze thuis, beseft dat je nodig zou kunnen hebben om Firefox te gebruiken om het werkend te krijgen. En wat ik ga doen met deze demonstratie is de volgende. Aan de onderkant, ik heb een hele hoop menu-opties, waaronder een start en een stopknop. Ook, als een terzijde, lijkt er een bug in deze programma's, waarbij je kan eigenlijk niet zien de start of stop knop tenzij je houd Command of Alt plus-en inzoomen, wat merkwaardig laat je meer knoppen. Dus gewoon FYI als je speelt met deze thuis. Nu ga ik om te klikken op Start in slechts een Momenteel, na het opgeven van een vertraging van, zoals, 200 milliseconden hier, net zodat we kunnen zien wat er gebeurt. Dus ik beweren dat dit een visualisatie van het eerste algoritme deze jongens deden, bubble sort, waarbij We wisselden mensen pair-wise. De sleutel tot dit inzicht visualisatie dat de hoogte van de staven geeft de grootte van het getal. Zodat het langer de balk, de Hoe groter het getal. Korter de balk, kleiner het getal. En als je merkt, we gaan door de eerste variant van dit algoritme, swapping grote en kleine aantallen, zodat het geringe aantal op de eerste plaats en het grote aantal gaat naar rechts. En zodra we het einde van de array van veel meer nummers dan zeven, zijn we gaan terug naar het begin. En te anticiperen op deze. Op de uiterst links, is dat ventje gaan om te wisselen naar de zijkant, en dit proces herhaalt. Nu deze visualisatie snel weer saai, dus laat ik doorgaan en stoppen het, verander de vertraging iets veel sneller gewoon om nu te krijgen, een gevoel voor dit algoritme. Dus ook al heb ik versneld het op, dit is zoals het upgraden mijn processor, kopen een nieuwe computer. Ik heb niet fundamenteel veranderd mijn algoritme, maar je kunt wel meer zien duidelijk dan bij mensen, dat de grote nummers zijn borrelen tot aan de top, en de kleine aantallen borrelen naar beneden. En nu dit ding hier gesorteerd. En als een terzijde, op de pleinen, is er slechts enkele boekhouding daar te helpen tellen hoeveel vergelijkingen, of hoeveel swaps hebben daadwerkelijk zijn gedaan. Nou, laten we proberen een van de anderen die we zagen. Laat ik klik op bubble sort hier, en laat me kiezen, en deze hele webpagina is een beetje buggy. Laten we accepteren het risico en voer het opnieuw. Daar gaan we. Dus laten we doen selectie sorteren. Ik weet niet waarom het menu verschijnt daar. Laten we inzoomen om dat te verhelpen bug, verandert dit naar 50. Ach, laten we eigenlijk doen dat veel sneller. Vijf milliseconden of zo, en Start. Dus dit is selectie sorteren. Dus nogmaals, na te denken over wat we deed met de mensen hier. We gingen door de array en geselecteerd opnieuw het kleinste element, en opnieuw, en opnieuw. Nu ik beweren dat nog steeds vrij slecht was. Het was nog steeds n kwadraat, geven of te nemen, maar het was, in de echte wereld, wat sneller, want ik was inderdaad het nemen van iets minder stappen elke keer. Maar we praten alleen wat? Misschien 40 of zo bars hier? We praten niet 40 miljoen. Dus het is niet helemaal duidelijk voor mij dat was inderdaad een belangrijke aanwinst. Laat me nu terug te gaan en te veranderen naar onze derde algoritme, dat werd selecteer insertion sort. En nu is het echt buggy omdat de menu moet echt niet daar beneden. Dus nu zullen we hier terug te scrollen en start dit algoritme. Whoop, starten en stoppen. Dus deze ene soort heeft een mooi patroon om het, waardoor we weer inbrengen van de mens, of casu de staven in hun juiste locatie. En het is al eerder gedaan Ik draaide me om. Maar deze ook, in theorie, is nog steeds n kwadraat. Dus laten we kijken of we niet kunnen vatten deze als volgt. Ik ga om te gaan en gewoon te geven ons soort van een gemeenschappelijke manier van praten over deze dingen, laat me even gewoon een beetje notatie hier. Je staat op het punt om te zien iets groots geroepen O, omdat het letterlijk een grote O. En dit is een manier die een computer wetenschapper of een wiskundige zelfs gebruikt aan de lopende tijd beschrijven sommige algoritme. Hoeveel stappen werkt het eigenlijk nemen? Nu ga ik mezelf in verlegenheid te brengen met mijn handschrift hier in slechts een moment. Maar laat me gaan en zeggen dat Dit zal grote O zijn hierheen. En laat me even een andere symbool, een hoofdletter omega. Omega gaat het tegenovergestelde, wezen, van grote O. Overwegende grote O middelen, in het ergste geval, hoeveel tijd misschien wat algoritme te nemen, in termen van n, wordt omega gaat worden hoeveel tijd zou het nemen in het beste geval. En we zullen zien wat we bedoelen met best case in slechts een moment. Dus laten we beginnen met iets eenvoudigs. Laat ik beginnen met een lineaire zoekopdracht. Dus niet sorteren. We zullen deze lineaire zoekopdracht noemen. En nu, maak een beetje tabel uit deze. Nu, in het geval van lineaire search, in het ergste geval, hoeveel stappen is het gaat me naar een vondst aantal willekeurige keuze? En er is n totaal deuren of n totaal nummers. Worst case. Hoeveel stappen ga ik moeten naar het nummer 50 vinden in een array van n deuren? En waarom? Omdat het misschien wel alle weg over naar het einde. Zoveel als Jennifer ondervonden, de nummer 50 in was helemaal over, zodat het ergste geval lineaire zoekopdracht is big O van n, zullen we zeggen. Hoe zit het met het beste geval, als je echt geluk? Het gaat gewoon om een ​​stap te nemen, of een constant aantal stappen. Dus we dat omschrijven als 1. Dit is dus vrij goed. Nu, wat als we iets deden als binary search? Dus binary search, in het slechtste geval, nam hoeveel tijd? [Onderbreekt hem VOICES] DAVID J. Malan: Dus eigenlijk, ik hoorde het in een paar plaatsen. Dus het is eigenlijk te loggen n, geven of te nemen, want zoals we verdelen de lijst in de helft opnieuw, en opnieuw, en opnieuw, zijn we in staat vinden, uiteindelijk, de waarde, Als het er is, maar er is een catch. Wat is de veronderstelling dat we moeten voor lief nemen voor binary search? Het moet worden gesorteerd. Het is niet gesorteerd, kunt u de zaak te splitsen in de helft opnieuw en opnieuw, en u kan naar links, en je kunt gelijk gaan, en je kunt gaan links en rechts, maar je bent niet van plan om het element indien vinden de lijst is niet gesorteerd, omdat de je zou missen. Omdat uw heuristische, voor het gaan naar links of rechts zal worden ontsierd als het inderdaad niet gesorteerd. Dus er is een soort van verborgen kosten om met behulp van iets als dit. Nu, laten we gaan in onze sortering algoritmen niet zoeken - oh, eigenlijk laten we gaan in deze blanco. Binair zoeken in het beste geval? Het is ook 1 als het gebeurt gewoon te zijn in het midden van de array, of het midden van het telefoonboek. Laten we nu een bubble sort. Dus nogmaals, nu zijn we het invoeren van de soorten, niet de zoekopdrachten. In het ergste geval, hoeveel stappen deden we vordering bubble sort gaat duren? n kwadraat. Dus ik ga om te tekenen dat. Ooh, mijn handschrift ziet er nog slechter wanneer het wordt voorspeld dat grote. Oke. Dus dat is n kwadraat. En in het beste geval van bubble sort, hoeveel stappen gaat dat duren? 1, hoorde ik. LUIDSPREKER 1: n. DAVID J. MALAN: n, hoorde ik. LUIDSPREKER 1: 2. DAVID J. MALAN: 2, hoorde ik. Hoor ik 3? Oke. Dus ik heb gehoord 1, n, 2, maar laten plukken elkaar ten minste de eerste van deze suggesties 1. Het is geen slechte instinct, want het soort volgt een patroon hier. Maar als het duurt maar 1 stap, hoe in de wereld kon ik beweren dat de lijst wordt gesorteerd, want als ik alleen toegestaan tot en met 1 stap, hoeveel elementen nemen kon ik eigenlijk controleren om er zeker van? Nou ja, gewoon 1, wat betekent dat er n minus 1 elementen die kunnen worden uit orde, en ik ben gewoon gaan over het geloof na bekeken 1 element dat de ding wordt gesorteerd. Dus 1 is hier niet te corrigeren. Dus minimaal, hoeveel moet ik naar kijken? [Onderbreekt hem VOICES] DAVID J. Malan: n minus 1, of eigenlijk, n, want ik moet kijken naar elke element ervoor zorgen dat het is niet in de juiste volgorde. Maar nogmaals, we soort van wave onze handen bij de kleinere aantallen en gaan ervan uit dat, als n groot wordt, zijn ze oninteressant toch. Dus dat is bubble sort. En nu, laten we deze laatste twee. Selectie sorteren, en dan zullen we doen insertion sort. En dan zullen wij uw blazen geest met iets veel beter dan deze. Oke. Wat is het ergste geval loopt tijdstip van de selectie sorteren? SPEAKER 4: n kwadraat. DAVID J. Malan: n vierkant, ik hoor. Maar waarom n kwadraat, intuïtief? SPEAKER 4: Omdat we deden het gewoon. DAVID J. Malan: Omdat we deden het gewoon. OK. Goed antwoord. Maar intuïtief, waarom is selectie sorteer n kwadraat? Wat hebben we moeten doen opnieuw en opnieuw? We moesten scannen via te houden, zijn u de kleinste, bent u de kleinste, bent u de kleinste. En verleend, waren we in staat om n te nemen stappen, dan n minus 1, dan is n minus 2. Maar als je soort die allemaal optellen, of neem het op het geloof dat ik heb toegevoegd ze van tevoren, krijgen we grofweg n kwadraat minus enkele kleinere aantallen. Dus ik ga dit n kwadraat noemen. Maar met de selectie sorteren in de beste geval is, hoeveel stappen is het gaat me te nemen? SPEAKER 5: [onverstaanbaar] DAVID J. Malan: Het is helaas nog n kwadraat, toch? Want als ik de keuze van de kleinste element, en we hadden zeven mensen hier, Ik weet alleen, zodra ik aan de zeer einde, dat ik heb de kleinste gevonden nummer, waar hij of ze kan zijn. Maar hoe kan ik het volgende vinden kleinste getal? Ik moet nog een keer doen. Dus in het beste geval, wat is de input voor selectie sorteren? Het is een reeds soort lijst, nummer een, nummer twee, nummer drie, nummer vier. Maar ik ben een computer. Ik kan alleen maar kijken naar een ding tegelijk. Ik kan niet sorteren van een stap terug als een mens en zeggen: ooh, dit ziet er correct. Ik kan alleen maar oordelen correctheid in selectie sorteren door het selecteren van de kleinste getal. Maar zelfs als ik vind nummer een eerste, als ik niet iets anders over weten de andere nummers, wat ik niet doe, alles wat ik weten dat ik heb ingeleverd een array of een stel deuren waarachter nummers, de enige manier waarop ik weet dat een was de kleinste? Als ik helemaal hier en realiseren, damn, was inderdaad het kleinst. Maar hoe kan ik dan bepalen dat twee is de volgende kleinste? Door hetzelfde te doen inefficiëntie weer. Dus eindelijk, met insertion sort, hoe, in het ergste geval, hadden we het zeggen presteert? Het ook is n kwadraat. En hoe zit het met de beste zaak? We laten dat als een cliffhanger. We zullen in die lege volgende keer vullen, maar eerst laat ik stel voor dat we fundamenteel beter doen dan al deze, oke? Dus denk zelf wat inbrengen soort gaat worden. Nou, dat was niet erg dramatisch, want ik ben de enige dat zag de verandering. Wow. OK. Dus hier hebben we een wat verschillende demonstratie. Als ik in te zoomen hier, zult u zien dat op de linkerkant hebben we bubble sort, in de midden hebben we selectie sorteren, en op Uiterst rechts, we iets hebben wij heb niet gekeken naar nog riep samenvoegen sorteren. Maar nadenken over wat we hebben hier tot nu toe vandaag. Toen Jennifer kwam voor het eerst op het podium, We gingen door de matrix van getallen opnieuw, en opnieuw, met lineaire zoeken, en we kregen lineaire lopende tijd, big O van n, zo te zeggen. Wanneer beschouwen we de eerste week van klasse, toen we hadden verdeel en heers, en we hadden het telefoonboek scheuren, en Jennifer, en we collectief leveraged dat belangrijk inzicht, dat was om steeds weer herhalen jezelf door een of andere manier weg te gooien, weg te gooien, weggooien, de helft van het probleem of algemeen, delen een probleem in half, en vervolgens behandelen van de kleinere stuk het probleem als conceptueel gelijkwaardig de andere, we hebben ergens fundamenteel beter. Maar met bubble sort, met selectie soort, met insertion sort, hebben we kunnen geen dergelijke inzichten die Jennifer deed. We vrijwel alleen liep terug en weer een hele hoop tijd, en we tweaked dingen een beetje, ruilen in deze volgorde, misschien invoegen of selecteren. Maar aan het eind van de dag, heb ik veel van onhandige lopen heen en weer. We hebben niet echt iets leverage smart als Jennifer deed zoals het verdelen en veroveren. Dus samenvoegen sorteren, daarentegen, waardoor we zal niet te zien tot volgende week, het gaat om gebruik te maken dat de belangrijkste idee door te delen de ingang, en dan halveren, en vervolgens halveren, en dan halveren. En elke iteratie van de loop, sorteren van de linkerhelft en de juiste helft, dan de linkerhelft van linkerdeel en de rechterhelft van de linker, dan de linkerhelft van de rechterhelft en de rechterhelft van de rechterhelft. En het herhalen weer. Dus zie je dit visueel te zien, maar dit is wat ons te wachten staat volgende week. En in het algemeen, als we denken een beetje beetje harder op dergelijke problemen. We n kwadraat links, n kwadraat in het midden, en n log n aan de rechterkant. Dus er is je echte cliffhanger. We zien je op maandag. [Applaus]