[Přehrávání hudby] DAVID J. Malan: Tohle je CS50. A to je začátek tří týdnů. Takže máme spoustu vzrušující věci k pokrytí dnes. Mnoho příležitostí pro dobrovolníci se na jevišti. A nakonec, dnes je nejde o kódu vůbec. Ale je to o myšlenkách, a je to o algoritmech, a vlastně přinášet zpět část poučení z týdne nula, kde odvolání, my představil tuto obludnost. A výpůjčky inspirace od toho, pro spuštění řešit stále sofistikovanější Problémy algoritmicky. Ale nejprve pár oznámení. Takže jeden, pokud byste se rádi připojili CS50 personál a spolužáci na oběd tento pátek, jak zde, tak v Cambridge a v New Haven, navštivte kurz je webové stránky, kde je možné URL nalezena. Přednáška bude tuto středu nemůže být tady v Sanders. Bude to on-line pouze, takže naladit na stránkách CS50 je, ať už tady v Cambridge nebo New Haven stejně. A pak problém nastavit dvě je již ve vašich rukou. Pokud jste se potápěl v dosud, dovolte mi nabídnout ostře formulovaný návrh , že zejména nyní, as Problém stanovuje postup, si opravdu chcete začít hned, ne-li fušovat trochu na víkend nebo před kdy se poprvé jít na Pátky, protože budete zjistíte, že to nemusí být nutně stále delší a náročnější na se. Myslím, že zjistíte, že v Obecně platí, že mají tendenci, aby se zhruba zhruba stejné množství času. Ale to rozhodně záleží na studenta, a to závisí na myšlení se kterým k němu přistupovat. Ale vždy, budete běžet proti nějaké zdi, a budete hit nějaký bug, a vy jste jen nebude moci dostat se přes to v určitém okamžiku. A to je velmi cenné, aby bylo možné ustoupit, vrať se další den, jít na pracovní dobu, příspěvek na CS50 Diskutovat nebo podobně, aby skutečně dostat odblokovat. Takže mějte na paměti, že. Spuštění nejdříve to bude možné je to nejlepší, co můžete udělat. Tak tady je místo, kde jsme začali třída, než v týdnu nula. A můžeme dostat dobrovolníka tady, aby mi pomohla najít mikrofony? DOBŘE. Stojí už vzhůru. Pojď nahoru. Hádejte, že to, jak to bude fungovat. Jak se jmenuješ? ALAN ESTRADA: Alan Estrada. DAVID J. Malan: Alan Estrada. Pojď nahoru. Rád tě poznávám. ALAN ESTRADA: Těší mě. DAVID J. Malan: A vy jste tady u nás v týdnu nula, samozřejmě. ALAN ESTRADA: jsem byl. Byl jsem. DAVID J. Malan: Takže byste mohli jít dopředu a najít pro nás Mike Smith, tak rychle, jak je to možné? Tak rychle, jak je to možné. Doslova trhá problém na polovinu, jak budete potřebovat. ALAN ESTRADA: Hm. DAVID J. Malan: Doslova trhání problém na polovinu. ALAN ESTRADA: Oh. Mm. Velmi dobře. DAVID J. Malan: OK. Dobrý. Děkuji. ALAN ESTRADA: Velmi dobře. DOBŘE. DAVID J. Malan: A tak teď, jste ořezaný dolů na polovinu velikosti problému. Teď, jsme až na čtvrtinu. Jste věnovat pozornost na které straně držíme? [Směje se] ALAN ESTRADA: Ano, já think-- DAVID J. Malan: Jaká část jsme v? ALAN ESTRADA: tlumiče, takže. DAVID J. Malan: OK. Ale Mike Smith se děje být po tlumiče. Tak-- [Směje se] Dobře. ALAN ESTRADA: Kde se to díváme? DAVID J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. Malan: Nyní jsme v chirurgické. Nyní lékaři. Now-- ALAN ESTRADA: Let's- pojďme s real. Real. DAVID J. Malan: Real. DOBŘE. Potřebujete-li skutečný. Nyní, která cesta je Mike Smith? ALAN ESTRADA: Tudy. DAVID J. Malan: Kudy? ALAN ESTRADA: Počkejte. M je-- pravdu? Začali jsme with-- DAVID J. Malan: Jo. Oni opustili. Vaše právo. ALAN ESTRADA: Jo. DAVID J. Malan: Takže Mike tady. ALAN ESTRADA: Co? [Směje se] Špatný příklad, chlapi. Litovat. DAVID J. Malan: To bude vyučovat vás vyskočit ze židle. ALAN ESTRADA: Oh. Aha. Mám tě. Mám tě. Aha. Aha. To je-- OK, mám tě. Smith tady? DAVID J. Malan: Smith, děkuji. Takže budu držet vzhlédl Smith? ALAN ESTRADA: Oh, jo. Ne ne ne. Ale ne. To je moje. DAVID J. Malan: Oh, máš Smith. DOBŘE. ALAN ESTRADA: Jo, myslím, dostal Smith tady. Omlouváme se, chlapi. Myslel jsem, že jsme se Michael-- hledali Michaela. Litovat. DAVID J. Malan: To je v pořádku. Dobře, teď jsme do Paccini and Sons. ALAN ESTRADA: Paccini a synové. DAVID J. Malan: Pouze vy a já jsme na toto téma. DOBŘE. Najděte nás Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. Malan: Smith. Jsme v R pro odpadky. ALAN ESTRADA: Odpadky. Aha. Bude to chvíli trvat. [Směje se] DAVID J. Malan: Shoes. Jsme v botách. ALAN ESTRADA: Teď jsme gonna-- DAVID J. Malan: Nice. ALAN ESTRADA: Which-- [Směje se] Oh, to je skvělé. [Směje se] DAVID J. Malan: To je v pořádku. ALAN ESTRADA: Oh, to je dobré. Nemyslím si, že budu mají PSAT kamarády po tomto. DAVID J. Malan: Dobrý. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O, P. DAVID J. Malan: OK. Takže pojďme roztrhat to na polovinu. Je to v pohodě. Tímto končí špatně tak jako tak, protože Mike Smith nebude ve Zlatých stránkách. ALAN ESTRADA: Aw. DAVID J. Malan: Ne, to je v pořádku. Ale pojďme předstírat, že je na této stránce. Takže teď, že jste ořezaný problém dolů na jedné straně, a zjistili jsme, Mike Smith. [Fandění] OK, díky. DOBŘE. To byl mimořádný. Ale to bylo ještě rychlejší než lineární vyhledávání, kde začneme u začátku knihy, a my se pohybují naši cestu zleva doprava, nakonec hledal Mike Smith. A tak, v případě, že telefonní seznam Měl snad 1000 stran, Možná, že by to vzali us 10 nebo tak stránky slzy. Ale můžete mít zadlužuje dotkl předpoklad při všech, které, což znamená že telefonní seznam předem bylo to, co? Diváků: Tříděný. DAVID J. Malan: Je to třídit. Je to tak? Je to řazeny abecedně, tak že všechny tyto jmen a čísel jsou řazeny od A to k Z je, a abecedně mezi tím. Ale dnes, nyní se zeptat otázka, dobře, Jak se Verizon nebo se telefon společnost dostat do tohoto stavu? Vzhledem k tomu, že je to jedna věc je využít tento předpoklad, a proto, vyřešit problém s algoritmus efektivněji. Ale my jsme nikdy zeptal se v týdnu nula, dobře, kolik to stálo Verizon nebo někdo jiný se dostat, že telefonní seznam v seřazeném pořadí? Je to tak? Nezáleží na tom, zda vzhlédl Mike Smith je super rychlý, když to trvá vám odkaz rok zpočátku seřazení stránek. Je to tak? Ty by mohly stejně dobře prosít přes randomizované telefonní seznam, pokud to bude být super drahé to třídit. Takže, jestli můžeme mít další dobrovolník. Pojďme se podívat tady na jak might-- pojď up-- jak můžeme jít o třídění těchto. A pokud by se skutečně Jordan Připojte se k nám tady na jevišti. Pojďte nahoru jen na chvíli. Jak se jmenuješ? CAROLINE: Caroline. DAVID J. Malan: Caroline, pojď nahoru. A vy budete spojeny mnou a Jordánskem zde. Caroline, děkuji. Dobře. Takže to, co jsme tady Caroline je 26 modré knihy že FAS používá ke správě některé závěrečné zkoušky. Ty jsou stále těžké najít, ale to, co jsme udělali v předstihu je to, že jsme vložili něčí jméno na přední straně každého z nich, ale my jsme stále to jednoduché od pak uvedení ven plná jména. Takže bychom dát osobu s názvem L, D, J, B, celá cesta A až Z, ale jsou v náhodném pořadí. A tak pokud byste, mluvil vašich cesta přes problém jako vy to je, můžete jít dopředu a třídit tyto pro nás, od A do Z. Publikum: OK, takže L je jako, uprostřed. C začíná. B. J před L. B, Q. DAVID J. Malan: Držte že Myslel dobu jedné sekundy. Vzhledem k tomu, jinak, je to jen zajímavé pro vás, já, a Jordánskem. Tam jedeme. Diváků: [Neslyšitelné]. R. DAVID J. Malan: OK. Co děláš? CAROLINE: M přichází po O. DAVID J. Malan: OK. CAROLINE: O. DAVID J. Malan: Ó, dobrá. CAROLINE: E. DAVID J. Malan: E, F. Jo. CAROLINE: T, U, V. DAVID J. Malan: V, T, U, V. tak to vypadá to, že jste making-- dál. Vypadá to, že děláte velká hromada tady, a druh velkou hromadu tamhle. Takže první polovina abecedy, Druhá polovina abecedy. DOBŘE. Dobrý. Druh rozdělení problému na dvě části. M, N, X. Jo. CAROLINE: K. DAVID J. Malan: OK. K. Takže druh výběru je jeden po druhém, uvedení buď vlevo nebo vpravo, nebo Z děje na zemi. DOBŘE. CAROLINE: Z se děje na zemi. DAVID J. Malan: OK. Y se děje na zemi. Nyní můžeme dát X. CAROLINE: G. DAVID J. Malan: G se děje odešel. S bude v pořádku. Dobře, A jde celou cestu vlevo. CAROLINE: A, B, C, D. DAVID J. Malan: Teď, dobře. Máme A, B, C, W děje tam dole. Dobře, T. CAROLINE: H, I, J. DAVID J. Malan: H, I, J. Good. CAROLINE: V centru, jsem gonna-- DAVID J. Malan: OK. Takže teď, budeme druhu o sloučení těchto různých piloty. Takže A až C, a pak vidím, D, a E a F a G a H a I. Nice. J, K. A pak, to je hromada vzhůru nohama, ale to je v pořádku. Jistě. Můžeme snížit některé rohy. DOBŘE. A pak musíme W, X, Y, Z. CAROLINE: Jo. DAVID J. Malan: Výborný. Tak velké poděkování Caroline pro třídění těchto. [Fandění] Děkuji. Děkuji mnohokrát. Takže teď uvažujme na okamžik jak Caroline šel o tom, že, a co přesně my byli schopni to-- jak byl schopen řešit, že problém, když jsme byli jen vzhledem k tomu, celá parta náhodných vstupů. No, vypadá to, že tam byl trochu tam systému? Správně. Takže čím dříve dopisy v abecedě, ona bylo uvedení na levé straně, a později písmen v abecedě, byla uvedení do pravé straně. A jakmile zjistila, že Některé proximální dopisy, ones které jdou hned vedle sebe, ona by dal ty v pořádku. A tak jsme trochu měli tyto malé hromady tříděných vstupů vyskytujících. A tak to je docela rád to, co Většina z nás by lidé dělají. Rádi bychom nějak prosít přes to, a my bychom trochu mít mechanismus. Ale to by mohlo být těžké psát že se ve vzorci, per se. Bylo to o něco více ekologická než to. Tak uvidíme, jestli můžeme nyní vázaný Problém s menším počtem vstupů. Místo toho, 26., pojďme něco daleko méně s jen říct, sedm, za tyto dveře, abych tak řekl. Jsou tam jen sedm čísel? A v případě, že cíl nyní na ruka je najít hodnotu, podívejme se, jak efektivně můžeme jít asi dělá. A uvidíme, jestli můžeme nyní začne platit nějaká čísla, nebo některé vzorce, s nimiž popsat Účinnost našeho telefonního seznamu algoritmus, naše zkouška kniha algoritmus, a obecněji, vyhledávání informací. Takže pro to, nechte mě jít dopředu, a Na dotykové obrazovce se sem, dát do webového prohlížeče, který má přesně těchto sedm dveře. A pokud bychom se mohli dostat jednu další dobrovolně pojď sem, Já jsem dal tyto stejné dveře sem. Quick dobrovolník. Tyto one-- dema jdou na rychlejší a rychlejší nyní. Pojď dolů. Jak se jmenuješ? Trevor: Trevor. DAVID J. Malan: Trevor? Dobře, Trevor, pojď dolů. Takže Trevor se tu dobrovolně dělat podobný problém, ale ten, který je užší rozsah, a to se děje abychom mohli pokusit formalizovat teď Proces třídění těchto čísel. Takže Trevor, rád vás poznávám. Takže tady je pole, tak mluví, seznam sedmi dveří. Jděte do toho a najít nám číslo 50. A pak se po faktu, řekněte nám, jak jste ji našli. Pokud by be-- v pořádku. Jo, to je ten tady? Uh-oh. DOBŘE. Klepli že jeden. Dobrý. A hodně. Nyní jste klikli, že jeden. A dovolte mi, abych vám mikrofon, takže ji máte za chvíli. Jděte do toho a klikněte na tlačítko vedle, že máte v úmyslu. Ano dobře. Trevor: Mohu unclick dveře? DAVID J. Malan: Ne, nemůžeš unclick. Trevor: OK. Toto. DAVID J. Malan: Kam chceš jít? Který? Trevor: Tenhle. DAVID J. Malan: Ne. Trevor: OK. Toto. DAVID J. Malan: Ano. To bylo dobré. Dobře. Takže jaká byla vaše algoritmus nebo Postup tohoto postupu, Trevor? Trevor: Jen jsem prošel dveře, až jsem našel 50. DAVID J. Malan: OK. Vynikající algoritmus. Tak je to v pořádku. Protože ve skutečnosti, když jsem odhalí, co je Za těmito dvěma dalšími dveřmi, co zjistíme je, že máme jen náhodnou vstup. Takže to byl vlastně as dobrý, jak byste mohli dostat. A ve skutečnosti, máš lepší než vyčerpávajícím hledání celé pole, protože by to bylo skutečně smůlu, pokud jste měli hit číslo 50 na poslední dveře. Ale co kdybychom namísto Dal vám předpoklad. Dejme tomu, že nějak jsem všechny tyto dveře kolem, takže máte Čísla řazeny tentokrát ale tentokrát je to vlastně different-- tentokrát, je to vlastně řazeny pro vás. A teď cíl na dosah ruky je trefit číslo 50. Trevor: OK. DAVID J. Malan: Co je Váš algoritmus bude? Trevor: No, když je to řazeny, je to buď jít na be-- pokud největší k největší, sestupně, bude to první, nebo pokud je to naopak, to bude poslední. Tak jsem si jen klepněte na dveře, a pak stačí klepnout na poslední dveře. DAVID J. Malan: Výborný. Dobře. Takže jsme zjistili, že číslo 50. Takže jakmile jste věděl, byly řazeny, my byli schopni využít tento předpoklad. Takže jsou moc rád telefonního seznamu příkladem. Jakmile budete mít, a to i malý problém jako je tento, vaše vstupy pre-tříděné, můžeme skutečně najít hodnotu pravděpodobně efektivněji. A já jsem tě, jestli je to říci řazeny malých až po velké, nebo velká, aby malé, a tak to bylo velmi rozumné začít na jednom konci nebo na druhou skutečně zjistit, že cílové hodnoty. Takže děkujeme Trevorem stejně. A já budu propose-- pěkně udělal. Máme trochu klip, ve skutečnosti, že je mezi naše oblíbené momentů CS50, přičemž někdy tyto ukázky ne zcela podle plánu. A skutečně právě teď, myslím, vytáhl špatnou rozhraní se kterým používat dotykovou obrazovku. Takže to byla moje chyba tam. Takže to bude dělat na příští rok klip as proč jsem se kliknutím na mé vlastní obrazovku. Ale pojďme se rychle podívat na to, co se stalo loni s Jay, který přišel, hodně jako Trevor tady, dobrovolně, a v tomto krátkém klipu uvidíte jak to totéž demo ne zcela odhalují stejné ponaučení. [VIDEOPŘEHRÁVÁNÍ] -všechny Chci, abyste udělat, je nyní najít pro mě a pro nás, Opravdu, číslo 50 krok za krokem. -The Číslo 50? -The Číslo 50. A můžete odhalit, co je Za každou z těchto dveří pouhým dotykem s prstem. Sakra. [Směje se] [END Přehrávání] DAVID J. Malan: Takže to šlo velmi dobře. Ti, kteří byli netříděné dveře. Jay a, samozřejmě, našel to všechno příliš rychle. Trevor udělal mnohem lepší práci v podmínkách učenlivý okamžik tak říkajíc, v tomto roce trvá delší dobu ji najít. Samozřejmě, pak jsme dali Jay druhá šance, čímž jsme řazeny dveře, jako jsme to udělali pro Trevora, a Trevor DID Super dobře tentokrát. Ale Jay to udělal polovinu rychle. [VIDEOPŘEHRÁVÁNÍ] -The Cílem je nyní také najít nám číslo 50, ale to algoritmicky, a řekněte nám, jak budete o tom. -DOBŘE. -A Pokud zjistíte, budete mít film. Pokud nenajdete to, dát ji zpět. -Muž. Oh! - [Neslyšitelný] OK. Takže já jdu zkontrolovat konců nejprve zjistit, zda there's-- Oh. [APPLAUSE] [END Přehrávání] DAVID J. Malan: OK. Takže jasně třídění dveře vede k větší efektivitě. A tak, dvakrát rychleji je to, co jsem tam měl na mysli. A tak Jay štěstí oba časy. A také štěstí v tom, že poslední rok, objednal jsem nějaké disky Blu-ray skutečně rozdávat. Je mi líto, letos jsme neměl stejný Trevor. Ale pořád lepší byla o několik let zpět. A někteří z vás možná vědí to chlapík, Sean, který kdy byl v CS50, byl napadán s přesný Stejný problém, i když v SD, jak budete brzy vidět, zpět v den. A zjistíte, že nejenže to trvat trochu déle, než Jay, o něco déle, než Trevora, to bylo vlastně to skvělá příležitost aby se zapojily téměř všichni v dav a la Price is Right, povzbuzující ho najít číslo jsme hledali. Pojďme. se rychle podívat. [VIDEOPŘEHRÁVÁNÍ] -DOBŘE. Takže váš úkol tady, Sean, je následující. Jsem se skrývá za tyto Dveře číslo sedm. Ale zastrčená v některé z těchto dveří jakož i jiné záporná čísla. A vaším cílem je si myslet, této horní řady čísel jen jako pole, nebo jen Sekvence kusů papíru s čísly za nimi. A vaším cílem je, pouze pomocí horní array tu, najděte mi číslo sedm. A pak jsme se k posudku jak se chodí dělat. -Dobře. -Find Nám číslo sedm, prosím. Ne. Five, 19, 13. [Směje se] To není chyták. One. [Směje se] V tomto okamžiku, skóre není příliš dobře, takže si klidně dál. Tři. [Směje se] Pokračuj. Upřímně řečeno, nemůžu si pomoct, ale zajímalo co si dokonce myslet, tak-- [Směje se] Jen horní řada, takže Máš tři doleva. Takže mi najít sedm. [Směje se] 17. Sedm. [APPLAUSE] Dobře. [END Přehrávání] DAVID J. Malan: Takže jsme mohli Sledujte tyto celý den. A samozřejmě, některé letošní dema možná bude nyní skončí v příštím Letošní videa stejně. Takže teď pojďme vlastně zaměřit se na algoritmech tady, a uvidíme, jestli nemůžeme Nyní začínají formalizovat jak můžeme jít o získání našich dat do tohoto stavu, že je to řazeny, takže nakonec můžeme skutečně prohledávat efektivněji. A i když jdeme použít poměrně malé datové soubory, stejně jako osm čísel, která máme zde na desce, nakonec by se mohly vztahovat tytéž myšlenky 1000 vstupů, milion vstupů, 4 miliardy vstupy, protože algoritmy se bude v podstatě stejné. A tak to je naše poslední příležitost pro dobrovolníky dnes, ale snad nejvíce zapojeni, kdo, pro které potřebujeme osm dobrovolníků přijít a jít přes nás proces třídění co bude brzy být na tyto hudbu zde stojí. Dovolte mi začít tady. Takže člověk v turquoise-- Zelená je to? Jste spáchání? Dva. Pojď dolů. DOBŘE. Tři. Čtyři. Nechť me-- OK, pět. Jste byl nominován váš přítel. Šest, sedm a osm. Pojď nahoru. Dobře. Děkuji mnohokrát. Pojď nahoru. Pojď nahoru. Dobře. Takže to, co máme, a to here-- je mezi těmi více neobvyklých, protože to bude vyžadovat, abyste humor pro mě jen trochu času. Ty musí být číslo jedna. Jak se jmenuješ? ANNAN: Annan. DAVID J. Malan: Annan. David. Jak se jmenuješ? JOSEPH: Joseph. DAVID J. Malan: Joseph, jste číslo dvě. SERENA: Serena, číslo tři. Stefan, číslo čtyři. CYNTHIA: Cynthia. DAVID J. Malan: Cynthia, číslo pět. [Neslyšitelných] DAVID J. Malan: [Neslyšitelné]. David, číslo šest. Matt: Matt. DAVID J. Malan: Mattova číslo sedm. A? WAVERLY: Waverly. DAVID J. Malan: Waverly, číslo osm. Dobře. Pokud could-- Jejda. Pokud se vám všem, jak vaše První výzvou, tam osm hudební stojany Zde směrem k divákům. Pokud byste mohli dát své číslo na tyto hudba stojí tak, že line up s stejná čísla na desce. Tak, aby sami vypadat, že uvedení vaše čísla na tyto hudby stojí zde. Vynikající tak daleko. Výborně. DOBŘE. Takže teď, budeme se zeptat otázka v několika různými způsoby. Jak můžeme jít o třídění tito lidé tady nahoře? Protože jsme měli několik přístupů dříve, přičemž jsme byli druh výroby dvou různých kbelíky. A pak jsme byli všeobecně Sestavujeme věci dohromady. Jakmile jsme viděli dvě čísla že patří k sobě, jsme dali dohromady. Dva dopisy, které patří k sobě. Ale uvidíme, jestli budeme nelze formalizovat to, takže nakonec jsme se někteří pseudo-kód budete, pomocí kterého můžete vyřešit tyto problémy. Takže teď, jsem díval se na těchto číslech zde. A vidím spoustu chyb. Nakonec, chci, jeden na vlevo a osmi na pravé straně. A tak jsem při pohledu na tyto dva, čtyři a dva. A v čem je problém, samozřejmě? To jo. Tak. Dva zřejmě přijde dříve čtyři, takže víte, co? Dovolte mi, abych nejprve se chamtivý přístup, chcete-li, stejně jako problém nastavit one-- pokud si vzpomínáte z Standard Edition z problému nastavit jednu, kde jsem jen místně vyřešit problém že je tady přede mnou a uvidíme, kam mě to vede. DOBŘE. Tak dva a čtyři, nechte mě jít dopředu a jen prohodit vy dva. Pokud můžete fyzicky přesunout sami a váš papír, Myslím, že jsem vyzrál Seznam v lepším stavu. Teď, jsou dobří. Chystám se jít dál, čtyři a šest, vypadá dobře. Není problem. Šest a osm, na tlačítko OK. Osm a jeden, další problém. Vzhledem k tomu, co je pravda o osm a jedna? Jednou přijde před osmou, a tak co bychom měli dělat? Pojďme vyměnit tyhle dva. Jeden a osm. A teď, budu pokračovat. Budu hledat dál dopředu. A uvidíme, co se stane. Osm a tři, z Samozřejmě, mimo provoz. Pojďme swapu. Osm a sedm, samozřejmě. Mimo provoz. Pojďme swapu. Osm a pět, samozřejmě, pojďme swapu. Dobře. Seznam je seřazen. ano? OK, zřejmě ne. Ale je to trochu lepší, že jo? Vzhledem k tomu, upozornění, co se stalo. Pokaždé, když jsme provedli výměnu, menší Počet druh perkoluje takhle, a větší číslo perkoluje tímto způsobem, nebo budeme začít říkat bublal do vlevo nebo probublává doprava. Nyní, to není dost, protože přinejlepším číslo by mohl se posune o jedno místo vpřed, nebo v nejhorším případě, číslo může mít posune o jedno místo dál. Takže víte, co tento druh z fungovalo docela dobře tak daleko. Dovolte mi, abych to zkusit znovu. Dva a čtyři, jsou v pořádku. Čtyři a šest, jsou v pořádku. Šest a jedním, mimo provoz. Takže pojďme vyměnit vy dva. A teď, Všimněte si, že problém je začíná být trochu zase lepší. Šest a tři, mimo provoz. Pojďme vyměnit vy dva. Šest a sedm, jsi dobrý. Sedm a pět, samozřejmě, mimo provoz. Sedm a osm, v uvedeném pořadí. A teď, bych mohl potřebovat to udělat ještě několikrát. A ve skutečnosti, myslím, že pro sebe snad kolikrát maximálně Možná budu muset chodit sem a tam? Vrátíme se k tomu. Tak dvě a čtyři jsou stále v pořádku. Čtyři a jeden, ani náhodou. Takže, pojďme výměnu. A opět si všimněte, vizuálně jeden je druh probublávání na levé straně, pokud by mělo být. Čtyři a tři odkládací. Čtyři a šest. Šest a pět swapu. Šest a sedm. Sedm a osm je dobré. Dobrý. Dostáváme ještě lepší. Takže pojďme se podívat. Nyní máme dva a jeden. Samozřejmě, vyměnit. Dva a tři, tři a čtyři, a pět, šest a sedm, sedm a osm. Dobrý. A víte co? Protože jsem tam jednu změnu, dovolte mi udělat jednu kontrolu zdravý rozum. Nech mě jít celou cestu zpět na začátek. DOBŘE. Jeden z nich, two-- Jo, vidíš? Něco bylo špatně. Tři, čtyři, pět, šest, sedm, osm. A v tomto posledním průchodu, jsou pohodlné s mým teď prohlašovat, že to je třídit? DOBŘE. Vizuálně, že je to naprostá pravda. Ale to, co Funkčně se také jen tak V té poslední průchod, která vám umožní potvrdit, že tento seznam je opravdu řazeny? Co jsem udělal, nebo ne tento poslední pas? Diváků: nedošlo k žádným změnám. DAVID J. Malan: Sorry? Diváků: žádné změny. DAVID J. Malan: nedošlo k žádným změnám. Tak to by bylo hloupé mě Udělej to stejný algoritmus znovu kdybych neudělal jakýkoli změní poprvé. A stát se nezměnil. Jistě, nebudu dělat Jakékoli změny podruhé. A tak je to teď v bezpečí říkat, seznam je tříděn. A skutečně, to je nyní něco, že budeme obecně hovor bublinkové řazení, přičemž po dvou, znovu opravit chyby, a znovu a znovu, a ti udržet tam a zpět, a sem a tam, dokud se neposkytujeme žádné takové swapy, na kterém místě můžete si být jisti, jo, já dokončil upevnění všechny chyby. Pojďme reset a zkusit jiný přístup. Pokud vy mohl vrátit do pořadí jste před chvílí, který vypadal takhle. Nyní se pojďme k přístupu, který trochu více jako zkoušku knize, kdy jsme byli neustále výběrem písmeno abecedy že jsme trochu chtěli řešit další. Možná to byl vysoký dopis, Stejně jako, nebo s nízkou písmeno Z. Takže každý je zpět v tomto pořadí. A teď mě to udělat. Pojďme se podívat, vím, že mám osm čísla zde. Chystám se jít dopředu a jen záměrně zvolte nejmenší prvky. Je to tak? To se zdá být intuitivní taky. Proč mi připadá nejmenší prvek, vložte ji tam, kam patří, pak dostanete další nejmenší prvek, dal je tam, kam patří, a jen zopakovat. Vzhledem k tomu, intuitivně, který by měl fungovat také. Tak čtyři, to je docela malý počet. Jdu si vzpomenout, kde to je. Počkej chvíli. Two je menší. Dovolte mi nyní vzpomenout, kde dvou je, a zapomenout na čtyři. Vyřídíme to později. Šest, nemám zájem. Osm, nemám zájem. Jedním z nich je můj nový malý počet. Takže budu pamatovat, kde jeden je. Tři, nemám zájem. Sedm, nemám zájem. Five, nemám zájem. Takže bez pádu fáze v tomto roce, Chystám se chytit počet one-- a to, co bylo zase Vaše jméno? ANNAN: Annan. DAVID J. Malan: Annan. A kdybyste se mnou na začátek seznamu pojďme tě tam, kam patříte. Bohužel-- Jak se jmenujete? STEFAN: Stefan. DAVID J. Malan: Stefan je v cestě. Takže než Stefan řeší tento Problém, co bychom měli dělat? Co budeme dělat s Stefan? Diváků: [Neslyšitelné]. DAVID J. Malan: OK. Takže jsme mohli udělat. Mohli bychom nějak vzít Stefan a jeho čtyři, a jen dát to do proměnné a držet se jí za určité množství času, čímž se vytvoří prostor pro číslo jedna. A to není špatné. Mohl bych navrhnout, proč ne jsme jen dát tu Stefana? Proč by to mohlo porušit jeden nápadů jsme začali mluví o minule, minulý týden? To jo? Diváků: [Neslyšitelné]. DAVID J. Malan: Neexistuje žádný index pro něj. Pokud si myslíte o tom, opravdu, jako pole, to je jako negativní, takže není žádná paměťová vlastně Zde, pokud je to skutečně pole, jako jsme deklarovali minulý týden v přednášce. Takže bychom neměli dělat. Můžeme uložit jej do proměnné. Nebo víte co? Slyšel jsem, že někdo jiný to naznačují. Co jiného můžeme dělat s Stefan? Proč jsme ho jen vystěhovat a ho přes číslo jedna, kde byl. Takže pokud chcete jít tam. A skutečně, to je docela dobré řešení. Nyní na jedné straně, jsem druh z dělal problém ještě horší. Čtyři je nyní dál od místa, kde by měla být. To by mělo být k tomuto polovinu. Ale víte co? To by mohlo být smůla. Možná, že číslo osm díval. A tak, možná bychom se dostali štěstí, a tlačil osmi blíže ke konci. Takže na konci dne, docela to všechny průměry ven. Nemusíme se starat o čtyři. Vše o co se starám právě teď výběru nejmenší prvek. A teď, co budu udělat, je zapomenout na číslo jedna natrvalo, protože vím, že Seznam za mnou je nyní seřazeny. Takže můj seznam byl dříve velikosti osm. Teď je to o velikosti sedm. Takže můj problém je dostat menší, ale přesto lineárně. Takže teď, budu vyberte proud nejmenší prvek, dva. Šest, osm, čtyři, tři, sedm, pět. To byl ten nejmenší prvek. Tak co mám dělat with-- co byl opět Vaše jméno? JOSEPH: Joseph. DAVID J. Malan: Joseph? Budeme nechat Josefa na místě. Teď, budu předstírat že tyto lidi are-- dobře, Vím, že tyto dvě je již řazeno. Pojďme se nyní zaměřují na Zbývající část seznamu. Šest je aktuální nejmenší. Osm je větší. Čtyři je nyní aktuální nejmenší. Tři je nyní aktuální nejmenší. A tak teď, budu vybrat tři, kdo je-- jaké je vaše jméno znovu? SERENA: Serena. DAVID J. Malan: Serena, kdybyste mohl urvat si číslo a swapu with-- Kalsang: Kalsang. DAVID J. Malan: Kalsang. Pojď zpátky, a my jsme chystá vyměnit ty dva. A teď, pojďme dát na autopilota to. Chystám se jít a nechat to na vás kluci zvolit nejbližší menší prvky. Dun, šedivý, šedivý, dun. Číslo čtyři, co byste měli dělat? Výborně. Teď, budu dělat další přihrávka. Dun, šedivý, šedivý, dun. Vidím pěti je další nejmenší. Teď, budu trvat další přihrávka. Dun, šedivý, šedivý, dun. Šest je nejmenší. Dobrý. Sedm je nejmenší. Žádná změna. Osm je nejmenší. Hotovo. Takže to, co jsme právě provádí opakovaně výběr jednoho prvku za sebou je implementovat něco, co jsme bude formalizovat jako výběr druhu. A to je možná i jednodušší na vysvětlení, v tom, že doslova po vás chtít udělat, je jen udržet tam a zpět přes seznam výběru, další nejmenší prvek, dokud máte hotovo. Takže je to ještě jednodušší, snad intuitivně, než poslední. Zkusme poslední jeden. Pokud vy sami mohli obnovit do následujících poloh jeden poslední čas, uvidíme, jestli nemůžeme Nyní formalizovat jednu další postup. Ve skutečnosti, by někdo tam chtěl navrhnout, jak jinak bychom mohli jít asi dělá? Bez hodil out módní slova nebo seřadit z odpovědí, které jsou již známy, jen intuitivně, co jsme mohli dělat? Diváků: [Neslyšitelné]. DAVID J. Malan: Jo. Takže tam je tam nějaký velký intuice. Dobré věci se zdá, tak daleko se stalo v oblasti počítačové vědy, když jsme se rozdělit a dobýt problém dělení je na polovinu a půl na půl. A tak my, mohl začít dělat to. A ve skutečnosti, že to bude, budeme vidět, jeden z našich nejlepších řešení dosud. Ale pojďme se vrátit k tomu zanedlouho. Ve skutečnosti, budeme dělat že o něco později tento týden. Co jiného můžeme dělat to vyřešit? Takže všichni tady je v zdánlivě náhodném pořadí. Ty víš co? Spíše než jít tam a zpět, sem a tam, tam a zpět pokaždé, to cítí jako Dělám hodně chůze. Proč jsem se začít na začátek seznamu a jen dát čtyři kam patří? Dovolte mi tedy předpokládat, že pro tuto chvíli můj seznam je pouze tento první prvek. Se čtyřmi řazeny v tomto okamžiku v čase, pokud všechno mě zajímá, je tady všechno? To je trochu triviálně pravda, že jo? Stejně jako v seznamu, který obsahuje jedno číslo, a že číslo čtyři je samozřejmě seřazeny. Takže mi dovolte stanovit že tento seznam je seřazen. Ale teď mám zbytek tohoto seznamu. Takže teď, jsem se setkávají dva. Kde se dva zjevně patří s ohledem na čtyři? Před čtyři. Takže to, co můžu dělat? Co se jmenuješ? JOSEPH: Joseph. DAVID J. Malan: Joseph, pokud byste mohli krok zpět na chvilku se svým číslem. A teď, co by měl dělat Stefan tady? Pojďme posun Stefana tady. A teď, ať Joseph přijít sem. A nyní mi dovolte, abych tvrdí, že Všechno je tu řazeny. Takže, Podobný výsledek, ale zásadně odlišný přístup. Ani jsem se podíval, co tam dole. Jen jsem pokračovat v užívání prvky jak se jim předali mi, a vypořádat se s nimi. Takže teď, vidím číslo šest. Kde se číslo šest patří? Máme dvě, čtyři, šest. Přesně tam, kde ona je právě teď. Takže nechme to samo o sobě, a teď tvrdí, že této části seznamu Nyní je seřazen. A tak, to cítí zásadně liší v tom, já jsem jen pohybující se v seznamu zde lineárně, a já jsem se nikdy zdvojnásobení zpět. Ano. Dobře. Tak osm, kam patříte? Právě tady. Perfektní. Takže teď, jedním. Uh-oh. Tento pocit, že je to bude drahé. Nyní, v předchozím algoritmu, Jen jsem vyměnil lidi. Tak jsem mu mohl dát celou cestu na začátek, ale pak se stěhoval Joseph. Ale když jsem se přesunout Joseph, nyní co se děje, aby být špatně? A teď, jsem nějak undone-- jsem vzít jeden krok vpřed a poté jeden krok zpátky, protože teď Josef by bylo mimo provoz. Tak jdeme na to. Pokud byste mohli mít číslo jedna a krok zpět jen na chvíli. Jak můžeme put-- co byl opět Vaše jméno? ANNAN: Annan. DAVID J. Malan: Annan na místě? Co se má stát, pokud jde na dvě, čtyři, šest a osm? Ti všichni potřebují posunout. Takže pokud osmi chtěli posunout první, pak šest, potom čtyři, pak dvě. A pak Annan, pokud byste Líbí se přijít sem, dobře. Ale tady, právě jsme druh zaplatil cenu na jiném místě v algoritmu. Zatímco minule s výběrem třídění, a dokonce i bublinkové řazení, Jdu zpátky a tam, tam a zpět, která je jistě sčítání časově a doslova postupně. Insertion sort, nejprve pohled, vypadá, že je to výborný chytřejší, v tom, že jsem jen dělat pomalý, postupný pokrok, ale nehodlám to tam a zpět. Ale pokud někdo skutečně mimo provoz, oznámení všechny práce jsem musel udělat. Musel jsem se přesunout polovinu seznamu jen aby se prostor pro číslo jedna. Takže je to stejná částka práce dosud ji cítí, jen jiný druh práce. Pojďme pokračovat. Takže teď víme, že každý mezi jedním a osm jsou seřazeny. Tady mám číslo tři. Máte-li rádi vyzvednout číslo tři, jeden krok zpět. A co vy musíte udělat? Jo. Tak to je ještě jeden, dva, tři kroky. Tři jednotky času, který právě stály mě, takže tři mohou nyní vejde. A konečně, sedm. Pojďme dál a mají si vzít krok zpět. Toto je teprve ve chvíli, aby nám stát jedna jednotka času, ale to je v pořádku. A teď, pět děje na být o něco dražší. Pokud byste chtěli udělat krok zpět. Musíme se pohybovat osm, a sedm a šest. A pak se všichni je nyní seřazeny. Tak velká ruka našim dobrovolníkům zde. Děkuji mnohokrát. [APPLAUSE] Děkuji vám všem. Děkuji vám všem. Tak uvidíme, teď jen, jak nákladné to všechno bylo. Pojďme zvážit možná nejjednodušší z nich, bublinkové řazení. A já říkám nejjednodušší, jen proto, můžete vyřešit ji nenasytně pouhým vyřešit pairwise problém. Opravit pairwise problém Zde, znovu a znovu a znovu, opakování tolik kolikrát je skutečně potřebují, aby. Tak to dopadá, že s bublinou druhu, dobře, kolik kroků musím přijmout První průchod z tohoto algoritmu? Mohl bych take-- pojďme see-- jednoho, dva, tři, čtyři, pět, šest, sedm. A je tu osm elementů sem. Takže je to jako n minus 1 kroků k se od začátku seznamu na konec seznamu. Ale s výběrem Třídit, připomenout, že já jsem znovu a znovu Výběr prvků a znovu to nejmenší, Dávám to na místě, ale pak jsem nejsem dívá za mnou znovu. Takže si myslím, že je to trochu jasnější pak, že poprvé, mohu muset vzít všechny n minus 1 stupni najít nejmenší prvek. Pak jsem dal je na místě, a já vypudit ten, kdo tu byl předtím. Ale pak jsem si nemusím držet při pohledu na tento prvek, protože vím, že je to Už nejmenší. Takže teď, můžu se podívat na právě sedmi elementů a pak šest prvky, pak pět prvků, pak čtyři elementy. A tak matematicky, pokud n je počet prvků nebo čísel že jsme začali s, ktere si lze predstavit že se jedná o stejné jako n minus 1, a n minus 2 stupně, a n minus 3 stupně, plus n minus 4 kroky, a to tím až na doraz jednom kroku. A já jsem na poslední osobu. A pokud si vzpomínáte, že hodně Statistiky knihy nebo matematické knihy mít ty vzorce na straně Vázaná zadní nebo přední z nich, Ukazuje se, že této sérii může být vyjádřena jednodušeji jak n krát n minus 1 nad 2. A to je v pořádku, pokud to není v popředí své mysli. To je však skutečně pravda. To je jen jednodušší způsob psaní. A pak, pokud si myslíte, zpět na základní škole, když jste právě spuštění násobí věci, to samozřejmě, právě n druhou minus n děleno 2. Všechno, co jsem udělal, je rozšířit výrazy tam. A tak se pojďme přepsat trochu jinak. To n čtverečkované dělí o 2 mínus N / 2. Takže znovu, jsem jen trochu uplatnění někteří aritmetický pravidla zde. Nevšimnout teď, že největší termín v tomto výrazu, abych tak řekl, je to, že n na druhou. Takže ano, je to n kvadrát děleno 2, mínus n / 2. Obecně ale, je-li n je Bude to velká hodnota, Budu tvrdit, že n čtvercový bude dominantním faktorem. Je to jen bude větší přispěvatel na počtu kroků, než n / 2. Tak co tím myslím? Zkusme si jednoduchý příklad, a to i ačkoli matematika dostane trochu velký. Takže předpokládám, že jsme měli 1 milion lidí na jevišti, nebo 1 milion věcí že chceme uspořádat. Pojďme zapojte milion do přesně v tomto vzorci vidět, kolik kroků to trvá celkem třídit milion prvky pomocí řekněme, výběr třídění. Takže budeme mít stejný vzorec jako předtím. Já bych připojit milion, tak, že jsem si milión čtverečkované děleno 2, minus jeden milion děleno 2. Pokud se mi, že matematiku v předstihu tady máme 500 miliard minus 500000, který nám dává 499999500000, což je zatraceně velký. Ve skutečnosti, pokud si porovnat teď 499000000000, 999000000, 500000 proti naší původní hodnoty, 500000000000, je to tak zatraceně blízko. Je to tak? n čtverečkované děleno 2 dává us-- nebo spíše, n čtverečkované děleno 2 dal nám 500 miliard. To je zatraceně blízko na 499,999,500,000, což znamená, že se odečte off 500000, nebo obecněji, odečtením off n čtverečkované, není opravdu velký problém. N čtvercový činí tyto Čísla rostou opravdu rychle. Nyní, to je důležité jen do té míry jako my, jako počítačových vědců, jsou obecně nebude tolik péče o nuance těchto vzorcích a co přesně přesné odpovědi. Víme jen, že péče, víte co? Na konci dne, tento vzorec je na pořadí n čtvercový. Ano, jsme vydělením 2 v tam. Ano, budeme odečítat z n minus 2. Ale na konci dne, termín že nás opravdu bolí a stojí nás hodně kroků, je to, že náměstí termín. A tak to, co počítačový vědec bude obecně dělat je ignorovat všechny ty menších objednávek podmínky, a jen se podívejte na ten, který nejvíce přispívá k nákladům. A to je pěkné, protože můžeme nyní hovořit v mnohem větší obecnosti o algoritmy, a mohou porovnávat je. A skutečnost, že jsem O použití tohoto je záměrné. Když řeknu, že na objednávce o, já jsem konkrétně s odkazem na něco volal velký O. A big O je zápis, že počítač vědec používá k popisu horní mez něco. Takže když říkáte, že algoritmus je ve velkém O z n na druhou, jak jsem navrhl jen před chvílí, že prostředky že pokud jde o její chod úvazek nebo jeho účinnost, to znamená v řádu n druhou kroků. Možná víc, možná méně. Ale to je na pořadí n na druhou. A to je horní mez. Není to bude více bolestivé než to. Není to bude n krychlový, nebo 2 na n, nebo něco mnohem většího. Jedná se o horní mez Na co to je cena. Takže vzhledem k tomu, pojďme zvážit jen několik příkladů. A to je jen konečný seznam velmi časté provozní doba pro algoritmy, který je určen k ilustrativní některých věcí, které jsme Viděl už. Tak například v případě výběr třídění, co jsem tvrdil zde je běh této výběrem Třídit je čas je na pořadí n na druhou. V nejhorším případě, budu mít celá parta náhodných čísel zde. A jak jsme viděli matematicky, když jsem chůzi držet v seznamu, a to prostřednictvím seznam, výběr příští nejmenší znovu a znovu prvek, pokud I vlastně zapsat všechny kroky Beru, jak jsem navrhl formulaically předtím, je to na objednávku n čtvercové kroky, které beru. A ukázalo se, že bublina třídění a insertion sort jsou stejně pomalu v nejhorším případě. Vezměme si například, insertion sort, úplně poslední algoritmus jsme se zabývali, který měl s námi podívat na prvek, a vložte ji tam, kam patří. A pak jsme se podívali na další prvek, a vložil ji tam, kam patří. Tak zváží nejlepší možný scénář. Dejme tomu, že jsem měl můj dobrovolníci line up doslova jako je tento, jedna až osm, již řazeno. Kolik kroků je insertion sort bude trvat třídit osm lidí, když dorazí na pódiu vypadající takhle? Osm lidí již řazeno. A já používám insertion sort. Že poslední z algoritmů. Dobře, pojďme reenact opravdu rychle. Takže když začnu tady, vidím jeden. Kde vůbec nepatří? Patří tady. Vidím dva. Kde dvou patří? Právě tady. Vidím tři. Kde Tři patří? Právě tady. Vidím čtyři. Právě tady. Pět, šest, sedm, osm. Neexistuje žádný důvod, aby se opakuji. A tak, jak mnoho kroků je to, že, pokud jde o n? Je to na objednávku n schůdky, že jo? n minus 1. Ale vzal jsem lineární číslo kroků, a teď jsem udělal. Tak to je nejlepší případ, ačkoli. Co nejhorším případě? Jaké bylo osm tam, a sedm bylo tam dole, a jeden a dva byli tady, tak že seznam byl skutečně zvrátit? No, co se děje ve skutečnosti jestli je to číslo? A uděláme jen pár příkladů. Co když, opravdu, číslo osm je tady, a number-- pokřiky. Takže to, co v případě, opravdu, číslo Osm je celou cestu sem, a já jsem s použitím insertion sort? DOBŘE. Tvrdím, v tuto chvíli je to na místě. Ale teď, sedmé Odkud sedmi jít? Samozřejmě, že jde přes zde. Takže jsem se pohybovat přes osm jednom místě. A teď šest, kde to jde? No, v pořádku. Teď musím se pohybovat přes osm místo, a sedm více než na místě, a pak jsem plop dolů šest. Takže první čas, že náklady mi jeden krok věci do pořádku, Pak mě to stálo dva kroky opravit věci. Kolik kroků je to bude trvat na opravu Co dát pět na správném místě? Tři. Protože teď musím přesunout jeden, dva, tři. Kolik kroků to bude trvat dát čtyři na správném místě? 4 a 5, a 6, a 7. A tak je to matematicky totožné s to, co jsme popsali pro výběr druhu. Máme tuto sérii to je jen roste. 1 plus 2 plus 3 plus 4, nebo naopak, 7 a 6 a 5 plus 4 sečte pro dnešní účely tak, aby na pořadí n na druhou. Dovolte mi také, že stanoví, bublinkové řazení je také v n na druhou. Vzhledem k tomu, s perličkovou druhu, každý Tentokrát jsem projít seznam, Beru zhruba kolik kroků? Pokaždé, když jsem se doslova pěšky odtud tam? Zhruba n kroků. Ale kolikrát bych mohl muset projít seznamu? No, hrubě n čas. Možná n minus 1, ale zhruba n časy. Tak proč je to? No, s bublinou druhu, pokud začneme s bublinou druhu, se seznamem v ten nejhorší možný situace, což je opět zcela dozadu, co se bude dít? I projít seznam, a číslo Patříte-celou cestu tam. Ale s bublinou druhu, jak daleko se může stát jeden přejít na svém prvním průchodu seznamu? Kolik místa se dostal blíže na správné místo? Jen jeden. Takže pokud máte trochu důvod přes to, pokaždé, prostřednictvím tohoto algoritmu, Davidovi, kteří se zhruba n kroků. Ale kolik prochází v seznamu je to bude trvat na jeden bublat na levé straně, kam patří? Má se pohybovat podobně, n prostory Tudy. Takže stačí k tomu třídění seznamu, Musím chodit sem a tam n-krát. A pokaždé, já jsem při pohledu na n elementy. Takže dělat věci, n n-krát na pořadí n na druhou. Teď uvidíme v některých šortek, které jsou uloženy v CS50 je další problém set, jiný přístup na nich, ale teď, ať to prostě vzít v úvahu některé ostatní provozní časy, zvláště v případě, že třídění ti brát trochu času, aby dřez. Co je to algoritmus jsme viděli již , který bere na pořadí n kroků? To, co by měl mít lineární číslo kroků, které jsme doposud viděli? Co je to? Vyhledávání telefonní seznam. První algoritmus. Je to tak? Tam, kde jsme lineárně hledání Mike Smith? Vskutku. Od týdne nula, když jsem začal soustružení jednu stránku najednou, a dokonce řekl jsem, že to bylo docela lineárního pocit algoritmu, a měli jsme ten obraz na straně deska s rovnou červenou čárou a rovný žlutý linka, ty byly skutečně algoritmy, které jsou ve velké O n. Vzhledem k tomu, najít Mike Smith v telefonu kniha n stránek, v nejhorším případě, mi n kroků může trvat. Co o tom, docházku? Jedna dva tři čtyři pět šest. Jaký je doba chodu tohoto algoritmus pro přijetí docházku? Velký O n, protože teoreticky I muset bod všichni v místnosti. Nyní jako stranou, co o další optimalizace z týdne nula? Dvě, čtyři, šest, osm, 10, 12. Počítač by vědec si uvědomit, počkejte chvíli, to je na pořadí n děleno dvou krocích. Je to tak? Protože dělám dva lidi najednou. Ale budeme ignorovat tyto nižšího řádu podmínky, a my jen tak vyhodit propast o 2, a jen říct, velké O n pro tento algoritmus, tak. Co tenhle? Budeme přeskočit některé z nich, ale to, co byl algoritmus, který byl log n? To zabralo zhruba log n kroky? Propast a panuj. Přesně tak. Stejně jako telefonního seznamu například v týden nula a dnes ráno, kde jsme rozdělili problém znovu a znovu a znovu. Čerpal jsme to na tabuli v týdnu nula jako zakřivený zelená linka, a my jsme řekli, že je to den, logaritmickou algoritmus. A opravdu, počet kroků IT potřebná k provedení rozděl a panuj, nebo binární vyhledávání, jak začneme volat to, stejně jako v telefonním seznamu, je řádově log a jen pár kroků. A to je trochu divný jeden. To, co se jeden krok, nebo přesněji konstantní počet kroků? Možná je to dvou, možná je to tři, ale počítačový vědec jen zjednodušuje to jako velký O 1, některé konstantní počet kroků. Co je to něco, co byste mohli udělat, že trvá konstantní počet kroků? Jaký je doba provozu tleskat? Konstantní čas. Je to tak? Stejně jako to, co je doba provozu dělat něco, který bere jen jeden provoz, stejně jako vytisknout F Hello World. To by mohlo být řekl, aby byl konstantní čas, ledaže méně rohový případě s tiskovým F, Co by mohlo čas běží tisku F být ve skutečnosti? A proč? Co je n měření v tomto případě? Diváků: [Neslyšitelné]. DAVID J. Malan: Přesně tak. Počet znaků chceme vytisknout. Takže je to velmi kontextová. Dnes jsme se zaměřuje hodně na písmena a číslice tady na palubě. Ale může to být také znaky v skutečném řetězci. Tak to dopadá je tu další opatření, které začnou starat o, a to je opak big O, abych tak řekl. To je omega notace. Vzhledem k tomu, velký O znamená, že to, co je se horní vázané na běžící čas? Maximálně, kolik času Možná něco vzít? Omega-- Omlouváme se, tento stále přichází up-- je opak toho, čímž je to dolní mez na Množství času, něco, co by mohlo trvat. Tak. Například, co je algoritmus který bere vždy n čtverečních kroky? No, jeden z algoritmů jsme viděli dnes, ve skutečnosti, že může být také. Selection sort. Výběrem Třídit to docela hloupé. I když se algorithm-- líto, a to i v případě, že je pole již seřazeny, Volba třídění se chystá chůzi držet v seznamu aby se ujistil, že má nejmenší prvek znovu a znovu a znovu. A i když lidé v diváci vědí, že, počkejte chvíli, již prošel nejmenší prvek, počítač neví, že až to vypadá celou cestu v seznamu. Podobně, dolní mez, která mohou být rovněž vzaty v úvahu by mohl být lineární čas. Kolik času trvá třídit n prvky v nejlepší Případ použití něco jako bublina druhu? Předpokládejme, že váš seznam je již řazeno. Řekli jsme, bublinkové řazení bere na pořadí n druhou kroků. Ale co když je to již řazeno? Co když si uvědomíte, po jeden průchod přes pole že jste udělali žádné swapy? Potřebujete udržet dělat více prochází? Ne. Takže spodní hranici bublinkové řazení by mohlo být řekl, aby byl lineární. Omega n. A my si prohlédnout další z nich, jakož. Takže pojďme se rychle podívat na pouhých vizualizaci zde vidět, jak se tyto odlišit. Chystám se jít sem dolů do toho Stránka, která je k dispozici na internetových stránkách C50 je, ale bude to bolet, aby si práci, protože používá technologii nazvanou Java applety, což je z velké části podporován v těchto dnech, alespoň Chrome a některé další produkty. A dovolte mi, abych do toho pusťte a urychlíte up a vysvětlit, co se děje. To je projevem bubliny třídění, první algoritmus jsme se na. A to je vizualizace, že každý z těchto tyčí představuje číslo. Čím větší je bar, Čím vyšší je číslo. Čím menší je bar, čím menší je počet. A co můžete vidět vizuálně, a to i i když to bude super rychlý, je to, že červený pruh je jako já, chůze sem a tam upevnění problémy. Můžete vidět, že větší prvky skutečně vyvěrá na pravé straně, a na menších elementy vyvěrá doleva. A tady dole, kdybychom ve skutečnosti vypadají lépe, vlastně můžeme počítat počet porovnání a swapů které byly vyrobeny. Ale místo toho, pojďme se podívat na druhém algoritmu jsme se podívali na dříve s naší dobrovolníci, výběr druhu. Vizuálně, to má velmi odlišný efekt. Ale je to opět velmi intuitivní, v že držíme výběr příští nejmenší prvek, a dostali jsme trochu štěstí. To se cítil zásadně rychleji. Ale když jsme běželi to znovu a znovu a opět se spoustou vstupů, viděli bychom, že je to opravdu stále ještě ve velké O n na druhou. Pojďme udělat jednu poslední tady, insertion sort, který byl třetí algoritmus jsme se podívali na, a odvolání že tento člověk se zabývá prvky, jak to s nimi setká, ale pak se to možná posuny věci, nad aby se uvolnilo místo, vkládání prvků tam, kam patří. A to také skončí dávat Konečný výsledek. Nyní všechny tři z těch, cítil docela rychle. A skutečně, běžel jsem je v docela dobrý klip. Ale v podstatě, oni jsou všichni dost hrozné, abych byl upřímný. Všechny tyto algoritmy dosud že dráha v velký O n čtvercový trvat docela dost čas pro spuštění v konci. A skutečně, můžeme vidět a cítit se to konečně když jsem vytáhnout tento třetí a poslední demo. To je další vizualizace, co se děje ukázat bublinkové řazení na levé straně, výběrem Třídit ve středu, a něco, jako jeden z našich ruka vyvolává dříve navrhl, merge sort na pravé straně. Předěl a panuj Strategie na pravé straně. A to je ve skutečnosti to, co jsme jít se podívat na středu. Ale pojďme čas tyto běžet paralelně. To je zhruba stejný počet prvky, všechny běží ve stejnou dobu. Bubble sort vs výběru třídit vs sloučení druhu. Teď se všichni běží teoreticky ve stejnou dobu. CPU běží na stejnou rychlost, ale Můžete cítit, jak je to nudné velmi rychle stane, a jak rychle, když jsme se vnést trochu týdne algoritmy Zero může jsme se věci urychlit. A teď pojďme porovnat tyto v posledním formě. Chystám se pokračovat na webové stránky CS50, kde máme tuto konečnou odkaz pro dnešek, kde někdo na internetu laskavě dal dohromady video, které zachycuje to, co jiný třídění algoritmy znít. To je insertion sort. [Pípání] Přičemž se ucházíte frekvenci založené na výšce baru baru. Je to bublina druh. [Warped pípání] Připravujeme další je-- přichází up další je-- výběr třídit, kde opět, my výběr příští nejmenší prvek, a my můžeme vidět, že růst zleva doprava. Merge sort, náš vítěz tak daleko ještě dnes. Všimněte si, jak je to dělení věcí do [neslyšitelný] polovinu a čtvrtiny. Gnome třídění, které my ne mluvil o, a vytváří vizuálně a audally trochu jiný tvar a zvuk. Tam a zpět, čištění věci. Také check out Heapsort na webových stránkách tenhle chlápek. A to je vše. Uvidíme se příště. [Whooshing a hudba]