SPEAKER: Dobře, to je CS50. To je konec tří týdnů, a pokud jste využili již vědět, že tam bude oběd tento pátek jako obvykle, kde můžete nyní dobrý rozhovor a jídlo na ohně a ledu s některými CS50 je Zaměstnanci a spolužáci. Vydejte se na této adrese zde. 

Nyní si můžete připomenout, nebo může brzy být seznámen s, tyto věci, která sem jsou uvedeny na konci semestru pro mnoho tříd. Takzvaná zkouška modré knihy, ve které můžete psát své odpovědi na zkoušky. Teď mám tu 26 jako modré knihy, na každý z nich je napsáno jméno, až Z. A opravdu jména jsou tak jednoduché, díky Z. A jeden z cíle na dosah ruky dnes bude pokračovat v co jsme začali v pondělí, což není tak při pohledu na kód, ale ve skutečnosti při pohledu na nápady a řešení problémů. Jedním z cílů a sliby tohoto kurzu je, aby vás naučí myslet více opatrně, více metodicky, a efektivněji řešit problémy. A skutečně, můžeme to udělat opravdu aniž byste se dotkli jediného řádku kódu. Takže mám pár slonů tady dnes, oranžové a modré, pokud bychom se mohli dostat jednoho dobrovolníka, možná z větší zpátky, než je obvyklé. Jak se asi tady, pojď dolů. Jehož cílem bude, aby pomoci a navíc spravovat tuto zkoušku tady. Jak se jmenujete? 

Diváků: Mary Beth. SPEAKER: Mary Beth, pojď nahoru. Dovolte mi, abych se mikrofon tu pro vás. Těší mě. 

Diváků: Těší mě. SPEAKER: Dobře, takže mám zde modré knihy A až Z, a budu předstírat, že Mám jeden ze studentů, a oni přicházejí poněkud náhodně na konci tři hodiny zkouška bloku, tak oni skončí v některé semi-náhodné pořadí takhle. Nyní svou práci za chvíli bude na bylo-- to je vlastně, jak se dostat obrátil na konci roku třídy, s největší pravděpodobností. Vaším úkolem nyní bude zcela Jednoduše řečeno, třídit tyto modré knihy pro nás od A po Z. 

DIVÁKŮ: Oh, to je bude trvat věčně. 

SPEAKER: A budeme sledovat jak to uděláte, žádný tlak. DIVÁKŮ: Ne, žádný tlak nebo tak něco. 

SPEAKER: A pro zábavu, pojďme dát časovač. 

Diváků: Tolik legrace, tolik legrace. 

SPEAKER: Můžu držet mikrofon pro vás. Dobře, právě jsme zdvojnásobili naši rychlost. Takže do té doby, dovolte mi, abych představovat, co je bude otázka pro Mary Beth je to, co dělá, jak je že jde o řešení tohoto? A ve skutečnosti, možná nebudete mít někdy přemýšleli o něčem tak jednoduché, jako když si vyberete až 26 knih, jako je tento, které mají přírodní objednání k nim. Jaký je proces že jste skutečně používat? Je to docela náhodně jen vybírání první uvidíte a uvedení na svém místě? Myslíte si nejprve přesunout své ruce kolem Hledáme pak hledal B? Myslíte si, podívejte se na pár z nich vedle sebe a jen řekl, počkej, to není v pořádku, a pak vyměnit pořadí? Již jsme viděli v pondělí že existuje řada způsobů, jak ve kterém můžeme udělat, a opravdu, jak jsme u konce tady, Chtěl bych vzít na vědomí možná z čeho Mary Beth dělá. Máme několik hromádek zdá se, Větší z nich, tři menší. 

Diváků: Já je objednání když jsem si dva dopisy že vím, že jsou spolu v pořadí, Dal jsem je dohromady tak, že se mi nelíbí muset starat o udržení track z celé řady knih. Je to jen, ach, je první, Mám tento stoh zde. SPEAKER: Takže, skoro jako puzzle kousky, které mít správný tvar na shodovat s navzájem. DIVÁKŮ: Docela hodně, jo. SPEAKER: OK, výborná. A teď každá z nich hromady je pravděpodobně řazeny? 

Hlediště: Ano. 

SPEAKER: Dobře, díky Z. Vše Dobře, gratuluji, jste to udělal. Máte možnost volby. Modrá? Dobře, děkuji vám za to. Takže Mary Beth se navrhnout co její přístup byl, ale to, co je jiný přístup, jak na Vás může jít o třídění těchto věcí? Co by jste udělali? Záznam porazit by bylo jednu minutu a 50 sekund, nebo tak, plus ty, které jsem zapomněl počítat. Co by jste udělali? Jo? Diváků: Vezměte stoh papírů. Od začátku. Zkontrolujte, zda vaše dokumenty. A v případě, že horní z nich je vyšší než, možná, že jsou spodní z nich je vyšší, pak nimi přepínat. 

SPEAKER: OK, tak začíná V horní a spodní části, a pracovní cestu dovnitř jako to, že je vymění? OK, tak málo podobný duchem bublinkové druhu, ale volba extrémy nejsou přilehlé páry. Ale krátké na to, že je tu jistě spoustu různých způsobů, bychom to mohli udělat, a Upřímně řečeno, myslím, že tak nějak přijal pár přístupy, ne? Udělal jsi něco jako čtyři tříděných piloty a pak efektivně spojil dohromady. A to je, troufám říct, další technika dohromady. Vy jste to brát to jako jedna velká hromada, můžete rozdělit problém do čtyř čtyřkolky, chcete-li, a pak se nějakým způsobem spojil je do konce. 

Takže pojďme zvážit, nakonec, Jak jinak bychom mohli udělat. Formalizované jsme pojem bublinkové třídění minule, a bubble sort odvolání bylo Algoritmus, který jsme vizualizovány s osmi svými spolužáky se zde, zdánlivě náhodně řazeny na prvním místě. A pak jsme se rozhodli po dvou, pokud dva prvky jsou mimo provoz, prostě je vyměnit. Takže čtyři a dvě zřejmě mimo provoz, Takže ti dva spolužáci přepnout pozice. A pak jsme se opakuje se čtyřmi a šesti, pak šest a osm, na každé iteraci, pohybující se doprava. 

