>> [Musik Spela]
DAVID MALAN: Okej.
Okej, välkommen tillbaka.
Så detta är Vecka 4, inledningen detta, redan.
Och du kommer ihåg att förra veckan, satte vi koda åt sidan för bara en liten bit
och vi började prata lite mer hög nivå, om saker som
sökning och sortering, som dock något enkla idéer, är
representant för en klass av problem du kommer att börja lösa särskilt
när du börjar tänka på final projekt och intressanta lösningar du
kanske måste verkliga problem.
Nu bubbla sortera var en av de enklaste dessa algoritmer, och det
arbetat med att ha dessa små siffror i en lista eller i en matris typ av
bubbla sig upp till toppen, och stora siffrorna flyttar sig ner till
I slutet av denna lista.
>> Och minns att vi kunde visualisera bubbla sortera lite
ungefär så här.
Så låt mig gå vidare och klicka på Start.
Jag har förvalt bubbla sortera.
Och om ni minns att den högre blå linjerna representerar stora siffror, små
blå linjerna representerar små siffror, som Vi går igenom det här igen och igen och
igen, jämföra två barer bredvid varje andra i rött, vi kommer att byta
största och den minsta om de är i ordning.
>> Så det här kommer att gå på och gå på och gå på, och du kommer att se att större
element gör sig till höger, och de mindre delarna är
på väg till vänster.
Men vi började att kvantifiera effektiviteten, den
kvaliteten på denna algoritm.
Och vi sa att i värsta fall, tog denna algoritm
ungefär hur många steg?
>> Så n kvadrat.
Och vad var n?
>> Publik: Antal element.
>> DAVID MALAN: So n var antal element.
Och så ska vi göra det ofta.
Varje gång vi vill tala om storleken av ett problem eller storleken på ett
ingång, eller hur lång tid det tar producera utskrifter, vi ska bara
generaliserad oavsett ingången är såsom n.
Så tillbaka i vecka 0, antalet sidor i telefonboken var n..
Antalet studenter i rummet var n.
Så även här, vi följer det mönstret.
>> Nu n kvadrat är inte särskilt snabbt, så vi har försökt att göra bättre.
Och så tittade vi på ett par andra algoritmer, bland vilka
var val sort.
Så val sortera var lite annorlunda.
Det var nästan enklare, jag vågar säga, där jag började i början av
Listan över våra volontärer och jag bara igen och igen och igen gick igenom
listan, plockning ut den minsta element i taget och sätta honom eller
henne i början av listan.
>> Men även detta, när vi började fundera genom matte och större
bild, tänkte på hur många gånger Jag gick fram och tillbaka och tillbaka
och tillbaka, sa vi i värsta fall, selection sort, också var vad?
n kvadrat.
Nu i den verkliga världen, kanske det faktiskt vara marginellt snabbare.
Eftersom igen, det gjorde jag inte hålla backa när jag hade sorterat
minsta beståndsdel.
Men om vi tänker mycket stort N, och om du sorts göra ut matten som
Jag gjorde i styrelsen, med n kvadrat minus någonting, allt annat
förutom n kvadrat, när n blir riktigt stor, inte
verkligen betyder så mycket.
Så som datavetare, sorterar vi om blundar för de mindre
faktorer och bara fokusera på de faktorer i ett uttryck som kommer att göra
den största skillnaden.
>> Nåväl, slutligen, såg vi vid insättning sort.
Och det var i samma anda, men snarare än att gå igenom iterativt och
välja det minsta elementet en i tid, tog jag istället handen som jag
behandlades, och jag bestämde mig, alla rätt, hör du här.
Sedan jag flyttade till nästa element och bestämde att han eller
hon tillhörde här.
Och sedan jag flyttade och på.
Och jag fick till, längs vägen, skifta dessa killar för att
göra plats för dem.
Så det var typ av mentala omsvängning av urvalet sortera som vi
kallas insättning sort.
>> Så dessa ämnen att uppstå i den verkliga världen.
För bara några år sedan, när en viss senator kördes för president,
Eric Schmidt, vid den tidpunkt då VD Google, faktiskt haft möjlighet
att intervjua honom.
Och vi trodde vi skulle dela denna YouTube klipp för dig här, om vi kunde vända upp
volymen.
>> [VIDEO SPELA]
>> -Nu, senator, du är här på Google, och jag gillar att tänka på ordförandeskapet
som en anställningsintervju.
>> [SKRATT]
>> -Nu är det svårt att få ett jobb som president.
Och du går igenom stelhet nu.
Det är också svårt att få ett jobb på Google.
Vi har frågor och vi ber Våra kandidater frågor.
Och den här är från Larry Schwimmer.
>> [SKRATT]
-Ni tror jag skojar?
Det är just här.
Vad är det mest effektiva sättet att sortera en miljon två-bitars heltal?
>> [SKRATT]
>> -Jo, uh -
>> -Jag är ledsen.
Kanske vi borde -
>> -Nej, nej, nej, nej, nej.
>> -Det är inte en -
OK.
>> -Jag tror att bubblan sort skulle vara fel väg att gå.
>> [SKRATT]
>> [Jublar och applåder]
>> -Kom igen, som berättade det här?
OK.
>> [END VIDEOAVSPELNING]
>> DAVID MALAN: Så där har ni det.
Så vi började att kvantifiera dessa körs gånger, så att säga, med något
kallas asymptotisk notation, vilket är bara hänvisa till vår typ av svarvning
blunda för dessa mindre faktorer och bara titta på gångtid,
utförandet av dessa algoritmer, som n blir riktigt stort över tiden.
Och så vi introducerade big O. Och big O representerade något som vi trodde
av som en övre gräns.
Och faktiskt, Barry, kan vi sänka än mic lite?
>> Vi trodde att detta är en övre gräns.
Så stort O i n kvadrat innebär att i värsta fall, något som
selection sort skulle ta n kvadrat steg.
Eller något liknande insättning sortera skulle n kvadrat steg.
Nu till något liknande insättning Sortera, vad var det värsta?
Givet en matris, är vad det värsta möjligt scenario som du kanske hitta
dig inför?
>> Det är helt bakåt, höger?
För om det är helt bakåt, du måste göra en hel del arbete.
För om du är helt bakåt, du kommer att hitta den
största delen här, även om det hör hemma där nere.
Så du kommer att säga, okej, vid denna tidpunkt, hör du här,
så du lämnar den ensam.
>> Då inser du, åh, fan, jag måste flytta denna något mindre inslag
vänster om dig.
Då måste jag göra det igen och igen och igen.
Och om jag gick fram och tillbaka, du skulle sorts känsla prestanda
denna algoritm, eftersom tiden är jag blanda alla andra nere i
array för att göra plats för den.
Så det är det värsta fallet.
>> Däremot -
och detta var en cliffhanger förra gången -
Vi sade att införandet sort var en omega av vad?
Vad är det bästa tänkbara löpning insättandet sort?
Så det är faktiskt n.
Det var tomt som vi lämnade på tavlan förra gången.
>> Och det är omega n eftersom varför?
Tja, i allra bästa fall, vad är insättning sort ska lämnas?
Tja, en lista som är helt sorteras redan, minimalt arbete att göra.
Men vad är snyggt om införande sort är att eftersom det börjar här och
beslutar, åh, är du numret en, hör du här.
Åh, vilken lycka.
>> Du är nummer två.
Du hör även hit.
Nummer tre, ännu bättre, du hör hemma här.
Så snart det blir till slut lista, per insättning sortera s pseudokod
att vi gick igenom muntligt förra gången, är det gjort.
Men urvalet sortera, däremot, hålls gör vad?
>> Hålls gå igenom listan igen och igen och igen.
Eftersom den viktigaste insikten fanns bara När du har tittat hela vägen till
slutet av listan kan du vara säker att elementet du valde var
verkligen för närvarande minsta elementet.
Så dessa olika mentala modeller slut upp ger några mycket verkliga
skillnader för oss, liksom dessa teoretiska asymptotiska skillnader.
>> Så bara för att sammanfatta, då, big O n kvadrat, har vi sett några sådana
algoritmer hittills.
Big O n?
Vad är en algoritm som kunde sägas vara stort O n?
I värsta fall, tar det en linjär antal steg.
>> OK, linjär sökning.
Och i värsta fall, där är element som du letar efter när
tillämpa linjär sökning?
>> OK, i värsta fall, det är inte ens där.
Eller i den näst värsta fall är det hela vägen i slutet, vilket är
plus-eller-minus en en-stegs skillnad.
Så i slutet av dagen, Vi kan säga att det är linjärt.
Big O n skulle vara linjär sökning, eftersom det i det värsta fallet, den
elementet är inte ens där eller det är hela vägen i slutet.
>> Tja, stort O i log n.
Vi pratade inte i detalj om detta, men vi har sett det här förut.
Vad körs i så kallad logaritmisk tid, i värsta fall?
>> Ja, så binär sökning.
Och binär sökning i värsta fall kan ha elementet någonstans i
mitten, eller någonstans inuti arrayen.
Men du bara hitta det när du dela upp listan på mitten, i
hälften, på mitten, på mitten.
Och sedan voila, det är där.
Eller igen, värsta fall, det är inte ens där.
Men du vet inte att det inte finns tills du sorts nå det sista
nedersta elementen genom att halvera och halvera och halvera.
>> Big O 1.
Så vi kunde stora O 2, big O 3.
När som helst du vill ha bara ett konstant antal, sorterar vi bara om just förenkla
att så stor O 1.
Även om om realistiskt, tar det 2 eller till och med 100 steg, om det är en
konstant antal steg, vi säger bara Big O 1.
Vad är en algoritm som är i stort O i 1?
>> Publik: Hitta längden av en variabel.
>> DAVID MALAN: Hitta längden av en variabel?
>> Publiken: Nej, längden om den redan är sorterade.
>> DAVID MALAN: Bra.
OK, så att hitta längden på något om längden av att något, som
en array, är lagrad i någon variabel.
Eftersom du kan bara läsa variabeln, eller skriva ut variabeln, eller
bara allmänt komma åt den variabeln.
Och voila, som tar konstant tid.
>> Däremot tänker tillbaka till noll.
Tänk tillbaka till den första veckan i C, ringer bara printf och skriva
något på skärmen är utan tvekan konstant tid, eftersom det tar bara
några antal CPU-cykler för att visa att text på skärmen.
Eller vänta - gör det?
Hur annars kan vi modellera prestanda för printf?
Skulle någon vilja att vara oense, att kanske är det inte riktigt konstant tid?
I vilken mening kan printf körs tid, faktiskt skriver ut en sträng på
skärmen, vara något annat än konstant.
>> Publik: [OHÖRBAR].
>> DAVID MALAN: Yeah.
Så det beror på vårt perspektiv.
Om vi ​​tänker faktiskt hos insignalen till printf som den sträng, och
Därför mäter vi storleken på det ingång genom sin längd - så låt oss kalla
att längden n samt -
utan tvekan, printf är själv stor O n eftersom det kommer att ta dig n steg
att skriva ut varje av dessa n tecken, mest sannolikt.
Åtminstone i den utsträckning som vi antar som kanske är det med hjälp av en for-loop
under huven.
>> Men vi skulle behöva titta på det Kod för att förstå det bättre.
Och faktiskt, när ni börjar analysera dina egna algoritmer, kommer du
bokstavligen göra just det.
Sortera på ögongloben din kod och tror om - okej, jag har denna slinga
här eller jag har en nästlade loopar här, som kommer att göra n saker N gånger,
och du kan sortera förnuftets väg igenom koden, även om det är
pseudokod och inte faktiska koden.
>> Så vad om omega n kvadrat?
Vad var en algoritm som i bästa fall fortfarande tog n kvadrat steg?
Yeah?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: So urval sort.
På grund av att problemet verkligen reduceras det faktum att igen, jag vet inte
Jag har hittat den nuvarande minsta tills Jag har kollat ​​alla jäkla element.
Så omega av, säg, N, vi bara kom upp med en.
Insertion sort.
Om listan råkar vara sorteras redan, i bästa fall har vi bara
för att göra en passage genom den, då vi är säkra.
Och sedan som kan sägas vara linjär, for sure.
>> Hur är omega av 1?
Vad, i bästa fall, kan ta ett konstant antal steg?
Så linjär sökning, om du får bara tur och elementet du söker
är precis i början av listan, om det är där du börjar ditt
linjär förflyttning av den listan.
>> Och detta är sant för en antal saker.
Till exempel, även binära sökning är omega av 1.
För vad om du får riktigt jäkla tur och smack-dab i mitten av
din array är antalet du letar efter?
Så du kan ha tur där, liksom.
>> Denna en slutligen omega av n log n.
Så n log n, det gjorde vi inte riktigt prata om ännu, men -
>> Publik: Merge sort?
>> DAVID MALAN: Merge sort.
Det var cliffhanger förra gången, där vi föreslog, och vi visade
visuellt, att det finns algoritmer.
Och slå samman liksom bara en sådan algoritm som är fundamentalt snabbare
än vissa av dessa andra killar.
I själva verket, slå ihop kort är inte bara i bästa fall n log, i värsta
För n n log.
Och när du har detta sammanträffande av omega och stora O är samma sak?
Vi kan faktiskt beskriva det som det är kallas theta, även om det är en
lite mindre vanligt.
Men det betyder bara de två gränserna, i detta fall är desamma.
>> Så sammanfoga sort, vad har detta verkligen koka ner till för oss?
Tja, minns motivationen.
Låt mig dra upp en annan animation som vi inte titta på förra gången.
Detta en, samma idé, men det är lite större.
Och jag ska gå vidare och påpeka först - vi har insättning Sortera på
längst upp till vänster, och sedan välja sortera, Bubble sort, ett par andra typer -
skal och snabb - att vi inte har pratat om, och heap och sammanfoga sort.
>> Så åtminstone försöka att fokusera ögonen på den översta tre till vänster och sedan
sammanfoga sort när jag klickar denna gröna pilen.
Men jag ska låta dem alla springa, bara för att ger dig en känsla av mångfalden av
algoritmer som finns i världen.
Jag kommer att låta denna körning för bara några sekunder.
Och om du fokuserar dina ögon - välj ett algoritm, fokusera på det för bara ett
sekunder - du kommer att börja se mönster som det är att genomföra.
>> Merge sort, varsel, görs.
Heap sort, snabbt sortera, shell -
så det verkar vi introducerade tre värsta algoritmer förra veckan.
Men det är bra att vi är här i dag för att titta på merge sortera, är där en av
de lättare dem är att titta på, även även om det förmodligen kommer att böja din hjärna
bara lite.
Här kan vi se precis hur mycket val Sortera suger.
>> Men på baksidan, det är verkligen lätt att genomföra.
Och kanske för P Set 3, det är en av de algoritmer du valde att genomföra
för standardversionen.
Perfekt fina, helt korrekt.
>> Men återigen, som n blir stor, om du välja att genomföra en snabbare algoritm
gillar samman sortera, oddsen är större och större insatser, är din kod bara
kommer att köra fortare.
Din webbplats kommer att fungera bättre.
Dina användare kommer att bli lyckligare.
Och så finns dessa effekter att faktiskt ge
oss lite djupare tanke.
>> Så låt oss ta en titt på vad som går samman Sortera egentligen handlar om.
Det häftiga är att slå ihop Sortera är just detta.
Detta är, återigen, vad vi har kallat pseudokod, pseudokod varelse
Engelsk-liknande syntax.
Och enkelheten är slags fascinerande.
>> Så på inmatning av n element - så att betyder bara, här är en array.
Det har fått n saker i det.
Det är allt vi säger det.
>> Om n är mindre än 2, tillbaka.
Så det är bara det triviala fallet.
Om n är mindre än 2, då är det uppenbart att det är 1 eller 0, i vilket fall sak
är redan sorterade eller obefintlig, så bara tillbaka.
Det finns inget att göra.
Så det är ett enkelt fall att plocka bort.
>> Else, har vi tre steg.
Sortera vänstra halvan av elementen, sortera den högra halvan av elementen,
och sedan slå ihop de sorterade halvorna.
Vad är intressant här är att Jag är typ av punting, rätt?
Det är lite av en cirkulär definition denna algoritm.
I vilken mening är denna algoritm är definition cirkulär?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: Yeah, my sorteringsalgoritm, två av dess steg är "sort
något. "Och så väcker fråga, ja, vad ska jag använda
att sortera den vänstra halvan och den högra halvan?
Och skönheten här är att även om igen, detta är den kluriga
del potentiellt, kan du använda samma algoritm för att sortera den vänstra halvan.
>> Men vänta en minut.
När du berättade att sortera vänstra halvan, vilka är de två
steg kommer att bli nästa?
Vi reder den vänstra halvan av vänstra halvan och den högra
hälften av den vänstra halvan.
Fan, hur jag sorterar dessa två halvor eller fjärdedelar, nu?
>> Men det är OK.
Vi har en sorteringsalgoritm här.
Och även om du kanske oroa dig först detta är typ av en oändlig
loop, det är en cykel som aldrig kommer att sluta - det kommer att
sluta en gång vad som händer?
När n är mindre än 2.
Som så småningom kommer att hända, eftersom om du håller halvera och
halvera halvera dessa halvor, säkert så småningom du kommer att sluta
upp med bara 1 eller 0 element.
Vid vilken punkt, denna algoritm säger du är klar.
>> Så den verkliga magin i denna Algoritmen verkar vara i
det sista steget, sammanslagning.
Denna enkla idé bara samman två saker, det är det som i slutändan kommer
att tillåta oss att sortera en array av, låt oss säga, åtta element.
Så jag har åtta mer stress bollar upp Här, åtta bitar av papper, och en
Google Glas -
som jag får behålla.
>> [SKRATT]
>> DAVID MALAN: Om vi ​​kunde ta åtta volontärer, och låt oss se om vi kan
spela ut det här, så.
Wow, OK.
Datavetenskap blir kul.
Okej.
Så vad sägs om dig tre, största handen uppe.
Fyra i ryggen.
Och hur vi ska göra dig tre i denna rad?
Och fyra i fronten.
Så du åtta, kom upp.
>> [SKRATT]
>> DAVID MALAN: Jag är faktiskt inte säker på vad det är.
Är det stress bollar?
De skrivbordslampor?
Materialet?
Internet?
>> OK.
Så kom den upp.
Vem skulle vilja -
fortsätter att komma upp.
Låt oss se.
Och detta sätter dig i plats -
du är på plats ett.
Uh-oh, vänta en minut.
1, 2, 3, 4, 5, 6, 7 - oh, bra.
Okej, vi är bra.
Okej, så att alla har en plats, men inte på Google Glass.
Låt mig att köa upp dessa.
Vad är ditt namn?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Okej, du får se ut geeken, om det är OK.
Tja, jag gör också, antar jag, för bara ett ögonblick.
Okej, standby.
Vi har försökt att komma fram till en använda fall för Google Glass, och vi
trodde det skulle vara kul att bara göra detta när folk är på scenen.
Vi kommer att spela in världen ur deras perspektiv.
Okej.
Inte nog vad Google avsett.
Okej, om ni inte har något emot att bära detta för nästa obekväma minuter,
det skulle vara underbart.
>> Okej, så vi har här en rad element, och den arrayen, som per den
bitar av papper i dessa folks ' händer, är för närvarande osorterade.
>> MICHELLE: Åh, det är så konstigt.
>> DAVID MALAN: Det är ganska mycket slumpmässigt.
Och på bara ett ögonblick, kommer vi att försöka att genomföra samman sort tillsammans
och se vart det viktigaste insikten är.
Och tricket här med merge sort är något som vi inte har tagit ännu.
Vi behöver faktiskt lite ytterligare utrymme.
Så vad som kommer att vara särskilt intressant med detta är att dessa
killar kommer att flytta runt lite lite, eftersom jag kommer att anta att
det finns en extra uppsättning av utrymme, säga, precis bakom dem.
>> Så om de är bakom sin stol, det är den sekundära arrayen.
Om de är sittande här, det är den primära uppsättningen.
Men detta är en resurs som vi har utan hävstång hittills med bubbel
Sortera, med val sortera, med införandet sort.
Minns förra veckan, alla bara slags shuffled på plats.
De använde inte någon ytterligare minne.
Vi gjorde plats för människor med flytta människor runt.
>> Så detta är en viktig insikt, alltför.
Det är denna avvägning, i allmänhet i datavetenskap, av resurser.
Om du vill snabba upp något som tid, du kommer att
måste betala ett pris.
Och en av dessa priser är mycket ofta utrymme, hur mycket minne eller hård
diskutrymme som du använder.
Eller, ärligt talat, det belopp av programmerare tid.
Hur mycket tid det tar, det mänskliga, att faktiskt genomföra några mer
komplicerad algoritm.
Men för idag, avvägningen är tid och rum.
>> Så om ni bara kunde hålla upp din nummer så att vi kan se att du är
indeed matcha 4, 2, 6, 1, 3, 7, 8.
Utmärkt.
Så jag kommer att försöka iscensätta saker, om ni bara kan
följ mig här.
>> Så jag kommer att genomföra, dels den första steget i pseudokod, som är
på ingången av n element, om n är mindre än 2, och sedan tillbaka.
Självklart gör det inte gäller, så vi går vidare.
Så sortera den vänstra halvan av elementen.
Så det betyder att jag kommer att fokusera min uppmärksamhet för ett ögonblick på dessa
fyra killar här.
Okej, vad ska jag göra nu?
>> Publik: sortera vänstra halvan.
>> DAVID MALAN: Så nu har jag att sortera den vänstra halvan av dessa killar.
Eftersom igen, antar att själv Målet är att sortera den vänstra halvan.
Hur gör du det?
Följ bara instruktionerna, även även om vi gör det igen.
Så sortera den vänstra halvan.
Nu ska jag sortera dessa två killar.
Vad kommer härnäst?
>> Publik: sortera vänstra halvan.
>> DAVID MALAN: sortera vänstra halvan.
Så nu dessa, denna plats här, är en lista med storlek 1.
Och vad heter du nu igen?
>> PRINCESS DAISY: Princess Daisy.
>> DAVID MALAN: Princess Daisy är här.
Och så är hon redan sorteras, eftersom listan är av storlek 1.
Vad gör jag nu?
OK, tillbaka, eftersom den listan är över storlek 1, som är mindre än 2.
Men vad är nästa steg?
Och nu måste du typ av backa i ditt sinne.
>> Sortera den högra halvan, vilket är -
vad är ditt namn?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
Och så vad gör vi nu att Vi har en lista med storlek 1?
>> Målgrupp: Return.
>> DAVID MALAN: Försiktig.
Vi återvänder först, och nu den tredje steg - och om jag slags skildra den genom
omfamna de två sätena nu, nu har jag behöva slå ihop dessa två element.
Så nu tyvärr elementen är ur funktion.
Men det är där det överlåtande processen börjar bli övertygande.
>> Så om ni skulle kunna stå upp för just ett ögonblick, jag kommer att behöva dig, i en
ögonblick, att kliva bakom din stol.
Och om Linda, eftersom två är mindre än 4, varför inte
du kommer runt först?
Stanna där.
Så Linda, du kommer runt först.
>> Nu i verkligheten om det bara är en array vi kunde bara flytta henne i realtid
från den här stolen till denna plats.
Så antar att tog någon konstant antal steg 1.
Och nu -
men vi måste sätta dig in den första platsen här.
>> Och nu om du kan komma runt, liksom, vi ska
vara i läge två.
Och även om det känns som det är ta en stund, vad trevligt nu är
att den vänstra halvan av vänstra halvan sorteras nu.
Så vad var nästa steg, om vi nu spola vidare i berättelsen?
>> Publik: Höger halva.
>> DAVID MALAN: sortera högra halvan.
Så ni måste göra det här, liksom.
Så om du kunde stå upp för bara ett ögonblick?
Och vad heter du?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, så Jess är nu vänster hälften av den högra halvan.
Och så är hon en lista med storlek 1.
Hon har uppenbarligen sorteras.
Och ditt namn igen?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle är uppenbarligen en lista med storlek 1.
Hon har redan sorterade.
Så nu det magiska händer, sammanslagning processen.
Så vem ska komma först?
Uppenbarligen Michelle.
Så om du kunde komma runt tillbaka.
Det utrymme vi har för henne nu är bakom denna stol här.
Och nu om du kunde komma tillbaka också, vi har nu, för att vara tydlig, två
halvor, vardera av storlek 2 -
och bara för avbildning skull, om du kunde göra en liten bit av ett utrymme -
en vänster halva här, en högra halvan här.
>> Rewind vidare i berättelsen.
Vilket steg är nästa?
>> Publiken: Merge.
>> DAVID MALAN: Så nu måste vi gå samman.
Så OK, så nu, tack och lov, vi bara frigjort fyra stolar.
Så vi har använt dubbelt så mycket minne, men vi kan ge flip-floppa mellan
de två uppsättningarna.
Så vilket nummer är att komma först?
Så Michelle, uppenbarligen.
Så kom runt och ta din plats här.
Och då nummer 2 är uppenbarligen nästa, så att du kommer hit.
Nummer 4, nummer 6.
Och igen, även om det finns en lite inblandade promenader,
egentligen, kan dessa ske omedelbart, genom att flytta en -
OK, välspelad.
>> [SKRATT]
>> DAVID MALAN: Och nu är vi i ganska bra form.
Den vänstra halvan av hela ingången har nu sorterats.
Okej, så dessa killar hade fördelen av mitt -
hur gick det till slut alla flickor på vänster och alla pojkar till höger?
>> OK, så killarnas tur nu.
Så jag inte kommer att gå igenom dessa steg.
Vi ska se om vi kan återanvända samma pseudokod.
Om du vill gå vidare och stå upp, och ni, låt mig ge er mic.
Se om du inte kan replikera vad Vi gjorde bara här på
andra änden av listan.
Vem behöver tala först, baserat på algoritmen?
Så förklara vad du gör innan du gör några fot rörelser.
>> Högtalare 1: Okej, så eftersom Jag är den vänstra halvan av
vänstra halvan, återvänder jag.
Rätt?
>> DAVID MALAN: Bra.
>> Högtalare 1: Och sedan -
>> DAVID MALAN: Vem gör MIC gå till nästa?
>> Högtalare 1: nästa nummer.
>> Högtalare 2: Så jag är den högra halvan av den vänstra halvan av
vänstra halvan, och jag återvänder.
>> DAVID MALAN: Bra.
Du återvänder.
Så nu vad är nästa för er?
>> Högtalare 2: Vi vill se vem som är mindre.
>> DAVID MALAN: Exakt.
Vi vill slå samman.
Det utrymme vi kommer att använda för att slå samman dig in i, även om de är
uppenbarligen sorteras redan, vi ska att följa samma algoritm.
Så vem går i ryggen först?
Så 3, och därefter 7.
Och nu mic går dessa killar, OK?
>> SPEAKER 3: Så jag är den högra halvan av vänstra halvan, och min n är mindre än
1, så jag ska bara passera -
>> DAVID MALAN: Bra.
>> Högtalare 4: Jag är den högra halvan av högra halvan av den högra halvan, och jag är
även en person, så jag är kommer att återvända.
Så nu vi samman.
>> SPEAKER 3: Så vi går tillbaka.
>> DAVID MALAN: Så du går in på baksidan.
Så 5 går först, och sedan 8.
Och nu publik, vilket är den steg vi nu spola tillbaka
tillbaka i våra sinnen?
>> Publiken: Merge.
>> DAVID MALAN: Sammanslagning vänstra och högra hälften av den ursprungliga vänstra halvan.
Så nu -
och bara för att klargöra detta, göra lite utrymme
mellan er två killar.
Så nu det är de två listorna, vänster och höger.
Så hur sammanfoga vi nu er in den främre stolsraden igen?
>> 3 går först.
Sedan 5, uppenbarligen.
Sedan 7, och nu 8.
OK, och nu är vi?
>> Publik: Inte gjort.
>> DAVID MALAN: Inte gjort, eftersom självklart, det finns ett steg kvar.
Men återigen, anledningen till att jag använder detta jargong som "bakåt i ditt sinne,"
det är för att det är egentligen vad som händer.
Vi går igenom alla dessa steg, men vi sorts pausa för ett
ögonblick, dyka djupare in i algoritm, pausa för ett ögonblick,
dykning djupare in i algoritmen, och nu måste vi sortera av bakåt i vår
sinnen och ångra alla dessa skikt att vi har sorts parkeras.
>> Så nu har vi två listor med storlek 4.
Om ni kunde stå upp för sista gången och göra lite utrymme här att
göra klart att detta är den vänstra hälften av den ursprungliga, den
högra hälften av den ursprungliga.
Vem är det första numret som vi behöva dra in på baksidan?
Michelle, förstås.
>> Så vi satte Michelle här.
Och vem har nummer 2?
Nummer 2 kommer på baksidan också.
Nummer 3?
Utmärkt.
Nummer 4, nr 5, nr 6, nummer 7, och nummer 8.
>> OK, så det kändes som en hel steg, for sure.
Men nu ska vi se om vi inte kan bekräfta sorts intuitivt att detta
algoritm grunden, särskilt som n blir riktigt stora, som vi har sett
med animationer, är fundamentalt snabbare.
Så jag hävdar denna algoritm i värsta fallet och även i bästa fall
är stor O n gånger log n.
Det vill säga, det finns någon aspekt av denna algoritm, som tar n steg, men
det finns en annan aspekt någonstans i denna iteration, att kretsa, som
tar log n steg.
Kan vi sätta fingret på vad de två siffror hänvisar till?
Tja, där -
där skulle micken gå?
>> Högtalare 1: Skulle log n vara bryta oss upp i två -
dividera med två, i huvudsak.
>> DAVID MALAN: Exakt.
Varje gång vi ser i någon algoritm därmed långt, det har varit detta mönster av
dela, dela, dela.
Och det är oftast minskas till något som är
logaritmisk, log bas 2.
Men det skulle verkligen vara något, men log bas 2.
>> Nu vad om n?
Jag kan se att vi typ av delat er killar - delat dig, uppdelat dig,
delat dig, uppdelat dig.
Var kommer utgången från?
>> Så det är en sammanslagning.
Eftersom tänka på det.
När du sammanfogar åtta personer tillsammans, varigenom hälften av dem är en uppsättning av fyra
och den andra hälften är en annan uppsättning av fyra, hur du går
om att göra en sammanslagning?
Tja, gjorde ni det ganska intuitivt.
>> Men om jag istället gjorde det lite mer metodiskt, kanske jag har pekat på
den vänstra personen först med min vänstra handen, pekade på den vänstra personen
av att hälften med min högra hand, och precis därefter gick genom
listan, pekar på det minsta elementet varje gång, flytta fingret över och
över som behövs hela listan.
Men vad är nyckeln om denna sammanslagning Processen är jag jämföra dessa par
av element.
Från den högra halvan och från vänster hälften, jag har aldrig en gång backa.
>> Så sammanfogningen själv tar inte mer än n steg.
Och hur många gånger har jag har att göra det ihop?
Tja, inte mer än N, och vi bara såg att den slutliga sammanfogningen.
Och så om du gör något som tar log n steg n gånger, eller vice versa,
det kommer att ge oss n gånger log n.
>> Och varför är det bättre?
Tja, om vi vet redan att log n är bättre än N - rätt?
Vi såg i binär sökning, telefonboken exempel var log n definitivt
bättre än linjär.
Så det betyder att n gånger log n är definitivt bättre än n gånger en annan
n, AKA n kvadrat.
Och det är vad vi i slutändan känner.
>> Så stor applåd, om vi kunde, för killarna.
>> [Applåder]
>> DAVID MALAN: Och dina gåvor avsked - du kan hålla tal,
om du skulle vilja.
Och din avskedsgåva, som vanligt.
Åh, och vi kommer att skicka dig filmen, Michelle.
Tack.
Okej.
Hjälp dig själv till en stress boll.
>> Och låt mig dra upp, under tiden, vår vän Rob Bowden att erbjuda
något annorlunda perspektiv på detta, eftersom du kan tänka på dessa
steg sker i en något annat sätt.
I själva verket, den set-up för vad Rob handlar om att visa oss utgår från att vi har
redan gjort uppdelningen av stor lista i åtta små listor,
varje storlek 1.
>> Så vi ändrar pseudokoden en lite bara för att sortera av få på
grundidé om hur det överlåtande fungerar.
Men speltid för vad han är på väg att göra är fortfarande
kommer att vara samma.
Och återigen, är set-up här att han är börjat med åtta listor med storlek 1.
Så du har missat den delen där han är faktiskt gjort log n, log n, log n
dividera på ingången.
>> [VIDEO SPELA]
>> -Det är det för steg ett.
För två steg, upprepade samman par av listor.
>> DAVID MALAN: Hm.
Endast ljud kommer ur min dator.
Låt oss prova det här igen.
>> -Just godtyckligt välja vilka - Nu har vi fyra listor.
Läs innan.
>> DAVID MALAN: Det gå vi.
>> -Sammanslagningen 108 och 15, slutar vi upp med listan 15, 108.
Sammanslagning 50 och 4, vi sluta med 4, 50.
Sammanslagning 8 och 42, vi sluta med 8, 42.
Och sammanslagning 23 och 16, vi sluta med 16, 23.
>> Nu är alla våra listor är av storlek 2.
Lägg märke till att var och en av fyra listor sorteras.
Så vi kan börja sammanslagning par listorna igen.
Sammanslagning 15 och 108 och 4 och 50, vi först ta 4, sedan 15, sedan
den 50, sedan 108.
Sammanslagning 8, 42 och 16, 23, tar vi först den 8, sedan 16, sedan 23,
sedan 42.
>> Så nu har vi bara två listor med storlek 4, är var och en sorteras.
Så nu vi samman dessa två listor.
Först tar vi 4, då vi tar 8, sedan tar vi det 15, sedan 16, sedan
23, sedan 42, sedan 50, sedan 108.
>> [END VIDEOAVSPELNING]
>> DAVID MALAN: Igen, varsel, aldrig han rörde en viss kopp mer än en gång
efter att avancera bortom det.
Så han aldrig upprepa.
Så han alltid flytta åt sidan, och det är där vi fick vår n..
>> Varför inte låta mig dra upp en animation som vi såg tidigare, men den här gången
fokusera enbart på merge sort.
Låt mig gå vidare och zooma in på detta här.
Först låt mig välja en slumpmässig indata, förstärka detta, och du kan sortera på se
vad vi tog för givet, tidigare, sammanfoga Sortera faktiskt gör.
>> Så märker att du får dessa halvor eller dessa kvartal eller dessa åttondelar av
problem som helt plötsligt börjar ta god form.
Och slutligen, ser du på slutet att bam,
allt slås ihop.
>> Så dessa är bara tre olika tar på samma idé.
Men den viktigaste insikten, precis som klyftan och erövra i den allra första klassen,
var att vi bestämde att på något sätt dela problemet till något stort, till
något slags identiska i anden, men mindre och mindre och mindre
och mindre.
>> Nu ett annat roligt sätt att sortera om tro om dessa, även om det inte är
kommer att ge dig samma intuitiva förståelse, är
Följande animation.
Så det här är en video någon sätta ihop den associerad annorlunda
ljud med de olika verksamheterna för insättning sortera, för merge sort, och
ett par andra.
Så i ett ögonblick, jag ska träffa Play.
Det handlar om en minut lång.
Och även om du kan fortfarande se mönster som händer, den här gången kan du
också höra hur dessa algoritmer är utför olika sätt och med
något olika mönster.
>> Detta är införandet sort.
>> [TONER SPELA]
>> DAVID MALAN: Det igen försöker att infoga varje element
in där det hör hemma.
Detta är bubbla sortera.
>> [TONER SPELA]
>> DAVID MALAN: Och du kan sortera på känsla hur relativt lite arbete det gör
på varje steg.
Detta är vad TRÅKIGHET låter som.
>> [TONER SPELA]
>> DAVID MALAN: Detta är selection sort, där vi väljer det element vi vill genom
går igenom igen och igen och igen och sätta det i början.
>> [TONER SPELA]
>> DAVID MALAN: Detta är samman sort, vilket du kan verkligen börja känna.
>> [TONER SPELA]
>> [SKRATT]
>> DAVID MALAN: Något som kallas GNOME Sortera, vilket vi inte har tittat på.
>> [TONER SPELA]
>> DAVID MALAN: Så låt mig se, nu, distraherad när du förhoppningsvis är av
musik, om jag kan glida lite bit av matematik i här.
Så det finns en fjärde sätt att vi kan tänka på vad det innebär dessa
funktioner för att vara snabbare än de som vi har sett tidigare.
Och om du kommer på kursen från en matematik bakgrund, du
faktiskt vet kanske redan att du kan smälla en term på denna teknik -
nämligen rekursion, en funktion som kallar sig av någon anledning.
>> Och igen, minns att merge sort pseudokod var rekursiv i den meningen
att en av merge sort fotspår var att ringa sort -
som i sig själv.
Men tack och lov, eftersom vi höll ringer sortera, eller slå samman sortera,
specifikt, på en mindre och mindre och mindre lista, så småningom vi
bottnat tack vare vad vi kallar ett basfall, den hårdkodade fall som
sade om listan är liten, mindre än 2 i så fall, bara omedelbart återvända.
Om vi ​​inte har den där speciella fall algoritm skulle aldrig bottna,
och du skulle verkligen komma in i en oändlig loop verkligen evigt.
>> Men antag att vi ville nu sätta några siffror på detta, återigen, med n
som storleken på den ingående.
Och jag ville fråga dig, vad är den totala tid som krävs för
rinnande merge sort?
Eller mer generellt, vad är kostnaden för det i tid?
>> Jo det är ganska lätt att mäta det.
Om n är mindre än 2, den tid det tar i sortering n element,
där n är 2, är 0.
Eftersom vi tillbaka bara.
Det finns inget arbete att göra.
Nu vågar jag påstå, det är kanske ett steg eller två steg för att räkna ut mängden
arbete, men det är tillräckligt nära 0 som Jag kommer bara att säga nej arbetet är
krävs om listan är så liten vara ointressant.
>> Men det här fallet är intressant.
Den rekursiva fallet var den gren av pseudokoden att nämnda annat, sortera
den vänstra halvan, sortera rätt hälften, slå ihop de två halvorna.
Nu varför detta uttryck representerar denna kostnad?
Tja, betyder T n bara tid att sortera n element.
Och sedan på den högra sidan av likhetstecken där, delade T n
av 2 hänvisar till kostnaden för vad?
Sortering den vänstra halvan.
Den andra T från n delat med två är förmodligen med hänvisning till kostnaden för
sortera den högra halvan.
>> Och sedan plus n?
Är en sammanslagning.
För om du har två listor, en för storlek n över 2 och ett annat av storlek n
över 2, måste du i huvudsak beröra vart och ett av dessa element, precis som Rob
berörde alla kopparna, och bara som vi pekade på var och en av
volontärer på scenen.
Så n är på bekostnad av sammanslagning.
>> Nu tyvärr, denna formel är också i sig rekursiv.
Så om ställde frågan, om n är, säg, 16, om det finns 16 personer på scenen
eller 16 koppar i videon, hur många totalt steg tar det att sortera dem
med merge sort?
Det är faktiskt inte ett självklart svar, eftersom du nu har att sortera av
rekursivt besvara denna formel.
>> Men det är OK, eftersom låt mig föreslå att vi gör följande.
Den tid det tar att sortera 16 personer eller 16 koppar kommer att vara representerade
generellt som T 16.
Men det är lika, enligt vår föregående formel, två gånger så mycket
tid det tar att sortera 8 koppar plus 16.
Och återigen, är plus 16 tiden att gå samman, och två gånger T av 8 är den
tid att sortera vänstra och högra halvan.
>> Men återigen, är detta inte tillräckligt.
Vi måste dyka in djupare.
Detta innebär att vi måste svara på Frågan, vad är T på 8?
Jo T av 8 är bara 2 gånger T 4 plus 8.
Tja, vad är T 4?
T 4 är bara 2 gånger T om 2 plus 4.
Tja, vad är T 2?
T 2 är bara 2 ggr T av 1 plus 2.
>> Och återigen, vi är typ att få fastnat i denna cykel.
Men det handlar om att träffa den sk basfall.
För vad är T 1, vi påstår?
0.
Så nu äntligen, kan vi arbeta bakåt.
>> Om T 1 är 0, kan jag nu gå tillbaka upp en linje till den här killen här, och jag kan
plug in 0 för T 1.
Så det betyder att det är lika med 2 gånger noll, annars känd som 0, plus 2.
Och så att hela uttrycket är 2.
>> Nu om jag tar T 2, vars svar är 2, anslut den till den mellersta raden, T
av 4, ger det mig 2 gånger 2 plus 4, så 8.
Om jag ansluter sedan i 8 till föregående line, ger det mig 2 gånger 8, 16.
Och om vi fortsätter sedan att med 24, lägga i 16, får vi äntligen en
värde av 64.
>> Nu det i och för sig sorts talar ingenting till N notation, den
stort O, den omega som vi har pratat om.
Men det visar sig att 64 verkligen är 16, storleken av den ingående,
log bas 2 av 16.
Och om detta är en liten främmande, bara tänker tillbaka, och det kommer tillbaka
till dig så småningom.
Om detta är log bas 2, det är som två upphöjt till vad som ger dig 16?
Åh, det är 4, så det är 16 gånger 4.
>> Och återigen, det är inte en stor sak om detta är en slags dimmig minne nu.
Men för nu, ta på tro att 16 log 16 är 64.
Och så faktiskt, med denna enkla förstånd kolla, har vi bekräftat -
men inte visat formellt -
att gångtiden för Merge sort är verkligen n log n.
>> Så inte illa.
Det är definitivt bättre än den algoritmer vi har sett hittills, och
Det beror på att vi har belånade, en, en teknik som kallas rekursion.
Men mer intressant än så, att begreppet dela och erövra.
Igen, verkligen vecka 0 saker som redan nu är återkommande i ett
mer övertygande sätt.
>> Nu en rolig liten övning, om du har aldrig gjort detta - och du förmodligen
inte skulle ha, eftersom slags normal folk tror inte att göra detta.
Men om jag går till google.com och om Jag vill lära sig något om
rekursion, Enter.
>> [SKRATT]
[Mera skratt]
DAVID MALAN: Bad joke sakta sprider sig.
[SKRATT]
DAVID MALAN: Just i fallet, det är där.
Jag visste inte stava det fel, och det är skämt.
Okej.
Förklara det för människor bredvid dig om Det har inte riktigt klickat ännu.
Men rekursion, mer allmänt, hänvisar till processen för en funktion ringer
själv, eller mer allmänt, dela ett problem till något som kan vara
lösas styckevis genom att lösa identiska representativa problem.
>> Nåväl, låt oss växla för bara ett ögonblick.
Vi vilja avsluta på vissa cliffhangers, så låt oss börja att ställa
scenen, i flera minuter, på en mycket enkel idé -
som att byta två element, eller hur?
Alla dessa algoritmer vi har varit talar om de senaste par
föreläsningar innebära några slags byte.
Idag var visualiseras genom dem få upp ur sina stolar och
gå runt, men i kod, skulle vi bara ta ett element från en array
och plopp det i en annan.
>> Så hur går vi om att göra detta?
Nåväl, låt mig gå vidare och skriva en snabb program här.
Jag kommer att gå vidare och göra detta som följande.
Låt oss kalla detta -
vad vill vi att kalla den här?
>> Nej, faktiskt inte.
Låt mig bakåt.
Jag vill inte göra det cliffhanger ännu.
Det kommer att förstöra det roliga.
Låt oss göra detta istället.
>> Antag att jag vill skriva ett litet program och som omfattar nu detta
idén om rekursion.
Jag slags fick framför mig där.
Jag kommer att göra följande.
>> Först en snabb inkludera i standarden io.h, liksom en include av cs50.h.
Och då jag ska gå vidare och förklara int main void
på vanligt sätt.
Jag insåg att jag har misnamed filen, så Låt mig bara lägga till en. c förlängning här så
att vi kan sammanställa det ordentligt.
Börja här funktionen.
>> Och den funktionen jag vill skriva, ganska helt enkelt, är en som ber
användaren för ett nummer och sedan lägger upp alla nummer mellan att
antal och, säg, 0.
Så först ska jag gå vidare och förklara int n.
Då jag kopierar någon kod som vi har använt på ett tag.
Medan något är sant.
Jag ska återkomma till det om en stund.
>> Vad vill jag göra?
Jag vill säga printf positiv heltal behaga.
Och sedan ska jag säga n blir få int.
Så återigen, vissa standardtext kod som vi har använt tidigare.
Och jag kommer att göra detta medan n är mindre än 1.
Så detta kommer att säkerställa att användaren ger mig ett positivt heltal.
>> Och nu ska jag göra följande.
Jag vill lägga upp alla nummer mellan 1 och och n, eller 0 och n,
ekvivalent, för att få den totala summan.
Så den stora sigma symbolen som ni kanske minns.
Så jag kommer att göra detta genom att först ringa en funktion som kallas sigma,
passerar den i N, och sedan kommer jag att säger printf, är svaret rätt där.
>> Så kort sagt, jag och int från användaren.
Jag se till att det är positivt.
Jag deklarerar en variabel som heter svar på typen int och butik i det returen
Värdet av sigma, passerar i n som indata.
Och då ska jag skriva ut det svaret.
>> Tyvärr, trots att sigma låter som något som kan vara i
den math.h filen, sin förklaring, det är faktiskt inte.
Så det är OK.
Jag kan genomföra detta själv.
Jag kommer att genomföra en funktion som kallas sigma, och det kommer att ta ett
parameter -
låt oss bara kalla det m, precis så det är annorlunda.
Och sedan upp här, jag kommer att säga, väl, om m är mindre än 1 - detta är en
mycket ointressant program.
Så jag kommer att gå vidare och omedelbart returnera 0.
Det bara inte vettigt att lägga upp alla talen mellan 1 och m om m
själv är 0 eller negativ.
>> Och då jag ska gå vidare och gör detta mycket iterativt.
Jag kommer att göra denna typ av old-school, och jag ska gå vidare
och säga att jag ska deklarera en summa för att vara 0.
Sedan kommer jag att ha en for-loop för int -
och låt mig göra det för att matcha våra distributionen kod, så att du har en kopia
hemma. int i får 1 på upp till i är mindre än eller lika med m.
I plus plus.
Och sedan insidan av denna för loop -
Vi är nästan där -
summan blir summa plus 1.
Och sedan ska jag tillbaka summan.
>> Så jag gjorde det snabbt, ganska visserligen.
Men återigen, är den viktigaste funktionen pretty okomplicerad, baserad på kod som vi har
skrivit hittills.
Använder dubbla loop för att få en positiv int från användaren.
Jag passerar då att int till en ny funktion heter sigma, kalla det, återigen, n..
Och jag lagrar returvärdet, svaret från den svarta lådan för tillfället
känd som sigma, i en variabel kallas svar.
Då jag skriver ut det.
>> Om vi ​​nu fortsätter berättelsen, hur är sigma genomförs?
Jag föreslår att genomföra följande.
Först, en liten bit av felkontroll att se till att användaren inte är
jävlas med mig och går i några negativa eller 0 värde.
Då ska jag deklarera en variabel som heter sammanfatta och ställa den till 0.
>> Och nu börjar jag att flytta från i lika 1 hela vägen upp till och med m,
eftersom jag vill inkludera alla siffror från ett till m, allomfattande.
Och inne i denna för slinga, gör jag bara Summan blir vad det är nu, plus
värdet av i.
Plus värdet av jag.
>> Som en parentes, om du inte har sett denna innan, det finns några syntaktiska socker
för denna linje.
Jag kan skriva om detta som plus lika i, bara för att rädda mig själv några enkla knapptryckningar
och se lite svalare.
Men det är allt.
Det är funktionellt samma sak.
>> Tyvärr, denna kod är inte gå att kompilera ännu.
Om jag kör make sigma 0, hur am Jag kommer att bli utskälld?
Vad kommer det att inte vilja?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: Ja, det gjorde jag inte förklara funktionen uppe, eller hur?
C är ganska dumt, eftersom det endast gör vad du säger åt den att göra, och du
måste göra det i den ordningen.
Och så om jag slår in här, kommer jag att få en varning om sigma implicita
deklaration.
>> Åh, inte ett problem.
Jag kan gå upp till toppen, och jag kan säga, okej, vänta en minut.
Sigma är en funktion som returnerar en int och det förväntar sig en
int som indata, semikolon.
Eller jag kunde sätta hela funktionen över huvud, men i allmänhet, skulle jag
rekommenderar mot detta, eftersom det är trevligt att alltid ha stora upptill så
du kan dyka rätt in och vet vad en Programmet gör genom att läsa på först.
>> Så nu låt mig rensa skärmen.
Remake sigma 0.
Allt verkar kolla.
Låt mig köra sigma 0.
Positiv inter.
Jag ska ge det numret 3 för att hålla det enkelt.
Så det borde ge mig 3 plus 2 plus en, så 6.
Enter, och faktiskt jag får 6.
>> Jag kan göra något större -
50, 12, 75.
Precis som en tangent, kommer jag att göra något löjligt som en riktigt stor
nummer, Oh, som faktiskt fungerade -
eh, jag tror inte det är rätt.
Låt oss se.
Låt oss verkligen bråka med den.
>> Det är ett problem.
Vad är det som händer?
Koden är inte så illa.
Det är fortfarande linjär.
Whistling är en god effekt, men.
Vad är det som händer?
>> Inte säker på om jag hörde det.
Så visar det sig - och Detta är som en parentes.
Detta är inte kärnan till idén om rekursion.
Det visar sig, eftersom jag försöker representera ett så stort antal, de flesta
sannolikt det är att misstolkas av C som ett inte positivt tal,
men negativt tal.
>> Vi har inte pratat om det här, men det visar sig att det finns negativa tal
i världen förutom till positiva tal.
Och de medel genom vilka du kan representera ett negativt tal
huvudsak, använder du en speciell bit för att indikera
positivt över negativ.
Det är lite mer komplicerat än så, men det är den grundläggande idén.
>> Så tyvärr, om c är förvirrande en av dessa bitar som verkligen betyder,
åh, är detta ett negativt tal, min loop här, till exempel, är faktiskt aldrig
kommer att upphöra.
Så om jag faktiskt skriva något om och om igen, skulle vi
se en hel del.
Men återigen, detta är förutom punkten.
Detta är egentligen bara en sorts intellektuell nyfikenhet som vi kommer
tillbaka till så småningom.
Men för nu, är detta en riktig genomförande om vi antar att den
användaren kommer att tillhandahålla ints som passar inom ints.
>> Men jag hävdar att denna kod, ärligt talat, skulle kunna göras så mycket mer enkelt.
Om målet till hands är att ta ett antal som m och lägg upp allt
siffror mellan det och en, eller omvänt mellan 1 och det, hävdar jag
att jag kan låna den här idén att slå samman Sortera hade, som ägde ett problem
av denna storlek och dividera det till något mindre.
Kanske inte hälften, men mindre, men representativt samma.
Samma idé, men ett mindre problem.
>> Så jag är faktiskt - låt mig spara den här filen med en annan version nummer.
Vi kallar denna version 1 stället för 0.
Och jag hävdar att jag kan faktiskt reimplement detta i denna typ av
kluriga sätt.
>> Jag kommer att lämna en del av den ensam.
Jag kommer att säga om m är mindre än eller till och med lika med 0 -
Jag kommer bara att vara lite mer anal denna gång
med min felkontroll -
Jag ska gå vidare och returnera 0.
Detta är godtycklig.
Jag bara helt enkelt avgöra om användaren ger mig ett negativt tal, jag
återvänder 0, och de borde ha läst dokumentationen närmare.
>> Else -
märker vad jag ska göra.
Else kommer jag att återvända m plus -
vad som är sigma av m?
Tja, sigma av m plus m minus 1, plus m minus 2, plus m minus 3.
Jag vill inte skriva allt detta ut.
Varför gör jag inte bara punt?
Rekursivt kalla mig själv med en något mindre problem, semikolon,
och kallar det en dag?
>> Rätt?
Nu även här, kanske du känner eller oroa att detta är en oändlig slinga som jag är
inducerande, där jag genomför sigma genom att ringa sigma.
Men det är helt OK, eftersom jag tänkte framåt en extra vilka linjer?
>> Publik: [OHÖRBAR].
>> DAVID MALAN: 23 till 26, vilket är min om tillstånd.
För vad är trevligt om subtraktion här, eftersom jag håller
handing sigma mindre problem, mindre problem, mindre - det är inte
halva storleken.
Det är bara en baby steg mindre, men det är OK.
Eftersom så småningom kommer vi att arbeta vår väg ner till 1 eller 0.
Och när vi slog 0, Sigma inte kommer att kalla sig själv längre.
Det kommer att omedelbart återvända 0.
>> Så effekten, om du slags vind här upp i ditt sinne, är att lägga m plus
m minus 1, plus m minus 2, plus m minus 3, plus dot, dot, dot, m minus
m, så småningom ge dig 0, och Effekten är i slutändan att lägga alla
dessa saker tillsammans.
Så vi har inte, med rekursion, löst problemet som vi
kunde inte lösa innan.
Faktum version 0 av detta, och varje Problemet hittills har varit lösbar
med att bara använda loopar eller medan öglor eller liknande konstruktioner.
>> Men rekursion, vågar jag säga, ger oss ett annorlunda sätt att tänka
problem, vilket om vi kan ta en problem, dela upp det från något
något stort till något något mindre, hävdar jag att vi kan lösa det
kanske lite mer elegant i termer av konstruktionen, med mindre kod,
och kanske även löser problem som skulle vara svårare, eftersom vi kommer så småningom
se, lösa rent iterativt.
>> Men cliffhanger som jag gjorde vill lämna oss på var det här.
Låt mig gå vidare och öppna upp en fil från -
faktiskt, låt mig gå och göra detta riktigt snabbt.
Låt mig gå vidare och föreslå följande.
Bland dagens kod är denna fil här.
Detta här, noswap.
>> Så detta är ett dumt litet program som Jag piskade upp som påstår sig göra
följande.
I huvud, deklarerar det först en int kallade x och tilldelar den
värdet 1.
Sen deklarerar en int y och tilldelar den värdet 2.
Sedan den skriver ut vad x och y är.
Sedan står det, byta, dot dot dot.
>> Sedan den påstår att anropa en funktion kallad swap, passerar i x-och
y, en idé som är det förhoppningsvis x och y kommer tillbaka
annorlunda, motsatsen.
Sen hävdar bytt!
med ett utropstecken.
Sen skriver ut x och y.
>> Men det visar sig att denna mycket enkel demonstration ned
här är faktiskt buggy.
Även om jag förklara en tillfällig variabel och tillfälligt sätta en i
det, då jag omplacera ett värde på b -
vilket känns rimligt, eftersom jag har sparat en kopia av ett i temp.
Då jag uppdaterar b till lika oavsett var i temp.
Denna typ av skal spel att flytta en till b och b till ett med hjälp av denna
medelålders man som heter temp känns helt rimligt.
>> Men jag hävdar att när jag kör det här kod, som jag gör nu -
låt mig gå vidare och klistra in här.
Jag kallar detta noswap.c.
Och som namnet antyder, är detta inte kommer att vara ett korrekt program.
Gör noswap. / Ingen swap.
x är 1, är y 2, byta, bytte.
x är 1, y är 2.
Detta är fundamentalt fel, även men detta verkar perfekt
rimligt för mig.
Och det finns en anledning, men vi är inte kommer att avslöja orsaken ännu.
>> För nu den andra cliffhanger jag ville att lämna dig med detta, en
tillkännagivandet av slag på rabattkoder.
Vår innovation med sena dagar i år har framkallat en icke-trivial antalet
frågor, vilket var inte vår avsikt.
Avsikten med dessa kupong koder, där om du gör en del av problemet
ställa tidigt, och därmed få en extra dag, var verkligen att hjälpa er hjälp
själv börjar tidigt, sortera av genom incentivizing dig.
Hjälper oss att fördela belastningen över kontorstid bättre så att
Det är typ av win-win.
>> Tyvärr tror jag mina instruktioner har inte varit hittills, mycket tydligt, så
Jag gick tillbaka i helgen och uppdaterade spec i större, djärvare text till
förklara kulor som dessa.
Och bara för att säga det mer allmänt, genom standard, problemsamlingar beror torsdag
vid middagstid, per kursplanen.
Om du börjar tidigt, avslutar en del av problemet fastställts av onsdag kl 12:00
PM, den del som hänför sig till en kupong kod, är tanken att du kan förlänga
din deadline för P satt fram till fredag.
Det vill säga, lite av en liten del av P in i förhållande till vad som normalt är den
större problem, och du köper själv en extra dag.
Återigen blir det du tänker problemet set, får du
kontorstid förr.
Men kupongkod problemet är fortfarande krävs, även om du inte skickar in den.
>> Men mer fängslande är här.
(TEATERVISKNING) Och de folk som lämnar tidigt är gonna ångra det.
Så är de folk på balkongen.
Jag ber om ursäkt i förväg till folk på balkongen av skäl som kommer att vara
klart på bara ett ögonblick.
>> Så vi är lyckligt lottade att ha en av CS50: s tidigare chef Undervisning Fellows vid
ett företag som heter dropbox.com.
De har mycket generöst donerat en kupongkod här för mycket utrymme,
som är upp från vanliga 2 gigabyte.
Så vad jag trodde vi skulle göra på detta sista anmärkning är att göra lite av en giveaway,
varigenom på bara ett ögonblick, kommer vi att avslöja vinnaren och som har en kupong
kod som du sedan kan gå till deras hemsida, skriv in det i, och voila, få en
hel del mer Dropbox utrymme för din apparaten och för dina personliga filer.
>> Och först, vem skulle vilja delta i denna ritning?
OK, nu som gör det ännu roligare.
Den person som tar emot denna 25-gigabyte kupongkod - vilket är långt
mer övertygande än den sena dagar nu, kanske -
är den som sitter på toppen av en sittdyna under vilken det finns
denna kupongkod.
Du kan nu titta under din sittdyna.
>> [VIDEO SPELA]
>> -Ett, två, tre.
>> [SCREAMING]
>> -Du får en bil!
Du får en bil!
>> DAVID MALAN: Vi får se du på onsdag.
>> -Du får en bil!
Du får en bil!
>> DAVID MALAN: Balkong folks, kom här nere till fronten,
där vi har extra.
>> -Alla får en bil!
Alla får en bil!
>> [END VIDEOAVSPELNING]
>> Berättare: Vid nästa CS50 -
>> SPEAKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh -
>> [Ukelele PLAYS]