[Přehrávání hudby] DAVID Malan: Dobře. Dobře, vítej zpět. Tak tohle je 4. týden, začátek této smlouvy, již. A budete připomenout, že minulý týden, dáme kód stranou pro jen trochu a začali jsme mluvit trochu víc na vysoké úrovni, o věci, jako je vyhledávání a řazení, které, ač poněkud jednoduché nápady, jsou zástupce skupiny problémů si začne řešit zejména jak začnete přemýšlet o finále projekty a zajímavé řešení, které Možná budete muset reálných problémů. Nyní bublina druh byl jeden z nejjednodušších Takové algoritmy, a to pracoval tím, že tyto malé množství v seznamu nebo v poli typu bublina svou cestu až na vrchol, a vysoká čísla pohybovat jejich cestu až do konec tohoto seznamu. A připomínají, že bychom mohli představit bubble sort trochu něco takového. Tak mě nech jít dál a klepněte na tlačítko Spustit. Jsem předvybrány bublina třídění. A pokud si vzpomínám, že vyšší modrá čáry představují velká čísla, malé Modré čáry představují malé množství, jako projdeme to znovu a znovu a Znovu, porovnat dvě tabulky vedle sebe další v červené barvě, jdeme k výměně největší a nejmenší, pokud jsou mimo provoz. Takže to bude pokračovat dál a dál a jít na, a uvidíte, že čím větší prvky dělají jejich cestu k Dobře, a menší prvky jsou aby jejich cestu na levé straně. Ale začali jsme kvantifikovat účinnost, Kvalita tohoto algoritmu. A my jsme řekli, že v nejhorším případ, tento algoritmus se zhruba, kolik kroků? Tak n na druhou. A co bylo n? DIVÁKŮ: Počet prvků. DAVID Malan: Takže n byl počet prvků. A tak jsme si to často. Kdykoliv chceme mluvit o velikosti o problému nebo velikost vstup, nebo množství času, které trvá produkovat výstup, budeme jen zobecnit, co vstup je pro n. Takže zpátky v týdnu 0, počet stran v telefonním seznamu bylo n. Počet studentů v místnosti n. Takže i zde sledujeme že vzor. Nyní n na druhou není zvláště rychle, takže jsme se snažili udělat lépe. A tak jsme se podívali na pár další algoritmy, z nichž byl výběr sort. Takže výběr byl druh trochu jiný. Bylo to skoro jednodušší, troufám si říci, kdy jsem začal na začátku Seznam našich dobrovolníků a já jen znovu a znovu a znovu procházel seznam, vyloupnutí nejmenší prvek v čase a dávat jej nebo ji na začátku seznamu. Ale i to, když jsme začali uvažovat přes matematiku a větší obraz, myslel na to, kolikrát Byl jsem tam a zpět a zpět a tam jsme si řekli, v nejhorším případě, Výběr druhu, byla taky co? n na druhou. Nyní, v reálném světě, mohou se ve skutečnosti mírně rychlejší. Vzhledem k tomu, znovu jsem nemusel držet backtracking, jakmile jsem řazeny nejmenší prvky. Ale pokud si myslíme, že o velké n, pokud si trochu udělat z matematiky jako Já jsem na desce s n na druhou minus něco, vše ostatní kromě n na druhou, jakmile n dostane opravdu velký, není opravdu záležet. Takže jak počítačových vědců, jsme tak nějak přimhouřit oko menší faktory a soustředit se pouze na faktoru v výraz, který to bude dělat největší rozdíl. No, nakonec jsme se zaměřili při vkládání druhu. A to byl podobný v duchu, ale spíše než jít přes opakované a vyberte nejmenší prvek jeden na Tentokrát jsem místo toho vzal za ruku, že jsem byla řešena, a rozhodl jsem se, všechno Dobře, sem patří. Pak jsem se přesunul na další prvek a rozhodl, že on nebo patřila zde. A pak jsem se přesunul dál a dál. A mohl bych se, po cestě, přesunout tyto lidi, aby se aby pro ně prostor. Takže to bylo něco jako duševní zvrat výběrového druhu, který jsme volal vložení řazení. Takže tato témata se objevují v reálném světě. Ještě před několika lety, kdy určité Senátor se ucházel o prezidenta, Eric Schmidt, v době, kdy generální ředitel Google, skutečně možnost aby ho vyslechnout. A my jsme si řekli, že sdílet YouTube klip pro tebe, kdyby se nám podařilo otočit až hlasitost. [PŘEHRÁVÁNÍ] -Teď, senátor, jste zde na Google, a já jsem rád, že předsednictví jako pohovoru. [Smích] -Teď je to těžké se dostat práce jako prezident. A ty teď procházíš ztuhlost nyní. Je to také těžké získat práci v Google. Máme na otázky a ptáme Naši kandidáti otázky. A tohle je od Larry Schwimmer. [Smích] -Myslíte si, že si dělám legraci? Je to tady. Jaký je nejúčinnější způsob, jak seřadit milion dvě bit celé číslo? [Smích] -No, uh - Je mi líto. Možná, že bychom měli - Ne, ne, ne, ne, ne. -To není - OK. -Myslím, že bublina druhu by je špatný způsob, jak jít. [Smích] [Fandění a potlesk] -No tak, kdo mu to? OK. [END PŘEHRÁVÁNÍ] DAVID Malan: Tak tady to máte. Takže jsme začali kvantifikovat běh krát, abych tak řekl, s něčím tzv. asymptotické notace, která je jen s odkazem na náš druh soustružení slepé oko k těm menším faktorů a jen při pohledu na dobu provozu, výkon těchto algoritmů, jako n dostane opravdu velký v průběhu času. A tak jsme zavedli velký O. a velký O představoval něco, co jsme si mysleli, jako horní mez. A skutečně, Barry, můžeme snížit než mic trochu? Mysleli jsme si, ze je to horní mez. Tak velký O prostředků n mocnin, že nejhorší případ, něco jako Výběr sort by se n čtvercová kroky. Nebo něco podobného vložení druhu by n na druhou kroky. Nyní něco jako vložení sort, co bylo nejhorší? Vzhledem k tomu, pole, co je to nejhorší možný scénář, že byste mohli najít sám tváří v tvář? Je to úplně obráceně, ne? Protože jestli je to úplně dozadu, co musíte udělat spoustu práce. Protože pokud jste úplně dozadu, budete si největší prvkem je zde, a to i když patří tam. Takže se chystáte říct, jo, na tento okamžik v čase, patříte sem, takže nechat to být. Pak si uvědomíte, oh, sakra, musím přesunout o něco menší element nalevo od vás. Pak jsem to dělat znovu a znovu a znovu. A když jsem šel tam a zpět, je by se nějak cítit výkon že algoritmus, protože stále jsem míchání všichni ostatní v pole, aby se prostor pro to. Tak to je nejhorší. Naproti tomu - a to byl cliffhanger poslední době - jsme si řekli, že vložení třídění byla omega čeho? Jaký je nejlepší-case běh čas vložení druhu? Takže je to vlastně n. To byl prázdný, že jsme opustili na desce naposledy. A je to omega n, protože proč? No, v tom nejlepším případě to, co je vložení třídění bude předána? No, seznam, který je zcela řazeny již minimální práci dělat. Ale to, co je hezké o vložení druhu je to, že z důvodu, že zde začíná a rozhodne, oh, ty jsi číslo jeden, patříš sem. Ach, to je štěstí. Ty jsi číslo dvě. Také sem patří. Číslo tři, ještě lepší, Patříš sem. Jakmile se dostane na konec Seznam, na vkládacího SORT v pseudokódu že jsme procházeli slovně Minule se to dělá. Ale výběr druhu, naopak, stále dělá co? Dál v seznamu znovu a znovu a znovu. Protože Klíčovou myšlenkou bylo jen jakmile jste se podíval až do konec seznamu si můžete být jisti, že prvek vyberete byla ve skutečnosti v současné době nejmenší prvek. Tak to různé mentální modely konec up dávat některé velmi reálný svět rozdíly u nás, ale i v těchto teoretické asymptotické rozdíly. Takže jen shrnout, pak velký O n čtvercový, viděli jsme několik takových algoritmy tak daleko. Velký O n? Co je to algoritmus, který by se říci, že velký O n? V nejhorším případě to trvá lineární počet kroků. OK, lineární hledání. A v nejhorším případě, kdy je prvek, který hledáte, pokud použití lineární hledání? OK, v nejhorším případě, to není ani tam. Nebo v druhém nejhorším případě je to úplně na konci, který je plus nebo mínus jeden krok rozdíl. Takže na konci dne, můžeme říci, že je lineární. Velký O n by být lineární vyhledávání, proto, že v nejhorším případě, prvek není to ani tam, nebo je to úplně na konci. No, velký O log n. Nemluvili jsme velmi podrobně o , ale my jsme viděli předtím. Co probíhá v tzv. logaritmický čas, v nejhorším případě? Jo, binární vyhledávání. A binární hledání v nejhorším případě může mít prvek někde střední, nebo někde uvnitř pole. Ale najdete jen jednou vás rozdělit seznam na polovinu, v roce poloviny, na polovinu, na polovinu. A pak ejhle, je to tam. Nebo znovu, v nejhorším případě, to není ani tam. Ale vy nevíte, že to tam není dokud se nějak dostat, že poslední zdola většina prvků podle polovinu a polovinu a snížit. Velký O z 1. Tak bychom mohli o velký O 2, O 3 velké. Kdykoliv budete chtít jen konstantní počet, jsme tak nějak prostě zjednodušit že tak velkou O. 1. I když, pokud realisticky, je potřeba 2, nebo dokonce 100 stupňů, pokud je to konstantní počet kroků, řekneme velký O z 1. Co je to algoritmus, který je ve velkém O. 1? DIVÁKŮ: Hledání délku proměnné. DAVID Malan: Hledání délka proměnné? DIVÁKŮ: Ne, délka pokud je již řazeno. DAVID Malan: Dobrý. OK, takže najít délku něco v případě, že délka tohoto něčeho, jako je pole, je uložen v nějaké proměnné. Protože můžete jen číst proměnnou, nebo vytisknout proměnnou nebo jen obecně přístup k této proměnné. A voila, že trvá konstantní čas. Naopak, myslím, že zpět do nuly. Vzpomeňte si na první týden v C, volání jen printf a tisk něco na obrazovce, je pravděpodobně konstantní čas, protože to prostě trvá určitý počet CPU cyklů ukázat tento text na obrazovce. Nebo čekat - je to tak? Jak jinak bychom mohli modelovat výkon printf? By někdo chtěl nesouhlasit, že Možná to opravdu není konstantní čas? V jakém smyslu by printf běží čas, ve skutečnosti tiskne řetězec na na obrazovce, bude něco jiné než konstantní. DIVÁKŮ: [neslyšitelné]. DAVID Malan: Jo. Takže to závisí na naší perspektivě. Pokud jsme vlastně myslet na vstup do printf jako řetězec, a Proto měříme velikost, která Vstup jeho délkou - tak říkejme že délka n i - pravděpodobně, printf je samo o sobě velký O n , protože to bude trvat n kroky tisknout každý z těchto n znaky, s největší pravděpodobností. Alespoň do té míry, že předpokládáme, že možná to pomocí smyčky for pod kapotou. Ale budeme muset podívat na to kód pochopit lépe. A skutečně, jakmile jste začít analyzovat své vlastní algoritmy, budete doslova dělat jen to. Druh oka kódu a myslím, o - v pořádku, mám tuto smyčku zde nebo mám vnořené smyčky zde že bude dělat věci n n-krát, a můžete seřadit rozumu cestu prostřednictvím kódu, i když je to pseudokódu, a ne skutečný kód. A co omega-n na druhou? Co byl algoritmus, který v nejlepším případ, trvalo ještě n na druhou kroky? Jo? DIVÁKŮ: [neslyšitelné]. DAVID Malan: Takže výběr sort. Vzhledem k tomu, v tomto problému velmi snížena k tomu, že opět nevím Našel jsem nejmenší proud, dokud Zkontroloval jsem všechny zatraceně prvky. Tak omega, řekněme, n, se Přišel s jedním. Vložení sort. Je-li seznam se stane být řazeny již v nejlepším případě budeme muset aby jeden průchod přes to, na kterém místě jsme si jisti. A pak by se dalo říci být lineární, pro jistotu. Co je Omega 1? Co, v nejlepším případě, může trvat konstantní počet kroků? Takže lineární vyhledávání, pokud jste právě štěstí a prvek, který hledáte je hned na začátku seznamu, jestli je to to, kam spuštění lineární průchod z tohoto seznamu. A to je pravda řada věcí. Například, i binární hledání omegou 1. Protože co když opravdu zatraceně štěstí a plácnutí DAB uprostřed vaše pole je číslo jste hledali? Takže můžete mít štěstí tam, stejně. Ten konečně, omega n log n. Tak n log n, my jsme opravdu mluvit o tom, ještě ne, ale - DIVÁKŮ: Sloučit druh? DAVID Malan: Merge sort. To byl cliffhanger poslední době, kde jsme navrhli, a ukázali jsme vizuálně, že existují algoritmy. A sloučit druh jen jeden takový algoritmus, který je v podstatě rychlejší než některé z těchto ostatních kluků. Ve skutečnosti, je krátký spojit nejen nejlepším případě n log n, v nejhorším Případ n log n. A když máte tuto koincidenci omega a velké O je totéž? Můžeme vlastně popisovat to jako to, co je tzv. theta, když je to trochu méně časté. Ale to znamená jen dvě meze, V tomto případě, jsou stejné. Takže sloučit druh, co to Opravdu se redukuje na pro nás? No, vzpomínám motivaci. Dovolte mi, abych vytáhnout další animaci, která jsme se nedíval na minule. Ten, stejný nápad, ale je to trochu větší. A já jdu dál a poukázat na První - máme kurzor na druh vlevo nahoře, pak výběr třídění, bublina třídění, pár dalších druhů - shell a rychle - že jsme spolu nemluvili o, a halda a sloučit druh. Tak se alespoň pokusit zaměřit svůj pohled na první tři vlevo a pak sloučit druh, když kliknu tato zelená šipka. Ale nechám všechny z nich spustit, jen aby dá vám pocit rozmanitosti algoritmy, které existují ve světě. Chystám se nechat to běžet jen na pár vteřin. A pokud se soustředíte vaše oči - vyberte si algoritmus, soustředit se na to jen za sekund - Začnete vidět vzor, který to provádí. Merge sort, oznámení, je hotovo. Heap sort, Quick sort, shell - takže se zdá, jsme představili tři nejhorší algoritmy minulý týden. Ale to je dobře, že jsme tady dnes se na druhu korespondence, který je jedním z koncentrace je snazší je podívat se na, a to i i když to asi bude ohýbat vaše mysl jen trochu. Zde můžeme vidět, jak moc Výběr trochu naštve. Ale na druhou stranu, je to velmi snadno implementovat. A možná pro sadu P 3, to je jedna z algoritmy jste se rozhodli realizovat pro standardní verzi. Naprosto v pořádku, zcela správné. Ale opět, jak n se zvětší, pokud se možnost provést rychlejší algoritmus chtěl sloučit druh, šance jsou větší a větší vstupy, váš kód je jen bude běžet rychleji. Váš web bude fungovat lépe. Vaši uživatelé se bude šťastnější. A tak jsou tyto účinky skutečně dává nám některé hlubší myšlenka. Takže pojďme se podívat na to, co sloučit Třídění je vlastně vše kolem. Super věc je, že sloučení Třídění je právě tento. To je opět to, co jsme tzv. pseudokódu, pseudokódu bytost Angličtina-jako syntax. A jednoduchost je druh fascinující. Takže na vstupu n prvků - tak, že prostě znamená, tady je pole. Je tu n věci v něm. To je vše, co říkáme tam. Jestliže je n menší než 2, vrátit. Tak to je jen triviální případ. Jestliže je n menší než 2, pak samozřejmě je to 1 nebo 0, v tomto případě jde o to je již řazeno nebo neexistující, takže stačí vrátit. Není nic dělat. Takže je to jednoduchý případ trhat off. Jinak máme tři kroky. Řazení levou polovinu prvků, třídění pravá polovina prvků, a pak sloučit seřazené poloviny. Co je zajímavé je to, že Jsem trochu plavit, že jo? Je to něco jako definice v kruhu do tohoto algoritmu. V jakém smyslu je tento algoritmus je definice kruhové? DIVÁKŮ: [neslyšitelné]. DAVID Malan: Jo, můj algoritmus třídění, dva z jeho kroky jsou "druh něco. "A tak to zamlouvá otázka, no, co budu používat třídit levou polovinu i pravá polovina? A nejlepší je, že i když Znovu, toto je mysl-ohýbání část potenciálně, můžete použít stejné algoritmus pro třídění levou polovinu. Ale počkejte chvilku. Když jste řekl, třídit levá polovina, co jsou dva kroky bude dál? Vyřešíme levou polovinu levá polovina a právo polovina levé polovině. Sakra, jak to mám vyřešit ty dva Půlky nebo čtvrtky, teď? Ale to je v pořádku. Máme třídící algoritmus zde. A i když byste mohli starat vůbec Zpočátku to tak trochu nekonečný smyčky, je to cyklus, který nikdy skončí - to bude konec jednou, co se stane? Jakmile n je menší než 2. Který nakonec se stane, protože pokud budete mít na polovinu a snížit na polovinu těchto polovin, určitě nakonec se chystáte na konec s jen 1 nebo 0 prvků. V tom okamžiku, tento algoritmus říká, že je hotovo. Takže magie v této algoritmus se zdá být v že poslední krok, slučování. To jednoduchá myšlenka jen sloučení dvou věci, to je to, co nakonec bude které nám umožní vyřešit řadu, řekněme, osm prvků. Takže mám dalších osm stresové míčky zde osm kousky papíru, a jeden Google Glass - které jsem se udržet. [Smích] DAVID Malan: Kdybychom mohli mít osm dobrovolníků, a uvidíme, jestli to půjde hrát se na to, tak. Wow, OK. Počítačová věda je stále bavit. Dobrá. Tak co vy tři, Největší ruka nahoře. Čtyři v zádech. A co budeme dělat vás tři v této řadě? A čtyři v přední části. Takže si osm, jít nahoru. [Smích] DAVID Malan: Ve skutečnosti jsem nejste jisti, co to je. Je to stresové koule? Na stolní lampy? Materiál? Internet? OK. Tak pojď nahoru. Kdo by chtěl - udržet přichází. Pojďme se podívat. A to vám dává lokalitě - jste na místě jeden. Uh-oh, počkej. 1, 2, 3, 4, 5, 6, 7 - Oh, dobře. Tak jo, jsme v pohodě. Dobře, takže všichni mají sídlo, ale ne na sklo Google. Dovolte mi, abych do fronty tyto nahoru. Jak se jmenujete? Michelle Michelle. DAVID Malan: Michelle? V pořádku, dostanete vypadat geek, jestli je to OK. No, já taky, myslím, jen na chvíli. Dobře, v pohotovostním režimu. Snažili jsme se přijít s případ použití pro Google skla a my si myslel, že by bylo zábavné se prostě to když jsou lidé na jevišti. Budeme zaznamenávat svět z jejich pohledu. Dobrá. Není asi to, co Google určen. Dobře, pokud vám nevadí, že na sobě na dobu příštích nepříjemných minut, že by bylo báječné. Dobře, takže tady máme řadu prvky, a že pole, podle kousky papíru v těchto lidech " ruce, je v současné době netříděný. Michelle: Oh, to je tak divné. DAVID Malan: Je to do značné míry náhodné. A za chvíli se budeme snažit realizovat sloučit dohromady jakousi a zjistit, kde ten klíč je vhled. A trik tady se druhu korespondence je něco, co jsme se dosud předpokládalo. Potřebujeme tedy nějaký prostor navíc. Tak co to bude zejména Zajímavé na tom je, že se jedná kluci budou trochu pohybovat bit, protože budu předpokládat, že je tam navíc pole prostoru, řekněme, hned za nimi. Takže pokud jsou za jejich předsedy, to je sekundární pole. Pokud jste zde sídlil, to je primární pole. Ale to je zdroj, který máme nevyužívají pákový efekt, tak daleko s bublinou druhu, s výběrem druhu, s vkládací druhu. Připomeňme si minulý týden, všichni jen druh míchány na místě. Neměli používat žádnou další paměť. Udělali jsme prostor pro lidi tím, pohybující se lidé kolem. Tak to je klíčový vhled taky. Tam je to kompromis, obecně v výpočetní technika, zdrojů. Chcete-li urychlit něco například čas, budete muset zaplatit cenu. A jedna z těchto cen je velmi často prostor, množství paměti nebo pevného disku, který používáte. Nebo, upřímně řečeno, výše programátor času. Jak dlouho to trvá vám, člověk, skutečně realizovat některé další komplikovaný algoritmus. Ale pro dnešek, trade-off je čas a prostor. Takže pokud jste mohl jen zvednout vaše čísla, takže můžeme vidět, že jste skutečně odpovídající 4, 2, 6, 1, 3, 7, 8. Výborný. Takže budu snažit organizovat věci, může-li jste právě za mnou tady. Takže budu realizovat jednak Prvním krokem tohoto pseudokódu, který je na vstupu prvků n, pokud je n méně než 2, pak se vrátit. Je zřejmé, že není Použít, takže jsme dál. Takže řadit levou polovinu prvků. Takže to znamená, že budu zaměřit své pozornost na chvíli o těchto čtyři chlapi. Tak jo, co mám příště udělat? DIVÁKŮ: Řazení levou polovinu. DAVID Malan: Takže teď musím vyřešit Levá polovina těchto kluků. Protože opět předpokládejme, že na sebe na Cílem je seřadit levou polovinu. Jak to děláte, že? Stačí sledovat instrukce, a to i když děláme to znovu. Takže řadit levou polovinu. Teď jsem třídění tihle dva. Co bude následovat? DIVÁKŮ: Řazení levou polovinu. DAVID Malan: Řazení levou polovinu. Takže teď ty, toto sedadlo zde je seznam velikosti 1. A co že se to jmenuješ? PRINCESS DAISY: Princess Daisy. DAVID Malan: Princezna Daisy je tady. A tak je již řazeno, protože Seznam je velikosti 1. Co mám dělat další? OK, návrat, protože tento seznam je velikost 1, který je menší než 2. Tak co je další krok? A teď jste si na druh ustoupit ve vaší mysli. Řazení pravou polovinu, což je - Jak se jmenujete? LINDA: Linda. DAVID Malan: Linda. A tak to, co budeme dělat teď, máme seznam o velikosti 1? DIVÁKŮ: Návrat. DAVID Malan: Opatrně. Vrátíme se první, a nyní třetí krok - a když jsem se trochu popsat ji zahrnuje dvě místa teď, teď jsem mají sloučit tyto dva prvky. Takže teď bohužel prvky jsou mimo provoz. Ale to je místo, kde proces sloučení začíná být přesvědčivé. Takže pokud jste mohl postavit jen za Okamžik, budu tě potřebuju, v okamžik, krok za svého křesla. A pokud Linda, protože 2 je menší než 4, proč ne Přijedete kolem první? Zůstaň tam. Takže Linda, přijdete asi první. Nyní ve skutečnosti, pokud je to jen pole jsme mohli jen přesunout ji v reálném čase z tohoto křesla tomto místě. Tak si představte, že se nějaká konstanta počet kroků 1. A teď - ale musíme dát do Na prvním místě je zde. A teď, pokud byste mohli přijít kolem, stejně, budeme být v místě dvou. A i když to pocit, že je to přičemž na chvíli, co je pěkné je nyní že levá polovina levá polovina je nyní řazeny. Takže jaký byl další krok, když jsme teď převinout dále v příběhu? Diváků: Pravá polovina. DAVID Malan: Třídit pravou polovinu. Takže vy musíte udělat to stejně. Takže pokud byste mohli postavit jen na chvíli? A Jak se jmenujete? JESS: Jess. DAVID Malan: Jess. OK, takže Jess je nyní vlevo polovina pravé polovině. A tak je seznam velikosti 1. Ona samozřejmě řazeny. A jmenujete? Michelle Michelle. DAVID Malan: Michelle je samozřejmě Seznam velikosti 1. Už je třídit. Takže teď magie stane, proces sloučení. Takže kdo přijde jako první? Je zřejmé, Michelle. Takže pokud jste přišel zadem. Prostor máme k dispozici pro ni teď je hned za téhle židli zde. A teď, když se může vrátit také, nyní máme, aby bylo jasno, dva poloviny, každá o velikosti 2 - a jen pro zobrazení jeho zájmu, pokud by mohlo být trochu prostoru - zbyla polovina tady, jeden Pravá polovina zde. Rewind dále v příběhu. Co krok dál? Diváků: Sloučit. DAVID Malan: Takže teď musíme spojit. Takže OK, takže teď, naštěstí jsme právě uvolnil čtyři židle. Takže jsme použili dvakrát tolik paměti, ale můžeme dát flip-flopu mezi dvě pole. Takže, jaké číslo je na prvním místě? Takže Michelle, samozřejmě. Tak pojď se kolem sebe a vzít vaše sídlo zde. A pak číslo 2 je zřejmě Dále, pokud jste sem přišel. Číslo 4, číslo 6. A opět, i když je trochu chůze zapojen, Opravdu, mohly by stát okamžitě, pohybem jednoho - OK, dobře hrál. [Smích] DAVID Malan: A teď jsme v dobrém stavu. Levá polovina celého Vstup byl nyní řazeny. Dobře, takže tito lidé měli Výhodou mého - jak to skončí všechny holky na doleva a všichni kluci na pravé straně? OK, takže kluci 'se nyní. Nebudu vás provede tyto kroky. Uvidíme, jestli se nám podaří znovu stejný pseudokódu. Chcete-li jít dopředu a vstát, a vy, dovolte mi, abych vám mikrofon. Uvidíme, jestli nemůže replikovat to, co Prostě jsme tady na Druhý konec seznamu. Kdo potřebuje mluvit jako první, na základě algoritmu? Takže vysvětlit, co děláte, než provedete nohy pohyby. SPEAKER 1: Dobře, takže od té doby Jsem Levá polovina levá polovina, vrátím. Je to tak? DAVID Malan: Dobrý. SPEAKER 1: A pak - DAVID Malan: Kdo mic jít dál? SPEAKER 1: Další číslo. SPEAKER 2: Tak jsem pravá polovina na levé polovině levá polovina, a já jsem se vrátit. DAVID Malan: Dobrý. Vrátíte se. Takže teď, co je další pro vás dva? SPEAKER 2: Chceme zjistit, kdo je menší. DAVID Malan: Přesně tak. Chceme spojit. Prostor budeme používat ke sloučení vás do, i když jsou samozřejmě řazeny už jdeme podle stejného algoritmu. Tak kdo jede zpět jako první? Takže 3 a potom 7.. A teď jde mic na ty chlapy, OK? SPEAKER 3: Takže jsem pravá polovina levá polovina, a moje je n menší než 1, takže jsem jen tak projít - DAVID Malan: Dobrý. SPEAKER 4: Jsem pravá polovina pravá polovina pravé polovině, a já jsem také jeden člověk, takže jsem chystá k návratu. Takže teď jsme sloučit. SPEAKER 3: Tak jdeme zpátky. DAVID Malan: Takže jdete do zad. Takže 5 jde první, a pak 8. A teď publikum, což je krok musíme se přetočit zpět v našich myslích? Diváků: Sloučit. DAVID Malan: Sloučení levé a pravé poloviny polovinu původního levé polovině. Takže teď - a jen proto, aby to bylo jasné, aby trochu prostoru mezi vámi dva kluci. Takže teď, že to jsou dva seznamy, doleva a doprava. Tak jak jsme se spojit ty lidi do Přední řada sedadel znovu? 3. jde první. Pak 5, samozřejmě. Potom 7, 8 a teď. OK, a teď jsme? Diváků: nedělá. DAVID Malan: Není udělal, protože samozřejmě, je tu jeden krok zbývá. Ale znovu, důvod, proč jsem pomocí tohoto žargonu jako "dozadu ve vaší mysli," je to proto, že je opravdu co se děje. Jedeme přes všechny tyto kroky, ale my jsme trochu odmlčel moment, potápění hlouběji do algoritmus, zastavil se na okamžik, potápění hlouběji do algoritmu a teď musíme nějak dozadu v našem mysl a vrátit zpět všechny tyto vrstvy že jsme trochu přidržen. Takže teď máme dva seznamy velikosti 4. Pokud jste mohl postavit jeden poslední čas a aby se trochu prostoru zde bylo zřejmé, že se jedná o levou polovina z originálu, Pravá polovina originálu. Kdo je první číslo, které jsme musí vytáhnout na zadní? Michelle samozřejmě. Takže jsme dali Michelle zde. A kdo má číslo 2? Číslo 2 je na zadní straně stejně. Číslo 3? Výborný. Č. 4, č. 5, č. 6, číslo 7 a č. 8. OK, tak to připadalo jako hodně kroků, pro jistotu. Ale teď uvidíme, jestli nemůžeme potvrdit, nějak intuitivně, že tento algoritmus zásadně, zejména pokud n dostane opravdu velký, jak jsme viděli s animací, je zásadně rychlejší. Takže tvrdím, tento algoritmus, v nejhorším případ a dokonce v nejlepším případě, je velký O n žurnál n krát. To znamená, že tam je nějaký aspekt tohoto Algoritmus, který má n kroků, ale je tu další aspekt, někde že iterace, že smyčky, že trvá log n kroků. Může dáme prst na to, co ti dvě čísla jsou na mysli? No, kde - Kde mic jít? Reproduktor 1: Mělo by log n je lámání nás do dvou - dělení dvěma, v podstatě. DAVID Malan: Přesně tak. Kdykoliv vidíme v každém algoritmu tedy Zatím tam byl tento vzor dělení, dělení, dělení. A je to typicky snížen na něco, co je logaritmická, log základ 2. Ale mohlo by to být opravdu cokoliv, ale přihlásit základ 2. Teď, co o n? Vidím, že jsme trochu rozdělit vás kluci - dělí vás dělí vás, dělí vás dělí vás. Kde se konec pochází? Takže je to sloučení. Protože o tom přemýšlet. Při sloučení osm lidí dohromady, přičemž polovina z nich je sada čtyř a druhá polovina jsou další sada čtyř, jak se vám jít o tom sloučení? No, vy jste to udělal poměrně intuitivně. Ale kdybych to dělal místo toho trochu víc metodicky, možná jsem již uvedl v vlevo osoba nejprve po mé levici ruku, ukázal na levém osoby této poloviny se mé pravici, a jen následně prošel Seznam a ukázal na nejmenší prvek pokaždé, pohybující se přes můj prst a více než v případě potřeby v celém seznamu. Ale co je klíčové o tomto sloučení proces jsem porovnání těchto párů prvků. Z pravé poloviny a zleva poloviny, jsem ani jednou couvat. Takže sloučení sám je při ne více než n kroků. A kolikrát to mám k tomu, že sloučení? No, ne více než n, a my jsme viděl, že s konečnou sloučení. A tak, pokud děláte něco, co trvá log n kroků n-krát, nebo naopak, to nám dá n log n krát. A proč je to lepší? No, když už víme, že protokol n je lepší než n - P? Viděli jsme v binárním vyhledávání v telefonním seznamu Například log n rozhodně lepší než lineární. Tak, že znamená, že n-krát log n je rozhodně lepší než n krát jiný n, n AKA druhou. A to je to, co jsme nakonec pocit. Tak velký potlesk, když Mohli bychom tyto lidi. [APPLAUSE] DAVID Malan: A vaše rozloučení dárky - můžete držet čísla, pokud byste chtěli. A váš dar na rozloučenou, jako obvykle. Jo, a my vám rádi zašleme záběry, Michelle. Děkuju. Dobrá. Poslužte stresu míč. A dovolte mi vytáhnout, do té doby, náš přítel Rob Bowden nabídnout poněkud odlišný pohled na to, protože si můžete myslet o těchto kroky se dějí v poněkud odlišným způsobem. Ve skutečnosti, set-up, co Rob je asi aby nám ukázal, předpokládá, že máme již provádí dělení na velký seznam do osmi menších seznamů, každý z velikosti 1. Takže Měníme pseudokódu trochu, jen aby nějak dostat Základní myšlenkou, jak se sloučení práce. Ale doba chodu co se chystá udělat, je stále bude stejná. A opět, set-up je, že je začala s osmi seznamů velikosti 1. Takže jste vynechal tu část, kde je to vlastně udělal log n, log n log n, dělení vstupu. [PŘEHRÁVÁNÍ] -A je to pro krok jedna. Na druhém kroku, a to opakovaně spojí dva seznamy. DAVID Malan: Hm. Pouze zvuk přichází z mého počítače. Zkusme to znovu. -Jen libovolně vybrat, které - Nyní máme čtyři seznamy. Naučte předtím. DAVID Malan: Tak jdeme. Sloučení-108 a 15, jsme se nakonec s seznam 15, 108. Sloučení 50 a 4, se skončit s 4, 50. Sloučení 8 a 42, se skončit s 8, 42. A sloučení 23 a 16, se skončit s 16, 23. Nyní jsou všechny naše seznamy jsou o velikosti 2. Všimněte si, že každý z čtyři seznamy se třídí. Takže můžeme začít sloučení páry opět kompletní seznam. Sloučení 15 a 108 a 4 a 50, se první se na 4, pak 15, pak 50, pak 108. Sloučení 8, 42 a 16, 23, nejprve se 8, pak 16, pak 23, pak 42. Takže teď máme jen dva seznamy velikosti 4, z nichž každý je tříděn. Takže teď jsme sloučit tyto dva seznamy. Nejprve vezmeme 4, pak se 8, pak budeme mít 15, pak 16, pak 23, pak 42, pak 50, pak 108. [END PŘEHRÁVÁNÍ] DAVID Malan: Opět, oznámení, nikdy dotkl dané šálek více než jednou po postupuje za ní. Takže nikdy opakovat. Takže je vždy v pohybu do strany, a to je, kde jsme dostali náš n. Proč ne, dejte mi vytáhnout jednu animaci které jsme viděli dříve, ale tentokrát zaměřuje pouze na druhu korespondence. Nech mě jít dopředu a zoom do toho tady. Nejprve mi dovolte, abych si vybrat náhodný vstup, zvětšit to, a můžete nějak vidět to, co jsme považovali za samozřejmé, dříve, sloučit druh skutečně dělá. Tak zjistíte, že vám tyto poloviny nebo Tyto čtvrtí nebo ty osminy problém, který se z ničeho nic začnou mít dobrou formu. A nakonec, uvidíte na velmi konec, který bam, vše je spojil. Tak to jsou jen tři různé se na stejnou myšlenku. Ale hlavní pohled, stejně jako rozdělení a podmanit si hned v první třídě, bylo to, že jsme se rozhodli nějak rozdělit problém do něčeho velkého, do něco trochu identické v duchu, ale menší a menší a menší a menší. Nyní další zábavný způsob, jak nějak myslet o nich, i když to není bude vám stejně intuitivní porozumění, je Následující animace. Tak tohle je video někdo dát dohromady jaké jsou spojeny různé zvuků s různými operacemi vložení druhu, pro druh korespondence a na pár dalších. Takže ve chvíli, jdu zasáhnout Play. Je to asi minutu dlouhý. A i když stále můžete vidět vzory děje, tentokrát si můžete také slyšet, jak tyto algoritmy jsou provádění odlišně a s poněkud různé vzory. To je druh vložení. [TÓNY PŘEHRÁVÁNÍ] DAVID Malan: Opět se snaží vložit každý prvek na tam, kam patří. To je bublina druh. [TÓNY PŘEHRÁVÁNÍ] DAVID Malan: A můžete tak nějak pocit jak relativně málo práce to dělá na každém kroku. To je to, co zní jako nudnost. [TÓNY PŘEHRÁVÁNÍ] DAVID Malan: Toto je výběr druhu, kde vyberte element, který chceme do prochází znovu a znovu a znovu a uvedení na začátku. [TÓNY PŘEHRÁVÁNÍ] DAVID Malan: Toto je sloučit druh, který můžete opravdu začít cítit. [TÓNY PŘEHRÁVÁNÍ] [Smích] DAVID Malan: Něco s názvem gnome třídění, které jsme se podíval na. [TÓNY PŘEHRÁVÁNÍ] DAVID Malan: Tak se ukažte, teď, roztržitý, jak jste snad jsou ve hudba, jestli můžu sklouznout trochu Trocha matematiky zde. Takže tam je čtvrtý způsob, který můžeme přemýšlet o tom, co to znamená, že tyto funkcí, které jsou rychlejší než ty že jsme neviděli. A pokud jedete na kurzu od matematika pozadí, můžete vlastně víte, možná už, že jste může plácnout termín na této technice - to rekurze, funkce že tak nějak volá sama sebe. A opět připomenout, že druh korespondence pseudokódu byl rekurzivní v tom smyslu, že jeden z Merge sort v krocích nazval druh - to znamená, že sama o sobě. Ale naštěstí, protože jsme si nechali volání třídit, nebo sloučit druh, specificky, na menší a menší a menší seznam, nakonec jsme dna díky, co budeme nazývat referenční případ, pevně platí, že řekl, že pokud je seznam je malý, menší než 2 V takovém případě si okamžitě vrátí. Pokud bychom neměli mít tento zvláštní případ, Algoritmus by nikdy dna, a vy byste opravdu dostat do nekonečná smyčka opravdu navždy. Ale předpokládejme, že jsme chtěli, aby se dal některá čísla na to, opět za použití n jako velikost vstupu. A chtěl jsem se vás zeptat, co je celkový čas účastní spuštění hromadné korespondence druh? Nebo obecněji, co je náklady na něj v čase? No, je to docela snadné změřit to. Jestliže je n menší než 2, času potřebného pro v třídění n prvků, kde n je 2, je 0. Protože jsme prostě vrátit. Neexistuje žádná práce je třeba udělat. Nyní pravděpodobně, možná je to jeden krok nebo dva kroky, aby zjistili množství práce, ale je to dost blízko 0, že Jen jsem chtěl říct, ne práce vyžaduje-li seznam je tak malý, být nezajímavé. Ale v tomto případě je zajímavé. Rekurzivní případ byl obor pseudokódu, který řekl jinde, třídění levá polovina, třídit právo poloviny, sloučit dvě poloviny. A teď, proč se tento výraz představují, že náklady? No, T n jen znamená, Doba třídit n prvků. A pak na pravé straně rovnítko tam, T n dělí o 2 odkazuje na cenu co? Řazení levou polovinu. Druhý T n děleno 2 je pravděpodobně se odkazovat na náklady seřadit pravou polovinu. A pak n a? Je sloučení. Vzhledem k tomu, máte-li dva seznamy, jeden z velikosti n na 2 a další velikosti n více než 2, máte v podstatě dotýkat každý z těchto prvků, stejně jako Rob dotkl každého z košíčků, a jen jak jsme upozornili na každé Dobrovolníci na jevišti. Tak n je náklad sloučení. Teď bohužel, tento vzorec je také sám rekurzivní. Takže pokud se ptal, je-li n je, řekněme, 16, v případě, že je 16 lidí na jevišti nebo 16 šálků na video, kolik celkem kroky je potřeba, aby třídit Pomocí Seřadit korespondence? Je to vlastně není jasná odpověď, protože teď budete muset nějak rekurzivně odpovědět na tento vzorec. Ale to je v pořádku, protože mi dovolte navrhnout, co děláme následující. Času potřebného pro třídění nebo 16 lidí 16 šálků se bude zastoupen obecně jako T ze dne 16.. Ale to se rovná, podle našich předchozí vzorec, 2 násobek částky čas potřebný k řazení 8 šálků plus 16. A opět, a 16 je čas spojit, a dvakrát T ze dne 8. je Doba třídit levou polovinu a pravé poloviny. Ale znovu, to nestačí. Musíme se do toho ponořit hlouběji. To znamená, že musíme odpovědět otázka, co je t 8? No T z 8 se nachází jen 2 Časy T z 4 plus 8. No, co se t 4? T 4 je jen 2 krát T z 2 plus 4. No, co je t 2? T 2 je jen 2 krát T z 1 plus 2. A opět jsme trochu dostat uvízl v tomto cyklu. Ale je to o tom, že zasáhnout tzv. referenční případ. Protože to, co je t 1, jsme se tvrdí? 0. Takže teď konečně můžeme pracovat pozpátku. Je-li T 1 je 0, teď mohu vrátit do jednoho linky na toho chlapa tady, a mohu zapojte 0 pro T z 1.. Takže to znamená, že se rovná 2 krát nula, jinak známý jako 0, + 2. A tak, že celý výraz je 2.. Teď, když jsem si na T 2, jejichž odpověď je 2, zapojte jej do prostřední řady, T ze dne 4., že mi dává 2 krát 2 a 4, tak 8.. Když jsem pak připojíte 8 na předchozí linka, která mi dává 2 krát 8, 16. A pokud budeme pokračovat, že se 24, tím, že do 16 let, se konečně dostat hodnota 64. Teď, když sám o sobě trochu mluví nic k zápisu n, velký O, omega, že máme o tom mluvili. Ale ukazuje se, že 64 je opravdu 16, velikost vstupu, přihlásit základnu 2 16 let. A pokud je to trochu neznámá, stejně vzpomínat, a to vrátím vám nakonec. Pokud je to log základ 2, je to jako 2 zvýšil na to, co vám dává 16? Oh, to je 4, takže je to 16 krát 4. A opět, není to velký problém, pokud to je trochu mlhavé paměti teď. Ale teď, se na základě víry že 16 protokolu 16 je 64. A tak se skutečně s tímto jednoduchým zdravého rozumu Zkontrolujte, jsme potvrzena - ale ukázalo formálně - že doba chodu sloučení Třídění je opravdu n log n. Takže to není špatné. Je to určitě lepší, než algoritmy jsme viděli doposud, a je to proto, že jsme zadlužuje, jedním, techniku zvanou rekurze. Ale zajímavější než to, že Pojem dělení a dobývání. Opět platí, že opravdu věci, které týden 0 i dnes se opakující v přesvědčivější způsobem. Teď trochu legrace cvičení, pokud jste nikdy nedělal - a pravděpodobně by neměl, protože jaksi normální lidé si nemyslím, že to udělat. Ale když jdu do google.com, a pokud Chci se dozvědět něco o rekurze, Enter. [Smích] [Další smích] DAVID Malan: Bad joke pomalu šíří. [Smích] DAVID Malan: Jen v případě, že tam je. Nechtěl jsem to špatně píše, a tam je ten vtip. Dobrá. Vysvětlete lidem vedle vás, jestli to není zcela kliknul jen zatím. Ale rekurze, obecně se odkazuje do procesu a volání funkcí sama o sobě, nebo obecněji, dělení problém do něčeho, co může být řeší po částech při řešení shodné reprezentativní problémy. Dobře, pojďme přeřadit jen na chvíli. Rádi bychom skončit na určitých cliffhangers, takže pojďme začít s nastavením fázi, po dobu několika minut, na velmi jednoduchém nápadu - to prohození dvou prvků, ne? Všechny tyto algoritmy jsme byli mluví o posledních pár Přednášky zahrnují některé druh vyměňovat. Dnes to bylo vizualizovat jejich získávání se ze svých židlí a chodí, ale v kódu, bychom jen se prvek z jednoho pole a plop to do druhého. Tak jak jsme se jít asi dělá? No, dovolte mi jít dál a psát rychlý program zde. Chystám se jít dál a dělat to je například následující. Řekněme to - Co chceme volat tohle? Ve skutečnosti, no. Nech mě dozadu. Nechci k tomu, že cliffhanger ještě. To bude kazit zábavu. Pojďme na to místo. Dejme tomu, že chci napsat něco program, a nyní zahrnuje tento Myšlenka rekurze. Tak nějak jsem se dostal před sebe tam. Chystám se provést následující kroky. Za prvé, je rychlý standardní io.h, stejně jako patří v cs50.h. A pak budu pokračovat a prohlásit za neplatné int main obvyklým způsobem. Uvědomil jsem si, jsem nesprávně pojmenovaný soubor, takže dovolte mi přidat. c příponu, takže zde že můžeme sestavit správně. Spusťte tuto funkci vypnout. A funkce chci napsat, docela Jednoduše řečeno, je ten, který žádá uživatel pro číslo a pak sečte všechna čísla, která mezi číslo a, řekněme, 0. Takže v první řadě budu pokračovat a prohlašují, int n. Pak jsem zkopírovat nějaký kód, který jsme použili na chvíli. I když je něco pravda. Vrátím se k tomu za chvíli. Co chci dělat? Chci říci printf pozitivní celé číslo, prosím. A pak budu říci, n dostane se int. Takže znovu, někteří standardizovaný kód že jsme použili předtím. A já jdu na to když n je menší než 1. Takže to bude zajistit, že uživatel mi dává kladné celé číslo. A teď budu dělat následující. Chci se sečíst všechna čísla mezi 1 a a n, nebo 0 a n, ekvivalentně, aby celkový součet. Takže velká sigma symbol které by vás mohly vyvolat. Takže budu dělat, tím prvním volání volána funkce sigma, procházet skrz n, a pak budu říkají printf, odpověď je tady. Takže ve zkratce, jsem si a int od uživatele. Já se zajistilo, že je to pozitivní. Prohlašuji proměnnou s názvem odpověď typ int a uložit v něm návrat hodnota sigma, předáním n jako vstup. A pak jsem vytisknout tuto odpověď. Bohužel, i když zní sigma jako něco, co by mohlo být v math.h souboru, jeho prohlášení, je to ve skutečnosti není. Tak to je v pořádku. Mohu provedení tohoto sám. Chystám se realizovat názvem funkce sigma, a že to bude trvat parametr - Řekněme, že m, jen tak to je něco jiného. A pak tady, budu říkat, a, je-li m je menší než 1 - jedná se o velmi nezajímavý program. Takže budu pokračovat a neprodleně vrátit 0. To prostě nedává smysl sečíst všechny čísla mezi 1 a M, jestliže m je sám o sobě 0 nebo negativní. A pak budu pokračovat a to velmi iterativně. Chystám se dělat takovéhle staré školy, a já jdu do toho a říkají, že budu deklarovat částku za 0. Pak budu mít pro smyčce int - a nech mě to udělat tak, aby odpovídala Our distribuce kód, takže máte kopii doma. int i dostane až na 1 i je menší než nebo rovna m. i plus plus. A pak uvnitř tohoto cyklu for - Už jsme skoro tam - Součet dostane částku plus 1. A pak jdu vrátit částku. Tak jsem to udělal tak rychle, docela pravda. Ale znovu, jehož hlavní funkcí je dost jednoduchý, založený na kódu jsme napsal tak daleko. Používá dvojí smyčku, aby se pozitivní int od uživatele. Pak jsem se projít, že int do nové funkce tzv. sigma, volat to opět n. A já uložit návratovou hodnotu, odpověď z černé skříňky v současné době známý jako Sigma, v proměnné volal odpověď. Pak jsem vytisknout. Pokud bychom nyní pokračovat v příběhu, jak je sigma realizován? Navrhuji provést takto. Nejprve trochu kontroly chyb aby se ujistil, že uživatel není probírat se mnou a předáním některé negativní nebo hodnota 0. Pak jsem deklarovat proměnnou s názvem shrnout a nastavte ji na hodnotu 0.. A teď se začne pohybovat i ze rovná 1 celou cestu až do m, protože chci, aby zahrnovala všechny čísla od jedničky do m včetně. A uvnitř tohoto cyklu for, jsem prostě Součet dostane, co je nyní, a hodnota i. Navíc hodnota i. Mimochodem, pokud jste to ještě neviděli dříve, je tu nějaký syntaktický cukr pro tuto linku. Mohu přepsat jako a rovná i, jen zachránit sebe několik klávesových zkratek a podívat se trochu chladnější. Ale to je všechno. Je to funkčně totéž. Bohužel, tento kód je nebude kompilovat ještě. Když jsem běžet, aby sigma 0, jak pm Budu se dostat křičel na? Jaké to bude nelíbí? DIVÁKŮ: [neslyšitelné]. DAVID Malan: Jo, já nepřiznal funkce až nahoře, vpravo? C je tak trochu blbost, v tom, že pouze dělá to, co řeknete to udělat, a vy musíte udělat to v tomto pořadí. A tak když jsem stiskněte klávesu Enter tady, jdu dostat varování o sigma implicitní prohlášení. Oh, není problém. Můžu jít až na vrchol, a mohu říkají, dobře, počkej. Sigma je funkce, která vrací int a očekává, že int jako vstup, středníkem. Nebo bych mohl dát celou funkci nad hlavní, ale obecně, tak bych nedoporučujeme, protože to je hezké vždy hlavní horem, aby se můžete ponořit přímo a vím, co Program dělá čtením hlavní nejdříve. Takže teď mi dovolte vyčistit obrazovku. Remake sigma 0. Vše vypadá, že check-out. Dovolte mi spustit sigma 0. Pozitivní inter. Dám to číslo 3, aby to jednoduché. Tak, že by mi 3 plus 2 plus 1, tak 6. Zadejte, a opravdu jsem si 6. Můžu udělat něco většího - 50, 12, 75. Stejně jako tečnu, budu dělat něco směšné jako opravdu velký číslo, Oh, to skutečně dopadlo - eh, já si nemyslím, že je to pravda. Pojďme se podívat. Pojďme opravdu si s ním. To je problém. Co se děje? Kód Není to tak zlé. Je to stále lineární. Pískání je dobrý účinek, ačkoli. Co se děje? Není si jistý, jestli jsem to slyšel. Tak to dopadá - a to je stranou. To není jádrem Myšlenka rekurze. Ukazuje se, protože já se snažím představují tak velké množství, většina pravděpodobně je to být mylně o C, jako to kladné číslo, ale záporné číslo. Nemluvili jsme o tom, ale je to Ukazuje se, že jsou záporná čísla ve světě navíc do kladných čísel. A prostředky, které můžete představují záporné číslo v podstatě je, že můžete použít jeden speciální bit pro indikaci pozitivní na negativní. Je to trochu složitější, než to, ale to je základní myšlenka. Takže bohužel, pokud C je matoucí z těchto bitů je ve skutečnosti znamená, oh, to je záporné číslo, moje smyčka Zde, například, je ve skutečnosti nikdy bude ukončena. Takže když jsem byl vlastně tisku něco znovu a znovu, bychom vidět spoustu. Ale opět, to je vedle bodu. To je opravdu jen jakýmsi intelektuální zvídavost, že přijdeme zpět nakonec. Ale teď je to správné Implementace pokud budeme předpokládat, že uživatel bude poskytovat ints které zapadají do ints. Ale tvrdím, že tento kód, upřímně řečeno, by se dalo udělat mnohem jednodušeji. Je-li cílem po ruce, je přijmout řadu jako m a sečíst všechny čísla mezi ním a 1, nebo naopak mezi 1 a, tvrdím, že mohu půjčit myšlenku, že sloučení druh měl, který byl s problémy této velikosti a oddělujících do něčeho menšího. Možná ne polovina, ale menší, ale reprezentativně stejné. Stejný nápad, ale menší problém. Takže jsem vlastně - dovolte mi, abych tento soubor uložit s jiným číslem verze. Zavoláme tuto verzi 1 místo 0. A tvrdím, že jsem si vlastně reimplement to v tomto druhu mysl-ohýbání cesta. Chystám se opustit jeho část samostatně. Chystám se říct, jestli m je méně než nebo se může dokonce rovnat 0 - Já jen bude trochu více anální tentokrát s mou kontrolu chyb - Chystám se jít dopředu a vrátí 0. To je libovolná. Jsem prostě rozhodne, zda uživatel mi dává záporné číslo, já jsem vrací 0, a měly by Přečetl dokumentace podrobněji. Else - Všimněte si, co budu dělat. Jinak se budu vracet M plus - co je sigma m? No, sigma M plus M minus 1, a m mínus 2 plus minus 3 m. Nechci psát všechny ty ven. Proč prostě nemůžu pramice? Rekurzivně volat sám s mírně menší problém, středník, a nazývat to den? Je to tak? Teď tady taky, možná máte pocit, strach nebo že se jedná o nekonečnou smyčku, že jsem vyvolávající, kdy jsem prováděcích sigma sigma voláním. Ale to je naprosto v pořádku, protože jsem myslel dopředu přidal které řádky? DIVÁKŮ: [neslyšitelné]. DAVID Malan: 23 až 26, které pokud je můj stav. Protože to, co je hezké o odčítání tady, protože jsem se udržet rozdávají sigma menší problémy, menší problémy, menší - to není poloviční velikosti. Je to jen krůček menší, ale to je v pořádku. Protože nakonec, budeme pracovat naše cesta dolů na hodnotu 1 nebo 0. A jakmile se dostaneme 0, sigma není zavolá sám už ne. Bude to okamžitě vrátí 0. Takže efekt, pokud jste trochu větru tento ve vaší mysli, je přidat M plus m minus 1 plus minus m 2 plus minus m 3 plus tečka, tečka, tečka, m minus m, která vám nakonec 0, a účinek je nakonec přidat všechny tyto věci dohromady. Takže nemáme s rekurze, vyřešit problém, že se nemůže vyřešit dříve. Ve skutečnosti, verze 0 tohoto, a každý problém k dnešnímu dni, byl řešitelný jen s použitím smyčky, nebo když smyčky nebo podobné konstrukty. Ale rekurze, troufám si říct, nám dává jiný způsob uvažování o Problémy, kterým můžeme-li se problém, rozdělit ji z něčeho poněkud velký na něco poněkud menší, tvrdím, že můžeme vyřešit možná trochu více elegantně, pokud jde konstrukce, s méně kódu, a možná i řešit problémy, které by bude těžší, protože my budeme nakonec vidět, řešení čistě iterativně. Ale cliffhanger, že jsem chtít nechat nás na to bylo. Nech mě jít dopředu a otevřete se soubor z - vlastně, nech mě jít a udělat opravdu rychle. Nech mě jít napřed a navrhnout následující. Mezi dnešní kódu je tento soubor zde. Tenhle, noswap. Tak to je hloupý malý program, který Prudce jsem se, že tvrdí, že to následující. V zásadě se nejprve deklaruje int x volal a přiřadí ji hodnota 1. Pak prohlásí, int y a přiřadí mu hodnotu 2. Pak to vytiskne, co x a y je. Pak říká, vyměňovat, dot dot dot. Pak tvrdí, že je volání funkce tzv. swapu a předat x a y, myšlenka je, že snad x a y se vrátí jinak, naopak. Pak to tvrdí zaměnit! s vykřičníkem. Pak se vytiskne x a y. Ale ukazuje se, že právě tato jednoduchá demonstrace dolů zde je vlastně buggy. I když jsem prohlásil dočasný variabilní a dočasně uvedení v to, pak jsem přerozdělení hodnota b - které se cítí rozumné, protože jsem uložili kopii na teplotě. Pak jsem aktualizovat b rovna vše, co bylo v temp. Tento druh hazardní hru pohybující se do b a b na použití tohoto středního muž jménem temp cítí naprosto rozumné. Ale tvrdím, že když jsem tento příkaz kód, jak budu dělat teď - nech mě jít dopředu a vložte jej sem. Zavolám tento noswap.c. A jak již název napovídá, že to není Bude to správný program. Udělat noswap. / Ne swap. x 1, y 2, vyměňovat, prohozeny. x je 1, y je 2.. To je zásadní chyba, a to i i když se to zdá naprosto přiměřené ke mně. A je tu důvod, ale nejsme chystá odhalit příčinu jen zatím. Pro tuto chvíli druhý cliffhanger jsem chtěl nechat se je to, Oznámení druhů na kupon kódů. Naše inovace v pozdních dnů tento rok vyvolalo netriviální počet otázek, který byl Není naším záměrem. Záměrem těchto kupon kódů, přičemž pokud tak učiníte část problému na počátku, a tím získat další den, Bylo to opravdu pomoci vy pomoci sami začít brzy, třídit vedlejších motivace vám. Nám pomáhá distribuovat zatížení mezi úřední hodiny tak, aby lépe Je to něco win-win. Bohužel si myslím, že mé instrukce nebyly do dnešního dne, velmi jasné, takže Vrátil jsem se o tomto víkendu a aktualizovány spec větší, odvážnější textu na vysvětlit kulky, jako jsou tyto. A právě to říci více veřejně, a výchozí, základní problémové okruhy jsou dány čtvrtek v poledne, dle sylabu. Pokud začnete brzy, dokončovací část problém nastavit ve středu v 12:00 PM, ta část, která se vztahuje k kupón kód, myšlenka je, že můžete rozšířit Váš termín pro P nastavit až do pátku. To znamená, že ukousl malou část P nastavit vůči tomu, co je obvykle větší problém a koupit si den navíc. Opět platí, že vás dostane přemýšlet o tom, Problém set, dostane vás do úřední hodiny dřív. Ale kuponu problém je stále nutné, i když nemáte předloží ji. Ale přesvědčivě to je. (Šepotem) A ti lidé odchází Již jsou toho litovat. Jak jsou lidé na balkoně. Omlouvám se předem na lidi na balkon z důvodů, které budou jasné, za chvíli. Tak jsme to štěstí, že jeden z CS50 bývalí kolegové hlava výuky na společnost s názvem dropbox.com. Mají velmi velkoryse darovali kupon kód zde pro tuto tolik místa, která je oproti obvyklé 2GB. Takže to, co jsem myslel, že by to na to Poslední poznámka je to trochu prozradí, přičemž za chvíli budeme odhalit vítěz a kdo má kupón kód, který pak můžete jít na jejich webové stránky, zadejte do, a voila, získat mnohem více prostoru pro vaši Dropbox zařízení a osobních souborů. A první, kdo by se chtěli zúčastnit v tomto obrázku? OK, teď, že je to ještě větší zábava. Osoba, která obdrží tento 25-gigabyte kupon kód - což je mnohem přesvědčivější než pozdě dny teď, možná - je ten, kdo sedí na vrcholu sedák, pod nímž je že kuponu. Nyní se můžete podívat pod Váš sedák. [PŘEHRÁVÁNÍ] -Jeden, dva, tři. [SCREAMING] -Ty si auto! Získáte auto! DAVID Malan: Uvidíme jste ve středu. -Ty si auto! Získáte auto! Získáte auto! Získáte auto! Získáte auto! DAVID Malan: Balkón lidi, no sem na přední straně, kde máme navíc. -Každý dostane auto! Každý dostane auto! [END PŘEHRÁVÁNÍ] Vypravěč: V dalším CS50 - SPEAKER 5: Ach můj bože bože bože bože bože bože bože bože bože bože - [Ukulele HRY]