Takže vzhledem k tomu osm lidí, kolik pairwise srovnání jsem udělal při chůzi od zleva doprava v jednom takovém iteraci? Kolik srovnání? Sedm, že jo? Vzhledem k tomu, jestli je osm lidé, ale máte pár ně a dál jeden hop na pravé straně, nebudeš mít osm srovnání, protože nemůžete porovnat prvek proti sobě, nebo by jen zbytečné, takže budete mít sedm. Nebo obecněji, pokud máme n lidi, jsme do n minus 1 srovnání bublinkové druhu. 

Takže uvažujme nyní, jak dobrý nebo špatný bubble sort vlastně byl, a zkuste aby sami slovní zásobu které k posudku algoritmů, jako je tento, a brzy se naše vlastní. Takže prvním průchodu bublina druh, poprvé Šel jsem zleva doprava přes etapa, vzal mě n mínus 1 srovnání. A to bude můj měrná jednotka, ne? Byl jsem trochu mluvit a procházky, poněkud rychle, poněkud pomalý, takže počítání moje číslo v sekundách není zvláště říká, ale spočítáním operace, které jsem dělal v pondělí, porovnání dvou lidí, že se cítí jako pěkný měrnou jednotku. 

Tak n minus 1 krok poprvé, ale potom, co se stalo potom? Co je to jeden vzhůru na jeden průchod přes jinak netříděného seznamu? Co mi můžete říct o prvek který byl po celou cestu tam? Jo? To byl největší prvek, ne? Číslo osm, i když zde začala, pokaždé, když jsem ve srovnání s ní proti soused, pořád vyvěrá na pravé straně straně seznamu. A vskutku, to je místo, kde algoritmus dostane jeho jméno. 

Právě tímto logiky, kolik srovnání Potřebuji, aby na podruhé Dělám, že přihrávku zleva doprava? n minus 2, ne? Bylo by to plýtvání mým časem, kdybych udržet porovnání osm proti někomu, jiného, ​​protože už víme, byla na správném místě. Takže je to trochu optimalizace, takže další průchod bude navíc n minus dva kroky, kde n je počet osob. Nyní můžete trochu extrapolovat, a to i pokud nejste počítačový odborník, jak to skončí. Na konci tohoto algoritmu, pravděpodobně máte jen jeden srovnání odešel. Musíte se trochu opravit začátku seznamu v případě, že dva a jedna jsou mimo pořadí a měla by být jedna a dvě, tak to doraz na plus 1 v konečném znění porovnání. 

Nyní je tečka, tečka, tečka druh vln je ruce na některé šťavnatější podrobnosti ale pojďme prostě jít dopředu a zjednodušit. Pokud si vzpomínáte z vysoce Škola, upřímně řečeno, mnoho z vás měli matematické knihy, které měly malý tahák na přední straně obálky nebo zadní kryt, který vám ukázal, co série součtů jako to nakonec přidal až. V obecném případě, máte-li variabilní, jako n, a ve skutečnosti to jeden, pokud jste se podívali na vaše old school math knihy, byste vidět, že to ve skutečnosti přidává do této částky zde n krát n minus 1 vše děleno 2. Takže teď mi dovolte stanoví je to pravda, tak na skok víry, to je to, co to vystihuje až, a my jsme mohli dokázat, že v obecnějším případě. Ale teď pojďme rozšířit to. Takže pojďme se množí na to, aby je n na druhou, mínus n, vše děleno 2. To je opravdu n na druhou, děleno 2, minus n na 2, tak to je všechno pěkné a zajímavé. Ale co se stane, když Nyní plug-in v hodnotě? Dejme tomu, že jsem neměl osm lidé, ale říkají milionu. A miliony jen proto, že to je docela velké číslo, pojďme zástrčka, že v roce, a uvidíme, co se stane. Takže když jsem plug milionů do tohoto vzorce Jdu si milion na druhou, děleno 2, minus milionů, děleno 2. A teď, co to jde, aby se rovnala? Takže 500 miliard, minus 500.000. A když jsem vlastně dělat že matematika, znamená to, že třídění milion lidé s bubliny druhu mi může trvat 499999500000 kroky nebo srovnání na konci, jsme jen extrapolace. 

Že se cítí docela pomalu, ale upřímně řečeno, měření jedné konkrétní vstup jako je toto, není všechno, že to řekl. Ale ve skutečnosti to naznačuje, že pro n dostane větší a větší, tento algoritmus druh cítí hůř a horší, nebo opravdu začnete cítit bolest, která umocňování, že n na druhou, který sčítá docela rychle. A to detail není ztratil na lidi, ve skutečnosti před několika lety jistý senátor, který byl kampaně, sedl si na pohovor s Google Eric Schmidt, CEO v té době, a byl napadán s otázkou stejně jako jsme zkoumání dnes. Pojďme se podívat. 

[PŘEHRÁVÁNÍ] 

-Senator, Že jsi tady na Google, a líbí se mi myslet na předsednictví jako pracovní pohovor. Nyní je těžké se dostat zaměstnání jako prezident, a jdete přes nástrahami teď. Je to také těžké získat práci ve společnosti Google. Máme otázky, a my zeptejte Naši kandidáti otázky, a tohle je od Larry Schwimmer. Co-- vy myslíte, že jsem Děláš si srandu, že je to tady. Jaký je nejúčinnější způsob, jak seřadit milion 32bitová celá čísla? 

-Well-- 

-Promiňte, Maybe-- 

Ne, ne, ne. Myslím si, že bublina druh by byl špatný způsob, jak jít. 

No tak, kdo mu to řekl? Neviděl jsem počítač věda v pozadí. 

-Musíme Naše zvědy tam. 

-OK, Pojďme se zeptat jiný rozhovor otázka. 

[END VIDEOPŘEHRÁVÁNÍ] 

SPEAKER: Tak mluví o Konkrétní čísla však se nebude všechno užitečné. Nejedná se o životní lekci, že bublina třídění, vzhledem k tomu milion vstupů, může trvat tolik jako 500 miliard kroky. Nemůžete opravdu zobecnit příliš účinně od a činit správná rozhodnutí návrhu při psaní programů. Takže pojďme se zaměřit na to, jak by můžeme zjednodušit tento výsledek. 

