>> [Musikk spilles]
DAVID MALAN: All right.
Greit, velkommen tilbake.
Så dette er Uke 4, begynnelsen derav, som allerede.
Og du husker at forrige uke, setter vi kode til side for bare litt
og vi begynte å snakke litt mer høyt nivå, om ting som
søking og sortering, som selv noe enkle ideer, er
representative for en klasse av problemene vil du begynne å løse spesielt
som du begynner å tenke på finalen prosjekter og interessante løsninger du
kanskje reelle problemer.
Nå boble sort ble en av de enkleste slike algoritmer, og det
arbeidet ved å ha disse små tall i en liste eller i en matrise slags
boble sin vei opp til toppen, og den store tallene beveger seg ned til
slutten av den listen.
>> Og husker at vi kunne visualisere boble sortere litt
noe sånt som dette.
Så la meg gå videre og klikk på Start.
Jeg har forhåndsvalgt boble slag.
Og hvis du husker at høyere blå linjer representerer store tall, små
blå linjene representerer små tall, som vi gå gjennom dette igjen og igjen og
igjen, sammenligne to barer ved siden av hver andre i rødt, vi kommer til å bytte
største og den minste hvis de er ute av drift.
>> Så dette vil gå på og gå på og gå på, og vil du se at større
elementer er på vei til høyre, og de mindre elementene er
på vei til venstre.
Men vi begynte å kvantifisere effektiviteten, den
Kvaliteten på denne algoritmen.
Og vi sa at i verste tilfelle, tok denne algoritmen
omtrent hvor mange skritt?
>> Så n kvadrat.
Og hva var n?
>> PUBLIKUM: Antall elementer.
>> DAVID MALAN: Så n var antall elementer.
Og så skal vi gjøre dette oftere.
Hver gang vi ønsker å snakke om størrelsen av et problem eller størrelsen på en
input, eller hvor lang tid det tar å produsere et resultat, vil vi bare
generalisert uansett inngangen er som n.
Så tilbake i uke 0, antall sider i telefonboken var n.
Antallet studenter i rommet var n.
Så også her, vi følger dette mønsteret.
>> Nå n squared er ikke spesielt fort, så vi prøvde å gjøre det bedre.
Og så har vi sett på et par andre algoritmer, blant annet
var valget slag.
Så valget slags var litt annerledes.
Det var nesten enklere, jeg tør si, der jeg startet på begynnelsen av
liste av våre frivillige, og jeg bare igjen og igjen og igjen gikk gjennom
listen, plukker ut den minste element om gangen og sette ham eller
henne på begynnelsen av listen.
>> Men også dette, når vi begynte å tenke gjennom matematikk og større
bilde, tenkt på hvor mange ganger Jeg går frem og tilbake og tilbake
og tilbake, sa vi i verste fall utvalg sortere, også, var det?
n squared.
Nå i den virkelige verden, kan det faktisk være marginalt raskere.
Fordi igjen, det gjorde jeg ikke å holde backtracking når jeg hadde sortert
minste elementene.
Men hvis vi tenker veldig stor n, og hvis du liksom gjøre ute regnestykket som
Jeg gjorde i styret, med n kvadrat minus noe, alt annet
foruten n kvadrat, når n blir veldig store, ikke
virkelig betyr så mye.
Så som dataforskere, sorterer vi av snu det blinde øyet til mindre
faktorer og fokusere bare på den faktoren i et uttrykk som kommer til å gjøre
den største forskjellen.
>> Vel, til slutt, så vi ved innsetting slag.
Og dette var lik i ånd, men heller enn å gå gjennom iterativt og
velge den minste elementet en om tid, jeg i stedet tok hånd som jeg
ble delt ut, og jeg bestemte meg, alle høyre, hører du her.
Da flyttet jeg videre til neste element og bestemte seg for at han eller
hun tilhørte her.
Og så flyttet jeg videre og videre.
Og jeg kan til, underveis, skifte disse gutta for å
gjøre plass til dem.
Så det var liksom den mentale reversering av utvalget typen som vi
kalt innsetting slag.
>> Så disse emnene å skje i den virkelige verden.
Bare et par år siden, da en viss senator kjørte for president,
Eric Schmidt, på det tidspunkt administrerende direktør i Google, faktisk hadde muligheten
å intervjue ham.
Og vi tenkte vi skulle dele denne YouTube klipp for deg her, hvis vi kunne slå opp
volumet.
>> [VIDEOAVSPILLING]
>> -Nå, Senator, du er her på Google, og jeg liker å tenke på formannskapet
som et jobbintervju.
>> [Latter]
>> -Nå er det vanskelig å få en jobb som president.
Og du går gjennom påkjenningene nå.
Det er også vanskelig å få en jobb hos Google.
Vi har spørsmål, og vi ber våre kandidater spørsmål.
Og dette er fra Larry Schwimmer.
>> [Latter]
-Dere tror jeg tuller?
Det er rett her.
Hva er den mest effektive måten å sortere en million to-bits heltall?
>> [Latter]
>> -Vel, uh -
>> -Jeg er lei for det.
Kanskje vi bør -
>> -Nei, nei, nei, nei, nei.
>> -Det er ikke en -
OK.
>> -Jeg tror boblen slags ville være feil vei å gå.
>> [Latter]
>> [Heier og applauderer]
>> -Kom igjen, som fortalte ham dette?
OK.
>> [END VIDEOAVSPILLING]
>> DAVID MALAN: Så det du har det.
Så vi begynte å kvantifisere disse kjører ganger, så å si, med noe
kalles asymptotisk notasjon, som er bare henvise til vår form for å snu
et blindt øye til de mindre faktorer og bare se på løpende tid,
utførelsen av disse algoritmene, som n blir veldig stor over tid.
Og så vi introduserte big O. Og big O representerte noe som vi trodde
på som en øvre grense.
Og faktisk, Barry, kan vi senke enn mic litt?
>> Vi tenkte på dette er en øvre grense.
Så stor O for n kvadrat betyr at i verste fall, noe som
utvalg slags ville ta n kvadrat trinn.
Eller noe sånt innsetting slags ville n kvadrat trinn.
Nå for noe sånt innsetting sortere, hva var det verste tilfellet?
Gitt en matrise, er det verste mulig scenario at du kan finne
selv møtt med?
>> Det er helt baklengs, ikke sant?
Fordi hvis det er helt baklengs, du trenger å gjøre en hel masse arbeid.
Fordi hvis du er helt baklengs, du kommer til å finne den
største momentet her, selv om det hører hjemme der nede.
Så du kommer til å si, all right, på dette øyeblikket i tid, hører du her,
så du la det være.
>> Så du skjønner, oh, faen, jeg må flytte denne litt mindre element til
venstre for deg.
Da må jeg gjøre det igjen og igjen og igjen.
Og hvis jeg gikk frem og tilbake, du ville liksom føle ytelsen
at algoritmen, fordi stadig er jeg shuffling alle andre ned i
array å gjøre plass til det.
Så det er det verste tilfellet.
>> I motsetning -
og dette var en cliffhanger siste gang -
vi sa at innsetting sortere var en omega av hva?
Hva er den best-case løping tidspunktet for innsetting slag?
Så det er faktisk n.
Det var tomt da vi forlot på brettet forrige gang.
>> Og det er omega for n fordi hvorfor?
Vel, i de aller beste fall, hva er innsetting sortere kommer til å bli levert?
Vel, en liste som er helt sortert allerede, minimalt arbeid å gjøre.
Men hva er ryddig om innsetting slags er det fordi det starter her og
bestemmer, oh, du er antall en, hører du her.
Oh, what a hell.
>> Du er nummer to.
Du hører også her.
Nummer tre, enda bedre, du hører hjemme her.
Så snart det blir til slutten av liste, per innsetting sortere sin pseudokode
at vi gikk gjennom verbalt siste gang, er det gjort.
Men utvalget sortere, derimot, holdt gjør hva?
>> Holdt gjennom listen igjen og igjen og igjen.
Fordi det viktig innsikt var det bare når du har sett hele veien til
slutten av listen kan du være sikker at elementet du valgte var
faktisk den tiden minste elementet.
Så disse forskjellige mentale modeller slutten opp gir noen svært virkelige verden
forskjeller for oss, samt disse teoretiske asymptotiske forskjeller.
>> Så bare for å gjenerobre, da, big O n kvadrat, har vi sett noen slike
algoritmer så langt.
Big O av n?
Hva er en algoritme som kunne sies å være big O av n?
I verste fall, det tar en lineær rekke trinn.
>> OK, lineær søk.
Og i verste fall, hvor er element du leter etter når
anvende lineær søk?
>> OK, i verste fall, det er ikke engang der.
Eller i det nest verste tilfelle, er det helt til slutt, noe som er
pluss-eller-minus en ett-trinns forskjell.
Slik på slutten av dagen, vi kan si at det er lineær.
Big O n ville være lineær søk, fordi i verste fall den
element er ikke engang der, eller det er helt på slutten.
>> Vel, big O av log n.
Vi snakket ikke i stor detalj om dette, men vi har sett dette før.
Hva kjører i såkalt logaritmisk tid, i verste fall?
>> Ja, så binære søk.
Og binære søk i verste fall kan ha element et sted i
midten, eller et sted inne i matrisen.
Men du bare finne det når du dele opp listen i to, i
halvparten, i to, i to.
Og så voila, det er der.
Eller igjen, verste fall det er ikke engang der.
Men du vet ikke at den ikke er der til du liksom nå det siste
nederste fleste elementene ved å halvere og halvere og halvere.
>> Big O av en.
Slik at vi kunne big O 2, big O av tre.
Når du vil bare et konstant tall, vi bare liksom bare forenkle
at så store O av en.
Selv om hvis realistisk, tar det 2 eller 100 skritt, hvis det er en
konstant antall skritt, vi bare si big O av en.
Hva er en algoritme som er i big O av en?
>> PUBLIKUM: Finne lengden av en variabel.
>> DAVID MALAN: Finne Lengden av en variabel?
>> PUBLIKUM: Nei, lengden hvis det er allerede sortert.
>> DAVID MALAN: Good.
OK, så å finne lengden på noe Hvis lengden av det noe i likhet
en matrise, er lagret på en eller annen variabel.
Fordi du kan bare lese variabel, eller skrive ut variabelen, eller
bare generelt få tilgang til variabelen.
Og voila, som tar konstant tid.
>> Derimot, tenker tilbake til scratch.
Tenk tilbake til den første uken i C, ringer bare printf og utskrift
noe på skjermen er uten tvil konstant tid, fordi det tar bare
noen antall CPU-sykluser for å vise som tekst på skjermen.
Eller vent - gjør det?
Hvordan ellers kan vi modellere utførelsen av printf?
Vil noen liker å være uenige, at kanskje det er egentlig ikke konstant tid?
På hvilken måte kan printf kjører tid, faktisk skrive en streng på
skjermen, være noe annet enn konstant.
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Yeah.
Så det kommer an på vårt perspektiv.
Hvis vi faktisk tenker på innspill til printf som strengen, og
derfor vi måle størrelsen av det inngang med lengde - så la oss kalle
at lengden n også -
uten tvil, er printf seg stor O n fordi det kommer til å ta deg n trinn
å skrive ut hver av de n tegn, mest sannsynlig.
I det minste i den grad at vi antar at kanskje den bruker en for loop
under hetten.
>> Men vi må se på det kode for å forstå det bedre.
Og ja, når dere starter analysere dine egne algoritmer, vil du
bokstavelig talt gjøre nettopp det.
Sortering av øyeeplet koden din og tenke om - all right, jeg har denne sløyfen
her eller jeg har en nestede løkker her, som kommer til å gjøre n ting n ganger,
og du kan sortere på grunn din måte gjennom koden, selv om den er
pseudokode og ikke selve koden.
>> Så hva med omega for n kvadrat?
Det var en algoritme som i beste tilfelle, likevel tok n kvadrat trinn?
Yeah?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Så utvalg slag.
Fordi i det problemet virkelig redusert til det faktum at igjen, jeg vet ikke
Jeg har funnet den nåværende minste inntil Jeg har sjekket alle darn elementer.
Så omega, sier n, vi bare kom opp med en.
Innsetting slag.
Hvis listen skjer skal sorteres allerede, i beste fall bare har vi
å gjøre en pasning gjennom det, på hvilket tidspunkt vi er sikker.
Og deretter som kan sies å være lineær, for sikker.
>> Hva med omega for en?
Hva, i beste fall, kan ta en konstant antall trinn?
Så lineær søk, hvis du bare få heldige og elementet du leter
er helt i begynnelsen av listen, Hvis det er der du starter din
lineær traversering av den listen.
>> Og dette er sant for en rekke ting.
For eksempel, selv binær Søket er omega for en.
For hva hvis du får virkelig darn heldig og smack-DAB i midten av
klyngen er antall du leter etter?
Så du kan ha flaks der, også.
>> Denne, til slutt, omega for n log n.
Så n log n, gjorde vi egentlig ikke snakke om ennå, men -
>> PUBLIKUM: Flett slag?
>> DAVID MALAN: Merge slag.
Det var den cliffhanger av siste gang, hvor vi foreslått, og vi viste
visuelt, at det er algoritmer.
Og flette liksom bare én slik algoritme som er fundamentalt raskere
enn noen av disse andre gutta.
Faktisk fusjonere kort er ikke bare i best case n log n, i verste
Ved n log n.
Og når du har denne sammentreff av omega og stor O er det samme?
Vi kan faktisk beskrive det som det er kalles theta, om det er en
litt mindre vanlig.
Men det betyr bare de to grenser, I dette tilfellet er de samme.
>> Så flette sortere, hva betyr dette egentlig koker ned til for oss?
Vel, husker motivasjon.
La meg trekke opp en annen animasjon som Vi så ikke på forrige gang.
Denne, samme idé, men det er litt større.
Og jeg kommer til å gå videre og påpeke første - vi har innsetting slag på
øverst til venstre, deretter valg sortere, boble sortere, et par andre former -
skall og rask - at vi ikke har snakket om, og heap og flette slag.
>> Så i det minste prøve å fokusere blikket på topp tre på venstre og deretter
flette slag når jeg klikker Dette grønn pil.
Men jeg skal la alle av dem kjøre, bare for å gi deg en følelse av mangfoldet i
algoritmer som finnes i verden.
Jeg kommer til å la denne kjøre for bare noen få sekunder.
Og hvis du fokuserer øynene dine - velg en algoritme, fokusere på det for bare en
sekunder - du vil begynne å se mønster som det er å implementere.
>> Flette sortere, varsel, er gjort.
Heap sortere, rask sortering, shell -
så det synes vi introduserte tre verste algoritmer forrige uke.
Men det er bra at vi er her i dag for å se på merge slag, som er en av
de enklere er å se på, selv selv om det trolig vil bøye sinn
bare en liten bit.
Her kan vi se hvor mye utvalg slags suger.
>> Men på baksiden, er det veldig lett å implementere.
Og kanskje for P Set 3, det er en av de algoritmer du valgte å implementere
for standardutgaven.
Helt greit, helt riktig.
>> Men igjen, som n blir stor, hvis du velge å gjennomføre en raskere algoritmen
liker flette sortere, oddsen er i større og større innganger, er koden bare
kommer til å kjøre fortere.
Ditt nettsted kommer til å fungere bedre.
Brukerne kommer til å være fornøyde.
Og så er det disse effektene av faktisk å gi
oss noen dypere trodde.
>> Så la oss ta en titt på hva fusjonere typen er faktisk handler om.
Det kule er at fusjonere typen er nettopp dette.
Dette er, igjen, det vi har kalt pseudokode, pseudokode vesen
Norsk-lignende syntaks.
Og enkelhet er slags fascinerende.
>> Så på input av n elementer - slik at betyr bare, her er en matrise.
Det har n ting i den.
Det er alt vi sier der.
>> Hvis n er mindre enn 2, tilbake.
Så det er bare den trivielle tilfelle.
Hvis n er mindre enn to, så åpenbart at det er 1 eller 0, i hvilket tilfelle tingen
er allerede sortert eller ikke-eksisterende, så bare komme tilbake.
Det er ingenting å gjøre.
Så det er en enkel sak å plukke av.
>> Else, vi har tre trinn.
Sortere venstre halvdel av elementene, sortere den høyre halvdel av elementene,
og deretter flette sortert halvdeler.
Det som er interessant her er at Jeg er litt punting, ikke sant?
Det er på en måte en sirkulær definisjon til denne algoritmen.
På hvilken måte er denne algoritmen er definition rundskrivet?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Ja, min sortering algoritme, to av sine trinnene er "slag
noe. "Og så trygler spørsmålet, vel, hva jeg kommer til å bruke
å sortere venstre halvdel og høyre halvdel?
Og det fine her er at selv om igjen, dette er mind-bending
del potensielt, kan du bruke samme algoritme for å sortere venstre halvdel.
>> Men vent litt.
Når du får beskjed om å sortere venstre halvdel, hva er de to
trinn kommer til å bli neste?
Vi vil sortere venstre halvdel av venstre halvdel og rett
halvparten av den venstre halvdel.
Damn, hvordan jeg sorterer disse to halvdeler, eller kvartaler, nå?
>> Men det er OK.
Vi har en sortering algoritme her.
Og selv om du kanskje bekymre deg i først dette er litt av en uendelig
loop, er det en syklus som aldri er kommer til å ende - det kommer til å
ende en gang hva som skjer?
Når n er mindre enn 2.
Som til slutt kommer til å skje, fordi hvis du holder halvere og
halvering i halvere disse halvdeler, sikkert slutt du kommer til å ende
opp med bare 1 eller 0 elementer.
På hvilket tidspunkt, denne algoritmen sier du er ferdig.
>> Så den virkelige magien i dette algoritmen synes å være i
at siste trinnet, sammenslåing.
Det enkle ideen bare sammenslåing to ting, det er det som til syvende og sist kommer
å tillate oss å sortere en rekke, la oss si, åtte elementer.
Så jeg har åtte stress baller opp her, åtte biter av papir, og en
Google Glass -
som jeg kommer til å holde.
>> [Latter]
>> DAVID MALAN: Hvis vi kunne ta åtte frivillige, og la oss se om vi kan
spille dette ut, så.
Wow, OK.
Informatikk blir gøy.
OK.
Så hva med deg tre, største hånden oppe.
Fire i ryggen.
Og hva vi vil gjøre deg tre i denne raden?
Og fire i front.
Så du åtte, kom igjen opp.
>> [Latter]
>> DAVID MALAN: Jeg er faktisk ikke sikker på hva det er.
Er det stress baller?
Skrivebord-lamper?
Materialet?
Internett?
>> OK.
Så kom igjen opp.
Hvem ønsker -
fortsette å komme opp.
La oss se.
Og dette setter deg i sted -
du er i stedet en.
Uh-oh, vent litt.
1, 2, 3, 4, 5, 6, 7 - OH, god.
Greit, vi er bra.
All right, slik at alle har en plass, men ikke på Google Glass.
La meg til kø opp disse.
Hva heter du?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Greit, du kommer til å se ut geek, hvis det er OK.
Vel, jeg gjør også, antar jeg, for bare et øyeblikk.
All right, standby.
Vi har prøvd å komme opp med en bruke saken for Google Glass, og vi
trodde det ville være morsomt å bare gjøre dette når folk er på scenen.
Vi vil dokumentere verden fra deres perspektiv.
OK.
Ikke nok hva Google ment.
Greit, hvis du ikke tankene iført dette for de neste pinlige minutter,
det ville være fantastisk.
>> Ok, så vi har her et utvalg av elementer, og at utvalg, som per
papirlapper i disse folkene ' hender, er for tiden usortert.
>> MICHELLE: Å, det er så rart.
>> DAVID MALAN: Det er ganske mye tilfeldig.
Og om en liten stund, kommer vi til å prøve å gjennomføre fusjonere slags sammen
og se hvor det viktig innsikt er.
Og trikset her med merge sort er noe som vi ikke har antatt ennå.
Vi må faktisk noen ekstra plass.
Så hva kommer til å være spesielt interessant med dette er at disse
Gutta kommer til å bevege seg litt litt, fordi jeg kommer til å anta at
det er et ekstra utvalg av plass, si, rett bak dem.
>> Så hvis de er bak stolen sin, det er den sekundære array.
Hvis de er satt her, er at den primære array.
Men dette er en ressurs som vi har ikke utnyttes så langt med boble
sortere, med utvalg sortere, med innsetting slag.
Recall forrige uke, alle bare slags stokket på plass.
De brukte ikke noe ekstra minne.
Vi gjorde plass for folk med flytte folk rundt.
>> Så dette er en viktig innsikt, også.
Det er denne avveiingen, generelt i informatikk, av ressurser.
Hvis du ønsker å fremskynde noe som tid, du kommer til
må betale en pris.
Og en av disse prisene er svært ofte plass, hvor mye minne eller hard
diskplass som du bruker.
Eller, ærlig talt, hvor mye av programmerer tid.
Hvor mye tid det tar deg, det menneskelige, å faktisk gjennomføre noen mer
komplisert algoritme.
Men for i dag, bytteforholdet er tid og rom.
>> Så hvis dere kunne bare holde opp tallene slik at vi kan se at du er
faktisk matchende 4, 2, 6, 1, 3, 7, 8.
Utmerket.
Så jeg kommer til å prøve å orkestrere ting, om dere kan bare
følge min bly her.
>> Så jeg kommer til å gjennomføre, først, første trinn i pseudokode, som er
på input av n elementer, hvis n er mindre enn to, så tilbake.
Selvfølgelig gjør det ikke lappeteppe, så vi går videre.
Så sorterer den venstre halvdelen av elementene.
Så det betyr at jeg kommer til å fokusere min oppmerksomhet for bare et øyeblikk på disse
fire gutta her.
Ok, hva gjør jeg neste gjøre?
>> PUBLIKUM: Sorter venstre halvdel.
>> DAVID MALAN: Så nå har jeg til å sortere den venstre halvdelen av disse gutta.
Fordi igjen, antar deg selv Målet er å sortere venstre halvdel.
Hvordan gjør dere det?
Bare følg instruksjonene, selv selv om vi gjør det igjen.
Så sorterer venstre halvdel.
Nå er jeg sortere disse to gutta.
Hva kommer etterpå?
>> PUBLIKUM: Sorter venstre halvdel.
>> DAVID MALAN: Sorter venstre halvdel.
Så nå disse, dette setet her, er en liste over størrelse 1.
Og hva heter du igjen?
>> PRINCESS DAISY: Princess Daisy.
>> DAVID MALAN: Princess Daisy er her.
Og så er hun allerede sortert, fordi listen er av størrelse 1.
Hva gjør jeg neste gjøre?
OK, tilbake, fordi den listen er av størrelse 1, som er mindre enn 2.
Så hva er neste steg?
Og nå må du slags Backtrack i tankene dine.
>> Sortere høyre halvdel, som er -
hva heter du?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
Og så hva gjør vi nå at Vi har en liste over størrelse 1?
>> PUBLIKUM: Return.
>> DAVID MALAN: Forsiktig.
Vi kommer tilbake først, og nå den tredje trinn - og hvis jeg slags skildre det ved
omfavner de to setene nå, nå er jeg nødt til å flette disse to elementene.
Så nå dessverre, elementene er ute av drift.
Men det er der fusjonsprosessen begynner å bli overbevisende.
>> Så hvis dere kunne stå opp for bare et øyeblikk, jeg kommer til å trenge deg, i en
øyeblikk, å gå bak stolen.
Og hvis Linda, fordi to er mindre enn 4, hva
du kommer rundt først?
Bo der.
Så Linda, kom deg rundt først.
>> Nå i virkeligheten om det er bare en matrise vi kan bare flytte henne i sanntid
fra denne stolen til dette stedet.
Så tenk deg at tok noen konstant antall trinn: 1.
Og nå -
men vi trenger å sette deg i den første plasseringen her.
>> Og nå hvis du kunne komme rundt, også, skal vi
være på plass to.
Og selv om dette føles som det er ta en stund, hva er fint nå er
at den venstre halvdelen av venstre halvdelen er nå sortert.
Så hva var neste skritt, hvis vi nå spole videre i historien?
>> PUBLIKUM: Høyre halvdel.
>> DAVID MALAN: Sortere høyre halvdel.
Så dere må gjøre dette, også.
Så hvis du kunne stå opp for bare et øyeblikk?
Og hva heter du?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, så Jess er nå den venstre halvdelen av den høyre halvdel.
Og så er hun en liste med størrelse 1.
Hun er åpenbart sortert.
Og navnet ditt igjen?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle er åpenbart en liste med størrelse 1.
Hun har allerede sortert.
Så nå magien skjer, fusjonsprosessen.
Så hvem kommer til å komme først?
Tydeligvis Michelle.
Så hvis du kunne komme rundt ryggen.
Plassen vi har tilgjengelig for henne nå er rett bak denne stolen her.
Og nå hvis du kunne komme tilbake også, vi nå har, for å være klar, to
halvdeler, hver på størrelse 2 -
og bare for skildring skyld, hvis du kunne gjøre en liten bit av en plass -
man forlot halvparten her, en høyre halvdel her.
>> Spol tilbake videre i historien.
Hva trinnet er neste?
>> PUBLIKUM: Flett.
>> DAVID MALAN: Så nå har vi å fusjonere.
Så OK, så nå, heldigvis, vi bare frigjort fire stoler.
Så vi har brukt dobbelt så mye minne, men vi kan gi flip-flopper mellom
de to arrays.
Så hvilke tall er å komme først?
Så Michelle, selvsagt.
Så kom rundt og ta ditt sete her.
Og så nummer to er åpenbart neste, så du kommer hit.
Nummer 4, nummer 6.
Og igjen, selv om det er en liten bit av vandre involvert,
egentlig, disse kunne skje umiddelbart, av en bevegelse -
OK, godt spilt.
>> [Latter]
>> DAVID MALAN: Og nå er vi i ganske god form.
Den venstre halvdel av hele innspill har nå blitt sortert.
Ok, så disse gutta hadde fordelen av min -
hvordan gikk det ender opp med alle jentene på venstre og alle guttene på høyre?
>> OK, så gutta "snu nå.
Så jeg vil ikke gå gjennom disse trinnene.
Vi får se om vi kan bruke på nytt samme pseudokode.
Hvis du ønsker å gå videre og stå opp, og dere, la meg gi deg mic.
Se om du ikke kan gjenskape det vi nettopp gjorde her på
andre enden av listen.
Som trenger å snakke først, basert på algoritmen?
Så forklare hva du gjør før du gjør noen fot bevegelser.
>> SPEAKER 1: All right, så siden Jeg er den venstre halvdelen av
venstre halvdel, jeg kommer tilbake.
Høyre?
>> DAVID MALAN: Good.
>> SPEAKER 1: Og så -
>> DAVID MALAN: Hvem gjør mic gå til neste?
>> SPEAKER 1: Neste nummer.
>> SPEAKER 2: Så jeg er høyre halvdel av den venstre halvdel av
venstre halvdel, og jeg kommer tilbake.
>> DAVID MALAN: Good.
Du kommer tilbake.
Så nå hva er neste opp for dere to?
>> SPEAKER 2: Vi vil se hvem som er mindre.
>> DAVID MALAN: Nettopp.
Vi ønsker å slå seg sammen.
Plassen vi skal bruke til å fusjonere deg inn, selv om de er
åpenbart sortert allerede, vi skal å følge den samme algoritmen.
Så hvem går inn bakerst først?
Så tre, og deretter 7.
Og nå mic går til disse gutta, OK?
>> SPEAKER 3: Så jeg er den høyre halvdelen av venstre halvdel, og min n er mindre enn
En, så jeg bare kommer til å passere -
>> DAVID MALAN: Good.
>> SPEAKER 4: Jeg er den høyre halvdelen av høyre halvdel av høyre halvdel, og jeg er
man også person, så jeg er kommer til å returnere.
Så nå er vi flette.
>> SPEAKER 3: Så vi går tilbake.
>> DAVID MALAN: Så du går inn på baksiden.
Så 5 går først, deretter åtte.
Og nå publikum, som er trinn må vi nå spole tilbake
tilbake til i våre sinn?
>> PUBLIKUM: Flett.
>> DAVID MALAN: Sammenslåing venstre halvdel og høyre halvparten av den opprinnelige venstre halvdel.
Så nå -
og bare for å gjøre dette klart, gjøre en liten bit av plass
mellom du to gutter.
Så nå det er de to listene, venstre og høyre.
Så hvordan skal vi nå slå sammen dere inn første rad av seter igjen?
>> 3 går først.
Deretter 5, selvsagt.
Deretter 7, og nå åtte.
OK, og nå er vi?
>> PUBLIKUM: Ikke gjort.
>> DAVID MALAN: Ikke gjort, fordi åpenbart, det er ett skritt gjenstår.
Men igjen, grunnen til at jeg bruker denne sjargong som "spole tilbake i tankene dine,"
det er fordi det er virkelig hva som skjer.
Vi går gjennom alle disse trinnene, men vi er liksom pause for en
øyeblikk, dykke dypere inn i algoritme, pause for et øyeblikk,
dykking dypere inn i algoritmen, og nå må vi liksom bakover i vår
sinn og angre alle disse lagene at vi har liksom satt på vent.
>> Så nå har vi to lister med størrelse 4.
Hvis dere kunne stå opp en siste gang og lage litt plass her til
gjøre det klart at dette er venstre halvparten av den opprinnelige, jo
høyre halvdel av den opprinnelige.
Hvem er det første tallet som vi behov for å trekke inn i ryggen?
Michelle, selvfølgelig.
>> Så vi satt Michelle her.
Og hvem har nummer to?
Nummer to kommer på ryggen også.
Nummer 3?
Utmerket.
Nummer 4, nummer fem, nummer 6, nummer 7, og nummer åtte.
>> OK, så det føltes som mye trinn, for sikker.
Men nå la oss se om vi ikke kan bekrefte slags intuitivt at dette
algoritme fundamentalt, spesielt som n blir veldig store, som vi har sett
med animasjoner, er fundamentalt raskere.
Så jeg hevder denne algoritmen i verste tilfelle, og selv i de beste tilfeller
er big O for n ganger log n.
Det vil si, det er noen aspekter av dette algoritme som tar n trinn, men
det er et annet aspekt sted i som iterasjon, som looping, som
tar log n trinn.
Kan vi sette vår fingeren på hva de to tallene henviser til?
Vel, der -
Hvor gikk mic reise?
>> SPEAKER 1: Ville logge n være bryte oss opp i to -
dividere med to, i det vesentlige.
>> DAVID MALAN: Nettopp.
Hver gang vi ser på noen algoritme dermed langt har det vært dette mønsteret av
dele, dele, dele seg.
Og det er vanligvis redusert til noe som er
logaritmisk, log base 2.
Men det kan egentlig være hva som helst, men logger base 2.
>> Hva nå om den n?
Jeg kan se at vi på en måte delt deg Gutta - delt deg, delt deg,
delt deg, delt deg.
Hvor kommer enden fra?
>> Så det er en sammenslåing.
Fordi tenke på det.
Når du slår sammen åtte mennesker sammen, hvorved halvparten av dem er et sett av fire
og den andre halvparten er en annen sett med fire, hvordan du går
om å gjøre sammenslåing?
Vel, det gjorde dere det ganske intuitivt.
>> Men hvis jeg i stedet gjorde det litt mer metodisk, kanskje jeg har pekt på
lengst til venstre personen først med min venstre hånd, pekte på leftmost person
av at halvparten med min høyre hånd, og bare senere gikk gjennom
listen, peker på det minste elementet hver gang, beveger fingeren over og
enn etter behov i løpet listen.
Men hva er nøkkelen om dette sammenslåing Prosessen er jeg sammenlikne disse parene
av elementer.
Fra høyre halvdel og fra venstre halvparten, jeg aldri en gang tilbakesporing.
>> Så flettingen selv tar ikke mer enn n trinn.
Og hvor mange ganger har jeg har å gjøre det sammenslåing?
Vel, ikke mer enn n, og vi bare så at med den endelige flettingen.
Og så hvis du gjør noe som tar log n trinn n ganger, eller vice versa,
det kommer til å gi oss n ganger log n.
>> Og hvorfor er dette bedre?
Vel, hvis vi allerede vet at log n er bedre enn n - ikke sant?
Vi så i binær søk, telefonboken eksempel var log n definitivt
bedre enn lineær.
Så det betyr n ganger log n er definitivt bedre enn n ganger en annen
n, AKA n kvadrat.
Og det er det vi til slutt føler.
>> Så stor applaus, hvis vi kunne, for disse gutta.
>> [APPLAUSE]
>> DAVID MALAN: Og dine avskjeds gaver - du kan beholde tallene,
hvis du ønsker.
Og avskjedsgave, som vanlig.
Oh, og vi vil sende deg opptakene, Michelle.
Takk.
OK.
Forsyn deg med en stress ball.
>> Og la meg trekke opp, i mellomtiden, vår venn Rob Bowden å tilby
noe annet perspektiv på dette, siden du kan tenke på disse
trinn som skjer i en noe annen måte.
Faktisk oppsett for hva Rob handler om å vise oss forutsetter at vi har
allerede gjort dele opp av stor liste i åtte små lister,
hver av størrelse 1.
>> Så vi endrer pseudokode en litt bare for å liksom få på
kjernen ideen om hvordan sammenslåing fungerer.
Men kjøretiden til hva han er i ferd med å gjøre er fortsatt
kommer til å være den samme.
Og igjen, er det satt opp her at han er begynt med åtte lister over størrelse 1.
Så du har gått glipp av den delen hvor han er faktisk gjort log n, log n, log n
delende på inngangen.
>> [VIDEOAVSPILLING]
>> -Det er det for trinn én.
For to trinn, flere ganger flette par lister.
>> DAVID MALAN: Hm.
Bare lyden kommer ut av datamaskinen min.
La oss prøve dette igjen.
>> -Just vilkårlig plukke som - nå har vi fire lister.
Lære før.
>> DAVID MALAN: Det vi går.
>> -Sammenslåing 108 og 15, ender vi opp med listen 15, 108..
Sammenslåing 50 og 4, vi ende opp med 4, 50.
Sammenslåing 8 og 42, vi ende opp med 8, 42.
Og sammenslåing 23 og 16, vi ende opp med 16, 23.
>> Nå er alle våre lister som er av størrelse 2.
Legg merke til at hver av de fire listene er sortert.
Så kan vi begynne å slå sammen par av listene igjen.
Sammenslåing 15 og 108 og 4 og 50, vi først ta fire, deretter 15, deretter
den 50, og den 108..
Sammenslåing 8, 42 og 16, 23, må vi først ta på 8, og deretter til 16, deretter 23
Da den 42.
>> Så nå har vi bare to lister med størrelse 4, er hver av disse sorteres.
Så nå er vi slå sammen disse to listene.
Først tar vi fire, så vi tar 8, og deretter tar vi 15, så 16, så
23, så 42, ​​så 50, så 108.
>> [END VIDEOAVSPILLING]
>> DAVID MALAN: Igjen, varsel, aldri han rørt en gitt kopp mer enn én gang
etter å gå forbi den.
Så han aldri gjenta.
Så han alltid beveger seg til siden, og det er der vi fikk vår n.
>> Hvorfor ikke la meg trekke opp en animasjon som vi så tidligere, men denne gangen
fokuserer bare på merge sort.
La meg gå videre og zoome inn på dette her.
Først la meg velge en tilfeldig input, foredle dette, og du kan liksom se
hva vi tok for gitt, tidligere, flette sortere faktisk gjør.
>> Så merke at du får disse halvdeler eller disse kvartaler eller disse åttendedeler av
Problemet som plutselig begynner å ta god form.
Og så til slutt, ser du på helt på slutten at bam,
alt er flettet sammen.
>> Så disse er bare tre forskjellige tar på den samme ideen.
Men nøkkelen innsikt, akkurat som divide og hersk i den aller første klasse,
var at vi bestemte oss for å liksom dele problemet til noe stort, inn
noe slags identisk i ånd, men mindre og mindre og mindre
og mindre.
>> Nå er en annen morsom måte å sortere av tro om disse, selv om det ikke er
kommer til å gi deg den samme intuitive forståelse, er
følgende animasjon.
Så dette er en video noen sette sammen den som er forbundet forskjellig
lyder med ulike operasjoner for innsetting sortere, for flettingen sortere og
for et par andre.
Så i et øyeblikk, jeg kommer til å treffe Play.
Det er omtrent et minutt lang.
Og selv om du kan fortsatt se mønstre som skjer, denne gangen kan du
også høre hvordan disse algoritmene er utfører annerledes og med
noe ulike mønstre.
>> Dette er innsetting slag.
>> [TONES SPILLE]
>> DAVID MALAN: Det igjen prøver å sette inn hvert element
inn der det hører hjemme.
Dette er boble slag.
>> [TONES SPILLE]
>> DAVID MALAN: Og du kan liksom følelsen hvor relativt lite arbeid den gjør
ved hvert trinn.
Dette er hva tediousness høres ut som.
>> [TONES SPILLE]
>> DAVID MALAN: Dette er valg sortere, hvor vi velger elementet vi ønsker ved
gå gjennom igjen og igjen og igjen og setter den i begynnelsen.
>> [TONES SPILLE]
>> DAVID MALAN: Dette er fusjonere slag, som du kan virkelig begynne å føle.
>> [TONES SPILLE]
>> [Latter]
>> DAVID MALAN: Noe som heter gnome sortere, som vi ikke har sett på.
>> [TONES SPILLE]
>> DAVID MALAN: Så la meg se, nå, distrahert som du forhåpentligvis er av
musikk, hvis jeg kan skli litt litt matematikk her.
Så det er en fjerde måte at vi kan tenke på hva det betyr disse
funksjoner for å være raskere enn de som vi har sett før.
Og hvis du kommer på kurset fra en matematikk bakgrunn, du
faktisk vet kanskje allerede at du kan klapse et begrep på denne teknikken -
nemlig rekursjon, en funksjon som kaller liksom seg selv.
>> Og igjen, husker at flettingen slags pseudokode var rekursiv i den forstand
at en av fusjonere sortere fotspor var å ringe sort -
som er, i seg selv.
Men heldigvis, fordi vi holdt ringer sorter eller flette sortere,
Nærmere bestemt, på en mindre og mindre og mindre liste, til slutt vi
bunnet ut takket være det vi kaller en base case, den hardkodet sak som
sa dersom listen er liten, mindre enn 2 i så fall, bare returnere umiddelbart.
Hvis vi ikke har den spesielle saken, algoritmen ville aldri bunnen ut,
og du vil faktisk komme inn i en uendelig løkke virkelig evig.
>> Men anta at vi ønsket å nå sette noen tall på dette, igjen, ved hjelp av n
som størrelsen på inngangen.
Og jeg ville spørre deg, hva er den totale tid involvert i
kjører flettingen slag?
Eller mer generelt, hva som er prisen for det i tide?
>> Vel det er ganske lett å måle det.
Hvis n er mindre enn 2, tiden involvert i sortering n elementer,
hvor n er 2, er 0.
Fordi vi bare tilbake.
Det er ingen arbeid som må gjøres.
Nå kanskje, kanskje det er et skritt eller to fremgangsmåten for å finne ut hvor mye
fungere, men det er nært nok til 0 som Jeg skal bare si nei arbeid er
nødvendig hvis listen er så liten å bli uinteressant.
>> Men dette tilfellet er interessant.
Den rekursive tilfellet var den grenen av den pseudokode som sagt annet, sortere
venstre halvdel, sortere riktig halvparten, slå sammen de to halvdelene.
Nå hvorfor dette uttrykket representerer det regning?
Vel, betyr T n bare tid til å sortere n elementer.
Og deretter på høyre side av likhetstegn der, delte T for n
ved 2 refererer til kostnaden av det?
Sortering venstre halvdel.
Den andre T av N dividert med 2 er antagelig henvise til kostnadene til
sortere den høyre halvdel.
>> Og så pluss n?
Er en sammenslåing.
Fordi hvis du har to lister, en av størrelse n over 2 og en annen størrelse av n
over 2, må du i hovedsak berøre hvert av disse elementer, i likhet Rob
rørt hvert av begrene, og bare som vi har pekt på hver av de
frivillige på scenen.
Så n er bekostning av sammenslåing.
>> Nå dessverre, denne formelen er også selv rekursiv.
Så hvis spørsmålet, hvis n er, sier, 16, hvis det er 16 personer på scenen
eller 16 kopper i videoen, hvor mange totalt trinn tar det å sortere dem
med flette slag?
Det er faktisk ikke et opplagt svar, fordi nå må du liksom
rekursivt besvare denne formelen.
>> Men det er OK, fordi la meg foreslå at vi gjør følgende.
Tiden involvert for å sortere 16 personer eller 16 kopper kommer til å være representert
generelt som T 16 av.
Men det er lik, i henhold til våre tidligere formel, to ganger det beløpet
av tiden det tar å sortere 8 kopper pluss 16.
Og igjen, pluss 16 på tide å fusjonere, og to ganger T av 8 er
tid til å sortere venstre halvdel og høyre halvdel.
>> Men igjen, dette er ikke nok.
Vi må dykke i dypere.
Dette betyr at vi må svare på spørsmålet, hva er T av 8?
Vel T av åtte er bare to ganger T av 4 pluss åtte.
Vel, hva er T av fire?
T av fire er bare to ganger T av to pluss fire.
Vel, hva er T for to?
T av to er bare to ganger T av en pluss to.
>> Og igjen, er vi på en måte å få fast i denne syklusen.
Men det handler om å treffe såkalt basen tilfelle.
Fordi det er T for en, vi hevder?
0.
Så nå endelig kan vi jobbe bakover.
>> Hvis T på 1 er 0, kan jeg nå gå tilbake opp ett linje til denne fyren her, og jeg kan
plugg inn 0 for T av en.
Så det betyr at det tilsvarer to ganger null, ellers kjent som 0, pluss 2.
Og så at hele uttrykket er to.
>> Nå hvis jeg tar T av to, hvis svaret er 2, plugge den inn i midten linje, T
av fire, som gir meg to ganger 2 pluss 4, så 8.
Hvis jeg da plugge i åtte til forrige linjen, som gir meg to ganger 8, 16.
Og hvis vi da fortsette som med 24, og legger i 16, vi endelig får en
verdi av 64 år.
>> Nå som i seg selv liksom snakker ingenting til n notasjon, den
big O, omega at vi har vært snakket om.
Men det viser seg at 64 er faktisk 16, størrelsen av tilførselen
logg base 2 av 16 år.
Og hvis dette er litt uvant, bare tenker tilbake, og det vil komme tilbake
til du til slutt.
Hvis dette er log base 2, det er som to hevet til det som gir deg 16?
Å, det er fire, så det er 16 ganger fire.
>> Og igjen, det er ikke en stor avtale hvis dette er liksom en disig minne nå.
Men for nå, ta på tro at 16 log 16 er 64 år.
Og så faktisk med denne enkle tilregnelighet sjekk, har vi bekreftet -
men ikke bevist formelt -
at kjøretiden til flettingen typen er faktisk n log n.
>> Så ikke ille.
Det er definitivt bedre enn den algoritmene vi har sett så langt, og
det er fordi vi har belånt, en, en teknikk som kalles rekursjon.
Men mer interessant enn det, at oppfatningen av å dele seg og erobre.
Igjen, virkelig uke 0 ting som selv nå er tilbakevendende i en
mer overbevisende måte.
>> Nå er en morsom liten øvelse, hvis du har aldri gjort dette - og du sannsynligvis
ville ikke ha, fordi liksom normal folk ikke tenker å gjøre dette.
Men hvis jeg går til google.com og hvis Jeg ønsker å lære noe om
rekursjon, Enter.
>> [Latter]
[Mer latter]
DAVID MALAN: Bad joke sakte sprer seg.
[Latter]
DAVID MALAN: Bare i tilfelle, er det der.
Jeg har ikke stave det galt, og det er spøk.
OK.
Forklare det til folk ved siden av deg hvis det har ikke helt klikket helt ennå.
Men rekursjon, mer generelt, refererer til prosessen med en funksjon ringer
seg selv, eller mer generelt, å dele en Problemet til noe som kan være
løst stykkevis ved å løse identiske representative problemer.
>> Vel, la oss endre tannhjul for bare et øyeblikk.
Vi liker å ende på visse cliffhangers, så la oss begynne å sette
scenen, i flere minutter, på en veldig enkel idé -
som å bytte to elementer, ikke sant?
Alle disse algoritmene vi har vært snakker om de siste par
forelesninger innebære noen slags bytte.
I dag ble det visualisert ved dem får opp av stolene sine og
vandre rundt, men i koden, ville vi bare ta et element fra ett array
og slenger den inn i en annen.
>> Så hvordan kan vi gå om du gjør dette?
Vel, la meg gå videre og skrive en rask program her.
Jeg kommer til å gå videre og gjøre dette følger nedenfor.
La oss kalle dette -
hva gjør vi ønsker å kalle dette en?
>> Nei, faktisk ikke.
La meg spole tilbake.
Jeg ønsker ikke å gjøre det cliffhanger ennå.
Det vil ødelegge moroa.
La oss gjøre dette i stedet.
>> Anta at jeg ønsker å skrive litt program og som omfavner nå dette
Ideen om rekursjon.
Jeg typen har foran meg selv der.
Jeg kommer til å gjøre følgende.
>> Først en rask inkluderer av standard io.h, samt et inkluder av cs50.h.
Og så jeg kommer til å gå videre og erklære int main ugyldig
på vanlig måte.
Jeg innså at jeg har misnamed filen, så la meg bare legge til en. c utvidelse her så
at vi kan kompilere den riktig.
Start denne funksjonen.
>> Og funksjonen jeg ønsker å skrive, ganske enkelt, er en som ber
bruker for et nummer og deretter legger opp alle tallene mellom at
nummer og, si, 0.
Så første jeg kommer til å gå videre og erklære int n.
Da jeg kopiere noen kode som vi har brukt på en stund.
Mens noe er sant.
Jeg skal komme tilbake til det i et øyeblikk.
>> Hva ønsker jeg å gjøre?
Jeg ønsker å si printf positive heltall behage.
Og så skal jeg si n får bli int.
Så igjen, noen standardtekst kode at vi har brukt før.
Og jeg kommer til å gjøre dette mens n er mindre enn 1.
Så dette vil sikre at brukeren gir meg et positivt heltall.
>> Og nå skal jeg gjøre følgende.
Jeg ønsker å legge opp alle tallene mellom 1 og og N eller 0 og n,
ekvivalent, for å få den totale summen.
Så det store sigma symbol som du kanskje husker.
Så jeg kommer til å gjøre dette ved første kall en funksjon som heter sigma,
passerer det i n, og da jeg kommer til å si printf, er svaret der.
>> Så kort sagt, får jeg og int fra brukeren.
Jeg sikre at det er positivt.
Jeg erklærer en variabel kalt svar på type int og butikk i den avkastningen
Verdien av sigma, passerer n som input.
Og da jeg skrive ut det svaret.
>> Dessverre, selv om sigma lyder som noe som kan være i
den math.h fil, sin erklæring, det er faktisk ikke.
Så det er OK.
Jeg kan implementere dette selv.
Jeg kommer til å implementere en funksjon som heter sigma, og det kommer til å ta en
parameter -
la oss bare kalle det m, bare så er det annerledes.
Og deretter opp her, kommer jeg til å si, vel, hvis m er mindre enn 1 - Dette er et
svært uinteressant program.
Så jeg kommer til å gå videre og umiddelbart returnere 0.
Det gir bare ikke mening å legge opp alle tallene mellom 1 og m hvis m
i seg selv er 0 eller negativ.
>> Og så jeg kommer til å gå videre og gjøre dette veldig iterativt.
Jeg kommer til å gjøre denne typen old-school, og jeg kommer til å gå videre
og si at jeg kommer til å erklære en sum for å være 0..
Så jeg kommer til å ha en for løkke av int -
og la meg gjøre det for å matche vår distribusjon kode, slik at du har en kopi
hjemme. int i får en på opptil i er mindre enn eller lik m.
Jeg pluss pluss.
Og så innsiden av dette for loop -
vi er nesten der -
Summen blir sum pluss en.
Og så jeg kommer til å returnere summen.
>> Så jeg gjorde dette raskt, ganske riktignok.
Men igjen, er den viktigste funksjonen pen grei, basert på koden vi har
skrevet så langt.
Bruker den doble loopen å få en positiv int fra brukeren.
Jeg så pass at int til en ny funksjon kalt sigma, kaller det, igjen, n..
Og jeg lagre returverdien, svaret fra den svarte boksen i dag
kjent som sigma, i en variabel kalt svaret.
Så jeg skriver det ut.
>> Hvis vi nå fortsette historien, hvordan er sigma implementert?
Jeg foreslår å implementere som følger.
Først, en liten bit av feil-sjekking å sørge for at brukeren ikke er
rote med meg og passerer noen negativ eller 0 verdi.
Så jeg erklære en variabel kalt oppsummere og sette den til 0.
>> Og nå begynner jeg å flytte fra jeg lik 1 hele veien opp til og med m,
fordi jeg ønsker å inkludere alle tall fra en gjennom m, inkluderende.
Og inne i dette for loop, jeg bare gjøre Summen blir uansett det er nå, pluss
Verdien av jeg.
Pluss verdien av i.
>> Som en side, hvis du ikke har sett denne før, er det noen syntaktisk sukker
for denne linjen.
Jeg kan skrive dette som pluss er lik i, bare for å redde meg selv noen få tastetrykk
og å se litt kjøligere.
Men det er alt.
Det er funksjonelt det samme.
>> Dessverre, denne koden er ikke kommer til å kompilere ennå.
Hvis jeg kjører gjør 0 sigma, hvordan er Jeg kommer til å bli skreket til?
Hva kommer det til å ikke like?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Ja, det gjorde jeg ikke erklære funksjonen opp topp, ikke sant?
C er litt dumt, ved at den kun gjør det du ber den om, og du
nødt til å gjøre det i den rekkefølgen.
Og så hvis jeg treffer Skriv inn her, kommer jeg til å får en advarsel om sigma implisitt
erklæring.
>> Oh, ikke et problem.
Jeg kan gå opp til toppen, og jeg kan si, ok, vent litt.
Sigma er en funksjon som returnerer en int og det forventer en
int som input, semikolon.
Eller jeg kunne sette hele funksjonen ovenfor viktigste, men generelt, ville jeg
anbefaler mot dette, fordi det er hyggelig å alltid ha viktigste på toppen så
du kan hoppe rett inn og vet hva en Programmet gjør ved å lese viktigste først.
>> Så nå la meg tømme skjermen.
Remake sigma 0.
Alt ser ut til å sjekke ut.
La meg kjøre sigma 0.
Positiv inter.
Jeg skal gi det antall 3 å holde det enkelt.
Så det burde gi meg 3 pluss 2 pluss 1, slik 6..
Enter, og faktisk jeg får seks.
>> Jeg kan gjøre noe større -
50, 12, 75.
Akkurat som en tangent, jeg kommer til å gjøre noe latterlig som en virkelig stor
nummer, Å, det fungerte faktisk -
eh, jeg tror ikke det er rett.
La oss se.
La oss virkelig rotet med det.
>> Det er et problem.
Hva skjer?
Koden er ikke så ille.
Det er fortsatt lineær.
Plystring er en god effekt, skjønt.
Hva skjer?
>> Ikke sikker på om jeg hørte det.
Så det viser seg - og Dette er som en side.
Dette er ikke kjernen til Ideen om rekursjon.
Det viser seg, fordi jeg prøver å representerer et så stort antall, mest
sannsynlig det blir feiltolket av C som ikke positivt tall,
men negativt tall.
>> Vi har ikke snakket om dette, men det viser seg at det er negative tall
i verden i tillegg til positive tall.
Og de midler som du kan representerer et negativt tall
egentlig er, bruker du en spesiell bit for å indikere
positivt enn negativt.
Det er litt mer komplisert enn det, men det er den grunnleggende ideen.
>> Så dessverre, hvis C er forvirrende ett av de bitene som faktisk betyr,
oh, dette er et negativt tall, min sløyfe her, for eksempel, er faktisk aldri
kommer til å avslutte.
Så hvis jeg var faktisk å skrive noe igjen og igjen, ville vi
se en hel masse.
Men igjen, er dette i tillegg til punktet.
Dette er egentlig bare en slags intellektuell nysgjerrighet som vi vil komme
tilbake til slutt.
Men for nå, er dette en riktig implementering hvis vi antar at
Brukeren vil gi ints som passer innenfor ints.
>> Men jeg hevder at denne koden, ærlig, kunne gjøres så mye enklere måte.
Hvis målet på hånden, er å ta en rekke som m og legg opp alle
tall mellom den og en, eller motsatt mellom 1 og det, hevder jeg
at jeg kan låne denne ideen om at fusjonere slag hadde, som ble tatt et problem
av denne størrelse og den delende til noe mindre.
Kanskje ikke halvparten, men mindre, men representativ det samme.
Samme idé, men et mindre problem.
>> Så jeg er faktisk - la meg lagre denne filen med en annen versjon nummer.
Vi kaller denne versjonen En i stedet for 0.
Og jeg påstår at jeg faktisk kan reimplement dette i denne typen
mind-bending måte.
>> Jeg kommer til å forlate en del av det alene.
Jeg kommer til å si hvis m er mindre enn eller lik 0 -
Jeg skal bare være litt mer anal denne gangen
med min feilsjekking -
Jeg kommer til å gå videre og returnere 0.
Dette er vilkårlig.
Jeg er bare rett og slett avgjøre om brukeren gir meg et negativt tall, er jeg
returnere 0, og de burde ha lest dokumentasjonen nærmere.
>> Else -
legge merke til hva jeg skal gjøre.
Annet jeg kommer til å returnere m plus -
hva er sigma av m?
Vel, sigma av m plus m minus 1, pluss m 2 minus, pluss m minus tre.
Jeg ønsker ikke å skrive alt dette ut.
Hvorfor gjør jeg ikke bare punt?
Rekursivt kalle meg selv med en litt mindre problem, semikolon
og kalle det en dag?
>> Høyre?
Nå også her kan du føle eller bekymre at dette er en uendelig loop som jeg er
inducing, der jeg implementere sigma ved å ringe sigma.
Men det er helt OK, fordi jeg trodde fremover en ekstra hvilke linjer?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: 23 til 26, som er mitt hvis tilstanden.
Fordi det er fint om subtraksjon her, fordi jeg holder
overlate sigma mindre problemer, mindre problemer, mindre - det er ikke
halve størrelsen.
Det er bare en baby skritt mindre, men det er OK.
Fordi til slutt, vil vi jobbe vei ned til 1 eller 0.
Og når vi treffer 0, er sigma ikke kommer til å kalle seg selv lenger.
Det kommer til å umiddelbart returnere 0.
>> Så effekten, hvis du liksom vinden denne opp i tankene dine, er å legge m pluss
m en minus, pluss m minus 2, pluss m minus 3, pluss prikk, prikk, prikk, m minus
m, til slutt gir deg 0, og Effekten er i siste instans å legge til alle
disse tingene sammen.
Så vi har ikke, med rekursjon, løste problemet at vi
kunne ikke løse før.
Faktisk versjon 0 av dette, og hvert Problemet i år har vært løsbar
med bare å bruke for sløyfer eller mens løkker eller lignende konstruksjoner.
>> Men rekursjon, jeg påstår at gir oss en annen måte å tenke på
problemer, der hvis vi kan ta en problem, dele det fra noe
noe stort til noe litt mindre, hevder jeg at vi kan løse det
kanskje litt mer elegant i form av design, med mindre kode,
og kanskje løse problemer som ville være vanskeligere, som vi vil til slutt
se, løse rent iterativt.
>> Men cliffhanger som jeg gjorde ønsker å forlate oss på var dette.
La meg gå videre og åpne opp en fil fra -
faktisk, la meg gå og gjøre dette virkelig rask.
La meg gå videre og foreslå følgende.
Blant dagens kode er denne filen her.
Denne her, noswap.
>> Så dette er et dumt lite program som Jeg pisket opp som hevder å gjøre
følgende.
I hovedsak erklærer det første en int kalt x og tildeler den
verdien 1.
Da er det erklærer en int y og tildeler den verdien 2.
Skriver den ut ut hva x og y er.
Da sier, bytte, dot dot dot.
>> Så det hevder å være å kalle en funksjon kalles swap, passerer x og
y, ideen om hvilken er som forhåpentligvis x og y vil komme tilbake
annen, motsatt.
Så det hevder byttet!
med et utropstegn.
Skriver den ut ut x og y.
>> Men det viser seg at dette svært enkel demonstrasjon ned
her er faktisk buggy.
Selv om jeg erklære en midlertidig variable og midlertidig sette en i
det, så jeg reassigning et verdien av b -
som føles rimelig, fordi jeg har lagret en kopi av en i temp.
Da jeg oppdatere b til lik hva som var i temp.
Denne typen skall spillet med å flytte en i b og b inn i en ved hjelp av denne
middelaldrende mann som heter temp føler helt rimelig.
>> Men jeg hevder at når jeg kjører denne kode, som jeg skal gjøre nå -
la meg gå videre og lim den inn her.
Jeg vil kalle dette noswap.c.
Og som navnet antyder, er dette ikke kommer til å være et riktig program.
Gjør noswap. / Nei swap.
x er 1, y er 2, bytte, byttes om.
x er 1, y er 2.
Dette er fundamentalt galt, selv om dette virker perfekt
fornuftig for meg.
Og det er en grunn, men vi er ikke kommer til å avsløre årsaken ennå.
>> For nå den nest cliffhanger jeg ønsket å forlate deg med dette, en
utlysing av former på kupongkoder.
Vår innovasjon med sene dager i år har provosert en ikke-triviell antall
spørsmål, som var ikke vår intensjon.
Intensjonen med disse kupongkoder, der hvis du gjør en del av problemet
satt tidlig, og dermed får en ekstra dag, var egentlig for å hjelpe dere hjelpe
selv starte tidlig, liksom om av incentivizing deg.
Hjelper oss fordele belastningen over kontortid bedre slik at
det er liksom vinn-vinn.
>> Dessverre tror jeg mine instrukser har ikke vært til dags dato, veldig klar, så
Jeg gikk tilbake denne helgen og oppdatert spec i større, dristigere tekst til
forklare kuler som disse.
Og bare for å si det mer offentlig, etter standard, oppgavesett skyldes torsdag
midt på dagen, per pensum.
Hvis du starter tidlig, etterbehandling del av problemet satt av onsdag klokken 12:00
PM, den delen som vedrører en kupong koden, er ideen om at du kan utvide
din fristen for P satt til fredag.
Det vil si, bet av en liten del av det P satt i forhold til hva som vanligvis er
større problem, og du kan kjøpe selv en ekstra dag.
Igjen, det blir du planlegger å oppgavesettet, får deg til
kontortid før.
Men kupongen koden problemet er fortsatt nødvendig, selv om du ikke sender det.
>> Men mer overbevisende er denne.
(STAGE STILLE) Og de folkene forlater tidlig er skal angre.
Som er folk på balkongen.
Jeg beklager på forhånd til folk på balkongen for grunner som vil være
klart i løpet av et øyeblikk.
>> Så vi er heldige som har en av CS50 er tidligere leder undervisning stipendiater ved
et firma som heter dropbox.com.
De har svært sjenerøst donert en kupong koden her for så mye plass,
som er opp fra vanlig 2 gigabyte.
Så det jeg tenkte vi skulle gjøre på denne endelig notat er å gjøre litt av en giveaway,
der i bare et øyeblikk, vil vi avsløre vinneren og som har en kupong
kode som du kan deretter gå til deres nettside, skriv det inn, og voila, få en
hel masse mer Dropbox plass for din apparatet og for dine personlige filer.
>> Og først, som ønsker å delta i denne tegningen?
OK, nå som gjør det enda mer moro.
Den som mottar denne 25-gigabyte kupong kode - som er langt
mer overbevisende enn sent dager nå, kanskje -
er den som sitter på toppen av en seteputen under hvilken det finnes
at kupongkode.
Du kan nå se under din seteputen.
>> [VIDEOAVSPILLING]
>> -En, to, tre.
>> [SKRIKING]
>> -Du får en bil!
Du får en bil!
>> DAVID MALAN: Vi vil se deg på onsdag.
>> -Du får en bil!
Du får en bil!
>> DAVID MALAN: Balkong folkens, kommer ned her til fronten,
hvor vi har statister.
>> -Alle får en bil!
Alle får en bil!
>> [END VIDEOAVSPILLING]
>> FORTELLER: Ved neste CS50 -
>> SPEAKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh -
>> [Ukelele SKUESPILL]