>> [Muziek]
DAVID Malan: Oke.
Oke, welkom terug.
Dus dit is Week 4, het begin daarvan, reeds.
En je zult zien dat vorige week herinneren, we zetten coderen gereserveerd voor slechts een klein beetje
en we begonnen te praten een beetje meer hoog niveau, over zaken als
zoeken en sorteren, die, hoewel ietwat simpele ideeën, zijn
vertegenwoordiger van een categorie problemen je zult beginnen te bijzonder lossen
als je begint te denken over het uiteindelijke projecten en interessante oplossingen die u
zou kunnen hebben om echte problemen.
Nu bubble sort was een van de eenvoudigste dergelijke algoritmen, en
gewerkt door het hebben van deze kleine aantallen in een lijst of in een array soort
bubble hun weg naar de top, en de grote aantallen bewegen hun weg naar
het einde van die lijst.
>> En herinner me dat we konden visualiseren bubble sort een beetje
zoiets als dit.
Dus laat me ga je gang en klik op Start.
Ik heb bubble sort voorgeselecteerd.
En als u zich herinneren dat het langer blauw lijnen stellen grote aantallen, kleine
blauwe lijnen geven kleine aantallen, zoals we gaan door dit opnieuw en opnieuw en
opnieuw vergelijken van twee staven naast elkaar andere in rood, gaan we de swap
grootste en de kleinste indien ze zijn niet in orde.
>> Dus dit zal gaan en gaan en gaan op, en je zult zien dat het voor een uitvergroting
elementen maken hun weg naar de rechts, en de kleinere elementen zijn
maken hun weg naar links.
Maar we begonnen te kwantificeren efficiëntere,
kwaliteit van dit algoritme.
En we zeiden dat in het ergste geval dit algoritme nam
ruwweg hoeveel stappen?
>> Zo n kwadraat.
En wat was n?
>> PUBLIEK: Aantal elementen.
>> DAVID Malan: Zo n was de aantal elementen.
En dus zullen we dit vaak.
Elke keer als we willen praten over de grootte van een probleem of de grootte van een
ingang of de hoeveelheid tijd die het kost om output te produceren, zullen we gewoon
gegeneraliseerde wat de ingang is zo n.
Dus terug in week 0, het aantal pagina's in het telefoonboek was n.
Het aantal studenten in de kamer was n.
Dus ook hier, we volgen dat patroon.
>> Nu n kwadraat is niet bijzonder snel, dus we probeerden het beter te doen.
En dus hebben we gekeken naar een paar andere algoritmen, waaronder
waren selectie sorteren.
Dus selectie sorteren was een beetje anders.
Het was bijna eenvoudiger, ik durf te zeggen, waarbij ik begon aan het begin van de
overzicht van onze vrijwilligers en ik gewoon weer en opnieuw en opnieuw ging door
de lijst, plukken uit de kleinste element in een tijd en zetten hem of
haar aan het begin van de lijst.
>> Maar ook dit keer begonnen we te denken door de wiskunde en groter
beeld, dacht na over hoe vaak Ik werd heen en weer en weer terug
en weer, we zeiden in het ergste geval, selectie sorteren was ook wat?
n kwadraat.
Nu in de echte wereld, is het misschien eigenlijk marginaal sneller.
Want nogmaals, ik heb niet moeten blijven backtracking zodra ik had naargelang de
kleinste elementen.
Maar als we denken aan zeer grote n, en als je soort te doen uit de wiskunde als
Ik heb op het bord, met de n kwadraat minus iets, alles anders
Naast de n kwadraat, zodra n wordt echt groot, niet
echt zo veel uit.
Dus als informatici, we soort van oogluikend naar de kleinere
factoren en aandacht alleen op de factor een uitdrukking die gaat om
het grootste verschil.
>> Nou, ten slotte, hebben we gekeken bij insertion sort.
En dit was in dezelfde geest, maar in plaats van te gaan door iteratief en
selecteer het kleinste element een voor een tijd, in plaats daarvan nam ik de hand die ik
werd behandeld, en ik besloot, alle rechts, je hoort hier.
Daarna verhuisde ik naar het volgende element en besloot dat hij of
Ze behoorde hier.
En toen bewoog ik op en op.
En ik zou aan, langs de weg, verschuiven deze jongens om
maak ruimte voor hen.
Dus dat was een soort van de mentale ommekeer van selectie soort dat we
riep insertion sort.
>> Dus deze onderwerpen voor te komen in de echte wereld.
Gewoon een paar jaar geleden, toen een zekere senator voor voorzitter liep,
Eric Schmidt, op het moment dat de CEO van Google, in feite de gelegenheid gehad
om hem te interviewen.
En we dachten dat we zouden dit YouTube delen clip voor u hier, als we zouden kunnen opduiken
het volume.
>> [VIDEO AFSPELEN]
>> -Nu, Senator, je bent hier bij Google, en ik denk graag dat het voorzitterschap
als een sollicitatiegesprek.
>> [Lachen]
>> -Nu is het moeilijk te krijgen een baan als president.
En je gaat door de ontberingen nu.
Het is ook moeilijk om een ​​baan bij Google te krijgen.
Wij hebben vragen en wij vragen onze kandidaten vragen.
En deze is van Larry Schwimmer.
>> [Lachen]
-Jullie denken dat ik een grapje maak?
Het is hier.
Wat is de meest efficiënte manier om sorteren een miljoen twee-bits gehele getallen?
>> [Lachen]
>> -Nou, uh -
>> Het spijt me.
Misschien moeten we -
>> -Nee, nee, nee, nee, nee.
>> -Dat is niet een -
OK.
>> -Ik denk dat de bubble sort zou zijn de verkeerde weg te gaan.
>> [Lachen]
>> [Gejuich en applaus]
>> -Kom op, die hem dit verteld?
OK.
>> [END VIDEO AFSPELEN]
>> DAVID Malan: Dus daar heb je het.
Dus we begonnen te kwantificeren deze bedrijfskosten tijden, om zo te zeggen, met iets
genoemd asymptotische notatie, hetgeen alleen over onze soort te draaien
een oogje op die kleinere factoren en alleen kijken naar de looptijd,
de uitvoering van deze algoritmen, zo n krijgt echt grote tijd.
En dus hebben we geïntroduceerd grote O. En big O vertegenwoordigd iets dat we dachten
van als een bovengrens.
En eigenlijk, Barry, kunnen we verlagen dan de microfoon een beetje?
>> We dachten dat dit is een bovengrens.
Zo groot O van n kwadraat betekent dat in het ergste geval, zoiets als
selectie sorteren zou nemen n kwadraat stappen.
Of iets als insertion sort zou n kwadraat stappen.
Nu voor iets als inbrengen sorteren, wat het ergste geval was?
Gegeven een array, wat is het ergste mogelijke scenario dat je zou kunnen vinden
je geconfronteerd wordt met?
>> Het is volledig achteruit, toch?
Want als het helemaal naar achteren, moet je een heleboel werk te doen.
Want als je helemaal naar achter bent, je gaat naar het vinden
grootste element hier, hoewel het behoort daar beneden.
Dus je gaat zeggen, oke, op dit moment in de tijd, hier u behoort,
zodat je hem met rust laat.
>> Dan besef je, oh, damn, ik moet verplaats deze iets kleiner element aan
links van u.
Dan moet ik dat opnieuw doen en weer.
En als ik liep heen en weer, je zou soort van voelen de prestaties van
dat algoritme, omdat steeds ben ik schuifelen iedereen die in de
array om ruimte te maken voor het.
Dus dat is het ergste geval.
>> Daarentegen -
en dit was een cliffhanger vorige keer -
zeiden we dat insertion sort was een omega van wat?
Wat is de best-case running tijd van insertion sort?
Dus het is eigenlijk n.
Dat was het leeg dat we vertrokken op het bord vorige keer.
>> En het is omega van n want waarom?
Nou, in het beste geval, wat is insertion sort gaat worden overhandigd?
Nou ja, een lijst die volledig is naargelang al, een minimum aan werk te doen.
Maar wat is er netjes over insertion sort is dat omdat het begint hier en
beslist, oh, jij bent de nummer een, je hoort hier.
O, wat een geluk.
>> Jij bent de nummer twee.
Jij ook hier hoort.
Nummer drie, nog beter, jij hier thuis.
Zodra het wordt om het einde van de pseudocode lijst, per insertion sort's
dat we liepen door mondeling vorige keer, is het gedaan.
Maar selectie sorteren daarentegen bleef doen wat?
>> Bleef gaan door de lijst opnieuw en opnieuw en opnieuw.
Omdat het belangrijk inzicht was er slechts zodra je de hele weg heb gekeken naar de
einde van de lijst kunt u er zeker van zijn dat het element dat u gekozen was
inderdaad nog kleinste element.
Dus deze verschillende mentale modellen einde up waardoor een aantal zeer reële-wereld
verschillen voor ons, evenals deze theoretische asymptotische verschillen.
>> Dus gewoon om samen te vatten, dan, grote O van n kwadraat, hebben we gezien hoe een paar van zulke
algoritmen tot nu toe.
Big O van n?
Wat is een algoritme dat kon worden gezegd dat grote O van n?
In het ergste geval is een lineaire aantal stappen.
>> OK, lineair zoeken.
En in het ergste geval, wanneer de element dat u zoekt bij
toepassen van lineaire zoeken?
>> OK, in het ergste geval, het is zelfs daar niet.
Of in het tweede slechtste geval, het is helemaal op het einde, dat is
plus-of minus-een stap verschil.
Dus aan het eind van de dag, we kunnen zeggen dat het lineair.
Big O van n zou lineair zoeken zijn, omdat in het ergste geval, de
element is ook daar niet of het is helemaal aan het einde.
>> Nou, big O van log van n.
We praatten niet in detail over dit, maar we hebben dit eerder gezien.
Wat loopt in zogenaamde logaritmische tijd, in het ergste geval?
>> Ja, dus binair zoeken.
En binaire in de worst case kan het element ergens in zijn
het midden, of ergens binnen de array.
Maar u alleen te vinden als je eenmaal verdelen de lijst in de helft, in
half, in half, in half.
En dan voila, het is er.
Of nog, het ergste geval, het is zelfs daar niet.
Maar je weet niet dat het er niet is totdat je soort te bereiken dat laatste
onderste elementen door halvering en halveren en halveren.
>> Big O van 1.
Dus konden we grote O van 2, grote O van 3.
Wanneer je maar wilt gewoon een constant aantal, we gewoon soort van gewoon te vereenvoudigen
dat zo groot O van 1.
Hoewel als realistisch, duurt 2 of zelfs 100 treden, als het een
constant aantal stappen, we gewoon zeggen grote O van 1.
Wat is een algoritme dat is in grote O van 1?
>> PUBLIEK: Het vinden van de lengte een variabele.
>> DAVID Malan: Het vinden van de lengte van een variabele?
>> PUBLIEK: Nee, de lengte indien deze al is opgelost.
>> DAVID Malan: Good.
OK, dus het vinden van de lengte van iets Als de lengte van dat wat, zoals
een array, wordt opgeslagen in een aantal variabele.
Want je kunt gewoon lezen van de variabele, of print de variabele of
gewoon over het algemeen toegang tot die variabele.
En voila, dat constante tijd kost.
>> Daarentegen denkt terug te krabben.
Denk terug aan de eerste week van C, gewoon printf bellen en printen
iets op het scherm is aantoonbaar constante tijd, want het duurt slechts
sommige aantal CPU-cycli te tonen dat de tekst op het scherm.
Of wacht - doet het?
Hoe anders kunnen we modelleren de prestaties van printf?
Zou iemand willen oneens, dat misschien is het niet echt constant tijd?
In welke zin zou printf loopt tijd, eigenlijk het afdrukken van een snaar op
het scherm, iets dan constant.
>> PUBLIEK: [onverstaanbaar].
>> DAVID Malan: Yeah.
Dus het hangt af van ons perspectief.
Als we eigenlijk denken van de input aan printf als de string, en
dus de grootte van dat meten we ingang door zijn lengte - dus laten we noemen
die lengte n, alsook -
betwistbaar, printf is zelf grote O van n omdat het gaat om je n stappen te ondernemen
uit te printen elk van deze n karakters, waarschijnlijk.
Althans voorzover we aannemen dat misschien is het gebruik van een lus
onder de motorkap.
>> Maar we zouden moeten kijken naar dat coderen om het beter te begrijpen.
En inderdaad, zodra jullie beginnen het analyseren van uw eigen algoritmes, je zult
letterlijk dat ook te doen.
Soort oogbol uw code en denken over - oke, ik heb deze lus
hier of ik heb een geneste lussen hier, dat gaat n dingen n keer, doe
en u kunt sorteren van reden uw weg door de code, zelfs als het
pseudocode en niet de werkelijke code.
>> Dus hoe zit het omega van n kwadraat?
Wat is een algoritme dat de beste geval, nam nog n kwadraat stappen?
Yeah?
>> PUBLIEK: [onverstaanbaar].
>> DAVID Malan: So selectie sorteren.
Want in dat probleem echt verminderd aan het feit dat nogmaals, ik weet het niet
Ik heb gevonden de huidige kleinste tot Ik heb alle darn elementen gecontroleerd.
Dus omega van, zeg, n, we net kwam met een.
Insertion sort.
Als de lijst gebeurt te sorteren reeds, in het beste geval hebben we alleen maar
om een ​​doorgang te maken doorheen, op welk punt we zeker.
En dan dat kan worden gezegd lineair te zijn, zeker.
>> Hoe zit het omega van 1?
Wat, in het beste geval, zou kunnen nemen een constant aantal stappen?
Zo lineair zoeken, als je gewoon geluk en het element dat u op zoek bent
is meteen aan het begin van de lijst, als dat is waar je begint je
lineaire traversal van die lijst.
>> En dit geldt voor een aantal dingen.
Bijvoorbeeld, zelfs binaire zoek is omega van 1.
Want wat als je echt darn geluk en smack-dab in het midden van
de array is het aantal u zoekt?
Dus je kunt daar je geluk, als goed.
>> Deze, ten slotte, omega van n log n.
Zo n log n, we deden niet echt praten over nog niet, maar -
>> PUBLIEK: sorteer samenvoegen?
>> DAVID Malan: Merge sort.
Dat was de cliffhanger van de vorige keer, waar we voorgesteld en we kwamen
visueel, dat er algoritmen.
En samenvoegen soort slechts een dergelijke algoritme die fundamenteel sneller
dan sommige van die andere jongens.
In feite, samenvoegen kort is niet alleen in de beste geval n log n, in het slechtste
geval n log n.
En als je dit samenvallen van omega en grote O is hetzelfde ding?
We kunnen eigenlijk omschrijven dat als wat genaamd theta, al is het een
iets minder vaak voor.
Maar dat betekent dat de twee grenzen, in dit geval zijn hetzelfde.
>> Dus samenvoegen soort, wat betekent dit echt neer op voor ons?
Nou, herinneren aan de motivatie.
Laat ik trek een andere animatie die We keken niet naar vorige keer.
Deze, hetzelfde idee, maar het is een beetje groter.
En ik ga je gang gaan en wijzen eerste - we hebben insertion sort op
linksboven, dan selectie sorteren, bubble sort, een paar andere soorten -
shell en snel - dat we niet hebben gesproken over, en hoop en samenvoegen sorteren.
>> Dus op zijn minst proberen om uw ogen te focussen op de top drie aan de linkerkant en vervolgens
merge sort als ik klik Deze groene pijl.
Maar ik laat ze allemaal lopen, gewoon om te geven je een gevoel van de diversiteit van
algoritmen die in de wereld bestaan.
Ik ga dit te laten lopen voor slechts een paar seconden.
En als je je ogen richten - kies een algoritme, gericht op het voor slechts een
seconden - u zult beginnen om het te zien patroon dat het uitvoering.
>> Merge sort, bericht, wordt gedaan.
Heap sort, snel sorteren, shell -
dus het lijkt erop dat we de drie geïntroduceerd slechtste algoritmen vorige week.
Maar dat is goed, dat wij hier vandaag te kijk naar merge sort, dat is een van
het gemakkelijker degenen is om naar te kijken, zelfs hoewel het waarschijnlijk zal je geest buigen
maar een klein beetje.
Hier kunnen we zien hoeveel selectie sorteren zuigt.
>> Maar aan de andere kant, het is heel eenvoudig te implementeren.
En misschien voor P Set 3, dat is een van de algoritmes je ervoor kiest om te implementeren
voor de standaard editie.
Prima, volkomen juist.
>> Maar nogmaals, als n groot wordt, als je kiezen voor een sneller algoritme te implementeren
willen samenvoegen sorteren, kansen zijn in grotere en grotere ingangen, uw code is gewoon
gaan om sneller te lopen.
Uw website gaat beter werken.
Uw gebruikers zullen gelukkiger zijn.
En dus zijn er deze effecten van daadwerkelijk geven
ons een diepere gedachte.
>> Dus laten we eens kijken naar wat fuseren soort is eigenlijk alles over.
Het koele ding is dat fuseren sort is gewoon dit.
Dit is, nogmaals, wat we hebben genoemd pseudocode pseudocode wezen
Engels-achtige syntax.
En de eenvoud soort fascinerend.
>> Dus op de input van n elementen - zodat betekent gewoon, hier is een array.
Het is n dingen in het kregen.
Dat is alles wat we daar zeggen.
>> Als n kleiner is dan 2, terugkeren.
Dus dat is gewoon de triviale zaak.
Als n kleiner is dan 2, dan is het uiteraard 1 of 0, waarbij de zaak
al naargelang of niet-bestaand, dus gewoon terug.
Er is niets te doen.
Dus dat is een simpel geval af te plukken.
>> Anders, we hebben drie stappen.
Sorteer de linkerhelft van de elementen, sorteren de rechterhelft van de elementen,
en dan fuseren de gesorteerde helften.
Wat interessant is dat Ik ben soort van punteren, toch?
Er is een soort van een circulaire definitie dit algoritme.
In welke zin is dit algoritme's definition ronde?
>> PUBLIEK: [onverstaanbaar].
>> DAVID MALAN: Ja, mijn sorteer-algoritme, twee van haar stappen zijn "soort
iets. 'En dat roept de vraag, goed, wat ik ga gebruiken
de linkerhelft sorteren en de rechterhelft?
En het mooie is dat alhoewel nogmaals, dit is de mind-bending
deel potentieel, kunt u gebruik maken van dezelfde algoritme om de linkerhelft sorteren.
>> Maar wacht eens even.
Als je verteld om het te sorteren linkerhelft, wat zijn de twee
stappen heen te zijn?
We zullen de linker helft van de gekozen afstand linker en rechter
helft van de linkerhelft.
Verdomme, hoe sorteer ik die twee helften of kwarten, nu?
>> Maar dat is OK.
We hebben hier een sorteer-algoritme.
En hoewel je zou kunnen zorgen bij eerste is dit soort van een oneindige
lus, het is een cyclus die is nooit gaat eindigen - het gaat om
eindigen wanneer wat gebeurt er?
Zodra n kleiner is dan 2.
Die uiteindelijk gaat gebeuren, want als je blijft halveren en
halvering in halveren deze helften, zeker uiteindelijk je gaat eindigen
met slechts 1 of 0 elementen.
Op welk punt, dit algoritme zegt dat je klaar bent.
>> Dus de echte magie in deze algoritme lijkt in
die laatste stap, het samenvoegen.
Dat simpel idee gewoon samenvoegen van twee dingen, dat is wat er uiteindelijk gaat
om ons in staat om een ​​scala van sorteren, laten we zeggen, acht elementen.
Dus ik heb acht meer stress ballen omhoog hier, acht stukjes papier, en een
Google Glass -
die ik krijg te houden.
>> [Lachen]
>> DAVID Malan: Als we acht konden nemen vrijwilligers, en laten we kijken of we kunnen
spelen dit uit, zo.
Wow, OK.
Informatica wordt steeds leuk.
Oke.
Dus hoe zit je drie, grootste de hand daar.
Vier in de rug.
En hoe zit zullen wij u doen drie in deze rij?
En vier aan de voorkant.
Dus je acht, kom op maximaal.
>> [Lachen]
>> DAVID Malan: Ik ben eigenlijk niet zeker wat het is.
Is het de stress ballen?
De bureaulampen?
Het materiaal?
Het internet?
>> OK.
Dus kom op omhoog.
Wie zou willen -
blijven komen.
Laten we eens kijken.
En dit zet je in de locatie -
je bent in een locatie.
Uh-oh, wacht even.
1, 2, 3, 4, 5, 6, 7 - oh, goed.
Oke, we zijn goed.
Oke, dus iedereen een zitplaats, maar niet op de Google Glass.
Laat me in de rij deze omhoog.
Wat is je naam?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle?
Oke, krijg je te zien als de geek, als dat is OK.
Nou, ik ook doen, denk ik, voor slechts een moment.
Oke, standby.
We hebben geprobeerd om te komen met een use case voor Google Glas, en we
vond het leuk om gewoon te doen zou zijn dit wanneer mensen op het podium.
We zullen de wereld opnemen vanuit hun perspectief.
Oke.
Niet waarschijnlijk wat Google bedoeld.
Oke, als je het niet erg dragen dit voor de volgende lastige minuten,
dat zou geweldig zijn.
>> Oke, dus we hebben hier een scala aan elementen, en de matrix, volgens de
stukjes papier in deze mensen ' handen, wordt momenteel ongesorteerd.
>> MICHELLE: Oh, dat is zo raar.
>> DAVID Malan: Het is vrij veel willekeurig.
En in slechts een moment, we gaan proberen te implementeren samenvoegen sorteren
en zie waar dat belangrijk inzicht is.
En de truc hier met merge sort is iets dat we nog niet hebben aangenomen.
We hebben eigenlijk een aantal extra ruimte.
Dus wat gaat bijzonder worden interessante hieraan is dat deze
jongens gaan bewegen een beetje beetje, want ik ga ervan uit dat
er is een extra serie van ruimte, zeggen, vlak achter hen.
>> Dus als ze achter hun stoel, dat is de secundaire array.
Als ze hier zitten, dat is de primaire matrix.
Maar dit is een bron die we hebben niet tot zover leveraged met bel
soort, met selectie sorteren, met insertion sort.
Vorige week herinneren, iedereen gewoon soort schuifelde op zijn plaats.
Ze gebruikten geen extra geheugen.
We hebben ruimte voor mensen met bewegende mensen rond.
>> Dus dit is een belangrijk inzicht, ook.
Er is deze trade-off, in het algemeen in computer wetenschap, van middelen.
Als je wilt versnellen iets zoals tijd, je gaat
een prijs moeten betalen.
En een van die prijzen is heel vaak ruimte, de hoeveelheid geheugen of harde
schijfruimte die u gebruikt.
Of, eerlijk gezegd, het bedrag van de programmeur tijd.
Hoeveel tijd het kost u, de mens, om daadwerkelijk uit te voeren wat meer
ingewikkeld algoritme.
Maar voor vandaag, de trade-off is tijd en ruimte.
>> Dus als jullie gewoon kon houden je nummers, zodat we kunnen zien dat je bent
inderdaad bijpassende 4, 2, 6, 1, 3, 7, 8.
Excellent.
Dus ik ga proberen te orkestreren dingen, als jullie kunnen gewoon
Volg hier mijn lood.
>> Dus ik ga voeren, ten eerste, de eerste stap van de pseudocode, die
de input van n elementen, als n minder dan 2, dan terug.
Uiteraard, dat niet van toepassing zijn, zodat we verder.
Dus sorteren de linkerhelft van de elementen.
Dus dat betekent dat ik ga focussen mijn aandacht voor slechts een moment in de volgende
vier jongens hier.
Oke, wat moet ik nu doen?
>> PUBLIEK: Sorteer de linker helft.
>> DAVID Malan: Dus nu heb ik om te sorteren de linker helft van deze jongens.
Want nogmaals, neem je jezelf de doel is de linkerhelft sorteren.
Hoe doe je dat?
Volg gewoon de instructies, zelfs maar we doen het weer.
Zo sorteert de linker helft.
Nu ben ik sorteer deze twee jongens.
Wat komt er nu?
>> PUBLIEK: Sorteer de linker helft.
>> DAVID Malan: Sorteer de linker helft.
Dus nu deze, deze stoel hier, is een lijst van maat 1.
En hoe heet je ook alweer?
>> PRINCESS DAISY: Princess Daisy.
>> DAVID Malan: Princess Daisy is hier.
En dus is ze al naargelang, omdat de lijst is van grootte 1.
Wat moet ik nu doen?
OK, terug te keren, want die lijst is van size 1, die kleiner is dan 2.
Wat is dan de volgende stap?
En nu moet je soort van backtrack in je geest.
>> Sorteer de rechterhelft, die -
wat is je naam?
>> LINDA: Linda.
>> DAVID Malan: Linda.
En dus wat doen we nu, dat doen We hebben een lijst van maat 1?
>> PUBLIEK: Return.
>> DAVID Malan: Voorzichtig.
We keren terug eerste, en nu de derde stap - en als ik het soort uitbeelden deze door
het omarmen van de twee zetels nu, nu ik moeten deze twee elementen samen te voegen.
Dus nu helaas elementen zijn niet in orde.
Maar dat is waar de fuserende proces begint te dwingend te krijgen.
>> Dus als jullie omhoog kon staan ​​voor slechts een moment, ik ga je nodig hebt, in een
ogenblik, naar stap achter je stoel.
Als Linda, omdat 2 kleiner dan 4, waarom niet
je rond komt eerst?
Blijf daar.
Dus Linda, rond komt u eerst.
>> Nu in werkelijkheid is het maar een array we konden haar gewoon bewegen in real-time
van deze stoel naar deze plek.
Dus stel dat een aantal constante nam aantal stappen 1.
En nu -
maar we moeten u in de eerste plaats hier.
>> En nu als je rond kon komen, als goed, we gaan
in plaats twee.
En ook al voelt dit als het is het nemen van een tijdje, wat is er nu leuk is
dat de linkerhelft van de linkerhelft wordt nu gesorteerd.
Dus wat is de volgende stap, als we nu terugspoelen verder in het verhaal?
>> PUBLIEK: Rechter helft.
>> DAVID Malan: Sorteer de rechter helft.
Dus jullie moeten dit doen, als goed.
Dus als je zou kunnen opstaan voor slechts een moment?
En wat is je naam?
>> JESS: Jess.
>> DAVID Malan: Jess.
OK, dus Jess is nu de linker helft van de rechterhelft.
En dus ze is een lijst van maat 1.
Ze is blijkbaar opgelost.
En je naam ook alweer?
>> MICHELLE: Michelle.
>> DAVID Malan: Michelle is uiteraard Een lijst van grootte 1.
Ze is al naargelang.
Dus nu de magie gebeurt, het samenvoegen proces.
Dus wie gaat eerst komt?
Uiteraard Michelle.
Dus als je rond kon terugkomen.
De ruimte die we beschikbaar hebben voor haar nu ligt pal achter deze stoel hier.
En nu als je terug kon komen als goed, hebben we nu, om duidelijk te zijn, twee
helften, elk van grootte 2 -
en net omwille van uitbeelding's, als je kon een beetje een ruimte te maken -
de ene helft hier linksaf, een rechterhelft hier.
>> Rewind verder in het verhaal.
Welke stap is de volgende?
>> PUBLIEK: samenvoegen.
>> DAVID Malan: Dus nu moeten we fuseren.
Dus OK, dus nu, gelukkig, we net vrijgekomen vier stoelen.
Dus we hebben twee keer gebruikt zoveel geheugen, maar kunnen we flip-floppen geven tussen
de twee arrays.
Dus welk nummer is de eerste plaats komen?
Dus Michelle, uiteraard.
Dus kom rond en nemen uw stoel hier.
En dan nummer 2 is uiteraard volgende, zodat u hier komt.
Nummer 4, nummer 6.
En nogmaals, ook al is er een beetje wandelen betrokken,
echt, deze kan direct gebeuren, by moving -
OK, goed gespeeld.
>> [Lachen]
>> DAVID Malan: En nu zijn we in vrij goede vorm.
De linker helft van de gehele ingang is nu gesorteerd.
Oke, dus deze jongens had het voordeel van mijn -
hoe is het uiteindelijk alle meisjes op de links en alle jongens aan de rechterkant?
>> OK, dus jongens 'nu draaien.
Dus zal ik je niet lopen door deze stappen.
We zullen zien of we kunnen opnieuw hetzelfde pseudocode.
Als je vooruit wilt gaan en opstaan, en jullie, laat me je de microfoon.
Kijk of je niet kan repliceren wat We deden gewoon hier op de
andere einde van de lijst.
Wie heeft als eerste het woord, gebaseerd op het algoritme?
Dus uitleggen wat je doet voordat je maakt elke voetbewegingen.
>> LUIDSPREKER 1: Oke, dus sinds Ik ben de linkerhelft van de
linkerhelft, keer ik terug.
Rechts?
>> DAVID Malan: Good.
>> LUIDSPREKER 1: En dan -
>> DAVID Malan: Wie doet de microfoon naar de volgende?
>> LUIDSPREKER 1: Volgende nummer.
>> SPEAKER 2: Dus ik ben de rechter helft van de linkerhelft van de
linkerhelft, en ik terug.
>> DAVID Malan: Good.
U keert terug.
Dus nu wat is de volgende voor jullie twee?
>> SPEAKER 2: We willen zien wie er kleiner.
>> DAVID Malan: Precies.
Wij willen fuseren.
De ruimte die we gaan gebruiken om te fuseren u in, ook al zijn ze
uiteraard al naargelang, we gaan op hetzelfde algoritme te volgen.
Dus die gaat in de rug eerste?
Dus 3, en vervolgens 7.
En nu de microfoon gaat naar deze jongens, OK?
>> SPEAKER 3: Dus ik ben de rechter helft van de linkerhelft en mijn n kleiner is dan
1, dus ik ga gewoon door te geven -
>> DAVID Malan: Good.
>> SPEAKER 4: Ik ben de rechter helft van de rechterhelft van de rechter helft, en ik ben
Ook een persoon, dus ik ben gaan om terug te keren.
Dus nu we fuseren.
>> SPEAKER 3: Dus we gaan terug.
>> DAVID Malan: Dus jullie gaan in de rug.
Dus 5 gaat als eerste, daarna 8.
Nu doelgroep, de stappen we nu moeten terugspoelen
terug in onze geest?
>> PUBLIEK: samenvoegen.
>> DAVID Malan: samenvoegen linker helft en rechts de helft van de oorspronkelijke linkerhelft.
Dus nu -
en alleen maar om dit duidelijk te maken, maak een beetje ruimte
tussen jullie twee.
Dus nu is dat de twee lijsten, links en rechts.
Dus hoe kunnen we nu samen te voegen jullie in de voorste rij stoelen weer?
>> 3 gaat eerst.
Dan 5, uiteraard.
Dan 7, en nu 8.
OK, en nu zijn we?
>> PUBLIEK: Niet uitgevoerd.
>> DAVID Malan: Niet gedaan, omdat natuurlijk, er is een stap overgebleven.
Maar nogmaals, de reden dat ik met behulp van deze jargon als 'rewind in je geest, "
het is want dat is echt wat er gebeurt.
We gaan door al deze stappen, maar we zijn soort pauzeren voor een
Momenteel duiken dieper in de algoritme, pauzeren voor een moment,
duiken dieper in het algoritme, en nu hebben we te sorteren van terugspoelen in onze
geesten en ongedaan al deze lagen dat we soort van in de wacht gezet.
>> Dus nu hebben we twee lijsten van grootte 4.
Als jullie omhoog kon staan ​​een laatste keer en maak een beetje ruimte hier aan
duidelijk dat dit de linker helft van de oorspronkelijke, de
rechterhelft van het origineel.
Wie is het eerste nummer dat we moeten trekken in de rug?
Michelle, natuurlijk.
>> Dus hebben we Michelle hier.
En wie heeft nummer 2?
Nummer 2 komt op de rug ook.
Nummer 3?
Excellent.
Nummer 4, nummer 5, nummer 6, nummer 7, en nummer 8.
>> OK, dus het voelde als een stuk stappen, zeker.
Maar laten we nu eens kijken of we niet kunnen bevestigen soort intuïtief dat deze
algoritme fundamenteel, in het bijzonder als n wordt echt groot, zoals we hebben gezien
met de animaties, is fundamenteel sneller.
Dus ik beweer dit algoritme, in het slechtste case en zelfs in het beste geval,
is big O van n keer log n.
Dat is, er is een aspect van deze algoritme dat n stappen neemt, maar
er is een ander aspect ergens in dat iteratie, die looping, dat
neemt log n stappen.
Kunnen we onze vinger op wat die twee nummers verwijzen naar?
Nou, waar -
waar ging de microfoon te gaan?
>> LUIDSPREKER 1: Zou het log n zijn breken ons in twee -
delen door twee, in hoofdzaak.
>> DAVID Malan: Precies.
Elke keer zien we in elk algoritme dus ver, er is dit patroon van
verdelen, verdelen, verdelen.
En het is meestal beperkt naar iets dat
logaritmische, log basis 2.
Maar het kan echt van alles zijn, maar log base 2.
>> Nu wat over de n?
Ik kan zien dat we soort van verdeelde u jongens - verdeelde u, verdeeld u,
onderverdeeld u, verdeeld u.
Waar komt het einde vandaan?
>> Dus het is de samenvoeging.
Omdat er over nadenkt.
Als je acht mensen bij elkaar fuseren, waarbij de helft van hen zijn een reeks van vier
en de andere helft een andere set van vier, hoe ga je
over het doen van de fusie?
Nou, jullie deden het vrij intuïtief.
>> Maar als ik in plaats daarvan deed het een beetje meer methodisch, ik zou hebben gewezen op
de meest linkse persoon voor het eerst met mijn linker hand, gericht op de meest linkse persoon
van dat half met mijn rechterhand, en gewoon vervolgens liep door de
lijst, wijzend op het kleinste element elke keer, beweegt mijn vinger over en
dan zo nodig de hele lijst.
Maar wat is belangrijk over deze samenvoeging proces is Ik vergelijk deze paren
elementen.
Uit de rechterhelft en van links half, ben ik niet een keer backtracking.
>> Dus de merge zelf neemt niet meer dan n stappen.
En hoeveel keer had ik aan dat samenvoegen doen?
Nou ja, niet meer dan n, en we gewoon zag dat bij de uiteindelijke samenvoegen.
En dus als je iets dat neemt doen log n stappen n keer, of vice versa,
Het gaat ons n keer log n geven.
>> En waarom is dit beter?
Nou, als we al weten dat log n is beter dan n - toch?
We zagen in binary search, het telefoonboek Bijvoorbeeld, log n was zeker
beter dan lineair.
Dus dat betekent dat n keer log n is zeker beter dan n keer een andere
n, AKA n kwadraat.
En dat is wat we uiteindelijk voelen.
>> Zo groot applaus, indien we konden, voor deze jongens.
>> [Applaus]
>> DAVID Malan: En je afscheid geschenken - je kan houden van de nummers,
als je zou willen.
En je afscheidscadeau, zoals gewoonlijk.
Oh, en we sturen u de beelden, Michelle.
Dank u.
Oke.
Help jezelf aan een stressbal.
>> En laat mij trekken, in de tussentijd, onze vriend Rob Bowden te bieden
enigszins andere kijk op deze, omdat je kunt denken over deze
stappen gebeurt in een enigszins andere manier.
In feite is de set-up voor wat Rob gaat over om ons te tonen ervan uit dat we hebben
al gedaan de verdeling van de grote lijst in acht kleine lijsten,
elk van maat 1.
>> Dus we veranderen de pseudocode een beetje gewoon om een ​​soort van te krijgen op de
kern idee van hoe het samenvoegen werkt.
Maar de looptijd van wat hij is ongeveer te doen is nog
naar dezelfde te zijn.
En nogmaals, de set-up hier is dat hij begonnen met acht lijsten van grootte 1.
Dus je hebt het deel waar hij is gemist eigenlijk gedaan de log n, log n, log n
delen van het ingangssignaal.
>> [VIDEO AFSPELEN]
>> -Dat is het voor stap een.
Voor stap twee, herhaaldelijk samenvoegen paren van lijsten.
>> DAVID Malan: Hm.
Alleen audio komt eraan uit mijn computer.
Laten we proberen dit opnieuw.
>> -Just willekeurig kiezen welke - nu hebben we vier lijsten.
Leren voordat.
>> DAVID Malan: Daar gaan we.
>> -Samenvoegen 108 en 15, eindigen we met de lijst 15, 108.
Samenvoegen 50 en 4, we eindigen met 4, 50.
Samenvoegen van 8 en 42, we eindigen met 8, 42.
En samenvoegen 23 en 16, we eindigen met 16, 23.
>> Nu al onze lijsten zijn van grootte 2.
Merk op dat elk van de vier lijsten wordt gesorteerd.
Zodat we kunnen beginnen met het samenvoegen paren van lijsten weer.
Samenvoegen 15 en 108 en 4 en 50, we eerst neemt de 4, dan is het 15, dan
de 50, dan 108.
Samenvoegen van 8, 42 en 16, 23, nemen we eerst De 8, dan is de 16 dan de 23,
dan de 42.
>> Dus nu hebben we slechts twee lijsten van omvang 4, die elk gesorteerd.
Dus nu we samenvoegen van deze twee lijsten.
Eerst nemen we de 4, dan nemen we de 8, dan nemen we de 15, dan 16, dan
23, dan 42, dan 50, dan 108.
>> [END VIDEO AFSPELEN]
>> DAVID MALAN: Nogmaals, aankondiging, hij nooit raakte een gegeven cup meer dan een keer
na oprukkende daarbuiten.
Dus hij is nooit te herhalen.
Dus hij is altijd in beweging naar de zijkant, en dat is waar we onze n.
>> Waarom laat me omhoog te trekken een animatie dat we eerder zagen, maar deze keer
alleen gericht op merge sort.
Laat me ga je gang en zoomen op deze hier.
Laat me eerst kiezen voor een willekeurige ingang, vergroot deze, en u kunt sorteren van zien
wat we vanzelfsprekend vonden, eerder, merge sort is werkelijk te doen.
>> Dus merken dat je deze helften of deze wijken of deze achtste van de
probleem dat ineens beginnen om een ​​goede vorm te krijgen.
En dan tot slot, zie je bij het einde dat bam,
alles is samengevoegd.
>> Dus dit zijn slechts drie verschillende neemt hetzelfde idee.
Maar het belangrijkste inzicht, net als divide en veroveren in de eerste klasse,
was dat we besloten om een ​​of andere manier te verdelen het probleem in iets groots, in
iets soort identiek in de geest, maar kleiner en kleiner
en kleiner.
>> Nu nog een leuke manier om een ​​soort van denken over deze, ook al is het niet
ga je dezelfde intuïtieve begrip, is
de volgende animatie.
Dus dit is een video iemand in elkaar gezet die verschillende bijbehorende
geluiden met de verschillende activiteiten voor insertion sort, voor merge sort, en
voor een paar anderen.
Dus in een moment, ik ga Play raken.
Het is ongeveer een minuut lang.
En hoewel je nog steeds kunt zien de patronen gebeurt, dit keer kun je
ook horen hoe deze algoritmen zijn anders en met het uitvoeren van
enigszins verschillende patronen.
>> Dit is insertion sort.
>> [TONEN AFSPELEN]
>> DAVID Malan: Het weer is proberen aan elk element invoegen
naar waar het hoort.
Dit is bubble sort.
>> [TONEN AFSPELEN]
>> DAVID Malan: En u kunt sorteren van gevoel hoe relatief weinig werk het doet
op elke stap.
Dit is wat verveling klinkt.
>> [TONEN AFSPELEN]
>> DAVID Malan: Dit is selectie sorteren, waar we selecteert u het element willen we door
doorlopen en opnieuw en opnieuw en zetten het in het begin.
>> [TONEN AFSPELEN]
>> DAVID Malan: Dit is merge sort, die kan je echt beginnen te voelen.
>> [TONEN AFSPELEN]
>> [Lachen]
>> DAVID Malan: Iets genaamd gnome soort, die we niet hebben gekeken.
>> [TONEN AFSPELEN]
>> DAVID Malan: Dus laat me zien, nu, afgeleid zoals je hopelijk zijn door de
muziek, als ik een beetje kan glijden beetje wiskunde in hier.
Dus er is een vierde manier die we kunnen denken over wat het betekent deze
functies om sneller dan degenen zijn dat we al eerder gezien.
En als je komt in de loop van een wiskunde achtergrond, je
eigenlijk weet misschien al dat je kan een term klap op deze techniek -
namelijk recursie, een functie dat een of andere manier noemt zichzelf.
>> En nogmaals, herinneren dat merge sort pseudocode was recursieve in de zin
dat een van de stappen merge sort's was te sorteren noemen -
dat is, zelf.
Maar gelukkig, want we hielden bellen sorteren of samenvoegen sorteren,
specifiek, op een steeds kleinere en kleinere lijst, we uiteindelijk
dieptepunt dankzij wat wij zullen noemen een basisscenario, de hard-coded geval dat
zei dat als de lijst is klein, minder dan 2 in dat geval gewoon direct terug.
Als we niet hebben dat speciaal geval, de algoritme zou nooit bodem uit,
en je zou inderdaad krijgen in een oneindige lus echt voor altijd.
>> Maar stel dat we wilden nu zetten sommige nummers op dit, opnieuw, met behulp van n
de grootte van de ingang.
En ik wilde u vragen, wat is de totale tijd die betrokken zijn bij
lopende merge sort?
Of meer in het algemeen, wat is de kosten in tijd?
>> Nou het is vrij eenvoudig te meten dat.
Als n kleiner is dan 2, de tijd die in het sorteren van n elementen,
waarin n 2 is 0.
Omdat we gewoon terug.
Er is geen werk te doen.
Nu misschien wel, misschien is het een stap of twee stappen te achterhalen van de hoeveelheid
werken, maar het is dicht genoeg bij 0 dat Ik ga gewoon zeggen dat geen werk is
vereist als de lijst is zo klein worden oninteressant.
>> Maar dit geval is interessant.
Het recursieve geval was de tak van de pseudocode die anders al zei, sorteren
de linkerhelft, sorteren rechts helft, fuseren de twee helften.
Nu waarom doet deze uitdrukking vertegenwoordigen dat kosten?
Nou, T van n betekent alleen de tijd om n elementen te sorteren.
En dan aan de rechterzijde van de gelijk-teken daar, de T van n verdeeld
met 2 verwijst naar de kosten van wat?
Het sorteren van de linkerhelft.
De andere T n gedeeld door 2 is waarschijnlijk verwijst naar de kosten
sorteren van de rechterhelft.
>> En dan de plus n?
Wordt de samenvoeging.
Want als je twee lijsten, een van size n meer dan 2 en een ander van grootte n
meer dan 2, moet je wezen raken elk van deze elementen, net als Rob
aangeraakt elk van de cups, en gewoon zoals we reeds bij elk van de
vrijwilligers op het podium.
Dus n is ten koste van het samenvoegen.
>> Nu helaas, deze formule Ook zelf recursief.
Dus als de vraag, als n, zeg, 16, als er 16 mensen op het podium
of 16 bekers in de video, hoeveel totaal stappen duurt het om ze te sorteren
met merge sort?
Het is eigenlijk niet een duidelijk antwoord, want nu heb je om een ​​soort van
recursief antwoord op deze formule.
>> Maar dat is OK, want laat me voorstellen dat we het volgende doen.
De tijd die gemoeid is met 16 personen sorteren of 16 cups zal worden vertegenwoordigd
algemeen als T 16.
Maar dat gelijk, volgens onze previous formule 2 keer de hoeveelheid
van de tijd die het kost om te sorteren 8 kopjes plus 16.
En nogmaals, plus 16 is het tijd om te fuseren, en tweemaal T 8 is de
tijd om linkerhelft en rechterhelft te sorteren.
>> Maar nogmaals, dit is niet genoeg.
We hebben om te duiken in dieper.
Dit betekent dat we de antwoorden vraag, wat is T van 8?
Nou T van 8 ligt op slechts 2 tijden T van 4 plus 8.
Nou, wat is T van 4?
T van 4 is slechts 2 keer T van 2 plus 4.
Nou, wat is T van 2?
T van 2 is slechts 2 keer T van 1 plus 2.
>> En nogmaals, we zijn soort van krijgen vast in deze cyclus.
Maar het is over te raken dat zogenaamde basisscenario.
Want wat is T van 1, hebben we beweren?
0.
Dus nu eindelijk, kunnen we terug te werken.
>> Als T van 1 is 0, kan ik nu weer terug ga een lijn om deze man hier, en ik kan
plug in 0 voor T van 1.
Dus dat betekent dat gelijk is aan 2 maal nul, ook wel bekend als 0, plus 2.
En dus dat hele uitdrukking is 2.
>> Nu als ik de T van 2, waarvan het antwoord is 2, steek hem in de middelste lijn, T
van 4, dat geeft me 2 keer 2 plus 4, dus 8.
Als ik vervolgens de stekker in 8 op de vorige lijn, dat geeft me 2 keer 8, 16.
En als we dan verder dat met de 24, het toevoegen van 16, eindelijk krijgen we een
waarde van 64.
>> Nu dat op zich soort spreekt niets met de notatie n, de
big O, de omega dat we hebben het over.
Maar het blijkt dat 64 inderdaad 16, de sterkte van het ingangssignaal,
log basis 2 van 16.
En als dit een beetje bekend, maar denk terug, en het zal terugkomen
tot je uiteindelijk.
Als dit log base 2, het is net als 2 verhoogd tot het wat geeft je 16?
Oh, dat is 4, dus het is 16 keer 4.
>> En nogmaals, het is geen big deal als deze is een soort van wazige herinnering nu.
Maar voor nu, nemen op geloof dat 16 log 16 is 64.
En dus inderdaad, met deze eenvoudige gezond verstand controleren, hebben we bevestigd -
maar niet formeel bewezen -
dat de looptijd van de merge soort is inderdaad n log n.
>> Dus niet slecht.
Het is zeker beter dan de algoritmen die we tot nu toe gezien, en
het is omdat we leveraged, een, een techniek genaamd recursie.
Maar interessanter dan dat, dat notie van het verdelen en veroveren.
Nogmaals, echt week 0 spul dat zelfs nu is terugkerend in een
meer dwingende manier.
>> Nu een leuke kleine oefening, als je hebt nooit gedaan - en u waarschijnlijk
niet, omdat soort normale mensen denken niet om dit te doen.
Maar als ik naar google.com en als Ik wil iets leren over
recursie, Enter.
>> [Lachen]
[Meer gelach]
DAVID Malan: Slechte grap langzaam verspreiden.
[Lachen]
DAVID Malan: Just in case, het is er.
Ik heb niet spellen het verkeerd, en er is de grap.
Oke.
Uitleggen aan de mensen naast u als het is niet helemaal klikte gewoon nog niet.
Maar recursie, meer algemeen, verwijst het proces van een functie oproepen
zelf, of meer algemeen, splitsen van een probleem in iets dat kan worden
fragmentarisch opgelost door het oplossen van identieke vertegenwoordiger van problemen.
>> Nou, laten we verandering versnellingen voor slechts een moment.
We willen eindigen op bepaalde momenten van angst, dus laten we beginnen op te zetten
het podium, voor enkele minuten, op een zeer eenvoudig idee -
dat van ruilen twee elementen, toch?
Al deze algoritmes we geweest te praten over de afgelopen paar
lezingen omvatten een aantal soort swapping.
Vandaag werd gevisualiseerd door ze te verkrijgen op uit hun stoelen en
rond te lopen, maar in de code, zouden we neem dan gewoon een element van de ene array
en plop in een ander.
>> Dus hoe kunnen we dat doen?
Nou, laat me ga je gang en schrijf snel een programma hier.
Ik ga om te gaan en te doen dit als volgt.
Laten we noemen dit -
wat willen we met deze ene bellen?
>> Eigenlijk niet.
Laat me terug te spoelen.
Ik wil niet dat doen cliffhanger nog.
Het zal de pret niet drukken.
Laten we dit doen in plaats daarvan.
>> Stel dat ik wil een beetje schrijven programma en die omarmt nu dit
idee van recursie.
Ik soort heb er voor mezelf.
Ik ga het volgende doen.
>> Ten eerste, een snelle bevatten standaard io.H, alsmede een include van cs50.h.
En dan ga ik om verder te gaan en verklaren int main nietig
op de gebruikelijke wijze.
Ik besefte dat ik heb het bestand verkeerde naam, dus laat ik voeg gewoon een. c extensie hier dus
dat we het goed kunnen compileren.
Start deze functie uit.
>> En de functie ik wil schrijven, heel gewoon, is er een die vraagt ​​de
gebruiker voor een nummer en vervolgens opgeteld alle nummers tussen die
nummer en, zeg, 0.
Dus eerst ga ik verder te gaan en verklaren int n.
Kopieer dan heb ik wat code die we hebben gebruikt voor een tijdje.
Terwijl er iets is waar.
Ik kom terug naar die komen in een moment.
>> Wat wil ik doen?
Ik wil printf positiefs te zeggen integer alsjeblieft.
En dan ga ik Zeg n krijgt krijgen int.
Dus nogmaals, sommige standaardtekst code dat we eerder hebben gebruikt.
En ik ga dit doen terwijl n kleiner is dan 1.
Dus dit zal ervoor zorgen dat de gebruiker geeft mij een positief geheel getal.
>> En nu ga ik het volgende doen.
Ik wil optellen alle nummers 1 tot en n of 0 en n,
equivalent, met het totaal bedrag te krijgen.
Dus de grote sigma symbool dat je zou herinneren.
Dus ik ga dit doen door eerst te bellen een functie genaamd sigma,
het passeren van het in n, en dan ga ik zeggen printf, het antwoord is daar.
>> Dus in het kort, krijg ik en int van de gebruiker.
Ik zorg ervoor dat het positieve.
Ik verklaar een variabele genaamd antwoord van type int en op te slaan in het het rendement
waarde van sigma, passeren in n als invoer.
En dan print ik dat antwoord.
>> Helaas, alhoewel sigma klinkt als iets dat zou kunnen zijn in
het math.h bestand, zijn verklaring, het is eigenlijk niet.
Dus dat is OK.
Ik kan dit zelf uitvoeren.
Ik ga een functie genaamd implementeren sigma, en het gaat om een ​​te nemen
parameter -
laten we noemen het m, net dus het is anders.
En dan hier, ik ga zeggen, goed, indien m kleiner dan 1 - Dit is een
zeer oninteressant programma.
Dus ik ga om verder te gaan en onmiddellijk 0 terug.
Het heeft gewoon geen zin om optellen maken allemaal de getallen tussen 1 en m als m
is zelf 0 of negatief is.
>> En dan ga ik om verder te gaan en dit doet zeer iteratief.
Ik ga dit soort old-school te doen, en ik ga om verder te gaan
en zeggen dat ik ga verklaren een bedrag te zijn 0.
Dan ga ik hebben een lus van int -
en laat mij het doen om onze wedstrijd verdeelsleutel, dus je hebt een kopie
thuis. int i krijgt 1 op maximaal i kleiner is dan of gelijk aan m.
i plus plus.
En dan de binnenkant van deze for loop -
we zijn er bijna -
sum krijgt sum plus 1.
En dan ga ik aan de som terug te keren.
>> Dus ik deed dit snel, heel toegegeven.
Maar nogmaals, de belangrijkste functie is vrij ongecompliceerd, gebaseerd op code die we hebben
tot nu toe geschreven.
Maakt gebruik van de dubbele lus om een ​​positieve krijgen int van de gebruiker.
Toen ik pas dat int naar een nieuwe functie genaamd sigma, noemde het, nogmaals, n.
En ik bewaar de return waarde, het antwoord uit de zwarte doos momenteel
bekend als sigma, in een variabele riep antwoord.
Dan print ik het.
>> Als we nu verder het verhaal, hoe wordt sigma geïmplementeerd?
Ik stel voor om te implementeren als volgt.
Eerst een beetje foutcontrole om ervoor te zorgen dat de gebruiker niet
knoeien met mij en passeren in aantal negatieve of 0 waarde.
Dan verklaar ik een variabele genaamd samenvatten en zet deze op 0.
>> En nu begin ik te verhuizen van i gelijk 1 helemaal tot en met m,
want ik wil alle bevatten getallen van een tot en met m, inclusief.
En binnenkant van deze for loop, ik doe sum krijgt wat het nu is, plus de
waarde van i.
Plus de waarde van i.
>> Even terzijde, als je dit niet hebt gezien eerder, is er een aantal syntactische suiker
voor deze lijn.
Ik kan dit herschrijven als plus evenaart i, alleen maar om mezelf te redden een paar toetsaanslagen
en kijken een beetje koeler.
Maar dat is alles.
Het is functioneel hetzelfde.
>> Helaas is deze code's niet van plan nog te compileren.
Als ik te maken sigma 0, hoe ben Ik ga krijgen schreeuwde?
Wat gaat het niet vinden?
>> PUBLIEK: [onverstaanbaar].
>> DAVID MALAN: Ja, heb ik niet verklaren de functie tot boven, toch?
C is een beetje dom, omdat het alleen doet wat je vertellen dat het te doen, en je
moeten het doen in die volgorde.
En dus als ik druk op Enter hier, ik ga krijg een waarschuwing over sigma impliciete
verklaring.
>> Oh, geen probleem.
Ik kan gaan tot de top, en ik kan zeggen, oke, wacht even.
Sigma is een functie die terugkeert een int en verwacht een
int als input, puntkomma.
Of ik kon de hele functie gezet boven de belangrijkste, maar in het algemeen, zou ik
afraden dat, want het is leuk om altijd de belangrijkste aan de top dus
kunt u rechts in duiken en weten wat een programma doet bij eerste lezing belangrijkste.
>> Dus nu laat ik het scherm te wissen.
Remake sigma 0.
Alles lijkt uit te checken.
Laat me sigma 0 draaien.
Positieve inter.
Ik geef het aantal 3 om het simpel te houden.
Zodat ik moet geven 3 plus 2 plus 1, dus 6.
Enter, en inderdaad krijg ik 6.
>> Ik kan iets groters doen -
50, 12, 75.
Net als een tangent, ga ik doen iets belachelijks als een echt grote
nummer, Oh, dat werkte eigenlijk -
eh, ik denk niet dat dat klopt.
Laten we eens kijken.
Laten we echt knoeien met het.
>> Dat is een probleem.
Wat is er gaande?
De code is niet zo slecht.
Het is nog steeds lineair.
Fluiten is een goed effect, dat wel.
Wat is er gaande?
>> Niet zeker of ik het hoorde.
Dus het blijkt - en Dit is als een terzijde.
Dit is niet de kern van de idee van recursie.
Het blijkt, want ik ben op zoek naar vertegenwoordigen zo'n groot aantal, meest
waarschijnlijk het wordt verkeerd geïnterpreteerd door C als niet positief getal,
maar negatief getal.
>> We hebben nog niet gesproken over deze, maar het blijkt dat er negatieve getallen
in de wereld naast positieve getallen.
En de wijze waarop u kunt vertegenwoordigen een negatief getal
in wezen een is, gebruikt u speciale bit om aan te geven
positieve dan negatieve.
Het is een beetje ingewikkelder dan dat, maar dat is het basisidee.
>> Dus helaas, als C is verwarrend ene van die stukjes als werkelijk betekenis,
oh, dit is een negatief getal, mijn lus Hier, bijvoorbeeld, eigenlijk nooit
gaat beëindigen.
Dus als ik daadwerkelijk iets af te drukken opnieuw en opnieuw, we zouden
zie een heleboel.
Maar nogmaals, dit is naast het punt.
Dit is eigenlijk gewoon een soort van intellectuele nieuwsgierigheid dat we komen
uiteindelijk terug.
Maar voor nu, dit is een correcte implementatie als we aannemen dat de
gebruiker zal ints bieden die passen binnen ints.
>> Maar ik beweren dat deze code, eerlijk gezegd, kon zo veel meer eenvoudig worden gedaan.
Als het doel bij de hand is om een ​​aantal te nemen zoals m en tel al van de
getallen tussen het en 1, of omgekeerd tussen 1 en het, beweren I
dat ik dit idee dat fuseren kunt lenen sort had, dat was het nemen van een probleem
van deze omvang en verdelen in iets kleinere.
Misschien niet de helft, maar kleiner, maar representatieve hetzelfde.
Hetzelfde idee, maar een kleiner probleem.
>> Dus ik ben eigenlijk - laat ik dit bestand op te slaan met een ander versienummer.
We zullen deze versie noemen 1 in plaats van 0.
En ik beweer dat ik kan eigenlijk herimplementeren deze in dit soort
breinbrekende weg.
>> Ik ga alleen een deel van het te verlaten.
Ik ga zeggen als m minder dan of gelijk aan 0 -
Ik ga gewoon een beetje te zijn meer anale deze tijd
met mijn foutcontrole -
Ik ga om te gaan en terug te keren 0.
Dit is willekeurig.
Ik ben gewoon de beslissing of de gebruiker geeft me een negatief getal, ik ben
terug 0, en ze moeten hebben gelezen de documentatie nauwer.
>> Else -
merken wat ik ga doen.
Anders ga ik terug m plus -
wat sigma van m?
Nou, sigma van m plus m minus 1, plus minus m 2, plus m minus 3.
Ik wil niet dat alles uit te schrijven.
Waarom doe ik niet gewoon punter?
Recursief noem mezelf met een iets kleiner probleem, puntkomma,
en noemen het een dag?
>> Rechts?
Nu ook hier, je zou voelen of zorgen dat dit een oneindige lus, dat ben ik
inducerende, waarbij ik ben de uitvoering sigma door te bellen naar sigma.
Maar dat is perfect OK, want ik dacht vooruit een toegevoegde welke lijnen?
>> PUBLIEK: [onverstaanbaar].
>> DAVID Malan: 23 tot 26, die is mijn als voorwaarde.
Want wat er leuk is aan de aftrekken hier, want ik houd
overdracht sigma kleinere problemen, kleiner problemen, kleinere - het is niet
half zo groot.
Het is slechts een baby stap kleiner, maar dat is OK.
Want uiteindelijk zullen we werken onze weg naar 1 of 0.
En als we eenmaal geraakt 0, sigma is niet gaat zich meer noemen.
Het gaat om direct 0 keren.
>> Dus het effect, als je soort van wind deze in je geest, is het m plus voegen
m minus 1, plus m minus 2, plus m minus 3, plus puntje, puntje, puntje, m minus
m, uiteindelijk geef je 0, en de effect uiteindelijk alle voegen
deze dingen samen.
We hebben dus niet, met recursie, het probleem opgelost dat we
kon niet op te lossen voordat.
Inderdaad, deze versie 0 en elke probleem tot op heden, is oplosbaar geweest
met alleen het gebruik van loops of tijdens lussen of soortgelijke constructen.
>> Maar recursie, ik durf te zeggen, geeft ons een andere manier van denken over
problemen, waarbij als we kunnen nemen een probleem, het verdelen van iets
enigszins groot in iets wat kleiner, ik beweer dat we het kunnen oplossen
misschien een beetje meer elegant in termen van het ontwerp, met minder code,
en misschien zelfs oplossen van problemen die zouden moeilijker, want we zullen uiteindelijk
zie, het oplossen van louter iteratief.
>> Maar de cliffhanger die ik deed wil ons verlaten op was dit.
Laat me ga je gang en open een bestand van -
eigenlijk, laat me gaan en doe dit echt snel.
Laat ik verder gaan en stellen de volgende.
Onder de code van vandaag is hier dit bestand.
Deze hier, noswap.
>> Dus dit is een stomme kleine programma dat Ik opgezweept die aanspraken te doen
de volgende.
In de belangrijkste, voor het eerst verklaart een int genaamd x en wijst deze
de waarde 1.
Dan verklaart het een int y en wijst deze de waarde 2.
Dan print het uit wat x en y.
Dan zegt hij, ruilen, dot dot dot.
>> Dan het beweert een functie te bellen riep swap, passeren in x en
y, het idee heeft dat hopelijk x en y zal terugkomen
anders, het tegenovergestelde.
Dan het te claimen geruild!
met een uitroepteken.
Dan print het uit x en y.
>> Maar het blijkt dat deze zeer eenvoudige demonstratie neer
hier eigenlijk buggy.
Hoewel ik ben waarbij een tijdelijke variabel en tijdelijk zetten een in
het, dan ben ik opnieuw toewijzen een waarde van m. -
die redelijk voelt, want ik heb opgeslagen een kopie van een in temp.
Toen ik b updaten om gelijke wat was in temp.
Dit soort shell game van het verplaatsen van een in b en b in een met behulp van deze
middle-man genaamd temp voelt heel redelijk.
>> Maar ik beweer dat wanneer ik dit run code, zoals ik nu doe -
laat me ga je gang en plak het in hier.
Ik zal dit noswap.c noemen.
En zoals de naam al doet vermoeden, is dit niet gaan een correcte programma.
Maak noswap. / Geen swap.
x is 1, y 2, ruilen, verwisseld.
x is 1, y is 2.
Dit is uit den boze, zelfs al lijkt dit volkomen
mij redelijk.
En er is een reden, maar we zijn niet gaan naar de reden te onthullen gewoon nog niet.
>> Voor nu de tweede cliffhanger ik wilde om u te verlaten met is dit, een
aankondiging van soorten op coupon codes.
Onze innovatie met late dagen van dit jaar heeft een niet-triviale nummer uitgelokt
van vragen, die was niet onze bedoeling.
De bedoeling van deze coupon codes, waarbij als je een deel van het probleem
set vroeg, waardoor het krijgen van een extra dag, was echt te helpen jullie helpen
je vroeg beginnen, sorteren van door incentivizing u.
Helpt ons verdelen lading over kantooruren beter, zodat
het is een soort van win-win.
>> Helaas, ik denk dat mijn instructies niet zijn, tot op heden, heel duidelijk, dus
Ik ging terug dit weekend en geactualiseerd de spec in grotere, krachtiger tekst
verklaren kogels als deze.
En alleen maar om het meer publiekelijk zeggen door Standaard probleem sets zijn te wijten donderdag
op de middag, per de syllabus.
Als je vroeg beginnen, afwerking deel van de door woensdag vastgesteld op 0:00 probleem
PM, het deel dat betrekking heeft op een coupon code, het idee is dat je kunt uitbreiden
uw deadline voor de P stellen tot vrijdag.
Dat is, beetje uit een klein deel van de P ingesteld ten opzichte van wat typisch is de
groter probleem, en je koopt zelf een extra dag.
Nogmaals, het krijgt u na te denken over het probleem set, krijgt u
kantoor uren eerder.
Maar de coupon code probleem is nog steeds vereist, zelfs als je het niet indienen.
>> Maar meer dwingend is dit.
(STAGE WHISPER) En die mensen verlaten vroeg zijn gonna spijt.
Net als de mensen op het balkon.
Ik verontschuldig me bij voorbaat aan de mensen op het balkon om redenen die zullen worden
duidelijk in slechts een moment.
>> Dus we hebben het geluk om een ​​van zijn Voormalig hoofd teaching fellows CS50's bij
een bedrijf genaamd dropbox.com.
Ze zijn zeer gul gedoneerd een couponcode hier voor dit veel ruimte,
dat is een stijging van de gebruikelijke 2 gigabyte.
Dus wat ik dacht dat we zouden doen op deze laatste opmerking is wel een beetje een weggevertje,
waarbij in slechts een moment, zullen we onthullen de winnaar en die heeft een coupon
code die u vervolgens kunt gaan naar hun website, typt u het in, en voila, krijgen een
veel meer Dropbox ruimte voor uw toestel en voor uw persoonlijke bestanden.
>> En de eerste, die willen deelnemen in deze tekening?
OK, nu dat maakt het nog leuker.
De persoon die deze 25-gigabyte ontvangt coupon code - die ver
dwingender dan de late dagen nu, misschien -
is degene die zit op een zitkussen waar doorheen er
die coupon code.
U kunt nu kijken eronder uw zitkussen.
>> [VIDEO AFSPELEN]
>> -Een, twee, drie.
>> [SCREAMING]
>> -Je krijgt een auto!
Je krijgt een auto!
>> DAVID Malan: We zullen zien u op woensdag.
>> -Je krijgt een auto!
Je krijgt een auto!
>> DAVID Malan: Balkon mensen, kom hier beneden aan de voorzijde,
waar we extra's.
>> -Iedereen krijgt een auto!
Iedereen krijgt een auto!
>> [END VIDEO AFSPELEN]
>> NARRATOR: Bij de volgende CS50 -
>> SPEAKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh -
>> [UKELELE PLAYS]