>> [MUSIC SPILLE]
>> PROFESSOR: All right.
Dette er CS50, og dette er slutten av uke tre.
Så vi er her i dag, ikke i Sanders Teater, i stedet i Weidner Library.
Innsiden av som er et studio kjent som Hauser Studio,
eller skal vi si Studio H, eller skal vi say-- hvis du likte den vitsen,
det er faktisk fra klassekamerat, Mark, online,
som foreslo så mye via Twitter.
Nå hva er kult om å være her i et studio
er at jeg er omgitt av disse grønne vegger, en grønn skjerm eller chromakey,
så å si, noe som betyr at CS50 s produksjon team, ukjent for meg
akkurat nå, kunne være å sette meg mest hvor som helst i verden,
for bedre eller verre.
>> Nå hva som ligger foran oss, oppgavesettet to er i dine hender for denne uken,
men med oppgavesettet tre denne kommende uken,
du vil bli utfordret med den såkalte game of 15,
et gammelt parti favør at du kanskje husker mottak
som et barn som har en hel haug av tall som kan skyve opp, ned,
venstre og høyre, og det er ett gap innen puslespillet, der du
faktisk kan skyve disse brikkene.
Til syvende og sist du får denne puslespillet i noen semi tilfeldig rekkefølge,
og målet er å sortere det, topp til bunn,
venstre til høyre, fra ett hele veien opp til og med 15.
>> Dessverre, gjennomføring du har for hånden
kommer til å være programvare basert, ikke fysisk.
Du er faktisk nødt til å skrive kode med som en student eller bruker kan
spille spillet på 15.
Og faktisk, i hacker utgaven av spillet på 15,
du vil bli en utfordring å implementere, ikke bare å spille av denne gamle skolen
spillet, men heller løse av det, implementere gud modus,
så å si, som faktisk løser gåten for det menneskelige,
ved å gi dem hint, etter hint etter hint.
Så mer om det i neste uke.
Men det er det som ligger foran oss.
>> For nå husker at tidligere denne uken vi hadde denne cliffhanger, om du vil,
hvorved det beste vi gjorde sortering klok var en øvre grense for store o n
squared.
Med andre ord, boble sortere, utvalg sortere, innsetting sortere,
alle av dem, mens forskjellige i gjennomføringen,
delegert til en n squared kjører tid i det aller verste tilfelle.
Og vi generelt anta at det aller verste fall for sortering
er en som dataen er helt bakover.
Og ja, det tok ganske få skritt for å gjennomføre hver av disse algoritmer.
>> Nå helt på slutten av klassen tilbakekallingen, sammenlignet vi boble liksom
mot valget sort mot en annen som vi kalte merge sort på den tiden,
og jeg foreslår at det tar Fordelen med en leksjon fra uke
null, Splitt og hersk.
Og en eller annen måte å oppnå en slags logaritmisk kjøretid til slutt,
i stedet for noe det er rent kvadratisk.
Og det er ikke helt logaritmisk, det er litt mer enn det.
Men hvis du husker fra klassen, Det var mye raskere.
La oss ta en titt på hvor vi slapp.
>> Bubble slags versus utvalg sorter versus merge sort.
Nå er de alle kjører i teori, samtidig.
CPU kjører i samme hastighet.
Men du kan føle hvor kjedelig dette er svært raskt kommer til å bli,
og hvor fort, når vi injiserer litt av uken null algoritmer,
kan vi fart på sakene.
>> Så mark liksom ser fantastisk.
Hvordan kan vi utnytte det, for å sortere tall raskere.
Vel la oss tenke tilbake til en ingrediens som vi
hadde tilbake i uke null, nemlig søker etter noen i en telefonboken,
og minner om at pseudokode som vi foreslått,
via som vi kan finne noen som Mike Smith,
så litt noe sånt som dette.
>> Nå tar en titt i særdeleshet ved linje 7 og 8, og 10 og 11,
som induserer at loop, der vi holdt går tilbake til linje 3 igjen, og igjen,
og igjen.
Men det viser seg at vi kan se denne algoritmen, her i pseudokode,
litt mer helhetlig.
Faktisk, hva jeg ser på her på skjermen,
er en algoritme for å søke etter Mike Smith blant noen sett med sider.
Og ja, vi kunne forenkle dette algoritmen i disse linjene 7 og 8,
og 10 og 11 for å bare si dette, som jeg har presentert her i gult.
Med andre ord, hvis Mike Smith er tidligere i boken,
vi trenger ikke å spesifisere trinn trinn nå hvordan du skal gå finne ham.
Vi trenger ikke å oppgi å gå tilbake til linje 3,
hvorfor gjør vi ikke bare stedet, si, mer generelt,
søke etter Mike i venstre halvdel av boken.
>> Derimot, hvis Mike er faktisk senere i boken,
hvorfor ikke vi bare sitere unquote søk for Mike i høyre halvdel av boken.
Med andre ord, hvorfor gjør vi ikke bare slags punt til oss selv sier,
søke etter Mike i denne undergruppe av boken,
og la den til vår eksisterende algoritme for å fortelle oss
hvordan du søker etter Mike i at venstre halvdel av boken.
Med andre ord, vår algoritmen fungerer enten det er
en telefon bok av denne tykkelse, av dette tykkelse, eller en hvilken som helst tykkelse hodet.
Så vi kan rekursivt definere denne algoritmen.
Med andre ord, i skjermen her, er en algoritme
for å lete etter Mike Smith blant sidene i en telefonkatalog.
Så i linje 7 og 10, la oss bare si akkurat det.
Og jeg bruker dette begrepet et øyeblikk siden, og ja, rekursjon
er buzzword for nå, og det er denne prosessen
for å gjøre noe syklisk av en eller annen måte bruker kode som du allerede har,
og kaller det igjen, og igjen, og igjen.
Nå kommer det til å være viktig at vi liksom bunnen
ut, og gjør ikke det uendelig lang.
Ellers skal vi har faktisk en uendelig loop.
Men la oss se om vi kan låne denne ideen av en rekursjon, gjør noe nytt
og igjen og igjen, for å løse sorterings problem via merge
sort, desto mer effektivt.
>> Så jeg gir deg flette slag.
La oss ta en titt.
Så her er pseudokode, med som vi kunne implementere sortering,
bruker denne algoritmen kalles merge sort.
Og det er ganske enkelt dette.
På innspill fra n elementer, med andre ord, hvis du er
gitt n elementer og tall og bokstaver eller hva input er,
hvis du får n elementer, hvis n er mindre enn to, bare tilbake.
Høyre?
Fordi hvis n er mindre enn 2, dvs. betyr at min liste over elementer
er enten av størrelse 0 eller 1, og i begge disse triviell tilfeller
listen allerede er sortert.
Hvis det ikke er noen liste, er det sortert.
Og hvis det er en liste over lengde 1, er det åpenbart sortert.
Så algoritmen kun trenger å virkelig gjøre noe interessant,
hvis vi har to eller flere elementer gitt til oss.
Så la oss se på den magiske da.
Else sortere den venstre halvdelen av elementene, deretter sortere høyre halvdel av elementene
fletter deretter sortert halvdeler.
Og hva er slags tankene bøyd her, er at jeg egentlig ikke
synes å ha fortalt deg noe ennå, ikke sant?
Alt jeg har sagt er, gitt en liste over n elementer, sortere venstre halvdel,
Da den høyre halvdel, og deretter fusjonere de sortert halvdeler,
men hvor er selve hemmeligheten saus?
Hvor er algoritmen?
Vel, det viser seg at disse to linjene først, liksom forlot halvparten av elementer,
og sortere høyre halvdel av elementer, er rekursive samtaler, så å si.
>> Tross alt, på dette tidspunkt, må jeg
en algoritme som å sortere en hel haug med elementer?
Ja.
Det er rett her.
Det er rett her på skjermen, og så jeg kan bruke det samme sett med trinn
å sortere venstre halvdel, som jeg kan høyre halvdel.
Og ja, igjen, og igjen.
Så en eller annen måte, og vi vil snart se denne, den magiske merge sort
er innebygd i det meget endelige linje, sammenslåing de sorterte halvdeler.
Og det virker ganske intuitivt.
Du tar to halvdeler, og du, en eller annen måte, flette dem sammen,
og vi får se dette konkret i et øyeblikk.
>> Men dette er en fullstendig algoritme.
Og la oss se nøyaktig hvorfor.
Vel antar at vi får de samme åtte elementer her på skjermen, ett
gjennom åtte, men de er i tilsynelatende tilfeldig rekkefølge.
Og målet for hånden er å sortere disse elementene.
Vel hvordan kan jeg gå om gjøre det ved hjelp, igjen,
flette slag, som per denne pseudo?
Og igjen, ingrain dette i tankene dine, for bare et øyeblikk.
Den første saken er ganske trivielt, hvis det er mindre enn 2,
bare tilbake, det er ingen jobb å gjøre.
Så egentlig er det bare tre tiltak for å virkelig huske på.
Igjen og igjen, jeg kommer til å ønske å ha
å sortere venstre halvdel, sortere høyre halvdel,
og deretter en gang deres to halvdelene er sortert,
Jeg ønsker å flette dem sammen inn i en sortert liste.
Så hold det i tankene.
>> Så her er den opprinnelige listen.
La oss behandle dette som en array, så vi begynte å
uke i to, som er et sammenhengende minneblokk.
I dette tilfellet, som inneholder åtte tall, rygg mot rygg mot rygg.
Og la oss nå søke merge sort.
Så jeg først ønsker å sortere den venstre halvdelen av denne listen,
og la oss derfor fokuserer på 4, 8, 6, og to.
>> Nå hvordan går jeg om sortering en liste over størrelse 4?
Vel jeg må nå vurdere sortering til venstre for den venstre halvdel.
Igjen, la oss spole tilbake for bare et øyeblikk.
Hvis pseudokode er dette, og jeg får åtte elementer,
8 er åpenbart større enn eller lik 2.
Så med det første tilfellet gjelder ikke.
Så for å sortere åtte elementer, jeg først sortere den venstre halvdelen av elementer
så jeg sortere høyre halvdel, så jeg flette de to sorterte halvdeler, hver på størrelse 4.
OK.
>> Men hvis du nettopp har fortalt meg, sortere venstre halvdel, som nå er i størrelse 4,
hvordan kan jeg sortere venstre halvdel?
Vel, hvis jeg har en input av fire elementer,
Jeg først sortere venstre to, så kan den riktige to,
og da jeg flette dem sammen.
Så igjen, blir det litt av et sinn bøying spillet her,
fordi du, hva slags, må huske hvor du er i historien,
men på slutten av dagen, gis hvilket som helst antall elementer
du først ønsker å sortere venstre halvdel, deretter høyre halvdel,
deretter flette dem sammen.
La oss begynne å gjøre akkurat det.
Her er inngangen av åtte elementer.
Nå vi ser på den venstre halvdelen her.
Hvordan sorterer fire elementene gjør?
Vel jeg først sortere venstre halvdel.
Nå hvordan kan jeg sortere venstre halvdel?
Vel jeg har fått to elementer.
Så la oss sortere disse to elementene.
2 er større enn eller lik 2, selvfølgelig.
Så det første tilfellet gjelder ikke.
>> Så jeg har nå til å sortere venstre halvparten av disse to elementer.
Venstre halvdel, selvfølgelig, er bare fire.
Så hvordan kan jeg sortere en liste over ett element?
Vel nå, at spesielle base case opp toppen, så å si, gjelder.
1 er mindre enn to, og min Listen er faktisk av størrelse 1.
Så jeg bare tilbake.
Jeg kan ikke gjøre noe.
Og ja, se på hva jeg har gjort, er fire allerede sortert.
Som jeg allerede delvis vellykket her.
>> Nå som virker litt dum krav, men det er sant.
4 er en liste over størrelse en.
Det er allerede sortert.
Det er den venstre halvdelen.
Nå har jeg sortere høyre halvdel.
Mitt innspill er ett element, 8 på samme måte, som allerede er sortert.
Dum, også, men igjen, Dette grunnleggende prinsippet
kommer til å tillate oss å nå bygge på toppen av dette med hell.
4 sorteres, 8 sorteres, nå hva var det siste trinnet?
Slik det tredje og siste trinnet, hvilken som helst gang du sortere en liste, husker,
var å slå sammen de to halvdelene, venstre og høyre.
Så la oss gjøre akkurat det.
Min venstre halvdel er, selvfølgelig, 4.
Min høyre halvdel er åtte.
>> Så la oss gjøre dette.
Først skal jeg fordele noen ekstra minne,
at jeg skal representere her, som bare en sekundær array,
som er stor nok til å passe dette.
Men du kan forestille deg å utvide at rektangelet hele lengden,
hvis vi trenger mer senere.
Hvordan tar jeg 4 og 8, og flette disse to lister med størrelse 1 sammen?
Også her ganske enkel.
4 kommer først, så kommer 8.
Fordi hvis jeg ønsker å sortere venstre halvdel, deretter høyre halvdel,
og deretter fusjonere de to halvdelene sammen, i sortert orden,
4 kommer først, så kommer 8.
>> Så vi synes å være å gjøre fremgang, selv selv om jeg ikke har gjort noe faktisk arbeid.
Men husk hvor vi er i historien.
Vi opprinnelig tok åtte elementer.
Vi sortert venstre halvdel, som er 4.
Da vi sortert venstre halvdel av den venstre halvdelen, som var to.
Og her vi går.
Vi er ferdig med dette trinnet.
>> Så hvis vi har sortert venstre halvdel av 2, nå er vi
å sortere den høyre halvdel av to.
Så høyre halvdel av 2 er disse to verdier her, 6 og 2.
Så la oss nå ta en inngang på størrelse 2, og sortere den venstre halvdelen, og deretter
høyre halvdel, og deretter flette dem sammen.
Vel hvordan kan jeg sortere en liste over størrelse 1, som inneholder bare antall 6?
Jeg er allerede gjort.
Denne listen av størrelse 1 er sortert.
>> Hvordan jeg sortere trenger en annen liste over størrelse 1, den såkalte høyre halvdel.
Vel det også, er allerede sortert.
Tallet 2 er alene.
Så nå har jeg to halvdeler, venstre og rett, jeg trenger å flette dem sammen.
La meg gi meg selv litt ekstra plass.
Og sette to der inne, 6 så der derved
sortering den listen, venstre og høyre, og sammenslåing det sammen til slutt.
Så jeg er i litt bedre form.
Jeg er ikke ferdig, fordi klart 4, 8, 2, 6 er ikke den endelige bestilling som jeg ønsker.
Men jeg har nå to lister med størrelse 2, som har begge, henholdsvis, er sortert.
Så nå hvis du spole tilbake i ditt indre øye, hvor ble det oss?
Jeg startet med åtte elementer, så jeg whittled det ned til den venstre halvdelen av fire,
Da den venstre halvdelen av to, og Da den høyre halvdel av 2,
Jeg er ferdig, derfor, sortering venstre halvparten av to, og den høyre halvdel av 2,
så hva er den tredje og siste trinnet her?
Jeg må flette sammen to lister med størrelse 2.
Så la oss gå videre.
Og på skjermen her, gi meg noen ekstra minne,
om teknisk, merker at jeg har fikk en hel haug med blank plass opp toppen
der.
Hvis jeg ønsker å være spesielt effektiv plass klokt,
Jeg kunne bare begynne å bevege elementene frem og tilbake, topp og bunn.
Men bare for visuell klarhet, Jeg kommer til å legge det ned nedenfor,
å holde ting rent og pent.
>> Så jeg har to lister med størrelse 2.
Den første listen har fire og åtte.
Den andre listen har to og seks.
La oss slå dem sammen i sortert rekkefølge.
2, selvsagt, kommer først deretter 4, deretter seks, deretter åtte.
Og nå vi synes å være å få et sted interessant.
Nå har jeg sortert halvdel av liste, og tilfeldigvis er det
alle partall, men det er faktisk bare en tilfeldighet.
Og jeg har nå sortert venstre halvparten, slik at den er 2, 4, 6, og 8.
Ingenting er ute av drift.
Det føles som pågår.
>> Nå føles det som jeg har snakket alltid nå,
så hva gjenstår å se om dette Algoritmen er faktisk mer effektivt.
Men vi går igjennom det super metodisk.
En datamaskin, selvfølgelig, ville gjøre det sånn.
Så hvor er vi?
Vi startet med åtte elementer.
Jeg sortert venstre halvdel av fire.
Jeg synes å bli ferdig med det.
Så nå neste steg er å sortere høyre halvdel av fire.
Og denne delen kan vi gå gjennom en litt mer
raskt, selv om du er Velkommen til spole eller ta pause, bare
tenke gjennom det på ditt eget tempo, men hva
vi har nå er en mulighet til å gjøre akkurat det samme algoritme på fire
forskjellige numre.
>> Så la oss gå videre, og fokus på høyre halvdel, som vi er her.
Den venstre halvdel av denne høyre halvdel, og nå
venstre halvdel av venstre halvparten av det høyre halvdel,
og hvordan kan jeg sortere en liste over størrelse En inneholdende bare antall 1?
Det er allerede gjort.
Hvordan gjør jeg det samme for en liste av størrelse 1 inneholder bare 7?
Det er allerede gjort.
Trinn tre for halvparten så er å slå sammen disse to elementene
inn en ny liste over størrelse 2, 1 og 7.
Synes ikke å ha gjort alt at mye interessant arbeid.
La oss se hva som skjer videre.
Jeg bare sortert venstre halvdel av høyre halvdel av mitt opprinnelige innspill.
Nå la oss sortere riktig halvparten, som inneholder fem og tre.
La oss igjen se på venstre halvparten, sortert, høyre halvdel, sortert,
og flette de to sammen, inn noen ekstra plass,
3 kommer først, så kommer 5.
Og så nå har vi sortert venstre halvdel av den høyre halvdel
av det opprinnelige problem, og den høyre halvdel av den høyre halvdel
av det opprinnelige problem.
Hva er den tredje og siste trinn?
Vel å slå sammen de to halvdelene sammen.
Så la meg få meg noen ekstra plass, men igjen, jeg
kan bruke de ledig plass opp toppen.
Men vi kommer til å holde det enkelt visuelt.
La meg slå sammen i nå ett, og deretter tre, og deretter 5, og deretter 7.
Dermed forlate meg nå med høyre halvparten av det opprinnelige problem
som er perfekt sortert.
>> Så hva gjenstår?
Jeg føler at jeg holder å si det samme tingene igjen og igjen,
men det er reflekterende av At vi bruker rekursjon.
Prosessen med å bruke en algoritme igjen, og igjen,
på mindre undergrupper av det opprinnelige problemet.
Så jeg har nå en venstre sortert halvparten av det opprinnelige problem.
Jeg har rett sortert halvparten av det opprinnelige problem.
Hva er den tredje og siste trinnet?
Åh, det er sammenslåing.
Så la oss gjøre det.
La oss sette av litt ekstra minne, men min Gud, vi
kunne sette den hvor som helst nå.
Vi har så mye ledig plass til oss, men vi vil holde det enkelt.
Istedenfor å gå tilbake og frem med vår opprinnelige minne,
la oss bare gjøre det visuelt ned her nedenfor,
til slutt opp sammenslåing venstre halvdel og høyre halvdel.
>> Så ved å slå sammen, hva må jeg gjøre?
Jeg ønsker å ta elementene i orden.
Så se på venstre halvdel, Jeg ser det første tallet er 2.
Jeg ser på høyre halvdel, Jeg ser det første tallet
er en, så åpenbart som nummer ønsker jeg å rykke ut,
og satt først i min endelige listen?
Selvfølgelig, 1.
Nå ønsker jeg å stille det samme spørsmålet.
På venstre halvdel, har jeg likevel fikk nummer 2.
På den høyre halvdel, Jeg har fått nummer tre.
Hvem av dem vil jeg skal velge?
Selvfølgelig, nummer 2 og nå merke kandidatene
er fire på venstre side, 3 på høyre side.
La oss, selvfølgelig, velger tre.
Nå kandidatene er fire på venstre, fem på høyre side.
Vi selvsagt velge fire.
6 på venstre, fem på høyre side.
Vi selvsagt velge fem.
6 på venstre side, 7 til høyre.
Vi velger seks, og da vi velge 7, og da velger vi åtte.
Voila.
>> Så et stort antall ord senere, vi har sortert denne listen over åtte elementer
inn i en liste over en gjennom åtte, som er økende med hvert trinn,
men hvor mye tid gjorde det tar oss å gjøre det.
Vel jeg har bevisst Laid ting ut billedlig
her, slik at vi kan slags se eller sette pris på divisjon
i erobrende som har skjedd.
>> Faktisk hvis du ser tilbake på kjølvannet, Jeg har forlatt alle disse stiplede linjene
i aliaser, kan du, slags, se, i omvendt rekkefølge,
hvis du slags se tilbake på historie nå, min opprinnelige liste
er, selvfølgelig, av størrelse 8.
Og så tidligere, var jeg arbeider med to lister med størrelse 4,
og deretter fire lister med størrelse 2, og deretter åtte lister over størrelsen 1.
>> Så hva gjør dette, slags, minne deg om?
Vel, ja, noen av algoritmene vi har
sett på så langt der vi dividere og dividere og dele,
holde å ha ting på nytt, og igjen, resulterer i denne generelle ideen.
Og så er det noe logaritmisk skjer her.
Og det er ikke helt logg over n, men det er en logaritmisk komponent
til det vi nettopp har gjort.
>> Nå la oss vurdere hvordan det faktisk er.
Så logger av n, igjen var en stor kjører tid,
når vi gjorde noe sånt binære søk, som vi nå kaller det,
skillet og hersk-strategi via som vi fant Mike Smith.
Nå teknisk.
Det er log base 2 av n, selv men i de fleste matematikk klasser,
10 er vanligvis basen som du antar.
Men dataforskere nesten alltid tenker og snakker i form av base 2,
så vi vanligvis bare si logg over n, i stedet for log base 2 av n,
men de er akkurat ett og samme i verden av datamaskinen
vitenskap, og som en side, det er en konstant faktor
Forskjellen mellom de to, slik at den er Moot uansett, for mer formelle grunner.
>> Men for nå, hva vi bryr oss om er dette eksempelet.
Så la oss ikke bevise ved eksempel, men på Minst bruke et eksempel av tallene
på hånden som en mental helse sjekk, hvis du vil.
Så tidligere formelen var log basen 2 av n, men hva er n i dette tilfellet.
Jeg hadde n opprinnelige tall, eller 8 av opprinnelige nummeret spesifikt.
Nå har det vært en liten stund, men jeg er ganske
sikker på at log base 2 av verdien 8 er 3,
og ja, det er fint om det er 3 er det nøyaktig antall ganger
at du kan dele opp en liste av lengde 8 igjen, og igjen,
og igjen, helt til du sitter igjen med lister over bare størrelse 1.
Høyre?
8 går til 4, går til to, går til en, og det er
reflekterende av akkurat det Bildet vi hadde bare et øyeblikk siden.
Så litt sunn fornuft sjekk om hvor logaritmen er faktisk involvert.
>> Så nå, hva annet er involvert her? n.
Så merker at hver gang jeg dele listen,
riktignok i omvendt rekkefølge i historien her, var jeg fortsatt gjør n ting.
At sammenslåing trinnet kreves at Jeg berører hver og en av tallene,
for å skyve den inn dens passende plassering.
Så selv om høyden av denne diagrammet er av størrelse log n av n eller 3,
spesifikt, med andre ord, Jeg gjorde tre divisjoner her.
Hvor mye arbeid har jeg gjort horisontalt langs denne oversikten hver gang?
>> Vel, jeg gjorde n trinnene fungere, fordi hvis jeg har
fikk fire elementer og fire elementer, og jeg trenger å flette dem sammen.
Jeg trenger å gå gjennom disse fire og disse fire,
slutt å flette dem tilbake i åtte elementer.
Hvis omvendt Jeg har åtte fingre over her, som jeg ikke gjør det, og åtte
fingers-- sorry-- Hvis jeg har fikk fire fingre over her,
som jeg gjør, fire fingre over her, som jeg gjør,
så det er det samme eksempel som før, hvis jeg gjør
har åtte fingre skjønt i totalt, som jeg kan, på en måte, gjør.
Jeg kan egentlig gjøre her, Da kan jeg sikkert
flette alle disse listene av størrelse 1 sammen.
Men jeg absolutt må se på hvert element nøyaktig en gang.
Slik at høyden på denne prosessen er log n, bredden av denne prosessen, så å si,
er n, så hva vi synes å ha, til slutt, er
en spilletid på størrelse n ganger log n.
>> Med andre ord, vi delt listen, log n ganger,
men hver gang vi gjorde det, hadde vi å berøre hver og en av elementene
for å slå dem sammen alle sammen, noe
ble n skritt, så vi har n ganger log n, eller som en datamaskin vitenskapsmann ville si,
asymptotisk, som ville være store ord
for å beskrive den øvre bundet på en driftstid,
vi kjører i en stor o log n tid, så å si.
>> Nå er dette viktig, fordi huske hva de kjører ganger var
med boble sortere og utvalg sortere og innsetting sortere,
og enda et par andre som eksisterer, n squared var der vi var på.
Og du kan, på en måte, ser dette her.
Hvis n squared er åpenbart n ganger n, men her har vi n ganger log n,
og vi vet allerede fra uke null, som log n, logaritmisk,
er bedre enn noe lineær.
Tross alt, husker bildet med den røde og den gule
og de grønne linjer som vi trakk, den grønn logaritmisk linje var mye lavere.
Og derfor mye bedre og raskere enn de rette gule og røde linjer,
n ganger log n er faktisk bedre enn n ganger n eller n kvadrat.
>> Så vi synes å ha identifisert en algoritme merge
sorter som går i mye raskere tid, og ja,
det er derfor, tidligere denne uken, da vi så at konkurransen mellom boble
sortere, utvalg sortere og flette sortere, fusjonere slags virkelig, virkelig vunnet.
Og ja, vi hadde ikke engang vente for boble sortere og utvalg sort
å bli ferdig.
>> La oss nå ta en annen pass på dette, fra en litt mer
formell perspektiv, bare i tilfellet, resonerer dette bedre
enn det høyere nivå diskusjon.
Så her er algoritmen igjen.
La oss spørre oss selv, hvilken kjøretiden
er av denne algoritmer forskjellige trinn?
La oss dele det inn i den første saken og det andre tilfellet.
IF og ellers i IF fall IF n er mindre enn to, bare tilbake.
Føles som konstant tid.
Det er, på en måte, som to trinn, IF n er mindre enn to, så tilbake.
Men som vi sa på mandag, konstant tid, eller store o av en,
kan være to trinn, tre trinn, og med 1.000 trinn.
Det som betyr noe er at det er et konstant antall skritt.
Så den gule uthevet pseudo her går i, vi kaller det,
konstant tid.
Så mer formelt, og vi kommer to-- dette
vil være i hvilken grad vi formalisere denne retten now-- T av n,
kjøretiden til et problem som tar n somethings som input,
tilsvarer stort o av en, IF n er mindre enn to.
Så det er betinget av det.
Så for å være klar, IF n er mindre enn 2, har vi en veldig kort liste, deretter
driftstiden, T av n, hvor n er 1 eller 0, i dette svært spesifikke tilfellet,
det bare kommer til å være konstant tid.
Det kommer til å ta ett trinn, to trinn, uansett.
Det er et bestemt antall trinn.
>> Så saftig del må sikkert være i det andre tilfellet i pseudokode.
Den ELSE tilfelle.
Sorter venstre halvdel av elementer, liksom rett halvparten av elementer, fusjonere sorterte halvdeler.
Hvor lang tid tar hver av disse trinnene?
Vel, hvis driften tid til å sortere n elementer
er, la oss kalle det veldig generisk, T n;
deretter sortering venstre halvparten av elementene
er, på en måte, som å si, T n dividert med 2,
og tilsvarende sortering høyre halvdel av elementer er, på en måte, som å si,
T n oppdelt 2, og deretter sammenslåing av sortert halvdeler.
Vel, hvis jeg har fått noen antall elementer her,
som fire, og et antall av elementer her, som fire,
og jeg må flette hver av disse fire i, og hver av disse fire i, ett
etter den andre, slik at slutt Jeg har åtte elementer.
Det føles som det er stor o av n trinn?
Hvis jeg har fått n fingre og hver av dem har til å bli slått sammen på plass,
det er som en annen n trinn.
>> Så ja formulaically, Vi kan uttrykke dette,
riktignok litt skremmende i starten øyekast, men det er noe
som fanger opp akkurat det logikk.
Kjøretiden, T for n, IF n er større enn eller lik 2.
I dette tilfellet, ELSE tilfellet er T n dividert med to, i tillegg til T av N dividert med 2,
pluss store o n, noen lineær antall skritt,
kanskje akkurat n, kanskje 2 ganger n, men det er omtrent, orden n.
Så det også, er hvordan vi kan uttrykke dette formulaically.
Nå trenger du ikke ville vite dette med mindre du har spilt det i tankene dine,
eller slå det opp i baksiden av en lærebok, som
kan ha litt jukse ark på slutten,
men dette er faktisk kommer til å gi oss en stor o n log n,
fordi gjentakelse som du ser her på skjermen,
hvis du faktisk gjorde det ut, med et uendelig antall eksempler,
eller du gjorde det formulaically, ville du se at dette, fordi denne formelen
selv er rekursiv, med t av n over noe på høyre side,
og t av N over på venstre side, kan dette faktisk bli uttrykt, til slutt,
som store go n log n.
Hvis ikke overbevist, det er greit for nå, bare
ta på tro, at det er, ja, hva som gjentakelse fører til,
men dette er bare litt mer av en matematisk tilnærming til jakt
på kjøretiden til merge sort basert på sin pseudokode alene.
>> Nå la oss ta en bit av en pusterom fra alt dette,
og ta en titt på en viss tidligere senator, som
kan se litt kjent, som satte seg ned med Googles Eric
Schmidt, en tid siden, for et intervju på scenen, foran en hel haug
mennesker, snakke til slutt om et tema, det er ganske nå kjent.
La oss ta en titt.
>> Eric Schmidt: Nå Senator, du er her på Google,
og jeg liker å tenke på formannskapet som et jobbintervju.
Nå er det vanskelig å få en jobb som president.
PRESIDENT OBAMA: Høyre.
Eric Schmidt: Og du er kommer til å gjøre [uhørbart] nå.
Det er også vanskelig å få en jobb på Google.
PRESIDENT OBAMA: Høyre.
>> Eric Schmidt: Vi har spørsmål, og vi ber våre kandidater spørsmål,
og dette er fra Larry Schwimmer.
>> PRESIDENT OBAMA: OK.
>> Eric Schmidt: Hva?
Dere tror jeg tuller?
Det er rett her.
Hva er den mest effektive måten å sortere en million 32 bits heltall?
>> PRESIDENT OBAMA: samt--
Eric Schmidt: Noen ganger, kanskje jeg er lei meg, maybe--
PRESIDENT OBAMA: Nei, nei, nei, nei, nei, think-- jeg
Eric Schmidt: Det er ikke it--
PRESIDENT OBAMA: I tror, ​​jeg tror boblen
sorter ville være feil vei å gå.
Eric Schmidt: Kom igjen.
Som fortalte ham dette?
OK.
Jeg gjorde ikke det informatikk on--
>> PRESIDENT OBAMA: Vi har fikk våre spioner der inne.
PROFESSOR: All right.
La oss legge bak oss nå teoretisk verden av algoritmer
i asymptotisk analyse av disse, og gå tilbake til noen temaer
fra uke null og én, og start å fjerne noen trening hjul,
Hvis du vil.
Slik at du virkelig forstår til slutt opp fra grunnen av, hva er
skjer under panseret, når du skrive, kompilere og kjøre programmer.
Husker spesielt at dette var den første C-programmet vi så på,
en kanonisk, enkelt program slags, relativt sett,
hvor, det skrives, Hello World.
Og husker at jeg sa, prosessen at kildekoden går gjennom
er akkurat dette.
Du tar din kildekode, pass det gjennom en kompilator, som klang,
og ut kommer objektkode, som kan se ut som dette, nuller og enere
at datamaskinens CPU, sentral processing unit eller hjerne,
slutt forstår.
>> Det viser seg at det er en litt av en overforenkling,
at vi er nå i en posisjon til å erte hverandre
å forstå hva som egentlig vært skjer under panseret
hver gang du kjører Klang, eller mer generelt,
hver gang du gjør et program, bruker Lag og CF 50 IDE.
Spesielt ting som dette er første generert,
når du først kompilere programmet.
Med andre ord, når ta kildekoden
og kompilere den, hva er første blir sendt ut av klang
er noe som kalles montering kode.
Og faktisk, det ser ut akkurat som dette.
>> Jeg kjørte en kommando på kommandolinje tidligere.
Klang dash kapital s hello.c, og dette har skapt en fil
for meg kalt hello.s, Innsiden var akkurat
dette innholdet, og litt mer over og litt under,
men jeg har satt den saftigste informasjon her på skjermen.
Og hvis du ser nøye etter, vil du se minst et par kjente søkeord.
Vi har hoved på toppen.
Vi har printf ned i midten.
Og vi har også hello world backslash n i anførselstegn ned nedenfor.
>> Og alt annet her er svært lave nivå instruksjoner
at datamaskinens CPU forstår.
CPU instruksjoner som beveger minne rundt, som laster strenger fra minnet,
og til slutt, print ting på skjermen.
Nå hva som skjer om etter denne forsamlingen kode genereres?
Til syvende og sist, gjør du, ja, fortsatt genererer objektkode.
Men trinnene som har virkelig pågått under panseret
ser litt mer ut som dette.
Kildekode blir montering kode, som deretter blir objektkode,
og de operative ord her er det, når du kompilere kildekoden,
ut kommer montering kode, og deretter når du monterer montering kode,
ut kommer objektkode.
>> Nå klang er super sofistikert, som mange kompilatorer,
og det gjør alle disse trinnene sammen, og det gjør ikke nødvendigvis
utgang mellomliggende filer som du selv kan se.
Det kompilerer bare ting, som er den generelle betegnelsen som
beskriver hele denne prosessen.
Men hvis du virkelig ønsker å være særlig, er det
mye mer å gå på der også.
>> Men la oss også vurdere nå at selv at super enkelt program, hello.c,
kalles en funksjon.
Det kalles printf.
Men jeg skrev ikke printf, ja, som følger med c, så å si.
Det er en funksjon tilbakekalling som er deklarert i standard io.h, som
er en header fil, som er et tema vi faktisk
dykke mer i dybden før lenge.
Men en header fil vanligvis ledsaget
av en kode fil, kildekode fil, så mye som det finnes standard io.h.
>> Gang siden, noen, eller vekke, skrev også
en fil som heter standard io.c, i som selve definisjonene,
eller implementeringer av printf, og bunter av andre funksjoner,
er faktisk skrevet.
Så gitt at, hvis vi vurdere å ha her til venstre, hello.c, at når
utarbeidet, gir oss hello.s, selv om Klang ikke bry besparelse på et sted
vi kan se det, og at forsamlingen kode blir satt sammen til hello.o, som
er faktisk standardnavnet gitt når du kompilere kilde
kode til objektkode, men er ikke helt klar til å kjøre den ennå,
fordi et nytt skritt må skje, og har
foregått de siste par uker, kanskje ukjent for deg.
>> Spesifikt sted i CS50 IDE, og dette,
også vil være litt av en forenkling for et øyeblikk,
det er, eller var en gang, en fil som heter standard io.c,
at noen kompilert inn standard io.s eller tilsvarende,
at noen deretter satt sammen inn standard io.o,
eller det viser seg i en litt annen fil
format som kan ha en annen filtypen helt,
men i teorien og konseptuelt, nøyaktig disse trinnene måtte skje i en eller annen form.
Som er å si, at nå når jeg skriver et program,
hello.c, som bare sier hei verden, og jeg bruker noen andres kode
som printf, som var en gang i tid, i en fil som heter standard io.c,
så en eller annen måte må jeg ta min objektkode, mine nuller og enere,
og at personens objekt kode, eller nuller og enere,
og liksom koble dem sammen til en siste fil, kalt hallo, at
har alle de nuller og de fra min hovedfunksjon,
og alle nuller og de for printf.
>> Og ja, det er siste ferd heter, linke din objektkode.
Utgangen fra hvilken er en kjørbar fil.
Så i rettferdighet, på slutten av dagen, noe
har endret seg siden uke en, når vi først begynte å kompilere programmer.
Faktisk har alt dette vært skjer under panseret,
men nå er vi i en posisjon hvor vi faktisk kan
erte hverandre disse ulike trinnene.
Og faktisk, på slutten av dagen, vi er fortsatt
igjen med nuller og enere, som er faktisk en fin naturlig overgang nå
til et annet evnen til C, som vi har ikke hatt til å utnytte mest sannsynlig
til dags dato, kjent som bitvis operatører.
Med andre ord, så langt, når som helst vi har jobbet med data i C eller variabler i C,
vi har hatt ting som chars og flyter og ins
og lengter og dobler og lignende, men alle av dem er minst åtte bits.
Vi har aldri ennå ikke vært i stand til å manipulere individuelle biter,
selv om en individuell bit, vi vet, kan representere en 0 og 1.
Nå viser det seg at i C, du kan få tilgang til enkelte biter,
hvis du vet syntaks, med å få på dem.
>> Så la oss ta en titt på bitvis operatører.
Så avbildet her er noen symboler som vi har, type, liksom, sett før.
Jeg ser en ampersand, en vertikal bar, og noen andre også,
og husker at ampersand-tegn er noe vi har sett før.
Den logiske AND operatør, hvor du har to av dem sammen, eller den logiske OR
operatør, hvor du har to loddrette streker.
Bitvis operatører, som vi vil se operere på bitene hver for seg,
bare bruke en enkelt-tegn, en enkelt vertikal bar, cirkumflekstegnet symbol
kommer etterpå, den lille tilde, og deretter til venstre
brakett venstre brakett, eller høyre brakett høyre brakett.
Hver av disse har forskjellige betydninger.
>> Faktisk, la oss ta en titt.
La oss gå gamle skolen i dag, og bruk en berøringsskjerm fra en svunnen tid,
kjent som en hvit bord.
Og denne hvite bord kommer til å tillate oss
å uttrykke noen ganske enkle symboler, eller rettere sagt noen ganske enkle formler,
at vi kan så til slutt innflytelse, for
å få tilgang til enkelte bits innenfor et C-program.
Med andre ord, la oss gjøre dette.
La oss først snakke om en øyeblikk om ampersand,
som er bitvis AND operatør.
Med andre ord er denne en operatør som gjør det mulig
meg å ha en venstre variabel typisk, og en høyre variabel,
eller en enkeltverdi, at hvis vi AND dem sammen, gir meg et endelig resultat.
Så hva mener jeg?
Hvis du er i et program, har du en variabel som lagrer en av disse verdiene
eller la oss holde det enkelt, og bare skrive ut nuller og enere individuelt,
her er hvordan tegnet operatør fungerer.
0 tegnet 0 kommer til å like 0.
Nå hvorfor er det?
>> Det er svært lik Boolske uttrykk,
at vi har diskutert så langt.
Hvis du tror tross alt, er det 0 falsk, er falsk, falsk og usann 0
er, som vi har diskutert logisk, også falske.
Så vi får 0 her også.
Hvis du tar 0-tegn 1, vel det også,
kommer til å være 0, fordi for dette venstre uttrykk for å være sanne eller 1,
det må være sant og ekte.
Men her har vi false og sant, eller 0 og 1.
Nå igjen, hvis vi har en ampersand 0, som også kommer til å være 0,
og hvis vi har en ampersand 1, endelig har vi en 1 bit.
Så med andre ord, vi ikke gjør noe interessant med denne operatøren
ennå, dette tegnet operatør.
Det er bitvis AND operatør.
Men disse er ingrediensene via som vi kan gjøre
interessante ting, som vi snart se.
>> La oss nå se på akkurat enkelt vertikale linjen over her til høyre.
Hvis jeg har en 0 bit og jeg ELLER den med, bitvis
OR operatør, en annen 0 bit, som kommer til å gi meg 0.
Hvis jeg tar en 0 bit og OR det med en 1 bit, så jeg kommer til å få en.
Og faktisk, bare for klarhet, la meg gå tilbake,
slik at mine vertikale linjene ikke forveksles med en s.
La meg omskrive alle min en er litt mer
tydelig, slik at vi neste ser, hvis jeg har en 1 eller 0, som kommer til å være en 1,
og hvis jeg har en 1 eller en som, også, kommer til å bli en en.
Så du kan se logisk at OR operatør oppfører seg veldig annerledes.
Dette gir meg 0 ELLER 0 gir meg 0, men annenhver kombinasjonen gir meg en.
Så lenge jeg har en 1 i formel, er resultatet vil være en.
>> I motsetning til AND operatør,-tegnet,
bare hvis jeg har to 1-er i ligningen, jeg faktisk får en en ut.
Nå er det et par andre operatører.
En av dem er litt mer involvert.
Så la meg gå videre og slette dette for å frigjøre litt plass.
Og la oss ta en titt på caret symbol, for bare et øyeblikk.
Dette er typisk en tegn du kan skrive
på tastaturet holding Shift og deretter ett av tallene oppå din US
tastatur.
>> Så dette er den eksklusive OR operatør, eksklusive ELLER.
Så vi bare så ELLER operatør.
Dette er den eksklusive operatoren OR.
Hva er egentlig forskjellen?
Vel la oss bare se på formelen, og bruke dette som ingredienser til slutt.
0 XOR 0.
Jeg kommer til å si er alltid 0.
Det er definisjonen av XOR.
0 XOR en kommer til å være en.
1 XOR 0 kommer til å bli en, og en XOR en kommer til å være?
Galt?
Eller rett?
Jeg vet ikke.
0.
Nå hva som skjer her?
Vel tenke på Navnet på denne operatøren.
Eksklusive ELLER-, så som navn, foreslår,
Svaret er bare kommer til å være en 1 hvis inngangene er eksklusiv,
utelukkende annerledes.
Så her inngangene er samme, slik at produksjonen er 0.
Her inngangene er samme, slik at produksjonen er 0.
Her er de utgangene er forskjellige, de er eksklusive, og slik at produksjonen er en.
Så det er svært lik OG, det er veldig likt,
eller rettere sagt det er svært lik OR, men bare i en eksklusiv måte.
Dette er ikke lenger en 1, fordi vi har to 1-tallet,
og ikke utelukkende, bare en av dem.
Greit.
Hva med de andre?
Vel tilde, i mellomtiden, er faktisk fin og enkel, heldigvis.
Og dette er en enhetlige Operatøren, som betyr
det er påført bare en inngang, én operand, så å si.
Ikke til en venstre og en til høyre.
Med andre ord, hvis du tar tilde av 0, vil svaret være det motsatte.
Og hvis du tar tilde av en, den Svaret vil det være motsatt.
Så tilde operatør er en måte å benektende litt,
eller bla litt fra Fra 0 til 1 eller 1 til 0.
>> Og som etterlater oss til slutt med bare to endelige operatører,
den såkalte venstre skift, og såkalte høyre shift operatør.
La oss ta en titt på hvordan de arbeidet.
Den venstre skifte operatør skrevet med to vinkelparenteser som det,
virker som følger.
Hvis mitt innspill, eller min operand, til venstre skifte operatør er ganske enkelt en en.
Og jeg da fortelle datamaskinen til venstre skift som en, sier syv plasser,
resultatet er som om jeg ta det en, og flytt den
syv steder i løpet av venstre, og som standard,
vi kommer til å anta at rom til høyre
kommer til å være polstret med nuller.
Med andre ord, en venstre shift 7 kommer å gi meg at 1, fulgt av 1, 2, 3,
4, 5, 6, 7 nuller.
Så på en måte, det kan du ta et lite tall som 1,
og tydelig gjør det mye mye, mye større på denne måten
men vi er faktisk kommer til å se mer smarte tilnærminger for det
i stedet, samt,
>> Greit.
Det er det for uke tre.
Vi vil se deg neste gang.
Dette var CS50.
>> [MUSIC SPILLE]
>> SPEAKER 1: Han var på snack bar spise en hot fudge sundae.
Han hadde det over hele ansiktet hans.
Han har på seg at sjokolade som et skjegg
SPEAKER 2: Hva er det du gjør?
SPEAKER 3: Hmmm?
Hva?
>> SPEAKER 2: Visste du bare dobbel dip?
Du dobbelt dyppet brikken.
SPEAKER 3: Unnskyld meg.
SPEAKER 2: Du dyppet chip, du tok en bit, og du dyppet igjen.
SPEAKER 3:
SPEAKER 2: Så det er som å sette hele munnen rett i dip.
Neste gang du tar en chip, bare dyppe det en gang, og avslutte den.
>> SPEAKER 3: Vet du hva, Dan?
Du dyppe den måten at du ønsker å dyppe.
Jeg skal dyppe den måten at jeg ønsker å dyppe.