[Přehrávání hudby] 

Profesor: Dobře. To je CS50, a to je koncem třetího týdne. Tak jsme tady dnes, ne v Sanders Divadlo, místo toho v Weidner knihovně. Uvnitř což je studio známý jako Hauser Studio, nebo řekněme Studio H, nebo musí my say-- pokud se vám to líbilo ten vtip, je to vlastně z spolužák, Mark, online, který navrhl tolik přes Twitter. Teď, co je v pohodě tady ve studiu je, že jsem obklopen těchto zelených zdi, zelené obrazovky nebo chromakey, tak říkajíc, což znamená, že je CS50 Inscenační tým unbeknownst mně právě teď, může být uvedení Nejvíc mě kdekoli na světě, k lepšímu nebo k horšímu. 

Teď, co je před námi, nastavte problém dva je ve vašich rukou pro tento týden, ale s problémem set Tři tento nadcházející týden, budete mít za úkol s tzv hra 15, starý strana laskavost, že můžete připomenout příjem jako dítě, který má spoustu čísel, která může klouzat nahoru, dolů, vlevo a vpravo, a je tu ještě jedna mezera v rámci skládačky, do kterého jste může skutečně posunout ty dílků. Nakonec obdržíte tento puzzle v nějakém semifinále náhodném pořadí, a cílem je, aby třídit to, shora dolů, zleva doprava, z jedné celou cestu nahoru přes 15. 

Bohužel, implementace budete mít po ruce bude software na bázi, není fyzicky. Ty vlastně bude muset psát kód, pomocí kterého student nebo Uživatel může hrát hru 15. A ve skutečnosti, v hacker vydání hry 15, budete výzvou realizovat, ne jen hraní této staré školy hra, ale spíše řešení o tom, kterou se provádí nesmrtelnost, abych tak řekl, že ve skutečnosti řeší puzzle pro člověka, tím, že jim s nádechem, po náznaku, po náznakem. Takže o tom až příští týden. Ale to je to, co nás čeká. 

Pro tuto chvíli připomenout, že začátkem tohoto týdne jsme měli tento cliffhanger, chcete-li, přičemž nejlepší, co jsme dělali třídění moudrý byla horní hranice velkého o n na druhou. Jinými slovy, bublinkové řazení, výběr třídění, insertion sort, všechny z nich, zatímco jiná při jejich provádění, přešel do n druhou spuštění Čas ve velmi nejhorším případě. A my obecně předpokládají, že úplně nejhorším případě pro třídění je ten, který vaše vstupy jsou zcela dozadu. A skutečně, to trvalo poměrně málo kroků k provádění každé z těchto algoritmů. 

Nyní na samém konci třídy Připomeňme, porovnali jsme bublinkové řazení proti výběru druhu proti jednomu jiný že jsme nazvali merge sort v té době, a navrhuji, aby to trvá Výhodou lekci od týdne nula, rozděl a panuj. A nějak dosáhnout nějaký druh logaritmická doba chodu nakonec, místo něčeho to je čistě kvadratická. A není to úplně logaritmické, je to trochu víc než to. Ale pokud si vzpomínáte ze třídy, to bylo mnohem, mnohem rychlejší. Pojďme se podívat, kde jsme přestali. 

Bubble sort proti výběru třídit proti sloučení druhu. Teď jsou všichni běží, v teorie, ve stejnou dobu. CPU běží stejnou rychlostí. Ale můžete cítit, jak to nuda se velmi rychle stane, a jen jak rychle, když jsme injekci trochu týdnu nula je algoritmů, můžeme věci urychlit. 

Takže značka nějak vypadá úžasně. Jak můžeme využít ji, aby rychleji seřadit čísel. Tak pojďme vzpomenu na složky, které jsme měla již v týdnu nula, to hledat někoho, kdo se v telefonním seznamu, a připomněl, že pseudokód, že jsme navrhli, přes který můžeme najít někdo jako Mike Smith, vypadal trochu něco takového. 

Nyní se podívejte především na řádku 7 a 8, a 10 a 11, který přimět jej smyčky, čímž jsme ponechali jít zpátky do řádku 3 znovu a znovu, a znovu. Ale ukazuje se, že můžeme zobrazit Tento algoritmus, tady v pseudokódu, trochu více holisticky. Ve skutečnosti to, co jsem hledal v tady na obrazovce, je algoritmus pro vyhledávání Mike Smith mezi některými sady stránek. A skutečně, můžeme zjednodušit tento algoritmus v těchto bodů 7 a 8, a 10 a 11 jen říct to, který jsem zde uvedena v žluté. Jinými slovy, v případě, Mike Smith je dříve v knize, nepotřebujeme specifikovat krok za krokem, teď, jak ho najít. Nemáme specifikovat se vrátit do řádku 3, proč ne my jen místo, řekněme, obecněji, hledat Mike v Levá polovina knihy. 

Naopak, pokud je Mike ve skutečnosti později v knize, proč ne my jen citovat konec citátu hledání Mike v pravé polovině knihy. Jinými slovy, proč ne my jen druh pramici na sebe říká, hledat Mike v této podmnožina knihy, a nechte to na naše stávající algoritmus, aby nám řekli jak hledat Mike v že levá polovina knihy. Jinými slovy, naše algoritmus pracuje ať už je to telefonní seznam této síly, z toho Tloušťka, nebo jakékoliv tloušťce vůbec. Takže můžeme rekurzivně definovat tento algoritmus. Jinými slovy, na Obrazovka tady, je algoritmus pro vyhledávání Mike Smith Mezi stránkami telefonního seznamu. Takže v řádku 7 a 10, pojďme jen říct, že přesně. A já používat tento termín na chvíli Před, a opravdu, rekurze je módní slovo pro tuto chvíli, a to je tento proces dělat něco, co by nějak cyklické pomocí kódu, který již máte, a znovu volá, a znovu a znovu. Teď to bude důležité, že jsme se nějak dno out, a nedělejte to nekonečně dlouho. V opačném případě budeme mají opravdu nekonečné smyčce. Ale pojďme se podívat, jestli můžeme půjčit tuto myšlenku z rekurze, zase něco a znovu a znovu, řešit třídění problém přes sloučení třídit, tím efektivněji. 

