[Prehrávanie hudby] David J. Malan: Dobre. Tak vitaj späť. To je CS50, a je Koniec týždňa tri. Takže pripomínajú v posledných niekoľkých týždňoch, sme strávili celkom dosť čas na C, na programovanie, na syntax. A to je celkom normálne, ak ste ešte zápasí s problémovými Set 2, sa búchanie hlavou proti múru. Je to tajomné vyzerajúce chybové správy a chyby, ktoré nemožno úplne naháňať. Vzhľadom k tomu, byť istí, že práve Doba pár týždňov budete obzerať na veci ako Caesara a [? V-genair,?] možno aj Crack a uvedomiť si, ako ďaleko ste prišli v krátkom časovom období. Takže či je to nejaká útecha, vydrž teraz. V súčasnej dobe sa však začneme prechod na veci vyššej úrovne. A začneme brať za samozrejmosť, že vy viete, ako programovať, alebo najmenej počiatky že úroveň pohodlia. A začneme uvažovať o tom, ako môžeme ísť o navrhovaní programov viac efektívne. Ako môžeme ísť o optimalizáciu Účinnosť našich algoritmov a všeobecne viac riešení zaujímavé problémy. A začínajú brať za samozrejmosť, že keby sme chceli, mohli by sme kódu vzostupne každý z príkladov, ktoré máme na mysli. Takže dnes sme sa nedotýkajte klávesnica pre akejkoľvek forme kódu. To bude oveľa vyššiu úroveň, a nakoniec, o riešení problémov. Takže sa dostať do tohto bodu, dovoľte mi navrhnúť že nasledujúce sedem obdĺžniky predstavujú sedem dvere, za ktoré sú celá partia čísla, medzi ktorými je číslo 50. Dovoľte mi, aby som to premietnuť na tomto displej i tu. A navrhnúť, že potrebujeme dobrovoľníka pomôže mi nájsť číslo pred internet tu. Poďte hore, v ružovej. Dobrá. Ako sa voláte? JENNIFER: [nepočuteľné] David J. Malan: Je nám ľúto? JENNIFER: Jennifer. David J. Malan: Jennifer. Dobre, Jennifer. Rád Vás vidím. Poď hore. Tak to tu je sedem dverí, a to, čo Chcel by som, aby si pre nás, v prednej časti všetkých vašich spolužiakov, sa k nám dostanete číslo, 50. Ak chcete nájsť číslo, môžete nahliadnuť za niektoré z týchto dverí jednoduchým poklepaním na jednej strane dverí, a to odhalí jeho číslo. A pozrime sa, ako rýchlo sa Nájdete u nás číslo, 50. 15. 16.. 50. Dobrá práca. Dobrá. Potlesk pre Jennifer. [APPLAUSE] Dobrá. Tak aká bola vaša stratégia pre nájsť číslo 50? JENNIFER: Hm, myslela som, že ak - [Nepočuteľný] David J. Malan: Oh. Dajte mu jednu sekundu. Tak bola vaša stratégia pre nájsť číslo 50? JENNIFER: Tak som sa začať na začína vidieť, čo prvé číslo bol, a potom som si myslel, možno, ak oni sú radené, budem len držať kliknutím výš? David J. Malan: OK. A zdá sa, že našli že tomu tak je. Aj keď, poďme Zlúpnite vrstvy len trochu, a vy chcete ísť dopredu a odhaliť ďalšie dvere si mohol vybrať? JENNIFER: Ach jo. David J. Malan: Ah. JENNIFER: Tak som mal šťastie. David J. Malan: Takže máš šťastie. Dobrá. Takže to nie je zlé. Ale to je zaujímavé, pohľad, nie? Ak máte predpokladať, a vy ste sa, naozaj, trochu šťastia tam. Ale ak sa predpokladá, že tieto čísla triedené, môžete byť presnejší ako ktorý ovplyvnil vaše správanie? JENNIFER: Takže ak by boli zoradené, som si myslel, že najmenšie k najväčšej. David J. Malan: OK. JENNIFER: Alebo, ak to skončilo ako bytia naozaj veľké, potom najväčšieho k najmenšiemu. David J. Malan: OK. Takže najväčšieho k najmenšiemu, alebo najmenšie k najväčšej. Ale dovoľte mi navrhnúť, že by ste mali dostali nešťastný, a predpokladáme, že nebola v skutočnosti, triedenie, koľko tie dvere by ste mali nahliadnuť pozadu v tomto najhoršom prípade? JENNIFER: Všetky z nich. David J. Malan: Všetky z nich. Takže poďme sa zovšeobecniť, že pre n Tam sa stane byť 7, ale poďme sa viac sa všeobecne povedať, že je to n dvere na screen tu. Takže v najhoršom prípade, mali by ste nahliadnuť za dvere, 7 alebo N dverí. A tak to je naozaj, je to trochu šťastie dnes, ale je to naozaj lineárna algoritmus druhov, aj keď ste milý preskočenie okolo. Je to fér? JENNIFER: Jo. David J. Malan: No, dovoľte mi, či váš stratégie zmeny, keď nás posunú náš druhý príklad tu 7 rôznych dvere. Rovnaké čísla, ale čas sú radené. Aká je vaša stratégia tu bude, snaží dať zo svojej mysle, čo iné čísla bola - JENNIFER: OK. David J. Malan: - skôr? JENNIFER: Začnime s prvým. David J. Malan: Dobre. Začnite s prvou. 4. Teraz, kam ísť, a prečo? JENNIFER: 4 je naozaj malá. Takže keď tak trochu možno najmenšie po najväčšie, mala by byť sa dvakrát, a -. David J. Malan: OK. Poďme sa pozrieť, ktoré si myslíte? JENNIFER: Skúste ten posledný. Pekný. David J. Malan: Veľmi pekne urobil. Dobrá. [APPLAUSE] David J. Malan: OK. Takže ste vlastne robíš hrozne, pretože si robí to veľmi dobre. Čo nám dáva schopný vykonať určité body. Skúsme sa vrátiť späť. JENNIFER: OK. David J. Malan: Veľmi dobre práce, však. Takže ste začal na začiatku, si videl, že to bolo 4, potom presunutý na koniec. Ale predpokladajme, že ste nemali šťastie tam, a predpokladajme, 50 niekde inde. Čo si Tretím krokom bolo? JENNIFER: Vráťte sa späť na začiatok. David J. Malan: Vykonať späť na začiatok. OK, takže by ste sa na to dotkol tieto dvere, čo bolo 8.. Dobrá. Takže to nie je 50. Kam by ste sa pozrel ďalej? JENNIFER: Ak som to neurobil vedia, že radené. David J. Malan: Správne. No, ak ste vedieť boli zaradené - JENNIFER: Jo, to viem, jo. David J. Malan - ale nie vedieť, kde 50 bol ešte? JENNIFER: Len pokračuj. David J. Malan: Dobre. OK. Len tak ďalej. OK, že môžem pracovať. JENNIFER: OK. David J. Malan: Teraz, keď ste len bude ďalej, aký je váš Algoritmus pripadajúca cúval do. JENNIFER: Lineárne -. David J. Malan: Je to tak trochu lineárny. Ale dovoľte mi navrhnúť, nech mi, aby som dal na mieste. Dovoľte mi, aby som aktualizujte stránku. rovnaké číslo, rovnaké usporiadanie, Rovnaké dvere. Ale si spomeniem na ten prvý deň v triedy, keď vytrhol telefónny zoznam vo polovice, tak nejako, a to, čo bolo naša stratégia tam? JENNIFER: Začnite u stredu. David J. Malan: OK. Takže začať v polovici. Tak poďme ďalej a simulovať to. Začnite v stredu ukázať, že dvere. Takže číslo 16. Takže to, čo by urobil silný chlap, ktorý trhal telefónny zoznam na polovicu, sa dostanete do ďalšej hádať? JENNIFER: Choď v tejto polovici. David J. Malan: A prečo na pravej strane? JENNIFER: Ak by boli nejako najmenšie po najväčšie, potom by mala byť 50 na tento účel. David J. Malan: Dobrý. Úplne rozumné. Tak ako telefónny zoznam, môžete ísť do právo na rozdiel od ľavej strane, ale tu je kľúčom stánok s jedlom. Teraz môžete vyhodiť, alebo odtrhnúť, polovica tohto problému, takže vám nebude s 7 dverí, ale v skutočnosti sa len tri. Čo je zhruba polovica Veľkosť problému. Dobrá. Takže teraz, čo by ste si vykonané po prechode nie? JENNIFER: Takže 16 je ešte celkom malý, vzhľadom k 50, takže možno sa budem snažiť, podobne, je tento. David J. Malan: Dobre. 42.. Dobre, tak teraz to, čo je vaša inštinkt ti? JENNIFER: Môžem vyhodiť to a potom už len - David J. Malan: OK. Dobrá, môžete zahodiť ľavá polovica tam. JENNIFER: - vyberte jeden. David J. Malan: A pravdu. JENNIFER: Jo. David J. Malan: Takže aj keď je to ťažké vidieť snáď, keď je tu len 7 dverí, premýšľať o tom, teraz, konzistencia Algoritmus stačí aplikovať. V predchádzajúcom prípade, ste šťastie, čo bolo skvelé. Ale ste použiť heuristiku, Povedal by som, že. Môžete použiť triedenie vašich inštinktov, a vedel, že radené, či je to dosť malá na začiatku, samozrejme, máme ísť viac doprava. Ale v istom zmysle, máš šťastie, pretože možno to bolo číslo 100, a možno aj 50 bol viac v strede. Možno, že 50 je ešte tu. Ale to, čo si urobil trochu inak Tentoraz bol si urobil to isté znova a znova. A ja by som tvrdiť, že to, čo ste práve to, aj keď vplyv na telefóne Kniha príklad, je niečo oveľa viac algoritmické a oveľa menej špeciálny puzdrom. Oveľa menej inštinktívny. Takže na konci dňa, ako by môžete popísať účinnosť Prvý algoritmus, kde sa stala zľava doprava, v porovnaní Druhý algoritmus tu? JENNIFER: toto by mal, rovnako ako, možno polovicu času, alebo dokonca viac, jo. David J. Malan: OK, možno ešte viac. Poďme sa tlačiť trochu viac na to. Čo sa naozaj, ak budeme pokračovať v tejto logika, rozhodne polovicu doba chodu tohto druhého algoritmu by zahodili polovicu čísla, ale čo budeme robiť na budúci iterácie, keď Jennifer odhalil druhé číslo? Sme na polovicu počtu dverí znova. A potom to, čo sme urobili po tom, ak je tam bolo viac vráta na hranie? Radi by sme znížiť ich, a znova, a znova a znova. A to bolo len ako vy všetci vstávanie v prvom týždni triedy, polovica z vás sedieť, polovica z vás sedieť, polovica z vás sedieť, kým jeden osamelý duša stála. A my sme povedali, že doba chodu , Že počet krokov Stačilo na poradí, čo? SPEAKER 1: [nepočuteľné] David J. Malan: Takže log základňa 2 n, alebo len jednoduchšie, prihláste n Takže niečo logaritmické. A graf nebol priamka že práve dostal horšie a horšie, to bolo tento zaujímavý krivka, ktorá nie tak zle v priebehu času. Takže poďme sa držať na tejto myšlienke. Poďakujme Jennifer. Díky moc za účasť nahor. A jeden s Žiadne stolové lampy dnes, ale predsa majú CS50 stres gule. JENNIFER: Yay. David J. Malan: Tak jo, tu. Ďakujem za vynaložení stres tu. Dobrá. Tak uvidíme, keď nie teraz formalizovať to trochu viac. Takže znova, čo sme práve urobili, bolo v podstate to isté ako my v tomto prvom týždni. Ale skôr než nakoniec len s lineárnou algoritmus, ktoré je znázornené predtým ako tento priamke, kedy, keď dáme ešte jednu dvere obrazovka, potom by Jennifer musel sa pozerať, potenciálne za jeden ďalšie dvere. Ak dáme dve dvere, mohla by mať aby sa za ďalšie dve dvere. A tak, že sa tento lineárny vzťah medzi veľkosťou problém na, povedzme, x-osi a množstvo času, ktoré trvá riešenie na y. Ale obraz bol som narážal na predtým bola táto zelená linka. Zelená zámerne, pretože to jednoducho cítil lepšie. Teoreticky algoritmus, keď sme to urobili s telefónneho zoznamu, keď sme to urobili s vami počítať seba, a V druhom prípade, kedy práve Jennifer urobil to tu, to bolo niečo o zásadne lepšie. Vzhľadom k tomu, že to nie je len dvakrát tak rýchlo. Nebolo to ani štyrikrát rýchlo. To bolo úplne závislé na tom, čo veľkosť vstupu bolo, pokiaľ ide o to, koľko kroky, ktoré nakoniec trvalo. A tak to jednoduchá myšlienka, že sme všetci vzali za samozrejmosť, sa v telefónnom zozname, dokument môže byť tiež použitá niečo ako toto. A to by mohlo byť viac uvoľnene známy ako, ako by ste si mohli predstaviť, rozdeľ a panuj. Nie na rozdiel od toho, čo sme urobili, samozrejme, s telefónneho zoznamu. Ale pseudokódu, odvolanie, to bolo. Tak sme sa to urobiť znovu, ale spomínam že prvý týždeň, všetci z nás vstal a polovica z vás sa posadil, polovica si sadol, polovica z vás sa posadil. Že algoritmus bol implementovaný v trochu podvádzanie spôsobom, že to Nebolo to len jeden z mnou počítať, Podstatnejšie je, že efektívnejšie. V tomto prípade som sa využitia sekundárny zdroj. Niečo, viac procesory, viac mozog, viac chytrých ľudí vo izba bola mi pomohol dostať sa z niečoho lineárne niečo logaritmické, z niečoho červenej na niečo zelené. Ale v tomto prípade, môže Jennifer sama zásadne zlepšiť na výkon jej prvý algoritmus, Znovu som premýšľal o niečo ťažšie. A teraz, keď príde čas na vykonanie tieto veci, prísť na to, aké riadky kódu môžete písať ako že môžete opakovať znovu a znovu a znovu, tak nejako v cyklické móde. Pretože nebudete mať luxusné, rovnako ako Jennifer to na prvý pohľad, na len veľa IFS a hovoria, hmm, je to prvé číslo 4, dovoľte mi, aby som skok celú cestu až do konca. Ooh, ak toto číslo je príliš veľká, dovoľte mi, aby som pohybovať ľubovoľne späť na druhý prvok. Zistíte, že to bude veľa ťažšie formalizovať, čo my ľudia brať za samozrejmosť, za veľmi rozumné heuristiky, ale počítač je len robiť to, čo poviete to urobiť. Teraz to má veľmi zaujímavé dôsledky. Tento graf je druh chcel nejako premôcť vizuálne, ale uvedomte si, kde je priamka v tomto grafe? Kde je lineárny graf ktoré nazývame n? No, je to trochu smerom k spodnej časti obrázku, nie? Takže všetko, čo sme urobili je, že sme si trochu oddialenie na osi x a os y pokúsiť sa získať zmysel toho, čo iné typy kriviek vyzerať. A špecifiká matematické výrazy dnes nebude záležať, aby moc, ale zistíte, že je tu veľa algoritmy, ktoré sú oveľa horšie, než niečo, čo je lineárna. Naozaj, n kocky vyzerá dosť zle. 2 na n vyzerá dosť zle. n na druhú vyzerá dosť zle. A uvidíme, čo niektorí z tých, môže byť v skutočnosti dnes. A log n necíti tak zlé, ale lepšie ako n je základ log 2 n Ale viete, to by bolo ešte viac ohromujúci, pokiaľ Jennifer, alebo ak my, že prvý týždeň, prišiel s niečo, čo je log log n Takže inými slovami, je to celá Rozsah možných riešení problémy, ale aj tu si všimnite, čo sa bude diať. Keď som sa vzdialite, ktoré z týchto kriviek bude ukázať, že je absolútna Najhoršie z tých, na obrazovke teraz? Tak n kocky vyzerá celkom zle v túto chvíľu. Ale ak sa oddialiť a vidieť viac x a osi y, kto bude dominujú nakoniec? Takže to vlastne Ukazuje sa, že 2 až n, a môžete to vyriešiť len tým, zapojením niektorých čoraz väčšie čísla, a uvidíte, že 2 až n, v skutočnosti, sa zväčšuje oveľa rýchlejšie. Ak naozaj vzdialite, pre 2 až n algoritmus absolútne nič. Myslím, že to bude trvať celkom dosť času na počítač k chrliť cez. Ale uvidíte v priebehu času, a to najmä s budúcimi základné problémové okruhy a dokonca záverečných prác, je vaše dáta súbor dostane veľký, dobre? Aj v prvej verzii Facebooku, ako počet priateľov, a Počet registrovaných užívateľov má veľký, môžete nejako telefónu ho a implementovať niečo s lineárnym vyhľadávania alebo veľmi jednoduché triedenie algoritmus, ako uvidíme dnes. Musíte začať premýšľať ťažšie a ťažšie o týchto problémoch. A druhy problémov miestach, ako je Facebook a Google a Microsoft, a iní pracujú na presne tie druh veľkého dátového druhu otázok čoraz častejšie v týchto dňoch. Dobrá. Takže úspech Jennifer v tom druhom algoritmus, úprimne povedané, ona prekvapivo tiež prvýkrát, ale poďme napísať, že ako šťastie tak, že sme môže tento bod. V druhom prípade sa zadlžujú algoritmus, ktorý znovu a znova, ale vzala za samozrejmosť istý predpoklad, že smieme nej, ale ona využívané niektoré detaily Druhýkrát, že nemala prvýkrát. Čo je to, čo? To, že bol zoznam zoradený. Aby, akonáhle bol priradený zoznam, sme tvrdí, že Jennifer bol schopný urobiť zásadne lepší. 7 dverí, áno, nie je to zaujímavé, Predpokladajme však, že to, že sme 7000000 dvere. Prihlásiť n je určite vykonávať oveľa rýchlejšie v dlhodobom horizonte. Ale musela mať Dvere radené pre ňu. Teraz som si dovolil robiť, že vopred na obrazovke počítača tu, ale predpokladám, že Jennifer Musel to urobiť sama? Predpokladajme, že dvere v otázke zastúpené dáta v databáze, alebo priatelia registrovaní na Facebook, alebo všetky webové stránky na internete, ktoré rôzne webové stránky, môže byť potrebné k indexu alebo prehľadávať. Predpokladajme, že ste práve mal surové dáta nastavenie a bolo ponechané na vás, alebo Jennifer k tomu, že triedenie? To skôr si vyžaduje, aby sme odpoveď otázka, no, koľko času by trvalo Jennifer, alebo dokonca ma, triediť tie čísla vopred, aby že by mohla využiť, že? Je to tak? Vzhľadom k tomu, dôsledky, samozrejme, je ak mi trvá dosť dlho, než triedenie čísla, ktoré to zaujíma, že ťa sakra môžete nájsť číslo ako 50 tak rýchlo, rovnako ako v prípade, Jennifer, pokiaľ sa viac než ohromený množstvo celkového času trvalo triedenie veci vopred? Tak uvidíme, či nemôžeme namaľovať obraz tu. Mám celá partia väčší dôraz guľa, je-li, že pomáha prelomiť ľady tu. A ak vám to nebude vadiť, my Potrebujete sedem dobrovoľníka - na, OK. Wow. Takže nemáme utrácať na stolných lampách, zdá sa. Dobrá. Tak čo tie dva vpredu. Ako sa o vás dvaja chlapci v chrbte. Tak to je štyri. Ako sa o vás pred päť, šesť a sedem. Presne tam. Váš priateľ sa ukázal von, tak dostanete cenu. Dobrá. Poď hore. A prečo sme si chlapci poď sem. Chystám sa vám každé číslo. A do toho pustite a zariadiť sami zhodne s tým, čo je zobrazený na obrazovke. [Prechodová Hlasy] David J. Malan: OOP, je mi ľúto. Bug. Dobrá. Tak, ideme na to. Číslo päť. Číslo šesť. Jedna, dve, tri, štyri, päť, šesť, sedem. Oh, to je trápne. SPEAKER 2: Budem len dostať -. David J. Malan: dobrý obchod. Dobrá. Ďakujem vám za účasť. [APPLAUSE] OK. Dobrá. Takže máme štyri, dva, šesť, jeden, tri, sedem, päť. Perfektné takže máme sedem dobrovoľníkov , Ktorí tu sú rovnakej šírky, aby Pole, ktoré hráme s predtým. A ja som si vybral sedem dôvodov že bude len výhodné v trochu. A ja idem navrhnúť, že prvá triedime týchto sedem dobrovoľníkov. Ak by ste chceli, prvý, pozdraviť hoci. Vzhľadom k tomu bude nevhodné niekoľko minút. Predstavte sa. GRACE: Ahoj, ja som milosť. Som vo druháku na Leverett domu. BRANSON: Ahoj. Som Branson. Som prvák na zvaru. Gabe: Ahoj. Som Gabe. Som junior v Cabot. NEIL: Som Neil. Som prvák na Matthews. JASON: Som Jason. Som prvák na Greenough. MIKE: Ja som Mike. Som prvák na Grays. JESS: Som Jess. Som vo druháku na Leverett. David J. Malan: Výborný. Dobrá. No, ďakujem všetkým našim Dobrovoľníci tu tak ďaleko. A výzva na dosah ruky teraz sa deje bude triediť z týchto chlapci, ale potom budeme musieť trošku premýšľať ťažké o tom, ako efektívne sme vlastne zoradené. Takže poďme sa najprv skúsiť. Vy môžete vidieť navzájom čísla len tým, v rohoch. Nehanbite sa a trvať niekoľko sekúnd a radiť sami od najmenšej na vľavo najväčšou na pravej strane. Prejsť. OK. Dobre. To bolo naozaj čertovsky rýchlo. Teraz tu niekto, čo to bolo algoritmus že títo ľudia aplikovať? SPEAKER 1: od najmenej po najväčšie. David J. Malan: OK. Aspoň najväčší je naozaj nejako objektívne, ale nie som si istý, že to naozaj algoritmus. Aspoň najväčšie nehovorí ma krok-za-krokom, čo robiť. Jo? SPEAKER 1: [nepočuteľné] David J. Malan: OK. Takže ak uvidíte osoba menšia než Vaše telefónne číslo, potom sa presuňte na právo z nich. Tak to je teraz stále viac expresívne, spíš algoritmu, pretože Dá sa povedať,, je-li to, potom je to. Takže máme nejaký podmienené konštrukcie. A títo chlapci zrejme k tomu, že niektoré časy, pretože niektorí z vás presťahoval trochu na diaľku. Takže tam bol pravdepodobne nejaký druh opakovanie deje v ich mysliach. Ale poďme sa snaží formalizovať, že. Ak ste mohli obnoviť späť na ne toto dojednanie. Uvidíme, či sa nemôžeme formalizovať tento bit, a potom položiť otázku, len ako efektívne je to? Samozrejme, že keď budeme robiť to pomalšie, to bude mať pocit, ako dobrý algoritmus, ale uvidíme, či to pôjde dať naše prsty na presných krokoch. Takže vy dvaja sú štyri a dva. Alebo si správne alebo nesprávne, aby? Je zrejmé nesprávne. Tak sme vymenili. Teraz idem oddialiť tu a hovoria štyroch až šiestich. Ste správne alebo nesprávne? Gabe: Správne. David J. Malan: Správne. Šesť a jedna? Nie. Swap. Tak to je dva swapy. Šesť a tri? Nie. Swap. Šesť a sedem? Vyzerá to dobre. Sedem a päť? JESS: [nepočuteľné] David J. Malan: OK, vymeniť. A triediť. Dobrá. Takže samozrejme nie je, že jo? Takže tam bolo viac deje. Ale naozaj, títo ľudia, a to aj len inštinktívne. stále v pohybe. Nemali zastaviť, akonáhle sa opravený jeden problém. Tak. Naozaj, budem mať urobiť rovnakú vec. Budem musieť nejako chrbte vzad na začiatku tohto problému, alebo na začiatku tejto rady ľudia, začnime volať im. A teraz, čo by môj algoritmus Na druhom prechode bude? SPEAKER 1: To je to isté. David J. Malan: To je to isté. A to ja začínam mať rada, nie? Akonáhle si môžete nájsť sami robiť to isté znova a znova, je to čoraz viac ako algoritmus, a menej ľudský inštinkt. Takže teraz je to tu zase. Dva a štyri? Nie. Štyri a jedna? Ah, bola naozaj niektorí práce je potrebné ešte urobiť. Pre a tri? Dobre. Štyri a šesť? Šesť a päť? Šesť a sedem? OK, teraz, hotovo. OK, no. Musím sa vrátiť. Takže teraz znova, toto robíme trochu zámerne. A teraz je tu len jeden mozog vykonávanie tohto algoritmu. Jeden CPU, ak chcete. A úprimne povedané, to je jediný zdroj budeme mať prístup. A akonáhle sme sa vrátiť ku klávesnici a niečo ako C v našom likvidácia, budeme len písať program ktorý môže robiť jednu vec naraz. Vzhľadom k tomu, títo ľudia pred chvíľou sme pákový efekt, ich kolektívne inteligenčného ako ste urobili v týždni nulu. Takže poďme v tom pokračovať. Dva a Dva a tri. Tri a štyri. Štyri a päť. Päť a šesť. Šesť a sedem. Hotovo? Takže som, ale dovoľte mi, aby som hrať diablovho advokáta. Musím sa trochu počítača, ktorý práve urobil priechod tejto rady ľudí, viem, že som urobil? Reproduktor 1: Nie David J. Malan: Tak prečo? Čo by som mal urobiť, aby sa k záveru, rozhodne, že som to urobil? Pravdepodobne jeden priechod. Je to tak? Pretože viem, že od predchádzajúcej priechod je, že som opravil chybu. A to znamená, možno je tu ešte jedna chyba že musím opraviť. Tak som sa môľete byť istí len tým, prevíjanie a potom kontrola, jeden dva, a dva tri, tri a štyri, štyri a päť, päť a šesť, šesť a sedem. OK, teraz som žiadnu prácu. Môžem si určite spomenú, že som žiadny pracovať s niečím ako premenné, ako int. Nazvime to swapy, swapy a ak je 0, keď som sem, a začala na 0, potom Ja by som jednoducho hlúpe ísť ďalej tam a späť, kontrola znova a znova a znova, že jo? Vzhľadom k tomu, uviaznete v niektorých druh nekonečnej slučke. Takže akonáhle tam je 0 swapy, môžeme konštatovať, že táto algoritmus je naozaj kompletný. Teraz sa poďme dať meno na túto tému. Algoritmus, ktorý navrhujem, aby sme len implementuje, je niečo, čo nazýva bubble druh, známy ako taká v tom zmysle, že čísla, ktoré sú väčšie druh bublina cestu až na vrchol, alebo sa na koniec rady čísel. Ale ako efektívne bol tento algoritmus? Koľko krokov som musel fyzicky Vezmite si napríklad, triediť tieto sedem ľudí? Štyri až päť? OK, príliš veľa je v konečnom dôsledku bude odpoveď. Ale aj potom, konkrétne číslo nie je ani tak zaujímavé. Poďme zovšeobecniť ju ako n Takže keby som n ľudí tu, a oni boli, tak nejako, v náhodnom poradí na na začiatku, v tomto pôvodnom poradí. No, koľko krokov som mal aby sa v prvom prechode? To bol jeden, dva, tri, štyri, päť, šesť, a sú sedem ľudí, tak to je sedem, šesť -, takže je n mínus jeden pár prvýkrát. Teraz, koľko krokov som mal vziať, keď som pretočil? No, mohli by sme dokonca zdvojnásobiť, že ak sme naozaj chceli, ale teraz som Len poviem, jo, ďalšie n mínus 1. Tak n mínus jedna je dostane nepríjemné sledovať, takže sa poďme Hneď za mierne. Takže 2n krokov. Takže 14 schodov, dávať alebo brať. Koľkokrát som sa krok nabudúce? No, je to 3n. Naozaj. A teraz, v najhoršom prípade pre inštancie, by koľkokrát mám išiel tam a späť, tam a späť, vykonávanie tohto algoritmu, vymieňať ľudia na každom priechode, asi? Je to vlastne n na druhú, nie? Vzhľadom k tomu, v najhoršom prípade môžete druh ze si o tom myslíte intuitívne, aj keď to môže trvať trochu trochu času potopiť palcov V najhoršom prípade, čo by títo sedem ľudí vyzeral v podmienky zmluvy ich čísla? Úplne dozadu, nie? A len simulovať to, ako sa voláte? MIKE: Mike. David J. Malan: Mike? OK, Miku, stačí pripojiť ma tu len jedna sekunda? V skutočnosti, no. Ospravedlňujeme sa Mike, poďme vzad. Ako sa voláte? Neil Neil. David J. Malan: Neil. OK, Neil, pôjdeš sa ma, či vám to nevadí. Takže budem navrhovať, len pre jednoduchosť, že Neil je teraz v jeho najhorší možný prípad. Ale spomínam, ako som implementoval môj algoritmus. Som porovnávanie, porovnávanie, porovnávanie, porovnávanie, porovnávanie, oh. Teraz títo ľudia sú mimo prevádzka, tak som opraviť. Takže vy vymeniť. Ale teraz zvážiť, ako moc ďalej Neil nemá ísť? Je to zhruba n Viete, nie je to v skutočnosti n Je to ako, n mínus jedna, ale ja som stále rozmrzelí sledovať tiež trochu číslo, tak nech to jednoducho hovoriť n Takže ak Neil posunie o jeden krok maximálne každý čas a prejsť Neil jeden krok, Musím si to naozaj nudný pas tam a späť, to je zhruba Tým, n krokov, celkovo n krát, , Pretože to bude pre mňa že mnoho opatrení, aby sa Neil všetky spôsob, ako sa tam, kam patrí. Nieto potom všetci ostatní, ak ste boli všetci mis-nariadil rovnako. Takže hovorme bublinkové triedenie n štvorcov. Doba chodu tohto algoritmu, Výkon tohto algoritmu, Účinnosť tohto algoritmu, budeme len popísať viac všeobecne ako n na druhú. Čo je pekné, pretože som mohol urobiť Rovnaký príklad s ôsmimi ľuďmi, deväť ľudí, a milióny ľudí, a že Odpoveď sa nebude meniť. Takže ak ste to nebude vadiť, poďme obnoviť vás tam, kde ste začali. A skúsme ďalšie dva prístupy a uvidíme, či môžeme to urobiť v zásade lepší než tohle. Takže tentoraz, budem navrhovať druh iný algoritmus. To bolo veľmi múdre nás minule, a vy sa právo na správne inštinkty tak nejako prehodenie párového. Ale keď som chcel tento prístup jednoducho, a mojím cieľom je presunúť všetky z malých čísel týmto spôsobom, a tlačiť všetky veľké čísel, ktorá Tak prečo som si, že v najviac naivný spôsob, ako je to možné a či by som môže robiť lepšie, než to, čo bolo pomerne zložitý algoritmus? Tak uvidíme. Štyri je celkom malé množstvo, takže som nechám ťa tam chvíľku. Ooh, číslo dva je ešte lepší. Takže stačí krok vpred na chvíľu? To je v súčasnej dobe som najmenší číslované kandidát, a budem si pamätať ktoré sa, ako, premenné. Ale budem držať kontrolu. Je tu niekto, ktorého číslo je menšie? Šesť, no. Oh, to je Neil znova. Takže budem tlačiť staré nejako koncepčne. Neil príde dopredu. A teraz, premennú, ktorá som pomocou sa sledovať, kto má najmenší číslo je aktualizovaný, aby obsahoval Neil umiestnenia. No, uvidíme. Tri, sedem, päť. OK, ja viem, Neil bol najmenší. Čo je to tá najjednoduchšia vec Pre mňa robiť teraz? Nebudem strácať čas tým, že len bublajúce Neil jedno miesto doľava. Prečo som dal Neila, kde patrí, čo je samozrejme kde? Úplne na začiatku. Takže Neil, poď so mnou. A čo sa vlastne voláš? GRACE: Milosť. David J. Malan: Milosť. OK. Takže Milosť, bohužiaľ, ty si druh v ceste. Tak ako sme sa tento problém vyriešiť? Je to tak? Pokiaľ sa jedná o pole, je tu iba sedem miest. Pripomeňme, že s Robom, hovorili sme o deklarovať veky, a my sme mali len konečný počet vekov? Rovnaká myšlienka tu. Máme len konečný počet ints. Grace je druh v našom spôsobom, tak ako to napraviť? Najjednoduchší spôsob, ako je rád, Milosť, je mi ľúto. Budeš musieť ísť cez tam, takže môžeme vytvoriť priestor. Teraz, keď si o tom myslíte, možná Práve sme problém ešte horšie. A možno sme urobili, pretože čo keby Milosť boli na správnom mieste? Ale my vieme, že to tak nie je, pretože inak, bola by stojaci dopredu miesto Neil v tejto dobe, že jo? Už sme sa pozrela na číslo von. Dobrá. Takže teraz, Neil je na správnom mieste, a Môžem robiť mierne optimalizáciu. Pre budúci minútu, budem ignorovať Neil dohromady, tak, aby sa strácať čas, alebo náhodne vymeniť ho na zlom mieste. Takže teraz, ako mám nájsť ďalšie prvok, ktorý je najmenší? Dva. To je celkom dobré číslo, ak je Chcete urobiť krok vpred a Budem si ťa. Šesť, nie je dobré. Štyri, tri, sedem, päť, nie je dobré. Takže dovoľte mi, aby som vám pohybovať sa vaše pravé miesto. A my sme mali šťastie tentoraz. Teraz budem ignorovať dvaja chlapci, a teraz ešte jednu prejsť to. Šesť, že dosť malé číslo. Poď dopredu. Oh, ospravedlňujem sa. Grace číslo je lepšie, tak šliapnuť dopredu. Štyri. Je nám ľúto, Grace. Vráťte sa znova. Číslo tri je lepší. Sedem. Päť. A teraz, čo sa to voláte? JASON: Jason. David J. Malan: Jason. Takže Jason je teraz najmenší prvok som vybraná. Ak má ísť? Takže tam, kde je šesť. A vaše meno je znova? Gabe: Gabe. David J. Malan: Gabe. Gabe je v ceste. Čo je to tá najjednoduchšia vec robiť? Vymeňte tieto dva chlapov a pokračovať. Takže teraz uvidíme. Kto je najmenší? Štyri. Dovoľte mi trochu podvádzať. Päť bude najmenší. Zistil som ďalšie, ak chcete krok dopredu, čo mám robiť s títo ľudia, s Gabe? Swap znova. Takže teraz, stále mierne mimo prevádzku. Zistil som, Gabe ako najmenší, a preto Aj pop mu von, pohybovať sa chlapci znova. A hotovo. Takže odpoveď je rovnaká. Konečný výsledok je rovnaký. , Ktorá z týchto algoritmov je lepší? Druhý, počul som. Prečo? SPEAKER 3: Je to n krokov [nepočuteľné]. David J. Malan: Je to n kroky na najviac. Zaujímavý. Tak to je keď? Tak ako som nenašiel najmenší prvok? Koľko krokov som vziať nájsť najmenší prvok? Som sa pozerať celú cestu na konci, nie? Vzhľadom k tomu, že v najhoršom prípade, čo ak Neil bol tu? Takže stačí nájsť najmenší prvok ma berie n kroky, alebo n mínus jedna. Ale OK. Takže opraviť Neila. Pamätajte si, že minútu alebo tak dávno. Ale ako som našiel ďalšie najmenší prvok? Je to n mínus 1 alebo n mínus 2 naozaj, z počtu krokov. Tak OK. Tak som sa n mínus 2. Dobrá. Tak, že sa cíti o niečo lepšie. Dobrá. Koľko krokov nabudúce nájsť číslo tri? Tak n mínus 4. Takže to klesá, jeden menej krok na každej iterácii. Tak to sa cítiť lepšie, nie? Pokiaľ poslednej dobe to bolo zhruba n krát n, tentokrát je to n mínus jedna plus mínus n 2, a n mínus 3, a n mínus 4, bodka, bodka, bodka. Ale ak si spomínam z vašej vysokej škole učebnice, trochu podvádzať list na zadnej strane, ktorý má vzorce, ak spočítate túto radu čísel, Aký je celkový počet krokov bude, že som sa tu? To je jeden z tých, ako, n mínus 1, n krát, delené 2. Tak sa ukážte, či môžem vytiahnuť to sa len na chvíľu. A opäť som trochu zaokrúhľovania niektorých čísla len aby náš život jednoduchý, ale ak si spomínam, je to niečo, ako keby Ja n mínus jedna veci, potom n mínus 2, potom n mínus tri, to je zhruba niečo také po 2, a keď som násobiť na to, že je v skutočnosti n námestí. To sa necíti moc dobre. n n mínus na 2. Ale tu je to vec. Vo vede o počítačoch, keď sa problémy začať byť zaujímavé, ak je n dostane naozaj veľký. A vtedy, keď n sa naozaj veľké, čo z Tieto hodnoty sa chystá ovládnuť všetky z ostatných? Je to tak trochu na n na druhú, nie? Áno, delenie 2 je celkom dobrý. Ale ak hovoríme o miliardách z kusov dát, alebo biliónoch časti dát, OK, tak ste dvakrát tak rýchlo. Ale kto naozaj zaujíma, či ten veľký počet, Keď je tento faktor je, čo sa bude väčšie a väčšie. A iste, to robí viac rozdiel, než toho chlapa. Takže aj keď ste pravdu, Druhý algoritmus, budeme nazývať výber druhu, je v reálnom svete, trochu rýchlejší potenciálne, pretože som s menej a menej kroky zakaždým. V skutočnosti to nie je zásadne rýchlejšie. Pretože ak budeme skutočne hrať to von veľké hodnoty n, na konci deň, po dobu dosť veľký n, je to stále bude cítiť celkom pomalý. No, dovoľte mi, aby som jednu posledný priechod na to. To je to, čo by som nazval Výber sort. Môže vás obnoviť sami raz naposledy? A v tomto poslednom prípade, idem navrhnúť niečo volal vloženie radenie. Vloženie druh bytia, koncepčne, trochu inak. Skôr než ísť tam a späť výberom najmenší prvok, som len tak vysporiadať s každou z nich chalani, ako som sa s nimi stretnúť, a vložte je do ich správne miesto. Tak som len tak začať s Grace, a vidím, že je to číslo štyri. Kde sa číslo štyri patrí? Som sa začala triediť nič, Milosť tak dostane zostať tu. A teraz budem tvrdiť, keby si mohol krok na pravej strane, to môj radené zoznam, to je moje netriedeného zostávajúce zoznam. Takže teraz budem pokračovať ďalej, a čo sa to voláte? BRANSON: Branson. David J. Malan: Branson. Takže Branson je číslo dva. Takže budem ťa vziať sa na chvíľu zamyslel. A teraz, kam patrí v tomto poli? Takže na pravej milosti. Takže znovu, sme druh výroby Milosť urobiť veľa práce tu. Kde sme ťa? Takže budeme kĺzať vás vľavo, a vložte tam Branson. Ale teraz tvrdia, že ste hotoví. Ale oznámenia, nebudem používať extra priestor. Je to stále dva elementy tu 5. sem. Celková veľkosť poľa je 7, takže som nepodvádza, v poriadku? Takže teraz máme s Gabe tu číslo šesť, kam patrí? Máš šťastie znova. Takže ste si zostať tu. Len sa mierny krok na pravej strane len aby bolo jasné, že ste radené. A teraz máme Neil opäť číslo jedno, kam pôjdeš? A teraz je tam, kde začneme vidieť, že Tento algoritmus, aj keď na prvý pohľad, sa cíti celkom múdra, sledovať čo sa stane. Ak by ste mohli krok vpred. Kde chceme dať Neila? Je teda jasné, tu, tak ako sa dostaneme Neila tam? Poďme urobiť tento krok-za-krokom. Gabe, kde budete musieť ísť? Jo, tak sa jeden veľký krok, alebo dve polovice-kroky, aby jeden krok tam. Milosť, kam ísť? Dobre. Takže ďalší krok. A konečne, Branson? Ďalším krokom. A teraz môžeme dať Neila na miesto. Takže teraz, aj naďalej túto logiku. Aj keď nie sme presúva Neil nad, a cez, a cez, aby ho kde ide, v najhoršom prípade, ďalšie číslo môžeme stretnúť mohli je číslo, povedzme, že sa rad nula, potom sa budeme presúvať všetky títo chlapci. Predpokladajme, že existuje celý rad, negatívny jeden, potom musíme posunúť všetkých týchto ľudí. Takže sme naozaj len tak preletia problém asi tak, že sme prevedenie náklady z Výberové konanie tak vloženie proces tak, že ste jednoducho musel pohybovať zhruba n mínus niečo počet krokov. A to počet krokov je až vo chvíli, zvýšiť, keď som vybrať viac čísel, keď budem musieť držať strkať chlapci späť, a späť, a späť. Tak smutné, teraz je všetko z nich algoritmy sú n na druhú. Poďme ďalej a vďaka týmto chlapci, a vizualizovať tieto trochu inak. Veľmi dobre. [APPLAUSE] Dobrá. Tu to je. Vďaka za - BRANSON: [nepočuteľné] držať čísla. David J. Malan: Nie, môžete držať čísla rovnako. Dobrá. Dobrá práca. Dobrá. Tak uvidíme, či nemôžeme teraz zhrnúť rýchlejšie a viac vizuálne, presne to, čo sa práve stalo tu takto. Chystám sa ísť dopredu a vytiahnite Firefox. Budeme odkaz na túto demonštráciu na ihrisku internetových stránkach. Java je trochu nepríjemné, aby sa pracovné v niektorých prehliadačoch v týchto dňoch. Takže ak nechcete hrať s tým doma, Uvedomujem si, môže byť potrebné používať Firefox aby si to prácu. A čo budem robiť s tým ukážka je nasledujúci. Na dne, mám veľa možnosti ponuky, vrátane začiatku a tlačidlo stop. Tiež, ako stranou, sa zdá, že chyba v týchto programoch, pričom si nemôže skutočne vidieť štart alebo zastavenie tlačidlo, ak budete držať príkazu alebo Alt plus a zoom, ktorý zvedavo zobrazuje viac tlačidiel. Takže len FYI, ak budete hrať s tým doma. Teraz idem na tlačidlo Štart v práve Okamih, po zadaní oneskorenie, ako, 200 milisekúnd, jednoducho takže môžeme vidieť, čo sa stane. Takže tvrdím, že je to vizualizácia prvého algoritmu títo ľudia urobili, bublinková triedenia, pričom sme vymenili ľudí párová. Kľúčovou myšlienkou tohto vizualizácie je, že výška stĺpcov predstavuje veľkosť čísla. Takže je stĺpec vyšší, Čím vyššie je číslo. Kratšie bar, menšie číslo. A ak si všimnete, ideme cez Prvá iterácia tohto algoritmu, vymieňať veľké aj malé množstvo, takže malý počet je na prvom mieste a Veľké množstvo ide na pravej strane. A akonáhle sa dostaneme na koniec poľa mnoho viac ako sedem čísel, sme ísť späť na začiatok. A to predvídať. Na úplne vľavo, ten malý chlapec sa deje swap na stranu, a to proces sa opakuje. Teraz je táto vizualizácia rýchlo dostane nuda, tak nechajte ma ísť dopredu a zastavte sa , Zmeniť oneskorenie niečo oveľa rýchlejšie len preto, aby teraz, cit pre Tento algoritmus. Takže aj keď som sa ponáhľal hore, je to ako upgrade môj procesor, nákup nový počítač. Som zásadne nezmenil môj algoritmus, ale môžete naozaj vidieť viac jasne ako s ľuďmi, že veľký Čísla vyviera na vrchol, a malé čísla vyviera až na dno. A teraz toto, čo tu radené. A stranou, na námestiach, je tu len niektoré účtovníctva tam pomôže spočítať, koľko porovnanie, alebo koľko swapy majú skutočne vykonané. Dobre, poďme vyskúšať jednu z ostatné sme videli. Dovoľte mi, aby som kliknite na bubliny druhu tu, a zvolím, a celá táto webová stránka je trochu buggy. Poďme prijať riziko a spustite ho znova. Tam ideme. Tak jdem na výber druhu. Neviem, prečo menu objaví sa tam. Poďme priblíženie napraviť chyba, zmeniť na 50 rokov. Ach, poďme skutočne o to rýchlejšie. Päť milisekúnd alebo tak, a začať. Tak to je výber druh. Takže znova, myslím, že o tom, čo robil s ľuďmi tady. Išli sme cez pole a vybrané najmenší prvok znovu, a znova a znova. Teraz tvrdí, že je stále dosť zlý. To bolo ešte n štvorcový, dávať alebo brať, ale to bolo v reálnom svete, trochu rýchlejší, pretože som bol naozaj s o niečo menej krokov zakaždým. Ale hovoríme len čo? Možno 40 alebo tak, bary tu? Nehovoríme 40 miliónov. Takže to nie je úplne jasné, že bol naozaj značný zisk. Dovoľte mi, aby som sa vrátiť a zmeniť k nášmu Tretí algoritmus, ktorý bol vyberte vloženie sort. A teraz je to naozaj buggy, pretože Ponuka naozaj by nemal byť tam dole. Takže teraz budeme listovať sem a začať tento algoritmus. Pokrik, spustenie a zastavenie. Takže to jeden druhov má pekný vzor na to, kedy sme znovu vloženie ľudí, alebo v V tomto prípade, bary do ich vhodné umiestnenie. A to už urobil pred Otočil som sa. Ale tento taky, teoreticky, je stále n na druhú. Tak uvidíme, či nemôžeme zhrnúť Tieto takto. Chystám sa ísť dopredu a len preto, aby nám trochu bežným spôsobom hovorí o týchto veciach, dovoľte mi predstaviť len trochu notácie tu. Chystáte sa vidieť niečo, čo nazýva veľký O, pretože je to doslova veľký O. A to je tak, že počítač vedec alebo matematik dokonca používa popísať prevádzkovú dobu nejakého algoritmu. Koľko krokov to vlastne trvá? Teraz idem do rozpakov som sa môj rukopis tú za chvíľu. Ale dovoľte mi ísť ďalej a povedať, že to bude veľký O sem. A dovoľte, aby som vám predstavil jeden ďalší symbol, kapitál omega. Omega bude naopak, v podstate z veľkej O. keďže veľké O znamená, v najhoršom prípade, koľko času môže nejaký algoritmus prijať, Podmienky n omega bude sa, koľko času mohlo by to sa v najlepšom prípade. A uvidíme, čo máme na mysli najlepšom prípade za chvíľu. Tak začnime niečo jednoduchého. Dovoľte mi začať s lineárnym vyhľadávania. Takže nie je triedenie. Nazveme to lineárne hľadanie. A teraz, aby sa trochu tabuľka z toho. A teraz, v prípade lineárneho vyhľadávania v najhoršom prípade sledovať, koľko krokov je bude trvať ma, počet ľubovoľnej voľby? A je tu celkom n dvere alebo n celkový počet. Najhorší prípad. Koľko krokov budem musieť sa nájsť číslo 50 v poli dverí n? A prečo? Vzhľadom k tomu, že to môže byť všetko cesta cez na koniec. Takže rovnako ako Jennifer sa stretol, Číslo 50 bolo celú cestu, tak v v najhoršom prípade lineárnej hľadanie je veľký O n, budeme hovoriť. A čo najlepšom prípade, ak máte naozaj šťastie? Je to len tak, aby sa jeden krok, alebo stály počet krokov. Takže budeme popisovať to ako jeden. Tak to je celkom dobrý. Teraz, čo keby sme urobili niečo ako binárne vyhľadávanie? Takže binárne vyhľadávanie, v najhoršom prípad, vzal koľko času? [Prechodová Hlasy] David J. Malan: Takže vlastne som počul za pár miestach. Takže je to vlastne log n, dávať alebo brať, pretože ako rozdeliť zoznam na dve polovice znova a znova, a znova, sme schopní nájsť, nakoniec, je táto hodnota, či je to tam, ale je tu jeden háčik. Aký je predpoklad, že musíme brať za samozrejmosť, pre binárne vyhľadávanie? Musí byť triedené. Je to netriedi, môžete rozdeliť vec na polovicu znova a znova, a vy môže ísť vľavo, a môžete ísť vpravo, a môžete ísť doľava a doprava, ale vy ste nenájde prvok, ak zoznam nie je zoradený, pretože môžete si ho ujsť. Pretože vaše heuristiky pre prechod vľavo alebo doprava sa bude chybný, ak je to naozaj nie sú zoradené. Takže je tu akýsi skryté náklady s použitím niečo také. Teraz poďme do nášho triedenia algoritmy nehľadal - oh, vlastne ideme v tomto prázdne. Binárne hľadanie v najlepšom prípade? Je to tiež jedno, pokiaľ to len sa stane byť v samom strede poľa, alebo uprostred telefónneho zoznamu. Teraz sa poďme robiť bubliny druhu. Takže znova, teraz sa vstupom do druhy, nie hľadanie. V najhoršom prípade, koľko krokov to sme tvrdenie bublina trochu to bude trvať? n na druhú. Takže budem kresliť to. Ooh, môj rukopis vyzerá ešte horšie keď sa to predpokladá, že veľký. Dobrá. Tak to je n na druhú. A v najlepšom prípade bublinkovej druhu, koľko krokov to bude trvať? 1, počul som. Reproduktor 1: n David J. Malan: n, počul som. SPEAKER 1: 2. David J. Malan: 2, počul som. Počujem 3? Dobrá. Počul som 1, n 2, ale poďme vybrať od seba aspoň prvé z nich návrhy, 1. Nie je to zlý inštinkt, pretože to druh kopíruje vzor tu. Ale ak to trvá len jeden krok, ako v svet mohol by som tvrdiť, že zoznam je triedený, pretože keď som povolené len aby sa jeden krok, koľko prvkov mohol by som vlastne skontrolujte, či? No, len 1, čo znamená, že je n mínus 1 prvkov, ktoré by mohli byť z poriadku, a ja som jednoducho ísť na viere po pri pohľade na jeden prvok, ktorý vec je zoradený. Takže 1. Nie je opraviť tady. Takže minimálne, koľko musím sa pozrieť na? [Prechodová Hlasy] David J. Malan: n mínus jedna, alebo naozaj, n, pretože som sa treba pozrieť sa na každý prvok, aby sa ubezpečil, že to nie je mimo prevádzky. Ale opäť budeme triediť vlny nášho ruky na menších číslach a Predpokladajme, že, ako n sa zväčší, sú nezaujímavé rovnako. Tak to je bublina triedenie. A teraz, poďme sa tieto dva posledné. Výber druhu, a potom budeme robiť vloženie radenie. A potom sa stočí svojou myseľ sa niečo oveľa lepšie ako všetky z nich. Dobrá. Čo je najhoršie beh Doba výber druhu? SPEAKER 4: n na druhú. David J. Malan: n námestí, počujem. Ale prečo n na druhú, intuitívne? SPEAKER 4: Pretože sme práve urobili. David J. Malan: Pretože sme práve urobili. OK. Dobrá odpoveď. Ale intuitívne, prečo je výber radiť n na druhú? Čo musíme urobiť, znova a znova? Museli sme sa držať skenovaním, sú môžete najmenší, ste Najmenšie sú tie najmenšie. A samozrejmosť, sme boli schopní prijať n kroky, potom n mínus 1, potom n mínus 2. Ale ak si trochu pridať tie všetko, alebo ju na viere, že som pridal je s predstihom, dostaneme zhruba n na druhú mínus niektorých menších čísel. Takže budem volať to n na druhú. Ale s výberom druhu v najlepšom prípad sledovať, koľko krokov je ma vezme? SPEAKER 5: [nepočuteľné] David J. Malan: Je to bohužiaľ Stále n na druhú, nie? Pretože keď som výberom najmenší prvok, a mali sme sedem ľudí tu, Ja len viem, akonáhle sa dostanem k veľmi koniec, že ​​som našiel najmenší číslo, kde on alebo ona môže byť. Ale ako nájdem ďalšie najmenšie číslo? Musím urobiť ďalšiu prihrávku. Takže v najlepšom prípade, aký je Vstup do výberu druhu? Je to už trochu zoznamu číslo jedna, číslo dva, číslo tri, číslo štyri. Ale ja som počítač. Môžem len pozrieť na jeden vec naraz. Nemôžem nejako krok späť ako človek a povedal: ooh, to vyzerá správne. Môžem len rozhodnúť korektnosť Triediť podľa výberu najmenšie číslo. Ale aj keď som si prvé číslo jedna, či neviem niečo o iné čísla, ktoré nemám, všetko, čo som viem, že som podal rad alebo sada za sebou dvere, ktoré sú čísla, jediný spôsob, ako viem, že jedna Jednalo sa o najmenší? Ak sa dostanem až sem a uvedomiť si, sakra, jeden bol naozaj najmenší. Ale ako som sa potom rozhodne, že dva je ďalší najmenší? Tým, že robí rovnakú neefektívnosť znova a znova. Tak konečne sa vloženie druhu, how, v najhoršom prípade, sme sa, že to robí? To tiež je n na druhú. A čo s tým najlepšom prípade? Necháme to ako Cliffhanger. Budeme vyplniť tej prázdne nabudúce, ale najprv mi dovoľte navrhnúť, aby sme podstatne lepšie ako všetky z nich, v poriadku? Takže myslíte, že to, čo pre seba vloženie druh to bude. No, to nie je príliš dramatický, pretože som jediný ktorá videla zmenu. Wow. OK. Takže tu máme niečo rôzne demonštrácie. Keby som priblížiť tu, uvidíte, že na vľavo máme bubliny druh, v Stredná máme výber druhu a na krajnej pravice, máme niečo, čo sme som sa pozrel na doteraz tzv zlúčenie druhu. Ale zvážte, čo sme boli tu robíš tak ďaleko ešte dnes. Keď Jennifer prvýkrát prišiel na pódium, sme šli cez pole čísel znova a znova, s lineárnou vyhľadávania a my sme dostali lineárny dobu chodu, veľké O n, aby som tak povedal. Keď sme sa teraz považujú za sebou prvý týždeň triedy, keď sme sa rozdeľ a panuj, a my sme v telefónnom zozname slzenie, a Jennifer, a my spoločne Kľúčovou myšlienkou, že hybnou silou, ktorá mala opakovať sa znova a znova nejako zahodili, vyhadzovanie, zahodili, polovica problému, alebo všeobecne, tak, že sa problém na polovicu, a liečbe menší kus problém, koncepčne ekvivalentná na druhej strane, sa nejako zásadne lepší. Ale s bublinou druhu, s výber druhu, s vkladacie druhu, máme sa môžu žiadne také poznatky, že Jennifer urobil. Sme skoro rovnako vrátil a tam celá partia z časov, a my Upravený veci trochu, vymieňať v tomto poradí, možno vkladanie alebo výberu. Ale na konci dňa, som veľa trápne chôdze tam a späť. Nemali sme využiť čo chytrý ako Jennifer som rád delenie a dobývanie. Takže zlúčiť druh, naopak, ktoré neuvidí až do budúceho týždňa, bude to sa pákového efektu, ktorý Kľúčovou myšlienkou vydelením vstup, a potom na polovicu, a potom polovicu a potom polovicu. A pri každom opakovaní tohto cyklu, triedenie ľavú polovicu, a právo polovicu, potom Ľavá polovica ľavej polovice, a pravá polovica doľava, potom Ľavá polovica v pravej polovici, a pravá polovica v pravej polovici. A opakovať znovu a znovu. Takže budete vidieť vizuálne, ale je to, čo nás čaká budúci týždeň. A vôbec, keď si myslíme, že niečo trochu ťažšie na takéto prípadné problémy. Máme n druhú vľavo, n druhú v polovici, a n log n na pravej strane. Takže tam je váš skutočný Cliffhanger. Uvidíme sa v pondelok. [APPLAUSE]