Tak jsem se zvýrazní žlutě zde výsledkem n na druhou děleno 2, tak milion na druhou děleno 2, a poté Jsem zvýrazní to, co konečná odpověď byla jakmile jsme se odečte z n děleno 2. A tvrzení, budu nyní dělat, je kdo sakra zajímá, jestli si odečíst z trochu starý n na 2, kdy první Součástí tohoto vzorce je tak mnohem větší? Je dominantou druhé Termín, n na druhou děleno 2 je tak mnohem větší, jasně, jak n dostane velký jako milión, to je opravdu velký rozdíl v konec dne mezi 500000000000 a 499999500000? Ne tak docela. A tak to, co budeme dělat, co počítačoví odborníci se ignorovat ty nižšího řádu podmínky a se něco takového a opravdu jen zjednodušit na termín, který to bude jedno. Větší naše soubory dat, tím větší Naše databáze získat, tím více webových stránek musíme hledat, více přátelé máte na Facebooku. 

Jako n zvětšuje, jsme opravdu bude se starat o největší Výraz v každé takové analýze naše algoritmy výkon. A já jsem chtěl říct, že víš, co, bubble sort je na objednávku velký O, na pořadí n na druhou. Není to zrovna n na druhou, jak jsme viděli, ale kdo opravdu zajímá o těch menších podmínkách, a upřímně řečeno, kdo opravdu zajímá, jestli budeme dělit dvě? To je jen konstantní faktor. A 500 miliard ve srovnání s 250 miliard opravdu tak velký problém? Jsem mohl jen čekat jeden rok, nechat notebook doslova se dvakrát tak rychle v hardwaru, a že tak nějak rozdíl prostě zmizí přirozeně v průběhu času. 

To, co zajímá je výraz, část výrazu, že se to liší jako náš vstup dostane větší a větší. A skutečně, v reálném světě, to je to, co se děje dál Je vstupy do našich problémů a algoritmy jsou stále větší. Tak velký O bude zápis, asymptotické notace, který jsme právě použít jako počítačoví odborníci popsat výkon, nebo čas běží, algoritmu. Takže můžeme porovnávat algoritmy na různých počítačích písemných různými lidmi, s použitím některé zásadně podobné metriky jako je počet porovnání jste dělat, nebo možná počet swapů děláte. 

Co my nebudeme počet je množství času, , který prochází na hodiny na stěně typicky. Co my nebudeme se bát o tom, je, kolik paměti používáte dnes na nejméně, i když je to jiný zdroj můžeme měřit. Budeme se snažit založit své analýzy na jen základní operace, ty, upřímně, že můžete vidět nejvíce vizuálně. Takže něco jako velký O n čtvercový, tvrdím, že O n na druhou je horní mez na takzvaný doba chodu bublin druhu. Jinými slovy, pokud máte chtěl tvrdit, že je tu Tento horní limit na tom, kolik kroky algoritmus může trvat, že to bude ve velkém O n v tomto případě čtvercový, horní mez. 

Co kdybych místo toho změnit příběh se nejedná o bubble sort, ale o to horní mez. Vzpomenete si na algoritmu že jsme se podíval na již jehož horní hranice, maximální měření času nebo provozu, by se říci, že je ohraničena o n, lineární funkce, není kvadratická ten, který je zakřivený? Co je to algoritmus, který vždy netrvá déle než jako n kroků, nebo 2n kroků, nebo 3n kroky? Jo? 

Diváků: Hledání největší číslo v seznamu? 

SPEAKER: Perfektní, hledání největší číslo v seznamu. Pokud jsem dal seznam lidé například, Každý, kdo je drží číslo, jaký je maximální počet kroků, to by mě vzít, přiměřeně inteligentní člověk, najít největší osoby v tomto seznamu? n, že jo? Vzhledem k tomu, v nejhorším případě, kdy je možné, že největší hodnota být? Jasně, úplně na konci. Takže v nejhorším případě horní mez, možná jsem muset jít celou cestu tady a být rád, oh, tady je číslo osm, nebo co, že hodnota je. Teď to bude jen hloupý když jsem šel dál, že jo? Hledáte více a více prvků v případě, že poslední z nich je tam? Tak jistě, n je horní mez. Nepotřebuju, aby se více kroků, než je. 

Co když místo toho navrhuje, aby jsou algoritmy v tomto světě, mají provozní dobu, která je ohraničené velkým O log n log n? Tam, kde jsme viděli dřív? Jo? 

Diváků: V telefonním seznamu problém? SPEAKER: Jako telefonního seznamu problém. Co bylo měřítkem toho, jak hodně času a kolik ji strhne trvalo mi najít někoho, jako je Mike Smith v telefonním seznamu? Prohlašoval jsme, že log n, a i když neznají, nebo je to trochu zamlžený, co logaritmus nebo exponent byl, Jen nezapomeňte, že log n obecně se odkazuje na proces, v tomto případě dělení něco v polovině znovu a znovu, a znovu, a znovu, tak, že dostane stále malý, jak to udělat. 

Takže log n odkazuje, jistě, do telefonního seznamu například binární vyhledávání v teorii, když jsme měl virtuální dveře na palubě, nebo když byl Sean něco hledal. Kdyby byl použit binární vyhledávání, binární log n bude horní mez na tom, kolik čas, který trvá. Ale ty algoritmy, které běžely v log n předpokládá, jaká klíčová detail? Že seznam byl tříděn, že jo? Algoritmus je-li špatně Váš vstup netřídí, a přesto, že používáte něco jako binární vyhledávání protože byste mohli skočit přímo přes prvku aniž by si uvědomil, že je to opravdu tam. 

A teď, co by to mohlo znamenat, velký O jednoho? To neznamená, že algoritmu trvá jeden a pouze jeden krok, to prostě znamená, že to trvá konstantní počet kroků. Možná je to jeden, možná je to 10, možná je to 1000, ale je to nezávislý Velikost problému. Bez ohledu na to, jak velký je n, časová konstanta algoritmus má vždy stejný počet kroků. Takže to, co by mohlo být algoritmus jsme mluvili o, nebo jen intuitivně, že k vám přijde, že vždy běží v takzvané konstantním čase? Jo? 