Takže dávám sloučení třídit. Pojďme se podívat. Takže tady je pseudokód, s které jsme mohli provádět třídění, Pomocí tohoto algoritmu s názvem merge sort. A je to docela jednoduše to. Na vstupu n elementy, Jinými slovy, pokud jste vzhledem k tomu, n prvky a čísla a dopisy nebo co je vstup, pokud jste dal n elementy, pokud n je menší než 2, jen se vrátit. Je to tak? Vzhledem k tomu, pokud n je menší než 2, které Znamená to, že můj seznam prvků je buď o velikosti 0 nebo 1, a V obou těchto případech triviální, seznam je již řazeno. Pokud není k dispozici seznam, je to třídit. A pokud tam je seznam délky 1, je to samozřejmě třídit. Takže algoritmus pouze potřebuje opravdu něco zajímavého, pokud budeme mít dva nebo více prvky nám dána. Takže pojďme se podívat na magii poté. Else seřadit levé poloviny prvků, pak třídit pravou polovinu prvků, pak sloučit setříděné poloviny. A co je druh mysli ohýbání tady je, že opravdu nemám Zdá se, že vám řekl, něco ještě ne, že jo? Všechno, co jsem řekl, je, dostane seznam n prvků, třídit levou polovinu, poté pravé poloviny, poté sloučit seřazené poloviny, ale tam, kde je skutečný tajný recept? Kde je algoritmus? No, ukázalo se, že těch dvou linek První, druh levé polovině prvků, a druh pravá polovina prvků, jsou rekurzivní volání, abych tak řekl. 

Koneckonců, na to bod v čase, musím algoritmus, se kterým seřadit spoustu prvků? Ano. Je to přímo tady. Je to přímo tady na obrazovce, a takže mohu použít ten stejný soubor kroků třídit levou polovinu, jak mohu pravá polovina. A skutečně, znovu a znovu. Takže tak či onak, a my brzy vidět, kouzlo sloučení druhu je zakotven v tom, že velmi konečný linka, slučování tříděných poloviny. A to se zdá být poměrně intuitivní. Budete mít dvě poloviny, a ti, nějak, spojit je dohromady, a my budeme vidět konkrétně za chvíli. 

Ale to je kompletní algoritmus. A podívejme se, proč. Tak předpokládám, že jsme vzhledem k tytéž Osm prvky tady na obrazovce, jeden přes osm, ale jsou ve zdánlivě náhodném pořadí. A cíl je na dosah ruky třídit tyto prvky. Tak jak mohu jít o dělá použití, znovu, merge sort, jak na tento pseudokódu? A opět, barvit to v vaše mysl, jen na chvíli. V prvním případě je dost triviální, pokud je to méně než 2, jen vrátit, není práce je třeba udělat. Takže opravdu tam je jen tři kroky k opravdu mít na paměti. Znovu a znovu, já jsem bude chtít mít třídit levou polovinu, třídit pravou polovinu, a pak ještě jednou jejich dvě poloviny jsou řazeny, Chci je sloučit dohromady do jednoho seřazeném seznamu. Takže mějte na paměti, že. 

Tak tady je původní seznam. Pojďme se touto jako pole, jak jsme začali ve dvou týdnu, což je souvislý blok paměti. V tomto případě, který obsahuje osm Čísla, zády k sobě k sobě. A pojďme se nyní vztahují merge sort. Tak jsem se poprvé chcete seřadit levá polovina tohoto seznamu, a pojďme se tedy, zaměřit se na 4, 8, 6, a 2. 

Nyní, jak mám jít o řazení seznamu velikosti 4? No musím nyní považují třídění vlevo od levé poloviny. Opět platí, pojďme vzad jen na chvíli. V případě, že je to pseudokód, a já jsem dal osm elementů, 8 je samozřejmě větší, než nebo roven 2. A tak se o první případ, nepoužije. Takže třídit osm elementů, jsem poprvé řadit levou polovinu prvků, Pak jsem seřadit pravou polovinu, pak jsem se sloučit obě seřazená poloviny, každá o velikosti 4. DOBŘE. 

Ale pokud jste právě mi řekl, setřiďte levá polovina, která je nyní o velikosti 4, jak mám třídit levou polovinu? No, pokud mám vstup ze čtyř prvků, Poprvé jsem řadit levou dvou a poté pravé dva, a pak jsem se spojit je dohromady. Takže znovu, to se stává trochu na mysli ohýbání hru tady, Protože ty, druh, musí vzpomenout, kde jste v příběhu, ale na konci dne, vzhledem k tomu, libovolný počet prvků, nejprve chcete třídit levá polovina, potom pravá polovina, pak spojit je dohromady. Pojďme začít dělat přesně to. Zde je vstup z osmi prvků. Nyní se díváme na levé polovině zde. Jak mám třídit čtyři prvky? Tak jsem nejprve seřadit levé poloviny. Nyní, jak se mohu řadit levou polovinu? No já jsem dostal dva prvky. Takže pojďme seřadit tyto dva prvky. 2 je větší než nebo rovné 2, samozřejmě. Tak, že první případ nevztahuje. 

