SPEAKER: Okay, det her er CS50. Det er i slutningen af ​​uge tre, og hvis du ikke har benyttet sig allerede, ved, at der vil være frokost denne fredag ​​som sædvanlig, hvor du kan nyde god samtale og fødevarer på Fire and Ice med nogle af CS50 s personale og klassekammerater. Hovedet til denne webadresse her. Nu kan du huske, eller du kan snart være bekendt med, disse ting her, som er givet i slutningen af semestret for mange klasser. Såkaldte eksamen blå bøger, hvor du skriver dine svar eksamener. Nu har jeg her 26 sådan blå bøger, på hver af dem er skrevet et navn, en A til Z. Og faktisk navnene er så simpelt, A gennem Z. Og en af målene ved hånden i dag vil være at fortsætte det, vi startede i mandags, hvilket ikke er så meget at kigge på koden, men virkelig ser på ideer og problemløsning. Et af målene og løfter om dette kursus er at lære dig at tænke mere omhyggeligt, mere metodisk, og til at løse problemer mere effektivt. Og ja, vi kan gøre, der virkelig uden selv at røre en linje kode. Så jeg har et par elefanter op her i dag, orange og blå, hvis vi kunne få en frivillig, måske fra længere tilbage end normalt. Hvad med lige der, kom ned. Målet, som vil være til hjælpe plus administrere denne eksamen her. Hvad er dit navn? Publikum: Mary Beth. SPEAKER: Mary Beth, kom op. Lad mig få mikrofonen her for dig. Rart at møde dig. Publikum: Rart at møde dig. SPEAKER: Okay, så jeg har her blå bøger A til Z, og jeg har tænkt mig at foregive, at Jeg har en af ​​de studerende, og de kommer i lidt tilfældigt ved slutningen af ​​en tre timers prøve blok, så de er ender i nogle semi-tilfældig rækkefølge som denne. Nu er din opgave på bare et øjeblik går at være-- dette er faktisk, hvordan de får slået i slutningen af klassen, mest sandsynlige. Dit job nu kommer til at være helt simpelthen, at sortere disse blå bøger til os fra A til Z. PUBLIKUM: Åh, det er kommer til at tage for evigt. SPEAKER: Og vi vil se som du gør dette, ingen pres. PUBLIKUM: Nej, ingen pres eller noget. SPEAKER: Og for sjov, lad os sætte en timer. PUBLIKUM: Så meget sjov, så meget sjov. SPEAKER: Jeg kan holde mikrofonen for dig. Okay, vi har lige fordoblet vores hastighed. Så i mellemtiden, lad mig stille, hvad der er vil være spørgsmålet om Mary Beth er, hvad hun laver, hvordan er hun går om at løse dette? Og i virkeligheden, har du måske ikke nogensinde tænkt over noget så simpelt som når du vælger op 26 bøger som denne, som har en naturlig bestilling til dem. Hvad er den proces, at du rent faktisk bruge? Er det temmelig tilfældigt bare plukke den første, du ser og sætte det på sin plads? Har du først flytte dine hænder rundt Leder du efter en så søger B? Har du tage et kig på en par af dem side om side og bare sige, vent et øjeblik, dette er ikke rigtigt, og så bytte den rækkefølge? Vi så allerede på mandag at der er en række måder hvor vi kan gøre dette, og ja da vi nær slutningen her, Jeg ville tage til efterretning måske af, hvad Mary Beth gør. Vi har et par bunker synes det, en større en, tre mindre. Publikum: Jeg beordrer dem når jeg finder to bogstaver at jeg ved, er sammen i en sekvens, Jeg satte dem sammen, så jeg ikke nødt til at bekymre sig om at holde spor af en hel række af bøger. Det er bare, åh, A er det første, Jeg har denne stak her. SPEAKER: Så, næsten som et puslespil stykker, har den rigtige form til passer sammen med hinanden. PUBLIKUM: Temmelig meget, ja. SPEAKER: OK, fremragende. Og nu hver af disse bunker formentlig sorteret? Publikum: Ja. SPEAKER: Okay, A til Z. Alle højre, tillykke, du gjorde det. Du har dit valg. Blue? Okay, tak for det. Så Mary Beth har foreslået hvad hendes tilgang var, men hvad er en anden tilgang, hvordan du måske gå om sortering disse ting? Hvad ville du have gjort? Pladen at slå ville have været et minut og 50 sekunder eller deromkring, plus dem, jeg glemte at tælle. Hvad ville du have gjort? Ja? PUBLIKUM: Tag stakken. Start fra begyndelsen. Tjek dine papirer. Og hvis den øverste er højere end, måske, de er, den nederste er højere, og derefter skifte dem. SPEAKER: OK, så starter ved toppen og bunden, og derefter arbejde din vej indad sådan, bytte dem? OK, så en lidt lignende i ånden at boble sortere, men at vælge ekstremer ikke de tilstødende par. Men korte af det er, at der er sikkert en masse forskellige måder vi kunne gøre dette, og helt ærligt, jeg tror, ​​du slags vedtaget et par tilgange, right? Du gjorde slags fire sorterede bunker, og så effektivt fusioneret dem sammen. Og det er, daresay, en anden teknik helt. Du har ikke behandle det som en stor bunke, du delte problemet i fire quads, hvis du vil, og derefter en eller anden måde fusioneret dem i sidste ende. Så lad os overveje, i sidste ende, hvordan vi ellers kan gøre dette. Vi formaliseret begrebet boble slags sidste gang, og boble sortere tilbagekaldelse var en algoritme, vi visualiseret med otte af dine klassekammerater op her, tilsyneladende tilfældigt sorteres først. Og vi besluttede derefter parvis, hvis to elementer er ude af drift, simpelthen bytte dem. Så fire og to er naturligvis ud af orden, Så dem to klassekammerater skiftet position. Og så har vi gentaget med fire og seks, derefter seks og otte på hver iteration bevæger sig til højre. Så givet otte personer, hvor mange parvise sammenligninger gjorde jeg, mens du går fra venstre til højre i en sådan iteration? Hvor mange sammenligninger? Syv, right? For hvis der er otte mennesker, men du har parret dem, og du holder bevægelse en hop til højre, du kommer ikke til at have otte sammenligninger, fordi du kan ikke sammenligne et element mod sig selv, eller det ville bare være meningsløst, så du har syv. Eller mere generelt, hvis vi har n mennesker, vi gøre n minus 1 sammenligninger med boble slags. Så lad os nu overveje, hvor god eller dårlig boble sortere faktisk var, og prøv at give os selv ordforråd med som til kritik algoritmer som denne, og snart vores egen. Så den første passage gennem boble sortere, første gang Jeg gik fra venstre til højre på tværs af stadium, tog mig n minus 1 sammenligninger. Og det kommer til at være min måleenhed, right? Jeg var slags taler og spadsereture, noget hurtigt, lidt langsom, så tælle mit antal sekunder er ikke specielt at fortælle, men at tælle antallet af operationer, som jeg gjorde i mandags, sammenligne to mennesker, der føler sig ligesom en nice måleenhed. Så n minus 1 trin for første gang, men hvad skete der efter det? Hvad er den ene på hovedet af en pass gennem en ellers usorteret liste? Hvad kan du fortælle mig om elementet der var hele vejen derovre? Ja? Det var den største element, right? Nummer otte, selvom hun startede her, hver gang jeg sammenlignet hende imod en nabo, hun holdt bobler op til højre side af listen. Og ja, det er her, algoritmen får sit navn. Nu ved denne logik, hvor mange sammenligninger behøver jeg gøre på anden gang Jeg gør, at bolden fra venstre mod højre? n minus 2, højre? Det ville bare være spild af min tid, hvis jeg holde sammenligne otte mod nogen andet fordi vi allerede kender Hun var på det rigtige sted. Så det er lidt af en optimering, så den næste linie vil være plus n minus to trin, hvor n er antallet af personer. Nu kan du slags ekstrapolere, selv hvis du ikke er en datalog, hvordan det ender. Ved afslutningen af ​​denne algoritme, formentlig du har bare en sammenligning venstre. Du er nødt til at slags fastsætte starten af ​​listen i tilfælde to og en er ude af drift og bør være et og to, så dette når bunden på plus 1 endelige sammenligning. Nu prik, prik, prik slags bølger, det er hænder på nogle af de juicier detaljer men lad os bare gå videre og forenkle. Hvis du husker fra høj skole, helt ærligt, en masse af jer havde matematik bøger, der havde lidt bedrager ark på forsiden eller bagsiden, der viste dig hvad serien summationer som dette i sidste ende lægges op til. I det generelle tilfælde, hvis du har en variabel ligesom n, og faktisk denne ene, hvis du har kigget på din old school matematik bog, vil du se, at dette faktisk tilføjer op til dette beløb her, n gange n minus 1 alle divideres med 2. Så lad mig nu bare fastsætte dette er sandt, så på et spring af tro, det er, hvad dette opsummerer op til, og vi kunne bevise, at en mere generelle tilfælde. Men lad os nu udvide denne ud. Så lad os multipliceres ud, så det er n kvadreret minus n, alle divideres med 2. Det er virkelig n kvadreret, divideret med 2, minus n over 2, så det er alle nice og interessant. Men hvad sker der, hvis vi nu plug-in en værdi? Antag jeg ikke har otte folk, men siger en million. Og en million bare fordi det er en temmelig stor antal, lad os sætte det i og se hvad der sker. Så hvis jeg sætte en million ind i denne formel Jeg har tænkt mig at få en million kvadreret, divideret med 2, minus en millioner, divideres med 2. Hvad er nu det kommer til at være lig? Så 500 milliarder, minus 500.000. Og hvis jeg rent faktisk gør at matematik, betyder at sortere en million folk med boblen slags kan tage mig 499999500000 trin eller sammenligninger i sidste ende, vi bare ekstrapolere. Det føles temmelig langsomme, men helt ærligt måle en bestemt indgang som dette, er det ikke alle, der fortæller. Men faktisk det antyder, at n bliver større og større, denne algoritme slags føles værre og værre, eller du virkelig begynder at føle smerten ved det eksponentiation, at n kvadreret, som tilføjer op temmelig hurtigt. Og denne detalje er ikke tabt på mennesker, i virkeligheden for nogle år siden en vis senator, der var kampagner, sad til et interview med Googles Eric Schmidt, administrerende direktør på det tidspunkt, og blev udfordret med et spørgsmål ligesom vi udforsker i dag. Lad os tage et kig. [VIDEOAFSPILNING] Senator, du er her på Google, og jeg kan lide at tænke på formandskabet som en jobsamtale. Nu er det svært at få et job som præsident, og du går igennem strabadserne nu. Det er også svært at få et job hos Google. Vi har spørgsmål, og vi spørger vores kandidater spørgsmål, og dette er fra Larry Schwimmer. Hvad-- du fyre tror jeg kidding, det er lige her. Hvad er den mest effektive måde at sortere en million 32-bit heltal? Jae-- Jeg er ked af, maybe-- Nej, nej, nej. Jeg tror boblen slags ville være den forkerte vej at gå. Kom nu, der fortalte ham det? Jeg kunne ikke se computer videnskab i din baggrund. -Vi Fik vores spioner derinde. -OK, Lad os bede en anden interview spørgsmål. [END VIDEO PLAYBACK] SPEAKER: Så taler om bestemte numre selv, kommer ikke til at være alt det nyttigt. Det er ikke et liv lektion, boble art, givet en million indgange, kan tage så mange som 500 milliarder trin. Du kan ikke rigtig generalisere også effektivt fra at og gøre gode design beslutninger når du skriver programmer. Så lad os fokusere dog på, hvordan vi måske forenkle dette resultat. Så jeg har markeret med gult her resultatet af n squared divideres med 2, så en million kvadreret divideret med 2 og derefter Jeg har fremhævet, hvad det ultimative svar var når vi trækkes væk n divideres med 2. Og påstanden jeg har tænkt mig at gøre nu, er, hvem dælen bekymrer sig hvis du trækker ud lidt gammel n over 2, da den første en del af denne formel er så meget større? Det dominerer den anden sigt n kvadreret divideret med 2 er så meget større, klart, som n bliver stor som en million, der er der virkelig en stor forskel på slutningen af ​​dag mellem 500 milliarder og 499.999.500.000? Ikke rigtig. Og så hvad vi kommer til at gøre som dataloger er ignorere disse lavere ordens led og tage noget som dette og virkelig bare forenkle det til begreb, der kommer til at ligegyldigt. De større vores datasæt får, jo større vores databaser får, jo flere websider vi nødt til at søge, jo mere venner du har på Facebook. Som n bliver større, er vi virkelig kommer til at bekymre sig om den største sigt i en sådan analyse af vores algoritmer ydeevne. Og jeg har tænkt mig at sige, ved du hvad, boble slags er på rækkefølgen af ​​store O, af størrelsesordenen n potens. Det er ikke ligefrem n kvadreret, som vi har set, men hvem virkelig bekymrer om disse mindre vilkår, og helt ærligt, der virkelig bekymrer sig hvis vi dividere med 2? Det er bare en konstant faktor. Og er 500 milliarder versus 250 milliarder virkelig så stor en deal? Jeg kunne bare vente et år lad min laptop bogstaveligt få dobbelt så hurtigt i hardware, og den slags forskel bare går væk naturligt over tid. Hvad vi bekymrer os om, er Udtrykket den del af det udtryk, der kommer til at variere som vores input bliver større og større. Og ja, i den virkelige verden, det er hvad der sker i stigende grad er input til vores problemer og algoritmer bliver større. Så stor O vil være den notation, den asymptotiske notation, at vi bare bruge som dataloger til at beskrive ydeevne, eller køretiden, af en algoritme. For at vi kan sammenligne algoritmer på forskellige computere skriftlige af forskellige mennesker, ved hjælp af nogle fundamentalt lignende metrisk ligesom antallet af sammenligninger, du er gør, eller måske antallet af swaps du laver. Hvad vi ikke kommer til at tæller er den mængde tid der passerer på uret på væggen typisk. Hvad vi ikke kommer til at bekymre sig om, er, hvor meget hukommelse du bruger i dag på mindste, selv om det er en anden ressource, vi kan måle. Vi vil forsøge at basere vores analyser på netop de grundlæggende operationer, dem, helt ærligt, at du kan se mest visuelt. Så med noget stort O n kvadreret, jeg hævder, at O ​​n kvadreret er en øvre grænse for den såkaldte køretid boble slags. Med andre ord, hvis du ønskede at hævde, at der er denne øvre grænse for, hvor mange skridt en algoritme kan tage, det kommer til at være i den store O af n kvadreret i dette tilfælde en øvre grænse. Hvad hvis jeg i stedet skifte historie ikke at være omkring boble sortere, men om denne øvre grænse. Kan du tænke på en algoritme at vi har kigget på allerede hvis øvre grænse, maksimum måle tid eller operationer, ville siges at være afgrænset med n, en lineær funktion, ikke en kvadratisk en, der er buet? Hvad er en algoritme, der altid tager ikke mere end lignende n trin, eller 2n trin eller 3n Steps? Ja? PUBLIKUM: at finde den højeste antal på en liste? SPEAKER: Perfekt, finde det største antal på en liste. Hvis jeg får en liste over folk for eksempel, hver, der holder et nummer, hvad der er det maksimale antal skridt det skal tage mig, et rimeligt smart person, at finde den største person i det liste? n, right? Fordi der i værste tilfælde, hvor måske den største værdi være? Højre, hele vejen i slutningen. Så i værste fald øvre grænse, kan jeg nødt til at gå hele vejen herover og være ligesom, åh, her er nummer otte, eller hvad denne værdi er. Nu vil det bare være dumt hvis jeg holdt hen, ikke? Leder du efter flere og flere elementer hvis den sidste af dem er derovre? Så sikkert, n er en øvre grænse. Jeg behøver ikke at tage flere trin end det. Så hvad nu hvis jeg i stedet foreslået, at der er algoritmer i denne verden, har en køretid, der er afgrænset af store O log n log n? Hvor har vi set det før? Ja? Publikum: I telefonbogen problemet? SPEAKER: Ligesom telefonbogen problemet. Hvad var mål for, hvor meget tid eller hvor mange tårer it Tog mig med at finde en person som Mike Smith i telefonbogen? Vi hævdede det var logn, og selvom ukendt, eller det er det lidt diset, hvad en logaritmen eller eksponent var bare huske, at log n generelt henviser til den proces, i dette tilfælde, at opdele noget i halve igen, og igen, og igen og igen, således at det får stadig mindre, som du gør det. Så log af n henviser til, sikker, til telefonbogen eksempel, til søgning binær i teorien, når vi havde de virtuelle døre på tavlen, eller når var Sean søger efter noget. Hvis han havde brugt binær søgning, log n ville være den øvre grænse for, hvor meget tid, der tager. Men de algoritmer, der kørte i log n antaget hvad nøgle detalje? At listen blev sorteret, right? Din algoritme er forkert, hvis Deres input er ikke sorteret, og alligevel du bruger noget binær søgning fordi du måske hoppe lige over elementet uden at vide det er faktisk der. Nu, hvad kan dette betyde, store O i en? Dette betyder ikke, at din algoritme tager en og kun et trin, det betyder bare, det tager en konstant antal trin. Måske er det 1, måske er det 10, måske er det 1.000, men det er uafhængigt af størrelsen af ​​problemet. Ligegyldigt hvor stor n er, en konstant tid algoritme altid har samme antal trin. Så hvad kunne være en algoritme vi har talt om eller bare intuitivt, der kommer til dig, at altid kører i såkaldt konstant tid? Ja? Publikum: Læg to numre. SPEAKER: Add to tal, 2 plus 2 er lig med 4, gjort. Så der kan arbejde, hvad ellers? Hvad med mere virkelige verden, ikke? PUBLIKUM: at finde den første ting på en liste. SPEAKER: at finde den første element i en liste, sikker. Vi har faktisk talt om arrays allerede hvordan får du på første element i et array, uanset hvor længe den array er i C-kode? Du skal bare bruge ligesom beslaget nul notation, bam, du er der. Og ja arrays, som en sidebemærkning, støtte noget almindeligt kendt tilfældig adgang, random access hukommelse, fordi du kan bogstavelig talt springe til en hvilken som helst sted. Vi kan gøre det endnu mere enkelt vi kan spole tilbage til uge nul når vi gjorde Scratch. Hvor lang tid tog det for sige blok i Scratch til at udføre? Bare konstant tid, ikke? Sig noget, siger noget, betyder det ikke noget Hvor stor Ridser verden er, er det altid kommer til at tage den samme mængde tid simpelthen at sige noget. Så det er konstant tid, men hvad er flip side? Hvis det var øvre grænser, hvad hvis vi vil at beskrive de nedre grænser af vores algoritmer køretid? Næsten en bedste fald potentielt, om man vil, om disse vilkår kunne gælde for bedst sager, værste tilfælde, gennemsnitlige tilfælde mere generelt, men lad os bare fokusere på nedre grænser mere generelt. Hvad er en algoritme, der har en nedre grænse af n trin, eller 2n trin eller 3n Steps? Nogle faktor n trin, det er dens nedre grænse. Ja? PUBLIKUM: boble slags? SPEAKER: boble slags tager du minimalt n trin, hvorfor? Hvorfor er det? Hvorfor skulle der begynder at komme til dig intuitivt, selv om det ikke bare endnu? Ja? Publikum: [uhørligt]. SPEAKER: Præcis. I det bedst mulige scenario boble slags, og en masse af algoritmer, hvis jeg giver dig otte personer som allerede er sorteret, det ville være tåbeligt for dig, den algoritme, at gå frem og tilbage mere end én gang, ikke? Fordi så snart du gå gennem listen én gang, du bør indse, åh, gjorde jeg ikke swaps, er denne liste sorteres, exit. Men det kommer til at tage dig n trin. Og omvendt, hvad er en anden måde at tænke om det? Bubble slags er en omega, så at sige, af n, fordi hvis man ser på færre end n elementer, hvad er det grundlæggende spørgsmål der? Du ved ikke, om det er sorteret, højre. Vi mennesker måske blik på otte mennesker og være ligesom, åh, det er sorteret, som ikke tage mig n trin, men det gjorde. Dine øjne, selvom du slags af har et stort synsfelt, du kiggede på otte elementer, du kiggede på otte personer, der er otte trin effektivt. Og kun hvis jeg går gennem hele liste gør jeg indser, ja, sorteres. Hvis jeg stopper halvvejs tænker alle højre, det er temmelig sorteres hidtil, Hvad er oddsene det ikke sorteres? Det algoritmer vil ikke være korrekt. Kunne være hurtigere, men forkert. Så nu har vi en måde at beskriver en nedre grænser, og hvad med konstant tid? Hvad er en algoritme, der har en lavere bundet på sin køretid på én? 1 trin 2 trin, 10 trin, men konstant, uafhængig af n størrelsen af ​​input? Ja, i ryggen. Publikum: printf? SPEAKER: Hvad er det? Publikum: printf? SPEAKER: printf. OK, helt sikkert. Så det tager et fast antal trin. Og jeg skulle nu-- nu, vi taler om C-kode og ikke Scratch, noget ligesom sige, med printf, vi skal begynde at få forsigtig. Fordi printf tager input, det er en streng, og strygere har teknisk har længde. Så hvis vi nu ønsker at plukke på dig, hvis du ikke har noget imod, teknisk kunne vi argumentere for, at printf tager en variabel længde-indgang, og sikkert det kan tage mere tid til at udskrive en streng denne lange, end denne lange. Så hvad nu hvis vi betragter bare sortering og søgning eksempler? Hvad med Mike Smith i telefonen bog, eller binær søgning mere generelt? I bedste fald, hvad der kan ske? Jeg åbne telefonbogen, og bam, der er Mike Smiths nummer. Jeg kan ringe til ham med det samme. Tog et skridt, måske to trin, men et konstant antal af trin hvis jeg fik heldig. Og helt ærligt, vi så på Mandag din klassekammerat få ganske heldig to gange i træk. Og det var faktisk konstant tid i et nedre grænser på algoritmen pågældende til at finde nummer 50 bag de lukkede døre. Nu, som en sidebemærkning, hvis du opdager at både store O, den øvre grænse, og omega, den nedre grænse, er en i samme, er den samme formel parenteser, kan du også sige, bare for at være smarte, at noget er i theta n eller theta af en anden værdi. Det betyder bare, når store O og omega er de samme. Nu hvad udvælgelse slags? Lad os bruge denne nye ordforråd. I udvælgelsen sortere, hvad vi var gør igen og igen, og igen? Jeg gik frem og tilbage gennem listen, på udkig efter hvem? Det mindste antal. Så hvordan mange trin, hvordan mange sammenligninger gjorde jeg nødt til at gøre for at finde ud af hvem det mindste element i listen var? n minus 1, højre? Fordi hvis jeg bare starte med det ene er jeg givet, og jeg begynder at sammenligne ham eller hende, så ham eller hende, ham eller hende, ham eller hende, jeg kan kun parre elementer sammen n minus 1 gange. Så udvælgelse sortere på samme måde tager n minus 1 trin første gang. Hvor mange skridt tager det mig til finde den næstmindste element? n minus 2, fordi jeg er dum hvis jeg bliver ved med at kigge på de samme mennesker igen, hvis jeg allerede har valgt ham eller hende, og sætte dem i deres sted. Og det tredje trin, n minus 3 og derefter n minus 4. Vi har set dette mønster før, og faktisk udvælgelse sortere på samme måde har en øvre grænse n kvadreret hvis vi gør op, at summation. Hvad er dens nedre grænse, udvælgelse slags? Minimalt, hvor meget tid skal udvælgelsen sortere tage, som vi definerede det på mandag? Foreslå to muligheder. Måske er det n, som før. Måske er det n kvadreret, da det er nu som den øvre grænse. PUBLIKUM: n potens. SPEAKER: n potens. Hvorfor? Publikum: Fordi du har at definere [uhørligt]. SPEAKER: Præcis. Mindst lige så jeg definerede udvælgelse slags det var temmelig naiv, holde i gang, finde det mindste element. Gå igen, finde det mindste element. Gå igen, finde det mindste element. Der er ingen form for optimering i der, kunne lade mig afbryde efter bare n eller så trin. Så ja, udvælgelse sortere, omega n potens. Hvad med indsættelse slags, hvor jeg tog hvem jeg fik, og så smed jeg ham eller hende i det rigtige sted? Derefter fortsatte jeg til den anden person, smed ham eller hende i det rigtige sted. Så den næste person, smed ham eller hende i det rigtige sted. Bemærk at dette er meget lineære, så at sige. Jeg er en lige linje, er jeg ikke gå frem og tilbage, Jeg har aldrig ser tilbage virkelig, men hvad der sker, når jeg sætter ham eller hende ind i begyndelsen af listen som vi gjorde på mandag? Hvad sker der? Ja? Publikum: [uhørligt]. SPEAKER: Ja, det var fangsten, right? Du husker muligvis fra dine klassekammerater, hvis de gjorde enhver bevægelse med deres fødder, det var en operation. Så hvis der var tre mennesker her og den nye person tilhørte vej derovre, på en lang scene som denne, sikker, han eller hun kunne bare gå til den bitre ende. Men hvis vi tænker på en computer og en vifte af hukommelse, disse mennesker går nødt til at blande i at gøre plads til denne person. Og så at n minus 1 shufflings, n minus 2 shufflings n minus 3 shufflings er lige slags sker bag mig, ikke foran mig som før, i en vis forstand. Nu som en sidebemærkning, og som du måske har set online hvis du begynder at rode rundt omkring sorterer, der er så mange forskellige dem derude, nogle af dem bedre end andre. Faktisk bogosort er en det er lidt sjovt at se op. Bogosort tager et sæt af tal eller sige et spil kort, tilfældigt blander dem, og kontrollerer, om de er sorteret. Og hvis ikke, gør det igen. Og hvis ikke, gør det igen. Hvis ikke, gør det igen. Utrolig dumt. Og ja, hvis du læse ligesom Wikipedia-artikel, sit øgenavn er dum slags. Det vil i sidste ende arbejde, forhåbentlig givet tilstrækkelig tid, men at mængden af ​​tid kunne tage temmelig lang tid. Så hvis jeg kunne, lad os fremskynde tingene op fra Mary Beth eksempel tidligere, ved at have et par flere elementer, men to processorer. To mennesker, hvis du ville ikke have noget imod at tilslutte mig. Hvordan omkring 1 herovre, og lad os go-- ingen derovre? Ingen derovre? OK. Du med den sorte skjorte, ja, kom nu ned. Okay, hvad er dit navn? Publikum: Peter. SPEAKER: Hvad er det? Publikum: Peter. SPEAKER: Peter, David, rart at møde dig. Okay, vi har Peter her, hvis du ønsker at komme på bordet herovre. Og hvad er dit navn? Publikum: Elena. SPEAKER: Elena. OK, rart at møde dig. Elena mødes Peter. Peter Elena. Og vi har brug for Andrew heroppe så godt, tak. Og din udfordring går at være at sortere et spil kort. Og hvis uvant, dæk kort skal i sidste ende sorteres lidt noget lignende dette, hvor vi vil gøre klubberne, så de spader, så hjerter og diamanter, fra es som én, hele vejen op til kongen. De kort, jeg har tænkt mig at give dig vil være 52 i mængde. Vi kommer til på samme måde gang du, på bare et øjeblik. Vi kommer til at kaste Andrew op på skærmen her, så at se på som du gør dette. Og så, at alt dette er desto mere synlige, det er de kort, jeg fik på Amazon. Så de er allerede tilfældigt sorteret, og vi vil gang du. Og vi vil holde det reelle denne gang, så vi vil forsøge at lægge pres på dig fordi ellers vil det få kedelige hurtigt. Hvis du kunne gå til at sortere 52 elementer sammen via nogle midler, nu. Og igen, som vi ser disse fyre gør, hvad der i sidste ende vil producere en indlysende resultat, så tænk virkelig hvordan de hver gør det, hvordan du kan beskrive det. Fordi igen, disse er alle processer, algoritmer at vi tager for givet som et menneske. Men du har sikkert længe haft intuition, længe før du selv tænkt på at tage et datalogi klasse du kunne have haft intuitionen med som at løse problemer som dette. Men når du genkende mønstrene og begynde at formalisere de skridt, med hvilke du at løse disse problemer, du opdage, at du kan løse meget mere interessant og meget mere kompleks problemer hurtigt. Så nogen fra publikum, hvad er mindst et element af algoritmen at de bruger her? Publikum: [uhørligt] SPEAKER: Hvad er det? Publikum: efter kulør. SPEAKER: efter kulør. Så først de clustering alle de diamanter sammen det synes alle hjerter sammen det ser ud, og så videre, uden hensyn til numrene på kortene. Og nu de ser, for eksempel, at sortere dem efter antal. Meget godt. Okay, så hvad der kommer til være det sidste skridt så her? Når vi har fire sorterede dragter, hvad skal vi gøre for at de fire bunker for at opnå en sorteres dæk, simpelthen? Så vi er nødt til at flette dem igen. Så der er en interessant idé, som igen, daresay, er meget intuitiv selv hvis du aldrig kunne have slået den slags mærkat på det. Denne grundlæggende opfattelse af at dividere problemet ikke i halvdelen af ​​denne tid, men i det mindste i fire stykker. Løsning temmelig meget fundamentalt identiske problemer i isolering af hinanden, og derefter sammenlægge resultaterne. Og fremragende, gjort. Okay, en stor rund bifald, hvis vi kunne. [Applaus] SPEAKER: Jeg har ingen idé om, hvad du vil gøre med disse, men her du går. Tak så meget. Så lad os se, to minutters og for otte sekunder, Hvis du gerne vil udfordre dine venner. Hvad er så gå til være en tage væk fra dette at vi kan udnytte mere generelt? Nå, tænker tilbage på denne række af tal, og tænker tilbage nu til nogle af de pseudokode vi har skrevet tidligere, og dette var pseudokode til løse telefonbogen problemet. Hvorved i pseudokode I opregnet en mere metodisk beskrive, hvordan jeg gjorde en meget intuitiv humant algoritme dividere telefonen bog i halve, gentag, gentag, gentag, indtil jeg finder en som Mike Smith, hvis han virkelig er i telefonbogen. Men jeg slags brugt, hvad jeg vil kalde en meget iterativ tilgang her, særlig meddelelse linje 8 og linie 11. Det er tegn på en iterativ tilgang, en looping tilgang, fordi det er præcis adfærd de inducerer. Disse linjer begge sige gå til linje tre, og du kan slags tænke på det i din indre øje som en løkke. Det fortæller dig at gå tilbage op til trin tre og gentage igen og igen, og igen. Men hvad nu, hvis vi udnytter en central idé her, vi gjorde ikke sidste gang, og forenkle linje 8 og linie 11 og deres naboer som netop dette, i gult. Det er ikke fundamentalt afkorte pseudokoden meget, men det er fundamentalt at ændre arten af ​​min algoritme. Hvad jeg nu siger i trin 7, i trin 10, er at søge efter Mike på præcis samme måde, men kun i den venstre halvdelen eller højre halvdel. Så med andre ord, hvis Jeg starter fra trin et, afhente telefonbog, åben for midten af telefonbogen, se på navnene, hvis Smith er blandt hedder, kalder Mike, ellers hvis Smith er tidligere i bogen, trin syv søge efter Mike i venstre halvdel af bogen. Men den slags føles det forlader mig hængende, ikke? I gul, er en instruktion, men hvordan gør jeg søge efter Mike i venstre halvdelen af ​​telefonbogen? Hvor har jeg en algoritme, som jeg kan søge efter en som Mike Smith? Tja, det er stirrer os i ansigtet. Jeg kan bogstaveligt talt bruge den nøjagtige samme program effektivt går op til toppen igen og re-drift de samme linjer kode. Så selv om dette skulle føle som lidt af en cyklisk definition hvor du svarer en persons spørgsmål ved bare slags spørger det samme spørgsmål igen, ligesom hvorfor, hvorfor, hvorfor? Virkeligheden er, fordi vi hårdt har kodet et par af særlige linjer, trin 4, der er en hvis, og trin 12, som er reelt en anden gren, fordi vi har disse lappeløsninger, denne algoritme vil ophøre, hvis vi finde Mike, eller hvis vi ikke gør det. Men i trin 7 og 10 nu, vi har hvad vi vil kalde en rekursiv algoritme. Og rekursion er faktisk en kraftfuld idé det er en lille sind bøjning først, at vi nu kan anvende som følger. Flet slags vil være den sidste slags, vi ser på, i det mindste i klassen formelt. Og det er fundamentalt anderledes fra de sidste tre, og bestemt sidste fire, hvis vi inkluderer bogosort. Her er pseudokode til sammenfletningen slags. Når på input af n elementer, så givet et array af størrelse n hvis n er mindre end 2, tilbage. Så hvorfor har jeg det tilregnelighed tjek først? Hvad er konsekvenserne, hvis jeg giver dig et array, hvis længde n er mindre end 2? Det er allerede sorteret, naturligvis, ikke? Fordi listen har enten et element, som er trivielt sorteres, fordi det er det eneste der. Eller, det er en størrelse nul, hvilket betyder, der er intet at sortere, så ved naturen det er sorteret. Der er bare ikke noget galt der. Så det er vores såkaldt base case. Det er ens i ånden til hvad vi gjorde med Mike. Hvis Mike i telefonbogen, ringe til ham. Hvis han ikke er der, give op. Det er en såkaldt base case, for at sikre denne algoritme i slutningen af ​​dagen vil stoppe i visse omstændigheder. Men her er det spring af tro nu, ellers, sortere den venstre halvdel af elementerne, derefter sortere det rigtige halvdelen af ​​de elementer, og derefter flette de sorterede halvdele. Og her er hvor det føles ligesom vi copping ud. Jeg har bedt dig om at sortere n elementer, og jeg er sige, OK, det ved at sortere venstre og sortering højre. Men jeg siger en andre ting, og det er det centralt tema ser det ud i intuition hidtil, der er denne tredje trin for at fusionere. Hvilke selvom det synes så dum i ånden, ligesom bare flette tingene sammen, ser det ud til at være et vigtigt skridt hen imod samling af to problemer, blev opdelt i sidste ende i halve. Så fusionere sortere, lad os gøre det, hvis du vil humor mig, med en mere demonstration, bare så vi har nogle numre til at arbejde med. Kan jeg udveksle otte stress kugler til otte personer? Okay, hvad med dig tre, du fire i dette afsnit, fem, seks, og lad os gør 7, 8, kom op. OK, ja OK. Minus 8, der går vi, plus 1. Fremragende. Okay kom op, lad os hurtigt give dig tal. Nummer to, nummer tre, nummer fire, nummer fem, seks, syv og otte. Jeg gjorde otte rigtigt denne gang. OK, så gå videre, hvis du kunne, og lad os sortere i den oprindelige rækkefølge at vi havde i går, som kiggede som dette, hvis du ikke har noget imod. Og lad os gøre det i foran af tabellen. Okay, så flette slags. Det er her, det går at få slags interessant, fordi jeg synes at give mig så meget mindre information dag. Så fusionere slags først på input af n elementer, og er naturligvis ikke mindre end to, det er otte, så jeg har nogle mere arbejde at gøre. Så nu mentalt vi som en klasse er nu i andet filial, hvilket betyder tre trin. Først vil jeg nødt til at sortere venstre halvdel af elementerne. Så hvordan kan jeg gå om at gøre dette? Nå, jeg har tænkt mig at slags mentalt opdele listen her, du behøver ikke at fysisk at bevæge sig, og jeg er går kun at fokusere på venstre halvdel af elementerne her. Så hvordan kan jeg gå om sortering en liste nu størrelse fire? Hvad er min algoritme? Først vil jeg kontrollere, er n mindre end to, nej, så jeg går videre til andet blok igen. Sorter forlod halvdelen af ​​elementer. Så nu igen, mentalt og det er her du er nødt til at optjene en masse mental historie, hvis du vil. Nu er jeg sortering venstre halvdelen af ​​den venstre halvdel. Okay, så nu kalder jeg min samme merge sorteringsalgoritme er n mindre end to? Nej, det er to, så jeg er nødt til at sortere den venstre halvdel og den højre halvdel. Så her vi går, sortere venstre halvdel. Hvorfor gør du ikke bare tage et skridt fremad. Hvad er dit navn? Publikum: Darren. SPEAKER: Dan. Dan har trådt frem. Publikum: Darren. SPEAKER: Darren, gjort. Sagde du Darren eller Dan? Publikum: Darren. SPEAKER: Darren. OK, Darren er trådt frem og han nu sorteres. Og det er næsten en åndsforladt krav, right? Jeg kan ikke rigtig synes at være at opnå noget, men lad os fortsætte. Lad mig nu sortere ret halvdelen af ​​elementerne. Hvad er dit navn? Publikum: Luke. SPEAKER: Luke. Kom, træd frem. Udført, har jeg ordnet Luke. Den venstre halvdel er nu sorteret og højre halvdel er nu sorteret, men igen, der er et vigtigt skridt her. Hvad gør jeg næste skal gøre? Flet de sorterede halvdele. Nu vil vi bare have alle frem og tilbage på denne måde, fordi jeg slags brug nogle bunden plads. Det er næsten ligesom disse fyre er på et bord, og jeg har brug for lidt plads at flytte dem rundt på. Så jeg har tænkt mig at fusionere jer ved at se på den venstre halvdel og den højre halvdel. Og der naturligvis kommer først, venstre halvdel eller højre halvdel? Så lige halvdel, så lad os gå Luke løbet her til Darren oprindelige holdning. Og nu at fusionere deres venstre halvdel i, Darren kommer til at bevæge sig lige der. Så føles næsten en boble slags effekt, men min grundlæggende algoritme, meget anderledes denne gang. Men nu er, hvor tingene bliver lidt irriterende, fordi du nødt til at spole tilbage mentalt hvor har jeg forlader slukket. Jeg har netop fusioneret de sorterede halvdele, hvilket betyder, at jeg er, hvor i min algoritme? Jeg er nødt til at sortere den højre halvdel, højre? Hvis du spole tilbage, bogstaveligt på videoen, vil du se, at vi fik til dette punkt i Lukas og Darren ved at sortere venstre halvdelen af ​​den venstre halvdel. Så vi fusionerede dem sorterede halvdele, som betyder, at næste skridt er sortere højre halvdel af den venstre halvdel. Okay, så lad os gøre dette hurtigere. Okay, seks, vil jeg hævde, du er nu sorteret, kom frem. Hvad er dit navn? Publikum: Adriano. SPEAKER: Adriano. Adriano er nu sorteret. Og hvad er dit navn? Publikum: Alex. SPEAKER: Alex er nu sorteret. Venstre halvdel, højre halvdel, hvad er det sidste skridt? Flet. Temmelig triviel, så jeg er kommer til at fusionere i seks, tage et skridt tilbage, otte, tage et skridt tilbage. Og nu bemærke dette er en nyttig takeaway, hvad nu er sandt om den venstre halvdel af liste, uanset hvordan vi begyndte? Det er sorteret. Nu er det ikke sorteret i det store arrangement med ting, men det er sorteret uafhængigt på den anden halvdel. Nu, hvad skridt er jeg på, hvis jeg holder tilbagespoling, hvordan historien begyndte? Nu er jeg nødt til at sortere den højre halvdel. Så nu er vi tilbage ved I begyndelsen af ​​historien, og lad os gøre det hurtigere. Så jeg har tænkt mig at sortere højre halvdel af hele listen. Hvad er næste skridt? Sorter venstre halvdel af den højre halvdel. Sorter venstre halvdel af venstre halvdel af den højre halvdel. Og hvad er dit navn? Publikum: Omar. SPEAKER: Omar, gå frem, gjort. Venstre halvdel er sorteret. Og hvad er dit navn? Publikum: Chris. SPEAKER: Chris, tage et skridt fremad, er du nu sorteres. Hvad er det afgørende skridt nu? Flet. Så man kommer til at fusionere på plads her, hvis du kunne tage et skridt tilbage, og tre vil tage et skridt tilbage, flette. Så den venstre halvdel af højre halvdel er nu sorteret. Helt ærligt, denne algoritme føles som vi spilder måde mere tid end før, men hvis vi gjorde dette i realtid, vil vi se, hvad grillbarer kommer til at være. Nu her er jeg, lige halvdel af den højre halvdel, lad mig gå videre og sortere den venstre halvdel. Træd frem, hvad er dit navn? Publikum: Ramsey. SPEAKER: Ramsey er nu sorteret. Hvad er dit navn? Publikum: Marina. SPEAKER: Marina er nu sorteres som godt, hvis du tager et skridt fremad. Key skridt her er nu fusionere, er jeg kommer til at plukke fra mine to lister, venstre og højre. Fem vil komme først, og syv vil komme næste. Og igen, det er bevidst. Det faktum, at de tager skridt frem og tilbage menes at repræsentere, at vi ikke kan gøre denne algoritme på plads så let som boble sortere, og udvælgelse sortere, og indsættelse slags, hvor vi bare holdt swapping mennesker. Jeg bogstaveligt talt har brug for en slags af bunden papir, hvor at sætte disse folk mens jeg gør det sammenlægning og så kan jeg sætte dem på plads igen. Og det er afgørende, fordi jeg bruger en ny ressource, rum, ikke blot tid. OK, det er forbløffende. Venstre halvdel er sorteret, højre halvdel er sorteret, nu hvor nøglen fusionerende trin. Hvordan skal jeg nu til at flette dette? Så hvis du vil følge mit venstre hånd og højre hånd, Jeg har tænkt mig at pege min venstre hånd på den venstre halvdel, min højre hånd på den højre halvdel, og nu har jeg til beslutte skridt for skridt, hvem de skal fusionere i. Der naturligvis kommer først? Nummer et. Så kom her over, her er vores notesblok. Så nu nummer et, og varsel hvad jeg vil gøre med min højre hånd, Jeg har tænkt mig at flytte min højre hånd en trin over til punkt nummer tre, og nu er jeg nødt til at gøre samme afgørelse. Og faktisk står til højre i foran Lukas her, hvis du kunne, fordi det er vores notesblok. Så hvem bliver det næste? Vi har Luke med nummer to eller Chris med nummer tre. Naturligvis Luke, nummer to, så du kommer her. Men min venstre hånd nu kommer til at øges til at pege på Darren, og her er nøglen tage væk med sammenlægning, vil jeg fortsætte med at gøre dette, selvfølgelig, hvis du slags af følge logikken. Men mine hænder er aldrig kommer til at gå baglæns, hvilket betyder, at jeg kun nogensinde flytter til venstre med min sammenlægning proces, og det kommer til at være nøglen til vores analyse på bare et øjeblik. Så lad os nu afslutte dette op hurtigt. Så tre kommer næste, derefter kommer fire næste, og nu fem kommer næste, så seks, og syv, og derefter endelig otte. Føles som den langsomste algoritme endnu, men ikke hvis vi faktisk køre det på samme slags af clock hastighed, så at tale, med samme tikkende ur som før. Hvorfor? Nå, lad os tage et se på slutresultatet. Lad os gå tilbage herovre, lad mig trække op en demonstration visuelt af, hvad vi lige gjorde. Zoomer ind her, på dette side her, fortæller Firefox at vi ønsker at stå i kø op i denne rubrik, lad os sige boble slags, med hvilke vi er nu godt bekendt, udvælgelse slags, som er en anden forholdsvis ligetil, og nu dagens fusionere slags, som vil være vores klimaks slutning. Grunden til at det tog så meget længere her med mennesker og mig verbalt er, selvfølgelig, jeg forklare hvert skridt. Men hvis du blot udføre dette, meget ligesom vi gjorde boble sortere og udvælgelse sortere ikke kun visuelt, ur hvor meget mere effektivt denne gearing af division og erobre kan, når den anvendes på et datasæt, der er ikke engang størrelse otte, men selv meget, meget større. Jeg giver dig flette sortere, ved siden af side med disse andre algoritmer. Dette kommer til at få smertefulde hurtigt, og slutter er ikke særlig klimatiske, de bare ender sorteres. Men nøglen tage væk, er, at se hvor meget hurtigere fusionere slags var, medmindre du tror, ​​jeg er bare lidt for at rode med dig. Hvis vi gør det en sidste gang, lad os genindlæse dette, lad os gå tilbage og vælg boble sortere, og bare for sjov, Lad os vælge indsættelse sortere, bare for god foranstaltning. Og denne gang igen, lad os vælg Merge sortere og lad os faktisk køre disse side om side. Og det er ikke i virkeligheden et lykketræf. Hvad jeg har faktisk gjort, er jeg har delte mit input i halve, igen, og igen og igen. Og der er kun så mange gange du kan opdele dit input i to halvdele, venstre og højre. Hvad er den formel, vi bliver ved med at der beskriver opdelingen i halve igen og igen, og igen og igen? PUBLIKUM: Log n. SPEAKER: log n. Men så er der en anden afgørende skridt, denne algoritme er ikke log n trin. Hvis det kun var log n trin, vi ville være i det samme problem som før, hvor vi ikke kan være at alt er ordnet. Du er nødt til minimalt at se på n elementer at være sikker på n elementer er sorteret, ellers er det et spring af tro. Så det er minimalt log n trin, men hvad med denne nøgle sammenlægning trin hvor jeg fusionerede min venstre halvdel og højre halvdelen og gik på tværs af scenen? Hvor mange skridt er, at samle? Det er n, men jeg gjorde ikke bare fusionere sidste gang. På hver af disse indlejrede opkald på hver af disse indlejrede fusionerer, jeg stadig sorteres. Jeg slået disse to fyre, så disse to gutter, så disse to fyre og så videre. Så jeg gjorde fusionere igen og igen. Hvor mange gange? Så hver gang jeg delte liste i halve, jeg gjorde en sammenfletning. Opdel listen i halve, gøre en sammenfletning. Så hvis dividere liste kan gøres log n gange, og sammenlægning i sidste ende tager n trin, hvad der nu er den øverste bundet på driften tidspunktet for vores algoritme? n log n. Og ja, det er hvad vi har opnået her. Så de føler, at du ser visuelt når de tre ting køre side om side er n kvadreret mod n kvadreret mod n log n. Der grundlæggende vil vi se, ikke kun i dag, men i fremtiden, er meget, meget hurtigere. En runde af bifald for disse fyre, Jeg vil belønne dem med stress bolde. Lad os udsætte her i dag, og vi vil se dig på mandag.