>> [Přehrávání hudby]
>> David J. Malan: Dobře.
Tak vítej zpět.
To je CS50, a je Konec týdne tři.
>> Takže připomínají v posledních několika týdnech, jsme strávili docela dost
čas na C, na programování, na syntaxi.
A to je docela normální, pokud jste ještě zápasí s problémovými Set 2, se
bouchání hlavou proti zdi.
Je to tajemné vypadající chybové zprávy a chyby, které
nelze zcela honit.
Vzhledem k tomu, být jisti, že právě Doba pár týdnů budete ohlížet na
věci jako Caesara a [? V-genair,?] možná i Crack a
uvědomit si, jak daleko jste přišli v krátkém časovém období.
Takže jestli je to nějaká útěcha, vydrž teď.
>> V současné době se však začneme přechod na věci vyšší úrovně.
A začneme brát za samozřejmost, že vy víte, jak programovat, nebo
nejméně počátky že úroveň pohodlí.
A začneme uvažovat o tom, jak můžeme jít o navrhování programů více
efektivně.
Jak můžeme jít o optimalizaci Účinnost našich algoritmů a
obecně více řešení zajímavé problémy.
A začínají brát za samozřejmost, že kdybychom chtěli, mohli bychom kódu vzestupně každý
z příkladů, které máme na mysli.
Takže dnes jsme se nedotýkejte klávesnice pro jakékoli formě kódu.
To bude mnohem vyšší úroveň, a nakonec, o řešení problémů.
>> Takže se dostat do tohoto bodu, dovolte mi navrhnout že následující sedm
obdélníky představují sedm dveře, za které jsou celá parta
čísla, mezi nimiž je číslo 50.
Dovolte mi, abych to promítnout na tomto displej i zde.
A navrhnout, že potřebujeme dobrovolníka pomůže mi najít číslo před
internet zde.
Pojďte nahoru, v růžové.
Dobrá.
Jak se jmenujete?
>> JENNIFER: [neslyšitelné]
>> David J. Malan: Je nám líto?
>> JENNIFER: Jennifer.
>> David J. Malan: Jennifer.
Dobře, Jennifer.
Rád Vás vidím.
Pojď nahoru.
Tak to zde je sedm dveří, a to, co Chtěl bych, abys pro nás,
v přední části všech vašich spolužáků, se k nám dostanete číslo, 50.
Chcete-li najít číslo, můžete nahlédnout za některé z těchto dveří pouhým poklepáním
na jedné straně dveří, a to odhalí jeho číslo.
A podívejme se, jak rychle se Najdete u nás číslo, 50.
>> 15.
16..
50.
Dobrá práce.
Dobrá.
Potlesk pro Jennifer.
>> [APPLAUSE]
>> Dobrá.
Tak jaká byla vaše strategie pro najít číslo 50?
>> JENNIFER: Hm, myslela jsem, že pokud -
[Neslyšitelný]
>> David J. Malan: Oh.
Dejte mu jednu sekundu.
Tak byla vaše strategie pro najít číslo 50?
>> JENNIFER: Tak jsem se začít na začíná vidět, co první číslo
byl, a pak jsem si myslel, možná, pokud oni jsou řazeny, budu jen držet
klepnutím výš?
>> David J. Malan: OK.
A zdá se, že našli že tomu tak je.
I když, pojďme Sloupněte vrstvy jen trochu, a vy chcete jít
dopředu a odhalit další dveře si mohl vybrat?
>> JENNIFER: Ach jo.
>> David J. Malan: Ah.
>> JENNIFER: Tak jsem měl štěstí.
>> David J. Malan: Takže máš štěstí.
Dobrá.
Takže to není špatné.
Ale to je zajímavé, pohled, ne?
Máte-li předpokládat, a vy jste se, opravdu, trochu štěstí tam.
Ale pokud se předpokládá, že tato čísla tříděny, můžete být přesnější
jak který ovlivnil vaše chování?
>> JENNIFER: Takže pokud by byly roztříděny, jsem si myslel, že nejmenší k největší.
>> David J. Malan: OK.
>> JENNIFER: Nebo, pokud to skončilo jako bytí opravdu velké, pak největší k nejmenší.
>> David J. Malan: OK.
Takže největší k nejmenší, nebo nejmenší k největší.
Ale dovolte mi navrhnout, že byste měli dostali nešťastný, a předpokládáme, že
nebyla ve skutečnosti, třídění, kolik ty dveře by jste měli nahlédnout
pozadu v tomto nejhorším případě?
>> JENNIFER: Všechny z nich.
>> David J. Malan: Všechny z nich.
Takže pojďme se zobecnit, že pro n.
Tam se stane být 7, ale pojďme se více se obecně říci, že je to n dveře na
screen zde.
Takže v nejhorším případě, měli byste nahlédnout za dveře, 7 nebo N dveří.
A tak to je opravdu, je to trochu štěstí dnes, ale je to opravdu lineární
algoritmus druhů, i když jste milý přeskočení kolem.
Je to fér?
>> JENNIFER: Jo.
>> David J. Malan: No, dovolte mi, zda váš strategie změny, když nás posunou
náš druhý příklad zde 7 různých dveře.
Stejná čísla, ale čas jsou řazeny.
Jaká je vaše strategie zde bude, snaží dát ze své mysli, co
jiná čísla byla -
>> JENNIFER: OK.
>> David J. Malan: - dřív?
>> JENNIFER: Začněme s prvním.
>> David J. Malan: Dobře.
Začněte s první.
4.
Nyní, kam jít, a proč?
>> JENNIFER: 4 je opravdu malá.
Takže když tak trochu možná nejmenší po největší, měla by být
se dvakrát, a -.
>> David J. Malan: OK.
Pojďme se podívat, které si myslíte?
>> JENNIFER: Zkuste ten poslední.
Pěkný.
>> David J. Malan: Velmi pěkně udělal.
Dobrá.
>> [APPLAUSE]
>> David J. Malan: OK.
Takže jste vlastně děláš hrozně, protože jsi
dělá to velmi dobře.
Což nám dává schopen provést určité body.
Zkusme se vrátit zpátky.
>> JENNIFER: OK.
>> David J. Malan: Velmi dobře práce, nicméně.
Takže jste začal na začátku, jsi viděl, že to bylo 4, pak
přesunut na konec.
Ale předpokládejme, že jste neměli štěstí tam, a předpokládejme, 50
někde jinde.
Co si Třetím krokem bylo?
>> JENNIFER: Vraťte se zpět na začátek.
>> David J. Malan: Jít zpět na začátek.
OK, takže byste se na to dotkl tyto dveře, což bylo 8..
Dobrá.
Takže to není 50.
Kam by jste se podíval dál?
>> JENNIFER: Pokud jsem to neudělal vědí, že řazeny.
>> David J. Malan: Správně.
No, pokud jste vědět byly zařazeny -
>> JENNIFER: Jo, to vím, jo.
>> David J. Malan - ale ne vědět, kde 50 byl ještě?
>> JENNIFER: Jen pokračuj.
>> David J. Malan: Dobře.
OK.
Jen tak dál.
OK, že mohu pracovat.
>> JENNIFER: OK.
>> David J. Malan: Teď, když jste jen bude dál, jaký je váš
Algoritmus připadající couval do.
>> JENNIFER: Lineární -.
>> David J. Malan: Je to tak trochu lineární.
Ale dovolte mi navrhnout, ať mi, abych dal na místě.
Dovolte mi, abych aktualizujte stránku.
stejné číslo, stejné uspořádání, Stejné dveře.
Ale si vzpomenu na ten první den v třídy, když vytrhl telefonní seznam ve
poloviny, tak nějak, a to, co bylo naše strategie tam?
>> JENNIFER: Začněte u středu.
>> David J. Malan: OK.
Takže začít v polovině.
Tak pojďme dál a simulovat to.
Začněte u středu ukázat, že dveře.
Takže číslo 16.
Takže to, co by udělal silný chlap, který trhal telefonní seznam na polovinu,
se dostanete do další hádat?
>> JENNIFER: Jdi v této polovině.
>> David J. Malan: A proč na pravé straně?
>> JENNIFER: Pokud by byly nějak nejmenší po největší, pak by měla být 50
na tento účel.
>> David J. Malan: Dobrý.
Naprosto rozumné.
Tak jako telefonní seznam, můžete jít do právo na rozdíl od levé straně, ale zde
je klíčem stánek s jídlem.
Nyní můžete vyhodit, nebo odtrhnout, polovina tohoto problému, takže vám nebude
s 7 dveří, ale ve skutečnosti se jen tři.
Což je zhruba polovina Velikost problému.
Dobrá.
Takže teď, co byste si provedeno po přechodu ne?
>> JENNIFER: Takže 16 je ještě docela malý, vzhledem k 50, takže možná se budu snažit,
podobně, je tento.
>> David J. Malan: Dobře.
42..
Dobře, tak teď to, co je vaše instinkt ti?
>> JENNIFER: Mohu vyhodit to a pak už jen -
>> David J. Malan: OK.
Dobrá, můžete zahodit levá polovina tam.
>> JENNIFER: - vyberte jeden.
>> David J. Malan: A pravdu.
>> JENNIFER: Jo.
>> David J. Malan: Takže i když je to těžké vidět snad, když je tu jen
7 dveří, přemýšlet o tom, teď, konzistence
Algoritmus stačí aplikovat.
V předchozím případě, jste štěstí, což bylo skvělé.
Ale jste použít heuristiku, Řekl bych, že.
Můžete použít třídění vašich instinktů, a věděl, že řazeny, jestli je to dost
malá na začátku, samozřejmě, máme jít víc doprava.
Ale v jistém smyslu, máš štěstí, protože možná to bylo číslo 100,
a možná i 50 byl více ve středu.
Možná, že 50 je ještě tady.
>> Ale to, co jsi udělal trochu jinak Tentokrát byl jsi udělal to samé
znovu a znovu.
A já bych tvrdit, že to, co jste právě to, i když vliv na telefonu
Kniha příklad, je něco mnohem více algoritmické a mnohem
méně speciální pouzdrem.
Mnohem méně instinktivní.
Takže na konci dne, jak by můžete popsat účinnost
První algoritmus, kde se stala zleva doprava, ve srovnání
Druhý algoritmus tady?
>> JENNIFER: tohle by měl, stejně jako, možná polovinu času, nebo dokonce více, jo.
>> David J. Malan: OK, možná ještě víc.
Pojďme se tlačit trochu víc na to.
Co se opravdu, pokud budeme pokračovat v této logika, rozhodně polovinu
doba chodu tohoto druhého algoritmu by zahodili polovinu
čísla, ale co budeme dělat na příští iterace, když Jennifer odhalil
druhé číslo?
>> Jsme na polovinu počtu dveří znovu.
A pak to, co jsme udělali po tom, je-li tam bylo více vrata na hraní?
Rádi bychom snížit je, a znovu, a znovu a znovu.
A to bylo jen jako vy všichni vstávání v prvním týdnu
třídy, polovina z vás sedět, polovina z vás sedět, polovina z vás
sedět, dokud jeden osamělý duše stála.
A my jsme řekli, že doba chodu , že počet kroků Stačilo
na pořadí, co?
>> SPEAKER 1: [neslyšitelné]
>> David J. Malan: Takže log základna 2 n, nebo jen jednodušeji, přihlaste n.
Takže něco logaritmická.
A graf nebyl přímka že právě dostal horší a horší, to bylo
tento zajímavý křivka, která ne tak zle v průběhu času.
Takže pojďme se držet na této myšlence.
Poděkujme Jennifer.
Díky moc za účast nahoru.
A jeden s.
Žádné stolní lampy dnes, ale přece mají CS50 stres koule.
>> JENNIFER: Yay.
>> David J. Malan: Tak jo, tady.
Děkuji za vynaložení stres tady.
Dobrá.
Tak uvidíme, když ne teď formalizovat to trochu víc.
Takže znovu, co jsme právě udělali, bylo v podstatě totéž jako my
v tomto prvním týdnu.
Ale spíše než nakonec jen s lineární algoritmus, které je znázorněno
dříve jako tento přímce, kdy, když dáme ještě jednu dveře
obrazovka, pak by Jennifer musel se dívat, potenciálně
za jeden další dveře.
Pokud dáme dvě dveře, mohla by mít aby se za další dvě dveře.
>> A tak, že se tento lineární vztah mezi velikostí
problém na, řekněme, x-osy a množství času, které trvá
řešení na y.
Ale obraz byl jsem narážel na dříve byla tato zelená linka.
Zelená záměrně, protože to prostě cítil lépe.
Teoreticky algoritmus, když jsme to udělali s telefonního seznamu, když jsme to udělali
s vámi počítat sebe, a V druhém případě, kdy právě Jennifer
udělal to tady, to bylo něco o zásadně lepší.
Vzhledem k tomu, že to není jen dvakrát tak rychle.
Nebylo to ani čtyřikrát rychle.
To bylo zcela závislé na tom, co velikost vstupu bylo, pokud jde o to, kolik
kroky, které nakonec trvalo.
>> A tak to jednoduchá myšlenka, že jsme všichni vzali za samozřejmost, se v telefonním seznamu,
dokument může být rovněž použita něco jako tohle.
A to by mohlo být více uvolněně známý jako, jak byste si mohli
představit, rozděl a panuj.
Ne na rozdíl od toho, co jsme udělali, samozřejmě, s telefonního seznamu.
>> Ale pseudokódu, odvolání, to bylo.
Tak jsme se to udělat znovu, ale vzpomínám že první týden, všichni z nás vstal
a polovina z vás se posadil, polovina si sedl, polovina z vás se posadil.
Že algoritmus byl implementován v trochu podvádění způsobem, že to
Nebylo to jen jeden z mnou počítat, Podstatnější je, že efektivněji.
V tomto případě jsem se využití sekundární zdroj.
Něco, více procesory, více mozek, více chytrých lidí ve
pokoj byl mi pomohl dostat se z něčeho lineární něco
logaritmická, z něčeho červené na něco zeleného.
>> Ale v tomto případě, může Jennifer sama zásadně zlepšit na
výkon její první algoritmus, Znovu jsem přemýšlel o něco těžší.
A teď, když přijde čas na provedení tyto věci, přijít na to,
jaké řádky kódu můžete psát jako že můžete opakovat znovu a
znovu a znovu, tak nějak v cyklické módě.
Protože nebudete mít luxusní, stejně jako Jennifer to na první pohled, na
jen spoustu IFS a říkají, hmm, je-li to první číslo 4,
dovolte mi, abych skok celou cestu až do konce.
Ooh, pokud toto číslo je příliš velká, dovolte mi, abych pohybovat libovolně zpět
na druhý prvek.
Zjistíte, že to bude hodně těžší formalizovat, co my lidé
brát za samozřejmost, za velmi rozumné heuristiky, ale počítač je jen
dělat to, co řeknete to udělat.
>> Teď to má velmi zajímavé důsledky.
Tento graf je druh chtěl nějak přemoci vizuálně, ale uvědomte si, kde
je přímka v tomto grafu?
Kde je lineární graf které nazýváme n?
No, je to trochu směrem ke spodní části obrázku, ne?
Takže všechno, co jsme udělali je, že jsme si trochu oddálení na ose x a
osa y pokusit se získat smysl toho, co jiné typy křivek vypadat.
>> A specifika matematické výrazy dnes nebude záležet, aby
moc, ale zjistíte, že je tu spousta algoritmy, které jsou mnohem horší, než
něco, co je lineární.
Opravdu, n kostičky vypadá dost špatně.
2 na n vypadá dost špatně. n na druhou vypadá dost špatně.
A uvidíme, co někteří z těch, může být ve skutečnosti dnes.
A log n necítí tak špatné, ale lepší než n je základ log 2 n.
Ale víte, to by bylo ještě více ohromující, pokud Jennifer, nebo pokud my,
že první týden, přišel s něco, co je log log n.
>> Takže jinými slovy, je to celá Rozsah možných řešení
problémy, ale i zde si všimněte, co se bude dít.
Když jsem se vzdálíte, které z těchto křivek bude ukázat, že je absolutní
Nejhorší z těch, na obrazovce teď?
Tak n kostičky vypadá docela špatně v tuto chvíli.
Ale pokud se oddálit a vidět víc x a osy y, kdo bude
dominují nakonec?
Takže to vlastně Ukazuje se, že 2 až n, a můžete to vyřešit jen tím,
zapojením některých stále větší čísla, a uvidíte, že 2 až
n, ve skutečnosti, se zvětšuje mnohem rychleji.
Pokud opravdu vzdálíte, pro 2 až n algoritmus absolutně nic.
Myslím, že to bude trvat docela dost času na
počítač k chrlit přes.
>> Ale uvidíte v průběhu času, a to zejména s budoucími základní problémové okruhy a dokonce
závěrečných prací, je vaše data soubor dostane velký, dobře?
I v první verzi Facebooku, jako počet přátel, a
Počet registrovaných uživatelů má velký, můžete nějak telefonu jej a
implementovat něco s lineárním vyhledávání nebo velmi jednoduché třídění
algoritmus, jak uvidíme dnes.
Musíte začít přemýšlet těžší a těžší o těchto problémech.
A druhy problémů místech, jako je Facebook a Google a Microsoft,
a jiní pracují na přesně ty druh velkého datového druhu otázek
stále častěji v těchto dnech.
>> Dobrá.
Takže úspěch Jennifer v tom druhém algoritmus, upřímně řečeno, ona překvapivě
také poprvé, ale pojďme napsat, že jak štěstí tak, že jsme
může tento bod.
V druhém případě se zadlužuje algoritmus, který znovu a
znovu, ale vzala za samozřejmost jistý předpoklad, že smíme
ní, ale ona využívány některé detaily Podruhé, že neměla
poprvé.
Což je to, co?
>> To, že byl seznam seřazen.
Aby, jakmile byl přiřazen seznam, jsme tvrdí, že Jennifer byl schopen udělat
zásadně lepší.
7 dveří, ano, není to zajímavé, Předpokládejme však, že to, že jsme 7000000 dveře.
Přihlásit n je určitě provádět mnohem
rychleji v dlouhodobém horizontu.
Ale musela mít Dveře řazeny pro ni.
Teď jsem si dovolil dělat, že předem na obrazovce počítače
tady, ale předpokládám, že Jennifer Musel to udělat sama?
Předpokládejme, že dveře v otázce zastoupeny data v databázi, nebo
přátelé registrovaní na Facebook, nebo všechny webové stránky na internetu, které
různé webové stránky, může být nutné k indexu nebo prohledávat.
>> Předpokládejme, že jste právě měl surová data nastavení a bylo ponecháno na vás, nebo
Jennifer k tomu, že třídění?
To spíše vyžaduje, abychom odpověď otázka, no, kolik času
by trvalo Jennifer, nebo dokonce mě, třídit ty čísla předem, aby
že by mohla využít, že?
Je to tak?
Vzhledem k tomu, důsledky, samozřejmě, je pokud mi trvá docela dlouho, než třídění
čísla, které to zajímá, že tě sakra můžete najít číslo jako 50 tak rychle,
stejně jako v případě, Jennifer, pokud se více než ohromen množství celkového času
trvalo třídění věci předem?
>> Tak uvidíme, jestli nemůžeme namalovat obraz tady.
Mám celá parta větší důraz koule, je-li, že pomáhá
prolomit ledy zde.
A pokud vám to nebude vadit, my Potřebujete sedm dobrovolníka -
na, OK.
Wow.
Takže nemáme utrácet na stolních lampách, zdá se.
Dobrá.
Tak co ty dva vpředu.
Jak se o vás dva kluci v zádech.
Tak to je čtyři.
Jak se o vás před pět, šest a sedm.
Přesně tam.
Váš přítel se ukázal ven, tak dostanete cenu.
>> Dobrá.
Pojď nahoru.
A proč jsme si kluci pojď sem.
Chystám se vám každé číslo.
A do toho pusťte a zařídit sami shodně s tím, co je
zobrazen na obrazovce.
>> [Přechodová Hlasy]
>> David J. Malan: OOP, je mi líto.
Bug.
Dobrá.
Tak, jdeme na to.
Číslo pět.
Číslo šest.
Jedna, dvě, tři, čtyři, pět, šest, sedm.
Oh, to je trapné.
>> SPEAKER 2: Budu jen dostat -.
>> David J. Malan: dobrý obchod.
Dobrá.
Děkuji vám za účast.
>> [APPLAUSE]
>> OK.
Dobrá.
Takže máme čtyři, dva, šest, jeden, tři, sedm, pět.
Perfektní takže máme sedm dobrovolníků , kteří zde jsou stejné šířky, aby
Pole, které hrajeme s dříve.
A já jsem si vybral sedm důvodů že bude jen
výhodné v trochu.
A já jdu navrhnout, že první třídíme těchto sedm dobrovolníků.
Pokud byste chtěli, první, pozdravit ačkoli.
Vzhledem k tomu bude nevhodné několik minut.
Představte se.
>> GRACE: Ahoj, já jsem milost.
Jsem ve druháku na Leverett domu.
>> BRANSON: Ahoj.
Jsem Branson.
Jsem v prváku na svaru.
>> GABE: Ahoj.
Jsem Gabe.
Jsem junior v Cabot.
>> NEIL: Jsem Neil.
Jsem v prváku na Matthews.
>> JASON: Jsem Jason.
Jsem v prváku na Greenough.
>> MIKE: Já jsem Mike.
Jsem v prváku na Grays.
>> JESS: Jsem Jess.
Jsem ve druháku na Leverett.
>> David J. Malan: Výborný.
Dobrá.
No, děkuji všem našim Dobrovolníci zde tak daleko.
A výzva na dosah ruky teď se děje bude třídit z těchto kluci, ale pak
budeme muset trošku přemýšlet těžké o tom, jak efektivně jsme vlastně
seřazené.
Takže pojďme se nejprve zkusit.
Vy můžete vidět navzájem čísla jen tím, v rozích.
Nestyď se a trvat několik sekund a řadit sami od nejmenší na
vlevo největší na pravé straně.
Přejít.
>> OK.
Dobře.
To bylo opravdu zatraceně rychle.
Teď tady někdo, co to bylo algoritmus že tito lidé aplikovat?
>> SPEAKER 1: od nejméně po největší.
>> David J. Malan: OK.
Alespoň největší je opravdu nějak objektivní, ale nejsem si jistý, že to
opravdu algoritmus.
Alespoň největší neříká mě krok-za-krokem, co dělat.
Jo?
>> SPEAKER 1: [neslyšitelné]
>> David J. Malan: OK.
Takže pokud uvidíte osoba menší než Vaše telefonní číslo, pak se přesuňte na
právo z nich.
Tak to je nyní stále více expresivní, spíš algoritmu, protože
Dá se říci,, je-li to, pak je to.
Takže máme nějaký podmíněné konstrukce.
A tihle kluci zřejmě k tomu, že některé časy, protože někteří z vás přestěhoval trochu
na dálku.
Takže tam byl pravděpodobně nějaký druh opakování děje v jejich myslích.
>> Ale pojďme se snaží formalizovat, že.
Pokud jste mohli obnovit zpět na ně toto ujednání.
Uvidíme, jestli se nemůžeme formalizovat tento bit, a pak položit otázku, jen
jak efektivní je to?
Samozřejmě, že když budeme dělat to pomaleji, to bude mít pocit, jako dobrý
algoritmus, ale uvidíme, jestli to půjde dát naše prsty na přesných krocích.
>> Takže vy dva jsou čtyři a dva.
Nebo si správné nebo nesprávné, aby?
Je zřejmé nesprávné.
Tak jsme vyměnili.
Teď jdu oddálit tady a říkají čtyř až šesti.
Jste správné nebo nesprávné?
>> GABE: Správně.
>> David J. Malan: Správně.
Šest a jedna?
Ne.
Swap.
Tak to je dva swapy.
Šest a tři?
Ne.
Swap.
Šest a sedm?
Vypadá to dobře.
Sedm a pět?
>> JESS: [neslyšitelné]
>> David J. Malan: OK, vyměnit.
A třídit.
Dobrá.
Takže samozřejmě není, že jo?
Takže tam bylo více děje.
Ale opravdu, tito lidé, a to i jen instinktivně.
stále v pohybu.
Neměli zastavit, jakmile se opraven jeden problém.
Tak.
Opravdu, budu mít udělat stejnou věc.
Budu muset nějak zádech vzad na začátku tohoto problému,
nebo na začátku této řady lidé, začněme volat jim.
>> A teď, co by můj algoritmus Na druhém průchodu bude?
>> SPEAKER 1: To je totéž.
>> David J. Malan: To je totéž.
A to já začínám mít ráda, ne?
Jakmile si můžete najít sami dělat totéž znovu a znovu, je to
stále více jako algoritmus, a méně lidský instinkt.
>> Takže teď je to tady zase.
Dva a čtyři?
Ne.
Čtyři a jedna?
Ah, byla opravdu někteří práce je třeba ještě udělat.
Pro a tři?
Dobře.
Čtyři a šest?
Šest a pět?
Šest a sedm?
OK, teď, hotovo.
OK, no.
Musím se vrátit.
>> Takže teď znovu, tohle děláme trochu záměrně.
A teď je tu jen jeden mozek provádění tohoto algoritmu.
Jeden CPU, chcete-li.
A upřímně řečeno, to je jediný zdroj budeme mít přístup.
A jakmile jsme se vrátit ke klávesnici a něco jako C v našem
likvidace, budeme jen psát program který může dělat jednu věc najednou.
Vzhledem k tomu, tito lidé před chvílí jsme pákový efekt, jejich kolektivní inteligenčního
jako jste udělali v týdnu nulu.
Takže pojďme v tom pokračovat.
>> Dva a.
Dva a tři.
Tři a čtyři.
Čtyři a pět.
Pět a šest.
Šest a sedm.
Hotovo?
Takže jsem, ale dovolte mi, abych hrát ďáblova advokáta.
Musím se trochu počítače, který právě udělal průchod této řady
lidí, vím, že jsem udělal?
>> Reproduktor 1: Ne
>> David J. Malan: Tak proč?
Co bych měl udělat, aby se k závěru, rozhodně, že jsem to udělal?
Pravděpodobně jeden průchod.
Je to tak?
Protože vím, že od předchozí průchod je, že jsem opravil chybu.
A to znamená, možná je tu ještě jedna chyba
že musím opravit.
Tak jsem se můľete být jisti pouze tím, převíjení a pak kontrola, jeden dva, a dva
tři, tři a čtyři, čtyři a pět, pět a šest, šest a sedm.
OK, teď jsem žádnou práci.
>> Mohu si určitě vzpomenou, že jsem žádný pracovat s něčím jako proměnné,
jako int.
Nazvěme to swapy, swapy a pokud je 0, když jsem sem, a začala na 0, pak
Já bych prostě hloupé jít dál tam a zpět, kontrola znovu a
znovu a znovu, že jo?
Vzhledem k tomu, uvíznete v některých druh nekonečné smyčce.
Takže jakmile tam je 0 swapy, můžeme konstatovat, že tato
algoritmus je opravdu kompletní.
>> Nyní se pojďme dát jméno na toto téma.
Algoritmus, který navrhuji, abychom jen implementuje, je něco, co nazývá bubble
druh, známý jako taková v tom smyslu, že čísla, která jsou větší druh
bublina cestu až na vrchol, nebo se na konec řady čísel.
Ale jak efektivní byl tento algoritmus?
Kolik kroků jsem musel fyzicky Vezměte si například, třídit tyto
sedm lidí?
>> Čtyři až pět?
OK, příliš mnoho je v konečném důsledku bude odpověď.
Ale i pak, konkrétní číslo není ani tak zajímavé.
Pojďme zobecnit ji jako n.
Takže kdybych n lidi tady, a oni byli, tak nějak, v náhodném pořadí na
na začátku, v tomto původním pořadí.
No, kolik kroků jsem měl aby se v prvním průchodu?
To byl jeden, dva, tři, čtyři, pět, šest, a jsou sedm lidí, tak
to je sedm, šest -, takže je n minus jeden pár poprvé.
>> Nyní, kolik kroků jsem měl vzít, když jsem přetočil?
No, mohli bychom dokonce zdvojnásobit, že pokud jsme opravdu chtěli, ale teď jsem
Jen řeknu, jo, další n minus 1.
Tak n mínus jedna je dostane nepříjemné sledovat, takže se pojďme
Hned za mírně.
Takže 2n kroků.
Takže 14 schodů, dávat nebo brát.
>> Kolikrát jsem se krok příště?
No, je to 3n.
Opravdu.
A nyní, v nejhorším případě pro instance, by kolikrát mám
šel tam a zpět, tam a zpět, provádění tohoto algoritmu, vyměňovat
lidé na každém průchodu, asi?
Je to vlastně n na druhou, ne?
>> Vzhledem k tomu, v nejhorším případě můžete druh ze si o tom myslíte intuitivně,
i když to může trvat trochu trochu času potopit palců
V nejhorším případě, co by tito sedm lidí vypadal v
podmínky smlouvy jejich čísla?
Zcela dozadu, ne?
A jen simulovat to, jak se jmenujete?
>> MIKE: Mike.
>> David J. Malan: Mike?
OK, Miku, stačí připojit mě zde jen jedna sekunda?
Ve skutečnosti, no.
Omlouváme se Mike, pojďme vzad.
Jak se jmenujete?
>> Neil Neil.
>> David J. Malan: Neil.
OK, Neil, půjdeš se mě, jestli vám to nevadí.
Takže budu navrhovat, jen pro jednoduchost, že Neil je nyní v jeho
nejhorší možný případ.
Ale vzpomínám, jak jsem implementoval můj algoritmus.
Jsem porovnávání, srovnávání, porovnávání, porovnávání, srovnávání, oh.
Nyní tito lidé jsou mimo provoz, tak jsem opravit.
Takže vy vyměnit.
Ale teď zvážit, jak moc dál Neil nemá jít?
Je to zhruba n.
Víte, není to ve skutečnosti n.
Je to jako, n mínus jedna, ale já jsem stále rozmrzelí sledovat také trochu
číslo, tak ať to prostě říkat n.
>> Takže pokud Neil posune o jeden krok maximálně každý čas a přejít Neil jeden krok,
Musím si to opravdu nudný pas tam a zpět, to je zhruba
Tím, n kroků, celkem n krát, , protože to bude pro mě
že mnoho opatření, aby se Neil všechny způsob, jak se tam, kam patří.
Natož pak všichni ostatní, pokud jste byli všichni mis-nařídil stejně.
>> Takže říkejme bublinkové třídění n čtverců.
Doba chodu tohoto algoritmu, Výkon tohoto algoritmu,
Účinnost tohoto algoritmu, budeme jen popsat více
obecně jako n na druhou.
Což je pěkné, protože jsem mohl udělat Stejný příklad s osmi lidmi, devět
lidí, a miliony lidí, a že Odpověď se nebude měnit.
>> Takže pokud jste to nebude vadit, pojďme obnovit vás tam, kde jste začali.
A zkusme další dva přístupy a uvidíme, jestli můžeme to udělat v zásadě
lepší než tohle.
Takže tentokrát, budu navrhovat druh jiný algoritmus.
To bylo velmi chytré nás minule, a vy se právo na
správné instinkty tak nějak přehození párového.
Ale když jsem chtěl tento přístup jednoduše, a mým cílem je přesunout
všechny z malých čísel tímto způsobem, a tlačit všechny velké čísel, která
Tak proč jsem si, že v nejvíce naivní způsob, jak je to možné a jestli bych
může dělat lépe, než to, co bylo poměrně složitý algoritmus?
>> Tak uvidíme.
Čtyři je docela malé množství, takže jsem nechám tě tam chvilku.
Ooh, číslo dvě je ještě lepší.
Takže stačí krok vpřed na chvíli?
To je v současné době jsem nejmenší číslované kandidát, a budu si pamatovat
které se, jako, proměnné.
Ale budu držet kontrolu.
Je tu někdo, jehož číslo je menší?
Šest, no.
Oh, to je Neil znovu.
>> Takže budu tlačit zpátky nějak koncepčně.
Neil přijde dopředu.
A teď, proměnnou, která jsem pomocí se sledovat, kdo má nejmenší
číslo je aktualizován, aby obsahoval Neil umístění.
No, uvidíme.
Tři, sedm, pět.
OK, já vím, Neil byl nejmenší.
Co je to ta nejjednodušší věc Pro mě dělat teď?
Nebudu ztrácet čas tím, že jen bublající Neil jedno místo doleva.
Proč jsem dal Neila, kde patří, což je samozřejmě kde?
>> Úplně na začátku.
Takže Neil, pojď se mnou.
A co se vlastně jmenuješ?
>> GRACE: Milost.
>> David J. Malan: Milost.
OK.
Takže Milost, bohužel, ty jsi druh v cestě.
Tak jak jsme se tento problém vyřešit?
Je to tak?
Pokud se jedná o pole, je tu pouze sedm míst.
Připomeňme, že s Robem, mluvili jsme o deklarovat věky, a my jsme měli jen
konečný počet věků?
Stejná myšlenka tady.
Máme jen konečný počet ints.
Grace je druh v našem způsobem, tak jak to napravit?
>> Nejjednodušší způsob, jak je rád, Milost, je mi líto.
Budeš muset jít přes tam, takže můžeme vytvořit prostor.
Teď, když si o tom myslíte, možná Právě jsme problém ještě horší.
A možná jsme udělali, protože co kdyby Milost byli na správném místě?
Ale my víme, že to tak není, protože jinak, byla by
stojící dopředu místo Neil v této době, že jo?
Už jsme se podívala na číslo ven.
>> Dobrá.
Takže teď, Neil je na správném místě, a Můžu dělat mírné optimalizaci.
Pro příští minutu, budu ignorovat Neil dohromady, tak, aby se
ztrácet čas, nebo náhodně vyměnit ho na špatném místě.
Takže teď, jak mám najít další prvek, který je nejmenší?
Dva.
To je docela dobré číslo, je-li Chcete udělat krok vpřed a
Budu si tě.
Šest, není dobré.
Čtyři, tři, sedm, pět, není dobré.
Takže dovolte mi, abych vám pohybovat se vaše pravé místo.
A my jsme měli štěstí tentokrát.
>> Teď budu ignorovat dva kluci, a teď ještě jednu
projít to.
Šest, že dost malé číslo.
Pojď dopředu.
Oh, omlouvám se.
Grace číslo je lepší, tak šlápnout dopředu.
Čtyři.
Je nám líto, Grace.
Vraťte se znovu.
Číslo tři je lepší.
Sedm.
Pět.
A teď, co se to jmenujete?
>> JASON: Jason.
>> David J. Malan: Jason.
Takže Jason je nyní nejmenší prvek jsem vybrána.
Pokud má jít?
Takže tam, kde je šest.
A vaše jméno je znovu?
>> GABE: Gabe.
>> David J. Malan: Gabe.
Gabe je v cestě.
Co je to ta nejjednodušší věc dělat?
Vyměňte tyto dva chlapy a pokračovat.
Takže teď uvidíme.
Kdo je nejmenší?
Čtyři.
Dovolte mi trochu podvádět.
Pět bude nejmenší.
Zjistil jsem další, pokud chcete krok dopředu, co mám dělat s
tito lidé, s Gabe?
Swap znovu.
Takže teď, stále mírně mimo provoz.
Zjistil jsem, Gabe jako nejmenší, a proto I pop mu ven, pohybovat se kluci znovu.
A hotovo.
>> Takže odpověď je stejná.
Konečný výsledek je stejný.
, Která z těchto algoritmů je lepší?
Druhý, slyšel jsem.
Proč?
>> SPEAKER 3: Je to n kroků [neslyšitelné].
>> David J. Malan: Je to n kroky na nejvíce.
Zajímavý.
Tak to je když?
Tak jak jsem nenašel nejmenší prvek?
Kolik kroků jsem vzít najít nejmenší prvek?
Jsem se dívat celou cestu na konci, ne?
Vzhledem k tomu, že v nejhorším případě, co pokud Neil byl tady?
Takže stačí najít nejmenší prvek mě bere n kroky, nebo n mínus jedna.
Ale OK.
Takže opravit Neila.
Pamatujte si, že minutu nebo tak dávno.
>> Ale jak jsem našel další nejmenší prvek?
Je to n mínus 1 nebo n minus 2 opravdu, z počtu kroků.
Tak OK.
Tak jsem se n mínus 2.
Dobrá.
Tak, že se cítí o něco lépe.
Dobrá.
Kolik kroků příště najít číslo tři?
Tak n mínus 4.
Takže to klesá, jeden méně krok na každé iteraci.
Tak to se cítit lépe, ne?
Pokud poslední době to bylo zhruba n krát n, tentokrát je to n mínus jedna plus mínus n
2, a n minus 3, a n minus 4, tečka, tečka, tečka.
Ale pokud si vzpomínám z vaší vysoké škole učebnice, trochu podvádět
list na zadní straně, který má vzorce, pokud sečtete tuto řadu čísel,
Jaký je celkový počet kroků bude, že jsem se tady?
>> To je jeden z těch, jako, n minus 1, n krát, děleno 2.
Tak se ukažte, jestli můžu vytáhnout to se jen na chvíli.
A opět jsem trochu zaokrouhlování některých čísla jen aby náš život jednoduchý,
ale pokud si vzpomínám, je to něco, jako kdyby Já n mínus jedna věci, pak n minus
2, pak n mínus tři, to je zhruba něco takového po 2, a když jsem
násobit na to, že je ve skutečnosti n náměstí.
To se necítí moc dobře. n n minus na 2.
>> Ale tady je to věc.
Ve vědě o počítačích, když se problémy začít být zajímavé, je-li n
dostane opravdu velký.
A když n se opravdu velké, což z Tyto hodnoty se chystá ovládnout všechny
z ostatních?
Je to tak trochu na n na druhou, ne?
Ano, dělení 2 je docela dobrý.
Ale pokud mluvíme o miliardách z kusů dat, nebo bilionech
části dat, OK, tak jste dvakrát tak rychle.
Ale kdo opravdu zajímá, jestli ten velký počet, Je-li tento faktor je, co se bude
větší a větší.
A jistě, to dělá více rozdíl, než toho chlapa.
Takže i když jste pravdu, Druhý algoritmus, budeme nazývat
výběr druhu, je v reálném světě, trochu rychlejší potenciálně, protože jsem
s méně a méně kroky pokaždé.
>> Ve skutečnosti to není zásadně rychleji.
Protože pokud budeme skutečně hrát to ven velké hodnoty n, na konci
den, po dobu dost velký n, je to stále bude cítit docela pomalý.
No, dovolte mi, abych jednu poslední průchod na to.
To je to, co bych nazval Výběr sort.
Může vás obnovit sami jednou naposledy?
A v tomto posledním případě, jdu navrhnout něco
volal vložení řazení.
Vložení druh bytí, koncepčně, trochu jinak.
>> Spíše než jít tam a zpět výběrem nejmenší prvek, jsem
jen tak vypořádat s každou z nich kluci, jak jsem se s nimi setkat, a vložte
je do jejich správné místo.
Tak jsem jen tak začít s Grace, a vidím, že je to číslo čtyři.
Kde se číslo čtyři patří?
Jsem se začala třídit nic, Milost tak dostane zůstat tady.
A teď budu tvrdit, kdybys mohl krok na pravé straně, to
můj řazeny seznam, to je moje netříděného zbývající seznam.
Takže teď budu pokračovat dál, a co se to jmenujete?
>> BRANSON: Branson.
>> David J. Malan: Branson.
Takže Branson je číslo dvě.
Takže budu tě vzít se na chvíli zamyslel.
A teď, kam patří v tomto poli?
Takže na pravé milosti.
Takže znovu, jsme druh výroby Milost udělat hodně práce tady.
Kde jsme tě?
Takže budeme klouzat vás vlevo, a vložte tam Branson.
Ale teď tvrdí, že jste hotovi.
Ale oznámení, nebudu používat extra prostor.
Je to stále dva elementy zde 5. sem.
Celková velikost pole je 7, takže jsem nepodvádí, v pořádku?
>> Takže teď máme s Gabe zde číslo šest, kam patří?
Máš štěstí znovu.
Takže jste si zůstat tady.
Jen se mírný krok na pravé straně jen aby bylo jasné, že jste řazeny.
A teď máme Neil opět číslo jedno, kam půjdeš?
A teď je tam, kde začneme vidět, že Tento algoritmus, i když na první
pohled, se cítí docela chytrá, sledovat co se stane.
Pokud byste mohli krok vpřed.
>> Kde chceme dát Neila?
Je tedy jasné, tady, tak jak se dostaneme Neila tam?
Pojďme udělat tento krok-za-krokem.
Gabe, kde budete muset jít?
Jo, tak se jeden velký krok, nebo dvě poloviny-kroky, aby
jeden krok tam.
Milost, kam jít?
Dobře.
Takže další krok.
A konečně, Branson?
Dalším krokem.
A nyní můžeme dát Neila na místo.
>> Takže teď, i nadále tuto logiku.
I když nejsme přesouvá Neil nad, a přes, a přes, aby ho
kde jde, v nejhorším případě, další číslo můžeme setkat mohli
je číslo, řekněme, že se řada nula, pak se budeme přesouvat všechny
tihle kluci.
Předpokládejme, že existuje celá řada, negativní jeden, pak musíme posunout
všechny tyto lidi.
Takže jsme opravdu jen tak proletí problém asi tak, že jsme
převedení náklady z Výběrové řízení tak vložení
proces tak, že jste prostě musel pohybovat zhruba n mínus něco
počet kroků.
A to počet kroků je teprve ve chvíli, zvýšit, když jsem vybrat více čísel,
když budu muset držet strkat kluci zpět, a zpět, a zpět.
>> Tak smutné, teď je všechno z nich algoritmy jsou n na druhou.
Pojďme dál a díky těmto kluci, a vizualizovat tyto trochu
jinak.
Velmi dobře.
>> [APPLAUSE]
>> Dobrá.
Tady to je.
Díky za -
>> BRANSON: [neslyšitelné] držet čísla.
>> David J. Malan: Ne, můžete držet čísla stejně.
Dobrá.
Dobrá práce.
Dobrá.
Tak uvidíme, jestli nemůžeme nyní shrnout rychleji a více vizuálně,
přesně to, co se právě stalo zde takto.
Chystám se jít dopředu a vytáhněte Firefox.
Budeme odkaz na tuto demonstraci na hřišti internetových stránkách.
Java je trochu nepříjemné, aby se pracovní v některých prohlížečích v těchto dnech.
Takže pokud nechcete hrát s tím doma, Uvědomuji si, může být nutné používat Firefox
aby si to práci.
A co budu dělat s tím ukázka je následující.
>> Na dně, mám spoustu možnosti nabídky, včetně začátku a
tlačítko stop.
Také, jako stranou, se zdá, že chyba v těchto programech, přičemž si
nemůže skutečně vidět start nebo zastavení tlačítko, pokud budete držet příkazu nebo Alt
plus a zoom, který zvědavě zobrazuje více tlačítek.
Takže jen FYI, pokud budete hrát s tím doma.
Teď jdu na tlačítko Start v právě Okamžik, po zadání zpoždění,
jako, 200 milisekund, prostě takže můžeme vidět, co se stane.
>> Takže tvrdím, že je to vizualizace prvního algoritmu
tito lidé udělali, bublinková třídění, přičemž jsme vyměnili lidi párová.
Klíčovou myšlenkou tohoto vizualizace je, že výška sloupců
představuje velikost čísla.
Takže vyšší je sloupec, Čím vyšší je číslo.
Kratší bar, menší číslo.
A pokud si všimnete, jedeme přes První iterace tohoto algoritmu,
vyměňovat velké i malé množství, takže malý počet je na prvním místě a
Velké množství jde na pravé straně.
>> A jakmile se dostaneme na konec pole mnoho více než sedm čísel, jsme
jít zpět na začátek.
A to předvídat.
Na zcela vlevo, ten malý kluk se děje swap na stranu, a to
proces se opakuje.
Nyní je tato vizualizace rychle dostane nuda, tak nechte mě jít dopředu a zastavte se
, změnit zpoždění něco mnohem rychleji jen proto, aby teď, cit pro
Tento algoritmus.
>> Takže i když jsem spěchal nahoru, je to jako upgrade můj procesor, nákup
nový počítač.
Jsem zásadně nezměnil můj algoritmus, ale můžete opravdu vidět víc
jasně než s lidmi, že velký Čísla vyvěrá na vrchol,
a malá čísla vyvěrá až na dno.
A teď tohle, co zde řazeny.
A stranou, na náměstích, je tu jen některé účetnictví tam
pomůže spočítat, kolik srovnání, nebo kolik swapy mají
skutečně provedeno.
>> Dobře, pojďme vyzkoušet jednu z ostatní jsme viděli.
Dovolte mi, abych klikněte na bubliny druhu zde, a zvolím, a celá tato webová stránka
je trochu buggy.
Pojďme přijmout riziko a spusťte jej znovu.
Tam jdeme.
Tak jdem na výběr druhu.
Nevím, proč menu objeví se tam.
Pojďme přiblížení napravit chyba, změnit na 50 let.
Ach, pojďme skutečně o to rychleji.
Pět milisekund nebo tak, a začít.
>> Tak to je výběr druh.
Takže znovu, myslím, že o tom, co dělal s lidmi tady.
Šli jsme přes pole a vybrané nejmenší prvek znovu,
a znovu a znovu.
Teď tvrdí, že je stále dost špatný.
To bylo ještě n čtvercový, dávat nebo brát, ale to bylo v reálném světě, trochu
rychlejší, protože jsem byl opravdu s o něco méně kroků pokaždé.
Ale mluvíme jen co?
Možná 40 nebo tak, bary tady?
Nemluvíme 40 milionů.
Takže to není úplně jasné, že byl opravdu značný zisk.
>> Dovolte mi, abych se vrátit a změnit k našemu Třetí algoritmus, který byl zvolte
vložení sort.
A teď je to opravdu buggy, protože Nabídka opravdu by neměl být tam dole.
Takže teď budeme listovat sem a začít tento algoritmus.
Pokřik, spuštění a zastavení.
Takže to jeden druhů má pěkný vzor na to, kdy jsme znovu
vložení lidi, nebo v V tomto případě, bary do
jejich vhodné umístění.
A to již udělal před Otočil jsem se.
Ale tenhle taky, teoreticky, je stále n na druhou.
>> Tak uvidíme, jestli nemůžeme shrnout Tyto takto.
Chystám se jít dopředu a jen proto, aby nám trochu běžným způsobem mluví
o těchto věcech, dovolte mi představit jen trochu notace zde.
Chystáte se vidět něco, co nazývá velký O, protože je to doslova velký
O. A to je tak, že počítač vědec nebo matematik dokonce používá
popsat provozní dobu nějakého algoritmu.
Kolik kroků to vlastně trvá?
>> Teď jdu do rozpaků jsem se můj rukopis tu za chvíli.
Ale dovolte mi jít dál a říct, že to bude velký O sem.
A dovolte, abych vám představil jeden další symbol, kapitál omega.
Omega bude naopak, v podstatě z velké O. vzhledem k tomu velké O
znamená, v nejhorším případě, kolik času může nějaký algoritmus přijmout,
Podmínky n omega bude se, kolik času mohlo by to
se v nejlepším případě.
A uvidíme, co máme na mysli nejlepším případě za chvíli.
>> Tak začněme něco jednoduchého.
Dovolte mi začít s lineárním vyhledávání.
Takže není třídění.
Nazveme to lineární hledání.
A nyní, aby se trochu tabulka z toho.
A nyní, v případě lineárního vyhledávání v nejhorším případě sledovat, kolik kroků je
bude trvat mě, počet libovolné volby?
A je tu celkem n dveře nebo n celkový počet.
Nejhorší případ.
Kolik kroků budu muset se najít číslo 50 v poli
dveří n?
A proč?
Vzhledem k tomu, že to může být všechno cesta přes na konec.
Takže stejně jako Jennifer se setkal, Číslo 50 bylo celou cestu, tak v
v nejhorším případě lineární hledání je velký O n, budeme říkat.
>> A co nejlepším případě, pokud máte opravdu štěstí?
Je to jen tak, aby se jeden krok, nebo stálý počet kroků.
Takže budeme popisovat to jako jeden.
Tak to je docela dobrý.
Teď, co kdybychom udělali něco jako binární vyhledávání?
Takže binární vyhledávání, v nejhorším případ, vzal kolik času?
>> [Přechodová Hlasy]
>> David J. Malan: Takže vlastně jsem slyšel za pár místech.
Takže je to vlastně log n, dávat nebo brát, protože jak rozdělit seznam na dvě poloviny
znovu a znovu, a znovu, jsme schopni najít, nakonec, je tato hodnota,
jestli je to tam, ale je zde jeden háček.
Jaký je předpoklad, že musíme brát za samozřejmost, pro binární vyhledávání?
Musí být tříděny.
Je to netřídí, můžete rozdělit věc na polovinu znovu a znovu, a vy
může jít vlevo, a můžete jít vpravo, a můžete jít doleva a doprava, ale vy jste
nenajde prvek, pokud seznam není seřazen, protože
můžete si ho ujít.
Protože vaše heuristiky pro přechod vlevo nebo doprava se bude vadný, pokud je to
opravdu nejsou seřazeny.
Takže je tu jakýsi skryté náklady s použitím něco takového.
>> Teď pojďme do našeho třídění algoritmy nehledal -
oh, vlastně jdeme v tomto prázdné.
Binární hledání v nejlepším případě?
Je to také jedno, pokud to jen se stane být v samém středu pole, nebo
uprostřed telefonního seznamu.
Nyní se pojďme dělat bubliny druhu.
Takže znovu, teď se vstupem do druhy, nikoli hledání.
>> V nejhorším případě, kolik kroků to jsme tvrzení bublina trochu to bude trvat?
n na druhou.
Takže budu kreslit to.
Ooh, můj rukopis vypadá ještě hůř když se to předpokládá, že velký.
Dobrá.
Tak to je n na druhou.
A v nejlepším případě bublinkové druhu, kolik kroků to bude trvat?
1, slyšel jsem.
>> Reproduktor 1: n.
>> David J. Malan: n, slyšel jsem.
>> SPEAKER 1: 2.
>> David J. Malan: 2, slyšel jsem.
Slyším 3?
Dobrá.
Slyšel jsem 1, n 2, ale pojďme vybrat od sebe alespoň první z nich
návrhy, 1.
Není to špatný instinkt, protože to druh kopíruje vzor zde.
Ale pokud to trvá jen jeden krok, jak v svět mohl bych tvrdit, že seznam
je tříděn, protože když jsem povoleno pouze aby se jeden krok, kolik prvků
mohl bych vlastně zkontrolujte, zda?
No, jen 1, což znamená, že je n minus 1 prvků, které by mohly být z
pořádku, a já jsem prostě jít na víře po při pohledu na jeden prvek, který
věc je seřazen.
Takže 1. Není opravit tady.
Takže minimálně, kolik musím se podívat na?
>> [Přechodová Hlasy]
>> David J. Malan: n mínus jedna, nebo opravdu, n, protože jsem se třeba podívat se na každý
prvek, aby se ujistil, že to není mimo provoz.
Ale opět budeme třídit vlny našeho ruce na menších číslech a
Předpokládejme, že, jak n se zvětší, jsou nezajímavé stejně.
Tak to je bublina třídění.
A teď, pojďme se tyto dva poslední.
Výběr druhu, a pak budeme dělat vložení řazení.
A pak se stočí svou mysl se něco mnohem
lepší než všechny z nich.
Dobrá.
>> Co je nejhorší běh Doba výběr druhu?
>> SPEAKER 4: n na druhou.
>> David J. Malan: n náměstí, slyším.
Ale proč n na druhou, intuitivně?
>> SPEAKER 4: Protože jsme právě udělali.
>> David J. Malan: Protože jsme právě udělali.
OK.
Dobrá odpověď.
Ale intuitivně, proč je výběr řadit n na druhou?
Co musíme udělat, znovu a znovu?
Museli jsme se držet skenováním, jsou můžete nejmenší, jste
Nejmenší jsou ty nejmenší.
A samozřejmost, jsme byli schopni přijmout n kroky, pak n mínus 1, pak n mínus 2.
Ale pokud si trochu přidat ty všechno, nebo ji na víře, že jsem přidal
je s předstihem, dostaneme zhruba n na druhou mínus některých menších čísel.
Takže budu volat to n na druhou.
Ale s výběrem druhu v nejlepším případ sledovat, kolik kroků je
mě vezme?
>> SPEAKER 5: [neslyšitelné]
>> David J. Malan: Je to bohužel Stále n na druhou, ne?
Protože když jsem výběrem nejmenší prvek, a měli jsme sedm lidí tady,
Já jen vím, jakmile se dostanu k velmi konec, že ​​jsem našel nejmenší
číslo, kde on nebo ona může být.
Ale jak najdu další nejmenší číslo?
Musím udělat další přihrávku.
Takže v nejlepším případě, jaký je Vstup do výběru druhu?
Je to už trochu seznamu číslo jedna, číslo dvě, číslo tři, číslo čtyři.
Ale já jsem počítač.
Mohu jen podívat na jeden věc najednou.
Nemůžu nějak krok zpět jako člověk a řekl:
ooh, to vypadá správné.
>> Mohu jen rozhodnout korektnost Třídit podle výběru
nejmenší číslo.
Ale i když jsem si první číslo jedna, jestli nevím něco o
jiná čísla, které nemám, všechno, co jsem vím, že jsem podal řadu
nebo sada za sebou dveře, které jsou čísla, jediný způsob, jak vím, že jedna
Jednalo se o nejmenší?
Pokud se dostanu až sem a uvědomit si, sakra, jeden byl opravdu nejmenší.
>> Ale jak jsem se potom rozhodne, že dva je další nejmenší?
Tím, že dělá stejnou neefektivnost znovu a znovu.
Tak konečně se vložení druhu, how, v nejhorším případě,
jsme se, že to provádí?
To také je n na druhou.
A co s tím nejlepším případě?
Necháme to jako cliffhanger.
Budeme vyplnit té prázdné příště, ale nejprve mi dovolte navrhnout, abychom
podstatně lépe než všechny z nich, v pořádku?
>> Takže myslíte, že to, co pro sebe vložení druh to bude.
No, to není příliš dramatický, protože jsem jediný
která viděla změnu.
Wow.
OK.
Takže tady máme něco různé demonstrace.
Kdybych přiblížit tady, uvidíte, že na vlevo máme bubliny druh, v
Střední máme výběr druhu a na krajní pravice, máme něco, co jsme
jsem se podíval na dosud tzv. sloučení druhu.
Ale zvažte, co jsme byli tady děláš tak daleko ještě dnes.
Když Jennifer poprvé přišel na pódium, jsme šli přes pole čísel
znovu a znovu, s lineární vyhledávání a my jsme dostali lineární dobu chodu, velké O
n, abych tak řekl.
>> Když jsme se nyní považují za sebou první týden třídy, když jsme se rozděl a panuj,
a my jsme v telefonním seznamu slzení, a Jennifer, a my společně
Klíčovou myšlenkou, že hybnou silou, která měla opakovat se znovu a znovu
nějak zahodili, vyhazování, zahodili, polovina problému, nebo
obecně, tak, že se problém na polovinu, a léčbě menší kus
problém, koncepčně ekvivalentní na druhé straně, se nějak
zásadně lepší.
Ale s bublinou druhu, s výběr druhu, s vkládací druhu, máme se mohou
žádné takové poznatky, že Jennifer udělal.
Jsme skoro stejně vrátil a tam celá parta z časů, a my
Upraven věci trochu, vyměňovat v tomto pořadí, možná
vkládání nebo výběru.
Ale na konci dne, jsem hodně trapné chůze tam a zpět.
Neměli jsme využít co chytrý jako Jennifer jsem rád dělení
a dobývání.
>> Takže sloučit druh, naopak, které neuvidí až do příštího týdne, bude to
se pákového efektu, který Klíčovou myšlenkou vydělením vstup, a pak na polovinu, a pak
polovinu a pak polovinu.
A při každém opakování tohoto cyklu, třídění levou polovinu, a právo
polovinu, pak Levá polovina levé poloviny, a pravá polovina doleva, pak
Levá polovina v pravé polovině, a pravá polovina v pravé polovině.
A opakovat znovu a znovu.
>> Takže budete vidět vizuálně, ale je to, co nás čeká příští týden.
A vůbec, když si myslíme, že něco trochu těžší na takový případný problém.
Máme n druhou vlevo, n druhou v polovině, a n
log n na pravé straně.
Takže tam je váš skutečný cliffhanger.
Uvidíme se v pondělí.
>> [APPLAUSE]