Takže jsem teď musí třídit levou polovina z těchto dvou prvků. Levá polovina, samozřejmě, je jen 4. Tak jak mám seřadit seznam z jednoho prvku? Tak a teď, že zvláštní referenční případ up vrcholu, abych tak řekl, platí. 1 je menší než 2, a my Seznam je skutečně o velikosti 1. Tak jsem se vrátit. Já nedělám nic. A skutečně, dívat se na to, co jsem udělal, 4 je již řazeno. Jako bych už částečně úspěšné zde. 

Nyní se zdá, že trochu hloupý nároku, ale je to pravda. 4 je uveden seznam velikosti 1. Je to již řazeno. To je levá polovina. Teď jsem řadit pravou polovinu. Můj vstup je jedním z prvků, 8 podobně, již seřazeny. Hloupý, taky, ale opět, Tento základní princip bude nám umožní si nyní budují v horní části této úspěšně. 4 řazeny, 8 je tříděn, nyní co to bylo poslední krok? Takže třetí a poslední krok, jakýkoliv Čas, který se třídění seznamu, odvolání, bylo sloučit dvě poloviny, levý a pravý. Takže pojďme udělat přesně to. Má levá polovina je, samozřejmě, 4. Moje pravá polovina je 8. 

Tak jdeme na to. Nejprve budu přidělit některé další paměť, že budu reprezentovat tady, jen jako sekundární pole, to je dost velký, aby se vešly to. Ale můžete si představit rozšíření že obdélník po celé délce, pokud budeme potřebovat více později. Jak mohu pořídit 4 a 8, a sloučit tyto dva seznamy velikosti 1 spolu? I zde docela jednoduché. 4 je na prvním místě, pak přijde 8. Protože pokud chci na třídíte levá polovina, potom pravá polovina, a potom sloučit tyto dvě poloviny společně, v seřazeném pořadí, 4 je na prvním místě, pak přijde 8. 

Takže se zdá, že bude dělat pokroky, a to i i když jsem neudělal žádnou skutečnou práci. Ale pamatujte, kde jsme v příběhu. Původně jsme vzali osm prvků. Vyřešili jsme levou polovinu, což je 4. Pak jsme řazeny levou polovinu z levé poloviny, který byl 2. A je to tady. Jsme skončili s tímto krokem. 

Takže pokud jsme třídí levé poloviny 2, teď jsme mají třídit pravou polovinu 2. Takže pravá polovina 2 je Tyto dvě hodnoty zde, 6 a 2. Takže pojďme se teď vstup velikosti 2, a třídit levou polovinu, a poté pravou polovinu, a poté sloučit dohromady. Tak jak mám seřadit seznam velikosti 1, který obsahuje jen číslo 6? Já jsem už skončil. Tento seznam o velikosti 1 je seřazen. 

Jak mohu vyřešit další seznam velikost 1, tzv pravá polovina. No to, také, je již řazeno. Číslo 2 je sám. Takže teď mám dvě poloviny, vlevo a Dobře, je třeba je sloučit dohromady. Dovolte mi abych si nějaké extra prostor. A dal 2 tam, pak 6 tam, čímž třídění tohoto seznamu, vlevo a vpravo, a slučování společně, nakonec. Takže já jsem v trochu lepším stavu. Já jsem neskončil, protože jasně 4, 8, 2, 6 není konečný, které nařizuje chci. Ale teď mám dva seznamy velikosti 2, že mají oba, v daném pořadí, byly seřazeny. Takže teď, pokud přetočíte ve vaší mysli oko, kde se to pro nás znamená? Začal jsem s osmi prvků, pak jsem ořezaný dolů do levé poloviny 4, poté levou část 2, a pak je pravá polovina 2, Jsem skončil, a proto, třídění levý poloviny 2, a v pravé polovině 2, takže to, co je tady třetí a poslední krok? Musím se spojit dohromady dva seznamy velikosti 2. Tak pojďme do toho. A na obrazovce se tady, dej mi některé další paměť, ačkoli technicky, všimněte si, že jsem dostal spoustu prázdné místo na začátek tam. Pokud chci být obzvláště efektivní prostor moudrý, Mohl bych dát do pohybu prvky tam a zpět, nahoře a dole. Ale jen pro vizuální jasnost, Chystám se dát to dole, udržet věci pěkné a čisté. 

Tak jsem dostal dva seznamy velikosti 2. První seznam má 4 a 8. Druhý seznam obsahuje 2 a 6. Pojďme sloučit ty spolu v seřazeném pořadí. 2, samozřejmě, je na prvním místě, pak 4, pak 6, pak 8. A teď se zdá, že se dostat někde zajímavé. Teď jsem řazeny polovina vypsat, a shodou okolností je to všechna sudá čísla, ale že je opravdu jen náhoda. A teď si řazeny levý polovina, tak, že to je 2, 4, 6 a 8. Nic není mimo provoz. To se cítí jako pokrok. 

Teď to vypadá, jsem byl nyní hovoří navždy, Takže to, co zbývá být viděn jestliže toto algoritmus je skutečně efektivnější. Ale my procházíme to výborný metodicky. Počítač, samozřejmě, bych to takhle. Tak kde to jsme? Začali jsme s osmi prvků. Řazeny jsem levou polovinu 4. Zdá se mi, je třeba udělat s tím. Takže teď je dalším krokem k třídit pravou polovinu 4. A tato část můžeme jít přes trochu více rychle, i když jste Vítáme Vás na vzad nebo pozastavit, jen myslíte, že přes to na svým vlastním tempem, ale to, co teď máme, je příležitost dělat přesně stejný algoritmus na čtyřech různá čísla. 

