[Predvajanja glasbe] DAVID Malan V redu. Vse je v redu, dobrodošli nazaj. Torej, to je 4 teden, začetek Pogodbe, že. In ti boš spomnil, da je prejšnji teden, smo se kodo namenjen le malo in smo začeli govoriti malo več na visoki ravni, o stvareh, kot iskanje in razvrščanje, ki je, čeprav Nekoliko preproste ideje, so Predstavnik vrsti problemov boste začeli zlasti reševanje kot ste začeli razmišljati o končni projekti in zanimive rešitve si morda morali resničnih problemov. Zdaj mehurček vrste je bil eden od najpreprostejših taki algoritmi, in delo, ki ga ob teh majhnih številkah na seznamu ali v matrično vrste mehurček svojo pot do vrha in velike številke premakniti svojo pot navzdol Konec tega seznama. In opozarjajo, da bi lahko vizualizirati bubble sort malo kaj takega. Naj gredo naprej in kliknite Start. Sem predizbere mehurček vrste. In če se spomnite, da je višji modra črte predstavljajo velike številke, mala modre črte predstavljajo majhno število, kot gremo skozi to spet in spet primerjavo dveh palic drug poleg druga v rdeči barvi, bomo zamenjali Največji in najmanjši če so v okvari. Tako da bo ta šel naprej in naprej in iti naprej, in videli boste, da večja Elementi so svojo pot do desno in manjše elementi ki svojo pot na levo. Vendar pa smo začeli količinsko učinkovitosti, Kakovost tega algoritma. In mi je rekel, da je v najslabšem primeru ta algoritem je približno koliko korakov? Torej n kvadrat. In kaj je bilo n? PUBLIKA: Število elementov. DAVID Malan: Tako je n število elementov. In zato bomo to pogosto. Vsak čas želimo govoriti o velikosti o problemu ali velikost vložek, ali koliko časa traja za izdelavo izhod, bova posplošena karkoli Vhod je, kot n. Torej nazaj v tednu 0, število strani V telefonskem imeniku je n. Število študentov V sobi je bil n. Torej tudi tu bomo po da vzorec. Zdaj n kvadrat ni posebej hitro, zato smo poskušali narediti bolje. In tako smo si ogledali nekaj drugi algoritmi, med katerimi so izbor sort. Torej, izbira sort je malo drugačna. Bilo je skoraj enostavnejša, upam si reči, s katerim sem začel na začetku seznam naših prostovoljcev in sem spet in spet in spet šla skozi Seznam, skubljenje od najmanjše element naenkrat in ga dajanje ali jo na začetku seznama. Ampak tudi to, ko smo začeli razmišljati s pomočjo matematike in večjo slika, pomislili kolikokrat Nameraval sem nazaj in naprej in nazaj in tja, smo rekli v najslabšem primeru, izbira sort, preveč, je bilo kaj? n kvadrat. Zdaj v resničnem svetu, bi bilo dejansko nekoliko hitreje. Ker še enkrat, nisem imel, da nazadovanja, ko sem razporejene najmanjši elementi. Ampak, če razmišljamo o zelo velikem n, in Če nekako storiti math kot Jaz sem na krovu, pri čemer n kvadrat minus nekaj, vse ostalo poleg n kvadrat, enkrat n postane zelo velik, ne res toliko pomembno. Tako kot računalniški znanstveniki, smo nekako zamižijo na eno oko, da manjša dejavniki in se osredotočiti le na faktor v izraz, ki se dogaja, da Največja razlika. No, na koncu smo pogledal ob vstavitvi vrste. In to je bila podobna v duhu, ampak namesto skozi ponavljajočim in izberite najmanjši element enega na Tokrat sem namesto da bi vzel v roke, da sem bila obravnavana, in sem se odločil, vse Dobro, ti spadaš sem. Potem sem se preselil na naslednji element in se odločil, da je on ali je pripadal tukaj. In potem sem se preselil naprej in naprej. In mislim, da bi lahko, na poti, premik te fante, da bi naredimo prostor za njih. Tako da je bil neke vrste mentalnega preobrata od izbire vrste, ki smo imenovano vstavljanja vrste. Torej te teme, da se pojavijo v resničnem svetu. Še pred nekaj leti, ko nekateri senator je kandidiral za predsednika, Eric Schmidt je v času uprave Google, dejansko možnost z njim razgovor. In smo mislili delili YouTube Posnetek zate, če bi lahko zavihati volumen. [Predvajanje videa] -Zdaj, senator, da ste tukaj na Googlu, in mi je všeč, da razmišljajo o predsedovanju kot razgovor za službo. [SMEH] -Zdaj je težko dobiti delo kot predsednik. In greste skozi mrzlica zdaj. Prav tako je težko dobiti službo pri Googlu. Imamo vprašanja in vprašamo Naši kandidati vprašanja. In to je eden od Larry Schwimmer. [SMEH] -Mislite, da se hecam? To je tukaj. Kaj je najbolj učinkovit način za razvrstite milijon dva-bitnih števil? [SMEH] No, uh - -Oprosti. Morda bi se morali - -Ne, ne, ne, ne, ne. -To ni - OK. Mislim, bubble sort bi biti napačna pot. [SMEH] [Vzklikati in aplavz] Daj no, kdo mu je to povedal? OK. [END predvajanje videa] DAVID Malan: Torej, tam ga imate. Tako smo začeli količinsko ti teče krat, tako rekoč, z nečim imenovano asimptotska zapis, ki je se sklicujejo le na naš nekakšen preobrat slepo oko na tiste manjše dejavnikov in samo gledaš časa teče, Izvajanje teh algoritmov, kot n postane zelo velik daljšem časovnem obdobju. In tako smo uvedli veliko O. In Big O predstavlja nekaj, kar smo mislili od kot zgornja meja. In dejansko, Barry, lahko znižamo kot mic malo bit? Mi smo se to je zgornja meja. Tako velik O izmed n kvadratov pomeni, da v najslabšem primeru nekaj podobnega Izbor vrste bi potrebovali n kvadratov korake. Ali nekaj takega vstavljanja vrste bi n kvadrat korakov. Zdaj pa nekaj podobnega vstavljanje sort, kar je bilo v najslabšem primeru? Glede na to, matrika, kaj je najhujše Možen scenarij, da bi našli sami soočajo s številnimi partnerji? To je povsem nazaj, kajne? Ker če je popolnoma nazaj, moraš narediti cel kup dela. Ker če ste popolnoma nazaj, boste našli Največji dejavnik tukaj, čeprav spada tja. Torej boste rekli, v redu, v Ta trenutek v času, spadaš sem, tako da ga pusti pri miru. Potem se zavedaš, oh, prekleto, moram premaknil nekoliko manjši element za levo od tebe. Potem moram storiti, da znova in znova in znova. In če sem šel naprej in nazaj, si bi nekako občutek uspešnosti da algoritem, saj nenehno sem shuffling vsem ostalim določa matrika da bi naredili prostor za to. Tako da je v najslabšem primeru. Nasprotno - in to je bil Alpinista zadnji čas - smo rekli, da je vključitev neke je omega česa? Kaj je najboljši primer tek Čas vstavljanja vrste? Torej je dejansko n. To je bil prazen, da smo zapustili na krovu zadnjič. In to je omega n, ker zakaj? No, v zelo najboljšem primeru, kaj je vstavljanje sort bodo predali? No, Seznam, ki je v celoti urejeno že minimalna delo narediti. Toda kaj je boljšega pri vstavljanja vrste je, da zato, ker Tu se začne in odloči, oh, ti si številka ena, spadaš sem. Oh, kakšna sreča. Ti si številka dve. Prav tako spadajo sem. Tretjič, še bolje spadaš sem. Takoj, ko pride do konca psevdokoda Seznam Per vstavitve razvrstite v da smo šli skozi verbalno zadnji čas, je to storjeno. Ampak izbira sort, nasprotno, redno počne kaj? Bo ohranil skozi seznam spet in spet in spet. Ker je bil ključni vpogled le ko ste pogledal vse do konec seznama, ste lahko prepričani, da je element izbrano res trenutno najmanjši element. Torej ti različni modeli duševno konec up prinaša nekaj zelo resničnega sveta razlike za nas, kot tudi ti teoretične asimptotske razlike. Torej, samo da Rekapitulacija, nato pa velik O n kvadrat, smo videli nekaj tak Algoritmi tako daleč. Big O n? Kaj je algoritem, ki bi lahko je dejal, da je velik O n? V najslabšem primeru je potrebno linearna več korakov. OK, linearno iskanje. In v najslabšem primeru, če je element iščeš, ko uporabi linearno iskanje? OK, v najslabšem primeru, sploh ni tam. Ali v drugem najslabšem primeru, to je vse poti na koncu, ki je plus ali minus razlika enem koraku. Torej, na koncu dneva lahko rečemo, da je linearna. Big O n bi bilo linearno iskanje, ker v najslabšem primeru element sploh ni tam ali pa je vse poti na koncu. No, veliki O log n. Nismo govorili zelo podrobno o to, ampak to smo že videli prej. Kaj deluje v tako imenovanih logaritemsko Čas, v najslabšem primeru? Ja, tako binarno iskanje. In binarno iskanje v najslabšem primeru morda element nekje v srednji ali nekje znotraj polja. Ampak ti samo zdi, ko vas razdeli seznam na pol, pri pol, na pol, na pol. In potem voila, da je tam. Ali pa še enkrat, v najslabšem primeru, sploh ni tam. Vendar ne veste, da to ni tam dokler si nekako doseči, da je zadnja spodaj je večina elementov po prepolovitev in prepolovitev in prepolovili. Big O od 1. Tako smo lahko velik O višini 2, velik O 3. Kadarkoli le konstantno število, smo le nekako le poenostaviti da je velik O 1. Čeprav če realno, je potrebno 2 ali celo 100 korakov, če je konstantno število korakov, smo pravkar rekel veliki O od 1. Kaj je algoritem, ki je v veliki O 1? PUBLIKA: Iskanje dolžino v spremenljivko. DAVID Malan: Iskanje Dolžina spremenljivke? PUBLIKA: Ne, dolžina če je to že urejeno. DAVID Malan: Dobro. OK, tako da iskanje dolžino nekaj če dolžina tistega nekaj, kot matrika, ki je shranjena v nekaterih spremenljivko. Saj lahko samo prebrati spremenljivko ali natisniti spremenljivko, ali samo na splošno dostop do te spremenljivke. In voila, da se stalno čas. Nasprotno, mislim nazaj na praske. Misli nazaj v prvem tednu C kliče samo printf in tiskanje nekaj, na zaslonu je nedvomno Časovna konstanta, saj traja le nekateri število CPE prikazati da je besedilo na zaslonu. Ali pa počakajte - to počne? Kako drugače bi lahko modelirati uspešnost printf? Bi kdo rad, da se ne strinjam, da je Mogoče to ni ravno konstanten čas? V kakšnem smislu bi lahko printf teče čas, pravzaprav tiskanje niz na zaslon, je nekaj razen konstantna. PUBLIKA: [neslišno]. DAVID Malan: Ja. Torej je odvisno od naše perspektive. Če smo dejansko razmišljati o vlaganju v printf kot string, in Zato smo merjenje velikosti, ki Vhod po svoji dolžini - tako recimo da dolžina n, kot tudi - verjetno, printf je sam velik O n saj se dogaja, da vas n korakov bo natisniti vsako od teh n znakov, najverjetneje. Vsaj do te mere, da prevzame da morda to je z uporabo zanke for Pod pokrovom. Vendar pa bi morali gledati, da kodo razumeti bolje. In res, ko vi začnete analizira svoje algoritme, boste dobesedno ne samo to. Nekako zrkla svojo kodo, in mislim, O - vse v redu, imam to zanko tukaj ali imam ugnezdene zanke tukaj da bo storil n stvari n-krat, in lahko razvrstite razuma svojo pot s kodo, tudi če je psevdokoda in ne dejanska koda. Torej, kaj pa omega n kvadrat? Kaj je algoritem, ki v najboljšem primer, še vedno je n kvadrat koraki? Ja? PUBLIKA: [neslišno]. DAVID Malan: Torej, izbira sort. Ker v tem problemu res zmanjša na dejstvo, da spet ne vem Našel sem trenutno najmanjši dokler Preveril sem vse darn elemente. Torej omega, recimo, n smo pravkar prišel gor z eno. Vstavitev vrste. Če je seznam zgodi, da je treba sortirati že, v najboljšem primeru imamo samo da en skozi to, na kateri točki smo prepričani. Potem, da bi se omenjeni da je linearna, zagotovo. Kaj pa omega od 1? Katere, v najboljšem primeru, lahko traja nespremenjeno število korakov? Torej linearno iskanje, če si le srečo in element iščete je takoj na začetku seznama, če je to, če ste se začne vaše Linearni prečkanje navedenega seznama. In to velja za število stvari. Na primer, čeprav binarni Iskanje je omega 1. Ker kaj pa če dobiš res darn srečo in zadah-DAB v sredini tvoj array je številka iščete? Tako da boste lahko srečni tam, kot dobro. Ta je, nenazadnje, omega n log n. Torej n log n, nismo zares govorimo o še, ampak - PUBLIKA: zlivanjem? DAVID Malan: zlivanjem. To je bil Alpinista zadnjega časa, kjer smo predlagali, in smo pokazali, vidno, da so algoritmi. In združiti vrste samo ena taka algoritem, ki je bistveno hitrejša kot nekateri od teh drugih fantov. Dejstvo je, zliti kratki ne le Najboljši primer n log n, v najslabšem Primer n log n. In ko imate to naključje omega in velik O počutje isto stvar? Mi lahko dejansko opiše kot tisto, kar je imenuje theta, čeprav je Malo manj pogosti. Ampak to samo pomeni dve meje, V tem primeru so enake. Torej zlivanjem, kaj to Res omejijo na za nas? No, spomnim motivacijo. Dovolite mi, dvigni drugo animacijo, da nismo pogled na zadnjem času. Ta je, enako zamisel, vendar to je malo večji. In jaz grem naprej in poudariti Prvi - imamo vstavljanja vrste na zgoraj levo, nato pa izbor sort, bubble sort, nekaj drugih vrst - lupine in hitro - da se nismo pogovarjali o, in kup in zlivanjem. Torej vsaj poskusiti, da se osredotoči na svoje oči Najboljši trije na levo in nato zlivanjem ko kliknem ta zelena puščica. Ampak bom pustil vse od njih teče, samo da bi vam občutek raznolikosti algoritmi, ki obstajajo na svetu. Bom pustil ta tek le za nekaj sekund. In če se osredotočite vaše oči - izberite algoritem, osredotočiti na to, za samo sekund - boste začeli videvati vzorec, ki ga je izvajati. Merge sort, obvestilo, je končano. Heap sort, hitro urejanje, lupini - Tako se zdi, smo uvedli tri Najhujši algoritmi prejšnji teden. Ampak to je dobro, da smo danes tukaj poglej zlivanjem, ki je eden od Lažje tisti je, da pogledamo, čeprav čeprav bo verjetno bend svoj um Samo malo. Tu lahko vidimo, koliko Izbor vrste zanič. Ampak na flip strani, je zelo preprosto izvajati. In morda za P Set 3, ki je eden od algoritmi ste se odločili za izvedbo Za standardni različici. Popolnoma v redu, popolnoma pravilna. Ampak spet, kot n postane velik, če odločijo za izvajanje hitrejši algoritem všeč zlivanjem, odds so v večji in Večje vhodi, vaša koda je le tekoč teči hitreje. Vaša spletna stran bo delovala bolje. Vaši uporabniki se bodo srečnejši. In tako so ti učinki dejansko daje nam nekaj globlje mislil. Torej, vzemimo si oglejte, kaj spajanje vrsta je pravzaprav vse okoli. Kul stvar je, da se združi razvrščanja je samo to. To je, še enkrat, kaj smo se imenuje psevdokoda, psevdokoda bitje Angleško-podobno skladnjo. In preprostost nekako zanimivo. Torej, na vhodu n elementov - tako, da pomeni le, tukaj je polje. Ima n stvari v njem. To je vse kar si rekel tam. Če je n manj kot 2, vrne. Torej to je samo nepomembna zadeva. Če je n manj kot 2, potem seveda to 1 ali 0, pri čemer stvar je že razporejene ali ga sploh ni, tako da samo vrniti. Ni nič narediti. Tako da je preprost primer, da drobovja off. Drugje, imamo tri korake. Razvrstite levo polovico elementov, razvrščanja desna polovica elementov, in nato združiti razvrščena polovici. Zanimivo tukaj je, da Nekako sem punting, kajne? Tam je nekako krožno definicijo na ta algoritem. V kakšnem smislu je to algoritem je definicija krožna? PUBLIKA: [neslišno]. DAVID Malan: Ja, moj sortiranje algoritem, dveh njegovih korakov "neke nekaj podobnega. "In tako, da Zastavlja Vprašanje, no, kaj bom uporabila razvrstiti levo polovico in desna polovica? In lepota tukaj je, da čeprav še enkrat, to je um-upogibni del potencialno lahko uporabite isto algoritem za razvrščanje levo polovico. Toda počakaj malo. Ko ste povedali, da razvrstite leva polovica, kar sta dva korake bo naslednji? Bomo razvrstite levo polovico levo polovico in desno polovica levo polovico. Prekleto, kako rešiti ta dva polovice ali četrtine, zdaj? Ampak to je v redu. Imamo razvrščanja algoritem tukaj. In čeprav boste morda skrbi, Prvi je to nekako neskončno zanke, da je cikel, ki je nikoli bo na koncu - da se bo na koncu enkrat, kaj se zgodi? Ko je n manj kot 2. Ki sčasoma se bo zgodilo, ker če boste obdržali prepolovi in prepolovitev v prepolovitev te polčasih, zagotovo sčasoma boš do konca s samo 1 ali 0 elementov. Tedaj je ta algoritem pravi, da ste končali. Torej resnično čarobno v tem Algoritem Zdi se, da da je zadnji korak, ki združuje. Ta preprosta ideja, samo združitev dveh Stvari, da je tisto, kar je v končni fazi bo nam omogočajo, da razvrstite niz, recimo, osem elementov. Torej imam osem več stresa Jajca Tu je osem koščke in eno Google Glass - ki lahko obdržim. [SMEH] DAVID Malan: Če bi lahko traja osem prostovoljci, in da vidimo, če lahko igrati to ven, tako. Wow, OK. Računalništvo postaja zabavno. Vse je v redu. Torej, kaj pa vi trije, Največji roko gor. Štiri zadaj. Kaj pa vam bomo narediti trije v tej vrsti? In štiri v ospredju. Torej si osem, pridi gor. [SMEH] DAVID Malan: Jaz sem pravzaprav Ne vem, kaj je. Je obremenilne kroglice? Mizi svetilke? Material? Internet? OK. Torej, pridi gor. Kdo bi rad - naprej prihajajo. Poglejmo. In to vas postavlja v mestu - ste v eni lokaciji. Uh, počakaj malo. 1, 2, 3, 4, 5, 6, 7 - Dobro. Vse je v redu, smo dobri. Vse je v redu, tako da vsi imajo sedež, vendar ne na Google Glass. Dovolite mi, da čakalne vrste te gor. Kako ti je ime? MICHELLE: Michelle. DAVID Malan: Michelle? Vse je v redu, boste dobili izgledal geek, če je to v redu. No, jaz tudi mislim, le za trenutek. Vse je v redu, v pripravljenosti. Smo bili poskuša dohiteti primera uporabe za Google Glass, in smo mislil, da bi bilo zabavno, da pač to, ko so ljudje na odru. Snemali bomo svet iz njihove perspektive. Vse je v redu. Ni verjetno, kaj Google je bilo predvideno. Vse je v redu, če vas ne moti nošenja to v naslednjih neugodnih minut da bi bilo čudovito. Vse je v redu, tako da imamo tu niz elemente, in da matrike, kot na Lističe v te ljudi ' Roke, ki je trenutno nesortirani. MICHELLE: Oh, to je tako čudno. DAVID Malan: To je precej naključno. In čez nekaj trenutkov, da bomo poskušali izvajati zlivanjem skupaj in videli, kje je ključ uvid je. In Trik z zlivanjem je nekaj, kar še nismo prevzel. Smo dejansko potrebovali nekaj dodaten prostor. Torej, kaj se dogaja, še posebej Zanimivo je to, da so ti Fantje se bodo za premikanje malo bit, ker bom za domnevo, da tam je dodatno polje prostora, recimo, takoj za njimi. Torej, če si za svojega predsednika, To je sekundarna polje. Če jih tukaj sedijo, da je primarno polje. Ampak to je vir, ki ga imamo Ne vzvodom doslej z mehurčkom vrsta z izbiro vrste, z vstavljanja vrste. Spomnimo, prejšnji teden, vsi le nekako premešan v mestu. Niso uporabljajte dodatnega pomnilnika. Smo naredili prostor za ljudi, ki jih premikanje ljudi okoli. Tako da je to ključno spoznanje, preveč. Tam je to kompromis, na splošno v računalništva, sredstev. Če želite pospešiti nekaj kot čas, boste morali plačati ceno. In eden od teh cen zelo pogosto prostor, količino pomnilnika ali trdega prostora na disku, ki ga uporabljate. Ali pa, odkrito povedano, znesek časa programer. Koliko časa vam bo, človek, dejansko izvajanje nekaterih bolj zapleten algoritem. Ampak za danes, kompromis je čas in prostor. Torej, če bi vidva Dvigni številke, tako da bomo lahko videli, da ste dejansko ujemanje 4, 2, 6, 1, 3, 7, 8. Odlično. Torej bom poskusil orkester stvari, lahko, če vidva sledite mi tukaj. Torej bom izvajala, prvič, Prvi korak psevdokoda, ki je o vnosu n elementov, če je n manj kot 2 in spet. Očitno je, da ne uporabljata tako da gremo naprej. Torej razvrstite levo polovico elementov. Torej to pomeni, da bom osredotočil moja pozornost za trenutek na to Štirje fantje tukaj. V redu, kaj moram storiti naslednji? PUBLIKA: Razvrstite levo polovico. DAVID Malan: Torej, zdaj moram rešiti leva polovica od teh fantov. Ker je spet prevzel nase v Cilj je, da razvrstite levo polovico. Kako si to naredil? Preprosto sledite navodilom, čeprav čeprav smo to počeli še enkrat. Torej razvrstite levo polovico. Zdaj sem razvrščanje teh dveh fantov. Kaj sledi? PUBLIKA: Razvrstite levo polovico. DAVID Malan: Razvrščanje levo polovico. Torej, zdaj ti, ta stol tukaj je seznam velikosti 1. In kaj ti je že ime? PRINCESS DAISY: Princesa Daisy. DAVID Malan: Princesa Daisy je tukaj. In tako se je že urejeno, ker Seznam je velikosti 1. Kaj moram storiti naslednji? OK, vrniti, ker ta seznam je velikost 1, ki je manjša od 2. Potem, kaj je naslednji korak? In zdaj moraš nekako Vrniti v tvoji glavi. Razvrstite desne polovice, ki je - Kako ti je ime? LINDA: Linda. DAVID Malan: Linda. In kaj naj storimo zdaj, imamo seznam velikosti 1? PUBLIKA: Nazaj. DAVID Malan: Previdno. Vračamo prvi, zdaj tretja korak - in če sem nekako ga opisujejo z zajema dva sedeža zdaj, zdaj sem ima združevanje teh dveh elementov. Torej, zdaj žal, elementi so v okvari. Ampak to je, če proces združevanja začne, da se prepričljivi. Torej, če bi vi stand up za samo Trenutek, bom te potrebujem, v Trenutek, da stopite na stol. In če Linda, ker 2 je manjše od 4, zakaj ne ste prišli okoli prvi? Ostanite tam. Torej Linda, prideš okoli prvi. Zdaj v resnici, če je le niz smo jo lahko samo premaknete v realnem času iz tega stola na tem mestu. Torej, si predstavljajte, da je nekaj konstanta število korakov 1. In zdaj - vendar vas moramo postaviti v Na prvem mestu so tukaj. In zdaj, če bi prišel okoli, kot tudi, da bomo v mestu dveh. In čeprav se to zdi, kot da je pri čemer nekaj časa, kaj je zdaj lepo je da leva polovica leva polovica je sedaj urejeno. Torej, kaj je naslednji korak, če bomo zdaj še nazaj v zgodbi? PUBLIKA: Pravica pol. DAVID Malan: Razvrščanje desne polovice. Torej vidva to morali storiti, kot dobro. Torej, če bi lahko vstane za trenutek? In kako ti je ime? JESS: Jess. DAVID Malan: Jess. OK, Jess je zdaj levo polovici desni polovici. In tako da je seznam velikosti 1. Ona je očitno razporejene. In tvoje ime? MICHELLE: Michelle. DAVID Malan: Michelle je očitno Seznam velikosti 1. Ona je že urejeno. Torej, zdaj se zgodi čarovnija, Postopek združevanja. Torej, kdo bo prvi prišel? Očitno Michelle. Torej, če bi lahko prišel od zadaj. Prostor imamo na razpolago za njo zdaj je takoj za tem stolu tukaj. In zdaj, če bi lahko prišel nazaj, kot tudi, imamo zdaj, da bo jasno, dva polovičke, vsaka velikosti 2 - in samo zavoljo upodobitev je, če bi lahko malo prostora - eden levo polovico tu ena desna polovica tukaj. Še previti v zgodbi. Kaj je naslednji korak? PUBLIKA: Merge. DAVID Malan: Zdaj moramo združiti. Torej OK, zdaj, na srečo smo pravkar sprostila štiri stole. Tako smo dvakrat uporablja toliko pomnilnika, vendar lahko damo flip-flopping med dveh nizov. Torej, katera številka je na prvem mestu? Torej Michelle, seveda. Tako da pridejo okoli in se vaš sedež tukaj. In potem številka 2, je očitno naslednji, tako da boste prišli sem. Številka 4, številka 6. In še enkrat, čeprav je Malo hoje sodeluje, res, bi to lahko zgodi v trenutku, s premikanjem enega - V redu, dobro igral. [SMEH] DAVID Malan: In zdaj smo je v dobrem stanju. Levo polovico celotnega Vhod je sedaj urejeno. Vse je v redu, tako da so ti ljudje imeli Prednost mojega - kako se je na koncu vse punce na levo in vsi fantje na desni strani? OK, torej 'fantje pa zdaj. Torej vas ne bo sprehod skozi ti koraki. Bomo videli, če bomo lahko znova Enako psevdokoda. Če želite, da gredo naprej in stand up, in vi, mi vam mic. Glej, če ne morete ponoviti, kar smo pravkar naredil tukaj na Drugi konec seznama. Kdo mora govoriti najprej ki temelji na algoritmu? Torej, razloži, kaj delaš, preden kar koli stopala gibe. SPEAKER 1: V redu, torej od leta Sem levo polovico levo polovico, se bom vrnil. Kajne? DAVID Malan: Dobro. SPEAKER 1: In potem - DAVID Malan: Komu mic iti naprej? SPEAKER 1: Naslednja številka. ZVOČNIK 2: Torej, jaz sem desna polovica na levi polovici levo polovico, in se bom vrnil. DAVID Malan: Dobro. Vrnete. Torej, zdaj, kaj je naslednje na vrsti za vaju? ZVOČNIK 2: Želimo videti, kdo je manjši. DAVID Malan: Točno tako. Želimo, da se združijo. Prostor bomo uporabili za spajanje , čeprav oni so si v očitno že razporejene, bomo da sledijo isti algoritem. Torej, kdo gre v prvi nazaj? Torej 3, nato 7. In zdaj mic gre s temi fanti, OK? ZVOČNIK 3: Zato sem desno polovico levo polovico in moj je n manj kot 1, tako da sem šele tekoč prehod - DAVID Malan: Dobro. ZVOČNIK 4: Sem prav polovica desno polovico desne polovice, in sem tudi ena oseba, zato sem vrača. Torej, zdaj smo spojiti. ZVOČNIK 3: Torej gremo nazaj. DAVID Malan: Torej, greš v hrbet. Torej 5 gre, potem 8. In zdaj občinstvo, ki je korak moramo sedaj nazaj nazaj v naših glavah? PUBLIKA: Merge. DAVID Malan: Združitev levo in desno polovico polovico začetne levo polovico. Torej, zdaj - in samo, da bi to jasno, narediti malo prostora med vami dva fanta. Torej sedaj, da je na dveh seznamih, levo in desno. Torej, kako bomo zdaj spajanju fantje v prednja vrsta sedežev spet? 3. gre prvi. Potem 5, seveda. Potem 7. in 8. sedaj. OK, zdaj smo? PUBLIKA: Ni storiti. DAVID Malan: Ni storiti, ker Očitno je, da je ostala korak. Ampak še enkrat, zato sem z uporabo tega žargon, kot je "previjanju v tvoji glavi," to je zato, ker je to res kaj se dogaja. Gremo skozi vse te korake, vendar smo nekako premori za Trenutek, potapljanje globlje algoritem, premori za trenutek, potapljanje globlje v algoritem, in Zdaj moramo nekako previjanju v našem možgane in razveljaviti vse te plasti da smo nekako na čakanju. Torej, zdaj imamo dva seznama velikosti 4. Če bi vidva stand up še zadnjič in da malo prostora tukaj jasno, da je to levo polovica original, desna polovica od originala. Kdo je prva številka, ki smo morali potegniti v zadnji? Michelle, seveda. Tako da smo dal Michelle tukaj. In kdo ima številko 2? Številka 2 prihaja na hrbtni strani, kot dobro. Številka 3? Odlično. Številka 4, številka 5, številka 6, številka 7 in številka 8. OK, tako da se mu je zdelo, kot veliko korakov, zagotovo. Zdaj pa da vidimo, če ne moremo potrditi, nekako intuitivno, da je to algoritem bistveno, zlasti n postane zelo velik, kot smo videli z animacijami, je bistveno hitreje. Torej Trdim ta algoritem, v najslabšem primera in tudi v najboljšem primeru je velik O n-krat log n. To pomeni, da je nekaj vidik tega algoritem, ki bo n korake, vendar obstaja še en vidik nekje da ponovitev, da se zanka, ki je log n korakih. Lahko vam bo naš prst na tisto, ki dve številki se nanaša? No, če - kam mic iti? SPEAKER 1: Bi se bo n nas razpada na dva dela - delimo z dve, v bistvu. DAVID Malan: Točno tako. Vsak čas bomo videli v nobenem algoritmu s tem sedaj je bilo to vzorec tako, tako, tako. In to je običajno zmanjša za nekaj, kar je logaritemska osnova dnevnik 2. Vendar pa bi res lahko karkoli, pa se prijavite osnove 2. Zdaj kaj pa n? Vidim, da smo nekako ti razdeljeni Fantje - ti razdeljen, razdeljen vas, ti deli, razdeljeni vas. Kje pa konec prišel? Torej je združevanje. Ker razmišljam o tem. Ko se združi osem ljudi skupaj, pri čemer polovica jih je sklop štirih , druga polovica pa so drugi Komplet štirih, kako si šel o tem združevanje? No, vidva to storila precej intuitivno. Ampak, če sem to storil namesto malo več metodično, morda sem opozoril na skrajno levo oseba najprej moja leva roko, opozoril na skrajno levo osebe od tega polovica s svojo desno roko, in šele nato šel skozi Seznam, ki kaže na najmanjši element vsakič, premikanje moj prst in čez po potrebi po seznamu. Ampak kaj je ključna za to združitev Postopek je jaz primerjavi teh parov elementov. Na desni polovici in z leve pol, jaz niti enkrat nazadovanja. Torej sama spajanje je ob ne več kot n korakov. In kolikokrat si moram storiti, da bi bila združitev? No, ne več kot n, in smo pravkar videl, da s končnim spajanje. In tako, če narediš nekaj, kar traja log n korakih n-krat, ali obratno, to se dogaja, da nam n-krat log n. In zakaj je to bolje? No, če smo že vedeli, da je dnevnik n je bolje kot n - kajne? Videli smo v binarnem iskanju, telefonski imenik Na primer, log n je definitivno bolje kot linearna. To pomeni n-krat log n definitivno boljše kot n-krat drugo n, AKA n kvadrat. In to je tisto, kar na koncu občutek. Tako velik aplavz, če smo lahko za te fante. [APLAVZ] DAVID Malan: In tvoji Razdjeljak darila - lahko obdržali število, če bi želeli. In tvoj slovo darilo, kot ponavadi. Oh, in smo vam bo poslal posnetkov, Michelle. Hvala. Vse je v redu. Pomagaj si na stres žogo. In mi potegnite navzgor, v tem času, naš prijatelj Rob Bowden, da ponudijo nekoliko drugačen pogled na to, saj si lahko misliš o teh koraki dogaja v nekoliko drugačen način. V resnici, set-up za to, kar je približno Rob da nam pokaže, predpostavlja, da smo jih že storili tako sestavljajo velik seznam na osem manjših seznamov, vsaka od velikosti 1. Torej smo spreminja psevdokoda malo samo da nekako priti na Osnovna ideja o tem, kako združuje dela. Toda čas kaj teče on je na tem, da je še vedno bo enaka. In spet, set-up tukaj je, da je on začeli z osmimi sezname velikosti 1. Torej ste zamudili del, kjer se je dejansko opravljeno log n, log n, log n delitvijo na vhodu. [Predvajanje videa] -To je to za en korak je. Za drugi korak, večkrat združi pare seznamov. DAVID Malan: Hm. Samo zvok prihaja iz mojega računalnika. Dajmo še enkrat poskusiti. -Samo samovoljno izbirati, katere - Zdaj imamo štiri sezname. Naučite prej. DAVID Malan: Takole. Združitev-108 in 15, smo na koncu s seznama 15, 108. Združitev 50 in 4, smo končajo s 4, 50. Združitev 8 in 42, smo končajo z 8, 42. In združitvijo 23 in 16, smo na koncu z 16., 23.. Zdaj vsi naši seznami velikosti 2. Opazili, da vsak štirje seznami so razvrščeni. Torej lahko začnemo združitvijo parov seznamov znova. Združitev 15 in 108 ter 4 in 50, smo najprej vzeti 4, nato 15, nato 50, nato 108. Združitev 8, 42 in 16, 23, moramo najprej sprejeti 8, nato 16, nato 23, nato 42. Torej, zdaj imamo samo dve sezname velikosti 4, od katerih je vsak razporejene. Torej, zdaj imamo združevanje teh dveh seznamov. Najprej smo vzeli 4, nato pa vzamemo 8, potem smo vzeli 15, nato 16, nato 23, nato 42, nato 50, nato 108. [END predvajanje videa] DAVID Malan: Spet obvestilo, nikoli dotaknila določeno posodo več kot enkrat Po napreduje zunaj njega. Torej še nikoli ponoviti. Torej, on je vedno gibljejo na strani in to je, če imava n. Zakaj ne pustite me dvigni eno animacijo da smo videli zgoraj, vendar tokrat osredotoča le na zlivanjem. Dovolite mi, da gredo naprej in povečavo V zvezi s tem tukaj. Najprej naj izberejo naključno vhod, poveličevati to, in si lahko nekako videti kar je samoumevno, prej, zlivanjem dejansko počne. Tako opazili, da ste dobili te polčasih ali te četrtine ali ti osmine Problem, ki naenkrat začnete jemati dobri formi. In potem na koncu, boste videli na Zelo konec, da bam, vse je združila skupaj. Torej so to le trije različni je na isti zamisli. Ampak ključno spoznanje, tako kot ločnice in vladaj v prvi razred, je bil, da smo se odločili, da nekako razdeliti problem v nekaj velikega, v kar nekako enaka v duhu ampak manjši in manjši in manjši in manjši. Zdaj pa še en zabaven način, da nekako mislim, o njih, čeprav to ni bo dal enako intuitivno razumevanje, je naslednja animacija. Torej je ta video je nekdo dal skupaj , ki so povezana različna zvoki z različnimi postopki za vstavljanje sort, za urejanje z zlivanjem, in za nekaj drugih. Torej, v tem trenutku, bom udaril Play. To je približno dolg minuto. In čeprav še vedno lahko vidite Vzorci se dogaja, tem času lahko tudi slišati, kako so ti algoritmi opravljanju drugače in z Nekoliko različni vzorci. To je vstavljanje vrste. [TONES IGRANJE] DAVID Malan: Spet se poskuša vstaviti vsak element na mesto, kamor spada. To je bubble sort. [TONES IGRANJE] DAVID Malan: In lahko nekako počutim kako relativno malo delo, ki ga počne za vsak korak. To je tisto, kar tediousness sliši. [TONES IGRANJE] DAVID Malan: To je izbor sort, kjer izberete element, ki ga želimo skozi znova in znova in znova in dajanje na začetku. [TONES IGRANJE] DAVID Malan: To je združiti vrste, ki lahko zares začutite. [TONES IGRANJE] [SMEH] DAVID Malan: Nekaj ​​se imenuje gnome sort, ki jih nismo pogledal. [TONES IGRANJE] DAVID Malan: Torej, da vidim, zdaj, raztresen, kot si upamo so jih glasbo, če bom lahko porinil malo malo matematike tukaj. Torej je Četrti način, da bomo lahko pomislite, kaj to pomeni, da ti naloge, ki se hitreje od tistih, , ki smo jih videli prej. In če ste prihajajo v času od matematika ozadje, si pravzaprav vem, morda je že, da si Lahko slap izraz na to tehniko - sicer rekurzija, funkcija da se nekako kliče. In spet opozoriti, da zlivanjem psevdokoda je rekurzivna v smislu da je eden od korakov zlivanjem je je, da pokličete vrste - da je sama. Ampak na srečo, ker smo ohranili kliče vrste ali zlivanjem, Natančneje, v manjši in manjši in manjši seznam, bomo na koncu dno, hvala za tisto, kar imenujemo osnovna, težko kodiran primeru, da omenjeni če seznam je majhna, manj kot 2 v tem primeru le vrnil takoj. Če ne bi imeli to poseben primer, Algoritem bi nikoli dno ven, in ti bi dejansko dobili v neskončna zanka resnično večno. Recimo, da želimo, da sedaj dajo nekatere številke o tem, še enkrat, z uporabo n kot je velikost vnosa. In sem te hotel vprašati, kaj je Skupni čas sodeluje pri teče zlivanjem? Ali bolj na splošno, kaj je stroški pa v času? No, to je precej težko izmeriti, da. Če je n manj kot 2, ki je vpletena čas V sortiranje n elementov, kjer je n 2, je 0. Ker smo pravkar vrnil. Ni treba kaj postoriti. Zdaj verjetno, morda je še korak ali dva korake, da ugotovimo količino delo, ampak to je dovolj blizu 0, da Jaz sem samo reči, no delo potrebna, če je seznam tako majhen ne zanimajo. Ampak v tem primeru je zanimivo. Rekurzivni primer je podružnica psevdokoda tem je dejal še, neke leva polovica razvrstite desno pol, združila dve polovici. Zdaj zakaj se ta izraz predstavljati, da je račun? No, T n pomeni le Čas je, da razvrstite n elementov. In nato na desni strani enačaj tam, T n razdelimo po 2 se nanaša na stroške za kaj? Razvrščanje levo polovico. Drugi T n deljeno z 2 je domnevno nanašajo na stroške razvrstite desno polovico. In potem plus n? Se združujejo. Ker če imate dva seznama, eden od velikost n več kot 2 in drugega velikosti n več kot 2, moraš v bistvu dotik vsak od teh elementov, tako kot Rob dotakne vsakega od skodelic, in samo kot smo poudarili na vsaki Prostovoljci na odru. Torej je n stroške združevanja. Zdaj žal, ta formula je tudi sama rekurzivno. Torej, če je vprašal, če je n, recimo, 16, če je 16 ljudi na odru ali 16 skodelic v videu, koliko skupaj koraki traja, da jih razvrstite z zlivanjem? To je pravzaprav ni očiten odgovor, ker zdaj moraš nekako rekurzivno odgovoriti na to formulo. Ampak to je v redu, ker mi predlagamo da bomo naslednje. Čas je izbral rešiti 16 ljudi, ali 16 skodelic se bo predstavljal splošno kot T 16. Ampak to je enako, glede na naše Predhodna formula, 2-krat znesek Čas, ki je potreben za razvrščanje 8 skodelice plus 16. In spet, plus 16 je čas, da se združijo, in dvakrat T 8 je Čas je, da razvrstite levo polovico in desno polovico. Toda tudi to ni dovolj. Moramo, da se potopite globlje. To pomeni, da moramo odgovoriti Vprašanje, kaj je T 8? No T 8 je samo 2 Časovni T 4 plus 8. No, kaj je T 4? T 4 je le 2-krat T 2 plus 4. No, kaj je T 2? T 2 je le 2-krat T 1 plus 2. In spet smo nekako dobili zaljubljen v tem ciklusu. Ampak to je približno zadeti, da tako imenovani osnovni primer. Ker kaj je T 1, ni trdimo? 0. Zdaj končno lahko delamo nazaj. Če T 1 je 0, lahko zdaj iti nazaj gor en poravnati s tem tipom sem in sem lahko plug 0 za t 1. Torej to pomeni, da je enaka 2 krat nič, sicer znan kot 0, plus 2. In da celo izraz je 2. Zdaj, če vzamem t 2, katerega odgovor je 2, ga priključite na srednjo črto, T od 4, ki mi daje 2-krat 2 plus 4, tako 8. Če sem nato priključite 8. do prejšnja linija, ki mi daje 2 krat 8, 16. In če potem še, da se z 24, tako da v 16., smo končno dobili vrednost 64. Zdaj, samo po sebi nekako govori nič do n zapisu velik O, omega, da smo jih je govoril. Ampak se je izkazalo, da je 64 dejansko 16, velikost vhodu log osnovo 2 16. In če je to malo poznajo, samo pomislim nazaj, in to bom prišel nazaj da vas na koncu. Če je to osnova dnevnik 2, je kot 2. postavljeno na kaj vam daje 16? Oh, to je 4, tako da je 16-krat 4. In spet, to ni nič takega, če je to je neke vrste meglenem spominu zdaj. Ampak za zdaj, da na veri da je 16 dnevnik 16 64. In tako res, s to preprosto duševno zdravje preveriti, smo potrdili - vendar ne dokazano formalno - da čas teče spajanje vrsta je res n log n. Torej ni slabo. To je vsekakor bolje kot algoritmi smo videli doslej, in to je zato, ker smo vzvodom, ena, tehniko, imenovano rekurzija. Še bolj zanimivo kot to, da Pojem delitve in osvajanje. Še enkrat, zares teden 0 stvari, ki tudi zdaj se ponovilo bolj prepričljiv način. Zdaj zabavno malo vaje, če ste nikoli naredil to - in verjetno ne bi bilo, ker nekako normalno ljudje ne mislijo, da to storijo. Ampak, če grem na google.com in, če je Želim, da se naučijo nekaj o rekurzija, Enter. [SMEH] [Več smeha] DAVID Malan: Bad šala počasi širi. [SMEH] DAVID Malan: Samo v primeru, da je tam. Nisem urok narobe, in tam je šala. Vse je v redu. Pojasnite, da ljudje poleg vas, če to je precej ni kliknil samo še. Ampak rekurzija, bolj na splošno, se nanaša s procesom funkcijo kliče sam, ali bolj na splošno, tako problem v nekaj, kar je lahko rešiti po kosih z reševanjem enaki reprezentativnih težave. No, pa prestavljanje le za trenutek. Radi bi na koncu o nekaterih cliffhangers, zato začnimo, da nastavite faza, za nekaj minut, na zelo preprosto idejo - da z zamenjavo dveh elementov, kajne? Vseh teh algoritmov smo bili govorimo o zadnjih nekaj predavanja vključujejo nekatere neke vrste zamenjavo. Danes je vizualizirali z njihovo pridobivanje največ iz svojih stolov in sprehod okoli, ampak v kodi, bi mi vzemite element iz enega niza Pasti in ga v drugo. Torej, kako bomo šli o tem? No, naj gredo naprej in pisati Hitro program najdete tukaj. Jaz grem naprej in to to kot sledi. Recimo to - Kaj hočemo, da pokličete to? Pravzaprav ne. Dovolite mi nazaj. Ne želim storiti, da Alpinista še ni. To bo pokvaril zabavo. Naredimo to namesto tega. Recimo, da želim napisati malo Program in da zdaj zajema ta Ideja rekurzije. Nekako sem dobil pred sebe tam. Jaz bom naredil naslednje. Prvič, hitro vključujejo standardne io.h, kot tudi vključujejo v cs50.h. In potem bom šel naprej in razglasi int main praznino na običajen način. Sem spoznal, da sem misnamed datoteko, tako da Naj samo dodati. podaljšanje c tukaj, tako da , ki ga lahko pripravijo pravilno. Začeti to funkcijo izklopite. In funkcija želim pisati, precej Preprosto povedano, je tista, ki prosi Uporabnik za številne in nato sešteje vse številke, ki med število in, recimo, 0. Torej, najprej bom šel naprej in razglasi int n. Potem sem kopirati nekaj kode, ki uporabili smo za nekaj časa. Medtem ko je nekaj res. Vrnil se bom na to v trenutku. Kaj hočem narediti? Hočem reči printf pozitiven celo prosim. In potem bom pravijo n dobi dobil int. Torej še enkrat, nekateri boilerplate koda , ki smo jih uporabljali prej. In jaz bom to naredil medtem ko je n manj kot 1. Tako se s tem zagotovi, da uporabnik mi daje pozitivno celo število. In zdaj bom naredil naslednje. Želim, da dodate do vseh številk med 1 in in n, ali 0 in n, ekvivalentno, da bi dobili skupno vsoto. Tako velik simbol sigma da boste morda spomni. Torej bom to naredil tako, da najprej kliče Funkcija Sigma, njegovo posredovanje v n, nato pa bom pravijo printf, odgovor je tam. Torej na kratko, dobim in int od uporabnika. Jaz se zagotovi, da je pozitivna. Izjavljam spremenljivko z imenom odgovor tip int in trgovina v njej povratek Vrednost sigma, ki poteka v n kot vhod. In potem sem izpisal tak odgovor. Na žalost, čeprav sigma sliši kot nekaj, kar bi lahko v math.h datoteke, njena izjava, da je dejansko ni. Tako, da je v redu. Ne morem izvajati to sam. Grem izvajati funkcijo imenovano sigma, in to bo trajalo parameter - kaj je samo call it m, samo tako da je drugačen. In potem je tu gor, bom rekel, in, če je m manj kot 1 - to je zelo nezanimiv program. Tako da sem šel naprej in takoj vrne 0.. To preprosto nima smisla sešteti vse številke od 1 do m, če m sam 0 ali negativna. In potem bom šel naprej in to zelo iterativno. Jaz bom naredil to vrsto old-school, in jaz grem naprej in rekel, da bom razglasi znesek za 0. Potem bom še za zanke int - in mi to storiti za doseganje naših distribucija kodo, tako da boste imeli kopijo doma. int i dobi 1 na do i je manjša ali enaka m. i plus plus. In potem notranjost ta zanka - smo skoraj tam - vsota dobi vsoto plus 1. In potem se bom vrnil vsoto. Zato sem to storil hitro, čisto res. Ampak še enkrat, katerega glavna funkcija je precej preprosta, temelji na kodi, ki smo jih doslej napisal. Uporablja dvojno zanko, da bi dobili pozitiven int od uporabnika. Nato sem mimo tega int na novo funkcijo imenovane sigma, ga kliče, še enkrat, n. In jaz shranjevanje vrne vrednost, odgovor od sedaj črne skrinjice znan kot sigma v variabilni imenovano odgovor. Potem sem ga natisnete. Če bomo zdaj še zgodbo, kako se sigma izvaja? Predlagam, da izvaja takole. Najprej malo napak in zagotoviti, da uporabnik ni zajebavam z mano in poteka v nekatera negativna ali 0 vrednost. Potem sem se razglasi spremenljivko sešteje in jo nastavite na 0. In zdaj sem začel premikati iz i je enak 1. vse tja do vključno m, ker želim, da se vključijo vsi številke od ena do m, vključno. In znotraj tega za zanke, sem naredil Vsota dobi vse, kar je sedaj, plus Vrednost i. Plus vrednost i. Kot prahi, če se niste videli tega prej, obstaja nekaj skladenjsko sladkorja Za te vrstice. To lahko znova kot plus enako i, samo, da sam prihranite nekaj tipkanja in pogledati malo hladnejše. Ampak to je vse. To je funkcionalno enako. Žal pa ta oznaka je ne bo še prevesti. Če sem teči, da sigma 0, kako am Jaz bom dobil nadrla? Kaj se to dogaja, da ni všeč? PUBLIKA: [neslišno]. DAVID Malan: Ja, ni prijavil Funkcija up top, kajne? C je malo butast, ampak samo v tem, da ne, kaj ti povem, da narediti, in ti to storiti v tem vrstnem redu. In tako, če sem udaril Enter tukaj, bom dobili opozorilo o sigma implicitna deklaracija. Oh, ni problema. Lahko grem do vrha in sem lahko rekli, v redu, počakaj malo. Sigma je funkcija, ki vrne int in pričakuje, da bo int kot vstopni, podpičjem. Ali lahko dam celotno funkcijo nad glavno, ampak na splošno, jaz bi odsvetujemo, da zato, ker je lepo, da imajo vedno glavni na vrhu tako lahko potopite v desno in vedo, kaj Program počne z branjem glavni prvi. Torej, zdaj mi počistite zaslon. Remake sigma 0. Vse se zdi, da preverite. Dovolite mi, da teče sigma 0. Pozitivna med. Dal bom številko 3. naj bo enostavno. Tako, da mi je dal 3 plus 2 plus 1, torej 6. Vnesti, in res sem dobil 6. Jaz lahko naredim nekaj večjega - 50, 12, 75. Tako kot tangenta, bom naredil nekaj smešno, kot je res velika Številka, Oh, to je dejansko delal - eh, jaz ne mislim, da je prav. Poglejmo. Kaj je res igraš z njim. To je težava. Kaj se dogaja? Koda ni tako slabo. Še vedno linearna. Žvižganje je dober učinek, čeprav. Kaj se dogaja? Ne vem, če sem to slišal. Tako se izkaže - in to je kot stran. To ni jedro Ideja rekurzije. Izkazalo se je, ker sem poskušal predstavljajo tako veliko število, najbolj verjetno je, da bi razlagala s C kot ne pozitivnim predznakom, ampak negativno število. Nismo govorili o tem, vendar je Izkazalo se je, da so negativne številke v svetu, poleg do pozitivnih številk. In sredstva, s katerimi lahko predstavljajo negativno število v bistvu je, da uporabite enega poseben bit, ki označuje pozitivna nad negativno. To je malo bolj zapleten kot to, ampak to je osnovna ideja. Torej, žal, če C je zmedeno eno teh bitov so dejansko pomeni, oh, to je negativno število, moja zanka Tukaj, na primer, je dejansko še bo prekine. Torej, če bi bil dejansko tiskanje nekaj znova in znova, bi se glej cel kup. Toda tudi to je poleg točke. To je res samo nekakšna intelektualna radovednost, da bomo prišli nazaj na koncu. Toda za zdaj, to je pravilno Izvajanje če predpostavimo, da Uporabnik bo ints , ki se prilegajo v ints. Vendar trdim, da je ta koda, odkrito povedano, bi lahko naredili toliko bolj preprosto. Če je cilj na roki, je, da se število kot m in seštejejo vsi številke med njim in 1 ali obratno med 1 in, Trdim da si lahko sposodim to idejo, da se združijo sortiranje imel, ki je bil ob težave te velikosti in deljenjem v nekaj manjši. Mogoče ne pol, ampak manjši, vendar reprezentativno enako. Enako zamisel, vendar manjši problem. Tako da sem pravzaprav - naj shraniti to datoteko z drugačno številko različice. Poklicali bomo to različico 1 namesto 0. In trdim, da sem lahko dejansko reimplement to v tovrstne um-upogibni način. Bom pustil del njega samega. Jaz bom rekel, če m je manj od ali celo enaka 0 - Grem, da se malo več anal tokrat z mojo napako preverjanje - Jaz grem naprej in vrne 0.. To je poljubna. Jaz sem samo preprosto odloči, če uporabnik mi daje negativno število, sem vračanje 0, in bi moral prebrati Dokumentacija bolj. Drugega - opazili, kaj bom naredil. Sicer se bom vrnil m plus - kaj je sigma od m? No, sigma o m plus minus 1 m, plus minus m 2, plus minus 3 m. Ne želim napisati vse to ven. Zakaj ne bi jaz samo punt? Rekurzivno sam klic z nekoliko manjši problem, podpičje, in za danes? Kajne? Zdaj tudi tu, bi lahko počutite ali skrbi da je to neskončno zanko, da sem indukcije, pri čemer sem izvajanjem sigma ga kliče sigma. Ampak to je popolnoma v redu, ker sem Mislil naprej dodal, katere vrstice? PUBLIKA: [neslišno]. DAVID Malan: 23 do 26, ki če je moj pogoj. Ker tisto, kar je lepo o odštevanje tukaj, ker sem naprej Izročitev sigma manjše težave, manjša Težave, manjši - to ni pol velikosti. Saj je samo otrok korak manjši, ampak to je v redu. Ker na koncu, bomo delo naša pot navzdol na 1 ali 0. In ko smo zadeli 0, sigma ni dogaja, da se več poklical. To se dogaja, da takoj vrne 0.. Torej učinek, če nekako veter to v tvoji glavi, je dodati m plus m minus 1, plus minus m 2, plus minus m 3, plus pika, dot, pika, m minus m, na koncu vam daje 0 in Učinek je na koncu dodati vse te stvari skupaj. Torej nimamo, z rekurzijo, rešiti problem, ki smo ne more rešiti prej. Dejansko verzija 0 tega, in vsak problem danes je bil rešljiv s samo uporabo for zanke ali pa zanke ali podobne konstrukcije. Ampak rekurzija, upam si reči, daje nam drugačen način razmišljanja o Težave, s katerimi se lahko, če vzamemo problem, ga razdelite od nečesa nekoliko velik v nekaj nekoliko manjši, Trdim, da ga bomo lahko rešili morda malo bolj elegantno v smislu zasnove, z manj kode, in morda celo rešili težave, ki bi bo težje, saj bomo sčasoma glej, reševanje zgolj iterativno. Ampak Alpinista, da sem storil želimo, da nas pustite bilo to. Dovolite mi, da gredo naprej in odprite do datotek od - pravzaprav, naj gredo in to storiti zelo hitro. Dovolite mi, da gredo naprej in predlagati Naslednji. Med današnjim koda je ta datoteka tukaj. Ta tukaj, noswap. Torej, to je neumno malo program, ki Sem podžigal, ki trdi, da ne Naslednji. V glavnem, najprej razglasi int imenuje x in ga dodeli vrednost 1. Potem pa izjavlja, int y in dodeli to vrednost 2. Potem se natisne kar x in y. Potem pa pravi, zamenjavo, dot dot piko. Potem pa trdi, da se kliče funkcijo imenuje zamenjavo, ki poteka v x in y, ideja, ki je, upajmo x in y bo ponovno drugačen, nasprotno. Potem pa trdijo, zamenjali! s klicajem. Potem se natisne x in y. Ampak se je izkazalo, da je to zelo preprosta predstavitev navzdol Tu je pravzaprav vozičkom. Čeprav sem o razglasitvi začasne spremenljiva in začasno dajanje v jo, nato pa sem prerazporeditev vrednost b - ki se počuti smiselno, ker sem shrani kopijo v temp. Potem sem posodobiti b, da enako kar je bilo v temp. Ta vrsta shell igro gibljejo v B in B v s tem middle-man imenovano temp počuti popolnoma razumljiva. Vendar trdim, da ko sem teči ta kodo, kot bom pa zdaj - Naj gredo naprej in ga prilepite tukaj. Poklical bom to noswap.c. Kot ime pove, da to ni bo pravilen program. Naredite noswap. / Ne swap. x 1, y 2, zamenjavo, zamenjali. x je 1, je y 2. To je popolnoma narobe, čeprav čeprav se to zdi povsem smiselno, da me. In tu je razlog, vendar nismo bo razkrila razlog samo še. Za zdaj drugi Cliffhanger sem hotel da greš s to, Napoved vrst na kod kuponov. Naša inovacija poznih dneh letos je izzvala nepomembno število vprašanj, kar je bilo ni naš namen. Namen teh kod kuponov, pri čemer, če vam del problema nastavite zgodaj, tako dobili dodaten dan, je res, da bi vi pomagali sami začeli zgodaj, vrste stranskih vas incentivizing. Pomaga nam distribucijo tovora čez Uradne ure bolje, tako da to je nekako win-win. Na žalost, mislim, da mojim navodilom niso bili do sedaj zelo jasno, da Ta vikend sem se vrnil in posodobljene spec v večji, drznejši besedilo k razložiti naboje kot ti. In samo to povedati javnosti bolj po privzete, problem sprejemnikov so posledica četrtek opoldne po predmetniku. Če začnete zgodaj, zaključna dela Problem, ki ga je v sredo ob 12:00 PM, del, ki se nanaša na obrestno mero koda, ideja je, da lahko podaljša poteče rok za P nastavite do petka. To je malo off majhen del P relativne glede na to, kar je značilno večji problem, kupite sami dodaten dan. Spet vam pride razmišljanje o Problem set, vam do gets govorilne ure prej. Ampak koda problem kupon še zahteva, da tudi če ga ne predloži. Ampak bolj prepričljivo je to. (ODER WHISPER) In ti ljudje zapuščajo zgodaj so žal boš. Ker so ljudje na balkonu. Se opravičujem vnaprej ljudska pesem o balkon iz razlogov, ki bodo jasno, čez nekaj trenutkov. Tako da smo srečni, da imajo enega CS50 je nekdanji vodja poučevanje tovariši na podjetje, imenovano dropbox.com. Imajo zelo velikodušno podaril kupon koda tukaj za to toliko prostora, ki je odvisno od Običajni 2 gigabajta. Torej, kaj sem mislil, da bi naredil o tem Končna ocena je narediti nekaj v zibelko, pri čemer vsak trenutek, bomo razkriti zmagovalec in kdo ima kupon kodo, ki jo lahko nato iti na svoje Spletna stran, ga vnesite v, in voila, dobil veliko več Dropbox prostor za vaš aparata in vaših osebnih datotek. In prvi, ki bi želeli sodelovati v tej risbi? OK, zdaj je še bolj zabavno. Oseba, ki prejme ta 25-GB kupon koda - ki je daleč bolj prepričljiv kot prepozno Zdaj dni, morda - je tisti, ki sedi na vrhu sedežne blazine, pod katerimi so da je koda kupona. Sedaj lahko ogledate spodaj vaše sedežne blazine. [Predvajanje videa] -Ena, dva, tri. [Kričanje] Si dobil avto! Dobiš avto! DAVID Malan: Bomo videli ste v sredo. Si dobil avto! Dobiš avto! Dobiš avto! Dobiš avto! Dobiš avto! DAVID Malan: Balkon ljudje, pridite dol s čela kjer imamo statistov. -Vsak dobi avto! Vsakdo dobi svoj avto! [END predvajanje videa] Pripovedovalec: Na naslednjem CS50 - ZVOČNIK 5: O moj bog bog bog bog bog bog bog bog bog bog - [UKELELE Predvaja]