SPEAKER: Greit, dette er CS50. Dette er slutten av uke tre, og hvis du ikke har utnyttet allerede, vet at det vil være lunsj denne fredagen som vanlig, der du kan nyte god samtale og mat på Fire and Ice med noen av CS50 sin ansatte og klassekamerater. Hodet til denne nettadressen her. Nå kan du husker, eller du kan snart bli kjent med, disse tingene her, som gis ut på slutten av semesteret i mange klasser. Såkalt eksamen blå bøker, der du skriver svarene dine til eksamen. Nå har jeg her 26 slike blå bøker, på hver av dem er skrevet et navn, A til Z. Og faktisk navnene er så enkelt, A gjennom Z. Og en av målene for hånden i dag kommer til å være å fortsette det vi startet på mandag, som ikke er så mye å se på koden, men egentlig ser på ideer og problemløsning. Ett av målene og løfter om dette kurset er å lære deg å tenke mer nøye, mer metodisk, og å løse problemer mer effektivt. Og ja, vi kan gjøre som virkelig uten engang å berøre en linje med kode. Så jeg har et par elefanter opp her i dag, oransje og blått, hvis vi kunne få en frivillig, kanskje fra lenger tilbake enn vanlig. Hva med akkurat der, komme ned. Målet med som kommer til å være til hjelpe pluss administrere denne eksamen her. Hva heter du? PUBLIKUM: Mary Beth. SPEAKER: Mary Beth, kom opp. La meg få mikrofonen her for deg. Hyggelig å møte deg. PUBLIKUM: Hyggelig å møte deg. SPEAKER: Ok, så jeg har her blå bøker A til Z, og jeg kommer til å late som Jeg har en av studentene, og de kommer i litt tilfeldig ved slutten av en tre timers undersøkelse blokk, slik at de ender opp i noen semi-tilfeldig rekkefølge som dette. Nå din jobb i bare et øyeblikk kommer å be-- dette er faktisk hvordan de får leverte i slutten av klassen, mest sannsynlig. Din jobb nå kommer til å være, ganske rett og slett, å sortere disse blå bøker for oss fra A til Z. PUBLIKUM: Å, dette er kommer til å ta en evighet. SPEAKER: Og vi vil se som du gjør dette, ikke noe press. PUBLIKUM: Nei, ikke noe press eller noe. SPEAKER: Og for moro skyld la oss sette opp en timer. PUBLIKUM: Så gøy, så gøy. SPEAKER: Jeg kan holde mikrofonen for deg. Greit, vi har bare doblet vår hastighet. Så i mellomtiden, la meg stille hva som er kommer til å være spørsmålet for Mary Beth er hva hun gjør, hvordan er hun går om å løse dette? Og faktisk, har du kanskje ikke noen gang tenkt på noe så enkelt som når du plukker opp 26 bøker som dette, som har en naturlig bestilling til dem. Hva er prosessen at du faktisk bruker? Er det ganske tilfeldig bare plukke den første du ser og setter det på sin plass? Har du først flytte hendene rundt På utkikk etter en så leter etter B? Vil du ta en titt på en par av dem ved siden av hverandre og bare si, vent litt, dette er ikke riktig, og deretter bytte den rekkefølgen? Vi så allerede på mandag at det er en rekke måter der vi kan gjøre dette, og faktisk som vi nærmer oss slutten her, Jeg ville ta notat kanskje av hva Mary Beth gjør. Vi har noen få hauger det virker, en større en, tre små. PUBLIKUM: Jeg beordrer dem når jeg finner to bokstaver at jeg vet er sammen i en sekvens, Jeg satte dem sammen slik at jeg ikke trenger å bekymre deg for å holde styr på en hel rad med bøker. Det er bare, oh, A er først, Jeg har fått denne bunken her. SPEAKER: Så, nesten som Et puslespill brikker som har rett form til matche opp med hverandre. PUBLIKUM: Ganske mye, ja. SPEAKER: OK, utmerket. Og nå hver av disse hauger er antagelig sortert? PUBLIKUM: Yeah. SPEAKER: Greit, A til Z. Alle høyre, gratulerer, du gjorde det. Du har ditt valg. Blue? Ok, takk for det. Så Mary Beth gjorde foreslå hva hennes tilnærming var, men hva er en annen tilnærming hvordan du kan gå om sortering disse tingene? Hva ville du ha gjort? Rekorden å slå ville ha vært ett minutt og 50 eller så sekunder, pluss de jeg glemte å telle. Hva ville du ha gjort? Yeah? PUBLIKUM: Ta bunken. Starte fra begynnelsen. Sjekk dine papirer. Og hvis det over er høyere enn, kanskje, er de, den nederste er høyere, deretter bytte dem. SPEAKER: OK, så starter øverst og nederst, og deretter jobbe din vei innover sånn, bytte dem? OK, så litt lignende i ånden til boble sortere, men velger ytterpunktene ikke de tilstøtende par. Men den korte av det, er at det finnes sikkert en haug med forskjellige måter vi kunne gjøre dette, og ærlig, jeg tror du slags vedtatt et par tilnærminger, ikke sant? Du gjorde liksom fire sorterte hauger, og så effektivt fusjonerte dem sammen. Og det er, påstår at en annen Teknikken helt. Du har ikke behandle det som en stor haug, du delt problemet inn i fire firehjulinger, om du vil, og deretter en eller annen måte fusjonerte dem til slutt. Så la oss vurdere, til slutt, hvordan annet vi kan gjøre dette. Vi formalisert begrepet boble slags siste gang, og boble slags tilbakekalling var en algoritme som vi visualisert med åtte av dine klassekamerater her oppe, tilsynelatende tilfeldig sortert først. Og vi deretter besluttet parvise, hvis to elementer er ute av drift, rett og slett bytte dem. Så fire og to er åpenbart ute av drift, så de to klassekamerater bytte posisjon. Og da har vi gjentatt med fire og seks, deretter seks og åtte, på hver iterasjon, beveger seg mot høyre. Så gitt åtte personer, hvor mange parvise sammenligninger gjorde jeg mens jeg gikk fra venstre til høyre i en iterasjon, for eksempel? Hvor mange sammenligninger? Seven, ikke sant? For hvis det er åtte folk, men du har paret dem, og du beveger deg ett hopp til høyre, du kommer ikke til å ha åtte sammenligninger, fordi du kan ikke sammenligne et element mot seg selv, eller det ville bare være meningsløst, så du har sju. Eller mer generelt, hvis vi har n mennesker, vi gjøre n minus 1 sammenligninger med boble slag. Så la oss vurdere nå hvor godt eller dårlig boble slags egentlig var, og prøv å gi oss selv vokabular med som til kritikk algoritmer som dette, og snart vår egen. Så den første går gjennom bobletype, første gang Jeg gikk fra venstre til høyre over scenen, tok meg n minus 1 sammenligninger. Og det kommer til å bli min måleenhet, ikke sant? Jeg var litt snakk og rusler, noe fort, noe treg, så teller min antall sekunder er ikke spesielt å fortelle, men telle antallet operasjoner som jeg gjorde på mandag, sammenligne to personer, mener at som en fin måleenhet. Så n minus 1 trinn første gang men så hva som skjedde etter det? Hva er en oppside på ett pass gjennom en ellers usortert liste? Hva kan du fortelle meg om elementet som var helt der borte? Yeah? Det var den største element, ikke sant? Nummer åtte, selv om hun startet her, hver gang jeg sammenlignet henne mot en nabo, holdt hun bobler opp til høyre side av listen. Og ja, det er der algoritmen har fått navnet sitt. Nå følger den logikken, hvor mange sammenligninger trenger jeg gjør på andre gang Jeg gjør at pasning fra venstre til høyre? n minus 2, ikke sant? Det ville bare være å kaste bort tiden min hvis jeg holde sammenligne åtte mot noen annet fordi vi allerede vet hun var på rett sted. Så det er litt av en optimalisering, slik at den neste ballen kommer til å være pluss n minus to trinn, der n er antall personer. Nå kan du slags ekstrapolere, selv hvis du ikke er en datamaskin vitenskapsmann, hvordan dette ender. Ved slutten av denne algoritmen, formodentlig du har bare én sammenligning venstre. Du må slags fikse begynnelsen av listen i tilfelle to og en er ute av rekkefølge og bør være en og to, så dette bunner ut på pluss en endelig sammenligning. Nå prikk, prikk, prikk slags bølger det er hendene på noen av de saftigere detaljer, men la oss bare gå videre og forenkle. Hvis du husker fra videregående skole, ærlig, mange av dere hadde mattebøker som hadde en liten jukselapp på frontdekselet eller bakdekselet som viste deg hva serien summeringer som dette til slutt lagt opp til. I det generelle tilfellet, hvis du har en variabel som n, og faktisk denne, hvis du så på din old school matte bok, du vil se at dette faktisk legger opp til denne sum her, n ganger n minus 1 alt delt på 2. Så for nå la meg bare fastsette dette er sant, så på en porsjon tro, det er hva dette oppsummerer opp til, og vi kunne vise seg at det i et mer generelt tilfelle. Men la oss nå utvide dette ut. Så la oss formere ut dette, så det er n kvadrert, minus n, alt dividert med to. Det er virkelig n squared, delt på to, minus n over 2, så det er alt fint og interessant. Men hva skjer hvis vi nå plug-in en verdi? Anta at jeg ikke har åtte mennesker, men si en million. Og en million bare fordi det er en ganske stort tall, La oss plugge det i og se hva som skjer. Så hvis jeg kobler en million inn i den formelen Jeg kommer til å få en million kvadrat, dividert med 2, minus millioner, delt på to. Nå hva som kommer til å like? Så 500 milliarder dollar, minus 500.000. Og hvis jeg faktisk gjør at regnestykket ut, det betyr at sortering en million mennesker med boblen slags kan ta meg 499999500000 trinn eller sammenligninger i slutten, vi bare ekstrapolere. Det føles ganske treg, men ærlig måler en bestemt inngang som dette, er ikke alle som fortelle. Men faktisk er det ikke tyder på at så n blir større og større, denne algoritmen slags føles verre og verre, eller du virkelig begynner å føle smerten ved det eksponenter, som n squared, som legger opp ganske fort. Og denne detaljen er ikke tapt på folk, faktisk for noen år siden en viss senator som var valgkamp, ​​satte seg ned for et intervju med Googles Eric Schmidt, administrerende direktør på den tiden, og ble utfordret med et spørsmål mye som vi utforsker i dag. La oss ta en titt. [VIDEOAVSPILLING] -Senator, Du er her på Google, og jeg liker å tenke på formannskapet som et jobbintervju. Nå er det vanskelig å få en jobb som president, og du går gjennom påkjenningene nå. Det er også vanskelig å få en jobb på Google. Vi har spørsmål, og vi ber våre kandidater spørsmål, og dette er fra Larry Schwimmer. Hva-- dere tror jeg er tuller, det er rett her. Hva er den mest effektive måten å sortere en million 32-bits heltall? -Well-- Jeg beklager, maybe-- Nei, nei, nei. Jeg tror boblen slags ville være feil vei å gå. Kom igjen, som fortalte ham dette? Jeg fikk ikke se datamaskinen vitenskap i din bakgrunn. Vi hare fikk våre spioner i det. -OK, La oss be en annen intervju spørsmål. [END VIDEOAVSPILLING] SPEAKER: Så snakker om spesifikke tall skjønt, ikke kommer til å være alt som er nyttig. Det er ikke et liv leksjon som boble sortere, gitt en million innganger, kan ta så mange som 500 milliarder dollar trinn. Du kan virkelig ikke general for effektivt fra at og lage gode design beslutninger når du skriver programmer. Så la oss fokusere selv på hvordan vi kan forenkle dette resultatet. Så jeg har uthevet i gult her produktet av n squared dividert med 2, så en million squared dividert med 2, og deretter Jeg har fremhevet det det ultimate svaret var når vi trekkes av n delt på to. Og påstanden jeg kommer til å gjøre nå er, hvem pokker bryr seg om du trekker ut litt gamle N over 2 når den første en del av denne formelen er så mye større? Det dominerer den andre sikt, n rutet delt på to er så mye større, tydelig, som N blir stor som en million, som er det virkelig en stor forskjell på slutten av dagen mellom 500000000000 og 499 999 500 000? Ikke egentlig. Og så hva vi skal gjøre som dataforskere er ignorere de lavere ordens ledd og ta noe sånt som dette, og virkelig bare forenkle den til begrep som kommer til å spille noen rolle. De større våre datasett blir, jo større våre databaser får, jo flere nettsider vi må søke, jo mer venner du har på Facebook. Som n blir større, vi er virkelig kommer til å bry seg om den største begrep i en slik analyse av våre prestasjoner algoritmer. Og jeg kommer til å si, vet du hva, boble slags er i størrelsesorden big O, av størrelsesorden n kvadrat. Det er ikke akkurat n squared som vi har sett, men som virkelig bryr seg om de mindre vilkår, og ærlig, som virkelig bryr seg hvis vi deler med 2? Det er bare en konstant faktor. Og er 500 milliarder dollar versus 250 milliarder virkelig så stor av en avtale? Jeg kunne bare vente ett år, la min laptop bokstavelig få dobbelt så raskt i maskinvare, og den slags forskjell bare forsvinner naturlig over tid. Hva vi bryr oss om er uttrykket, delen av uttrykket som kommer til å variere som våre innspill blir større og større. Og ja, i den virkelige verden, det er hva som skjer i økende grad er inngangene på våre problemer og algoritmer blir større. Så stor O kommer til å være notasjonen, asymptotisk notasjon, at vi bare bruke som dataforskere å beskrive ytelsen, eller løpende tid, av en algoritme. Slik at vi kan sammenligne algoritmer på forskjellige datamaskiner skrevet av forskjellige mennesker, ved å bruke noen fundamentalt lik metriske som antall sammenligninger du er gjør, eller kanskje antall bytteavtaler du gjør. Hva vi kommer ikke til å teller er tiden som passerer på klokken på veggen vanligvis. Hva vi kommer ikke til å bekymre om er hvor mye minne du bruker i dag på minst, selv om det er annen ressurs vi kan måle. Vi kommer til å prøve å basere våre analyser på akkurat de grunnleggende operasjoner, de, ærlig, som du kan se mest visuelt. Så med noe sånt som stor O av n squared, jeg hevder at O ​​av n squared er en øvre grense for den såkalte kjøretiden boble slag. Med andre ord, hvis du ønsket å hevde at det er denne øvre grense for hvor mange trinn en algoritme kan ta, det kommer til å være i stor O av n kvadrert i dette tilfelle en øvre grense. Hva om jeg i stedet endre historie å være ikke om boble sortere, men om dette øvre grense. Kan du tenke deg en algoritme at vi har sett på allerede som øvre grense, maksimal måle tid eller operasjoner, skulle kunne sies å være avgrenset med n, en lineær funksjon, ikke en kvadratisk en som er buet? Hva er en algoritme som alltid tar ikke mer enn som n trinn, eller 2n skritt, eller 3n trinn? Yeah? PUBLIKUM: Finne største antallet i en liste? SPEAKER: Perfect, finne det største antallet i en liste. Hvis jeg får en liste over mennesker for eksempel, hver av hvem som holder et nummer, hva som er det maksimale antallet trinn det skal ta meg, en rimelig smart person, å finne den største personen i denne listen? n, ikke sant? Fordi i verste fall, hvor kanskje den største verdien være? Høyre, helt på slutten. Så i verste fall øvre grense, kan jeg nødt til å gå hele veien over her og være like, oh, her er nummer åtte, eller hva denne verdien er. Nå ville det bare være dum hvis jeg fortsatte å gå, ikke sant? Leter du etter flere og flere elementer hvis den siste av dem er der borte? Så sikkert, er n en øvre grense. Jeg trenger ikke å ta flere trinn enn det. Så hva om stedet jeg foreslått at det er algoritmer i denne verden som har en driftstid som er avgrenset av store O av log n, log n? Hvor har vi sett dette før? Yeah? PUBLIKUM: I telefonboken problemet? SPEAKER: Som telefonboken problem. Det var et mål på hvordan mye tid eller hvor mange tårer det Tok meg å finne noen som Mike Smith i telefonboken? Vi hevdet at det var log n og selv om ukjente eller det det er litt disig hva en logaritmen eller eksponent var, bare husk at log n generelt refererer til prosessen, i dette tilfellet, for å dele noe i to igjen, og igjen, og igjen og igjen, slik at den blir stadig mindre som du gjør det. Så logge av n refererer, sikker, til telefonboken eksempel til binær søk i teorien, når vi hadde de virtuelle dørene på brettet, eller når Sean var søker etter noe. Hvis han hadde brukt binære søk, log n vil være den øvre grense for hvor mye tiden som tar. Men disse algoritmene som kjørte i log n antatt hva viktige detalj? At listen ble sortert, ikke sant? Din algoritmen er galt hvis dine innspill er ikke sortert, og ennå du bruker noe sånt som binære søk fordi du kan hoppe rett over elementet uten å vite det er faktisk det. Nå hva kan dette bety, big O av en? Dette betyr ikke at algoritmen tar ett og bare ett trinn, det betyr bare det tar en konstant antall skritt. Kanskje det er en, kanskje det er 10, kanskje det er 1000, men det er uavhengig av størrelsen av problemet. Uansett hvor stor n er, en konstant tid algoritme alltid tar det samme antall trinn. Så hva kan være en algoritme vi har snakket om, eller bare intuitivt som kommer til deg som alltid løper i såkalte konstant tid? Yeah? PUBLIKUM: Legg to tall. SPEAKER: Legg to tall, 2 pluss 2 er lik 4, gjort. Så det kan fungere, hva annet? Hva med mer virkelige verden, ja? PUBLIKUM: Finne første i en liste. SPEAKER: Finne den første element i en liste, sikker. Vi har faktisk vært snakket om arrays allerede, hvordan får du på første element i en matrise, uansett hvor lenge matrise er i C-kode? Du bare bruke som braketten null notasjon, bam, du er der. Og faktisk arrays, som en side, støtte noe generelt kjent som random access, random access minne, fordi du kan bokstavelig talt hoppe til et hvilket som helst sted. Vi kan gjøre dette enda enklere vi kan spole tilbake til uke null når vi gjorde Scratch. Hvor mye tid tok det for si blokk i Scratch å utføre? Bare konstant tid, ikke sant? Si noe, sier noe, spiller det ingen rolle Hvor stor Riper verden er, er det alltid kommer til å ta like lang tid å bare si noe. Så det er konstant tid, men hva er baksiden? Hvis det var øvre grenser, hva om vi ønsker å beskrive de nedre grenser av våre algoritmer gangtid? Nesten et best case potensielt, om du vil, selv om disse vilkårene kan gjelde for beste tilfeller, verste tilfellene gjennomsnittlig tilfeller mer generelt, men la oss bare fokusere på nedre grenser mer generelt. Hva er en algoritme som har en nedre grense for n skritt, eller 2n skritt, eller 3n trinn? Noen faktor av n skritt, det er dens nedre grense. Yeah? PUBLIKUM: Bubble slag? SPEAKER: Bubble slags tar du minimalt n skritt, hvorfor? Hvorfor er det? Hvorfor skulle det begynne å komme til deg intuitivt, selv ikke om den gjør det bare ennå? Yeah? PUBLIKUM: [uhørlig]. SPEAKER: Nettopp. På best mulig scenario av boble sortere, og mye av algoritmer, hvis jeg hånd du åtte personer som allerede er sortert, det ville være tåpelig for deg, algoritmen, å gå frem og tilbake mer enn en gang, ikke sant? Fordi så snart du gå gjennom listen en gang, , du bør innse oh, gjorde jeg ingen bytteavtaler, er denne listen sorteres, exit. Men det kommer til å ta deg n trinn. Og omvendt, hva er en annen måte å tenke på det? Bubble sort er en omega, så å si, av n, fordi hvis du ser på færre enn n elementer, hva er den grunnleggende problem der? Du vet ikke om det er sortert, ikke sant. Vi mennesker kan blikk på åtte mennesker og være som, oh, er det sortert, som ikke tar meg n skritt, men det gjorde. Dine øyne, selv om du på en måte av har en stor synsfelt, du så på åtte elementer, du så på åtte personer, det er åtte trinn effektivt. Og bare hvis jeg går gjennom hele liste må jeg skjønner, ja, sortert. Hvis jeg stoppe halvveis tenker, alt Greit, det er ganske sortert så langt, hva er oddsen det er ikke sortert? At algoritmer ikke kommer til å være korrekt. Kan være raskere, men feil. Så nå har vi en måte å beskriver en nedre grense, og hva med konstant tid? Det er en algoritme som har en lavere bundet på sin driftstid for en? 1 trinn, 2 trinn, 10 trinn, men konstant, uavhengig av n, størrelsen på inngangs? Ja, i ryggen. PUBLIKUM: Printf? SPEAKER: Hva er det? PUBLIKUM: Printf? SPEAKER: Printf. OK, sikkert. Så det tar et fast antall skritt. Og jeg burde now-- nå at vi snakker om C-kode og ikke Scratch, noe som sier, med printf, vi bør begynne å bli forsiktig. Fordi printf tar input, er det en streng, og strenger trenger teknisk har lengde. Så hvis vi nå ønsker å plukke på deg, hvis du ikke tankene, teknisk vi kan argumentere for at printf tar en variabel lengde inngang, og sikkert kan det ta mer tid til å skrive ut en streng dette lenge, enn så lenge. Så hva hvis vi ser bare sortering og søking eksempler? Hva med Mike Smith i telefonen bok, eller binære søk mer generelt? I beste fall kan det skje? Jeg åpner telefonboken, og bam, det er Mike Smith nummer. Jeg kan ringe ham med en gang. Tok et skritt, kanskje to trinn, men en konstant antall skritt hvis jeg hadde flaks. Og ærlig talt, vi så på Mandag din klassekamerat bli ganske heldig to ganger på rad. Og det var faktisk konstant tid i en nedre grenser på algoritmen aktuelle for å finne nummer 50 bak de stengt dører. Nå, som en side, hvis du oppdager at både stor O, den øvre grensen, og omega, den nedre grensen, er en i samme, at er den samme formel i parentes, kan du også si, bare for å være fancy, at noe er i theta n eller theta av en annen verdi. Det betyr bare at når store O og omega er de samme. Hva nå om valg slag? La oss bruke denne nye vokabular. I utvalget sortere, hva var vi gjøre igjen, og igjen, og igjen? Jeg skulle frem og tilbake gjennom listen, på jakt etter hvem? Det minste tallet. Så hvor mange trinn, hvordan mange sammenligninger gjorde jeg må gjøre for å finne ut hvem det minste element i listen var? n minus en, ikke sant? Fordi hvis jeg bare begynne med en jeg er gitt, og jeg begynner å sammenligne ham eller henne, så ham eller henne, ham eller henne, ham eller henne, jeg kan bare koble elementer sammen n minus 1 ganger. Så utvalget tar liksom på samme måte n minus 1 trinn første gang. Hvor mange skritt tar det meg til finne den nest minste element? n minus 2, fordi jeg blir stum hvis jeg fortsetter å se på de samme menneskene igjen hvis jeg allerede har valgt ham eller henne og sette dem i deres sted. Og det tredje trinnet, n minus 3, deretter n minus fire. Vi har sett dette mønsteret før, og faktisk utvalg slags tilsvar har en øvre grense av n squared hvis vi gjør opp at summering. Hva er dens nedre grense, valg liksom? Minimal, hvor mye tid must utvalg Sorter ta, slik vi definerte det på mandag? Foreslår to alternativer. Kanskje det er n, som før. Kanskje det er n squared, som det er nå som den øvre grensen. PUBLIKUM: n squared. SPEAKER: n squared. Hvorfor? PUBLIKUM: Fordi du har å definere [uhørbart]. SPEAKER: Nettopp. Minst som jeg definert utvalg sort det var ganske naiv, holde det gående, finne den minste element. Gå igjen, finne det minste elementet. Gå igjen, finne det minste elementet. Det er ingen form for optimalisering i det at kanskje la meg avbryte etter bare n eller så trinnene. Så ja, utvalg sortere, omega n squared. Hva om innsetting sortere, der jeg tok som jeg fikk, og da jeg plopped ham eller henne på rett sted? Så jeg gikk videre til andre personen, plopped ham eller henne på rett sted. Så neste person, plopped ham eller henne på rett sted. Bemerk at dette er svært lineær, så å si. Jeg er en rett linje, jeg er ikke går frem og tilbake, Jeg har aldri ser tilbake egentlig, men hva som skjer når jeg setter ham eller hennes inn i begynnelsen av listen som vi gjorde på mandag? Hva skjer? Yeah? PUBLIKUM: [uhørlig]. SPEAKER: Ja, det var fangsten, ikke sant? Du husker kanskje fra klassekameratene dine, hvis de var å gjøre enhver bevegelse med sine føtter, som var en operasjon. Så hvis det var tre personer her og den nye personen tilhørte veien der borte, på en lang etappe som dette, sikker, han eller hun bare kunne gå helt til enden. Men hvis vi tenker på en datamaskin og en matrise av minne, disse menneskene går å måtte stokke løpet å gjøre plass til den personen. Og slik at n minus en shufflings, n minus 2 shufflings, n minus 3 shufflings er bare slags skjer bak meg, ikke foran meg som før, i noen forstand. Nå som en side, og som du kanskje har sett på nettet hvis du begynner poking rundt om sorterer, det er så mange forskjellige lister ute, noen av dem bedre enn andre. Faktisk er bogosort ett det er like gøy å se opp. Bogosort tar et sett tall eller si en kortstokk, stokker dem tilfeldig, og sjekker om de er sortert. Og hvis ikke, gjør det igjen. Og hvis ikke, gjør det igjen. Hvis ikke, gjør det igjen. Utrolig dumt. Og ja, hvis du leser som Wikipedia-artikkelen, sitt kallenavn er dum liksom. Det vil etterhvert fungere, forhåpentligvis, gitt nok tid, men at tiden kan ta ganske lang tid. Så hvis jeg kunne, la oss fart på sakene opp fra Mary Beth eksempel tidligere, ved å ha noen flere elementer, men to flere prosessorer. To personer, hvis du ville ikke tankene å bli med meg. Hva med en over her, og la oss Vær så god ingen der borte? Ingen der borte? OK. Du med den svarte skjorte, ja, komme ned. Ok, hva heter du? PUBLIKUM: Peter. SPEAKER: Hva er det? PUBLIKUM: Peter. SPEAKER: Peter, David, hyggelig å møte deg. Greit, vi har Peter her, hvis du ønsker å komme på bordet over her. Og hva heter du? PUBLIKUM: Elena. SPEAKER: Elena. OK, hyggelig å møte deg. Elena møte Peter. Peter, Elena. Og vi trenger Andrew opp her også, takk. Og utfordringen går å være å sortere en kortstokk. Og hvis ukjente, dekk av kortene bør til slutt sorteres litt noe sånt dette hvor vi vil gjøre klubbene, deretter de spar, deretter hjertene og diamanter, fra ess som ett, hele veien opp til kongen. Kortene jeg kommer til å gi deg kommer til å være 52 i kvantitet. Vi skal på samme måte gang du, i løpet av et øyeblikk. Vi kommer til å kaste Andrew opp på skjermen her slik som å se på som du gjør dette. Og slik at hele denne er enda mer synlig, dette er de kortene jeg fikk på Amazon. Så de er allerede tilfeldig sorteres, og vi kommer til tiden du. Og vi kommer til å holde det ekte denne gangen, så vi kommer til å prøve å presse deg fordi ellers vil dette bli kjedelig raskt. Hvis du kunne fortsette å sortere 52 elementene sammen via noen midler, som nå. Og igjen, når vi ser disse gutta gjør hva, til slutt kommer til å produsere en åpenbar resultat, tenker egentlig hvordan de hver gjør det, hvordan du kan beskrive det. Fordi igjen, er disse Alle prosesser, algoritmer som vi tar for gitt som et menneske. Men du har sikkert lenge hatt intuisjon, lenge før du selv tenkte på å ta en informatikk klasse du kan ha hatt intuisjon med for å løse problemer som dette. Men når du kjenner igjen mønstrene og begynne å formalisere trinnene med som du løse disse problemene, du vil finne at du kan løse mye mer interessant og mye mer kompleks problemer raskt. Så noen fra publikum, hva er i det minste ett element av algoritmen at de bruker her? PUBLIKUM: [uhørbart] SPEAKER: Hva er det? PUBLIKUM: Ved dress. SPEAKER: Ved dress. Så først de clustering alle diamantene sammen det virker, hele hjerter sammen det virker, og så videre, uten å gjøre forskjell for tallene på kortene. Og nå de dukker opp, for eksempel, skal sortere dem etter nummer. Veldig bra. Greit, så hva som kommer til være det siste trinnet så her? Når vi har fire sorterte dresser, hva trenger vi å gjøre til de fire hauger for å oppnå en sortert dekk, ganske enkelt? Så vi trenger å sette dem sammen igjen. Så det er en interessant idé som igjen, daresay, er svært intuitivt selv hvis du kanskje aldri har slapped den slags merkelapp på det. Denne grunnleggende tanken om å dele problemet ikke i halvparten av denne tiden men i det minste i fire deler. Løse ganske mye fundamentalt identiske problemer isolert fra hverandre, og deretter å slå sammen resultatene. Og, utmerket, gjort. Greit, en stor runde applaus, hvis vi kunne. [APPLAUSE] SPEAKER: Jeg aner ikke hva du vil gjøre med disse, men her du går. Takk så mye. Så la oss se, to minutter og åtte sekunder, Hvis du ønsker å utfordre vennene dine. Hva da kommer til å være en ta bort fra dette at vi kan utnytte mer generelt? Vel, tenker tilbake til denne matrisen av tall, og tenker tilbake nå til noen av de pseudo vi har skrevet i det siste, og dette var den pseudokode for løse telefonboken problem. Der det i pseudo jeg oppregnet en mer metodisk måte beskrive hvordan jeg gjorde en veldig intuitiv menneskelig algoritme for å dele telefonen bok i to, gjenta, gjenta, gjenta, til jeg finner noen som Mike Smith, hvis han er faktisk i telefonboken. Men jeg slags brukt det jeg vil kalle en svært iterativ tilnærming her, særlig forvarsel linje 8 og linje 11. De er bevis på en iterativ tilnærming, en looping tilnærming, fordi det er akkurat atferden de indusere. Disse linjene både si gå til linje tre, og du kan slags tenk på at i din indre øye som en loop. Det er å fortelle deg å gå tilbake til trinn tre og gjenta, igjen og igjen, og igjen. Men hva om vi utnytte et sentralt begrep her at vi gjorde ikke siste gang, og forenkle linje 8 og linje 11 og deres naboer som nettopp dette, i gult. Det er ikke fundamentalt forkorte den pseudo veldig mye, men det er fundamentalt endre arten av min-algoritmen. Det jeg nå sier i trinn 7, i trinn 10, er å søke etter Mike på nøyaktig samme måte, men bare i den venstre halvparten eller høyre halvdel. Så med andre ord, hvis Jeg starter fra trinn én, plukke opp telefonboken, åpen for midten av telefonboken, se på navn, hvis Smith er blant heter, ringe Mike, annet hvis Smith er tidligere i boken, steg syv søke etter Mike i venstre halvdel av boken. Men den slags føles som det drar meg hengende, ikke sant? I gult, er en instruksjon, men hvordan gjør jeg søk etter Mike i venstre halvparten av telefonboken? Hvor har jeg en algoritme som jeg kan søke etter noen som Mike Smith? Vel, det stirrer oss i ansiktet. Jeg kan bokstavelig talt bruke nøyaktig samme programmet effektivt å gå opp til toppen igjen, og re-løpe de samme linjer med kode. Så selv om dette bør føle som en bit av en syklisk definisjon hvor du svare noens spørsmålet ved bare liksom spørre det samme spørsmålet igjen, som hvorfor, hvorfor, hvorfor? Realiteten er fordi vi har hardkodet et par spesielle linjer, trinn 4, som er en hvis, og trinn 12, som er effektivt en annen gren, fordi vi har disse nødhjelp tiltak, denne algoritmen vil opphøre dersom vi finne Mike, eller hvis vi ikke gjør det. Men i trinn 7 og 10 nå, har vi hva vi vil kalle en rekursiv algoritme. Og rekursjon er faktisk en kraftig idé som er litt tankene bøyd i starten, at vi nå kan bruke som følger. Flett typen vil være den siste typen som vi ser på, i det minste i klassen formelt. Og det er fundamentalt annerledes fra de siste tre, og i hvert fall siste fire hvis vi inkluderer bogosort. Her er pseudokode for flettingen slag. Når på innspill av n elementer, så gitt en matrise av størrelse n, hvis n er mindre enn 2, tilbake. Så hvorfor har jeg det tilregnelighet sjekk først? Hva er implikasjonen om jeg leverer deg en matrise som har lengde n er mindre enn 2? Det er allerede sortert, selvsagt, ikke sant? Fordi listen har enten ett element, som er trivielt sortert fordi det er det eneste der. Eller, det er av størrelse null som betyr det er ingenting å sortere, så av natur det er sortert. Det er bare ikke noe galt der. Så det er vårt såkalte base case. Det ligner i ånden til hva vi gjorde med Mike. Hvis Mike i telefonboken, kan du ringe ham. Hvis han ikke er der, gi opp. Det er en såkalt base case, for å være sikker denne algoritmen på slutten av dagen vil stoppe i visse tilfeller. Men her er spranget tro nå, annet, sortere venstre halvdel av elementene, deretter sortere riktig halvparten av elementene, og deretter fusjonere de sorterte halvdeler. Og her er der det føles som om vi copping ut. Jeg har bedt deg om å sortere n elementer, og jeg er sa OK, gjør det ved å sortere venstre og sortering høyre. Men jeg sier ett andre ting, og dette er nøkkelen tema det virker i intuisjon så langt, det er dette tredje trinnet av sammenslåing. Som selv om det virker så dum i ånden, som bare flette ting sammen, virker det å være et viktig skritt mot remontering av to problemer som ble delt slutt i to. Så flette sortere, la oss gjøre dette, hvis du vil humor meg, med ett mer demonstrasjon, akkurat slik at vi har noen tall å jobbe med. Kan jeg bytte åtte stresset baller for åtte personer? Ok, hva med deg tre, du fire i denne delen, fem, seks, og la oss trenger 7, 8, kom igjen opp. OK, ja OK. Minus 8, der vi går, pluss en. Utmerket. Greit kom igjen opp, la oss raskt gi deg tall. Nummer to, nummer tre, fire tall, nummer fem, seks, sju, og åtte. Jeg gjorde åtte riktig denne gangen. OK, så gå videre hvis du kunne, og La oss sortere i den opprinnelige bestillingen at vi hadde i går som sett som dette, hvis du ikke hadde noe imot. Og la oss gjøre det foran på tabellen. Greit, så flette slag. Det er der det kommer å få like interessant, fordi jeg synes å være å gi meg selv så mye mindre informasjon i dag. Så fusjonere liksom først av alt på innspill av n elementer, og er åpenbart ikke er mindre enn to, er det åtte, så jeg har litt mer arbeid å gjøre. Så nå mentalt vi som en klasse er nå i andre grenen, noe som betyr at tre trinn. Først må jeg sortere venstre halvdel av elementene. Så hvordan går jeg om du gjør dette? Vel, jeg kommer til å slags mentalt dele listen her, du trenger ikke å fysisk flytte, og jeg er kommer til å fokusere bare på venstre halvdel av elementene her. Så hvordan går jeg om sortering en liste nå av størrelse fire? Hva er min algoritme? Først sjekker jeg er n mindre enn to, nei, så jeg går videre til andre blokken igjen. Sorter forlot halvparten av elementer. Så nå igjen, mentalt, og det er her du må løpe mye mental historie, hvis du vil. Nå er jeg sortering venstre halvparten av den venstre halvdel. Ok, så nå jeg kaller min samme merge sortering algoritme, er N mindre enn to? Nei, det er to, så jeg må sortere den venstre halvdelen, og høyre halvdel. Så her går vi, sortere den venstre halvdelen. Hvorfor ikke bare ta ett skritt fremover. Hva heter du? PUBLIKUM: Darren. SPEAKER: Dan. Dan har trappet fremover. PUBLIKUM: Darren. SPEAKER: Darren, gjort. Visste du sier Darren eller Dan? PUBLIKUM: Darren. SPEAKER: Darren. OK, Darren har trappet fremover og er han nå sortert. Og dette er nesten en tåpelig påstand, ikke sant? Jeg vet egentlig ikke synes å være å oppnå noe, men la oss fortsette. Nå la meg sortere riktig halvparten av elementene. Hva heter du? PUBLIKUM: Luke. SPEAKER: Luke. Kom igjen, kom frem. Gjort, har jeg sortert Luke. Den venstre halvdelen er nå sortert og høyre halvdel blir nå sortert, men igjen, det er et viktig steg her. Hva gjør jeg neste trenger å gjøre? Fusjonere de sorterte halvdeler. Nå skal vi bare ha alle frem og tilbake på denne måten, fordi jeg slags trenger noen scratch plass. Det er nesten som disse gutta er på et bord, og jeg trenger litt plass for å flytte dem rundt på. Så jeg kommer til å fusjonere dere ved å se på den venstre halvdel og den høyre halvdel. Og som åpenbart kommer først, venstre halvdel eller høyre halvdel? Så høyre halvdel, så la oss gå Luke løpet her til Darren opprinnelige posisjon. Og nå for å fusjonere deres venstre halvdel i, Darren kommer til å flytte rett der. Så føles nesten en boble slags effekt, men min grunnleggende algoritme, veldig annerledes denne gangen. Men nå er der ting blir litt irriterende fordi du må spole tilbake mentalt hvor har jeg sluttet. Jeg har nettopp slått sammen de sorterte halvdeler, noe som betyr at jeg er der i min algoritme? Jeg må sortere høyre halvdel, ikke sant? Hvis du spoler, bokstavelig talt på video, vil du se at vi fikk til dette poenget med Luke og Darren ved å sortere venstre halvparten av den venstre halvdel. Da vi fusjonerte de sorterte halvdeler, hvilke betyr det neste trinnet er liksom den høyre halvdel av venstre halvdel. Ok, så la oss Dette gjør raskere. Greit, seks, kommer jeg til å hevde du er nå sortert, kom frem. Hva heter du? PUBLIKUM: Adriano. SPEAKER: Adriano. Adriano er nå sortert. Og hva heter du? PUBLIKUM: Alex. SPEAKER: Alex er nå sortert. Venstre halvdel, høyre halvdel, hva er det siste trinnet? Fusjonere. Ganske trivielt, så jeg er kommer til å fusjonere i seks, ta et skritt tilbake, åtte, ta et skritt tilbake. Og nå merke til dette er en nyttig takeaway, hva er nå sant om den venstre halvdelen av liste, uavhengig av hvordan vi begynte? Det er sortert. Nå er det ikke sorteres i den store sammenhengen, men det er sortert uavhengig av den andre halvparten. Nå hva trinnet er jeg på hvis jeg holder tilbakespoling hvordan historien begynte? Nå må jeg sortere høyre halvdel. Så nå er vi helt tilbake på begynnelsen av historien, og la oss gjøre dette raskere. Så jeg kommer til å sortere høyre halvpart av hele listen. Hva er neste steg? Sortere den venstre halvdel av høyre halvdel. Sortere den venstre halvdelen av venstre halvdel av den høyre halvdel. Og hva heter du? PUBLIKUM: Omar. SPEAKER: Omar, gå fremover, gjort. Venstre halvdelen er sortert. Og hva heter du? PUBLIKUM: Chris. SPEAKER: Chris, ta et skritt fremover, er du nå sortert. Hva er viktig skritt nå? Fusjonere. Så man kommer til å flette på plass her, hvis du kunne ta et skritt tilbake, og tre kommer til å ta et skritt tilbake, flette. Så den venstre halvdelen av høyre halvdel, er nå sortert. Oppriktig, føles denne algoritmen som vi kaster bort mye mer tid enn før, men hvis vi gjorde dette i sanntid, vil vi se hva takeaways kommer til å være. Nå er jeg her, ikke sant halvparten av den høyre halvdel, la meg gå videre og sortere den venstre halvdelen. Skritt fremover, hva heter du? PUBLIKUM: Ramsey. SPEAKER: Ramsey er nå sortert. Hva heter du? PUBLIKUM: Marina. SPEAKER: Marina er nå sortert som vel, hvis du tar ett skritt frem. Viktig steg her er nå flette, jeg er kommer til å rykke fra mine to lister, venstre og høyre. Fem skal komme først, og syv skal komme neste. Og igjen, dette er bevisst. Det faktum at de tar skritt frem og tilbake er ment å representere at vi ikke kan Dette gjør algoritmen i stedet som lett som boble sortere, og utvalg sortere, og innsetting slags der vi bare holdt bytte folk. Jeg bokstavelig talt trenger en slags kladdepapir der å sette disse folkene mens jeg gjør sammenslåing, og da kan jeg sette dem tilbake på plass. Og det er nøkkelen fordi jeg bruker en ny ressurs, plass, ikke bare tid. OK, dette er fantastisk. Venstre halvdel er sortert, høyre halvdel er sorteres, nå som nøkkelen sammenslåing trinn. Hvordan kommer jeg til å flette dette? Så hvis du vil følge min venstre hånd og høyre hånd, Jeg kommer til å peke min venstre hånd på venstre halvdel, min høyre hånd på høyre halvdel, og nå må jeg bestemme trinnvis hvem du skal flette inn. Som åpenbart kommer først? Nummer én. Så kom igjen over her, her er vår kladdeblokk. Så nå nummer én, og varsel hva skal jeg gjøre med min høyre hånd, Jeg kommer til å flytte min høyre hånd en gå over til punkt nummer tre, og nå er jeg nødt til å gjøre den samme beslutningen. Og faktisk stå rett foran Luke her hvis du kunne, fordi dette er vår kladdeblokk. Så hvem kommer neste? Vi har Luke med nummer to eller Chris med nummer tre. Tydeligvis Luke, antall to, slik at du kommer hit. Men min venstre hånd nå kommer til å skal økes til å peke på Darren, og her er nøkkelen ta bort med sammenslåing, kommer jeg til å fortsette å gjøre dette, Selvfølgelig, hvis du snill av følge logikken. Men hendene mine er aldri kommer til å gå bakover, som betyr at jeg bare måtte flytte til venstre med min fusjonsprosessen, og som kommer til å være nøkkelen til vår analyse på bare et øyeblikk. Så nå la oss avslutte dette raskt opp. Så tre kommer neste, deretter fire kommer etterpå, og nå fem kommer etterpå, så seks, og syv, og deretter til slutt åtte. Føles som den tregeste algoritmen ennå, men ikke hvis vi faktisk kjøre den på samme sorter av klokkefrekvens, så å tale, med samme tikkende klokke som før. Hvorfor? Vel, la oss ta en se på sluttresultatet. La oss gå tilbake over her, la meg trekke opp en demonstrasjon visuelt av hva vi nettopp gjorde. Zoome inn her, på dette side her, forteller Firefox at vi ønsker å stå i kø opp i denne boksen, la oss si boble sortere, som vi er nå godt kjent, valg sorter, som er en annen ganske grei en, og nå dagens merge sort, som vil være vår spennende slutt. Grunnen til at det tok så mye lenger her med mennesker og meg verbalt er, selvsagt, jeg forklare hvert trinn. Men hvis du bare utføre dette, mye som vi gjorde boble sortere og utvalg liksom ikke bare visuelt, watch hvor mye mer effektivt denne utnytte av divisjon og erobre kan når den anvendes på et sett med data som finnes ikke engang størrelse åtte, men enda mye, mye større. Jeg gir deg flette sortere, side ved side med disse andre algoritmer. Dette kommer til å bli smertefullt raskt, og avslutningen er ikke spesielt klimaks, de bare ender opp sortert. Men nøkkelen ta bort er at Se hvor mye raskere flette sortere var, med mindre du tror jeg er bare slags tuller med deg. Hvis vi gjør dette for siste gang, la oss laste dette, la oss gå tilbake og velg boble sortere, og bare for morro skyld, la oss velge innsetting sortere, bare for godt mål. Og denne gangen igjen, la oss velge merge sortere og la oss faktisk kjøre disse side ved side. Og det er ikke, faktisk, et lykketreff. Hva jeg har effektivt gjort er at jeg har delt mitt innspill i to, igjen, og igjen og igjen. Og det er bare så mange ganger du kan dele dine innspill i halvdeler, venstre og høyre. Hva er formelen som vi fortsette å se som beskriver divisjonen i halvparten igjen, og igjen, og igjen, og igjen? PUBLIKUM: Logg n. SPEAKER: Logg n. Men så er det en annen viktig skritt, denne algoritmen er ikke logge n trinn. Hvis det var bare log n trinn, vi ville være i det samme problemet som før hvor vi ikke kan være at alt er sortert. Du må minimal se på n elementer for å være sikker på n elementer sorteres, ellers er det en tillitserklæring. Så det er minimalt log n trinn, men hva med denne nøkkelen sammenslåing trinn hvor jeg fusjonert min venstre halvdel og høyre halvparten og gikk over scenen? Hvor mange skritt er at å fusjonere? Det er n, men jeg gjorde ikke bare flette den siste tiden. På hver av de nestede anrop, på hvert av disse nestet fusjonerer, jeg fortsatt sortert. Jeg slått sammen disse to gutta, så disse to folkens, da disse to gutta, og så videre. Så jeg gjorde sammenslåing igjen, og igjen. Hvor mange ganger? Så hver gang jeg delt liste i to, gjorde jeg en flette. Dele opp listen i to, gjør en flette. Så hvis dele listen kan gjøres for log n ganger, og sammenslåing tar slutt n trinn, hva som kan være nå den øvre bundet på løpe tid algoritmen vår? n log n. Og ja, det er det vi har oppnådd her. Så føler at du ser visuelt når disse tre tingene kjøres side ved side er n squared mot n squared mot n log n. Hvilke fundamentalt vi får se, ikke bare i dag, men i fremtiden, er mye, mye raskere. En applaus for disse gutta, Jeg vil belønne dem med stress baller. La oss utsette her i dag, og vi vil se deg på mandag.