Tak pojďme do toho, a zaměřit se na pravá polovina, který jsme tady. Levá polovina, která pravou polovinu, a teď Levá polovina vlevo polovina z té pravé poloviny, a jak seřadit seznam velikosti 1 obsahující pouze číslo 1? Už se stalo. Jak to mám udělat totéž pro seznam o velikosti 1, který obsahuje jen 7? Už se stalo. Třetí krok pro toto je polovina je sloučit tyto dva prvky do nového seznamu velikosti 2, 1 a 7. Nezdá se, že udělali vše že hodně zajímavá práce. Podívejme se, co se bude dít dál. Jen jsem řazeny do levé poloviny pravá polovina mého původního vstupu. Nyní pojďme seřadit právo polovina, která obsahuje 5 a 3. Pojďme se znovu podívat na levé straně polovina, tříděny, pravá polovina, tříděny, a spojit ty dva dohromady, do nějakého dalšího prostoru, 3 je na prvním místě, pak přijde 5. A tak teď jsme se třídí Levá polovina pravou polovinu z původní problém, a pravá polovina pravou polovinu z původní problém. Co je třetí a poslední krok? No sloučit tyto dvě poloviny dohromady. Tak ať mi, abych si sám trochu prostor navíc, ale opět jsem může být pomocí tohoto extra prostor na vrchol. Ale budeme držet to jednoduché vizuálně. Dovolte mi, abych nyní sloučit v 1, a pak 3, a poté 5, a pak 7. Tím mě teď opouští s Pravá polovina původní problém to je dokonale seřazeny. 

Takže to, co zůstane? Mám pocit, jako bych držet říkat stejné věci znovu a znovu, ale to je odrážející Skutečnost, že jsme pomocí rekurze. Proces za použití algoritmus znovu a znovu, na menší podmnožiny původní problém. Takže jsem teď se levý seřazena polovinu původní problém. Mám právo seřazené polovinu z původní problém. Co je třetí a poslední krok? Oh, to je sloučení. Takže pojďme to udělat. Pojďme přidělit některé další paměť, ale můj Bože, ji mohl dát teď kdekoliv. Máme tolik místa k dispozici k nám, ale my budeme držet to jednoduché. Místo toho, aby šel zpět a dále s naší původní pamětí, ať to prostě udělat vizuálně tady dole, aby dokončit sloučení levou polovinu a pravá polovina. 

Takže sloučením, co musím udělat? Chci, aby se prvky v pořadí. Takže při pohledu na levé polovině, Vidím, první číslo je 2. Dívám se na pravou polovinu, Vidím první číslo je 1, tak samozřejmě což Číslo nechci trhat ven, a dal první v mém konečném seznamu? Samozřejmě, 1. Teď chci položit tuto stejnou otázku. Na levé polovině, jsem pořád číslo 2. Na pravé polovině, Mám číslo 3. Který z nich si chci vybrat? Samozřejmě, že číslo 2 a Nyní si všimnout kandidátů jsou 4 vlevo, 3 vpravo. Pojďme se, samozřejmě, zvolte 3. Nyní jsou 4 kandidáti na levá, 5 na pravé straně. My, samozřejmě, zvolte 4. 6 na levé straně, 5 vpravo. My, samozřejmě, zvolte 5. 6 na levé straně, 7 na pravé straně. Vybíráme 6, a pak jsme vybrat 7, a pak volíme 8. Voila. 

Tak obrovské množství slov později jsme mají řazeny tento seznam osmi prvků do seznamu jeden přes osm, který je roste s každým krokem, ale kolik času udělal trvat nás to udělat. No jsem záměrně položené věci obrazově tady, takže můžeme druh vidět nebo ocenit divizi dobýt, že se děje. 

Ve skutečnosti, když se podíváte zpátky na brázdě, Nechala jsem všechny tyto přerušovanou čarou V držitelů místě, můžete, druh, vidět, v opačném pořadí, pokud jste trochu ohlédnout v Historie teď, můj původní seznam Je, samozřejmě, velikosti 8. A pak již dříve, jsem byl zabývající se dvěma seznamy velikosti 4, a pak čtyři seznamy velikosti 2, a pak osm seznamy velikosti 1. 

Takže to, co dělá to, druh, vás upozorní na? No, opravdu, některé z algoritmy jsme Podíval se na tak daleko, kde jsme rozděl a dělit, a rozdělit, zachovat s věci znovu, a opět vede v tomto obecném myšlence. A tak je tu něco logaritmická tady děje. A není to úplně log n, ale tam je logaritmická komponent k tomu, co jsme právě udělali. 

Nyní se pojďme zvážit, jak to ve skutečnosti je. Takže log n, opět byl skvělý hrací čas, když jsme udělali něco jako binární vyhledávání, jak my teď říkáme, rozděl a panuj strategie přes který jsme našli Mike Smith. Teď technicky. To je základ log 2 n, a to i i když ve většině matematických tříd, 10 je obvykle báze, která se domníváte. Ale počítačoví odborníci téměř vždy myslet a mluvit, pokud jde o základně 2, takže jsme se obecně stačí říct záznam n, místo toho, log základny 2 n, ale jsou to přesně jeden a Totéž ve světě počítače vědy, a jak stranou, tam je konstantní faktor Rozdíl mezi těmito dvěma, takže je diskutabilní tak jako tak, pro více formálních důvodů. 

Ale teď, to, co nás zajímá o je tento příklad. Takže pojďme nedokazuje příkladem, ale v alespoň na jeden příklad z čísel po ruce jako kontrola sanitačního, chcete-li. Takže předtím vzorec byl základ log 2 n, ale to, co je v tomto případě n. Měl jsem n původní čísla, nebo 8 z původního počtu specificky. Teď už je to trochu zatímco, ale jsem docela jisti, že log základ 2 hodnoty 8 je 3, a opravdu, co je hezké o který je 3, který je přesně počet, kolikrát že můžete rozdělit seznam délky 8 znovu a znovu, a znovu, dokud jste odešel seznamy pouze velikosti 1. Je to tak? 8 jde do 4, jde do 2, jde k 1, a to je odrazem přesně to picture měli jsme před chvílí. Tak trochu zdravý rozum zjistit, kam logaritmus je vlastně jedná. 

