>> [MUSIC Playing]
DAVID MALAN: Okay.
Okay, velkommen tilbage.
Så dette er uge 4, begyndelsen , og allerede.
Og du vil huske, at i sidste uge, vi sætter kode afsat til bare en lille smule
og vi begyndte at tale lidt mere højt niveau, omkring ting som
søgning og sortering, som selv noget enkle idéer, er
repræsenterer en klasse af problemer vil du begynde at løse særligt
som du begynder at tænke på den endelige projekter og interessante løsninger, du
måske nødt til virkelige verdens problemer.
Nu boble slags var en af ​​de enkleste sådanne algoritmer, og det
arbejdet ved at have disse små tal på en liste eller i et array slags
boble deres vej op til toppen, og store tal flytter deres vej ned til
i slutningen af ​​denne liste.
>> Og huske, at vi kunne visualisere boble sortere lidt
noget som dette.
Så lad mig gå videre og klik på Start.
Jeg har forvalgt boble slags.
Og hvis du husker at højere blå linjer repræsenterer store tal, små
blå linjer repræsenterer små tal, som vi går gennem dette igen og igen, og
igen, sammenligne to søjler ved siden af ​​hinanden anden i rødt, vi kommer til at skifte
største og den mindste hvis de er ude af drift.
>> Så dette vil gå på og gå på og gå videre, og du vil se, at de større
elementer gør deres vej til højre, og de mindre elementer er
gøre deres vej til venstre.
Men vi begyndte at kvantificere effektivitet, at
kvaliteten af ​​denne algoritme.
Og vi sagde, at i værste tilfælde, denne algoritme tog
nogenlunde hvor mange skridt?
>> Så n potens.
Og hvad var n?
>> PUBLIKUM: Antal elementer.
>> DAVID MALAN: So n var række elementer.
Og så vil vi gøre det ofte.
Helst vi ønsker at tale om størrelsen af et problem eller størrelsen af ​​en
input, eller den tid, det tager at producere output, vi bare
generaliseret uanset input er så n.
Så tilbage i uge 0, antallet sider i telefonbogen var n.
Antallet af elever i værelset var n.
Så også her, vi følger dette mønster.
>> Nu n kvadreret er ikke særlig hurtigt, så vi forsøgte at gøre det bedre.
Og så vi kiggede på et par andre algoritmer, blandt hvilke
var valg slags.
Så udvælgelse sortere var lidt anderledes.
Det var næsten enklere, jeg tør sige, hvorefter jeg begyndte i begyndelsen af
Listen over vores frivillige, og jeg bare igen og igen og igen gik igennem
listen, plukning ud den mindste element på et tidspunkt og sætte ham eller
hende i starten af ​​listen.
>> Men også dette når vi begyndte at tænke gennem matematik og større
billede, tænkt over, hvor mange gange Jeg gik frem og tilbage og tilbage igen
og tilbage, vi sagde i værste fald, udvælgelse sortere, var også hvad?
n squared.
Nu i den virkelige verden, kan det blive faktisk være marginalt hurtigere.
Fordi igen, havde jeg ikke nødt til at holde tilbageskridt når jeg havde sorteres
mindste elementer.
Men hvis vi tænker meget store n, og hvis du slags gøre ud matematik som
Jeg gjorde på brættet, med n kvadreret minus noget, alt andet
foruden n kvadreret, når n bliver rigtig stort, ikke
virkelig noget så meget.
Så som dataloger, sortere vi om vende det blinde øje til den mindre
faktorer og kun fokusere på den faktor i et udtryk, der kommer til at gøre
den største forskel.
>> Nå, endelig, så vi ved indsættelse slags.
Og dette var ens i ånden, men snarere end at gå gennem iterativt og
vælge den mindste element én ad gang, jeg tog i stedet den hånd, jeg
blev behandlet, og jeg besluttede, alt Okay, du hører til her.
Så jeg flyttede til det næste element og besluttede, at han eller
hun hørte her.
Og så flyttede jeg på og.
Og jeg kunne til undervejs, flytte disse fyre for at
gøre plads til dem.
Så det var en slags mental vending af udvælgelse slags, vi
kaldet indsættelse slags.
>> Så disse emner for at forekomme i den virkelige verden.
Bare et par år siden, da en vis senator kørte til formand,
Eric Schmidt, på det tidspunkt, den administrerende direktør for Google faktisk haft mulighed
at interviewe ham.
Og vi troede, vi ville dele denne YouTube klip for dig her, hvis vi kunne slå op
lydstyrken.
>> [VIDEO AFSPIL]
>> -Nu, senator, er du her på Google, og jeg kan lide at tænke på formandskabet
som en jobsamtale.
>> [Latter]
>> -Nu er det svært at få et job som præsident.
Og du går igennem rigor nu.
Det er også svært at få et job hos Google.
Vi har spørgsmål, og vi beder vores kandidater spørgsmål.
Og denne er fra Larry Schwimmer.
>> [Latter]
-Du fyre tror jeg kidding?
Det er lige her.
Hvad er den mest effektive måde at sortere en million to-bit heltal?
>> [Latter]
>> -Jamen, øh -
>> -Undskyld.
Måske burde vi -
>> -Nej, nej, nej, nej, nej.
>> -Det er ikke en -
OK.
>> -Jeg tror, ​​at boblen slags ville være den forkerte vej at gå.
>> [Latter]
>> [Jubler og klapper]
>> -Kom nu, der fortalte ham det her?
OK.
>> [END VIDEOAFSPILNING]
>> DAVID MALAN: Så der har du det.
Så vi begyndte at kvantificere disse kørende gange, så at sige, med noget
kaldet asymptotisk notation, som er bare at henvise til vores slags drejning
det blinde øje til de mindre faktorer, kun at se på den løbende tid,
udførelsen af ​​disse algoritmer, da n får virkelig store over tid.
Og så vi introducerede big O. Og big O repræsenterede noget, som vi troede
på som en øvre grænse.
Og faktisk, Barry, kan vi sænke end mic lidt?
>> Vi troede på dette er en øvre grænse.
Så store O i n kvadreret betyder, at i værste fald noget lignende
udvælgelse sortere ville tage n kvadreret trin.
Eller noget lignende indsættelse slags ville n kvadreret trin.
Nu til noget som indsættelse sortere, hvad der var det værste tilfælde?
Givet et array, er hvad det værste mulige scenario, som du kan finde
dig selv konfronteret med?
>> Det er helt bagud, right?
For hvis det er helt bagud, du nødt til at gøre en hel masse arbejde.
Fordi hvis du er helt bagud, du kommer til at finde den
største element her, selvom det hører dernede.
Så du kommer til at sige, okay, ved dette tidspunkt, du hører til her,
så du lader det alene.
>> Så du er klar, åh, damn, jeg er nødt til flytte dette lidt mindre element
venstre dig.
Så jeg er nødt til at gøre det igen og igen og igen.
Og hvis jeg gik frem og tilbage, du ville sortere i føler udførelsen af
denne algoritme, fordi tiden er jeg blander alle andre nede i
matrix at gøre plads til det.
Så det er det værste tilfælde.
>> Derimod -
og dette var en cliffhanger sidste gang -
Vi sagde, at indsættelse sortere var en omega af hvad?
Hvad er det bedst tænkelige drift tidspunktet for anbringelsen slags?
Så det er faktisk n.
Det var tomt, da vi forlod på tavlen sidste gang.
>> Og det er omega n fordi hvorfor?
Tja, i de allerbedste fald, hvad er indsættelse sortere kommer til at blive afleveret?
Tja, en liste, der er helt sorteres allerede minimal arbejde at gøre.
Men hvad er pæne om indsættelse sortere er, at fordi det starter her og
beslutter, åh, du er nummer en, du hører til her.
Åh, sikke en god formue.
>> Du er nummer to.
Du hører også her.
Nummer tre, endnu bedre, du hører her.
Så snart det bliver til slutningen af liste, pr indsættelse slags s pseudokode
at vi gik gennem verbalt sidste gang, er det gjort.
Men udvælgelse sortere, derimod, holdes gør hvad?
>> Holdes i gang gennem listen igen og igen og igen.
Fordi nøglen indsigt var der kun når du har kigget hele vejen til
slutningen af ​​listen kan du være sikker at det element, du valgte var
faktisk den aktuelt mindste element.
Så disse forskellige mentale modeller ende up giver nogle meget virkelige verden
forskelle for os, samt disse teoretiske asymptotiske forskelle.
>> Så bare for at opsummere, så big O n kvadreret, vi har set et par sådanne
algoritmer hidtil.
Big O n?
Hvad er en algoritme, der kunne siges at være stor O n?
I værste tilfælde tager det en lineær række trin.
>> OK, lineær søgning.
Og i værste fald er hvor element, du leder efter, når
anvende lineær søgning?
>> OK, i værste fald, det er ikke engang der.
Eller i det andet værste tilfælde er det hele vejen i sidste ende, hvilket er
plus-eller-minus en et-trins forskel.
Så i slutningen af ​​dagen, kan vi sige, det er lineær.
Big O n ville være lineær søgning, fordi i værste fald
element er ikke engang der, eller det er hele vejen i slutningen.
>> Nå, big O log n.
Vi talte ikke meget detaljeret om dette, men vi har set det før.
Hvad kører i såkaldt logaritmisk tid, i værste fald?
>> Yeah, så binær søgning.
Og binær søgning i værste fald kan have elementet sted i
midten, eller et andet sted inde i array.
Men du kun finde den, når du opdele listen i halve, i
halvdelen i halve. i halve
Og så voila, det er der.
Eller igen, værste fald, det er ikke engang der.
Men du ved ikke, at det ikke er der indtil du slags nå at sidste
bottom-de fleste elementer ved at halvere og en halvering og en halvering.
>> Big O 1..
Så vi kunne big O på 2, big O på 3.
Når du vil bare et konstant antal, vi bare sortere for bare forenkle
at så stor O i 1..
Selvom om realistisk, det tager 2 eller endda 100 trin, hvis det er en
konstant antal trin, siger vi bare big O i 1..
Hvad er en algoritme, der er i big O af 1?
>> PUBLIKUM: Finde længden af en variabel.
>> DAVID MALAN: at finde den Længden af ​​en variabel?
>> PUBLIKUM: Nej, længden hvis den allerede er sorteret.
>> DAVID MALAN: Godt.
OK, så at finde længden af ​​noget hvis længden af, at noget, som
et array, lagres i nogle variabel.
Fordi du kan bare læse den variable, eller udskrive variabel eller
bare generelt få adgang til denne variabel.
Og voila, der tager konstant tid.
>> Derimod tænker tilbage til bunden.
Tænk tilbage til den første uge af C, ringer bare printf og udskrivning
noget på skærmen er velsagtens konstant tid, fordi det tager bare
vist antal af CPU cycles at vise denne tekst på skærmen.
Eller vent - hvad betyder det?
Hvor ellers kan vi modellere udførelse af printf?
Skulle nogen gerne være uenige, at måske er det ikke rigtig konstant tid?
I hvilken forstand kan printf kører tid, faktisk udskrive en streng på
skærmen, være noget bortset konstant.
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Ja.
Så det afhænger af vores perspektiv.
Hvis vi tror faktisk af input til printf som strengen, og
derfor har vi måle størrelsen af ​​denne input fra dens længde - så lad os kalde
denne længde n samt -
velsagtens, printf selv store O n fordi det kommer til at tage dig n skridt
at udskrive hver af disse n tegn, mest sandsynlige.
I det mindste i det omfang, at vi antager at måske er det ved hjælp af en for-løkke
under hætten.
>> Men vi ville have til at se på det kode til at forstå det bedre.
Og ja, når du fyre starter analysere dine egne algoritmer, vil du
bogstaveligt gøre netop det.
Sort of øjeæblet din kode og tænke om - okay, jeg har denne løkke
her eller jeg har en indlejret sløjfer her der kommer til at gøre n ting n gange,
og du kan sortere fornuftens vej gennem koden, det, selvom er
pseudokode og ikke selve koden.
>> Så hvad med omega n kvadreret?
Hvad var en algoritme, der i den bedste tilfælde stadig tog n kvadreret trin?
Ja?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: So udvælgelse slags.
Fordi i dette problem virkelig reduceret det faktum, at igen, ved jeg ikke
Jeg har fundet den nuværende mindste indtil Jeg har tjekket alle darn elementer.
Så omega, siger, n, vi bare kom op med én.
Insertion slags.
Hvis listen sker for at blive sorteret allerede i bedste fald vi bare
at gøre en pass gennem det, på hvilket tidspunkt vi er sikre.
Og så der kunne siges at være lineær, for sikker.
>> Hvad omega af 1?
Hvad i bedste fald tage måske en konstant antal trin?
Så lineær søgning, hvis du bare heldig og elementet du søger
er lige ved starten af ​​listen, hvis det er, hvor du starter din
lineær traversal af listen.
>> Og dette er sandt for en række ting.
For eksempel, binære selv søgning er omega på 1.
For hvad hvis du får virkelig pokkers heldig og smack-dab i midten af
dit array er antallet du leder efter?
Så du kan få heldige der, så godt.
>> Denne ene endelig omega n log n.
Så n log n, vi virkelig ikke tale om endnu, men -
>> PUBLIKUM: Flet slags?
>> DAVID MALAN: Merge slags.
Det var cliffhanger sidste gang, hvor vi foreslog, og vi viste
visuelt, at der er algoritmer.
Og flette slags blot en sådan algoritme, der er fundamentalt hurtigere
end nogle af de andre fyre.
Faktisk fusionere kort er ikke kun i bedste fald n log n, i værste
tilfælde n log n.
Og når du har dette sammenfald af omega og store O er den samme?
Vi kan faktisk beskrive det som hvad der er kaldet theta, selvom det er en
lidt mindre almindelige.
Men det betyder bare de to grænser, i dette tilfælde, er de samme.
>> Så fusionere sortere, hvad betyder dette virkelig koges ned til os?
Nå, genkalde motivation.
Lad mig trække op en anden animation, vi ikke se på sidste gang.
Denne ene, samme idé, men det er lidt større.
Og jeg har tænkt mig at gå videre og påpege første - vi har indsættelse sortere på
øverst til venstre, derefter valg sortere, boble sortere, et par andre former -
shell og hurtigt - at vi ikke har talt om, og heap og flette slags.
>> Så i det mindste forsøge at fokusere dine øjne på top tre på den venstre og derefter
fusionere slags når jeg klikker denne grønne pil.
Men jeg vil lade dem alle køre, bare for at give dig en fornemmelse af mangfoldigheden af
algoritmer, der findes i verden.
Jeg har tænkt mig at lade dette løbe for blot et par sekunder.
Og hvis du fokusere dine øjne - vælg et algoritme, fokus på det for bare en
sekunder - du vil begynde at se mønster, at det er at gennemføre.
>> Flet sortere, varsel, er gjort.
Heap sortere, hurtig sortere, shell -
så det synes vi introducerede tre værste algoritmer sidste uge.
Men det er godt, at vi er her i dag for at se på sammenfletning slags, som er en af
de lettere dem er at se på, selv selv om det sandsynligvis vil bøje dit sind
bare en lille smule.
Her kan vi se, hvor meget udvælgelse sortere stinker.
>> Men på bagsiden, er det virkelig nemt at implementere.
Og måske for P Set 3, er, at en af algoritmer du har valgt at implementere
for standard edition.
Helt fint, helt korrekt.
>> Men igen, da n bliver store, hvis du vælger at gennemføre en hurtigere algoritme
gerne fusionere sortere, odds er i større og større input, din kode er bare
kommer til at løbe hurtigere.
Din hjemmeside kommer til at fungere bedre.
Dine brugere vil være gladere.
Og så der er disse effekter for rent faktisk at give
os nogle dybere tanke.
>> Så lad os tage et kig på, hvad fusionere sortere er faktisk handler om.
Det fede er, at fusionere slags er netop dette.
Dette er, igen, hvad vi har kaldt pseudokode, pseudokode væsen
Engelsk-lignende syntaks.
Og enkelheden er slags fascinerende.
>> Så på input med n elementer - således at betyder bare, her er et array.
Det har fået n ting i det.
Det er alt, vi siger der.
>> Hvis n er mindre end 2, vende tilbage.
Så det er bare den trivielle sagen.
Hvis n er mindre end 2, så selvfølgelig er det 1 eller 0, i hvilket tilfælde ting
er allerede sorteret eller ikke-eksisterende, så bare vende tilbage.
Der er intet at gøre.
Så det er en enkel sag at plukke fra.
>> Else, vi har tre trin.
Sortere den venstre halvdel af de elementer, sortere den højre halvdel af elementerne,
og derefter flette de sorterede halvdele.
Det interessante her er, at Jeg er lidt punting, right?
Der er lidt af en cirkulær definition til denne algoritme.
I hvilken forstand er denne algoritme s definition cirkulære?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Ja, min sortering algoritme, to af sine trin er "slags
noget ". Og så rejser Spørgsmålet, ja, hvad skal jeg bruge
at sortere den venstre halvdel og den højre halvdel?
Og skønhed her er, at selvom igen, det er den hjernevridende
del potentielt, kan du bruge samme algoritme til at sortere den venstre halvdel.
>> Men vent et øjeblik.
Når du får at vide at sortere venstre halvdel, hvad er de to
skridt kommer til at være den næste?
Vi sortere venstre halvdel af venstre halvdel og højre
halvdelen af ​​den venstre halvdel.
Damn, hvordan jeg sorterer de to halvdele, eller kvarte, nu?
>> Men det er OK.
Vi har en sorteringsalgoritme her.
Og selvom du måske bekymre sig på først det er lidt en uendelig
loop, det er en cyklus, der er aldrig vil ende - det vil
ende, når det sker?
Når n er mindre end 2.
Som i sidste ende kommer til at ske, fordi hvis du holder halvere og
halvering at halvere disse halvdele, helt sikkert sidst du kommer til at ende
op med kun 1 eller 0 elementer.
På hvilket punkt, denne algoritme siger, at du er færdig.
>> Så den virkelige magi i denne algoritme synes at være i
at sidste trin, sammenlægning.
Denne enkle idé bare at fusionere to ting, det er, hvad der i sidste ende kommer
at tillade os at sortere et array af, lad os sige, otte elementer.
Så jeg har otte mere stress bolde op her otte stykker papir, og en
Google Glas -
som jeg kommer til at holde.
>> [Latter]
>> DAVID MALAN: Hvis vi kunne tage otte frivillige, og lad os se om vi kan
spille dette ud, så.
Wow, OK.
Datalogi bliver sjovt.
Ok.
Så hvad med jer tre, største hånd deroppe.
Fire i ryggen.
Og hvad vi vil gøre dig tre i denne række?
Og fire i front.
Så du otte, kom op.
>> [Latter]
>> DAVID MALAN: Jeg er faktisk ikke sikker på, hvad det er.
Er det stress bolde?
De bordlamper?
Materialet?
Internettet?
>> OK.
Så kom op.
Hvem vil gerne -
at komme op.
Lad os se.
Og det sætter dig i placering -
du er i location én.
Uh-oh, vent et øjeblik.
1, 2, 3, 4, 5, 6, 7 - Åh, godt.
Okay, vi er gode.
Okay, så alle har et sæde, men ikke på Google Glass.
Lad mig til kø disse op.
Hvad er dit navn?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Okay, du kommer til at ligne nørd, hvis det er OK.
Tja, det gør jeg også, jeg formoder, for bare et øjeblik.
Okay, standby.
Vi har forsøgt at komme med en use case for Google Glass, og vi
troede det ville være sjovt at bare gøre dette, når folk er på scenen.
Vi registrerer verden fra deres perspektiv.
Ok.
Ikke nok, hvad Google hensigten.
Okay, hvis du ikke har noget imod at bære dette for de næste akavede minutter,
det ville være vidunderligt.
>> Okay, så vi har her en vifte af elementer, og at matrix, som pr
stykker papir i disse folk ' hænder, er i øjeblikket usorteret.
>> MICHELLE: Åh, det er så underligt.
>> DAVID MALAN: Det er temmelig tilfældigt.
Og på bare et øjeblik, vi kommer til at prøve at gennemføre fusionere slags sammen
og se, hvor det centrale indsigt er.
Og det trick her med merge slags er noget, vi ikke har antaget endnu.
Vi har faktisk brug for nogle ekstra plads.
Så hvad kommer til at være særligt interessante ved dette er, at disse
fyre kommer til at bevæge sig lidt rundt bit, fordi jeg har tænkt mig at antage, at
der er en ekstra række af rum, sige, lige bag dem.
>> Så hvis de er bag deres stol, det er den sekundære array.
Hvis de er siddende her, det er den primære array.
Men det er en ressource, som vi har ikke gearede hidtil med boble
sortere, med udvælgelse sortere, med indsættelse slags.
Recall i sidste uge, alle bare slags blandes på plads.
De havde ikke bruge nogen ekstra hukommelse.
Vi gjorde plads til folk med flytte folk rundt.
>> Så dette er en vigtig indsigt, også.
Der er denne afvejning, i almindelighed i datalogi, af ressourcer.
Hvis du ønsker at fremskynde noget som om tiden, er du nødt til
nødt til at betale en pris.
Og en af ​​disse priser er meget ofte rum, mængden af ​​hukommelse eller hård
diskplads, du bruger.
Eller ærligt, beløbet programmør tid.
Hvor meget tid det tager dig, det menneskelige, til rent faktisk at gennemføre nogle mere
kompliceret algoritme.
Men i dag, det trade-off er tid og rum.
>> Så hvis du fyre bare kunne holde din tal, så vi kan se, at du er
faktisk matchende 4, 2, 6, 1, 3, 7, 8.
Excellent.
Så jeg har tænkt mig at forsøge at orkestrere ting, hvis du fyre kan bare
følge mit bly her.
>> Så jeg vil gennemføre det første, at første trin af pseudokode, som er
på input med n elementer, hvis n er mindre end 2, og derefter vende tilbage.
Det er klart, at der ikke finder anvendelse, så vi videre.
Så sortere den venstre halvdel af elementerne.
Så det betyder, at jeg har tænkt mig at fokusere min opmærksomhed for bare et øjeblik på disse
fire fyre her.
Okay, hvad skal jeg næste gøre?
>> PUBLIKUM: Sortere den venstre halvdel.
>> DAVID MALAN: Så nu har jeg til at sortere den venstre halvdel af disse fyre.
Fordi igen, påtager dig selv det Målet er at sortere den venstre halvdel.
Hvordan gør du det?
Bare følg instruktionerne, selv selvom vi gør det igen.
Så sortere den venstre halvdel.
Nu er jeg sortere disse to fyre.
Hvad bliver det næste?
>> PUBLIKUM: Sortere den venstre halvdel.
>> DAVID MALAN: Sortere den venstre halvdel.
Så nu disse, denne plads her, er en liste over størrelse 1.
Og hvad er dit navn igen?
>> PRINCESS DAISY: Princess Daisy.
>> DAVID MALAN: Princess Daisy er her.
Og så er hun allerede sorteret, fordi listen er over størrelse 1.
Hvad gør jeg næste gøre?
OK, tilbage, fordi denne liste er str. 1, hvilket er mindre end 2.
Så hvad er næste skridt?
Og nu er du nødt til at slags bakke i dit sind.
>> Sortere den højre halvdel, som er -
hvad er dit navn?
>> Linda: Linda.
>> DAVID MALAN: Linda.
Og så hvad gør vi nu, at Vi har en liste over størrelse 1?
>> PUBLIKUM: Return.
>> DAVID MALAN: Forsigtig.
Vi vender tilbage først, og nu er den tredje skridt - og hvis jeg slags skildre det ved
omfavne de to pladser nu, nu er jeg nødt til at flette disse to elementer.
Så nu desværre elementerne er ude af drift.
Men det er, hvor de fusionerende proces begynder at få overbevisende.
>> Så hvis du fyrene kunne stå op for netop et øjeblik, jeg får brug for dig, i en
øjeblik at træde bag din stol.
Og hvis Linda, fordi 2 er mindre end 4, hvorfor ikke
du kommer rundt først?
Bliv der.
Så Linda, du kommer rundt først.
>> Nu i virkeligheden, hvis det er bare et array Vi kunne bare flytte hende i realtid
fra denne stol til dette sted.
Så forestil dig, der tog nogle konstante Antallet af trin 1.
Og nu -
men vi er nødt til at sætte dig i den første placering her.
>> Og nu, hvis du kunne komme rundt, så godt, vi kommer til at
være i placering to.
Og selvom det føles som om det er tage et stykke tid, er det dejligt nu
at den venstre halvdel af venstre halvdel er nu sorteret.
Så hvad var det næste skridt, hvis vi nu spole videre i historien?
>> PUBLIKUM: Right halvdel.
>> DAVID MALAN: Sortere højre halvdel.
Så du fyre nødt til at gøre dette, så godt.
Så hvis du kunne stå op for bare et øjeblik?
Og hvad er dit navn?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, så Jess er nu den venstre halvdelen af ​​den højre halvdel.
Og så er hun en liste over størrelse 1.
Hun er tydeligvis sorteres.
Og dit navn igen?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle er naturligvis en liste over størrelse 1.
Hun har allerede ordnet.
Så nu magien sker, de fusionerende proces.
Så hvem kommer til at komme først?
Naturligvis Michelle.
Så hvis du kunne komme rundt igen.
Den plads, vi har til rådighed for hende nu er lige bag denne stol her.
Og nu, hvis du kunne komme tilbage så godt, vi nu har, for at være klar, to
halvdele, hver af størrelse 2 -
og bare for skildring skyld, hvis du kunne gøre en lille smule af et rum -
man forlod halvdelen her, en højre halvdel her.
>> Spol tilbage yderligere i historien.
Hvilken trin er det næste?
>> PUBLIKUM: Flet.
>> DAVID MALAN: Så nu har vi at fusionere.
Så OK, så nu, heldigvis, vi netop frigjort fire stole.
Så vi har brugt dobbelt så meget hukommelse, men vi kan give flip-floppe mellem
de to arrays.
Så hvilket nummer der skal komme først?
Så Michelle, naturligvis.
Så kom rundt og tage din plads her.
Og derefter nummer 2 er naturligvis næste, så du kommer her.
Nummer 4, nummer 6.
Og igen, selvom der er en lidt Walking involveret,
virkelig kunne disse ske med det samme, ved at flytte en -
OK, godt spillet.
>> [Latter]
>> DAVID MALAN: Og nu er vi i temmelig god figur.
Den venstre halvdel af hele input er nu blevet sorteret.
Okay, så disse fyre havde den fordel min -
hvordan gik det ender alle pigerne på venstre og alle drengene til højre?
>> OK, så fyre 'Slå nu.
Så jeg vil ikke gå dig gennem disse trin.
Vi vil se, om vi kan genanvende samme pseudokode.
Hvis du ønsker at gå videre og stå op, og jer, lad mig give dig mikrofonen.
Se om du ikke kan kopiere, hvad Vi gjorde bare her på
anden ende af listen.
Hvem har brug for at tale først, baseret på algoritmen?
Så forklare, hvad du laver, før du foretager nogen mund bevægelser.
>> SPEAKER 1: Okay, så da Jeg er venstre halvdel af
venstre halvdel, jeg vender tilbage.
Right?
>> DAVID MALAN: Godt.
>> SPEAKER 1: Og så -
>> DAVID MALAN: Hvem gør mic gå til det næste?
>> SPEAKER 1: Næste nummer.
>> SPEAKER 2: Så jeg er den højre halvdel Den venstre halvdel af
venstre halvdel, og jeg vender tilbage.
>> DAVID MALAN: Godt.
Du vender tilbage.
Så nu, hvad er det næste op for jer to?
>> SPEAKER 2: Vi ønsker se, hvem der er mindre.
>> DAVID MALAN: Præcis.
Vi ønsker at fusionere.
Den plads, vi vil bruge til at fusionere dig ind, selvom de er
naturligvis sorteres allerede, vi vil at følge den samme algoritme.
Så der går i tilbage først?
Så 3 og derefter 7..
Og nu mic går til disse gutter, OK?
>> SPEAKER 3: Så jeg er den højre halvdel af venstre halvdel, og min n er mindre end
1, så jeg bare kommer til at passere -
>> DAVID MALAN: Godt.
>> SPEAKER 4: Jeg er den rigtige halvdel af højre halvdel af den højre halvdel, og jeg er
også en person, så jeg er vil vende tilbage.
Så nu vi flette.
>> SPEAKER 3: Så vi gå tilbage.
>> DAVID MALAN: Så du går ind i ryggen.
Så 5 går først, derefter 8..
Og nu publikum, der er den trin er vi nødt til nu tilbage
tilbage til i vores sind?
>> PUBLIKUM: Flet.
>> DAVID MALAN: Sammenlægning venstre halvdel og højre halvdelen af ​​den oprindelige venstre halvdel.
Så nu -
og bare for at gøre dette klart, gøre en lille smule plads
mellem jer to.
Så nu, er de to lister, venstre og højre.
Så hvordan kan vi nu flette jer ind forreste sæderække igen?
>> 3. går først.
Derefter 5, naturligvis.
Derefter 7 og nu 8.
OK, og nu er vi?
>> PUBLIKUM: Ikke færdig.
>> DAVID MALAN: Ikke gjort, fordi selvfølgelig er der et skridt tilbage.
Men igen, grunden jeg bruger dette jargon som "tilbage i dit sind,"
det er fordi det er virkelig hvad der sker.
Vi går igennem alle disse trin, men vi er en slags pause efter en
øjeblik, dykning dybere ind i algoritme, pause et øjeblik,
dykning dybere ind i algoritmen, og nu er vi nødt til at sortere i tilbagespoling i vores
sind og fortryde alle disse lag at vi har slags sat på hold.
>> Så nu har vi to lister over str. 4.
Hvis du fyre kunne stå op en sidste gang og gøre lidt plads her
gøre det klart, at dette er den venstre halvdelen af ​​den oprindelige, den
højre halvdel af originalen.
Hvem er det første nummer, som vi nødt til at trække ind i ryggen?
Michelle, selvfølgelig.
>> Så vi sætter Michelle her.
Og hvem har nummer 2?
Nummer 2 kommer tilbage samt.
Nummer 3?
Excellent.
Nummer 4, nummer 5, nummer 6, nummer 7, og nummer 8.
>> OK, så det følte ligesom en masse af trin. sikker
Men lad os nu se, om vi ikke kan bekræfte slags intuitivt at dette
algoritme fundamentalt, især da n bliver rigtig stort, som vi har set
med animationer, er fundamentalt hurtigere.
Så jeg hævder denne algoritme i værste sag og selv i bedste fald,
er stort O n gange log n.
Det vil sige, at der er nogle aspekter af dette algoritme, der tager n trin, men
Der er et andet aspekt et sted i at iteration at looping, der
tager log n trin.
Kan vi sætte fingeren på, hvad de to tal taler om?
Tja, hvor -
Hvor blev mikrofonen hen?
>> SPEAKER 1: Ville log n være bryde os op i to -
dividere med to, hovedsagelig.
>> DAVID MALAN: Præcis.
Helst ser vi i enhver algoritme dermed langt, har der været dette mønster af
dividere, dividere, dividere.
Og det er typisk reduceret til noget, der er
logaritmisk, log basis 2.
Men det kunne virkelig være noget, men log base 2.
>> Nu hvad n?
Jeg kan se, at vi slags delt dig fyre - delt dig, delt dig,
delt dig, delt dig.
Hvor kommer enden komme fra?
>> Så det er de fusionerende.
Fordi tænke over det.
Når du fletter otte mennesker sammen, hvorved halvdelen af ​​dem er et sæt af fire
og den anden halvdel er en anden sæt af fire, hvordan kan du gå
om at gøre de fusionerende?
Nå, du fyre gjorde det forholdsvis intuitivt.
>> Men hvis jeg i stedet gjorde det lidt mere metodisk, jeg måske har peget på
længst til venstre person først med min venstre hånd, pegede på den yderste venstre persons
af det halve med min højre hånd, og bare efterfølgende gik gennem
liste, der peger på det mindste element hver gang, flytte min finger over og
løbet efter behov i listen.
Men hvad er nøglen om dette fusionerende proces er jeg sammenligne disse par
elementer.
Fra den højre halvdel og fra venstre halvdelen, jeg aldrig når tilbageskridt.
>> Så sammenfletningen selv tager ikke mere end n trin.
Og hvor mange gange har jeg har at gøre det fusionerende?
Nå, ikke mere end n, og vi bare så, at med den endelige fusionere.
Og så hvis du gør noget, der tager log n trin n gange, eller omvendt,
det kommer til at give os n gange log n.
>> Og hvorfor er det bedre?
Tja, hvis vi allerede ved, at log n er bedre end n - right?
Vi så i binær søgning, telefonbogen Eksempelvis var log n absolut
bedre end lineær.
Så det betyder n gange log n er absolut bedre end n gange en anden
n, AKA n potens.
Og det er, hvad vi i sidste ende føler.
>> Så stor runde af bifald, hvis vi kunne, for disse fyre.
>> [Applaus]
>> DAVID MALAN: Og jeres afskedsord gaver - kan du holde antallet,
hvis du gerne vil.
Og din afskedsgave, som sædvanlig.
Åh, og vi vil sende dig optagelserne, Michelle.
Tak.
Ok.
Hjælp dig selv til en stress bold.
>> Og lad mig trække op i mellemtiden, vores ven Rob Bowden at tilbyde
noget anderledes perspektiv på dette, da du kan tænke om disse
trin sker i en noget anderledes måde.
Faktisk set-up for, hvad Rob handler om at vise os antager, at vi har
allerede gjort opdeling af stor liste i otte små lister
hver af størrelse 1.
>> Så vi ændrer pseudokoden en lidt bare for at sortere i komme på
centrale idé om, hvordan de fusionerende værker.
Men køretiden for hvad han er ved at gøre, er stadig
vil være den samme.
Og igen, set-up er, at han er begyndt med otte lister over størrelse 1.
Så du har savnet den del, hvor han er faktisk gjort log n, log n, log n
dividere af input.
>> [VIDEO AFSPIL]
>> -Det er det for trin et.
For trin to, gentagne gange fusionere par lister.
>> DAVID MALAN: Hm.
Kun lyd kommer ud af min computer.
Lad os prøve det igen.
>> -Just vilkårligt vælge hvilken - nu har vi fire lister.
Lær før.
>> DAVID MALAN: Der går vi.
>> -Fletning 108 og 15, vi ender op med listen 15, 108.
Fletning 50 og 4, vi ender med 4, 50.
Fletning 8 og 42, vi ender med 8, 42.
Og sammenlægning 23 og 16 vi ender med 16, 23.
>> Nu er alle vores lister er af størrelse 2.
Bemærk, at hver af de fire lister er sorteret.
Så vi kan begynde at fusionere par lister igen.
Fletning 15 og 108 og 4 og 50, vi først tage 4 og derefter 15, derefter
50, så de 108.
Fletning 8, 42 og 16, 23, vi først tage den 8., derefter 16, derefter 23,
derefter 42..
>> Så nu har vi kun to lister over størrelsen 4 er hver især sorteret.
Så nu er vi flette disse to lister.
Først tager vi de 4, så vi tager 8, så tager vi de 15, så 16, så
23, så 42, ​​så 50, så 108.
>> [END VIDEOAFSPILNING]
>> DAVID MALAN: Igen, varsel, han aldrig rørt en given kop mere end én gang
efter at fremme ud over det.
Så han har aldrig gentage.
Så han er altid at flytte til den side, og det er, hvor vi fik vores n.
>> Hvorfor ikke lade mig trække op en animation at vi så tidligere, men denne gang
kun at fokusere på merge slags.
Lad mig gå videre og zoome ind på dette her.
Først lad mig vælge en tilfældig indgang, forstørre det, og du kan sortere i se
hvad vi tog for givet, tidligere, fusionere slags faktisk gør.
>> Så bemærke, at du får disse halve eller disse kvartaler eller disse ottendedele af den
problem, at alle pludselig begynde at tage god form.
Og så endelig, kan du se på allersidst, at bam,
alt er slået sammen.
>> Så disse er blot tre forskellige tager på den samme idé.
Men nøglen indsigt, ligesom kløft og erobre i den allerførste klasse,
var, at vi besluttede at en eller anden måde opdele problemet til noget stort, ind
noget slags identiske i ånden, men mindre og mindre og mindre
og mindre.
>> Nu er en anden sjov måde at sortere i tænke om disse, det, selvom det ikke
kommer til at give dig den samme intuitive forståelse, er
Følgende animation.
Så dette er en video nogen sætte sammen der er knyttet forskellige
lyde med de forskellige operationer for indsættelse sortere, for merge sortere og
for et par andre.
Så i et øjeblik, jeg kommer til at ramme Play.
Det handler om et minut lang.
Og selvom du kan stadig se mønstre sker, denne gang kan du
også høre, hvordan disse algoritmer er udfører forskelligt og med
noget forskellige mønstre.
>> Dette er indsættelse slags.
>> [TONER AFSPILNING]
>> DAVID MALAN: Det igen forsøger at indsætte hvert element
i, hvor det hører hjemme.
Dette er boble slags.
>> [TONER AFSPILNING]
>> DAVID MALAN: Og du kan sortere i føler hvor relativt lidt arbejde det laver
på hvert trin.
Dette er, hvad tediousness lyder.
>> [TONER AFSPILNING]
>> DAVID MALAN: Dette er valg sortere, hvor vi vælger det element, vi ønsker, ved
gå igennem igen og igen og igen og sætte det i begyndelsen.
>> [TONER AFSPILNING]
>> DAVID MALAN: Dette er flette sortere, hvilket kan du virkelig begynde at føle.
>> [TONER AFSPILNING]
>> [Latter]
>> DAVID MALAN: Noget, der hedder gnome sortere, som vi ikke har kigget på.
>> [TONER AFSPILNING]
>> DAVID MALAN: Så lad mig nu se, distraheret som du forhåbentlig er ved
musik, hvis jeg kan smutte lidt bit math her.
Så der er en fjerde måde at vi kan tænke over, hvad det betyder, at disse
funktioner til at være hurtigere end dem at vi har set før.
Og hvis du kommer på kurset fra en matematik baggrund, du
faktisk kender måske allerede, at du kan smække en periode på denne teknik -
nemlig rekursion, en funktion der på en måde kalder sig.
>> Og igen, minde om, at merge sortere pseudokode var rekursive i den forstand
at en af ​​merge sortere taget skridt var at kalde slags -
det er, selv.
Men heldigvis, fordi vi holdt ringer sortere, eller flette sortere,
specifikt på en mindre og mindre og mindre liste, vi i sidste ende
bundede takket være det, vi vil kalde en base tilfælde hard-coded sag,
sagde, at hvis listen er lille, mindre end 2 i så fald vende tilbage lige med det samme.
Hvis vi ikke havde denne særlige tilfælde algoritme ville aldrig bunden,
og du ville faktisk komme ind i en uendelig løkke virkelig evigt.
>> Men formoder, at vi ønskede at nu sætte nogle numre på denne igen, ved hjælp af n
som størrelsen af ​​input.
Og jeg ville gerne spørge dig, hvad er den samlede tid involveret i
kører merge slags?
Eller mere generelt, hvad er omkostningerne ved det i tide?
>> Jamen det er ret nemt at måle det.
Hvis n er mindre end 2, hvor lang tid sagen i sortering n elementer,
hvor n er 2, er 0.
Fordi vi bare vende tilbage.
Der er ikke noget arbejde, der skal gøres.
Nu velsagtens, måske er det et skridt eller to skridt til at finde ud af mængden af
arbejde, men det er tæt nok på 0, at Jeg skal bare sige nej arbejde
påkrævet, hvis listen er så lille at være uinteressant.
>> Men denne sag er interessant.
Den rekursive tilfælde var den gren af pseudokoden der sagde andet, sortere
den venstre halvdel, sortere højre halvdelen, flette de to halvdele.
Nu hvorfor dette udtryk repræsenterer denne udgift?
Nå, T n betyder bare tid til at sortere n elementer.
Og derefter på den højre side af lighedstegn der, T n delte
med 2 hentyder til udgifterne til hvad?
Sortering den venstre halvdel.
Den anden T fra n divideret med 2 er antages at referere til omkostningerne til
sortere højre halvdel.
>> Og så plus n?
Er sammenlægning.
Fordi hvis du har to lister, en af size n over 2 og en anden af ​​størrelse n
over 2, er du nødt til hovedsageligt berøre hver af disse bestanddele, ligesom Rob
rørte hver af kopper, og bare som vi pegede på hvert af de
frivillige på scenen.
Så n er på bekostning af sammenlægning.
>> Nu desværre denne formel er også selv rekursiv.
Så hvis stillede spørgsmålet, hvis n er, siger, 16. Hvis der er 16 personer på scenen
eller 16 kopper i videoen, hvor mange i alt skridt tager det at sortere dem
med merge slags?
Det er faktisk ikke et indlysende svar, fordi du nu nødt til at sortere i
rekursivt besvare denne formel.
>> Men det er OK, fordi lad mig foreslå at vi gør følgende.
Den tid, der til at sortere 16 personer eller 16 kopper vil være repræsenteret
generelt som T 16.
Men der er lig med, i henhold til vores foregående formel, 2 gange den mængde
tid det tager at sortere 8 kopper plus 16.
Og igen, plus 16 er det tid til at fusionere, og to gange T på 8 er
tid til at sortere venstre halvdel og højre halvdel.
>> Men igen, det er ikke nok.
Vi er nødt til at dykke dybere.
Det betyder, at vi er nødt til at besvare spørgsmål, hvad er T på 8?
Nå T på 8 er blot 2 gange T på 4 plus 8.
Jamen, hvad er T på 4?
T på 4 er kun 2 gange T på 2 plus 4.
Jamen, hvad er T af 2?
T på 2 er kun 2 gange T på 1 plus 2.
>> Og igen, vi er sådan at få fast i denne cyklus.
Men det handler om at ramme såkaldt base case.
For hvad er T på 1, vi hævder?
0.
Så nu endelig kan vi arbejde baglæns.
>> Hvis T på 1 er 0, kan jeg nu gå tilbage op en Line til denne fyr her, og jeg kan
plug in 0 for T 1..
Så det betyder, at det er lig med 2 gange nul, ellers kendt som 0, plus 2.
Og så hele udtrykket er 2..
>> Hvis jeg nu tager T på 2, hvis svar er 2, sæt det i den midterste linie, T
af 4, giver det mig 2 gange 2 plus 4, så 8.
Hvis jeg derefter sætte i 8 til den forrige linje, der giver mig 2 gange 8, 16.
Og hvis vi derefter fortsætte at med 24, tilføjer i 16, vi endelig får en
værdi af 64.
>> Nu, i sig selv slags taler intet til n notation, den
big O, omega, at vi har talt om.
Men det viser sig, at 64 er faktisk 16, størrelsen af ​​input,
log base 2 af 16 år.
Og hvis dette er en lille ukendt, bare tænke tilbage, og det vil komme tilbage
til dig sidst.
Hvis dette er log base 2, det er ligesom 2 hævet til hvad der giver dig 16?
Åh, det er 4, så det er 16 gange 4.
>> Og igen, det er ikke en big deal, hvis det er en slags tåget hukommelse nu.
Men for nu, tage på tro at 16 log 16 er 64.
Og så ja, med denne enkle tilregnelighed tjek, vi har bekræftet -
men ikke bevist formelt -
at køretiden for merge sortere er faktisk n log n.
>> Så ikke dårligt.
Det er helt sikkert bedre end den algoritmer, vi har set hidtil, og
Det er fordi vi har gearede, en, en teknik, der kaldes rekursion.
Men mere interessant end det, der begrebet dividere og erobre.
Igen, virkelig uge 0 ting, selv nu er tilbagevendende i en
mere overbevisende måde.
>> Nu er en sjov lille øvelse, hvis du har aldrig gjort det - og du sandsynligvis
ville ikke have, fordi slags normal folk tror ikke at gøre dette.
Men hvis jeg går til google.com, og hvis Jeg ønsker at lære noget om
rekursion Enter.
>> [Latter]
[Mere latter]
DAVID MALAN: Bad joke langsomt breder sig.
[Latter]
DAVID MALAN: Just in case, det er der.
Jeg havde ikke stave det forkert, og der er joke.
Ok.
Forklar det til mennesker ud for dig, hvis Det har ikke helt klikket endnu.
Men rekursion, mere generelt, henvises til processen for en funktion ringer
selv, eller mere generelt, dividere en problem til noget, der kan være
løst stykkevis ved at løse identiske repræsentative problemer.
>> Nå, lad os skifte gear for bare et øjeblik.
Vi vil gerne slutte på visse cliffhangers, så lad os begynde at sætte
scenen, i flere minutter, på en meget enkel idé -
der at bytte to elementer, right?
Alle disse algoritmer vi har været taler om de sidste par
foredrag indebærer en vis slags swapping.
Dag blev visualiseret ved dem at få op af deres stole og
gå rundt, men i koden, ville vi bare tage et element fra en matrix
og plop det i en anden.
>> Så hvordan kan vi gå om at gøre dette?
Nå, lad mig gå videre og skrive en hurtig program her.
Jeg har tænkt mig at gå videre og gøre dette som følgende.
Lad os kalde det -
Hvad ønsker vi at kalde denne ene?
>> Faktisk, nej.
Lad mig spole tilbage.
Jeg ønsker ikke at gøre det cliffhanger endnu.
Det vil ødelægge det sjove.
Lad os gøre det i stedet.
>> Antag, at jeg vil skrive lidt program, og at det nu omfatter det
idé rekursion.
Jeg slags fik forud for mig der.
Jeg har tænkt mig at gøre følgende.
>> Først en hurtig omfatter i standard io.h, samt en include af cs50.h.
Og så jeg har tænkt mig at gå videre og erklære int main void
på sædvanlig måde.
Jeg indså, at jeg har misnamed filen, så lad mig lige tilføje et. c udvidelse her, så
at vi kan kompilere det ordentligt.
Start denne funktion fra.
>> Og den funktion jeg vil skrive, helt enkelt, er en, der spørger
brugeren for en række, og derefter tilføjer op alle de numre mellem denne
nummer og, siger, 0.
Så først vil jeg tænkt mig at gå videre og erklærer, int n.
Så jeg kopiere noget kode, der Vi har brugt et stykke tid.
Mens noget er sandt.
Jeg kommer tilbage til om et øjeblik.
>> Hvad ønsker jeg at gøre?
Jeg vil gerne sige printf positive integer venligst.
Og så vil jeg sige n får få int.
Så igen, nogle standardtekst kode at vi har brugt før.
Og jeg har tænkt mig at gøre dette mens n er mindre end 1.
Så dette vil sikre, at brugeren giver mig et positivt heltal.
>> Og nu vil jeg gøre følgende.
Jeg ønsker at tilføje op alle de numre mellem 1 og og n eller 0 og n,
ækvivalent, for at få den totale sum.
Så det store sigma symbolet som du måske husker.
Så jeg har tænkt mig at gøre dette ved første kald en funktion kaldet sigma
passerer den i n, og så vil jeg siger printf, er svaret lige der.
>> Så kort sagt, jeg får, og int fra brugeren.
Jeg sikre, at det er positivt.
Jeg erklærer en variabel kaldet svar typen int og butik i det afkastet
værdi af sigma, passerer i n som input.
Og så kan jeg udskrive det svar.
>> Desværre, selvom sigma lyde som noget, der kan være i
Den math.h filen sin erklæring, det er faktisk ikke.
Så det er OK.
Jeg kan gennemføre denne selv.
Jeg har tænkt mig at gennemføre en funktion kaldet sigma, og det kommer til at tage et
parameter -
lad os bare kalde det m, bare så det er anderledes.
Og så op her, vil jeg sige, Tja, hvis m er mindre end 1 - dette er en
meget uinteressant program.
Så jeg har tænkt mig at gå videre og øjeblikkeligt returnere 0.
Det bare ikke giver mening at tilføje op alle tallene mellem 1 og m, hvis m
er selv 0 eller negativ.
>> Og så jeg har tænkt mig at gå videre og gøre det meget iterativt.
Jeg har tænkt mig at gøre denne form for old-school, og jeg har tænkt mig at gå videre
og sige, at jeg har tænkt mig at erklære en sum til at være 0.
Så jeg har tænkt mig at have en for-løkke af int -
og lad mig gøre det til at matche vores fordeling kode, så du har en kopi
derhjemme. int i får 1 på op til i er mindre end eller lig med ca.
Jeg plus plus.
Og så på indersiden af ​​dette for loop -
Vi er der næsten -
sum får sum plus 1.
Og så jeg har tænkt mig at returnere beløbet.
>> Så jeg gjorde det hurtigt, ganske ganske.
Men igen, hvis hovedfunktion er temmelig ligetil, er baseret på kode, vi har
skrevet hidtil.
Bruger den dobbelte loop til at få en positiv int fra brugeren.
Jeg så videregive denne int til en ny funktion kaldet sigma, kalder det, igen, n.
Og jeg gemmer returværdien, svaret fra den sorte boks i øjeblikket
kendt som sigma, i en variabel kaldet svar.
Så jeg udskrive det.
>> Hvis vi nu fortsætte historien, hvordan sigma gennemført?
Jeg foreslår at gennemføre som følger.
Først en lille smule af fejlkontrol for at sikre, at brugeren ikke er
rode med mig og passerer nogle negative eller 0 værdi.
Så jeg erklære en kaldet variabel opsummere og sæt den til 0.
>> Og nu begynder jeg at flytte fra jeg lig 1 hele vejen op til og med m,
fordi jeg ønsker at medtage alle de tal fra en gennem m, inklusive.
Og inde i dette for loop, jeg bare gøre sum får hvad det nu er, plus
værdi af i.
Plus værdien af ​​jeg.
>> Som en sidebemærkning, hvis du ikke har set det før, er der nogle syntaktiske sukker
for denne linje.
Jeg kan omskrive dette som plus lig i, bare for at spare mig selv et par tastetryk
og til at se en smule køligere.
Men det er alt.
Det er funktionelt det samme.
>> Desværre denne kode er ikke kommer til at kompilere endnu.
Hvis jeg kører gør sigma 0, hvordan am Jeg kommer til at få råbte på?
Hvad går det ikke at lide?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: Ja, havde jeg ikke erklære funktionen op øverst, right?
C er en slags dum, at den kun gør hvad du fortæller det til at gøre, og du
nødt til at gøre det i den rækkefølge.
Og så hvis jeg ramte Skriv her, vil jeg får en advarsel om sigma implicit
erklæring.
>> Oh, ikke et problem.
Jeg kan gå op til toppen, og jeg kan sige, okay, vent et øjeblik.
Sigma er en funktion, der returnerer en int, og det forventer en
int som input, semikolon.
Eller jeg kunne sætte hele funktionen over main, men i almindelighed, ville jeg
anbefale mod det, fordi det er rart altid at have main øverst, så
du kan dykke lige ind og vide, hvad en Programmet laver ved at læse main først.
>> Så lad mig rydde skærmen.
Remake sigma 0.
Alt ser ud til at tjekke ud.
Lad mig køre sigma 0.
Positiv indbyrdes.
Jeg vil give det et nummer 3 for at holde det simpelt.
Så det skulle give mig 3 plus 2 plus 1, så 6..
Indtast, og faktisk får jeg 6.
>> Jeg kan gøre noget større -
50, 12, 75.
Ligesom en tangent, jeg kommer til at gøre noget latterligt som en virkelig stor
nummer, Åh, der faktisk arbejdede ud -
eh, tror jeg ikke, det er rigtigt.
Lad os se.
Lad os virkelig rodet med det.
>> Det er et problem.
Hvad sker der?
Koden er ikke så slemt.
Det er stadig lineær.
Whistling er en god effekt, selv om.
Hvad sker der?
>> Ikke sikker på om jeg hørte det.
Så det viser sig - og dette er som en sidebemærkning.
Dette er ikke core til idé rekursion.
Det viser sig, fordi jeg forsøger at repræsenterer sådan et stort tal, de fleste
sandsynligt er det at blive misforstået af C som en ikke positivt tal,
men negativt tal.
>> Vi har ikke talt om det, men det viser sig at der er negative tal
i verden desuden til positive tal.
Og de midler, som du kan repræsentere et negativt tal
det væsentlige, du bruger en særlig bit at angive
positive end negative.
Det er lidt mere kompliceret end som så, men det er den grundlæggende idé.
>> Så desværre hvis C er forvirrende én af disse bits som rent faktisk betyder,
Åh, det er et negativt tal, min loop her, for eksempel, er faktisk aldrig
vil afslutte.
Så hvis jeg var faktisk udskrivning noget igen og igen, ville vi
se en hel masse.
Men igen, dette er ud over punktet.
Dette er egentlig bare en slags intellektuelle nysgerrighed, som vi vil komme
tilbage til sidst.
Men for nu, er dette en korrekt implementering, hvis vi antager, at
Brugeren vil give int'er der passer inden int'er.
>> Men jeg hævder, at denne kode, helt ærligt, kunne gøres så meget mere simpelt.
Hvis målet ved hånden er at tage en række Ligesom m og tilføje op alle de
tal mellem det og 1, eller omvendt mellem 1 og det hævder jeg
at jeg kan låne denne idé at fusionere sortere havde, som tog et problem
af denne størrelse og dividere det til noget mindre.
Måske ikke halvt, men mindre, men repræsentativt den samme.
Samme idé, men et mindre problem.
>> Så jeg faktisk - lad mig gemme denne fil med en anden version nummer.
Vi kalder denne udgave 1 i stedet for 0.
Og jeg hævder, at jeg rent faktisk kan reimplement dette i denne form for
hjernevridende måde.
>> Jeg har tænkt mig at lade en del af det alene.
Jeg har tænkt mig at sige, hvis m er mindre end eller endda lig med 0 -
Jeg skal bare være lidt mere anal denne gang
med min fejlkontrol -
Jeg har tænkt mig at gå videre og returnere 0.
Dette er vilkårlig.
Jeg er bare blot at beslutte, hvis brugeren giver mig et negativt tal, jeg er
returnere 0, og de bør have læst dokumentationen nærmere.
>> Else -
mærke til, hvad jeg har tænkt mig at gøre.
Else jeg kommer til at vende tilbage m plus -
hvad er sigma af m?
Nå, sigma af m plus m minus 1, plus m minus 2, plus m minus 3.
Jeg ønsker ikke at skrive alt det ud.
Hvorfor kan jeg ikke bare punt?
Rekursivt kalde mig selv med en lidt mindre problem, semikolon,
og kalder det en dag?
>> Right?
Nu også her, kan du føler eller bekymre at dette er en uendelig løkke, som jeg
overtalelse, hvorved jeg gennemføre sigma ved at kalde sigma.
Men det er helt OK, fordi jeg troede forude en ekstra hvilke linjer?
>> PUBLIKUM: [uhørlig].
>> DAVID MALAN: 23 til 26, hvilket er min hvis tilstand.
For hvad er rart om de subtraktion her, for jeg holder
afleverer sigma mindre problemer, mindre problemer, mindre - det er ikke
halv størrelse.
Det er kun en baby skridt mindre, men det er OK.
Fordi i sidste ende, vil vi arbejde vores vej ned til 1 eller 0.
Og når vi ramte 0, sigma er ikke kommer til at kalde sig selv længere.
Det kommer til at øjeblikkeligt returnere 0.
>> Så effekten, hvis du slags vind dette op i dit sind, er at tilføje m plus
m minus 1 plus m minus 2, plus m minus 3, plus dot, dot, dot, m minus
m, i sidste ende giver dig 0 og effekt er i sidste ende at tilføje alle
disse ting sammen.
Så vi har ikke med rekursion, løste det problem, som vi
kunne ikke løse før.
Faktisk udg.0 af dette, og hver problem til dato har været løselige
med blot bruger til loops, eller mens løkker eller lignende konstruktioner.
>> Men rekursion, jeg tør sige, giver os en anden måde at tænke på
problemer, hvor hvis vi kan tage en problem, opdele det fra noget
noget stort til noget lidt mindre, jeg påstå, at vi kan løse det
måske lidt mere elegant i form af design, med mindre kode
og måske endda løse problemer, der ville være sværere, da vi vil i sidste ende
se, løse rent iterativt.
>> Men cliffhanger, som jeg gjorde ønsker at forlade os på var dette.
Lad mig gå videre og åbne en fil fra -
faktisk, lad mig gå, og gøre dette virkelig hurtigt.
Lad mig gå videre og foreslå følgende.
Blandt dagens kode er denne fil her.
Denne ene her noswap.
>> Så dette er en dum lille program, Jeg pisket op, der hævder at gøre
følgende.
I main, først den erklærer en int kaldet x og tildeler den
værdien af ​​1..
Så erklærer en int y og tildeler den værdien 2.
Så udskriver hvad x og y er.
Så det siger, bytte, dot dot dot.
>> Så er det hævder at være at kalde en funktion kaldet swap, der passerer i x-og
y, tanken om at der, som forhåbentlig x og y vil komme tilbage
anderledes, det modsatte.
Så er det hævder byttet!
med et udråbstegn.
Så den udskriver x og y.
>> Men det viser sig, at denne meget simple demonstration ned
her er faktisk buggy.
Selvom jeg erklære en midlertidig variabel og midlertidigt at sætte en i
det, så er jeg omfordeling en værdien af ​​b -
som føles rimelige, fordi jeg har gemt en kopi af en i temp.
Så jeg opdatere b til lige uanset var i temp.
Denne form for shell spil at flytte en i b og b til en ved hjælp af denne
midt-mand kaldet temp føler helt rimeligt.
>> Men jeg hævder, at når jeg kører denne kode, som jeg vil gøre nu -
lad mig gå videre og indsætte det her.
Jeg ringer denne noswap.c.
Og som navnet antyder, er dette ikke kommer til at være et korrekt program.
Gør noswap. / Nej swap.
x er 1, y er 2, swapping, byttes.
x er 1, y er 2.
Dette er fundamentalt forkert, selv selvom dette synes perfekt
rimeligt for mig.
Og der er en grund, men vi er ikke vil afsløre årsagen endnu.
>> For nu anden cliffhanger jeg ønskede at efterlade dig med, er dette en
annonceringen af ​​sorterer på kupon koder.
Vores innovation med sene dage i år har fremprovokeret en ikke-triviel nummer
spørgsmål, som var ikke vores hensigt.
Hensigten med disse kupon koder, hvorved, hvis du gør en del af problemet
sætte tidligt, og derved få en ekstra dag, var virkelig til at hjælpe jer hjælpe
selv starte tidligt, sort af ved incentivizing dig.
Hjælper os distribuere belastningen over kontortid bedre, så
Det er en slags win-win.
>> Jeg tror desværre, mine anvisninger har ikke været til dato, meget klar, så
Jeg gik tilbage denne weekend og opdateret spec i større, federe tekst til
forklare kugler som disse.
Og bare for at sige det mere offentligt, ved standard, problemløsning sæt skyldes torsdag
ved middagstid, pr. pensum
Hvis du starter tidligt, efterbehandling en del af det problem fastsat senest onsdag kl 12:00
PM, den del, der vedrører en kupon kode, ideen er, at du kan udvide
din deadline for P sæt til fredag.
Det vil sige, lidt fra en meget lille del af P sæt i forhold til hvad typisk er
større problem, og du kan købe selv en ekstra dag.
Igen, det får du tænker problemet sæt, får dig til
kontortid før.
Men kuponkode problemet stadig påkrævet, selvom du ikke sende det.
>> Men mere uimodståelig er dette.
(Teaterhvisken) Og disse folk forlader tidligt er gonna fortryde det.
Da er de folk på balkonen.
Jeg undskylder på forhånd til folk på balkonen grunde, der vil være
klart på bare et øjeblik.
>> Så vi er heldige at have en af CS50 tidligere hoved undervisning stipendiater på
et firma kaldet dropbox.com.
De har meget generøst doneret en kuponkode her for denne meget plads,
der er op fra sædvanlige 2 gigabyte.
Så hvad jeg troede, vi ville gøre på dette afsluttende bemærkning er at gøre lidt af en foræring,
hvorved i bare et øjeblik, vil vi afsløre vinderen og som har en kupon
kode, som du derefter kan gå til deres website, skal du skrive det i, og voila, få en
hel masse mere Dropbox plads til dine apparat og til dine personlige filer.
>> Og først, hvem ville gerne deltage i denne tegning?
OK, nu gør det endnu sjovere.
Den person, der modtager denne 25-gigabyte kuponkode - hvilket er langt
mere overbevisende end den sene dage nu, måske -
er den, der sidder på toppen af ​​en siddepude hvorunder der er
at kuponkode.
Du kan nu se nedenunder Deres sædehynden.
>> [VIDEO AFSPIL]
>> -En, to, tre.
>> [SCREAMING]
>> -Du får en bil!
Du får en bil!
>> DAVID MALAN: Vi vil se, dig på onsdag.
>> -Du får en bil!
Du får en bil!
>> DAVID MALAN: Balcony folkens, kom hernede til fronten,
hvor vi har ekstramateriale.
>> -Alle får en bil!
Alle får en bil!
>> [END VIDEOAFSPILNING]
>> Fortæller: På det næste CS50 -
>> SPEAKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh -
>> [Ukelele PLAYS]