Diváků: Přidejte dvě čísla. SPEAKER: Přidejte dvě čísla, 2 plus 2 se rovná 4, hotovo. Tak to by mohlo fungovat, co jiného? Jak se o více skutečném světě, ne? 

Diváků: Hledání První věc, kterou v seznamu. SPEAKER: Nalezení první prvek v seznamu, jistě. Jsme vlastně mluvili o polích již jak se dostat na první prvek v matici, bez ohledu na to, jak dlouho pole je v C kódu? Stačí použít jako držák bum, jste tam nula notace, ty. A samozřejmě pole, jako stranou, Podpora něco všeobecně známo, jako náhodný přístup, s přímým přístupem paměť, protože můžete doslova přeskočit na jednom místě. Můžeme to udělat ještě jednodušeji můžeme přetočit na týden nulové když jsme nuly. Kolik času to trvat říci, blok Scratch vykonat? Jen konstantní čas, že jo? Řekni něco, řekni něco, nezáleží na tom, jak velké škrábance svět, je to vždy bude trvat stejnou dobu prostě něco říct. 

Tak to je časová konstanta, ale co druhá strana? Kdyby tomu tak bylo vyšší hranice, co chceme-li popsat dolní meze z našich algoritmů běží čas? Téměř v nejlepším případě potenciálně, chcete-li, když tyto podmínky by se mohly vztahovat k nejlepším pouzdra, nejhorší případy, průměr pouzdra více obecně, ale pojďme se soustředit jen Na spodní hranice obecně. Co je to algoritmus, který má dolní mez n kroků, nebo 2n kroků, nebo 3n kroky? Některé faktor n kroků, to je jeho dolní mez. Jo? 

Diváků: Bubble sort? 

SPEAKER: Bubble sort se budete minimálně n kroků, proč? Proč tomu tak je? Proč by to začátek přijít k vám intuitivně, i když to není jen ještě? Jo? 

Diváků: [neslyšitelné]. SPEAKER: Přesně tak. V nejlepším možném scénáři bublina třídit a mnoho algoritmů, pokud předám vám osm lidí který je již řazeno, že by bylo pošetilé pro vás, algoritmus, jít tam a zpět více než jednou, ne? Vzhledem k tomu, jakmile se projít seznam jednou, měli byste si uvědomit, oh, jsem žádný swapy, tento seznam je tříděn, exit. Ale, co se děje, aby vás n kroků. 

A naopak, co je jiný způsob, jak o tom přemýšlet? Bubble sort je omega, abych tak řekl, n, protože když se podíváte na méně než n prvků, co se je zde zásadní problém? Nevíte, jestli je to třídění, doprava. Jsme lidé, může dojít pohled na osm lidí a být rád, ach, je to třídění, že jsi mi n kroků nebere, ale stalo se. Tvé oči, i když tak nějak ze mají velký zorné pole, jste se podívali na osmi prvků, jste se podívali na osm osob, to je osm kroků efektivně. A jen tehdy, pokud jsem projít celý Seznam mám uvědomit, ano, třídit. Pokud bych se zastaví na mysli všechny Dobře, je to docela řazeny tak daleko, jaké jsou šance, že to není tříděné? To algoritmy nebude správné. Může být rychlejší, ale nesprávné. 

Takže teď máme způsob, jak popisující dolní hranice, a co konstantním čase? Co je to algoritmus, který má nižší vázána na jeho chodu době jednoho? 1 krok, dva kroky, 10 kroků, ale konstantní, nezávisle na n, Velikost vstupu? Jo, v zádech. 

Diváků: printf? SPEAKER: Co je to? Diváků: printf? SPEAKER: printf. OK, jistě. Tak to trvá stanoveném počtu kroků. A já jsem měla teď-- teď mluvíme o C kódu a ne Scratch, něco jako řekněme, s printf, bychom měli začít, aby si opatrný. Vzhledem k tomu, printf se vzít vstup, je to řetězec, a řetězce to technicky mít délku. Takže pokud chceme nyní vybrat na vás, jestli vám to nebude vadit, technicky bychom mohli tvrdit, že printf to se s proměnnou délkou vstup, a jistě by to mohlo trvat déle Doba tisku řetězec tak dlouho, než tak dlouho. 

A co když vezmeme v úvahu jen třídění a vyhledávání příkladů? Co Mike Smith v telefonu kniha, nebo binární vyhledávání obecně? V nejlepším případě, co se může stát? Otevřel jsem telefonní seznam, a bum, tam je číslo Mike Smith. Nemůžu ho zavolat hned. 

Udělal jeden krok, možná dva kroky, ale konstantní počet kroků když jsem měl štěstí. A upřímně řečeno, jsme viděli na Pondělí váš spolužák dostat docela štěstí dvakrát za sebou. A to je skutečně konstantní čas v dolní mez na algoritmu se jedná o hledání číslo 50 za ty zavřené dveře. 

Nyní, stejně jako stranou, když zjistíte, že jak velký O, horní mez, a omega, dolní mez, jsou jeden ve stejné, že je stejný vzorec v závorky, můžete také říci, jen pro chuť, , že něco, co je v theta n nebo theta nějaké jiné hodnoty. To prostě znamená, že když velká O a omega jsou stejné. A co výběr druhu teď? Využijme tuto novou slovní zásobu. Ve výběru druhu, o čem jsme dělat znovu a znovu a znovu? Byl jsem tam a zpět přes seznam, hledá pro koho? Nejmenší číslo. 

Tak kolik kroků, jak mnoho srovnání udělal já muset udělat, aby se zjistit, kdo nejmenší prvek v seznamu je? n minus 1, ne? Protože když jsem začít s jedním Jsem vzhledem k tomu, a začnu ho porovnávání, pak on nebo ona, ho nebo ona, on nebo ona, jsem lze spárovat pouze prvky spolu n minus 1 krát. Takže výběr trochu podobně se n minus 1 krok poprvé. 