Takže teď, co ještě se zde jedná? n. Takže si všimnout, že každý Když jsem rozdělil seznamu, i když v opačném pořadí v historii tady, byl jsem stále dělá n věci. Že sloučení krok vyžaduje, aby Dotknu každý jeden z čísel, aby to sklouznout svým vhodným umístěním. Takže i když je výška této diagram je velikosti log n n nebo 3, specificky, jinými slovy, Udělal jsem tři divize sem. Kolik práce jsem udělal horizontálně podél této tabulce pokaždé? 

No, já jsem n kroky fungovat, protože pokud jsem dostal čtyři elementy a čtyři elementy, a musím sloučit dohromady. Musím projít tyto čtyři a tyto čtyři, nakonec sloučit zpět do osmi prvků. Pokud naopak mám osm prstů tady, což nechci, a osmi fingers-- sorry-- jestli jsem dostal čtyři prsty sem, které dělám, čtyři prsty tady, což dělám, pak je to stejné Příkladem jako předtím, když to udělám mají osm prstů i když v celkem, který jsem si, druh, ano. Můžu přesně se zde, pak jsem si určitě sloučit všechny z těchto seznamů o velikosti 1, společně. Ale já rozhodně se podívat u každého prvku právě jednou. Takže je výška tohoto procesu je log n, šířka tohoto procesu, abych tak řekl, je n, takže to, co se nám zdá, mít, nakonec, je běžící čas o velikosti n časy log n. 

Jinými slovy, jsme rozdělili seznam, log n-krát, ale pokaždé, když jsme udělali, že jsme měli dotknout každý jeden z prvků, za účelem jejich sloučení dohromady, což n byl krok, takže máme n-krát log n, nebo jako počítačový vědec by řekl, asymptoticky, který by bylo velké slovo popsat horní vázané na jízdní doby, jsme se běží ve velkém O log n času, abych tak řekl. 

Nyní je to významné, protože vzpomenout, co běží časy byly bublinkové druhu, a výběr třídění a vkládání třídění, a dokonce i několik dalších, které existují, n čtvercový bylo místo, kde jsme byli na. A můžete, druh, vidět tady. Je-li na druhou n je samozřejmě n krát n, ale tady máme n-krát log n, a my již známe z týdne nula, že log n, logaritmické, je lepší než něco lineární. Koneckonců, připomínají obraz s červenou a žlutou a zelené linky, které jsme vypracovali, tím green logaritmická linie byla mnohem nižší. A proto, mnohem lépe a rychleji než rovných žluté a červené čáry, n-krát log n je skutečně lepší, než N-krát n, nebo n na druhou. 

Takže se zdá, že se identifikoval algoritmus sloučení druh, který běží v mnohem rychlejší, a dokonce, to je důvod, proč na počátku tohoto týdne, kdy jsme viděli, že soutěž mezi bubliny třídění, výběr třídit, a sloučit třídění, merge sort opravdu, ale opravdu vyhrál. A skutečně, jsme neměli ani čekat k Bubble druhu a výběru druhu dokončit. 

Nyní se pojďme jeden další průchod na to, ze o něco více formální perspektiva, jen v případ, to rezonuje lépe než této vyšší úrovni diskuse. Takže tady je opět algoritmus. Pojďme se sami sebe zeptat, co je doba chodu Je to algoritmy různé kroky? Pojďme rozdělit jej na první pouzdro a druhý případ. IF a jiný v případě, pokud, IF n je menší než 2, jen se vrátit. Cítím se jako konstantním čase. Je to, druh, stejně jako dvou krocích, IF n je menší než 2, pak se vrátíte. Ale jak jsme si řekli v pondělí, konstantní čas, nebo velký O 1, mohou být dvě, tři kroky kroky, dokonce i 1000 kroků. Důležité je, že je to konstantní počet kroků. Takže žlutý zvýrazněné pseudocode tady běží v, budeme říkat, konstantní čas. Takže více formálně, a jdeme to-- to bude míra, do které formalizovat toto právo now-- T n, běžící čas problému že se n somethings jako vstup, rovná big o jedné, IF n je menší než 2. Takže je to podmíněno to. Tak aby bylo jasno, když n je menší než 2, máme velmi krátký seznam, poté Doba chodu, T n, kde n je 1 nebo 0, v tomto velmi specifickém případě, je to jen bude konstantní čas. Bude to trvat jeden krok, dva kroky, cokoliv. Je to pevně stanovený počet kroků. 

Takže šťavnaté část musí jistě být v Druhým případem v pseudokódu. Případ ELSE. Třídit levou polovinu prvků, třídit vpravo polovina z prvků, sloučit tříděných půlky. Jak dlouho trvá každý z těchto kroků trvat? No, v případě, že běží čas, aby třídit n prvků je, nazvěme to velmi obecně, T n, pak třídění levou polovina elementů je trochu, jako říkat, T n děleno 2, a podobně třídění pravou polovinu prvků je, druh, jako říkat, T n rozdělena 2, a poté slučování seřazené poloviny. No, pokud mám nějaký počet prvků zde, stejně jako čtyři, a nějaké číslo prvků tady, stejně jako čtyři, a já musím sloučit každé z těchto čtyř v, a každé z těchto čtyř v, jeden po druhém tak, že nakonec Mám osm prvků. Vypadá to, že to je velká o n kroků? Jestliže mám n prstů a každý z jim musí být sloučeny do místa, to je jako další n kroků. 

