[Musiikki soi] DAVID MALAN: Okei. Okei, tervetuloa takaisin. Joten tämä on viikolla 4, alussa sen jo. Ja voit muistaa, että viime viikolla, laitamme koodata varattu vain vähän ja aloimme puhua hieman korkean tason, asioita, kuten etsiminen ja lajittelu, joka tosin hieman yksinkertaisia ​​ideoita, ovat tyypillinen luokan ongelmia alatte ratkaista erityisesti kun alkaa miettiä lopullinen hankkeisiin ja mielenkiintoisia ratkaisuja sinulle ehkä reaalimaailman ongelmia. Nyt kupla tavallaan oli yksi yksinkertaisin tällaisia ​​algoritmeja, ja se työskenteli ottaa nämä pienet numerot luettelon tai matriisin sellainen kupla tiensä ylös, ja suuret numerot siirtää alas loppuun luetteloon. Ja muistuttaa, että voisimme visualisoida kupla tavallaan hieman jotain tällaista. Joten anna minun mennä eteenpäin ja napsauta Käynnistä. Olen ennalta kupla tavallaan. Ja jos muistatte, että pitempi sininen linjat edustavat suuret numerot, pieni siniset viivat edustavat pienien kuin käymme läpi tämän uudestaan ​​ja uudestaan ​​ja uudelleen, vertaamalla kaksi baaria vierekkäin toinen punainen, aiomme vaihtaa suurin ja pienin, jos ne ovat epäkunnossa. Joten tämä menee päälle ja mennä ja mennä on, ja näet, että suurempi elementit tiensä oikealle, ja pienemmät elementit ovat tiensä vasemmalle. Mutta aloimme määrällisesti tehokkuutta, laatu tämä algoritmi. Ja sanoimme, että pahimmassa tapauksessa tämä algoritmi kesti suunnilleen kuinka monta askelta? Joten n potenssiin. Ja mikä oli n? Yleisö: elementtien määrä. DAVID MALAN: Joten n oli useita tekijöitä. Ja niin me teemme tätä usein. Aina me haluamme puhua koko ongelma tai kokoa tulo tai aikaa kuluu tuottaa tuotos, me vain yleistynyt riippumatta tulo on kuin n. Joten takaisin viikolla 0, numero sivujen puhelinluettelosta, oli n. Opiskelijoiden määrä huone oli n. Niin täälläkin, olemme jälkeen että kuvio. Nyt n potenssiin ei ole erityisen nopeasti, joten yritimme tehdä paremmin. Ja niin me katsoimme pari muita algoritmeja, joista oli valinta lajitella. Joten valinta tavallaan oli hieman erilainen. Se oli melkein yksinkertaisempaa, uskallan sanoa, jolloin aloitin alussa luettelo meidän vapaaehtoisille ja minä vain kerran ja uudestaan ​​ja uudestaan ​​meni läpi lista, nyppiminen pois pienin elementti kerrallaan ja työnsivät tai hänen alussa luettelosta. Mutta tämäkin, kun aloimme ajatella läpi matematiikka ja isompi kuva, ajatellut kuinka monta kertaa Olin menossa edestakaisin ja takaisin edestakaisin, totesimme pahimmassa tapauksessa valinta lajitella, liian, oli mitä? n potenssiin. Nyt todellisessa maailmassa, se saattaa todella vähän nopeammin. Koska taas, en tarvitse pitää vetäytymistä kerran olin lajiteltu pienin elementtejä. Mutta jos ajattelemme hyvin suuri n ja jos tavallaan tehdä pois matematiikasta sen Tein pöydällä, jossa n potenssiin miinus jotain, kaikki muu lisäksi n potenssiin, kun n saa todella suuri, ei oikeastaan ​​väliä niin paljon. Niin tietotekniikan tutkijoita, me tavallaan ummistaa silmänsä pienempi tekijät ja keskittyä vain tekijä lauseke, joka tulee tehdä Suurin ero. No, lopuksi, me katsoimme klo lisäyslajittelu. Ja tämä oli hengeltään samanlainen, mutta eikä mene läpi iteratiivisesti ja Valitse pienin elementti yksitellen aikaa, olen sen sijaan otti käsi I oli käsitelty, ja päätin, kaikki oikeassa, sinä kuulut tänne. Sitten minä siirryin seuraavaan elementtiin ja päätti, että hän tai hän kuului täällä. Ja sitten muutin ja. Ja voisin sen, matkan varrella, siirtää nämä kaverit, jotta tehdä tilaa heille. Niin, että oli tavallaan henkistä kääntyminen valinnan sellaista, että me nimeltään lisäyslajittelu. Joten näitä aiheita esiintyy todellisessa maailmassa. Vain muutama vuosi sitten, kun tietty senaattori käynnissä presidentiksi, Eric Schmidt, tuolloin toimitusjohtaja Google, todella oli mahdollisuus haastattelemaan häntä. Ja ajattelimme jakaa tämän YouTube clip sinua täällä, jos voisimme kääntää ylös äänenvoimakkuutta. [VIDEOTOISTOSTA] -Senaattori, olet täällä Google, ja haluan ajatella puheenjohtajakauden kuin työhaastattelu. [Naurua] -Nyt on vaikea saada työtä presidenttinä. Ja olet menossa läpi jäykkyys nyt. On myös vaikea saada työpaikan Google. Meillä on kysymyksiä ja pyydämme meidän ehdokkaita kysymyksiä. Ja tämä yksi on Larry Schwimmer. [Naurua] -Luuletteko olen tosissasi? Se on täällä. Mikä on tehokkain tapa lajitella miljoonaa kahden bitin kokonaislukuja? [Naurua] -No, öh - -Olen pahoillani. Ehkä meidän pitäisi - -Ei, ei, ei, ei, ei. -Se ei ole - OK. -Mielestäni kupla semmoista on väärä tapa edetä. [Naurua] [Hurraavat ja suosionosoituksia] -Tule, jotka kertoivat hänelle tämän? OK. [END VIDEOTOISTOSTA] DAVID MALAN: Siinäpä se. Joten aloimme määrällisesti näiden käynnissä kertaa, niin sanotusti, jotain kutsutaan asymptoottinen merkintätapa, joka on tarkoita pelkästään meidän eräänlainen käännekohta silmänsä ne pienet tekijät ja tarkastellaan vain ajoaika suorituskykyä näiden algoritmien N saa todella suuren ajan. Ja niin me otettiin iso O. Ja iso O edustaa jotain, ajattelimme AS ylärajana. Ja todella, Barry, voimme laskea kuin mic vähän? Ajattelimme tämän on yläraja. Joten iso O n potenssiin tarkoittaa, että Pahimmassa tapauksessa jotain valinta sort veisi n potenssiin vaiheet. Tai jotain lisäyslajittelu olisi n potenssiin vaiheet. Nyt jotain paikoilleen lajitella, mikä oli pahin? Koska joukko, mikä on pahin mahdollinen skenaario, että saatat löytää itsesi edessä? Se on täysin taaksepäin, eikö? Koska jos se on täysin taaksepäin, sinun täytyy tehdä paljon työtä. Koska jos olet täysin taaksepäin, olet menossa löytää Suurin osa täällä, vaikka se kuuluu sinne. Joten aiot sanoa, okei, kello tällä hetkellä, et kuulu tänne, niin jätät sen yksin. Niin huomaat, oh, damn, minun on siirtää tätä hieman pienempi tekijä vasemmalla teistä. Sitten minun täytyy tehdä se uudestaan ja uudestaan ​​ja uudestaan. Ja jos minä kävelin edestakaisin, sinä olisi tavallaan tuntuu suorituskykyä että algoritmi, koska jatkuvasti olen laahustavat kaikki muutkin alas array tehdä sille tilaa. Niin, että pahimmassa tapauksessa. Sen sijaan - ja tämä oli jännitysnäytelmä viimeisen kerran - sanoimme, että lisäyslajittelu oli omega, mitä? Mikä on parhaassa tapauksessa käynnissä aika lisäyslajittelu? Joten se on todella n. Se oli tyhjä, että lähdimme taululle viimeisen kerran. Ja se on omega n koska miksi? No, parasta tapauksessa mitä lisäyslajittelu aiotaan luovuttaa? No, luettelo, joka on täysin lajiteltu jo vähän työtä tehdä. Mutta mitä on siisti noin lisäyslajittelu on, että koska se alkaa täällä päättää, oh, olet numero yksi, sinä kuulut tänne. Voi, mikä onni. Olet numero kaksi. Sinulla on myös kuulu tänne. Numero kolme, jopa parempi, et kuulu tänne. Heti kun se saa loppuun lista, per lisäyslajittelu n pseudokoodina että kävelimme läpi suullisesti Viimeisen kerran, se on tehty. Mutta valinta lajitella, sen sijaan, pidetään tekee mitä? Piti läpi lista uudestaan ​​ja uudestaan ​​ja uudestaan. Koska keskeinen oivallus oli vain kun olet etsinyt aina luettelon loppuun voit olla varma että elementti valitsemasi oli todellakin tällä hetkellä pienin elementti. Niinpä nämä eri ajattelumallien lopussa up saatiin hyvin reaalimaailman eroja meille, sekä näiden teoreettinen asymptoottinen eroja. Joten vain kertaus, sitten iso O n potenssiin, olemme nähneet muutamia tällaisia algoritmeja toistaiseksi. Big O n? Mitä algoritmi, joka voisi sanoa olevan iso O n? Pahimmassa tapauksessa, se kestää lineaarinen useita vaiheita. OK, lineaarista hakua. Ja pahimmassa tapauksessa, jossa on elementti etsit, kun soveltamalla lineaarista hakua? OK, pahimmassa tapauksessa, se ei ole edes olemassa. Tai toiseen pahimmassa tapauksessa se on aina lopulta, joka on plus-tai miinus-yksi-vaihe ero. Joten lopussa päivä, Voimme sanoa, että se lineaarinen. Big O n olisi lineaarinen haku, sillä pahimmassa tapauksessa, elementti ei ole edes olemassa tai se on koko matkan lopussa. No, iso O log n. Emme puhuneet hyvin yksityiskohtaisesti noin , mutta olemme nähneet tämän ennenkin. Mikä toimii ns logaritminen aikaa, pahimmassa tapauksessa? Joo, niin binäärihaku. Ja binäärihaku pahimmassa tapauksessa saattaa olla tekijä jossain keski-tai jonnekin sisällä array. Mutta et vain löydä sitä kerran jakaa listan kahtia, vuonna puoli, puoli, puoli. Ja sitten voila, se on olemassa. Tai jälleen, pahimmassa tapauksessa se ei ole edes olemassa. Mutta et tiedä, että se ei ole siellä kunnes tavallaan päästä, että viime alimmaisen elementtejä puolittamalla ja puolittaa ja puolittaa. Big O 1. Joten voisimme iso O 2, iso O 3. Milloin haluat vain vakiomäärä, me vain eräänlainen vain yksinkertaistaa että iso O 1. Vaikka jos realistisesti, se kestää 2 tai jopa 100 askeleen, jos se on jatkuvasti useita vaiheita, me vain sanoa iso O 1. Mitä algoritmi, joka on iso O 1? Yleisö: Finding pituus muuttujan. DAVID MALAN: Finding pituus muuttuvan? Yleisö: Ei, pituus jos se on jo järjestetty. DAVID MALAN: Hyvä. OK, niin löytää pituus jotain jos pituus, että jotain, kuten array, tallennetaan joissakin muuttuja. Koska voit lukea muuttujan tai tulostaa muuttujan tai vain yleisesti käyttää muuttuja. Ja voila, että kestää jatkuvaa aikaa. Sen sijaan muistelen raapia. Muistelen ensimmäisellä viikolla C, soittaa vain printf ja tulostus jotain ruudulla on kiistatta vakioaikaisia, koska se vain vie joitakin määrä suorittimen käytön näyttää että tekstiä ruudulla. Tai odota - eihän? Miten muuten voisimme mallintaa suorituskykyä printf? Voisiko joku olla eri mieltä, että ehkä se ei ole oikeastaan ​​jatkuvaa aikaa? Missä mielessä voisi printf juoksee aikaa, oikeastaan ​​tulostaa merkkijonon näyttö, olla jotain muuta kuin vakio. Yleisö: [kuultavissa]. DAVID MALAN: Joo. Joten se riippuu meidän näkökulmasta. Jos me todella ajattelemme panos printf olevan merkkijonon, ja Siksi me mittaamme koko kyseisen syöttää sen pituus - joten kutsukaamme että pituus n sekä - Ilmeisesti printf on itse iso O n koska se vie sinut n toimet tulostaa kaikki nämä n merkkiä, todennäköisesti. Ainakin siltä osin, että oletamme että ehkä se käyttää silmukka alla huppu. Mutta meidän olisi tarkasteltava, että Koodi ymmärtää sitä paremmin. Ja todellakin, kun kaverit alkaa analysoida omia algoritmeja, sinun kirjaimellisesti tehdä juuri niin. Lajittele silmämunan koodi ja ajatella noin - kaikki hyvin, minulla on tämä silmukka tässä tai minulla on sisäkkäisiä silmukoita täällä, että aikoo tehdä n asioita n kertaa, ja voit lajitella järjen tiesi koodin läpi, vaikka se on pseudokoodina eikä varsinainen koodi. Entä omega n potenssiin? Mikä on algoritmi, joka on paras tapauksessa edelleen otti n potenssiin vaiheet? Niin? Yleisö: [kuultavissa]. DAVID MALAN: Joten valinta lajitella. Koska tämä ongelma todella vähentää siihen, että jälleen, en tiedä Olen löytänyt nykyisen pienin asti Olen tarkistanut kaikki hiton elementtejä. Joten omega vaikkapa n, me tuli juuri yksi. Lisäyslajittelu. Jos luettelo sattuu lajitella jo, parhaassa tapauksessa meidän on vain tehdä kerralla läpi, jolloin emme varmasti. Ja sitten, että voidaan sanoa olla lineaarinen, varmasti. Entä omega 1? Mitä, parhaassa tapauksessa saattaa kestää jatkuva useita vaiheita? Joten lineaarinen haku, jos vain onnekas ja elementin etsit on aivan listan alkuun, jos se jos olet aloittamassa lineaarinen läpikäyminen luetteloon. Ja tämä on totta useita asioita. Esimerkiksi jopa binary haku on omega 1. Koska mitä jos saat todella hiton onnekas ja ihan keskellä levyjärjestelmän on määrä etsit? Joten voit saada onnekas siellä samoin. Tämä yksi, lopuksi omega n log n. Joten n log n, emme oikeastaan puhua vielä, mutta - Yleisö: Merge sort? DAVID MALAN: Merge sort. Se oli jännitysnäytelmä viime aikaa, jossa ehdotimme, ja osoitimme visuaalisesti, että on olemassa algoritmeja. Ja yhdistää tavallaan vain yksi tällainen algoritmi, joka on pohjimmiltaan nopeampi kuin jotkut näistä muista tyyppejä. Itse asiassa, yhdistää lyhyt ei ainoastaan Parhaassa tapauksessa n log n, pahimmassa tapauksessa n log n. Ja kun sinulla on tämä sattuma omega ja iso O on sama asia? Voimme itse kuvata, että mitä kutsutaan theta, vaikka se on hieman harvinaisempia. Mutta se tarkoittaa vain kaksi bounds, tässä tapauksessa ovat samat. Joten yhdistää tavallaan, mitä tämä todella pohjimmiltaan meille? No, muistaa motivaatio. Saanen vetää toinen animaatio emme katso viimeinen kerta. Tämä yksi, sama idea, mutta se on hieman suurempi. Ja aion mennä eteenpäin ja huomauttaa Ensimmäinen - meillä on lisäyslajittelu on vasemmassa yläkulmassa, niin valinta lajitella, kupla lajitella, pari muunkinlaisia ​​- kuori ja nopea - että emme ole keskustelleet noin, ja kasaan ja yhdistää tavallaan. Joten ainakin yrittää keskittyä silmäsi kärkikolmikkoon vasemmalle ja sitten yhdistää eräänlainen kun klikkaa Tämä vihreä nuoli. Mutta minä annan ne kaikki ajaa, vain antaa sinulle tunteen monimuotoisuuden algoritmeja, että olemassa maailmassa. Aion antaa tämän nousun vain muutaman sekunnin. Ja jos keskittyä silmäsi - pick algoritmi, keskittyä siihen vain sekuntia - voit alkaa nähdä kuvio, että se toteuttaa. Yhdistä lajitella, ilmoitus on tehty. Heap lajitella, nopeasti lajitella, kuori - joten se näyttää esittelimme kolme pahin algoritmit viime viikolla. Mutta se on hyvä, että olemme täällä tänään katso yhdistäminen lajitella, joka on yksi helpommalla on tarkastella, vaikka vaikka se todennäköisesti taipuu mielesi vain vähän. Täällä voimme nähdä, kuinka paljon valinta lajitella perseestä. Mutta kääntöpuoli, se on todella helppo toteuttaa. Ja ehkä P Set 3, joka on yksi algoritmeja valitsit toteuttaa standardin painos. Hienosäätää, aivan oikeassa. Mutta jälleen kerran, kun n saa suuret, jos päättää panna nopeammin algoritmi kuin sulautua lajitella, kertoimet ovat suurempia ja Suuremmat tulot, koodi on vain menossa ajaa nopeammin. Sivuston tulee toimimaan paremmin. Käyttäjät tulevat olemaan onnellisempi. Ja niin on nämä vaikutukset todella antaa meille hieman syvemmällä ajatellut. Joten katsomaan mitä sulautua sort on oikeastaan ​​kyse. Viileä asia on, että sulautuvat sort on juuri tämä. Tämä on taas mitä me olemme kutsuneet pseudokoodit pseudokoodina olento Englanti-syntaksi. Ja yksinkertaisuus on tavallaan kiehtovaa. Joten tulo n elementtejä - niin, että tarkoittaa vain sitä, tässä on jono. Se sai n asioita siinä. Siinä kaikki sanomme siellä. Jos n on pienempi kuin 2, palaa. Joten se on vain vähäpätöinen asia. Jos n on pienempi kuin 2, niin ilmeisesti se on 1 tai 0, jolloin asia on jo järjestetty tai olematon, niin vain palata. Ei mitään tekemistä. Niin, että yksinkertainen asia nyppiä pois. Else, meillä on kolme vaihetta. Lajitella vasen puoli elementtejä, lajitella oikealla puolella elementtejä, ja sitten yhdistää lajiteltu puolikkaat. Mielenkiintoista tässä on se, että Olen sellainen punting, eikö? On sellainen pyöreä määritelmän Tämän algoritmin. Missä mielessä tämä algoritmi määritelmä pyöreä? Yleisö: [kuultavissa]. DAVID MALAN: Joo, minun lajittelu algoritmi, kaksi sen vaiheet ovat "tavallaan jotain. "Ja niin, että herättää kysymys, hyvin, mitä aion käyttää lajitella vasen puoli ja oikea puoli? Ja kauneus tässä on se, että vaikka kerran, tämä on aistiharhoja osa mahdollisesti voit käyttää samaa algoritmi lajitella vasen puoli. Mutta hetkinen. Kun olet kertonut lajitella vasen puoli, mitkä ovat kaksi vaiheet tulee seuraavaksi? Me lajitella vasen puoli vasen puoli ja oikea puolet vasen puoli. Hitto, miten voin lajitella nämä kaksi puolikkaat tai neljännekset, nyt? Mutta se on OK. Meillä on Lajittelualgoritmi täällä. Ja vaikka saatat huolehtia ollenkaan Aluksi tämä on eräänlainen ääretön silmukka, se on sykli, joka ei ole koskaan ehdi - se on menossa päättyy, kun mitä tapahtuu? Kun n on pienempi kuin 2. Joka lopulta tulee tapahtumaan, koska jos pitää puolittaa ja puolittaa puolittamaan nämä puolikkaat, varmasti lopulta olet menossa loppuun jopa vain 1 tai 0 elementtejä. Jolloin tämä algoritmi sanoo olet valmis. Joten todellinen taika tässä algoritmi näyttää olevan että viimeinen vaihe, yhdistäminen. Tämä yksinkertainen ajatus vain yhdistämällä kaksi asioita, se mitä lopulta tapahtuu jotta voimme järjestää erilaisia, sanotaanko, kahdeksan elementtejä. Olen siis kahdeksan enemmän stressiä palloja ylös täällä kahdeksan paperille, ja yksi Google Glass - jonka saan pitää. [Naurua] DAVID MALAN: Jos voisimme ottaa kahdeksan vapaaehtoisia, ja katsotaan jos voimme pelata tätä ulos, niin. Vau, OK. Tietotekniikassa on tulossa hauskaa. Selvä. Niin miten te kolme, Suurin käsi ylös. Neljä takana. Ja miten me teemme sinulle kolme tällä rivillä? Ja neljä edessä. Joten te kahdeksan, tule ylös. [Naurua] DAVID MALAN: Olen oikeastaan ole varma, mitä se on. Onko stressi pallot? Kirjoituspöydän lamput? Materiaalia? Internet? OK. Joten tule ylös. Kuka haluaisi - tulee koko ajan. Katsotaanpa. Ja tämä asettaa sinut paikkaan - olet paikalla yksi. Uh-oh, odota hetki. 1, 2, 3, 4, 5, 6, 7 - OH, hyvä. Okei, olemme hyviä. Okei, joten jokainen on paikka, mutta ei Google Glass. Saanen jonottaa nämä ylös. Mikä sinun nimesi on? MICHELLE: Michelle. DAVID MALAN: Michelle? Okei, saat näyttää pelle, jos se on OK. No, minä myös, oletan, vain hetken. Okei, valmiustilassa. Olemme yrittäneet keksiä käyttää tapauksessa Google Glass, ja me ajattelin että olisi hauskaa vain tehdä Tässä kun ihmiset ovat lavalla. Me tallentaa maailman heidän näkökulmastaan. Selvä. Ei luultavasti mitä Google tarkoitettu. Okei, jos et mielessä yllään Tämän seuraavan hankala minuuttia, Se olisi hienoa. Okei, joten meillä on täällä joukko elementtejä, ja että array, kohti paperinpaloja nämä ihmiset " kädet, on tällä hetkellä lajittelematta. MICHELLE: Voi, se on niin outoa. DAVID MALAN: Se on aika paljon satunnaisia. Ja vain hetken, aiomme kokeilla toteuttaa yhdistää tavallaan yhdessä ja katso, että keskeiset oivallus on. Ja temppu täällä merge sort on jotain, että emme ole oletettu vielä. Me todella tarvitsemme lisätilaa. Joten mitä tulee olemaan erityisen mielenkiintoista tässä on se, että nämä kaverit ovat menossa liikkua hieman vähän, koska aion olettaa, että siellä on ylimääräistä joukko tilaa, sanoa, oikealla takana. Joten jos he takana tuoli, se toissijainen array. Jos he istuvat täällä, se on ensisijainen jono. Mutta tämä on voimavara, että meillä on ei velkarahalla toistaiseksi kupla lajitella, jossa valinta lajitella, kanssa lisäyslajittelu. Recall viime viikolla, kaikki vain Tällainen sekoitetaan paikallaan. He eivät käytä mitään lisämuistia. Teimme tilaa ihmisten liikkuvat ihmiset ympärillä. Joten tämä on keskeinen oivallus, too. Ei tämä kompromissi, yleisesti tietojenkäsittelytiede, resursseja. Jos haluat nopeuttaa jotain kuten aika, olet menossa on maksettava hinta. Ja yksi näistä hinnoista on hyvin usein tilaa, muistin määrän tai kova levytilaa, että käytät. Tai suoraan sanoen määrä ohjelmoija aikaa. Kuinka paljon aikaa se vie, ihmisten, todella toteuttaa joitakin enemmän monimutkainen algoritmi. Mutta tänään, kauppa-off on aikaa ja tilaa. Joten jos te voisi vain pitäkää numerot, jotta voimme nähdä, että olet todellakin vastaa 4, 2, 6, 1, 3, 7, 8. Erinomainen. Joten aion yrittää johdatella asioita, jos te voitte vain noudattaa esimerkkiäni täällä. Joten aion toteuttaa, ensin, ensimmäisessä vaiheessa pseudokoodi, joka on syötettyjen n osia, jos n on alle 2, palaa sitten. On selvää, että ei apply, joten siirrymme. Joten lajitella vasemmalla puolella elementtejä. Niin se tarkoittaa, aion keskittyä minun huomiota vain hetken seuraavilla neljä kaveria täällä. Okei, mitä teen seuraavaksi tehdä? Yleisö: lajitella vasen puoli. DAVID MALAN: Joten nyt minun täytyy lajitella vasen puoli nämä kaverit. Koska taas olettaa itse Tavoitteena on lajitella vasen puoli. Miten teet sen? Seuraa ohjeita, vaikka vaikka teemme sen uudestaan. Joten lajitella vasen puoli. Nyt olen lajittelu nämä kaksi kaveria. Mitä seuraavaksi? Yleisö: lajitella vasen puoli. DAVID MALAN: lajitella vasen puoli. Joten nyt nämä, tämä paikka täällä, on lista koko 1. Ja mikä sinun nimesi olikaan? PRINCESS DAISY: Prinsessa Daisy. DAVID MALAN: Prinsessa Daisy on täällä. Ja niin hän on jo järjestetty, koska luettelo on koko 1. Mitä seuraavaksi tehdä? OK, palaa, koska luettelo on koko 1, joka on pienempi kuin 2. Mikä sitten on seuraava askel? Ja nyt sinulla on sellainen takapakkia mielessäsi. Lajitella oikea puoli, joka on - Mikä sinun nimesi on? LINDA: Linda. DAVID MALAN: Linda. Ja niin mitä teemme nyt, että meillä on lista koko 1? Yleisö: Return. DAVID MALAN: varovainen. Palaamme ensimmäinen, ja nyt kolmas askel - ja jos olen sellainen kuvaavat sitä käsittää kaksi paikkaa nyt, nyt minä on yhdistää nämä kaksi asiaa. Joten nyt valitettavasti elementtejä ovat epäkunnossa. Mutta siitähän yhdistämismenettelystä alkaa saada pakottavia. Joten jos te voisi nousta vain hetki, aion tarvitsevat teitä, hetkellä vaiheeseen takana tuolin. Ja jos Linda, koska 2 on pienempi kuin 4, mikset tulet noin ensin? Pysy siellä. Joten Linda, tulet noin ensin. Nyt todellisuudessa se on vain joukko voisimme siirtää hänet reaaliajassa Tämän tuolin tällä paikalla. Joten kuvitella, että kesti jonkin jatkuvaa useita vaiheita 1. Ja nyt - mutta meidän täytyy laittaa sinut ensimmäisen sijainnin tässä. Ja nyt jos voisit tulla noin, samoin, aiomme olla paikalla kaksi. Ja vaikka tämä tuntuu se ottaen samalla, mitä mukavaa nyt että vasen puoli vasen puoli on nyt järjestetty. Joten mikä oli seuraava askel, jos me nyt kelaa edelleen tarina? Yleisö: Oikea puoli. DAVID MALAN: lajitella oikea puoli. Joten te täytyy tehdä tämä, samoin. Joten jos voisitte seisomaan vain hetken? Ja mikä on nimesi? JESS: Jess. DAVID MALAN: Jess. OK, joten Jess on nyt vasen puolet oikealla puolella. Ja niin hän on luettelo koko 1. Hän ilmeisesti lajitellaan. Ja sinun nimesi olikaan? MICHELLE: Michelle. DAVID MALAN: Michelle on tietenkin luettelo koko 1. Hän on jo järjestetty. Joten nyt taika tapahtuu, yhdistämismenettelystä. Joten kuka tulee ensiksi? Ilmeisesti Michelle. Joten jos voisit tulla ympäri takaisin. Tilaa meillä on käytettävissä hänen nyt on oikeassa takana tuolin täällä. Ja nyt jos voisit palata sekä, meillä on nyt, on selvää, kaksi puolikkaat, kukin kooltaan 2 - ja vain kuvaus vuoksi, jos voisi tehdä vähän tilaa - yksi jäljellä puoli täällä, yksi oikea puoli täällä. Kelaa edelleen tarina. Mikä vaihe on seuraava? Yleisö: Yhdistä. DAVID MALAN: Nyt meidän täytyy yhdistää. Joten OK, joten nyt onneksi meillä vain vapautti neljä tuolia. Joten olemme käyttäneet kaksi kertaa enemmän muistia, mutta voimme antaa flip-flopping välillä kaksi paneelit. Joten mikä numero on tulla ensin? Joten Michelle, tietenkin. Joten tulevat ympäri ja ottaa Varmista paikkasi. Ja sitten numero 2 on ilmeisesti seuraava, niin tulet tänne. Numero 4, numero 6. Ja vielä, vaikka siellä vähän kävelyä mukana, todella, nämä voi tapahtua hetkessä, siirtämällä yhtä - OK, hyvin pelattu. [Naurua] DAVID MALAN: Ja nyt me olemme hyvässä kunnossa. Vasen puoli koko tulo on nyt lajiteltu. Okei, niin nämä kaverit oli etu minun - miten se lopulta kaikki tytöt vasemmalle ja kaikki pojat oikealla? OK, joten kaverit vuoro nyt. Joten en opastaa nämä vaiheet. Näemme, jos voimme hakea uudelleen Sama pseudokoodina. Jos haluat mennä eteenpäin ja seisomaan, ja te, minä annan sinulle mic. Katso jos et voi jäljitellä mitä me vain teimme täällä muut listan loppuun. Kuka tarvitsee puhua ensin, perusteella algoritmi? Joten selittää, mitä olet tekemässä ennen teet jalka liikkeitä. SPEAKER 1: Okei, joten sillä Olen vasen puoli vasen puoli, palaan. Oikea? DAVID MALAN: Hyvä. SPEAKER 1: Ja sitten - DAVID MALAN: Kuka tekee mic mennä seuraavaksi? SPEAKER 1: Seuraava numero. SPEAKER 2: Olen siis oikea puoli ja vasen puoli vasen puoli, ja palaan. DAVID MALAN: Hyvä. Palaat. Joten nyt mitä seuraavaksi ylös sinulle kaksi? SPEAKER 2: Haluamme nähdä, kuka on pienempi. DAVID MALAN: Aivan. Haluamme yhdistää. Tilaa aiomme käyttää sulautua sinut, vaikka he ilmeisesti lajitellaan jo aiomme noudattaa samaa algoritmia. Kuka menee ensin takaisin? Joten 3, ja sitten 7. Ja nyt mic menee Näiden kaverit, OK? SPEAKER 3: Olen siis oikea puoli vasen puoli, ja minun n on pienempi kuin 1, joten olen juuri menossa ohi - DAVID MALAN: Hyvä. SPEAKER 4: Olen oikea puoli oikea puoli oikea puoli, ja olen Lisäksi yksi henkilö, joten olen aio palata. Joten nyt olemme yhdistäminen. SPEAKER 3: Eli menemme takaisin. DAVID MALAN: Eli menet takaisin. Joten 5 menee ensin, sitten 8. Ja nyt yleisö, joka on vaiheeseen meidän on nyt kelata takaisin mielessämme? Yleisö: Yhdistä. DAVID MALAN: yhdistäminen vasen puoli ja oikea puolet alkuperäisestä vasen puoli. Joten nyt - ja vain tehdä tämän selväksi, tehdä hieman tilaa välillä te kaksi kaveria. Joten nyt on kaksi listaa, vasemmalle ja oikealle. Miten siis nyt sulautua te osaksi eturivin paikkaa uudelleen? 3. menee ensin. Sitten 5, tietenkin. Sitten 7, ja nyt 8. OK, ja nyt me olemme? Yleisö: Ei tehty. DAVID MALAN: Ei tehty, koska tietenkin, siellä on yksi askel jäljellä. Mutta jälleen kerran, syy Käytän tätä sanastoa kuten "taaksepäin mielessäsi" se on koska se on todella mitä tapahtuu. Menemme läpi kaikki nämä vaiheet, mutta olemme tavallaan pysähtyen hetki, sukellus syvemmälle algoritmi, pysähtyen hetkeksi, sukellus syvemmälle algoritmin, ja nyt meillä on tavallaan taaksepäin meidän mielissä ja kumoa kaikki nämä kerrokset että olemme tavallaan pitoon. Meillä on nyt siis kaksi luetteloa koko 4. Jos te voisi nousta viimeisen kerran ja tehdä vähän tilaa täällä tehdä selväksi, että tämä on vasen puoleen alkuperäisestä, oikeus puolet alkuperäisestä. Kuka ensimmäinen numero että täytyy vetää takaisin? Michelle, tietenkin. Joten laitoimme Michelle täällä. Ja kuka on numero 2? Numero 2 syttyy takaisin samoin. Numero 3? Erinomainen. Numero 4, numero 5, numero 6, numero 7 ja numero 8. OK, joten se tuntui paljon vaiheita, varmasti. Mutta nyt katsotaanpas jos emme voi vahvistaa eräänlainen intuitiivisesti, että tämä algoritmi pohjimmiltaan, erityisesti n saa todella suuri, kuten olemme nähneet kanssa animaatioita, on pohjimmiltaan nopeammin. Joten Väitän tämä algoritmi pahimmassa tapauksessa ja jopa parhaassa tapauksessa on iso O n kertaa log n. Eli siellä on joitakin osa tätä algoritmi, joka vie n askelta, mutta on toinen näkökohta jossain että iteraatio, että kiehkura, että otetaan log n vaiheet. Voimmeko laittaa sormi mitä ne kaksi numeroa viittaavat? No, jos - Minne mic mennä? SPEAKER 1: Olisiko log n on rikkomatta meidät kahteen - jakamalla kaksi lähinnä. DAVID MALAN: Aivan. Aina näemme missään ollen algoritmi mennessä siellä on ollut tämä malli jakamalla, jakamalla, jakamalla. Ja se yleensä vähenee jotain, joka on logaritminen, logaritmina 2. Mutta se voisi todella olla mitä tahansa, mutta logaritmi 2. Mutta mites n? Näen, että meillä sellainen jaettu sinua kaverit - jakaa teille, jakaa teille, jakaa teille, jakaa teille. Mistä lopulta tulee? Joten se yhdistämistä. Koska mieti sitä. Kun yhdistät kahdeksan ihmistä yhdessä, jolloin puolet on asetettu neljä ja toinen puoli ovat toinen Neljä, miten edetä noin tekee yhdistäminen? No, te teitte sen melko intuitiivisesti. Mutta jos sen sijaan teki siitä hieman suunnitelmallisesti, olisin suunnattu vasemmanpuoleisin henkilö ensin minun vasen käsi, huomautti vasemmalla henkilö Kyseisen puolet minun oikealle puolelleni, ja vain myöhemmin käveli lista, osoittaen pienimmän alkion joka kerta, liikkuvat minun sormella ja yli tarpeen koko lista. Mutta mitä näppäintä tästä sulautuvan prosessi on olen vertaamalla näitä paria elementtejä. Oikean puolen ja vasemman puoli, en kertaakaan vetäytymistä. Joten yhdistäminen on itse tuossa enintään n askelta. Ja kuinka monta kertaa olen tehdä, että yhdistäminen? No, enintään n, ja me vain näki, että lopullinen yhdistämisen. Ja niin jos teet jotain, joka vie log n askelta n kertaa, tai päinvastoin, se tulee antamaan meille n kertaa log n. Ja miksi tämä on parempi? No, jos me jo tiedämme, että log n on parempi kuin n - eikö? Näimme binäärihaku, puhelinluettelo Esimerkiksi log n oli ehdottomasti parempi kuin lineaarinen. Joten se tarkoittaa n kertaa log n on ehdottomasti parempi kuin n kertaa toisen n, AKA n potenssiin. Ja sitähän me lopulta tuntuu. Joten aplodit, jos Voisimme nämä kaverit. [APPLAUSE] DAVID MALAN: Ja jakaus lahjat - voi pitää numerot, jos haluat. Ja jakaus lahja, kuten tavallista. Niin, ja me lähetämme sinulle kuvamateriaalia, Michelle. Kiitos. Selvä. Auta itseäsi stressipallo. Ja haluan vetää, sillä välin, ystävämme Rob Bowden tarjota hieman erilaisen näkökulman tähän, koska voit ajatella näitä vaiheet tapahtuu hieman eri tavalla. Itse asiassa, set-up, mitä Rob on noin näyttää meille olettaa, että olemme jo jakamista ja iso lista kahdeksaan pieniä luetteloita, kukin koko 1. Joten me muutumme pseudokoodina hieman vain tavallaan saada aikaa ydinajatuksena miten yhdistäminen toimivat. Mutta ajoaika mitä hän on aikeissa tehdä, on edelleen olemaan sama. Ja vielä, set-up on, että hän on alkanut kahdeksan luettelot koko 1. Joten olet jäänyt osa, jossa hän on todella tehneet log n, log n, log n jakamalla tulo. [VIDEOTOISTOSTA] -Se on se ensimmäinen vaihe. Vaiheessa kaksi, toistuvasti yhdistää paria luetteloita. DAVID MALAN: Hm. Vain ääni on tulossa pois minun tietokone. Kokeillaan tätä uudelleen. -Aivan mielivaltaisesti valita, - Nyt meillä on neljä luettelot. Lue ennen. DAVID MALAN: Siellä mennään. -Yhdistäminen 108 ja 15, päädymme kanssa luettelon 15, 108. Yhdistäminen 50 ja 4, me päätyä 4 50. Yhdistäminen 8 ja 42, me päätyä 8, 42. Ja yhdistämällä 23 ja 16, me päätyä 16, 23. Nyt kaikki luettelot ovat kooltaan 2. Huomaa, että kukin neljä luettelot lajitellaan. Joten voimme aloittaa sulautuvan paria luettelot uudelleen. Yhdistäminen 15 ja 108 ja 4 ja 50, me toteuttaa ensin 4, sitten 15, sitten 50, sitten 108. Yhdistäminen 8, 42 ja 16, 23, ensin ottaa 8, sitten 16, sitten 23, sitten 42. Joten nyt meillä on vain kaksi luetteloa koko 4, joista kukin on järjestetty. Nyt siis yhdistää nämä kaksi luetteloa. Ensin otamme 4, niin otamme 8, sitten otamme 15, sitten 16, sitten 23, sitten 42, sitten 50, sitten 108. [END VIDEOTOISTOSTA] DAVID MALAN: Jälleen ilmoituksen, hän ei koskaan kosketti tietyn kuppi useamman kuin yhden kerran jälkeen etenee pidemmälle. Joten hän ei ole koskaan toistuvan. Niin hän on aina siirtymässä puolelle, ja se jos saimme n. Miksi ei anna minun vetää yksi animaatio että näimme aiemmin, mutta tällä kertaa keskitytään vain merge sort. Anna minun mennä eteenpäin ja zoomata sisään täällä. Ensinnäkin haluan valita satunnainen tulo, tämä korostuu, ja voit tavallaan nähdä mitä otimme itsestäänselvyytenä, aiemmin, yhdistää tavallaan todella tekee. Niin huomaat että saat nämä puolikkaat tai neljännesvuoden tai näiden kahdeksasosaa ongelma, että yhtäkkiä alkaa ottaa hyvässä kunnossa. Ja lopulta, näet at aivan lopussa, että bam, kaikki on sulautunut yhteen. Joten nämä ovat vain kolme eri vie samaan ideaan. Mutta avain oivalluksia, kuten kuilu ja valloittaa aivan ensiluokkainen, oli, että päätimme jotenkin jakaa Ongelma tulee jotain suurta, osaksi jotain tavallaan sama henki, mutta pienempiä ja pienempiä ja pienempiä. Nyt toinen hauska tapa tavallaan ajatella näistä, vaikka se ei ole aio antaa teille saman intuitiivinen ymmärtäminen, on seuraava animaatio. Joten tämä on video joku koota että liittyvät eri äänet eri toimintojen lisäyslajittelu varten yhdistäminen lajitella ja ja pari muuta. Joten hetki, aion lyödä Play. Se on noin minuutin pituinen. Ja vaikka et voi vielä nähdä kuvioita tapahtuu, tällä kertaa voit myös kuulla, miten nämä algoritmit ovat suorittaa eri tavoin ja hieman erilaisia ​​kuvioita. Tämä on lisäyslajittelu. [TONES PLAYING] DAVID MALAN: Se taas yrittää lisätä jokaisen elementin siitä, mihin se kuuluu. Tämä on kupla tavallaan. [TONES PLAYING] DAVID MALAN: Ja voit tavallaan tuntuu miten suhteellisen vähän työtä se tekee kussakin vaiheessa. Tämä on mitä tediousness kuulostaa. [TONES PLAYING] DAVID MALAN: Tämä on valinta lajitella, jossa valitse elementti haluamme by läpi uudestaan ​​ja uudestaan ​​ja uudestaan ja laittoi pallon alussa. [TONES PLAYING] DAVID MALAN: Tämä on yhdistää tavallaan, joka voit todella alkaa tuntea. [TONES PLAYING] [Naurua] DAVID MALAN: Jotain nimeltään gnome lajitella, joita emme ole katsonut. [TONES PLAYING] DAVID MALAN: Niin anna minun nähdä, nyt hajamielinen kun toivottavasti ovat by musiikkia, jos voin luistaa hieman vähän matematiikkaa täällä. Joten on neljäsosa tavalla, että voimme miettiä, mitä se tarkoittaa, että nämä toimintoja nopeammin kuin niitä että olemme nähneet ennen. Ja jos olet tulossa kurssin matematiikan tausta, voit oikeastaan ​​tiedä ehkä jo, että olet voi isku aikavälillä tähän tekniikkaan - eli rekursio, toiminto että jotenkin kutsuu itseään. Ja vielä, muistaa, että yhdistäminen lajitella pseudokoodina oli rekursiivinen mielessä että yksi Merge sort askeleet oli soittaa tavallaan - se on, itse. Mutta onneksi, koska pidimme soittamalla lajitella tai yhdistää lajitella, Erityisesti on pienempiä ja pienempi lista, me lopulta pohjansa ansiosta mitä me kutsumme pohja tapauksessa koodattu niin, että sanoi, että jos lista on pieni, alle 2 siinä tapauksessa, palaa heti. Jos meillä ei ole, että erikoistapaus, algoritmi olisi koskaan pohja pois, ja sinulla olisi todellakin päästä päättymättömään silmukkaan todella ikuisesti. Mutta oletetaan, että halusimme nyt laittaa joitakin numeroita tässä, jälleen käyttäen n kuin koko panos. Ja halusin kysyä teiltä, ​​mitä kokonaisaika mukana käynnissä Yhdistämisen tavallaan? Tai yleisemmin, mitä kustannukset sen ajoissa? No se on melko helppo mitata sitä. Jos n on pienempi kuin 2, aikaa mukana lajittelussa n elementtejä, jossa n on 2, on 0. Koska me vain palata. Ei ole tehtävää. Nyt luultavasti, ehkä se on yksi askel tai kaksi vaiheet selvittää määrä työtä, mutta se on tarpeeksi lähellä 0, että Olen juuri menossa sanoa mitään työtä ei vaadita, jos lista on niin pieni on mielenkiinnoton. Mutta tämä tapaus on mielenkiintoinen. Rekursiivinen tapaus oli haara pseudokoodina että mainittu muuta, sort vasen puoli, lajitella oikea puoli, yhdistää kaksi puolikasta. Nyt miksi tämä ilmaus edustaa että kuluja? No, T n vain sitä, aikaa selvittää n elementtejä. Ja sitten oikealla puolella yhtäläisyysmerkkiä siellä, T n jaettu 2 viittaa kustannukset mitä? Lajittelu vasen puoli. Muut T n jaettuna 2 on oletettavasti viitaten kustannukset lajitella oikea puoli. Ja sitten plus n? Onko yhdistämistä. Koska jos sinulla on kaksi listaa, yksi koko n yli 2 ja toisen koko on n yli 2, sinun on olemukseltaan jokainen näistä seikoista, kuten Rob kosketti molempia kupit, ja vain kuten jo jokaisessa vapaaehtoiset lavalla. Joten n on kustannuksella yhdistämistä. Nyt valitettavasti tämä kaava on myös itse rekursiivinen. Joten jos kysyi, jos n on vaikkapa 16, jos siellä on 16 ihmistä lavalla tai 16 kupillista video, kuinka monta yhteensä vaiheet kestää järjestellä Yhdistäminen lajitella? Se on oikeastaan ​​ole selvää vastausta, koska nyt sinulla on tavallaan rekursiivisesti vastata tähän kaavaan. Mutta se on OK, koska haluan ehdottaa että teemme seuraavat. Aikaa mukana lajitella 16 henkilöä tai 16 kuppia tulee olla edustettuna yleisesti T 16. Mutta joka vastaa saamiemme edellinen kaava, 2 kertaa enemmän aikaa kuluu lajitella 8 kuppia plus 16. Ja vielä, plus 16 on aika yhdistää, ja kaksi kertaa T 8 on aikaa selvittää vasen puoli ja oikea puoli. Mutta jälleen kerran, tämä ei riitä. Meidän täytyy sukeltaa syvemmälle. Tämä tarkoittaa, että meidän on vastattava kysymys, mikä on T 8? No T 8 on vain 2 kertaa T 4 +8. No, mitä T 4? T 4 on vain 2 kertaa T 2 plus 4. No, mitä T 2? T 2 on vain 2 kertaa T 1 plus 2. Ja vielä, olemme tavallaan saada juuttunut tämä sykli. Mutta se on osumassa, että ns base tapauksessa. Koska mitä T 1, ei me väitämme? 0. Joten nyt vihdoin, voimme työskennellä taaksepäin. Jos T 1 on 0, voin nyt palata edelliselle linja tämä kaveri täällä, ja voin plug in 0 T 1. Niin se tarkoittaa, se vastaa 2 kertaa nolla, joka tunnetaan myös 0, plus 2. Ja niin, että koko ilmaisua on 2. Nyt jos otan T 2, jonka vastaus on 2, kytke se keskilinjaa, T 4, joka antaa minulle 2 kertaa 2 plus 4, joten 8. Jos en kytke 8 edelliseen line, joka antaa minulle 2 kertaa 8, 16. Ja jos me sitten jatkaa, että 24 lisäämällä, 16, me vihdoinkin arvo 64. Nyt sinänsä tavallaan puhuu mitään n merkintä, iso O, omega, että olemme puhuneet. Mutta näyttää siltä, ​​että 64 on todellakin 16, koko syöttö, logaritmi 2 16. Ja jos tämä on hieman tuntematon, vain muistelen, ja se tulee takaisin sinulle lopulta. Jos tämä on logaritmina 2, se on kuin 2 nostetaan mitä saat 16? Voi, se on 4, niin se on 16 kertaa 4. Ja vielä, se ei ole iso juttu, jos tämä on eräänlainen utuinen muisti nyt. Mutta nyt, ottaa uskossa että 16 log 16 on 64. Ja niin tosiaan, tämä yksinkertainen järki Tarkista, olemme vahvistaneet - mutta ei osoittautunut muodollisesti - että ajoaika Yhdistämisen sort on todellakin n log n. Joten ei paha. Se on ehdottomasti parempi kuin algoritmeja olemme nähneet tähän mennessä, ja se on koska olemme velkarahalla, yksi, tekniikkaa kutsutaan rekursion. Mutta mielenkiintoisempaa kuin, että käsitettä jakamalla ja valloittaa. Jälleen todella viikolla 0 kamaa, että jo nyt on toistuva enemmän pakottavia tavalla. Nyt hauskaa vähän liikuntaa, jos olet koskaan tehnyt tätä - ja luultavasti ei olisi, koska tavallaan normaalia ihmiset eivät usko tähän. Mutta jos menen google.com ja jos Haluan oppia jotain rekursio, Anna. [Naurua] [Naurua] DAVID MALAN: Bad vitsi hitaasti leviää. [Naurua] DAVID MALAN: Vain siinä tapauksessa, että se on siellä. En kirjoittaa sen väärin, ja siellä on vitsi. Selvä. Selitä sitä ihmisille vieressäsi jos Se ei ole aivan napsautetaan vielä. Mutta rekursio yleisemmin viitataan prosessia toiminto soittaa itse, tai yleisemmin, väliseinä ongelma jotain, joka voi olla ratkaista vähitellen ratkaisemalla identtisiä edustaja ongelmia. No, vaihtohammaspyöriä vain hetken. Haluamme lopettaa tiettyjen cliffhangers, joten aloitamme asettaa vaiheessa useita minuutteja, on hyvin yksinkertainen idea - että vaihtava kahdesta osasta, eikö? Kaikki nämä algoritmit olemme olleet puhumme parin viime luentoja osallistuu noin tavallaan vaihtamalla. Tänään se oli visualisoitu niitä saada ylös niiden puheenjohtajat ja käveleminen, mutta koodi, olisimme ota elementti yhdestä array ja plop se toiseen. Miten siis edetä näin? No, anna minun mennä eteenpäin ja kirjoittaa nopea ohjelma täältä. Aion mennä eteenpäin ja tehdä tätä seuraava. Kutsun tätä - mitä haluamme kutsua tämä? Oikeastaan ​​ei. Minäpä taaksepäin. En halua tehdä sitä jännitysnäytelmä vielä. Se pilaa hauskaa. Tehdään tämä sijaan. Oletetaan, että haluan kirjoittaa hieman ohjelma ja että nyt kattaa tämän Ajatus rekursio. Olen sellainen sai ennen itseäni siellä. Aion tehdä seuraavasti. Ensinnäkin, nopea ovat standardin io.h, sekä include of cs50.h. Ja sitten aion mennä eteenpäin ja julistaa int main void tavalliseen tapaan. Tajusin olen väärin nimetty tiedosto, niin haluan vain lisätä. c laajennus täällä niin että voimme kääntää sen oikein. Aloittaa tämän toiminnon pois päältä. Ja toiminto Haluan kirjoittaa, varsin yksinkertaisesti, on yksi, joka kysyy käyttäjän numero ja lisää jopa kaikki numerot välillä että numero ja vaikkapa 0. Ensin aion mennä eteenpäin ja julistaa int n. Sitten voin kopioida koodia että olemme käyttäneet jonkin aikaa. Vaikka jokin on totta. Tulen takaisin hetken päästä. Mitä haluat tehdä? Haluan sanoa printf positiivinen kokonaisluku kiitos. Ja sitten aion sanoa n saa saada int. Joten jälleen, jotkut boilerplate koodi että olemme käyttäneet ennen. Ja aion tehdä tämän kun n on pienempi kuin 1. Joten näin varmistetaan, että käyttäjä antaa minulle positiivinen kokonaisluku. Ja nyt aion tehdä seuraavaa. Haluan lisätä jopa kaikki numerot välillä 1 ja ja n, tai 0 ja n, yhtäpitävästi, saada kokonaissummasta. Joten iso sigma symboli että saatatte muistaa. Joten aion tehdä tämän ensimmäistä tehtäväänsä toiminto nimeltään sigma, kulkee sen n, ja sitten aion sanovat printf, vastaus on oikeassa. Joten lyhyt, saan ja int käyttäjältä. Varmistan se on positiivista. Julistan muuttuja nimeltä vastausta int ja säilytä se tuotto arvo sigma, ohimennen n tulona. Ja sitten tulostaa, että vastaus. Valitettavasti, vaikka sigma kuulostaa jotain, joka voisi olla math.h tiedosto, sen julistuksen, se ei todellisuudessa ole. Niin se on OK. Voin toteuttaa tämän itse. Aion toteuttaa toiminto nimeltään sigma, ja se tulee ottaa parametri - Haluan vain kutsua sitä m, vain joten se on erilainen. Ja sitten täällä, aion sanoa, hyvin, jos m on pienempi kuin 1 - tämä on erittäin mielenkiinnoton ohjelma. Joten aion mennä eteenpäin ja välittömästi palautettava 0. Se vain ei ole mitään järkeä lisätä jopa kaikki numeroita välillä 1 ja m, jos m itse 0 tai negatiivinen. Ja sitten aion mennä eteenpäin ja tehdä tämän hyvin iteratiivisesti. Aion tehdä tällaista vanhan koulukunnan, ja aion mennä eteenpäin ja sanoa, että aion julistaa summa on 0. Sitten aion olla varten silmukka int - ja anna minun tehdä se vastaamaan meidän jakelu-koodi, joten sinulla on kopio kotona. int i saa 1 asti i on pienempi tai yhtä suuri kuin m. i plus plus. Ja sitten sisällä tämän silmukan - olemme melkein perillä - summa saa summan plus 1. Ja sitten aion palata summa. Tein nopeasti, melko tosin. Mutta jälleen kerran, päätehtävä on melko suoraviivainen perustuva koodi olemme kirjoitettu tähän mennessä. Käyttää kaksoislenkin saada positiivista int käyttäjältä. Sitten tapahtui, että int uusi toiminto kutsutaan sigma, kutsuen sitä taas, n. Ja minä tallentaa palauttaa arvo, vastaus alkaen musta laatikko hetkellä tunnettu sigma, muuttujaan nimeltään vastaus. Sitten voin tulostaa sen. Jos me nyt jatkaa tarinaa, miten sigma toteutetaan? Ehdotan toteuttaa seuraavasti. Ensin hieman virheentarkistava varmistaa, että käyttäjä ei ole Messing minun kanssani ja kulkee joitakin negatiivisia tai 0-arvo. Sitten Julistan muuttuja nimeltä Yhteenvetona ja aseta se 0. Ja nyt alkaa siirtyä i vastaa 1 aina enintään m, koska haluan sisällyttää kaikki numerot yhdestä kautta m, mukaan lukien. Ja sisällä tämä silmukka, en vain summa saa mitä se on nyt, plus arvo i. Plus arvo i. Sivuhuomautuksena, jos et ole nähnyt tätä ennen, on joitakin syntaktisia sokeria tällä linjalla. Voin kirjoittaa tätä plus vastaa i, vain säästää itseäni muutamalla näppäimen painalluksella ja näyttää hieman viileämpi. Mutta siinä kaikki. Se on toiminnallisesti sama asia. Valitettavasti tämä koodi n aio laatia vielä. Jos juoksen tehdä sigma 0, miten am Olen menossa huusin? Mitä se aikoo pidä? Yleisö: [kuultavissa]. DAVID MALAN: Joo, en julistaa toiminto ylös, eikö? C on typerää, että se on omiaan tekee mitä kerrot sen tehdä, ja sinun on tehtävä se tässä järjestyksessä. Joten jos osuin Anna tähän, aion saada varoituksen sigma implisiittinen ilmoitus. Voi, ei ole ongelma. En voi mennä ylös, ja voin sanoa, okei, odota hetki. Sigma on funktio, joka palauttaa int ja se odottaa int syötteenä, puolipiste. Tai voisin laittaa koko toiminto Edellä tärkein, mutta yleensä olin Suosittelen vastaan, että koska se on kiva aina tärkein yläreunassa niin voit sukeltaa suoraan ja tietää, mitä Ohjelma tekee lukemalla tärkein ensin. Joten nyt haluan tyhjentää näytön. Remake sigma 0. Kaikki näyttää tarkistaa. Saanen ajaa sigma 0. Positiivinen muun. Annan sen numeron 3. pitää se yksinkertainen. Niin, että pitäisi antaa minulle 3 plus 2 plus 1, niin 6. Anna, ja olen todellakin saat 6. Voin tehdä jotain suurempaa - 50, 12, 75. Aivan kuten tangentti, aion tehdä jotain naurettavaa kuin todella iso numero, Oh, joka todella toiminut - eh, en usko, että on oikeassa. Katsotaanpa. Katsotaanpa todella sotkea sitä. Se on ongelma. Mitä on tekeillä? Koodia ei ole niin paha. Se on edelleen lineaarinen. Vihellys hyvä vaikutus, vaikka. Mitä on tekeillä? Ole varma, jos olen kuullut sen. Joten se kääntyy pois - ja tämä on niin syrjään. Tämä ei ole ydin Ajatus rekursio. On käynyt ilmi, koska yritän edustavat niin iso numero, useimmat todennäköisesti se tulkitaan väärin by C ole positiivinen luku, mutta negatiivinen luku. Emme ole puhuneet tästä, mutta se Osoittautuu olemassa negatiivisia lukuja maailman lisäksi positiiviseen numeroita. Ja keinoja, joilla voit edustavat negatiivinen luku pohjimmiltaan on, käytät yhden erityisen vähän osoittamaan ylijäämäisenä negatiivinen. Se on hieman monimutkaisempi kuin, että mutta se perusajatus. Joten valitettavasti jos C on hämmentävä yksi näistä bittejä todella tarkoittaa, Voi, tämä on negatiivinen luku, minun loop tässä, esimerkiksi, on itse asiassa koskaan menossa lopettaa. Joten jos olisin itse tulostaa jotain uudelleen ja uudelleen, olisimme nähdä paljon. Mutta jälleen kerran, tämä on lisäksi kohta. Tämä on oikeastaan ​​vain eräänlainen älyllinen uteliaisuus, että tulemme takaisin lopulta. Mutta nyt, tämä on oikea täytäntöönpanon jos oletamme, että Käyttäjä antaa ints että mahtuvat ints. Mutta väitän, että tätä koodia, rehellisesti, voitaisiin tehdä paljon yksinkertaisemmin. Jos tavoitteena käsillä on ottaa useita kuten m ja lisätä jopa kaikki numeroita sen ja 1 tai päinvastoin välillä 1 ja se, Väitän että voin lainata tätä ajatusta, jotka sulautuvat lajitella oli, joka otti ongelman Tämän koko ja jakamalla se osaksi jotain pienempää. Ehkä ei puoli, mutta pienempiä, mutta edustavasti sama. Sama idea, mutta pienempi ongelma. Joten olen todella - haluan tallentaa tiedoston kanssa eri versionumero. Soitamme tämän version 1 sijasta 0. Ja väitän, että voin itse reimplement tämä tämäntyyppisiin aistiharhoja tavalla. Aion jättää osa sitä yksin. Aion sanoa, jos m on vähemmän kuin tai jopa yhtä suuri kuin 0 - Olen vain olemaan hieman enemmän anaali tällä kertaa minun virheentarkistukset - Aion mennä eteenpäin ja palata 0. Tämä on mielivaltainen. Olen vain yksinkertaisesti päättää, jos käyttäjä antaa minulle negatiivinen luku, olen palaavat 0, ja ne olisi pitänyt lukea asiakirjat tarkemmin. Else - huomaa, mitä aion tehdä. Else Aion palata m plus - mikä on sigma m? No, sigma m plus m miinus 1, plus m miinus 2, plus m miinus 3. En halua kirjoittaa kaiken tuon pois. Miksi en vain potkaista? Rekursiivisesti kutsua itseäni hieman pienempi ongelma, puolipiste, ja lopettaa tältä päivältä? Oikea? Nyt täälläkin, saatat tuntea tai huolehtia että tämä on loputon silmukka, että olen asiakkuutta, jolloin olen täytäntöönpanosta sigma soittamalla sigma. Mutta se on täysin OK, koska olen ajattelin eteenpäin lisätty mitkä linjat? Yleisö: [kuultavissa]. DAVID MALAN: 23-26, jotka on minun, jos kunnossa. Koska mitä mukavaa noin vähennyslaskua täällä, koska pidän luovuttamalla sigma pienempiä ongelmia, pienempiä ongelmia, pienempi - se ei ole puolet pienempi. Se on vain vauva pykälää pienempi, mutta se on OK. Koska lopulta, hoidamme Matkalla alas 1 tai 0. Ja kun osuimme 0, sigma ei ole aikoo kutsua itseään enää. Se tulee välittömästi palata 0. Joten vaikutus, jos sellainen tuulen tämän up mielessäsi, on lisätä m + m miinus 1, plus m miinus 2, plus m miinus 3, plus piste, piste, piste, m miinus m, lopulta antaa sinulle 0, ja vaikutus on viime kädessä lisätä kaikkien nämä asiat yhdessä. Joten meillä ei ole, ja rekursio, ratkaista ongelma, että me ei ratkaista ennen. Todellakin, versio 0 tämän ja jokainen Ongelmana on tähän asti ollut ratkaistavissa vain käyttämällä silmukoita tai kun silmukoita tai vastaavia rakenteita. Mutta rekursio, Luulen, antaa meille erilainen tapa ajatella ongelmia, jolloin jos voimme ottaa ongelma, jakaa sitä jotain suurehko jotain hieman pienempi, Väitän, että voimme ratkaista sen ehkä hieman tyylikkäästi kannalta suunnittelu, vähemmän koodia, ja ehkä jopa ratkaisemaan ongelmia, jotka olla vaikeampaa, kuten tulemme lopulta katso, ratkaista puhtaasti iteratiivisesti. Mutta jännitysnäytelmä, että tein halua lähteä meitä oli tämä. Anna minun mennä eteenpäin ja avata up tiedosto - todella, anna minun mennä ja tehdä tämän todella nopeasti. Anna minun mennä eteenpäin ja ehdottaa seuraavat. Tämän päivän koodi on tämä tiedosto tästä. Tämä yksi täällä, noswap. Joten tämä on typerä pieni ohjelma, joka Olen lyöty jopa joka väittää tehdä seuraavat. Main, se ilmoittaa ensin int kutsutaan x ja määrittää sen arvon 1. Sitten se ilmoittaa, int y ja määrittää sen arvo 2. Sitten se tulostaa mitä x ja y on. Sitten se sanoo, vaihtamalla, dot dot dot. Sitten se väittää vaatii toimia nimeltään swap, ohimennen x ja y, ajatus on, että toivottavasti x ja y tulevat takaisin eri, päinvastoin. Sitten se väittää vaihdettu! huutomerkki. Sitten se tulostaa x ja y. Mutta näyttää siltä, ​​että tämä hyvin yksinkertainen esittelyä alas täällä on todella buginen. Vaikka olen julistamisesta väliaikainen muuttuja ja tilapäisesti käyttöön vuonna sitä, niin olen vaihtaminen mille b: n arvo - joka tuntuu kohtuullinen, koska olen tallennettu kopio temp. Sitten voin päivittää b yhdenvertaiseen mikä oli temp. Tällainen kuori peli liikkuvat osaksi b ja b osaksi käyttämällä tätä keski-mies nimeltä temp tuntuu täysin järkevää. Mutta väitän, että kun juoksen tämän koodi, kuten minä teen nyt - anna minun mennä eteenpäin ja liitä se täällä. Soitan tämän noswap.c. Ja kuten nimestä voi päätellä, tämä ei ole olemaan oikea ohjelma. Tee noswap. / Ei swap. x 1, y on 2, vaihtamalla, vaihdoin. x on 1, y on 2. Tämä on täysin väärä, vaikka vaikka tämä vaikuttaa täysin järkevää minulle. Ja siellä on syy, mutta emme ole aikoo paljastaa syy vielä. Nyt toinen jännitysnäytelmä halusin jätä sinua on tämä, ilmoitus tapaisena kuponkikoodeista. Innovaatioiden myöhään päivää tänä vuonna on herättänyt ei-triviaali määrä kysymyksiä, jotka oli Tarkoituksemme ei ole. Tarkoituksena näistä kuponkikoodeista, jolloin jos teet osa ongelmaa asettaa aikaisin, mikä saada ylimääräinen päivä, oli todella auttaa teitä auttaa itse aloittaa aikaisin, sort ja palkitsemalla sinua. Auttaa meitä jakamaan kuormaa poikki virka paremmin niin, että se on eräänlainen win-win. Valitettavasti luulen ohjeet ei ole ollut tähän mennessä hyvin kirkas, niin Menin takaisin tänä viikonloppuna ja päivitetään spec suurempi, rohkeampi teksti selittää luoteja kuin nämä. Ja vain sanoa sen avoimempi, jonka Oletuksena ongelma sarjaa johtuvat torstai keskipäivällä, per oppimäärän. Jos aloitat varhain, viimeistely osa ongelma asettamat keskiviikkona klo 12:00 PM, osa, joka liittyy kuponki koodi, ajatus on, että voit laajentaa teidän määräaika P asettaa vasta perjantaina. Eli hieman pois pieni osa P asettaa siihen, mitä on tyypillisesti suurempi ongelma, ja ostat itse ylimääräinen päivä. Jälleen, se saa sinut ajattelemaan Harjoitus, saa sinut virka nopeammin. Mutta kuponkikoodi ongelma on edelleen tarvitaan, vaikka et lähetä se. Mutta enemmän pakottavan on tämä. (Stage Whisper) Ja ne ihmiset lähtevät alussa tulet katumaan sitä. Koska ovat seudullamme parvekkeella. Pahoittelen jo etukäteen seudullamme parveke syistä, jotka on tyhjentää vain hetken. Joten olemme onnekkaita olla yksi CS50: n entinen johtaja opetus Fellows yritys nimeltä dropbox.com. He ovat hyvin anteliaasti lahjoitti kuponkikoodi täällä näin paljon tilaa, joka on ylös tavallisesti 2 gigatavua. Joten mitä ajattelin tekisimme tästä Viimeinen huomautus on tehdä vähän kylkiäinen, jolloin vain hetki, me paljastaa voittaja ja joka on kuponki koodia, jota voi sitten mennä heidän verkkosivuilla, kirjoita se, ja voila, saada paljon enemmän Dropbox tilaa laite ja henkilökohtaiset tiedostot. Ja ensimmäinen, joka haluaa osallistua tässä piirustuksessa? OK, nyt joka tekee siitä entistä hauskempaa. Henkilö, joka saa tämän 25 gigatavun kuponkikoodi - joka on kaukana enemmän pakottavia kuin myöhään päivän ajan, kenties - on se, joka istuu päälle istuinosan alla, joka on että kuponkikoodi. Voit nyt katsoa alla oman istuintyynyn. [VIDEOTOISTOSTA] -Yksi, kaksi, kolme. [SCREAMING] -Saat auton! Saat auton! DAVID MALAN: Tulemme näkemään keskiviikkona. -Saat auton! Saat auton! Saat auton! Saat auton! Saat auton! DAVID MALAN: Parveke ihmiset, tulevat tänne eteen, jossa meillä on extrat. -Jokainen saa auton! Jokainen saa auton! [END VIDEOTOISTOSTA] Kertoja: Seuraavassa CS50 - SPEAKER 5: Jestas Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh - [Ukelele PLAYS]