[Speel van musiek] David Malan: Alle reg. Alle reg, welkom terug. So dit is Week 4, die begin daarvan, reeds. En jy sal die laaste week onthou, ons sit kodeer opsy gesit is vir net 'n bietjie en ons begin praat 'n bietjie meer hoë-vlak, oor dinge soos soek-en sorteer, wat al ietwat eenvoudige idees, is verteenwoordiger van 'n klas van probleme jy sal begin om veral op te los as jy begin dink oor die finale projekte en interessante oplossings wat jy mag hê om werklike probleme. Nou borrel soort was een van die eenvoudigste sulke algoritmes, en dit gewerk het deur met hierdie klein getalle in 'n lys of in 'n verskeidenheid soort borrel hul weg op die top, en die groot getalle beweeg om hul pad af te die einde van die lys. En onthou dat ons kan visualiseer borrel soort 'n bietjie iets soos hierdie. So laat my voort te gaan en kliek op 'Begin. Ek het vooraf gekies borrel soort. En as jy onthou dat die langer blou lyne stel groot getalle, klein blou lyne stel klein getalle, soos ons gaan deur dit weer en weer en weer, vergelyking van twee bars langs elke ander in rooi, ons gaan die te ruil grootste en die kleinste indien hulle is buite orde. So dit sal gaan en gaan op en gaan op, en jy sal sien dat die groter elemente maak hul pad na die reg, en die kleiner elemente maak hul pad na die linkerkant. Maar ons het begin om te kwantifiseer die doeltreffendheid, die kwaliteit van hierdie algoritme. En ons het gesê dat in die ergste geval, hierdie algoritme het Ongeveer hoeveel stappe? So n vierkant. En wat was n? GEHOOR: Aantal elemente. David Malan: So n was die aantal elemente. En so sal ons doen dit dikwels. Enige tyd wat ons wil om te praat oor die grootte van 'n probleem of die grootte van 'n insette, of die bedrag van die tyd wat dit neem uitset te produseer, sal ons net veralgemeen wat die insette is as n. So terug in Week 0, die aantal bladsye in die telefoon boek was n. Die aantal studente wat in die kamer was n. So ook hier, ons volgende dat patroon. Nou n vierkant is nie besonder vinnig, so ons probeer om beter te doen. En so het ons gekyk na 'n paar ander algoritmes, waaronder was seleksie soort. So seleksie soort was 'n bietjie anders. Dit was amper 'n eenvoudiger, durf ek sê, waardeur ek begin by die begin van die lys van ons vrywilligers en ek het net weer en weer en weer het deur die lys, pluk uit die kleinste element op 'n slag en om hom of haar aan die begin van die lys. Maar hierdie, ook, sodra ons begin om te dink deur middel van die wiskunde en groter prentjie, gedink oor hoeveel keer Ek is heen en weer en weer terug en weer, ons het in die ergste geval, seleksie soort ook, was wat? n vierkant. Nou in die werklike wêreld, kan dit eintlik effens vinniger. Omdat weer, het ek nie hoef te hou back tracking nadat ek gesorteer van die kleinste elemente. Maar as ons dink oor baie groot n, en As jy soort van doen uit die wiskunde as Ek het op die raad, met die n geruite minus iets, alles Behalwe die n vierkant, een keer n regtig groot, nie regtig soveel saak nie. So as die rekenaar wetenskaplikes, ons sorteer draai 'n blinde oog na die kleiner faktore en fokus net op die faktor in 'n uitdrukking wat gaan maak die grootste verskil maak. Wel, laastens, het ons gekyk by te voeg soort. En dit was soortgelyk in die gees, maar eerder as om te gaan deur iteratief en kies die kleinste element een op 'n tyd, ek plaas het die hand dat ek gehandel is, en ek het besluit, al reg, jy hoort hier. Daarna het ek verhuis na die volgende element en besluit dat hy of sy behoort hier. En dan het ek verhuis oor en oor. En ek kan nie, langs die pad, skuif hierdie ouens in orde te om plek te maak vir hulle. So dit was 'n soort van die geestelike ommekeer van seleksie soort wat ons genoem voeg soort. So het hierdie onderwerpe te voorkom in die werklike wêreld. Net 'n paar jaar gelede, toe 'n sekere senator hardloop vir president, Eric Schmidt, teen die tyd dat die hoof uitvoerende beampte van Google, eintlik die geleentheid gehad om hom te ondervra. En ons het gedink ons ​​hierdie YouTube wil deel clip vir jou hier, as ons kon draai die volume. [Video speel] -Nou, Senator, jy is hier op Google, en ek wil om te dink aan die presidensie as 'n werksonderhoud. [Gelag] -Nou is dit moeilik om te kry 'n werk as president. En jy gaan deur middel van die pogings nou. Dit is ook moeilik om 'n werk by Google te kry. Ons het vrae en ons vra ons kandidate vrae. En hierdie een is van Larry Schwimmer. [Gelag] -Julle dink ek is 'n grap? Dit is reg hier. Wat is die mees doeltreffende manier om te sorteer 'n miljoen twee-bit heelgetalle? [Gelag] -Wel, uh - -Ek-is jammer. Miskien moet ons - -Nee, nee, nee, nee, nee. -Dit is nie 'n - OK. -Ek dink die borrel soort sou wees op die verkeerde manier om te gaan. [Gelag] [Juig en applous] -Kom op, wat hom dit vertel? OK. [Einde video-vertoning] David Malan: So daar het jy dit. So het ons begin om hierdie bedryf te kwantifiseer tye, om so te spreek, met iets genoem asimptotiese notering, wat net verwys na ons soort van die draai 'n blinde oog op die kleiner faktore en net na die loop van die tyd, die prestasie van hierdie algoritmes, as n regtig groot met verloop van tyd. En so het ons 'n groot O. en Big O verteenwoordig iets wat ons gedink van so 'n bogrens. En eintlik, Barry, ons kan verlaag as die mikrofoon 'n bietjie? Ons het gedink dat van hierdie is 'n bogrens. So groot O van n vierkant beteken dat in die ergste geval, iets soos seleksie soort sou neem n 'vierkante stappe. Of iets soos voeg soort sou n vierkant stappe. Nou vir iets soos te voeg soort, wat was die ergste geval? Gegewe 'n skikking, wat is die ergste moontlike scenario wat jy kan vind jouself gekonfronteer met? Dit is heeltemal agteruit, reg? Want as dit is heeltemal agteruit, jy het 'n hele klomp van die werk te doen. Want as jy heeltemal agtertoe, jy gaan die te vind grootste element hier, selfs al dit behoort daar. So jy gaan om te sê, alles reg, by hierdie oomblik in tyd, kan jy hier hoort nie, sodat jy laat dit alleen. Dan besef jy, o, damn, ek het om te skuif dit effens kleiner element te links van jou. Dan moet ek dit weer te doen en weer en weer. En as ek loop heen en weer, moet jy sou soort van voel die prestasie van dat algoritme, want voortdurend is ek geskuifel almal anders in die verskeidenheid plek te maak vir dit. So wat is die ergste geval. In teenstelling - en dit was 'n fotonische lewe laaste keer - Ons het gesê dat voeg soort was 'n omega van wat? Wat is die beste geval loop tyd van die inplanting soort? So dit is eintlik n. Dit was die leë dat ons verlaat op die bord laaste tyd. En dit is omega van n, want hoekom? Wel, in die beste geval, wat is voeg soort gaan oorhandig word? Wel, 'n lys wat is heeltemal gesorteer reeds, minimale werk te doen. Maar wat is netjies oor te voeg soort is dat omdat dit begin hier en besluit, o, jy is die aantal een, jy behoort hier. O, wat 'n goeie geluk. Jy is die nommer twee. Jy kan ook hier hoort nie. Nommer drie, nog beter, jy hier hoort nie. Sodra dit raak tot aan die einde van die lys, per inplanting soort se pseudokode dat ons stap deur mondelings laaste keer, is dit gedoen. Maar seleksie soort, daarenteen, bly doen wat? Aan die gang gehou deur die lys weer en weer en weer. Omdat die sleutel insig was daar net sodra jy het al die pad na die einde van die lys kan jy seker wees dat die element wat jy gekies het, was inderdaad die oomblik kleinste element. So hierdie verskillende verstandelike modelle einde up opbrengs van 'n paar baie werklike wêreld verskille vir ons, sowel as dié teoretiese asimptotiese verskille. So net om te vat, dan, 'n groot O van n vierkantig, het ons gesien dat 'n paar sulke algoritmes tot dusver. Big O van n? Wat is 'n algoritme wat kon word gesê dat groot O van n? In die ergste geval, dit neem 'n lineêre aantal stappe. OK, lineêre soek. En in die ergste geval, waar is die element wat jy soek vir wanneer toepassing van lineêre soek? OK, in die ergste geval, dit is nie eens daar nie. Of in die tweede ergste geval, is dit al die pad in die einde, wat plus-of-minus 'n een-stap verskil. So aan die einde van die dag, Ons kan sê dit is lineêr. Big O van n sal lineêre soek wees, want in die ergste geval, die element is nie eens daar of is dit al die pad aan die einde. Wel, 'n groot O van log van n. Ons het nie gepraat in groot detail oor hierdie, maar ons het dit gesien voor. Wat loop in die sogenaamde logaritmiese tyd, in die ergste geval? Ja, so binêre soek. En binêre soek in die ergste geval kan die element iewers in 'n die middel, of iewers binne-in die skikking. Maar jy vind dit wanneer jy verdeel die lys in die helfte, in helfte, in die helfte, in die helfte. En dan voila, dit is daar. Of weer, die ergste geval, dit is nie eens daar nie. Maar jy weet nie dat dit nie daar totdat jy soort van bereik dat die laaste bottom-die meeste elemente by halveer en halveer en halveer. Big O van 1. Sodat ons kan groot O van 2, groot O van 3. Wanneer jy wil net 'n konstante getal, ons het net soort van net vereenvoudig dat so 'n groot O van 1. Selfs al as realisties, neem dit 2 of selfs 100 stappe, indien dit is 'n konstante aantal stappe, ons net sê groot O van 1. Wat is 'n algoritme wat in 'n groot O van 1? GEHOOR: Dit vind van die lengte van 'n veranderlike. David Malan: Dit vind van die lengte van 'n veranderlike? GEHOOR: Nee, die lengte As dit is reeds uitgesorteer. David Malan: Goed. OK, so vind die lengte van iets As die lengte van iets, soos 'n skikking, gestoor word in 'n veranderlike. Want jy kan net lees die veranderlike, of druk die veranderlike, of net oor die algemeen toegang tot daardie veranderlike. En siedaar, wat neem konstante tyd. In teenstelling hiermee, dink terug te krap. Dink terug aan die eerste week van C, bel net printf en druk iets op die skerm is waarskynlik konstante tyd, want dit neem net 'n aantal van die CPU siklusse aan te toon dat die teks op die skerm. Of wag - dit doen? Hoe anders kan ons model prestasie van printf? Sou iemand wil om te verskil, wat Miskien is dit is nie regtig 'n konstante tyd? In watter sin kan printf se loop tyd, eintlik die druk van 'n string op die skerm, iets anders as konstant. GEHOOR: [onhoorbaar]. David Malan: Ja. So dit hang af van ons perspektief. As ons dink eintlik van die insette te printf as die string, en Daarom het ons meet die grootte van daardie insette deur sy lengte - so kom ons noem dat lengte n so goed - waarskynlik, is printf self groot O van n want dit gaan jou n stappe te neem om uit te druk elk van die n karakters, waarskynlik. Ten minste tot die mate dat ons aanvaar dat miskien is dit die gebruik van 'n for-lus onder die kap. Maar ons sal moet kyk na wat Kode te verstaan ​​dit beter. En inderdaad, wanneer jy ouens begin ontleding van jou eie algoritmes, sal jy letterlik net dat doen. Soort van oogbal jou kode en dink - alles reg, ek het hierdie lus hier of ek 'n geneste lusse hier, wat gaan N Dinge n keer te doen, en jy kan sorteer rede om jou manier deur middel van die kode, selfs al is dit pseudokode en nie die werklike kode. So, wat oor omega van n vierkant? Wat was 'n algoritme wat in die beste geval, nog steeds het n vierkantige stappe? Ja? GEHOOR: [onhoorbaar]. David Malan: So seleksie soort. Want in daardie probleem werklik verminder aan die feit dat die weer, ek weet nie Ek het gevind dat die huidige kleinste tot Ek het bewys al die darn elemente. So omega van, sê, n, ons net vorendag gekom met een. Invoeging soort. As die lys gebeur word uitgesorteer reeds, in die beste geval het ons net Een Pass te maak deur dit, op watter punt ons is seker. En dan is dit kan gesê word om lineêre, vir seker. Wat van omega van 1? Wat, in die beste geval is, kan neem 'n konstante aantal stappe? So lineêre soek, as jy net kry gelukkig en die element wat jy soek reg aan die begin van die lys, As dit is waar jy die begin van jou lineêre traversal van die lys. En dit is waar van 'n aantal van die dinge. Byvoorbeeld, selfs binêre soek is omega van 1. Omdat wat as jy regtig darn gelukkig en smack-dab in die middel van jou skikking is die aantal jy soek? So kan jy gelukkig is daar, as well. Hierdie een, laastens, omega van n log n. So n log n, ons het nie regtig praat nie, maar - GEHOOR: Merge soort? David Malan: Merge soort. Dit was die fotonische lewe van verlede tyd, waar ons voorgestel het, en ons het visueel, dat daar algoritmes. En voeg soort van net een so 'n algoritme wat is fundamenteel vinniger as sommige van die ander ouens. Trouens, saam te smelt kort is nie net in die beste geval n log n, in die ergste geval n log n. En wanneer jy hierdie sameloop van omega en 'n groot O synde die dieselfde ding? Ons kan eintlik beskryf wat as wat is genoem theta, al is dit 'n bietjie minder algemeen. Maar dit beteken net die twee grense, in hierdie geval, is dieselfde. So saamsmelt soort, wat beteken dit regtig neer op vir ons? Wel, onthou die motivering. Laat my toe om 'n ander animasie wat ons het nie kyk na die laaste keer. Hierdie een is, dieselfde idee nie, maar dit is 'n bietjie groter. En ek gaan om voort te gaan en wys eerste - ons voeg soort op die top links, dan seleksie soort, borrel soort, 'n paar van die ander vorme - dop en vinnig - dat ons nie gepraat oor, en hoop en voeg soort. So ten minste probeer om jou oë te fokus op die top drie op die linker-en dan saamsmelt sorteer toe ek op Hierdie groen pyl. Maar ek sal laat almal van hulle loop, net om te gee jou 'n gevoel van die diversiteit van algoritmes wat bestaan ​​in die wêreld. Ek gaan hierdie termyn te laat net vir 'n paar sekondes. En as jy fokus jou oë - kies 'n algoritme, fokus op dit net vir 'n sekondes - jy sal begin om te sien patroon wat dit die implementering. Merge soort, kennisgewing, gedoen word. Hoop sorteer, vinnige soort, dop - so dit lyk asof ons het die drie ergste algoritmes verlede week. Maar dit is goed dat ons hier is vandag kyk na saamsmelt soort, wat een van die die wat makliker is, is om te kyk na, selfs hoewel dit waarskynlik sal buig jou gedagtes net 'n bietjie. Hier kan ons sien hoeveel seleksie soort suig. Maar aan die ander kant, is dit regtig maklik om te implementeer. En dalk ook vir P Stel 3, dit is een van die algoritmes jy verkies om te implementeer vir die standaard uitgawe. Heeltemal fyn, heeltemal korrek. Maar weereens, as n groot kry, as jy kies 'n vinniger algoritme te implementeer wil saamsmelt soort, is die kans in groter en groter insette, jou kode is net gaan om vinniger te hardloop. Jou webwerf gaan beter werk. Jou gebruikers gaan gelukkiger wees. En so is daar hierdie effekte van die werklikheid te gee ons 'n paar dieper gedink. So kom ons neem 'n blik op wat saamsmelt soort is eintlik alles oor. Die cool ding is dat saamsmelt soort is net hierdie. Dit is, weer, wat ons geroep pseudokode, pseudokode wese Engels-agtige sintaksis. En die eenvoud soort van fassinerend. So op die insette van n elemente - sodat beteken net, hier is 'n skikking. Dit het 'n dinge in dit. Dit is al wat ons daar is gesê. As n is minder as 2, terug te keer. So dit is net die triviale geval. As n is minder as 2, dan natuurlik is dit 1 of 0, in welke geval die ding is reeds gesorteer of nie bestaan ​​nie, sodat net terug te keer. Daar is niks om te doen. So dit is 'n eenvoudige saak te ruk af. Else, het ons drie stappe. Sorteer die linker helfte van die elemente, soort die reg om die helfte van die elemente, en dan saam te smelt die gesorteer helftes. Wat is interessant hier is dat Ek is soort van vaar, reg? Daar is 'n soort van 'n omsendbrief definisie hierdie algoritme. In watter sin is hierdie algoritme se definisie omsendbrief? GEHOOR: [onhoorbaar]. David Malan: Ja, my sorteringsalgoritme, twee van sy stappe is "soort iets "En. sodat lei tot die vraag, nou ja, ek wat ek gaan gebruik die linker helfte te sorteer en die reg om die helfte? En die skoonheid hier is dat selfs al weer, dit is die gedagte-buiging deel potensieel, kan jy gebruik dieselfde algoritme die linker helfte te sorteer. Maar wag 'n minuut. Wanneer jy aan die uit te sorteer linker helfte, wat is die twee stappe gaan volgende wees? Ons sal sorteer die linker helfte van die linker helfte en die reg helfte van die linker helfte. Damn, hoe kan ek sorteer die twee helftes of huisvesting, wat nou? Maar dit is OK. Ons het 'n sorteeralgoritme hier. En selfs al sou jy bekommerd wees op eerste van hierdie is 'n soort van 'n oneindige lus, dit is 'n siklus wat nooit gaan eindig - dit gaan eindig keer wat gebeur? Sodra n is minder as 2. Wat uiteindelik gaan gebeur, want as jy hou halveer en halveer in halveer hierdie helftes, sekerlik uiteindelik sal jy gaan aan die einde met net 1 of 0 elemente. By watter punt, hierdie algoritme sê jy klaar is. Dus is die werklike magie in hierdie algoritme blyk te wees in dat die finale stap, saam te smelt. Dat eenvoudige idee net samesmelting twee dinge, dit is wat uiteindelik gaan om voorsiening te maak vir ons 'n verskeidenheid van uit te sorteer, kom ons sê, agt elemente. So ek het agt meer stres balle hier, agt stukkies papier, en een Google Glass - wat ek kry om te hou. [Gelag] David Malan: As ons kon neem agt vrywilligers, en laat ons kyk of ons kan speel dit uit, so. Sjoe, OK. Rekenaarwetenskap is om pret. Alle regte. So hoe oor julle drie, grootste hand daar. Vier in die rug. En hoe oor ons sal doen wat jy drie in hierdie ry? En vier in die voorkant. So jy agt, kom op. [Gelag] David Malan: Ek is eintlik nie seker wat dit is. Is dit die stres balle? Die lessenaar lampe? Die materiaal? Die internet? OK. So kom op. Wie wil - hou kom. Kom ons kyk. En dit sit jy in plek - jy is in plek een. Uh-oh, wag 'n minuut. 1, 2, 3, 4, 5, 6, 7 - O, goed. Alle reg, ons is goed. Alle reg, sodat almal 'n sitplek, maar nie op die Google Glass. Laat my toe om te ry hierdie up. Wat is jou naam? MICHELLE: Michelle. David Malan: Michelle? Alle reg, jy lyk soos die geek, as dit is OK. Wel, ek doen ook, dink ek, vir net 'n oomblik. Alle reg, bystand. Ons het probeer om vorendag te kom met 'n gebruik geval vir Google Glass, en ons gedink dit sou pret wees om te doen net wanneer mense op die verhoog is. Ons sal rekord van die wêreld uit hulle perspektief. Alle regte. Nie seker watter Google bedoel is. Goed, as jy nie omgee nie dra dit vir die volgende ongemaklike minute, wat jou sal wonderlik wees. Alle reg, so ons het hier 'n verskeidenheid van elemente, en dat skikking, soos per die stukkies papier in hierdie mense se hande, is tans ongesorteerde. MICHELLE: O, dis so weird. David Malan: Dit is nogal baie random. En in 'n oomblik, gaan ons om te probeer te implementeer saamsmelt soort saam en sien dat die sleutel insig is. En die truuk hier met saamsmelt soort is iets wat ons nie aanvaar nie. Ons het eintlik 'n paar addisionele ruimte. So, wat gaan wees veral interessant oor hierdie is dat hierdie ouens gaan om rond te beweeg 'n bietjie bietjie, want ek gaan om te aanvaar dat daar is 'n ekstra verskeidenheid van ruimte, sê, reg agter hulle. So as hulle agter hul stoel, dit is die sekondêre skikking. As hulle hier sit, is dit die primêre skikking. Maar dit is 'n bron wat ons het nie benut tot dusver met borrel soort, met seleksie soort, met inplaas van aard. Onthou verlede week, almal net soort skuifel in plek. Hulle het nie die gebruik van enige addisionele geheue. Ons het ruimte vir mense deur beweeg mense rond. So, dit is 'n belangrike insig, ook. Daar is hierdie trade-off, in die algemeen in rekenaarwetenskap, van hulpbronne. As jy wil te bespoedig iets soos die tyd, gaan jy het 'n prys te betaal. En een van die pryse is baie dikwels ruimte, die bedrag van die geheue of hard spasie op die hardeskyf wat jy gebruik. Of, eerlik, die bedrag van programmeerder tyd. Hoeveel tyd wat dit neem om jou, die menslike, om werklik te implementeer 'n paar meer ingewikkelde algoritme. Maar vir vandag, die trade-off 'n tyd en ruimte. So as jy ouens kan net hou jou nommers sodat ons kan sien dat jy inderdaad ooreenstem met 4, 2, 6, 1, 3, 7, 8. Uitstekend. So ek gaan om te probeer om te orkestreer dinge, as jy ouens kan net volg my lei hier. So ek gaan om te implementeer, die eerste, die eerste stap van die pseudokode, wat op insette van n elemente, as n minder as 2, dan terug. Dit is duidelik dat, wat nie van toepassing is, sodat ons beweeg aan. So sorteer die linker helfte van die elemente. Dus beteken dit dat ek gaan om te fokus my aandag vir 'n oomblik op hierdie vier ouens hier. Alle reg, doen wat ek doen? GEHOOR: sorteer die linker helfte. David Malan: So nou het ek te sorteer die linker helfte van hierdie ouens. Omdat weer, neem vir jouself die doel is om die linker helfte te sorteer. Hoe doen jy dit? Volg net die instruksies, selfs maar ons doen dit weer. So sorteer die linker helfte. Nou is ek sorteer hierdie twee ouens. Wat kom volgende? GEHOOR: sorteer die linker helfte. David Malan: sorteer die linker helfte. So nou hierdie, die setel hier, is 'n lys van die grootte 1. En wat is jou naam nou weer? PRINCESS DAISY: Princess Daisy. David Malan: Princess Daisy is hier. En so het sy reeds gesorteer is, omdat die lys is van die grootte 1. Wat moet ek nou doen nie? OK, terug te keer nie, want die lys is van grootte 1, wat minder is as 2. Dan wat is die volgende stap? En nou moet jy soort backtracks in jou gedagtes. Sorteer die regter helfte, wat - Wat is jou naam? LINDA: Linda. David Malan: Linda. En so wat doen ons nou dat Ons het 'n lys van die grootte 1? GEHOOR: Terug. David Malan: versigtig wees. Ons keer terug eerste, en nou is die derde stap - en as ek soort van beeld dit deur die aanvaarding van die twee sitplekke nou, nou is ek het hierdie twee elemente saam te voeg. So nou ongelukkig die elemente buite werking is. Maar dit is waar die samesmelting proses begin om dwingende. So as jy ouens kan opstaan ​​vir net 'n oomblik, ek gaan jou nodig het, in 'n oomblik te stap agter jou stoel. En as Linda, want 2 is kleiner as 4 is, hoekom dit nie doen nie jy kom om eerste? Daar bly. So Linda, jy kom om die eerste. Nou in werklikheid is dit net 'n skikking Ons kan net beweeg haar in reële tyd uit hierdie stoel by hierdie plek. So dink wat het 'n paar konstante aantal stappe 1. En nou - maar ons het jou nodig om te sit in die eerste plek hier. En nou as jy kon kom rond, sowel, gaan ons wees in plek twee. En selfs al is dit voel soos dit is neem 'n rukkie, wat is nice is nou dat die linker helfte van die linker helfte is nou gesorteer. So wat was die volgende stap, as ons nou rewind verder in die storie? GEHOOR: Right helfte. David Malan: sorteer die reg om die helfte. So julle ouens het dit te doen, as well. So as jy kan opstaan net vir 'n oomblik? En wat is jou naam? JESS: Jess. David Malan: Jess. OK, so Jess is nou die linker helfte van die reg om die helfte. En so sy is 'n lys van die grootte 1. Sy is natuurlik gesorteer. En jou naam nou weer? MICHELLE: Michelle. David Malan: Michelle is natuurlik 'n lys van die grootte 1. Sy is reeds uitgesorteer. So nou is die magic gebeur, die samesmelting proses. So wie gaan eerste kom? Dit is duidelik dat Michelle. So as jy kan kom om terug te. Die ruimte wat ons beskikbaar het nou vir haar is reg agter die stoel hier. En nou as jy kan terug kom so goed, ons het nou, duidelik te wees, twee helftes, elk van grootte 2 - en net vir die uitbeelding se ontwil, as jy kan 'n bietjie van 'n ruimte - een links half hier, die een reg half hier. Rewind verder in die storie. Wat stap is volgende? Gehoor deur saam te smelt. David Malan: So nou het ons om saam te smelt. So OK, so nou, gelukkig, ons net bevry vier stoele. So het ons twee keer gebruik soveel geheue, maar ons kan flip-uittrek gee tussen Die twee skikkings. So watter getal is om eerste te kom? So Michelle, natuurlik. So kom rond en neem jou plek hier. En dan is nommer 2 is natuurlik volgende, so jy hier kom. Nommer 4, nommer 6. En weer, selfs al is daar 'n bietjie van die loop betrokke is, regtig, kan hierdie onmiddellik gebeur nie, deur die beweging van een - OK, goed gespeel. [Gelag] David Malan: En nou is ons in redelik goeie vorm. Die linker helfte van die hele insette is nou gesorteer. Alle reg, sodat hierdie ouens gehad die voordeel van my - hoe het dit uiteindelik al die meisies op die links en al die seuns van die reg? OK, so ouens "Nou draai. So ek sal nie loop jy deur hierdie stappe. Ons sal kyk of ons kan weer aansoek doen dieselfde pseudokode. As jy wil om voort te gaan en te staan, en julle, laat my gee u die mic. Sien as jy nie kan herhaal wat Ons het net hier op die ander einde van die lys. Wie het dit nodig om eerste te praat, gebaseer op die algoritme? So verduidelik wat jy doen voordat jy maak 'n voet bewegings. Spreker 1: Alle reg, so sedert Ek is die linker helfte van die linker helfte, het ek terug. Reg? David Malan: Goed. Spreker 1: En dan - David Malan: Wie doen die mikrofoon gaan na die volgende? Spreker 1: Volgende nommer. Spreker 2: So ek is die regter helfte van die linker helfte van die linker helfte, en ek terugkeer. David Malan: Goed. Jy terugkeer. So nou wat is die volgende vir julle twee? Spreker 2: Ons wil sien wie is kleiner. David Malan: Presies. Ons wil hê om saam te smelt. Die ruimte wat ons gaan gebruik om saam te smelt julle in, selfs al is hulle natuurlik gesorteer reeds, ons gaan dieselfde algoritme te volg. So wat gaan in die rug eerste? So 3, en dan 7. En nou het die mic gaan om hierdie ouens, OK? SPREKER 3: So ek is die regter helfte van die linker helfte, en my n minder is as 1, so ek gaan net om te slaag - David Malan: Goed. SPREKER 4: Ek is die reg om die helfte van die regter helfte van die reg om die helfte, en ek is ook een persoon, so ek is gaan om terug te keer. So nou het ons saam te smelt. SPREKER 3: So gaan ons terug. David Malan: So jy gaan in die rug. So 5 gaan die eerste, dan 8. En nou het gehoor, wat is die stap ons nou rewind terug in ons gedagtes? Gehoor deur saam te smelt. David Malan: Kombineer linker helfte en regs helfte van die oorspronklike linker helfte. So nou - en net om dit duidelik maak, 'n bietjie van die ruimte tussen julle twee ouens. So nou is dit die twee lyste links en regs. So hoe ons saam te smelt nou nie julle ouens in die voorste ry sitplekke weer? 3 gaan eerste. Dan 5, natuurlik. Dan 7, en nou 8. OK, en nou is ons? Publiek: nie gedoen nie. David Malan: Nie gedoen nie, want natuurlik, daar is 'n stap in die jaar. Maar weereens, die rede waarom ek die gebruik van hierdie jargon soos "rewind in jou gedagtes," dit is omdat dit is regtig wat gebeur. Ons gaan deur al hierdie stappe maar ons is soort van pousering vir 'n oomblik, duik dieper in die algoritme, pousering vir 'n oomblik, duik dieper in die algoritme, en nou het ons te sorteer van rewind in ons gedagtes en ongedaan te maak al hierdie lae dat ons het soort van op te hou. So nou het ons twee lyste van grootte 4. As jy ouens kan staan ​​vir oulaas en maak 'n bietjie van die ruimte hier te duidelik maak dat dit die linker helfte van die oorspronklike, die regter helfte van die oorspronklike. Wie is die eerste getal wat ons nodig het om te trek in die rug? Michelle, natuurlik. So sit ons Michelle hier. En wie het nommer 2? Nommer 2 kom op die rug as well. Nommer 3? Uitstekend. Nommer 4, nommer 5, nommer 6, nommer 7, en die getal 8. OK, so dit voel soos 'n baie stappe, vir seker. Maar laat ons kyk of ons kan dit nie bevestig soort van intuïtief dat hierdie algoritme fundamenteel, veral as n regtig groot, soos ons gesien het met die animasies, is fundamenteel vinniger. So ek beweer hierdie algoritme, in die ergste geval en selfs in die beste geval, is 'n groot O van n keer log n. Dit is, daar is 'n aspek van hierdie algoritme wat neem n stappe, maar daar is 'n ander aspek iewers in dat iterasie, wat herhaling, wat neem log n stappe. Kan ons ons vinger op wat daardie twee getalle word verwys na? Wel, waar - Waar kom die mikrofoon gaan? Spreker 1: Sou die teken wees n breek ons ​​in twee - deel deur twee, in wese. David Malan: Presies. Enige tyd wat ons sien in 'n algoritme dus ver, is daar 'hierdie patroon van verdeel, verdeel, te verdeel. En dit is tipies verminder na iets wat logaritmiese, log basis 2. Maar dit kan regtig enigiets, maar teken basis 2. Nou wat van die n? Ek kan sien dat ons soort van verdeel jy ouens - verdeel jou, verdeel jy, verdeel jy gedeel het. Waar kom die einde kom? So dit is die samesmelting. Want daaroor dink. Wanneer jy voeg agt mense bymekaar, waardeur die helfte van hulle is 'n stel van vier en die ander helfte is 'n ander stel van vier, hoe kan jy gaan oor die doen van die samesmelting? Wel, julle het dit redelik intuïtief. Maar as ek in plaas daarvan het dit 'n bietjie meer metodies, kan ek uitgewys het op die linker persoon eers met my linkerhand hand, wys na die linker persoon van dat die helfte met my regterhand, en net daarna het, deur die lys, wat dui op die kleinste element elke keer, beweeg my vinger oor en meer as wat nodig is deur die lys. Maar wat is die sleutel oor hierdie samesmelting proses is ek hierdie pare is vergelyk van elemente. Van die regter helfte en van links half, ek het nooit een keer back tracking. So het die samesmelting self neem nie meer as n stappe. En hoeveel keer het ek om dit te doen samesmelting? Wel, nie meer as n, en ons het net sien dat met die finale saamsmelt. En so, as jy iets doen wat neem teken n stappe n keer, of andersom, dit gaan om te gee ons n keer log n. En hoekom is dit beter? Wel, as ons reeds weet dat log n is beter as n - reg? Ons het in binêre soek, die telefoon boek Byvoorbeeld, log n was beslis beter as lineêre. Dus beteken dit dat n keer log n is beslis beter as n keer 'n ander n, AKA n vierkant. En dit is wat ons uiteindelik voel. So groot applous, indien ons kon nie, want hierdie ouens. [Applous] David Malan, en julle afskeid geskenke - jy mag die getalle, as jy wil. En jou afskeidsgeskenk, soos gewoonlik. O ja, en ons sal jou die beeldmateriaal, Michelle. Dankie. Alle regte. Help jouself om 'n stress bal. En laat my trek, in die tussentyd, ons vriend Rob Bowden aan te bied ietwat ander perspektief op hierdie, want jy kan dink oor hierdie stappe gebeur in 'n ietwat ander manier. Trouens, die set-up vir dit wat Rob is oor om ons te wys aanvaar dat ons reeds gedoen het die verdeling van die groot lys in agt klein lyste, elk van grootte 1. So ons is besig om die pseudokode 'n bietjie net om te sorteer van kry by die kern idee van hoe die samesmelting van werke. Maar die loop van die tyd wat hy is om te doen, is nog steeds gaan dieselfde wees. En weer, die set-up hier is dat hy begin met agt lyste van grootte 1. So jy het gemis die deel waar hy is eintlik gedoen die puntelys n, log n, log n verdeling van die insette. [Video speel] -Dit is dit vir stap een. Vir stap twee, herhaaldelik saamsmelt pare lyste. David Malan: Hm. Slegs klank kom uit my rekenaar. Kom ons probeer dit weer. -Net arbitrêr kies wat - Nou het ons vier lyste. Leer voor. David Malan: Daar gaan ons. -Kombineer 108 en 15, het ons uiteindelik met die lys 15, 108. Samesmelting 50 en 4, wat ons eindig met 4, 50. Samesmelting 8 en 42, het ons eindig met 8, 42. En die samesmelting van 23 en 16, het ons eindig met 16, 23. Nou al ons lyste van grootte 2. Let daarop dat elk van die vier lyste gesorteer is. Sodat ons kan begin samesmelting pare lyste weer. Samesmelting 15 en 108 en 4 en 50, het ons eers die 4, dan is die 15, dan die 50, dan is die 108. Samesmelting 8, 42 en 16, 23, het ons vir die eerste maal die 8, dan is die 16, dan is die 23, dan is die 42. So nou het ons net twee lyste van grootte 4, is elk van wat gesorteer. So nou het ons saam te smelt die twee lyste. Eerstens, neem ons die 4, dan neem ons die 8, dan neem ons die 15, dan 16, dan 23, dan 42, dan 50, dan 108. [Einde video-vertoning] David Malan: Weereens, kennisgewing, het hy nooit raak 'n gegewe koppie meer as een keer na die bevordering van buite dit. So het hy nog nooit herhaal. So hy is altyd beweeg aan die kant, en dit is waar ons ons n. Waarom nie laat my trek een animasie dat ons vroeër gesien het, maar hierdie keer fokus net op saamsmelt soort. Laat my gaan voort en vergroot op hierdie hier. Eerste laat my kies 'n ewekansige insette, vergroot dit, en jy kan sorteer sien wat ons as vanselfsprekend aanvaar het, Vroeër, saam te smelt soort is eintlik doen. So sien dat jy hierdie helftes of hierdie oorde of hierdie agstes van die probleem wat al van 'n skielike begin 'n goeie vorm te neem. En dan uiteindelik, wat jy sien by die einde wat bam, alles saam saamgesmelt. So dit is net drie verskillende neem op dieselfde idee. Maar die sleutel insig, net soos kloof en verower in die heel eerste klas, was dat ons besluit het om een ​​of ander manier verdeel die probleem in iets groot, in iets soort van identiese in gees, maar kleiner en kleiner en kleiner. Nou 'n ander prettige manier om uit te sorteer dink hieroor, selfs al is dit nie gaan vir jou dieselfde intuïtief begrip, is die volgende animasie. So dit is 'n video iemand saam te stel wat verband hou verskillende klanke met die verskillende bedrywighede vir voeg soort, vir saamsmelt soort, en vir 'n paar van die ander. So in 'n oomblik, ek gaan speel om te tref. Dit gaan oor 'n minuut lank. En selfs al is jy kan nog steeds die patrone gebeur, hierdie tyd wat jy kan ook hoor hoe hierdie algoritmes uitvoering anders en met ietwat verskillende patrone. Dit is te voeg soort. [Toon SPEEL] David Malan: Dit is weer probeer elke element te voeg in waar dit hoort. Dit is borrel soort. [Toon SPEEL] David Malan: En jy kan soort van gevoel hoe relatief min werk dit doen op elke stap. Dit is wat die eentonigheid klink. [Toon SPEEL] David Malan: Dit is seleksie soort, waar ons kies die element wat ons wil deur gaan deur weer en weer en weer en sit dit aan die begin. [Toon SPEEL] David Malan: Dit is saamsmelt soort, wat kan jy regtig begin om te voel. [Toon SPEEL] [Gelag] David Malan: Iets wat genoem gnome soort, wat ons nog nie gekyk het nie. [Toon SPEEL] David Malan: So laat ek sien, nou, afgelei as jy hopelik is deur die musiek, as ek 'n bietjie kan glip bietjie van wiskunde in hier. So is daar 'n vierde manier wat ons kan dink oor wat dit beteken om hierdie funksies om vinniger as kinders wees dat ons nog nooit gesien. En as jy kom by die kursus uit 'n wiskunde-agtergrond, wat jy eintlik miskien reeds weet dat jy kan 'n term wat klap op hierdie tegniek - naamlik rekursie, 'n funksie wat doen 'n beroep op 'n manier self. En weer, onthou dat saamsmelt soort pseudokode was rekursiewe in die sin dat een van saamsmelt soort se stappe was soort te noem - dit is, is self. Maar gelukkig, want ons het roep soort, of saam te smelt soort, spesifiek, op 'n kleiner en kleiner en kleiner lys, het ons uiteindelik onderste draaipunt bereik het danksy wat ons bel 'n basis geval, die hard-gekodeerde geval dat het gesê dat indien die lys is 'n klein, minder as 2 In daardie geval, net dadelik terug te keer. As ons nie gehad het dat die spesiale geval, die algoritme sou nooit onder uit, en jy sal wel kry in 'n oneindige lus werklik vir ewig. Maar veronderstel dat ons wou nou sit 'n paar nommers op hierdie, weer, met behulp van n as die grootte van die insette. En ek wou jou vra, wat is die totale tyd wat betrokke is in hardloop saamsmelt soort? Of meer in die algemeen, wat is die koste van dit in die tyd? Wel, dit is redelik maklik om dit te meet. As n is minder as 2, die tyd wat betrokke is in sortering n elemente, waar n 2, is 0. Omdat ons net terug te keer. Daar is geen werk wat gedoen moet word. Nou waarskynlik, miskien is dit 'n stap of twee stappe om uit te vind die bedrag van werk nie, maar dit is naby genoeg aan 0 wat Ek is net gaan om te sê geen werk is vereis indien die lys is so klein word oninteressant. Maar hierdie geval is interessant. Die rekursiewe geval was die tak van die pseudokode wat sê anders, soort die linker helfte, sorteer die regte helfte, saam te smelt die twee helftes. Nou hoekom het hierdie uitdrukking stel dat die koste? Wel, T van n beteken net die tyd n elemente uit te sorteer. En dan op die regterkant van die gelyk teken is, is die T van n verdeelde deur 2 verwys na die koste van wat? Sorteer die linker helfte. Die ander T van n gedeel deur 2 is vermoedelik verwys na die koste te sorteer die reg om die helfte. En dan is die plus n? Is die samesmelting. Want as jy twee lyste, een van grootte n meer as 2 en 'n ander van grootte n meer as 2, wat jy hoef te raak in wese elk van die elemente, net soos Rob aangeraak elk van die koppies, en net Soos ons by elk van die vrywilligers op die verhoog. So n is die koste van die samesmelting. Nou ongelukkig, hierdie formule is ook self rekursiewe. So as die vraag gevra het, vir n ', sê, 16, indien daar is 16 mense op die verhoog of 16 koppies in die video, hoeveel totale stappe neem dit om hulle te sorteer met saamsmelt soort? Dit is eintlik nie 'n duidelike antwoord, want nou het jy te sorteer rekursief beantwoord hierdie formule. Maar dis OK, want laat my stel dat ons die volgende doen. Die tyd wat betrokke is 16 mense uit te sorteer of 16 koppies gaan word verteenwoordig algemeen as T van 16. Maar dit is gelyk aan, volgens ons vorige formule, 2 keer die bedrag van die tyd wat dit neem om te sorteer 8 koppies plus 16. En weer, plus 16 is die tyd om saam te smelt, en die twee keer T van 8 is die tyd links en regs helfte helfte te sorteer. Maar weereens, dit is nie genoeg nie. Ons het om te duik in dieper. Dit beteken dat ons die antwoord vraag, wat is T van 8? Wel T van 8 is net 2 tye T van 4 plus 8. Wel, wat is T van 4? T van 4 is net 2 keer T van 2 plus 4. Wel, wat is T van 2? T van 2 is net 2 keer T van 1 en 2. En weer, ons is soort van kry vas in hierdie siklus. Maar dit is oor te slaan wat sogenaamde basis geval. Want wat is T van 1, het ons beweer? 0. So nou uiteindelik, kan ons terug werk. As T van 1 is 0, kan ek nou gaan terug tot een lyn na hierdie man hier, en ek kan plug in 0 vir T van 1. So dit beteken dat dit gelyk is aan 2 keer nul, andersins bekend as 0, plus 2. En so dat die hele uitdrukking is 2. Nou as ek die T van 2, wie se antwoord is 2, prop dit in die middel lyn, T 4, wat gee my 2 keer 2 plus 4, so 8. As ek dan prop in 8 na die vorige lyn, wat gee my 2 keer 8, 16. En as ons dan voortgaan om met die 24, en voeg in 16, het ons uiteindelik 'n waarde van 64. Nou dat in en van die self soort van praat niks aan die n notering, die Big O, die omega wat ons het gepraat oor. Maar dit blyk dat die 64 wel 16, die grootte van die insette, teken basis 2 van 16. En as dit is 'n bietjie vreemd, net dink terug, en dit sal kom terug aan jou uiteindelik. As dit is log basis 2, is dit soos 2 geopper word, te die wat gee jou 16? O, dit is 4, so dit is 16 keer 4. En weer, dit is nie 'n groot deal as dit is 'n soort van 'n vae herinnering nou. Maar vir nou, neem oor geloof dat 16 log 16 is 64. En so ja, met hierdie eenvoudige gesonde verstand kyk, het ons bevestig - maar nie bewys formeel - dat die loop van die tyd van saamsmelt soort is inderdaad 'n teken n. So nie sleg nie. Dit is beslis beter as die algoritmes wat ons tot dusver gesien het, en dit is, want ons het aged, een, 'n tegniek genoem rekursie. Maar meer interessant as dit, wat idee van verdeling en verower. Weereens, werklik week 0 dinge wat Selfs nou is herhalende in 'n meer dwingende manier. Nou 'n prettige min oefening, as jy het nog nooit dit gedoen - en jy sal waarskynlik wil nie hê, want soort van normale mense dink nie dit te doen. Maar as ek gaan na google.com en as Ek wil iets om te leer rekursie, Tik. [Gelag] [MEER Gelag] David Malan: slegte grap stadig versprei. [Gelag] David Malan: Slegs in die geval is, is dit daar. Ek het nie spel dit verkeerd is, en daar is die grap. Alle regte. Verduidelik dit aan die mense langs jou as dit het nog nie gekliek net nog nie. Maar rekursie, meer in die algemeen, verwys om die proses van 'n funksie roep self, of meer algemeen, die verdeling van 'n probleem in iets wat kan wees opgelos sporadies deur die oplossing van identiese verteenwoordiger probleme. Wel, laat ons wisselratte vir net 'n oomblik. Ons wil eindig op sekere cliffhangers, so laat ons begin te stel die stadium vir 'n paar minute, op 'n baie eenvoudige idee - dié van die uitruiling van twee elemente, reg? Al hierdie algoritmes ons het al praat oor die afgelope paar lesings behels 'n soort van uitruiling. Vandag is dit gesien word deur hulle kry uit hul stoele en rond te loop nie, maar in die kode, sou ons neem net 'n element van die een reeks en plop dit in 'n ander. So, hoe ons te werk gaan om dit te doen? Wel, laat ek gaan voort en skryf 'n vinnige program hier. Ek gaan om voort te gaan en te doen dit as die volgende. Kom ons noem dit - Wat wil ons doen om hierdie een te noem? Eintlik nie. Laat my rewind. Ek wil nie hê om dit te doen fotonische lewe nog. Dit sal bederf die pret. Kom ons doen dit eerder. Dink dat ek wil 'n bietjie te skryf program en wat behels nou hierdie idee van rekursie. Ek soort van het voor my daar. Ek gaan die volgende te doen. Eerstens, 'n vinnige sluit van standaard io.h, sowel as 'n sluit van cs50.h. En dan gaan ek om voort te gaan en verklaar int main leemte in die gewone manier. Ek het besef dat ek die lêer Verkeerd benoem, so laat my net voeg 'n C-uitbreiding. hier so dat ons kan stel dit behoorlik. Begin hierdie funksie af. En die funksie wat ek wil skryf, heel eenvoudig, is een wat vra die gebruiker vir 'n aantal en dan voeg tot al die getalle tussen wat nommer en, sê, 0. So eerste ek gaan om voort te gaan en verklaar int n. Toe het ek kopieer die kode wat wat ons gebruik het vir 'n rukkie. Terwyl iets waar is. Ek sal terug te kom na wat in 'n oomblik. Wat wil ek doen? Ek wil om te sê printf positiewe integer asseblief. En dan gaan ek sê n kry kry int. So weer, 'n paar boiler-kode dat ons al voorheen gebruik. En ek gaan om dit te doen terwyl n is minder as 1. So dit sal verseker dat die gebruiker gee my 'n positiewe heelgetal. En nou gaan ek die volgende te doen. Ek wil toe te voeg tot al die nommers tussen 1 en en N, of 0 en n, anders gestel, te kry om die totale bedrag. So die groot Sigma simbool wat jy kan onthou. So ek gaan om dit te doen deur die eerste roeping 'n funksie genoem Sigma, om dit in n, en dan gaan ek sê printf, die antwoord is reg daar. Dus, in kort, ek kry en int van die gebruiker. Ek verseker dit is positief. Ek verklaar 'n veranderlike genaamd antwoord tipe int en stoor in dit die terugkeer waarde van Sigma, verby in n as insette. En dan het ek druk die antwoord. Ongelukkig, selfs al Sigma klink soos iets wat kan wees in die math.h lêer, die verklaring, dit is eintlik nie. So dit is OK. Ek kan die uitvoering van hierdie myself. Ek gaan 'n funksie genoem te implementeer Sigma, en dit gaan 'n te neem parameter - Kom ons noem dit m, net dus is dit anders. En dan is hier, ek gaan om te sê, Wel, as m is minder as 1 - dit is 'n baie oninteressant program. So ek gaan om voort te gaan en onmiddellik terugkeer 0. Dit is net nie sin maak om op te tel al die nommers tussen 1 en m as m self 0 of negatief. En dan gaan ek om voort te gaan en doen dit baie iteratief. Ek gaan hierdie soort van die ou-skool te doen, en ek gaan om voort te gaan en sê dat ek gaan verklaar 'n bedrag aan 0 wees nie. Toe ek gaan te hê 'n lus vir die van int - en laat my dit doen ons aan te pas verspreiding kode, sodat jy het 'n afskrif by die huis. Int ek kry 1 op tot Ek is minder as of gelyk aan m. i plus plus. En dan binnekant van die for-lus - Ons is amper daar - som kry som plus 1. En dan gaan ek die som om terug te keer. So ek het dit vinnig nogal weliswaar. Maar weereens, die belangrikste funksie is redelik eenvoudige, gebaseer op kode wat ons het geskryf dusver. Gebruik van die dubbele lus om 'n positiewe te kry int van die gebruiker. Ek het toe gebeur dat int na 'n nuwe funksie sigma genoem, noem dit, weer, n. En ek slaan die terugkeer waarde, is die antwoord van die swart boks tans bekend as Sigma, in 'n veranderlike genoem antwoord. Dan druk ek dit. As ons nou voortgaan om die storie, hoe word Sigma geïmplementeer? Ek stel voor om te implementeer as volg. Eerstens, 'n bietjie van die fout kontrole om seker te maak dat die gebruiker nie ' geknoei met my en verby in 'n paar negatiewe of 0 waarde. Toe ek verklaar 'n veranderlike genoem som en sit dit aan 0. En nou het ek begin om te beweeg van i gelyk 1 al die pad tot en met m, want ek wil al die te sluit getalle van een deur m, ingesluit. En binnekant van die for-lus, het ek net doen som kry wat dit nou is, plus die waarde van i. Plus die waarde van i. As 'n eenkant, as jy nie gesien het nie hierdie voor, daar is 'n paar sintaktiese suiker vir hierdie lyn. Ek kan herskryf dit as plus gelyk aan i, net om te red myself 'n paar toetsaanslagen en 'n bietjie koeler te kyk. Maar dis al. Dit is funksioneel dieselfde ding. Ongelukkig is hierdie kode se nie van plan om nog saam te stel. As ek loop maak Sigma 0, hoe is Ek gaan om te skree? Wat gaan dit nie hou nie? GEHOOR: [onhoorbaar]. David Malan: Ja, ek het nie verklaar die funksie tot bo, reg? C is 'n soort van dom, in dat dit net doen wat jy vertel om dit te doen, en jy het om dit te doen in daardie volgorde. En so as ek getref Tik hier, ek gaan kry 'n waarskuwing oor Sigma implisiete verklaring. O ja, nie 'n probleem nie. Ek kan gaan na die top, en ek kan sê, alles reg, wag 'n minuut. Sigma is 'n funksie wat terugkeer 'n int en verwag om 'n int as insette, kommapunt. Of ek kon die hele funksie bogenoemde hoof, maar in die algemeen, ek wil beveel teen daardie, want dit is lekker om altyd hoof by die top so jy kan reg duik en weet wat 'n program doen deur die lees van die eerste hoof. So nou laat my duidelik die skerm. Remake Sigma 0. Al lyk te sien. Laat my toe hardloop Sigma 0. Positiewe inter. Ek sal dit gee die aantal 3 om te hou dit eenvoudig. So wat gee my 3 plus 2 plus 1, so 6. Betree, en ja, ek kry 6. Ek kan iets groter - 50, 12, 75. Net soos 'n raaklyn, ek gaan om dit te doen iets belaglik soos 'n baie groot nommer, O, wat eintlik gewerk het - eh, ek dink nie dit is reg. Kom ons kyk. Kom ons regtig gemors met dit. Dit is 'n probleem. Wat gaan aan? Die kode is nie so sleg nie. Dit is nog steeds lineêre. Fluit is 'n goeie effek, al is. Wat gaan aan? Nie seker of ek dit hoor. So dit blyk uit - en Dit is as 'n eenkant. Dit is nie die kern van die idee van rekursie. Dit blyk uit, want ek probeer stel so 'n groot aantal, die meeste waarskynlik dit is wat verkeerd deur C as 'n positiewe getal nie, maar negatiewe getal. Ons het nie gepraat oor hierdie, maar dit blyk daar is negatiewe getalle in die wêreld, benewens om positiewe nommers. En die wyse waarop jy kan verteenwoordig 'n negatiewe getal wese is, kan jy gebruik maak van een spesiale bietjie aan te dui positief oor die negatiewe. Dit is 'n bietjie meer kompleks as dit, maar dit is die basiese idee. So ongelukkig, as C is verwarrend een van daardie stukkies as eintlik beteken, O ja, dit is 'n negatiewe getal, my lus hier, byvoorbeeld, is eintlik nooit gaan beëindig. So as ek was eintlik die druk van iets weer en weer, sou ons sien 'n hele klomp. Maar weereens, dit is behalwe die punt. Dit is regtig net 'n soort intellektuele nuuskierigheid wat ons sal kom uiteindelik weer aan. Maar vir nou, is dit 'n korrekte implementering as ons aanvaar dat die gebruiker sal ints wat pas binne ints. Maar ek beweer dat hierdie kode, eerlik, kon word soveel meer eenvoudig gedoen. As die doel by die hand is 'n aantal te neem soos m en voeg aan al die getalle tussen dit en 1, of omgekeerd tussen 1 en dit, ek eis dat ek kan leen hierdie idee dat saamsmelt soort het, wat 'n probleem is die neem van van hierdie grootte en dit te verdeel in iets kleiner. Miskien nie die helfte, maar kleiner, maar verteenwoordigend dieselfde. Dieselfde idee, maar 'n kleiner probleem. So ek is eintlik - laat my red hierdie lêer met 'n ander weergawe nommer. Ons sal noem hierdie weergawe 1 in plaas van 0. En ek sê dat ek eintlik kan reimplement dit in hierdie soort van gedagte-buiging manier. Ek gaan 'n deel daarvan uit te los. Ek gaan om te sê as m is minder as of selfs gelyk aan 0 - Ek gaan net 'n bietjie meer anale hierdie tyd met my foutkontroles - Ek gaan om voort te gaan en 0 terugkeer. Dit is arbitrêr. Ek is eenvoudig net te besluit of die gebruiker gee my 'n negatiewe getal, is ek terugkeer 0, en hulle moet lees die dokumentasie nader. Else - sien wat ek gaan doen. Anders gaan ek m plus om terug te keer - Wat is Sigma van m? Wel, Sigma van m plus m minus 1, plus minus 2 m, plus minus 3 m. Ek wil nie al wat uit te skryf. Hoekom het ek nie net punt? Rekursief noem ek myself met 'n effens kleiner probleem, kommapunt, en noem dit 'n dag? Reg? Nou ook hier is, kan jy voel of bekommerd dat dit 'n oneindige lus dat ek induserende, waardeur ek die implementering Sigma deur roeping Sigma. Maar dit is heeltemal OK, want ek gedink het voor 'n bykomende wat lyne? GEHOOR: [onhoorbaar]. David Malan 23 tot 26, wat is my indien toestand. Want wat is lekker om oor die aftrek hier, want ek bewaar oorhandig Sigma kleiner probleme, kleiner probleme, kleiner - dit is nie helfte van die grootte. Dit is net 'n baba stap kleiner, maar dis OK. Omdat uiteindelik, sal ons werk ons pad af na 1 of 0. En wanneer ons getref het 0, Sigma is nie gaan om homself meer te noem. Dit gaan dadelik terug te keer 0. So het die effek, as jy soort van wind hierdie up in jou gedagtes, is m plus by te voeg m minus 1, plus minus 2 m, plus m minus 3, plus dot, dot, dot, m minus m, en uiteindelik gee jy 0, en die effek is uiteindelik al te voeg hierdie dinge saam. So ons het nie, met rekursie, die probleem opgelos dat ons kon nie los voor. Inderdaad, weergawe 0 van hierdie, en elke probleem tot op datum, is opgelos met net die gebruik vir sirkelroetes of terwyl sirkelroetes of soortgelyke konstrukte. Maar rekursie, het ek daresay, gee ons 'n ander manier van dink oor probleme, waardeur as ons kan neem om 'n probleem, verdeel dit uit iets bietjie groot in iets ietwat kleiner, Ek eis dat ons dit kan oplos miskien 'n bietjie meer elegant in terme van die ontwerp, met minder kode, en dalk selfs probleme op te los wat sou moeiliker wees, as ons uiteindelik sien, die belangrikheid van suiwer iteratief. Maar die fotonische lewe wat ek gedoen het ons wil verlaat het, was dit. Laat my gaan voort en oop 'n lêer van - eintlik, laat my gaan en doen dit baie vinnig. Laat my gaan voort en stel die volgende. Onder vandag se kode is hierdie lêer hier. Hierdie een hier, noswap. So, dit is 'n dom bietjie program wat Ek opgesweep dat eise om te doen die volgende. In die belangrikste, is dit verklaar 'n eerste int genoem x en ken dit die waarde van 1. Dan is dit verklaar 'n int y en wys dit die waarde 2. Dan is dit druk uit wat x en y is. Dan sê dit, uitruiling, dot dot dot. Dan is dit beweer dat hy 'n beroep 'n funksie genoem ruil, verby in x en y, die idee van wat is dat hopelik x en y sal terugkom anders, die teenoorgestelde. Dan is dit eis verruil! met 'n uitroepteken. Dan is dit druk uit x en y. Maar dit blyk dat hierdie baie eenvoudige demonstrasie af hier is eintlik karretjie. Selfs al het ek waarby 'n tydelike veranderlike en tydelik om 'n in dit, dan is ek gehou indiensneming n die waarde van b - wat voel redelik, want ek het gered van 'n afskrif van 'n in temp. Toe het ek werk b op gelyke wat ook al in temp. Hierdie soort dop spel van die beweging van 'n in b en b in 'n deur die gebruik van hierdie middel-man genoem temp voel heel redelik. Maar ek beweer dat wanneer ek loop hierdie kode, soos ek nou sal doen - Laat my gaan voort en plak dit hier. Ek bel die noswap.c. En soos die naam aandui, is dit nie gaan na 'n korrekte program wees. Maak noswap / geen ruil.. x is 1, y is 2, uitruiling, verruil. x is 1, y is 2. Dit is fundamenteel verkeerd is, selfs hoewel dit lyk perfek my redelik. En daar is 'n rede, maar ons is nie gaan om die rede om net nog nie openbaar. Vir nou die tweede fotonische lewe Ek wou om jou te laat is, word 'n aankondiging van spesies op coupons. Ons innovasie met laat dae hierdie jaar uitgelok het 'n nie-triviale aantal van die vrae wat was nie ons bedoeling. Die bedoeling van hierdie coupon kodes, waardeur as jy nie deel van die probleem stel vroeg, sodoende kry 'n ekstra dag, was regtig om jou te help ouens help jouself vroeg begin, soort van deur incentivizing jou. Help ons versprei vrag oor kantoorure beter sodat dit is soort van wen-wen. Ongelukkig, ek dink my instruksies het nie, tot op datum, baie duidelik, so Ek het teruggegaan hierdie naweek en opgedateer die spec in groter, vetter teks verduidelik koeëls soos hierdie. En net om dit meer in die openbaar sê, deur verstek, probleem stelle is as gevolg van Donderdag teen die middag, volgens die leerplan. As jy vroeg begin, afwerking deel van die probleem wat deur Woensdag om 12:00 PM, die deel wat verband hou met 'n koepon kode, die idee is dat jy kan uit te brei jou sperdatum vir die P stel tot Vrydag. Dit is bietjie af 'n klein deel van die P stel met betrekking tot wat tipies is die groter probleem, en jy koop jouself 'n ekstra dag. Weereens, dit kry jy dink oor die probleem stel, kry jy te kantoorure gouer. Maar die koepon kode probleem is nog steeds vereis word, selfs al is jy nie dien nie. Maar is meer compellingly hierdie. (Verhoog Fluister) En dié mense verlaat vroeg is dit nou eers spyt. As die mense op die balkon. Ek vra om verskoning by voorbaat aan die mense op die balkon vir die redes wat sal wees duidelik in net 'n oomblik. So ons is bevoorreg om een ​​te hê CS50 se voormalige hoof onderrig metgeselle by 'n maatskappy genaamd dropbox.com. Hulle het baie mildelik geskenk van 'n coupon code hier vir hierdie baie ruimte, wat uit die gewoonlik 2 GB. So, wat het ek gedink ons ​​sou doen oor hierdie laaste opmerking is nie 'n bietjie van 'n bonus, waardeur in net 'n oomblik, sal ons openbaar die wenner en wat 'n koepon kode wat jy dan kan gaan na hul webwerf, tik dit in, en voila, kry 'n hele klomp meer Dropbox ruimte vir jou apparaat en vir jou persoonlike lêers. En die eerste, wat graag om deel te neem in hierdie tekening? OK, nou wat maak dit selfs meer pret. Die persoon wat hierdie 25-GB ontvang coupon kode - dit is verreweg meer oortuigend as die laat dae nou, miskien - is die een wat op die top van 'n sit stoel kussing onder wat daar is dat coupon code. Jy kan nou kyk onder jou stoel kussing. [Video speel] -Een, twee, drie. [Skree] -Jy kry 'n motor! Kry jy 'n kar! David Malan: Ons sal sien jy op Woensdag. -Jy kry 'n motor! Kry jy 'n kar! Kry jy 'n kar! Kry jy 'n kar! Kry jy 'n kar! David Malan: balkon mense, kom hier aan die voorkant, waar ons ekstras. -Almal kry 'n motor! Almal kry 'n motor! [Einde video-vertoning] NARRATOR: By die volgende CS50 - SPREKER 5: Oh my gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh - [Ukelele TONEELSTUKKE]