Takže opravdu formulaically, můžeme vyjádřit to, i když trochu děsivě zprvu pohled, ale je to něco který zachycuje přesně tuto logiku. Doba běhu, T n, n IF je větší než nebo rovno 2. V tomto případě, ELSE případě je T n děleno 2 plus T n děleno 2, a velký o n, některé lineární počet kroků, možná přesně n, možná 2 krát n, ale je to zhruba, pořadí n. Tak to také, je to, jak můžeme to vyjádřit formulaically. Teď už by neznal, pokud to není které jste nahráli ve své mysli, nebo hledat to v zadní učebnice, že může mít trochu cheat sheet na konci, ale to je opravdu jít do nám velkou o n log n, protože opakování, že vidíte tady na obrazovce, pokud jste vlastně dělal to, s nekonečný počet příkladů, nebo jste to udělal formulaically, že ne vidět, že to, protože tento vzorec sám o sobě je rekurzivní, s t n nad něčím na pravé straně, a t o n přes na levé straně, to může ve skutečnosti být vyjádřeno, v konečném důsledku, jak velký go n log n. Pokud tomu tak není přesvědčen o tom, že je to pokuta pro tuto chvíli, jen vzít na víře, že to je, opravdu, co to vede k opakování, ale to je jen trochu více matematický přístup k dívá v běžící době merge sort na základě svého pseudokódu sám. 

Nyní se pojďme trochu průduch z všechno, a vzít podívat se na jistý bývalý senátor, který může vypadat trochu povědomý, kdo si sedl s Google Eric Schmidt, před časem, na pohovor na pódiu, v přední části celá parta lidí, mluví nakonec o téma, to je docela teď povědomý. Pojďme se podívat. 

Eric Schmidt: Nyní Senator, jsi tady na Google, a já jsem rád myslet na Předsednictví jako pracovní pohovor. Teď je těžké sehnat práci jako prezident. Prezident Obama: Správně. Eric Schmidt: A ty jsi dělat [neslyšitelný] teď. Je také těžké získat práci ve společnosti Google. Prezident Obama: Správně. 

Eric Schmidt: Máme dotazy, a žádáme naše kandidáty otázky, a tohle je od Larry Schwimmer. 

Prezident Obama: OK. 

Eric Schmidt: Co? Myslíte si dělám legraci? Je to přímo tady. Jaký je nejúčinnější způsob, jak třídit milion 32 bit celé číslo? 

Prezident Obama: Well-- Eric Schmidt: Někdy Možná mi to líto, maybe-- Prezident Obama: Ne, ne, Ne, ne, ne, já think-- Eric Schmidt: To není to-- Prezident Obama: Já myslím, myslím, že bublinu sort by byl špatný způsob, jak jít. Eric Schmidt: Pojď. Kdo mu to řekl? DOBŘE. Nechtěl jsem počítač věda on-- 

Prezident Obama: Máme dostal své špehy tam. Profesor: Dobře. Nechme za námi nyní teoretický svět algoritmů v asymptotické analýze této smlouvy, a vrátit se do některá témata týden od nuly do jedné, a začátek odstranit některé kolečka, chcete-li. Aby jste opravdu pochopit, nakonec od základů, co je děje pod kapotou, když vás psát, kompilovat a spouštět programy. Připomeňme, a zejména, že je to První program v jazyce C jsme se na, kanonický, jednoduchý program druhů, relativně vzato, kde, vytiskne, Hello World. A Vzpomínám si, že jsem řekl, proces že zdrojový kód prochází je přesně to. Berete zdrojového kódu, projít to přes kompilátor, jako je Clang, a ven vychází strojový kód, který může vypadat takhle, nul a jedniček že procesor počítače, centrální procesorová jednotka nebo mozku, nakonec chápe. 

Ukázalo se, že je to bit jako zjednodušující, že jsme nyní v Postoj k šprýmaři odděleně pochopit, co to opravdu bylo děje pod kapotou pokaždé, když spustíte Clang, nebo obecněji, pokaždé, když program, pomocí funkce Provést a CF 50 IDE. Zejména, věci jako to je nejprve generován, při prvním kompilaci programu. Jinými slovy, když vás vezměte si zdrojový kód a zkompilovat, co je nejprve bytí výstupu by Clang je něco, co znám jako assembleru. A ve skutečnosti, to vypadá přesně jako to. 

Běžel jsem příkaz u příkazového řádku dříve. Řinčet DASH velkým S hello.c, a to vytvořili soubor pro mě volal hello.s, uvnitř které byly přesně tyto obsahy, a trochu více výše a trochu níže, ale já jsem dal nejšťavnatější Informace zde na obrazovce. A když se podíváte pozorně, uvidíte, alespoň několik známých klíčová slova. Máme hlavní nahoře. Máme printf dole uprostřed. A máme také hello world zpětné lomítko n v uvozovkách dole. 

A všechno ostatní tady je návod na velmi nízké úrovni že procesor počítače rozumí. Pokyny pro CPU, které se pohybují paměť kolem, že zatížení struny z paměti, a nakonec, tisk věci na obrazovce. Teď, co se stane, když po Tato sestava kód je generován? Nakonec, to uděláte, opravdu, ještě tvořit objektový kód. Ale kroky, které mají opravdu se děje pod kapotou vypadat trochu víc jako je tento. Zdrojový kód se stává kód assembleru, který se pak stává kód objektu, a operativní pojmy jsou to, při kompilaci zdrojového kódu, out přijde kód montáž, a pak když si sestavit svou assembleru, out přijde objektový kód. 

Nyní Clang je super sofistikované, jako hodně překladačů, a to dělá všechny tyto kroky dohromady, a to není nezbytně Výstup jakýkoli meziprodukt soubory, které můžete dokonce vidět. Prostě kompiluje věci, což je obecný pojem, který popisuje celý tento proces. Ale pokud opravdu chcete být konkrétní, je tu mnohem více děje i tam. 