Kolik kroků to mě vzít najít druhý nejmenší prvek? n minus 2, protože jsem byl hloupý pokud Pořád se dívá na stejných lidí znovu, jestli jsem ho už vybrali nebo ji a dát je na jejich místo. A třetí krok, n minus 3, pak n minus čtyři. Viděli jsme tento model před, a skutečně Výběr třídění podobně je horní hranice n na druhou, pokud budeme dělat až ten shrnutí. Jaká je jeho dolní mez, výběr trochu? Minimálně, kolik výběr času musí třídění se, jak se nám to definováno v pondělí? Navrhnout dvě možnosti. Možná je to n, jako předtím. Možná, že to je n na druhou, jak to Nyní je jako horní mez. 

Diváků: n na druhou. SPEAKER: n na druhou. Proč? 

Diváků: Protože máte definovat [neslyšitelné]. 

SPEAKER: Přesně tak. Alespoň jak jsem je definováno výběr druhu to bylo dost naivní, pokračuj, najít nejmenší prvek. Jděte zase, a najít nejmenší prvek. Jděte zase, a najít nejmenší prvek. Neexistuje žádný druh optimalizace v tam, že může mi dovolte ukončit po jen n nebo tak kroky. Takže opravdu, výběr třídění, omega n na druhou. 

Co vložení druhu, kde jsem vzal který jsem dostal, a pak jsem ho svalil nebo ji na správné místo? Pak jsem přistoupil k druhé osobě, svalil ho na správném místě. Pak další osoba, svalil ho nebo ji na správném místě. Všimněte si, že je to velmi lineární, abych tak řekl. Jsem přímka, já jsem Není tam a zpět, Nikdy jsem se ohlédl ne, ale co se děje, když jsem se ho vložit nebo ji do začátku seznam jako jsme to udělali v pondělí? Co se děje? Jo? Diváků: [neslyšitelné]. SPEAKER: Jo, to byl úlovek, ne? Možná pamatujete z svými spolužáky, pokud se dělali jakýkoli pohyb s jejich nohy, to je operace. Takže v případě, že byli tři lidé tady a nový člověk patřil támhle, na dlouhou fázi, jako je tato, jistě, že nebo mohla prostě jít až do samého konce. Ale pokud uvažujete o počítače a pole paměti, tito lidé jdou muset zamíchat přes aby se prostor pro tuto osobu. A tak, aby n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings je jen trochu se děje za mnou, ne přede mnou jako dříve, v jistém smyslu. Nyní jako stranou a jako jste mohli vidět on-line pokud začnete vrtat o druhy, je tam tolik různých ty tam, některé z nich lepší než ostatní. Ve skutečnosti, je jedním bogosort to je docela zábavné vzhlédnout. Bogosort má sadu čísla nebo říkají, balíček karet, náhodně zamíchá je a zkontroluje, zda oni jsou řazeny. A pokud ne, udělá to znovu. A pokud ne, udělá to znovu. Pokud ne, dělá to znovu. Neuvěřitelně hloupý. 

A skutečně, když si přečtete jako Wikipedia článku, jeho přezdívka je hloupý druh. To bude nakonec fungovat, doufejme, že vzhledem k tomu dostatek času, ale to množství času, může trvat nějakou dobu. Takže pokud bych mohl, pojďme rychlosti věcí up od Mary Beth je například dříve, tím, že má ještě několik dalších prvků, ale další dva procesory. Dva lidé, pokud máte Nevadilo by mi to spojení. Jak se o jeden sem, a pojďme jít-- nikoho tam? Nikdo tam? OK. Ty s černou košile, ano, pojď dolů. Tak jo, Jak se jmenujete? 

DIVÁKŮ: Peter. 

SPEAKER: Co je to? 

DIVÁKŮ: Peter. SPEAKER: Peter David, rád tě poznávám. Dobře, máme Petra tady, pokud máte chtějí přijít na stůl sem. A Jak se jmenujete? 

DIVÁKŮ: Elena. SPEAKER: Elena. OK, rád tě poznávám. Elena setkat Petera. Petr, Elena. A budeme potřebovat Andrew se i zde, prosím. A vaše výzva se děje aby třídit balíček karet. A pokud neznáte, paluba karet by mělo v konečném důsledku seřadit trochu něco jako Tady uděláme kluby, pak lopatky, pak srdce a diamanty, od esa jako jeden, celou cestu až ke králi. 

Karty budu vám se bude 52 v množství. Chystáme se podobně čas vás za chvíli. Budeme házet Andrew na obrazovce zde tak se dívat, jak to uděláte. A aby to všechno je to více vidět, to jsou karty Dostal jsem na Amazonu. Takže už jsou náhodně řazeny, a budeme vám čas. A jdeme na udržet skutečný tentokrát takže budeme snažit tlačit protože jinak to bude únavné rychle. Pokud byste mohli pokračovat třídit 52 prvky spolu přes některé prostředky, hned. 

A opět, jak jsme se dívat na to kluci dělat co, na konci bude produkovat jasné Výsledkem je, přemýšlet o tom, opravdu jak si každý dělá, jak můžete to popsat. Vzhledem k tomu, opět se jedná o Všechny procesy, algoritmy které bereme jako samozřejmost jako člověk. Ale pravděpodobně jste už dlouho intuice, dlouho předtím, než vás, i myšlenka o tom, výpočetní technika vám třída mohla být důvodem pro intuici s pro řešení problémů, jako je tento. Ale jakmile poznáte vzory a začít formalizovat kroky, s nimiž máte řešení těchto problémů, zjistíte, že můžete vyřešit mnoho zajímavější a mnohem složitější problémy rychle. Takže někdo z publika, co je alespoň jeden prvek z algoritmu že používáte tady? 

Diváků: [neslyšitelné] SPEAKER: Co je to? DIVÁKŮ: Podle obleku. SPEAKER: Podle obleku. Takže nejprve se klastrování všechny diamanty společně Zdá se, že všechny srdce spolu se zdá, a tak dále, a to bez ohledu pro čísla na kartách. A teď se zdá, například, k třídění je podle čísla. Velmi dobře. 