Ale pojďme se také zvážit, že i teď že mimořádně jednoduchý program, hello.c, nazývá funkce. Vyzvala printf. Ale já jsem nepsal printf, opravdu, který je dodáván s c, abych tak řekl. Je to funkce, připomeňme, že je to deklarován ve standardním io.h, který je soubor záhlaví, který je téma, budeme vlastně ponořit do větší hloubky, než dlouhý. Ale hlavičkový soubor je obvykle doprovázené souborem kódu, zdrojový kód souboru, takže stejně jako existuje standardní io.h. 

Před nějakým časem, někdo, nebo něčí, také psal soubor s názvem standardní io.c, v niž je skutečný definice, nebo implementace printf, a trsy dalších funkcí, jsou ve skutečnosti v písemné formě. Takže vzhledem k tomu, že, pokud vezmeme v úvahu s tady na levé straně, hello.c, že ​​když sestavovány, nám dává hello.s, i když Clang netrápí úspory v místě můžeme vidět, a že kód shromáždění dostane sestaveny do hello.o, který je, opravdu, výchozí název vzhledem k tomu, kdykoli budete kompilovat zdroje kód do objektového kódu, ale nejsou zcela připraven jej vykonat ještě, protože další krok se musí stát, a má dělo v posledních několika týdnů, možná bez vašeho vědomí k vám. 

Konkrétně někde V CS50 IDE, a to, Také bude tak trochu oversimplification na chvíli, tam je, nebo byl na nějaký čas, soubor s názvem standardní io.c, že někdo sestavil do standardní io.s nebo ekvivalent, že někdo pak shromáždil do standardního io.o, nebo se ukáže na A mírně odlišný soubor formát, který může mít jiný příponu souboru úplně, ale v teorii a koncepčně, přesně ty kroky se muselo stát v nějaké formě. Což znamená, že nyní když píšu program, hello.c, že ​​jen říká, hello world, a já jsem s použitím kódu někoho jiného jako printf, který byl kdysi čas, v souboru s názvem standardní io.c, pak nějak musím Take My objektový kód, moji nuly a jedničky, a že osoby objekt kódu nebo nuly a jedničky, a nějak spojit je do jeden poslední soubor, nazvaný ahoj, že má všechny nul a ty z mé hlavní funkci, a všechny nul a ty pro printf. 

A opravdu, že poslední proces je volal, spojující vaše objektový kód. Jehož výstup je spustitelný soubor. Takže ve spravedlnost, u konec dne, nic změnilo od týdne jedna, když jsme První začal sestavování programů. Ve skutečnosti, je to vše děje pod kapotou, ale teď jsme v situaci, kde můžeme skutečně šprýmaři odděleně tyto jednotlivé kroky. A skutečně, na konci dne, jsme pořád odešel s nul a jedniček, které je skutečně skvělý segue nyní na jiné schopnosti C, která jsme neměli využívat největší pravděpodobností k dnešnímu dni, známý jako operátory bitové. Jinými slovy, tak daleko, kdykoliv máme zabýval s daty v C nebo proměnných v C, jsme měli věci, jako znaky a plováky a ins a touží a dvoulůžkové a podobně, ale všechny z nich jsou nejméně osm bitů. My jsme ještě nikdy nebyl schopen manipulovat s jednotlivými bity, i když individuální bitu, jsme Víte, mohou představovat 0 a 1. Nyní se ukazuje, že v C, vy mohou získat přístup k jednotlivých bitů, pokud víte, syntaxi, s nimiž se dostat na ně. 

Takže pojďme se podívat na operátory bitové. Tak tady na snímku je několik symboly, které jsme se, druh, druh, předtím neviděl. Vidím ampersand, vertikální bar, a některé další, stejně, a připomněla, že ampersand ampersand je něco, co jsme neviděli. Logická AND operátor, kde musíte dva z nich společně, nebo logické OR operátor, kde na vás mají dva svislé pruhy. Bitové operátory, které budeme viz fungují na bity jednotlivě, stačí použít jeden ampersand, je single svislá čára, stříška symbol přijde příště, malý vlnovky, a pak doleva držák levý držák, nebo pravá závorka pravá závorka. Každý z nich má různé významy. 

Ve skutečnosti, pojďme se podívat. Pojďme stará škola dnes, a použití dotyková obrazovka z dávných dob, známý jako bílou tabuli. A to bílé tabule bude nám neumožňuje, vyjadřovat některé docela jednoduché symboly, nebo spíše některé poměrně jednoduché vzorce, že se pak můžeme nakonec pákový efekt, za účelem individuální přístup bity v rámci programu C. Jinými slovy, jdeme na to. Let první mluvit Aby moment o ampersand, což je bitové operace AND operátor. Jinými slovy, je to operátor, který umožňuje abych si levostranné proměnné typicky, a pravá variabilní, nebo individuální hodnotu, že pokud budeme A je dohromady, mi dává konečný výsledek. Tak co mám na mysli? Je-li v programu, máte proměnnou , který ukládá jednu z těchto hodnot, nebo řekněme, aby to jednoduché, a jen vypsat nulami a jedničkami jednotlivě, Zde je návod, jak operátor ampersand funguje. 0 ampersand 0 se bude rovnat 0. Teď proč je tomu tak? 