Dobře, takže to, co se být posledním krokem pak tady? Jakmile budeme mít čtyři tříděných obleky, co to musíme udělat, aby se čtyři piloty , aby se dosáhlo jedné řazeny palubu, jednoduše? Proto musíme znovu sloučit. 

Takže tam je to zajímavý nápad, který opět Troufám si tvrdit, je velmi intuitivní, i pokud jste možná nikdy facku tento druh štítku na to. Tato základní představa o rozdělení problém není v polovině této doby, ale alespoň do čtyř částí. Řešení do značné míry v podstatě identické problémy izolovaně od sebe, a sloučení výsledků. A vynikající, hotovo. Tak jo, malý a velký okruh potlesk, kdybychom mohli. 

[APPLAUSE] 

SPEAKER: Nemám ponětí, co budete dělat s nimi, ale tady to máte. Děkuji moc. Tak se podívejme, dvě minuty a osm sekund, pokud byste chtěli vyzvat své přátele. Co se pak bude by se od tohoto že můžeme využít obecně? No, myslím, že zpět do Toto pole čísel, a myslím, že teď vrátit k některým pseudokód psali jsme v minulosti, a to pseudokód pro řešení telefonního seznamu problém. Přičemž v pseudokódu I vyjmenoval více metodický způsob popisovat, jak jsem to udělal velmi intuitivní lidský algoritmus dělení telefon knihy na polovinu, opakovat, opakovat, opakovat, dokud nenajdu někoho, jako Mike Smith, v případě, že je opravdu v telefonním seznamu. 

Ale nějak jsem použít to, co budu říkat velmi iterativní přístup zde zejména oznámení linka 8 a linka 11. To jsou důkazy o iterativní přístup, přístup smyčkování, protože to je přesně to, chování, které vyvolávají. Tyto řádky oba, že jít do řádek tři, a můžete trochu myslet, že ve vašem mysli oko jako smyčka. Je to říkám, jít zpět ke kroku tři a opakovat znovu a znovu, a znovu. 

Ale co když budeme využívat klíčovou myšlenku tady, že jsme neměli v poslední době, a zjednodušit linky 8 a řádek 11 a jejich sousedé jak je jen to, žlutě. Není to v podstatě zkrácení pseudokód moc, ale je to v podstatě mění povahu mého algoritmu. To, co jsem teď řekl v kroku 7, v kroku 10, je hledat Mike v přesně stejným způsobem, ale jen v levé polopenze nebo pravou polovinu. 

Takže jinými slovy, v případě, Začnu od kroku jedna, zvednout telefonní seznam, otevřený střed z telefonního seznamu, podívejte se na jména, pokud Smith patří mezi Název je, zavolejte Mike, jinak pokud Smith dříve v knize krok za sedm hledat Mike v levé polovině knihy. Ale trochu pocit, jako to nechal mě visí, že jo? Ve žluté, je instrukce, ale jak to mám hledání Mike v levé polovina z telefonního seznamu? Kde mám algoritmus, se kterým jsem Můžete hledat někoho, jako je Mike Smith? No, je to zírá nás tváří v tvář. Mohu doslova použít přesně stejný program skutečně jít až na vrchol Znovu a znovu běží stejné řádky kódu. 

Takže i když by to mělo cítit jako trochu cyklické definice kam odpovědi někdo Otázka, kterou tak nějak se ptát opět stejná otázka, jako proč, proč, proč? Skutečností je, protože jsme pevně dáno několik speciálních linek, krok 4, , který je v případě, a krok 12, který je v podstatě další větev, protože máme ty provizorium opatření, Tento algoritmus se ukončí, pokud budeme najít Mike, nebo pokud to neuděláme. Ale v kroku 7 a 10 nyní máme co budeme říkat rekurzivní algoritmus. A rekurze je opravdu silný nápad to je trochu mysl ohýbání na první, že nyní můžeme aplikovat takto. 

Merge sort bude poslední druh, který se podíváme na, alespoň ve třídě formálně. A to je zásadně odlišná z těch posledních tří, a jistě Poslední čtyři zahrneme-li bogosort. Zde je pseudokód pro slučovací druhu. Když se na vstupu n prvků tak, vzhledem k pole o velikosti n, pokud n je menší než 2, vrátit. Tak proč mám, že zdravý rozum zkontrolovat jako první? Jaký je důsledek, pokud předám vás pole, jehož délka n je menší než 2? Je to již řazeno, samozřejmě, že jo? Protože seznam má buď jeden prvek, který je triviálně řazeny, protože je to Jediné, co tam. Nebo je to o velikosti nula, což znamená, nic vyřešit, tak od přírody to je tříděn. Je tu jen nic špatného tam. Tak to je náš takzvaný referenční případ. 

To je podobné v duchu na to, co jsme udělali s Mikem. Pokud se Mike v telefonním seznamu, zavolejte mu. Pokud tam není, vzdát. Je to takzvaný referenční případ, aby se ujistil, Tento algoritmus na konci dne se zastaví v určitých okolností. 

Ale tady je ten skok víry nyní, jinak, seřadit levou polovinu prvků, seřadit právo polovina z prvků, a pak sloučit seřazené poloviny. A tady je místo, kde se cítí to, že jsme copping ven. Požádal jsem vás, abyste třídění n prvků, a já jsem řka: OK, to je třídění doleva a třídění právo. Ale já říkám jedno Další věc, a to je klíčové téma se zdá, v intuici tak daleko, tam je to třetí krok slučování. Které, i když se zdá být tak hloupý v duchu, jako právě sloučit věci spolu, se zdá být klíčovým krokem směrem k opětovnou montáž dvou problémů, které byly rozděleny nakonec v polovině. 

Takže sloučit druh, jdeme na to, pokud budete humor, abych se ještě jednu demonstraci, jen proto, že máme nějaké Čísla pracovat. Mohu u Vás vyměnit osm stres míče pro osm lidí? Dobře, a co vy tři, vy čtyři v této části, pět, šest, a pojďme do 7, 8, pojď nahoru. OK, jo OK. Minus 8, jdeme na to, plus 1. Výborně. Dobře pojď nahoru, pojďme Rychle vám čísel. Číslo dvě, číslo tři, číslo čtyři, číslo pět, šest, sedm a osm. Udělal jsem osm správně tentokrát. 