Je to velmi podobné Boolean výrazy, že jsme diskutovali doposud. Pokud si myslíte, že po tom všem, 0 false, 0 je false, false false je, jak jsme diskutovali logicky, také falešné. Tak dostaneme 0 i zde. Pokud budete mít 0 ampersand 1, dobře, že taky, bude být 0, protože pro tento levá exprese aby to byla pravda nebo 1, to by musela být pravdivá a pravdivá. Ale tady máme false a pravdivé, nebo 0 a 1. A teď zase, máme-li 1 ampersand 0, to také bude 0, a pokud budeme mít 1 ampersand 1, Nakonec to máme 1 bit. Takže jinými slovy, my neděláme něco zajímavého s tímto operátorem ještě ne, tento operátor ampersand. Je to bitové operace AND operátor. Ale to jsou ingredience přes který můžeme udělat zajímavých věcí, jak brzy uvidíme. 

Nyní se pojďme podívat na právě jeden svislá čára tady na pravé straně. Pokud mám 0 bit a I NEBO to s, bitové OR operátor, další 0 bit, , co se děje, aby mi 0. Pokud bych se trochu 0 a nebo to s 1 bit, a pak budu mít 1. A ve skutečnosti, jen pro jasnost, nech mě jít zpátky, takže moje svislé pruhy nejsou splést 1 je. Dovolte mi, abych přepsat všechny můj 1 je trochu více Je zřejmé, že tak, že vedle vidět, je-li I mají 1 nebo 0, že to bude 1, a když mám 1 nebo 1, která, Také bude 1. Takže můžete vidět, že logicky OR operátor se chová velmi odlišně. To mi dává 0 nebo 0 mi dává 0, ale každá jiná kombinace mi dává 1. Tak dlouho, jak budu mít jeden 1 V vzorec, výsledek bude 1. 

Na rozdíl od AND operátor, ampersand, pouze tehdy, když mám dvě 1 je v rovnice, mohu skutečně dostat do vedení 1 out. Teď je tu několik dalších Provozovatelé stejně. Jedním z nich je trochu více zapojit. Tak nech mě jít dopředu a vymazat to, aby se uvolnily nějaké místo. A pojďme se podívat na stříška symbol, jen na chvíli. Toto je typicky znak můžete zadat na klávesnici SHIFT a pak jedno z čísel na vrcholku vaší USA klávesnice. 

Tak tohle je exkluzivní OR operátor, exclusive OR. Takže jsme právě viděli provozovatelem nebo. Toto je exkluzivní OR operátor. Jaký je vlastně rozdíl? Tak pojďme stačí se podívat na vzorec, a použít jako přísady v konečném důsledku. 0 XOR 0. Já jsem chtěl říct, je vždy 0. To je definice XOR. 0 XOR 1 bude 1. 1 XOR 0 bude 1, a 1 XOR 1 bude? Špatné? Nebo ne? Nevím. 0. A teď, co se tady děje? No přemýšlet o název tohoto operátora. Exkluzivní OR, tak jak jméno, druh, naznačuje, odpověď bude pouze 1, pokud vstupy jsou exkluzivní, výhradně různé. Tak tady vstupy jsou stejné, takže na výstupu je 0. Zde vstupy jsou stejné, takže na výstupu je 0. Zde jsou výstupy jsou odlišné, jsou exkluzivní, a tak výstup je 1. Takže je to velmi podobné A je to velmi podobné, nebo spíše je to velmi podobné OR, ale pouze v exkluzivním způsobem. Tato je již není 1, protože máme dvě 1 je, a ne výlučně, jen jeden z nich. Dobře. A co ostatní? No tilda, zatím, je skutečně pěkný a jednoduchý, naštěstí. A to je unární operátor, což znamená, že to je aplikován pouze na jeden vstup, jedním operand, abych tak řekl. Není na levé a pravé. Jinými slovy, pokud budete mít na vlnovku 0, odpověď bude opačný. A pokud budete mít vlnovky z 1, odpověď bude naopak. Takže tilda provozovatel způsob, jak negování trochu, nebo obracející kousek od 0-1, nebo od 1 do 0 ° C. 

A to nás nechává konečně s pouhými dvěma konečnými operátory, tzv doleva posun, a takzvaný doprava operátor posunu. Pojďme se podívat na to, jak této práci. Provozovatel vlevo posun, psaný se dvěma lomených závorkách, jako je to, pracuje následovně. Pokud je můj vstup, nebo má operand, vlevo operátor posun je jednoduše 1. A já pak říci počítače na je vlevo posun, že 1, řekněme sedm míst, Výsledkem je, jako bych přijmout, že 1, a přesunout ji sedm míst, více než na vlevo, a ve výchozím nastavení, budeme předpokládat, že prostor na pravé straně se bude ořezán nulami. Jinými slovy, 1 učinilo posun 7 se děje aby mi, že 1, následovaný 1, 2, 3, 4, 5, 6, 7 nuly. Takže svým způsobem to vám umožní trvat malé množství jako 1, a jasně, aby to hodně mnohem, mnohem větší, tímto způsobem, ale my jsme vlastně bude vidět chytřejší přístupy k ní místo toho, jakož i, 

Dobře. To je pro tři týden. Uvidíme se příště. To bylo CS50. 

[Přehrávání hudby] 

Reproduktor 1: On byl u občerstvení bar jíst hot fudge pohár. Měl to všechno přes obličej. Má na sobě, že čokoláda jako vousy SPEAKER 2: Co to děláš? SPEAKER 3: Hmmm? Cože? 

SPEAKER 2: Věděli jste právě double dip? Ty double ponořil čipu. SPEAKER 3: Promiňte. SPEAKER 2: ponořil jste čip, budete vzal sousto, a znovu ponořil. SPEAKER 3: SPEAKER 2: Takže to je jako dávat Celá vaše ústa přímo v dip. Příště budete mít čip, ponořit jen jednou, a nakonec to. 

SPEAKER 3: Víš co, Dane? Můžete ponořit způsob, jakým chcete ponořit. Budu ponořit způsob, jakým chci ponořit.