OK, tak do toho, pokud byste mohl, a seřaďte v původním pořadí že jsme měli včera, která se zabývala takhle, pokud vám to nebude vadit. A jdeme na to před stolem. Dobře, takže sloučit druh. To je místo, kde to bude dostat docela zajímavé, protože to vypadá, že dávat sám sebe mnohem méně informací dnes. 

Takže sloučit druh v první řadě na vstupu n prvků, a je samozřejmě ne méně než dva, je to osm, takže mám trochu víc práce. Takže teď psychicky jsme se jako třída jsou nyní v odvětví jiném, což znamená, že tři kroky. Za prvé, musím vyřešit levá polovina prvků. Tak jak mám jít asi dělá? No, já jdu na druh mentálně rozdělit seznam zde nemáte k fyzicky pohybovat, a já jsem Zaměřím se pouze na levá polovina prvků zde. Tak jak mám jít o třídění seznam se velikosti čtyři? Co je můj algoritmus? Nejprve jsem zkontrolujte n menší než dva, ne, tak jsem se přistoupit k bloku jiného znovu. Seřadit levé polovině prvků. 

Takže znovu, mentálně, a to je tam, kde Máte přibývat spoustu duševní historie, chcete-li. Teď třídění levé polovina z levé poloviny. Dobře, takže teď volám stejný korespondence algoritmus třídění, n je menší než dva? Ne, je to dva, takže musím vyřešit levá polovina, a pravou polovinu. Tak jdeme na to, třídění levé poloviny. Proč ne jen jeden krok vpřed. Jak se jmenujete? 

DIVÁKŮ: Darren. 

SPEAKER: Dan. Dan udělal krok vpřed. 

DIVÁKŮ: Darren. SPEAKER: Darren, hotovo. Říkala jste, že Darrena nebo Dan? 

DIVÁKŮ: Darren. 

SPEAKER: Darren. OK, Darren přistoupil dopředu a on je nyní řazeny. A to je téměř stupidní tvrzení, že jo? Nemám opravdu Zdá se, že dosažení něco, ale pojďme pokračovat. Nyní mi dovolte seřadit právo polovina z těchto prvků. Jak se jmenujete? 

DIVÁKŮ: Luke. 

SPEAKER: Luke. Pojď, krok vpřed. Hotovo, jsem řazeny Luku. Levá polovina je nyní tříděny a pravá polovina je nyní tříděny, ale zase tam je klíčovým krokem zde. Co u potřeba udělat? Sloučit seřazené poloviny. Nyní budeme prostě muset všichni sem a tam tak, protože jsem tak trochu potřebovat nějaký odkládací prostor. Je to skoro, jako jsou tyto kluci jsou na stole, a já potřebuju nějaký prostor je pohybovat dál. Takže budu sloučit vy od pohledu v levé polovině a pravé polovině. A kdo zřejmě je na prvním místě, vlevo nebo vpravo polovina poloviny? Takže pravá polovina, takže pojďme Luka nad zde původní polohy Darren. A teď sloučit jejich levou polovinu v, Darren se bude pohybovat právě tam. 

Tak se cítí jako téměř bublina druh účinku, ale moje základní algoritmus, velmi odlišné tentokrát. Ale teď je místo, kde se věci trochu nepříjemné, protože jste muset přetočit mentálně kde jsem odejít pryč. Právě jsem se spojil setříděné poloviny, což znamená, že jsem tam, kde ve svém algoritmu? Musím vyřešit pravou polovinu, ne? 

Máte-li vzad, a to doslova na videu, budete vidět, že jsme se dostali do této bod Luke a Darren tříděním doleva polovina z levé poloviny. Pak jsme se spojil ty tříděné poloviny, které znamená, že dalším krokem je třídění Pravá polovina levé polovině. Dobře, tak pojďme to rychleji. Tak jo, šest, budu tvrdit, jste nyní tříděny, pojď dopředu. Jak se jmenujete? 

DIVÁKŮ: Adriano. 

SPEAKER: Adriano. Adriano je nyní řazeny. A Jak se jmenujete? 

DIVÁKŮ: Alex. 

SPEAKER: Alex je nyní řazeny. Levá polovina, pravá polovina, co je poslední krok? Sloučit. Docela triviální, takže jsem k fúzi v šesti, krok zpět, osm, udělat krok zpět. A teď si toho všimnout je užitečné stánek s jídlem, co je nyní platí o levé polovině seznam, a to bez ohledu na to, jak jsme začali? To je tříděn. 

Teď to není seřazen velký schématu věcí, ale to je řazen samostatně z druhé poloviny. A teď, co krok to jsem na tom, zda jsem se udržet převíjení, jak příběh začal? Teď musím vyřešit pravou polovinu. Takže teď jsme cestu zpět na začátek příběhu, a pojďme na to rychleji. Takže budu třídit pravá polovina celého seznamu. Jaký je další krok? Seřadit levou polovinu pravé polovině. Seřadit levé polovině levá polovina v pravé polovině. A Jak se jmenujete? 

DIVÁKŮ: Omar. 

SPEAKER: Omar, krok vpřed, hotovo. Levá polovina je tříděn. A Jak se jmenujete? 

DIVÁKŮ: Chris. 

SPEAKER: Chris, krok vpřed, jste nyní řazeny. Co je klíčovým krokem teď? Sloučit. Takže člověk se chystá sloučit své místo zde, pokud byste mohli udělat krok zpět, a tři se chystá krok zpět, sloučit. Takže levá polovina Pravá polovina je nyní řazeny. Upřímně řečeno, tento algoritmus pocit, jako bychom Ztrácíte způsobem více času než dříve, ale když jsme to udělali v reálném čase, budeme vidět, co takeaways bude. A teď jsem tady, že jo polovina pravé polovině, nech mě jít napřed a seřadit levou polovinu. Krok vpřed, Jak se jmenujete? DIVÁKŮ: Ramsey. SPEAKER: Ramsey je nyní řazeny. Jak se jmenujete? 

DIVÁKŮ: Marina. 

SPEAKER: Marina je nyní řazeny jako dobře, pokud budete mít o jeden krok vpřed. Klíčovým krokem je zde nyní sloučit, jsem bude trhat ze svých dvou seznamů, vlevo a vpravo. Pět bude na prvním místě, a sedm se chystá přijít další. A opět, je to záměrné. Skutečnost, že užíváte kroky vpřed a vzad má představovat, že nemůžeme do tohoto algoritmu na místě, jak snadno jako bublinkové třídění a výběru druhu, a vložení třídění, kde se právě stále vyměňovat lidí. Doslova jsem potřebovat jakousi poškrábání papíru, ve kterém aby tyto lidi když jsem to sloučení, a pak jsem je dát zpět na místo. A to je klíč, protože já jsem s použitím nové zdroje, prostor, a to nejen čas. 

OK, to je úžasné. Levá polovina je tříděn, pravá polovina je tříděny, teď ten klíč sloučení krok. Jak to mám sloučit to? Takže pokud budete následovat mé levá ruka a pravá ruka, Chystám se ukázat svou levou ruku na levé polovině, moje pravá ruka v pravé polovině, a teď musím rozhodnout, krok za krokem, kterého se sloučí. Kdo samozřejmě na prvním místě? Číslo jedna. Tak pojď sem, tady je náš poznámkový blok. Takže teď číslo jedna a oznámení co budu dělat s mou pravou rukou, Chystám se hýbat pravou rukou jednoho krokem se k bodu číslo tři, a teď mám udělat Stejné rozhodnutí. A vlastně stojí přímo v přední Lukáše zde, pokud byste mohli, protože to je náš poznámkový blok. Tak kdo je další? Máme Luke s číslem dvě nebo Chris s číslem tři. Je zřejmé, Luke, číslo dva, takže se sem. 

Ale moje levá ruka teď se chystá být zvýšen poukázat na Darrena, a tady je klíč odnést s sloučení, budu v tom pokračovat, Je zřejmé, že pokud máte trochu o sledovat logiku. Ale moje ruce nikdy jít zpět, což znamená, že jsem jen někdy stěhují do odešel s mým proces sloučení, a že to bude klíčem k naše analýza za chvíli. 

Takže teď pojďme dokončit rychle nahoru. Takže tři přijde příště, pak čtyři přijde příště, a teď pět přijde příště, pak šest, a sedm a nakonec osm. Cítím se jako nejpomalejší algoritmus ještě, ale ne v případě, vlastně nechte jej běžet na stejném druhu o taktovací frekvenci, takže se mluvit, se stejným tikající hodiny jako předtím. Proč? No, pojďme se se podívat na konečný výsledek. 

Vraťme se tady, dovolte mi, abych vytáhnout demonstraci vizuálně z toho, co jsme právě udělali. Zvětšení zde, na tomto strana tady, říká Firefox že chceme do fronty v tomto poli, pojďme říkají bublina druh, s nímž teď jsme dobře obeznámeni, Výběr třídění, což je další poměrně přímočará, a nyní dnešní merge sort, který bude naše vrcholná konec. Důvod, proč to trvalo tak dlouho zde s lidmi a já slovně je, samozřejmě, já jsem vysvětlovat každý krok. Ale pokud jste jednoduše spusťte tento, moc jako jsme to udělali bubble sort a výběr třídit nejen vizuálně, hodinky jak mnohem efektivněji to prosazováním dělení a dobývání může být při aplikaci do datového souboru, který je Ani velikost osm, ale ještě mnohem, mnohem větší. Dám vám sloučit druh, vedle strana s těmito dalšími algoritmy. To dostane bolestivé rychle, a konec není nijak zvlášť vrcholná, prostě skončit řazeny. Ale klíč odnést je, že Podívej se, jak daleko rychleji sloučit druh byl, pokud si myslíte, že jsem jen tak si s vámi. Pokud se nám tento jeden poslední čas, pojďme znovu to, vraťme a zvolte bubliny druhu, a jen tak pro legraci, Zvolme vložení třídění, jen pro jistotu. A tentokrát opět, pojďme vyberte slučovací druh a pojďme vlastně spustit tyto bok po boku. 

A to není, ve skutečnosti, náhoda. Co jsem skutečně udělal je, že jsem rozdělit svůj vstup na polovinu, opět a znovu a znovu. A je to jen tolikrát můžete rozdělit váš vstup do poloviny, levá a vpravo. Jaký je vzorec, který držíme vidět , který popisuje rozdělení na dvě poloviny znovu a znovu, a znovu, a znovu? 

Diváků: log n. 

SPEAKER: log n. Ale pak je tu ještě jedna další klíčový krok, Tento algoritmus není přihlášena n kroků. Pokud by bylo jen přihlásit n kroků, bychom být ve stejném problému jako dříve, kde nemůže být že všechno je třídit. Musíte se minimálně podívat na n prvků být jisti, že n prvky jsou tříděny, jinak je to skok víry. 

Takže je to minimálně log n kroky, ale co této klíčové sloučení kroku kde jsem se spojil moje levá polovina a doprava poloviny a přešel přes jeviště? Kolik kroků je sloučit? Je to n, ale neudělal jsem to jen sloučit konečný čas. Na každé z těchto vnořených volání, na každém z těchto vnořených slučování, přesto jsem řazeny. I sloučil tyto dva chlápky, pak se tyto dvě kluci, pak tihle dva, a tak dále. 

Tak jsem se sloučení znovu a znovu. Kolikrát? Takže pokaždé, když jsem se rozdělil seznam na polovinu, jsem sloučení. Rozdělte seznam na dvě poloviny, do sloučení. Takže v případě, dělení seznam může být provedeno log n krát, a sloučení nakonec se n kroky, co by mohlo být nyní horní vázána na chod Doba našeho algoritmu? n log n. 

A vskutku, to je to, co jsme tu dosáhli. Takže myslíte, že jste vidět vizuálně, když tyto tři věci běží bok po boku je n na druhou proti n na druhou proti n log n. Které zásadním uvidíme, nejen dnes, ale v budoucnu, je mnohem, mnohem rychleji. Potlesk pro tyto lidi, Já se za to odmění Antistresové míčky. Pojďme odložit dnes, a Vás budeme vidět v pondělí.