[Prehrávanie hudby] 

Profesor: Dobre. To je CS50, a to je koncom tretieho týždňa. Tak sme tu dnes, nie v Sanders Divadlo, namiesto toho v Weidner knižnici. Vnútri čo je štúdio známy ako Hauser Studio, alebo povedzme Studio H, alebo musí my say-- ak sa vám to páčilo ten vtip, je to vlastne z spolužiak, Mark, online, ktorý navrhol toľko cez Twitter. Teraz, čo je v pohode tu v štúdiu je, že som obklopený týchto zelených múry, zelené obrazovky alebo chromakey, tak povediac, čo znamená, že je CS50 Inscenačné tím unbeknownst mne práve teraz, môže byť uvedenie Najviac ma kdekoľvek na svete, k lepšiemu alebo k horšiemu. 

Teraz, čo je pred nami, nastavte problém dva je vo vašich rukách pre tento týždeň, ale s problémom set Tri tento nadchádzajúci týždeň, budete mať za úlohu s tzv hra 15, starý strana láskavosť, že môžete pripomenúť príjem ako dieťa, ktorý má veľa čísel, ktorá môže kĺzať hore, dole, vľavo a vpravo, a je tu ešte jedna medzera v rámci skladačky, do ktorého ste môže skutočne posunúť tie dielikov. Nakoniec dostanete tento puzzle v nejakom semifinále náhodnom poradí, a cieľom je, aby triediť to, zhora dole, zľava doprava, z jednej celú cestu hore cez 15. 

Bohužiaľ, implementácia budete mať po ruke bude softvér na báze, nie je fyzicky. Tie vlastne bude musieť písať kód, pomocou ktorého študent alebo Užívateľ môže hrať hru 15. A v skutočnosti, v hacker vydania hry 15, budete výzvou realizovať, nie len hranie tejto starej školy hra, ale skôr riešenie o tom, ktorou sa vykonáva nesmrteľnosť, aby som tak povedal, že v skutočnosti rieši puzzle pre človeka, tým, že im s nádychom, po náznaku, po náznakom. Takže o tom až budúci týždeň. Ale to je to, čo nás čaká. 

Pre túto chvíľu pripomenúť, že začiatkom tohto týždňa sme mali tento Cliffhanger, ak chcete, pričom najlepšie, čo sme robili triedenie múdry bola horná hranica veľkého o n na druhú. Inými slovami, bublinkové radenie, výber triedenie, insertion sort, všetky z nich, zatiaľ čo iné pri ich vykonávaní, prešiel do n druhú spustenie Čas vo veľmi najhoršom prípade. A my všeobecne predpokladajú, že úplne najhoršom prípade pre triedenie je ten, ktorý vaše vstupy sú úplne dozadu. A skutočne, to trvalo pomerne málo krokov na vykonávanie každej z týchto algoritmov. 

Teraz na samom konci triedy Pripomeňme, porovnali sme bublinkové triedenie proti výberu druhu proti jednému iný že sme nazvali merge sort v tej dobe, a navrhujem, aby to trvá Výhodou lekciu od týždňa nula, rozdeľ a panuj. A nejako dosiahnuť nejaký druh logaritmické doba chodu nakoniec, miesto niečoho to je čisto kvadratická. A nie je to úplne logaritmickej, je to trochu viac než to. Ale ak si spomínate z triedy, to bolo oveľa, oveľa rýchlejšie. Poďme sa pozrieť, kde sme prestali. 

Bubble sort proti výberu triediť proti zlúčeniu druhu. Teraz sú všetci beží, v teórie, v rovnakom čase. CPU beží rovnakou rýchlosťou. Ale môžete cítiť, ako to nuda sa veľmi rýchlo stane, a len ako rýchlo, keď sme injekciu trochu týždni nula je algoritmov, môžeme veci urýchliť. 

Takže značka nejako vyzerá úžasne. Ako môžeme využiť ju, aby rýchlejšie zoradiť čísel. Tak poďme spomeniem na zložky, ktoré sme mala už v týždni nula, to hľadať niekoho, kto sa v telefónnom zozname, a pripomenul, že pseudokód, že sme navrhli, cez ktorý môžeme nájsť niekto ako Mike Smith, vyzeral trochu niečo také. 

Teraz sa pozrite predovšetkým na riadku 7 a 8, a 10 a 11, ktorý prinútiť ho slučky, čím sme ponechali ísť späť do riadku 3 znovu a znovu, a znovu. Ale ukazuje sa, že môžeme zobraziť Tento algoritmus, tu v pseudokódu, trochu viac holisticky. V skutočnosti to, čo som hľadal v tu na obrazovke, je algoritmus pre vyhľadávanie Mike Smith medzi niektorými sady stránok. A skutočne, môžeme zjednodušiť tento algoritmus v týchto bodov 7 a 8, a 10 a 11 len povedať to, ktorý som tu uvedená v žltej. Inými slovami, v prípade, Mike Smith je skôr v knihe, nepotrebujeme špecifikovať krok za krokom, teraz, ako ho nájsť. Nemáme špecifikovať sa vrátiť do riadku 3, prečo nie my len miesto, povedzme, všeobecnejšie, hľadať Mike v Ľavá polovica knihy. 

Naopak, pokiaľ je Mike v skutočnosti neskôr v knihe, prečo nie my len citovať koniec citátu hľadanie Mike v pravej polovici knihy. Inými slovami, prečo nie my len druh pramici na seba hovorí, hľadať Mike v tejto podmnožina knihy, a nechajte to na naše existujúce algoritmus, aby nám povedali ako hľadať Mike v že ľavá polovica knihy. Inými slovami, naša algoritmus pracuje či už je to telefónny zoznam tejto sily, z toho Hrúbka, alebo akejkoľvek hrúbky vôbec. Takže môžeme rekurzívne definovať tento algoritmus. Inými slovami, na Obrazovka tu, je algoritmus pre vyhľadávanie Mike Smith Medzi stránkami telefónneho zoznamu. Takže v riadku 7 a 10, poďme len povedať, že presne. A ja používať tento termín na chvíľu Pred, a naozaj, rekurzia je módne slovo pre túto chvíľu, a to je tento proces robiť niečo, čo by nejako cyklické pomocou kódu, ktorý už máte, a znovu volá, a znova a znova. Teraz to bude dôležité, že sme sa nejako dno out, a nerobte to nekonečne dlho. V opačnom prípade budeme majú naozaj nekonečnej slučke. Ale poďme sa pozrieť, či môžeme požičať túto myšlienku z rekurzie, zase niečo a znovu a znovu, riešiť triedenie problém cez zlúčenie triediť, tým efektívnejšie. 

Takže dávam zlúčenie triediť. Poďme sa pozrieť. Takže tu je pseudokód, s ktoré sme mohli vykonávať triedenie, Pomocou tohto algoritmu s názvom merge sort. A je to celkom jednoducho to. Na vstupe n elementy, Inými slovami, ak ste vzhľadom k tomu, n prvky a čísla a listy alebo čo je vstup, ak ste dal n elementy, pokiaľ n je menší ako 2, len sa vrátiť. Je to tak? Vzhľadom k tomu, ak n je menšia ako 2, ktoré Znamená to, že môj zoznam prvkov je buď o veľkosti 0 alebo 1, a V oboch týchto prípadoch triviálne, zoznam už je zoradený. Ak nie je k dispozícii zoznam, je to triediť. A ak tam je zoznam dĺžky 1, je to samozrejme triediť. Takže algoritmus len potrebuje naozaj niečo zaujímavé, ak budeme mať dva alebo viac prvky nám daná. Takže poďme sa pozrieť na mágiu potom. Else zoradiť ľavej polovice prvkov, potom triediť pravú polovicu prvkov, potom zlúčiť zotriedené polovice. A čo je druh mysli ohýbanie tu je, že naozaj nemám Zdá sa, že vám povedal, niečo ešte nie, že jo? Všetko, čo som povedal, je, dostane zoznam n prvkov, triediť ľavú polovicu, potom pravé polovice, potom zlúčiť zoradené polovice, ale tam, kde je skutočný tajný recept? Kde je algoritmus? No, ukázalo sa, že tých dvoch liniek Prvý, druh ľavej polovici prvkov, a druh pravá polovica prvkov, sú rekurzívne volanie, aby som tak povedal. 

Koniec koncov, na to bod v čase, musím algoritmus, s ktorým zoradiť veľa prvkov? Áno. Je to priamo tu. Je to priamo tu na obrazovke, a takže môžem použiť ten rovnaký súbor krokov triediť ľavú polovicu, ako môžem pravá polovica. A skutočne, znovu a znovu. Takže tak či onak, a my čoskoro vidieť, kúzlo zlúčenie druhu je zakotvený v tom, že veľmi konečný linka, zlučovanie triedených polovice. A to sa zdá byť pomerne intuitívne. Budete mať dve polovice, a tí, nejako, spojiť ich dohromady, a my budeme vidieť konkrétne za chvíľu. 

Ale to je kompletný algoritmus. A pozrime sa, prečo. Tak predpokladám, že sme vzhľadom k tie isté Osem prvky tu na obrazovke, jeden cez osem, ale sú v zdanlivo náhodnom poradí. A cieľ je na dosah ruky triediť tieto prvky. Tak ako môžem ísť o robí použitie, znovu, merge sort, ako na tento pseudokódu? A opäť, farbiť to v vaša myseľ, len na chvíľu. V prvom prípade je dosť triviálne, ak je to menej ako 2, len vrátiť, nie je práce je potrebné urobiť. Takže naozaj tam je len tri kroky k naozaj mať na pamäti. Znovu a znovu, ja som bude chcieť mať triediť ľavú polovicu, triediť pravú polovicu, a potom ešte raz ich dve polovice sú radené, Chcem je zlúčiť dohromady do jedného zoradení zoznamu. Takže majte na pamäti, že. 

Tak tu je pôvodný zoznam. Poďme sa touto ako pole, ako sme začali v dvoch týždni, čo je súvislý blok pamäte. V tomto prípade, ktorý obsahuje osem Čísla, chrbtom k sebe k sebe. A poďme sa teraz vzťahujú merge sort. Tak som sa prvýkrát chcete zoradiť ľavá polovica tohto zoznamu, a poďme sa teda, zamerať sa na 4, 8, 6, a 2. 

Teraz, ako mám ísť o radenie zoznamu veľkosti 4? No musím teraz považujú triedenie vľavo od ľavej polovice. Opäť platí, poďme vzad len na chvíľu. V prípade, že je to pseudokód, a ja som dal osem elementov, 8 je samozrejme väčšia, než alebo rovný 2. A tak sa o prvý prípad, neuplatňuje. Takže triediť osem elementov, som prvýkrát radiť ľavú polovicu prvkov, Potom som zoradiť pravú polovicu, potom som sa zlúčiť obe zoradená polovice, každá o veľkosti 4. OK. 

Ale ak ste práve mi povedal, Roztieďte ľavá polovica, ktorá je teraz o veľkosti 4, ako mám triediť ľavú polovicu? No, ak mám vstup zo štyroch prvkov, Prvýkrát som radiť ľavú dvoch a potom pravé dva, a potom som sa spojiť ich dohromady. Takže znovu, to sa stáva trochu na mysli ohýbanie hru tu, Pretože tie, druh, musí spomenúť, kde ste v príbehu, ale na konci dňa, vzhľadom k tomu, ľubovoľný počet prvkov, najprv chcete triediť ľavá polovica, potom pravá polovica, potom spojiť ich dohromady. Poďme začať robiť presne to. Tu je vstup z ôsmich prvkov. Teraz sa pozeráme na ľavej polovici tu. Ako mám triediť štyri prvky? Tak som najprv zoradiť ľavej polovice. Teraz, ako sa môžem radiť ľavú polovicu? No ja som dostal dva prvky. Takže poďme zoradiť tieto dva prvky. 2 je väčší alebo rovné 2, samozrejme. Tak, že prvý prípad nevzťahuje. 

Takže som teraz musí triediť ľavú polovica z týchto dvoch prvkov. Ľavá polovica, samozrejme, je len 4. Tak ako mám zoradiť zoznam z jedného prvku? Tak a teraz, že zvláštne referenčné prípad up vrchole, aby som tak povedal, platí. 1 je menšia ako 2, a my Zoznam je skutočne o veľkosti 1. Tak som sa vrátiť. Ja nerobím nič. A skutočne, pozerať sa na to, čo som urobil, 4 už je zoradený. Ako by som už čiastočne úspešné tu. 

Teraz sa zdá, že trochu hlúpy nároku, ale je to pravda. 4 je uvedený zoznam veľkosti 1. Je to už je zoradený. To je ľavá polovica. Teraz som radiť pravú polovicu. Môj vstup je jedným z prvkov, 8 podobne, už zoradené. Hlúpy, taky, ale opäť, Tento základný princíp bude nám umožní si teraz budujú v hornej časti tejto úspešne. 4 radené, 8 je triedený, teraz čo to bolo posledný krok? Takže tretí a posledný krok, akýkoľvek Čas, ktorý sa triedenie zoznamu, odvolanie, bolo zlúčiť dve polovice, ľavý a pravý. Takže poďme urobiť presne to. Má ľavá polovica je, samozrejme, 4. Moja pravá polovica je 8. 

Tak ideme na to. Najprv budem prideliť niektoré ďalšie pamäť, že budem reprezentovať tu, len ako sekundárny poľa, to je dosť veľký, aby sa zmestili to. Ale môžete si predstaviť rozšírenie že obdĺžnik po celej dĺžke, ak budeme potrebovať viac neskôr. Ako môžem zaobstarať 4 a 8, a zlúčiť tieto dva zoznamy veľkosti 1 spolu? Aj tu celkom jednoduché. 4 je na prvom mieste, potom príde 8. Pretože ak chcem na triedite ľavá polovica, potom pravá polovica, a potom zlúčiť tieto dve polovice spoločne, v zoradení poradí, 4 je na prvom mieste, potom príde 8. 

Takže sa zdá, že bude robiť pokroky, a to aj aj keď som neurobil žiadnu skutočnú prácu. Ale pamätajte, kde sme v príbehu. Pôvodne sme vzali osem prvkov. Vyriešili sme ľavú polovicu, čo je 4. Potom sme radené ľavú polovicu z ľavej polovice, ktorý bol 2. A je to tu. Sme skončili s týmto krokom. 

Takže ak sme triedi ľavej polovice 2, teraz sme majú triediť pravú polovicu 2. Takže pravá polovica 2 je Tieto dve hodnoty tu, 6 a 2. Takže poďme sa teraz vstup veľkosti 2, a triediť ľavú polovicu, a potom pravú polovicu, a potom zlúčiť dohromady. Tak ako mám zoradiť zoznam veľkosti 1, ktorý obsahuje len číslo 6? Ja som už skončil. Tento zoznam o veľkosti 1 je zoradený. 

Ako môžem vyriešiť ďalší zoznam veľkosť 1, tzv pravá polovica. No to, tiež, už je zoradený. Číslo 2 je sám. Takže teraz mám dve polovice, vľavo a Dobre, je potrebné ich zlúčiť dohromady. Dovoľte mi aby som si nejaké extra priestor. A dal 2 tam, potom 6 tam, čím triedenie tohto zoznamu, vľavo a vpravo, a zlučovanie spoločne, nakoniec. Takže ja som v trochu lepšom stave. Ja som neskončil, pretože jasne 4, 8, 2, 6 nie je konečný, ktoré nariaďuje chcem. Ale teraz mám dva zoznamy veľkosti 2, že majú obaja, v danom poradí, boli zoradené. Takže teraz, ak pretočíte vo vašej mysli oko, kde sa to pre nás znamená? Začal som s ôsmimi prvkov, potom som orezaný dole do ľavej polovice 4, potom ľavú časť 2, a potom je pravá polovica 2, Som skončil, a preto, triedenie ľavý polovice 2, a v pravej polovici 2, takže to, čo je tu tretí a posledný krok? Musím sa spojiť dohromady dva zoznamy veľkosti 2. Tak poďme do toho. A na obrazovke sa tu, daj mi niektoré ďalšie pamäť, hoci technicky, všimnite si, že som dostal veľa prázdne miesto na začiatok tam. Ak chcem byť obzvlášť efektívna priestor múdry, Mohol by som dať do pohybu prvky tam a späť, hore a dole. Ale len pre vizuálnu jasnosť, Chystám sa dať to dole, udržať veci pekné a čisté. 

Tak som dostal dva zoznamy veľkosti 2. Prvý zoznam má 4 a 8. Druhý zoznam obsahuje 2 a 6. Poďme zlúčiť tie spolu v zoradení poradí. 2, samozrejme, je na prvom mieste, potom 4, potom 6, potom 8. A teraz sa zdá, že sa dostať niekde zaujímavé. Teraz som radené polovica vypísať, a zhodou okolností je to všetky párne čísla, ale že je naozaj len náhoda. A teraz si radené ľavý polovica, tak, že to je 2, 4, 6 a 8. Nič nie je mimo prevádzku. To sa cíti ako pokrok. 

Teraz to vyzerá, som bol teraz hovorí navždy, Takže to, čo zostáva byť videný ak toto algoritmus je skutočne efektívnejšie. Ale my prechádzame to výborný metodicky. Počítač, samozrejme, by som to takto. Tak kde to sme? Začali sme s ôsmimi prvkov. Radené som ľavú polovicu 4. Zdá sa mi, je potrebné urobiť s tým. Takže teraz je ďalším krokom k triediť pravú polovicu 4. A táto časť môžeme ísť cez trochu viac rýchlo, aj keď ste Vítame Vás na vzad alebo pozastaviť, len myslíte, že cez to na svojím vlastným tempom, ale to, čo teraz máme, je príležitosť robiť presne rovnaký algoritmus na štyroch rôzne čísla. 

Tak poďme do toho, a zamerať sa na pravá polovica, ktorý sme tu. Ľavá polovica, ktorá pravú polovicu, a teraz Ľavá polovica vľavo polovica z tej pravej polovice, a ako zoradiť zoznam veľkosti 1 obsahujúcej iba číslo 1? Už sa stalo. Ako to mám urobiť to isté pre zoznam o veľkosti 1, ktorý obsahuje len 7? Už sa stalo. Tretí krok pre toto je polovica je zlúčiť tieto dva prvky do nového zoznamu veľkosti 2, 1 a 7. Nezdá sa, že urobili všetko že veľa zaujímavá práca. Pozrime sa, čo sa bude diať ďalej. Len som radené do ľavej polovice pravá polovica môjho pôvodného vstupu. Teraz poďme zoradiť právo polovica, ktorá obsahuje 5 a 3. Poďme sa znovu pozrieť na ľavej strane polovica, triedia, pravá polovica, triedia, a spojiť tie dva dohromady, do nejakého ďalšieho priestoru, 3 je na prvom mieste, potom príde 5. A tak teraz sme sa triedi Ľavá polovica pravú polovicu z pôvodnej problém, a pravá polovica pravú polovicu z pôvodnej problém. Čo je tretí a posledný krok? No zlúčiť tieto dve polovice dohromady. Tak nech mi, aby som si sám trochu priestor navyše, ale opäť som môže byť pomocou tohto extra priestor na vrchol. Ale budeme držať to jednoduché vizuálne. Dovoľte mi, aby som teraz zlúčiť v 1, a potom 3, a potom 5, a potom 7. Tým ma teraz opúšťa s Pravá polovica pôvodnej problém to je dokonale zoradené. 

Takže to, čo zostane? Mám pocit, ako by som držať hovoriť rovnaké veci znovu a znovu, ale to je odrážajúce Skutočnosť, že sme pomocou rekurzia. Proces za použitia algoritmus znovu a znovu, na menšie podmnožiny pôvodnej problém. Takže som teraz sa ľavý zoradená polovicu pôvodnej problém. Mám právo zoradené polovicu z pôvodnej problém. Čo je tretí a posledný krok? Oh, to je zlúčenie. Takže poďme to urobiť. Poďme prideliť niektoré ďalšie pamäť, ale môj Bože, ju mohol dať teraz kdekoľvek. Máme toľko miesta k dispozícii k nám, ale my budeme držať to jednoduché. Namiesto toho, aby šiel späť a ďalej s našou pôvodnou pamäťou, nech to jednoducho urobiť vizuálne tu dole, aby dokončiť zlúčenie ľavú polovicu a pravá polovica. 

Takže zlúčením, čo musím urobiť? Chcem, aby sa prvky v poradí. Takže pri pohľade na ľavej polovici, Vidím, prvé číslo je 2. Pozerám sa na pravú polovicu, Vidím prvé číslo je 1, tak samozrejme čo Číslo nechcem trhať von, a dal prvý v mojom konečnom zozname? Samozrejme, 1. Teraz chcem položiť túto rovnakú otázku. Na ľavej polovici, som stále číslo 2. Na pravej polovici, Mám číslo 3. Ktorý z nich si chcem vybrať? Samozrejme, že číslo 2 a Teraz si všimnúť kandidátov sú 4 vľavo, 3 vpravo. Poďme sa, samozrejme, vyberte 3. Teraz sú 4 kandidáti na ľavá, 5 na pravej strane. My, samozrejme, vyberte 4. 6 na ľavej strane, 5 vpravo. My, samozrejme, vyberte 5. 6 na ľavej strane, 7 na pravej strane. Vyberáme 6, a potom sme vybrať 7, a potom volíme 8. Voila. 

Tak obrovské množstvo slov neskôr sme majú radené tento zoznam ôsmich prvkov do zoznamu jeden cez osem, ktorý je rastie s každým krokom, ale koľko času urobil trvať nás to urobiť. No som zámerne položenej veci obrazovo tu, takže môžeme druh vidieť alebo oceniť divíziu dobyť, že sa deje. 

V skutočnosti, keď sa pozriete späť na brázde, Nechala som všetky tieto prerušovanou čiarou V držiteľov mieste, môžete, druh, vidieť, v opačnom poradí, ak ste trochu obzrieť v História teraz, môj pôvodný zoznam Je, samozrejme, veľkosti 8. A potom už skôr, som bol zaoberajúce sa dvoma zoznamy veľkosti 4, a potom štyri zoznamy veľkosti 2, a potom osem zoznamy veľkosti 1. 

Takže to, čo robí to, druh, vás upozorní na? No, naozaj, niektoré z algoritmy sme Pozrel sa na tak ďaleko, kde sme rozdeľ a deliť, a rozdeliť, zachovať s veci znova, a opäť vedie v tomto všeobecnom myšlienke. A tak je tu niečo logaritmické tu deje. A nie je to úplne log n, ale tam je logaritmické komponentov k tomu, čo sme práve urobili. 

Teraz sa poďme zvážiť, ako to v skutočnosti je. Takže log n, opäť bol skvelý hrací čas, keď sme urobili niečo ako binárne vyhľadávanie, ako my teraz hovoríme, rozdeľ a panuj stratégie cez ktorý sme našli Mike Smith. Teraz technicky. To je základ log 2 n, a to aj aj keď vo väčšine matematických tried, 10 je zvyčajne bázy, ktorá sa domnievate. Ale počítačoví odborníci takmer vždy myslieť a hovoriť, pokiaľ ide o základni 2, takže sme sa všeobecne stačí povedať záznam n, namiesto toho, log základne 2 n, ale sú to presne jeden a To isté vo svete počítača vedy, a ako stranou, tam je konštantný faktor Rozdiel medzi týmito dvoma, takže je diskutabilné tak ako tak, pre viac formálnych dôvodov. 

Ale teraz, to, čo nás zaujíma o je tento príklad. Takže poďme nedokazuje príkladom, ale v aspoň na jeden príklad z čísel po ruke ako kontrola sanitačného, ​​ak chcete. Takže predtým vzorec bol základ log 2 n, ale to, čo je v tomto prípade n. Mal som n pôvodné čísla, alebo 8 z pôvodného počtu špecificky. Teraz už je to trochu zatiaľ čo, ale som celkom istí, že log základ 2 hodnoty 8 je 3, a naozaj, čo je pekné o ktorý je 3, ktorý je presne počet, koľkokrát že môžete rozdeliť zoznam dĺžky 8 znovu a znovu, a znovu, kým ste odišiel zoznamy iba veľkosti 1. Je to tak? 8 ide do 4, ide do 2, ide k 1, a to je odrazom presne to picture mali sme pred chvíľou. Tak trochu zdravý rozum zistiť, kam logaritmus je vlastne jedná. 

Takže teraz, čo ešte sa tu jedná? n. Takže si všimnúť, že každý Keď som rozdelil zoznamu, aj keď v opačnom poradí v histórii tu, bol som stále robí n veci. Že zlúčenie krok vyžaduje, aby Dotknem každý jeden z čísel, aby to skĺznuť svojím vhodným umiestnením. Takže aj keď je výška tejto diagram je veľkosti log n n alebo 3, špecificky, inými slovami, Urobil som tri divízie sem. Koľko práce som urobil horizontálne pozdĺž tejto tabuľke zakaždým? 

No, ja som n kroky fungovať, pretože ak som dostal štyri elementy a štyri elementy, a musím zlúčiť dohromady. Musím prejsť tieto štyri a tieto štyri, nakoniec zlúčiť späť do ôsmich prvkov. Pokiaľ naopak mám osem prstov tu, čo nechcem, a ôsmich fingers-- sorry-- či som dostal štyri prsty tu ktoré robím, štyri prsty tu, čo robím, potom je to rovnaké Príkladom ako predtým, keď to urobím majú osem prstov aj keď v celkom, ktorý som si, druh, áno. Môžem presne sa tu, potom som si určite zlúčiť všetky z týchto zoznamov o veľkosti 1, spoločne. Ale ja rozhodne sa pozrieť pri každom prvku práve raz. Takže je výška tohto procesu je log n, šírka tohto procesu, aby som tak povedal, je n, takže to, čo sa nám zdá, mať, nakoniec, je bežiaci čas o veľkosti n časy log n. 

Inými slovami, sme rozdelili zoznam, log n-krát, ale zakaždým, keď sme urobili, že sme mali dotknúť každý jeden z prvkov, za účelom ich zlúčenie dohromady, čo n bol krok, takže máme n-krát log n, alebo ako počítačový vedec by povedal, asymptoticky, ktorý by bolo veľké slovo popísať hornej viazané na jazdnej doby, sme sa beží vo veľkom O log n času, aby som tak povedal. 

Teraz je to významné, pretože spomenúť, čo beží časy boli bublinkové druhu, a výber triedenie a vkladanie triedenie, a dokonca aj niekoľko ďalších, ktoré existujú, n štvorcový bolo miesto, kde sme boli na. A môžete, druh, vidieť tu. Ak je na druhú n je samozrejme n krát n, ale tu máme n-krát log n, a my už poznáme z týždňa nula, že log n, logaritmické, je lepšie ako niečo lineárne. Koniec koncov, pripomínajú obraz s červenou a žltou a zelenej linky, ktoré sme vypracovali, tým green logaritmické línia bola oveľa nižšia. A preto, oveľa lepšie a rýchlejšie než rovných žltej a červenej čiary, n-krát log n je skutočne lepšie, než N-krát n, alebo n na druhú. 

Takže sa zdá, že sa identifikoval algoritmus zlúčenie druh, ktorý beží v oveľa rýchlejší, a dokonca, to je dôvod, prečo na začiatku tohto týždňa, kedy sme videli, že súťaž medzi bubliny triedenie, výber triediť, a zlúčiť triedenie, merge sort naozaj, ale naozaj vyhral. A skutočne, sme nemali ani čakať k Bubble druhu a výberu druhu až do konca. 

Teraz sa poďme jeden ďalší priechod na to, ze o niečo viac formálne perspektíva, len v prípad, to rezonuje lepšie než tejto vyššej úrovni diskusie. Takže tu je opäť algoritmus. Poďme sa sami seba opýtať, čo je doba chodu Je to algoritmy rôzne kroky? Poďme rozdeliť ho na prvý púzdro a druhý prípad. IF a iný v prípade, ak, IF n je menší ako 2, len sa vrátiť. Cítim sa ako konštantnom čase. Je to, druh, rovnako ako dvoch krokoch, IF n je menšie ako 2, potom sa vrátite. Ale ako sme si povedali v pondelok, konštantný čas, alebo veľký O 1, môžu byť dve, tri kroky kroky, dokonca aj 1000 krokov. Dôležité je, že je to konštantný počet krokov. Takže žltý zvýraznené pseudocode tu beží v, budeme hovoriť, konštantný čas. Takže viac formálne, a ideme to-- to bude miera, do ktorej formalizovať toto právo now-- T n, bežiaci čas problému že sa n somethings ako vstup, rovná big o jednej, IF n je menšie ako 2. Takže je to podmienené to. Tak aby bolo jasno, keď n je menšia ako 2, máme veľmi krátky zoznam, potom Doba chodu, T n, kde n je 1 alebo 0, v tomto veľmi špecifickom prípade, je to len bude konštantný čas. Bude to trvať jeden krok, dva kroky, čokoľvek. Je to pevne stanovený počet krokov. 

Takže šťavnaté časť musí určite byť v Druhým prípadom v pseudokódu. Prípad ELSE. Triediť ľavú polovicu prvkov, triediť vpravo polovica z prvkov, zlúčiť triedených polovičky. Ako dlho trvá každý z týchto krokov trvať? No, v prípade, že beží čas, aby triediť n prvkov je, nazvime to veľmi všeobecne, T n, potom triedenie ľavú polovica elementov je trochu, ako hovoriť, T n delené 2, a podobne triedenie pravú polovicu prvkov je, druh, ako hovoriť, T n rozdelená 2, a potom zlučovanie zoradené polovice. No, ak mám nejaký počet prvkov tu, rovnako ako štyri, a nejaké číslo prvkov tu, rovnako ako štyri, a ja musím zlúčiť každej z týchto štyroch v, a každé z týchto štyroch v, jeden po druhom tak, že nakoniec Mám osem prvkov. Vyzerá to, že to je veľká o n krokov? Ak mám n prstov a každý z im musia byť zlúčené do miesta, to je ako ďalší n krokov. 

Takže naozaj formulaically, môžeme vyjadriť to, aj keď trochu desivo sprvu pohľad, ale je to niečo ktorý zachytáva presne túto logiku. Doba behu, T n, n IF je väčší alebo rovné 2. V tomto prípade, ELSE prípade je T n deleno 2 plus T n delené 2, a veľký o n, niektoré lineárne počet krokov, možno presne n, možno 2 krát n, ale je to zhruba, poradie n. Tak to tiež, je to, ako môžeme to vyjadriť formulaically. Teraz už by nepoznal, pokiaľ to nie je ktoré ste nahrali vo svojej mysli, alebo hľadať to v zadné učebnice, že môže mať trochu cheat sheet na konci, ale to je naozaj ísť do nám veľkú o n log n, pretože opakovanie, že vidíte tu na obrazovke, ak ste vlastne robil to, s nekonečný počet príkladov, alebo ste to urobil formulaically, že nie vidieť, že to, pretože tento vzorec sám o sebe je rekurzívne, s t n nad niečím na pravej strane, a t o n cez na ľavej strane, to môže v skutočnosti byť vyjadrené, v konečnom dôsledku, ako veľký go n log n. Ak tomu tak nie je presvedčený o tom, že je to pokuta pre túto chvíľu, len vziať na viere, že to je, naozaj, čo to vedie k opakovaniu, ale to je len trochu viac matematický prístup k pozerá v bežiaci dobe merge sort na základe svojho pseudokódu sám. 

Teraz sa poďme trochu prieduch z všetko, a vziať pozrieť sa na istý bývalý senátor, ktorý môže vyzerať trochu povedomý, kto si sadol s Google Eric Schmidt, pred časom, na pohovor na pódiu, v prednej časti celá partia ľudí, hovorí nakoniec o téma, to je celkom teraz povedomý. Poďme sa pozrieť. 

Eric Schmidt: Teraz Senator, si tu na Google, a ja som rád myslieť na Predsedníctvo ako pracovný pohovor. Teraz je ťažké zohnať prácu ako prezident. Prezident Obama: Správne. Eric Schmidt: A ty si robiť [nepočuteľný] teraz. Je tiež ťažké získať prácu v spoločnosti Google. Prezident Obama: Správne. 

Eric Schmidt: Máme otázky, a žiadame našich kandidátov otázky a toto je od Larry Schwimmer. 

Prezident Obama: OK. 

Eric Schmidt: Čo? Myslíte si robím srandu? Je to priamo tu. Aký je najúčinnejší spôsob, ako triediť milión 32 bit celé číslo? 

Prezident Obama: Well-- Eric Schmidt: Niekedy Možno mi to ľúto, maybe-- Prezident Obama: Nie, nie, Nie, nie, nie, ja think-- Eric Schmidt: To nie je to-- Prezident Obama: Ja myslím, myslím, že bublinu sort by bol zlý spôsob, ako ísť. Eric Schmidt: Poď. Kto mu to povedal? OK. Nechcel som počítač veda on-- 

Prezident Obama: Máme dostal svoje špehov tam. Profesor: Dobre. Nechajme za nami teraz teoretický svet algoritmov v asymptotickej analýze tejto zmluvy, a vrátiť sa do niektoré témy týždeň od nuly do jednej, a začiatok odstrániť niektoré kolieska, ak chcete. Aby ste naozaj pochopiť, nakoniec od základov, čo je deje pod kapotou, keď vás písať, kompilovať a spúšťať programy. Pripomeňme, a najmä, že je to Prvý program v jazyku C sme sa na, kánonický, jednoduchý program druhov, relatívne vzaté, kde, vytlačí, Hello World. A Spomínam si, že som povedal, proces že zdrojový kód prechádza je presne to. Beriete zdrojového kódu, prejsť to cez kompilátor, ako je Clang, a von vychádza strojový kód, ktorý môže vyzerať takto, núl a jednotiek že procesor počítača, centrálne procesorová jednotka alebo mozgu, nakoniec chápe. 

Ukázalo sa, že je to bit ako zjednodušujúce, že sme teraz v Postoj k srandista oddelene pochopiť, čo to naozaj bolo deje pod kapotou zakaždým, keď spustíte Clang, alebo všeobecnejšie, zakaždým, keď program, pomocou funkcie Uskutočniť a CF 50 IDE. Najmä, veci ako to je najprv generovaný, pri prvom kompilácii programu. Inými slovami, keď vás vezmite si zdrojový kód a skompilovať, čo je najprv bytia výstupu by Clang je niečo, čo poznám ako assembleri. A v skutočnosti, to vyzerá presne ako to. 

Bežal som príkaz u príkazového riadku skôr. Rinčať DASH veľkým S hello.c, a to vytvorili súbor pre mňa volal hello.s, vnútri ktoré boli presne tieto obsahy, a trochu viac vyššie a trochu nižšie, ale ja som dal nejšťavnatější Informácie tu na obrazovke. A keď sa pozriete pozorne, uvidíte, aspoň niekoľko známych kľúčové slová. Máme hlavné hore. Máme printf dole uprostred. A máme tiež hello world spätné lomítko n v úvodzovkách dole. 

A všetko ostatné tu je návod na veľmi nízkej úrovni že procesor počítača rozumie. Pokyny pre CPU, ktoré sa pohybujú pamäť okolo, že zaťaženie struny z pamäte, a nakoniec, tlač veci na obrazovke. Teraz, čo sa stane, keď po Táto zostava kód je generovaný? Nakoniec, to urobíte, naozaj, ešte tvoriť objektový kód. Ale kroky, ktoré majú naozaj sa deje pod kapotou vyzerať trochu viac ako je tento. Zdrojový kód sa stáva kód assembleri, ktorý sa potom stáva kód objektu, a operatívne pojmy sú to, pri kompilácii zdrojového kódu, out príde kód montáž, a potom keď si zostaviť svoju assembleri, out príde objektový kód. 

Teraz Clang je super sofistikované, ako veľa prekladačov, a to robí všetky tieto kroky dohromady, a to nie je nevyhnutne Výstup akýkoľvek medziprodukt súbory, ktoré môžete dokonca vidieť. Proste kompiluje veci, čo je všeobecný pojem, ktorý opisuje celý tento proces. Ale ak naozaj chcete byť konkrétny, je tu oveľa viac deje aj tam. 

Ale poďme sa tiež zvážiť, že aj teraz že mimoriadne jednoduchý program, hello.c, nazýva funkcie. Vyzvala printf. Ale ja som nepísal printf, naozaj, ktorý je dodávaný s c, aby som tak povedal. Je to funkcia, pripomeňme, že je to deklarovaný v štandardnom IO.H, ktorý je súbor hlavičky, ktorý je téma, budeme vlastne ponoriť do väčšej hĺbky, ako dlhý. Ale hlavičkový súbor je zvyčajne sprevádzané súborom kódu, zdrojový kód súboru, takže rovnako ako existuje štandardná io.h. 

Pred nejakým časom, niekto, alebo niečí, tiež písal súbor s názvom štandardné io.c, v ktorý sú skutočné definície, alebo implementácia printf, a trsy ďalších funkcií, sú v skutočnosti v písomnej forme. Takže vzhľadom k tomu, že, ak vezmeme do úvahy s tu na ľavej strane, hello.c, že ​​keď zostavovať, nám dáva hello.s, aj keď Clang netrápi úspory v mieste môžeme vidieť, a že kód zhromaždenie dostane zostavené do hello.o, ktorý je, naozaj, predvolený názov vzhľadom k tomu, kedykoľvek budete kompilovať zdroje kód do objektového kódu, ale nie sú úplne pripravený vykonať ho ešte, pretože ďalší krok sa musí stať, a má dialo v posledných niekoľkých týždňov, možno bez vášho vedomia k vám. 

Konkrétne niekde V CS50 IDE, a to, Tiež bude tak trochu oversimplification na chvíľu, tam je, alebo bol na nejaký čas, súbor s názvom štandardné io.c, že niekto zostavil do štandardné io.s alebo ekvivalent, že niekto potom zhromaždil do štandardného io.o, alebo sa ukáže na A mierne odlišný súbor formát, ktorý môže mať iný príponu súboru úplne, ale v teórii a koncepčne, presne tie kroky sa muselo stať v nejakej forme. Čo znamená, že teraz keď píšem program, hello.c, že ​​len hovorí, hello world, a ja som s použitím kódu niekoho iného ako printf, ktorý bol kedysi čas, v súbore s názvom štandardné io.c, potom nejako musím Take My objektový kód, moji nuly a jednotky, a že osoby objekt kódu alebo nuly a jednotky, a nejako spojiť ich do jeden posledný súbor, nazvaný ahoj, že má všetky núl a tie z mojej hlavnú funkciu, a všetky núl a tie pre printf. 

A naozaj, že posledný proces je volal, spájajúcej vaše objektový kód. Ktorého výstup je spustiteľný súbor. Takže v spravodlivosť, u koniec dňa, nič zmenilo od týždňa jedna, keď sme Prvý začal zostavovaní programov. V skutočnosti, je to všetko deje pod kapotou, ale teraz sme v situácii, kde môžeme skutočne srandista oddelene tieto jednotlivé kroky. A skutočne, na konci dňa, sme stále odišiel s núl a jednotiek, ktoré je skutočne skvelý segue teraz na iné schopnosti C, ktorá sme nemali využívať najväčšou pravdepodobnosťou k dnešnému dňu, známy ako operátory bitové. Inými slovami, tak ďaleko, kedykoľvek máme zaoberal s dátami v C alebo premenných v C, sme mali veci, ako znaky a plaváky a ins a túžia a dvojlôžkové a podobne, ale všetky z nich sú najmenej osem bitov. My sme ešte nikdy nebol schopný manipulovať s jednotlivými bitmi, aj keď individuálna bitu, sme Viete, môžu predstavovať 0 a 1. Teraz sa ukazuje, že v C, vy môžu získať prístup k jednotlivých bitov, ak viete, syntax, s ktorými sa dostať na ne. 

Takže poďme sa pozrieť na operátorov bitové. Tak tu na snímke je niekoľko symboly, ktoré sme sa, druh, druh, predtým nevidel. Vidím ampersand, vertikálne bar, a niektoré ďalšie, rovnako, a pripomenula, že ampersand ampersand je niečo, čo sme nevideli. Logická AND operátor, kde musíte dvaja z nich spoločne, alebo logické OR operátor, kde na vás majú dva zvislé pruhy. Bitové operátory, ktoré budeme pozri fungujú na bity jednotlivo, stačí použiť jeden ampersand, je single zvislá čiara, strieška symbol príde nabudúce, malý vlnovky, a potom doľava držiak ľavý držiak, alebo pravá zátvorka pravá zátvorka. Každý z nich má rôzne významy. 

V skutočnosti, poďme sa pozrieť. Poďme stará škola dnes, a použitie dotyková obrazovka z dávnych čias, známy ako bielu tabuľu. A to biele tabule bude nám neumožňuje, vyjadrovať niektoré celkom jednoduché symboly, alebo skôr niektoré pomerne jednoduché vzorce, že sa potom môžeme nakoniec pákový efekt, za účelom individuálny prístup bity v rámci programu C. Inými slovami, ideme na to. Rokov prvý hovoriť Aby moment o ampersand, čo je bitové operácie AND operátor. Inými slovami, je to operátor, ktorý umožňuje aby som si ľavostranné premenné typicky, a pravá variabilné, alebo individuálne hodnotu, že ak budeme A je dohromady, mi dáva konečný výsledok. Tak čo mám na mysli? Ak je v programe, máte premennú , Ktorý ukladá jednu z týchto hodnôt, alebo povedzme, aby to jednoduché, a len vypísať nulami a jednotkami jednotlivo, Tu je návod, ako operátor ampersand funguje. 0 ampersand 0 sa bude rovnať 0. Teraz prečo je tomu tak? 

Je to veľmi podobné Boolean výrazy, že sme diskutovali doteraz. Ak si myslíte, že po tom všetkom, 0 false, 0 je false, false false je, ako sme diskutovali logicky, tiež falošné. Tak dostaneme 0 i tu. Ak budete mať 0 ampersand 1, dobre, že taky, bude byť 0, pretože pre tento ľavá expresie aby to bola pravda alebo 1, to by musela byť pravdivá a pravdivá. Ale tu máme false a pravdivé, alebo 0 a 1. A teraz zase, ak máme 1 ampersand 0, to tiež bude 0, a ak budeme mať 1 ampersand 1, Nakoniec to máme 1 bit. Takže inými slovami, my nerobíme niečo zaujímavého s týmto operátorom ešte nie, tento operátor ampersand. Je to bitové operácie AND operátor. Ale to sú ingrediencie cez ktorý môžeme urobiť zaujímavých vecí, ako skoro uvidíme. 

Teraz sa poďme pozrieť na práve jeden zvislá čiara tu na pravej strane. Ak mám 0 bit a I ALEBO to s, bitové OR operátor, ďalší 0 bit, , Čo sa deje, aby mi 0. Ak by som sa trochu 0 a alebo to s 1 bit, a potom budem mať 1. A v skutočnosti, len pre jasnosť, nechaj ma ísť späť, takže moje zvislé pruhy nie sú spliesť 1 je. Dovoľte mi, aby som prepísať všetky môj 1 je trochu viac Je zrejmé, že tak, že vedľa vidieť, ak je I majú 1 alebo 0, že to bude 1, a keď mám 1 alebo 1, ktorá, Tiež bude 1. Takže môžete vidieť, že logicky OR operátor sa chová veľmi odlišne. To mi dáva 0 alebo 0 mi dáva 0, ale každá iná kombinácia mi dáva 1. Tak dlho, ako budem mať jeden 1 V vzorec, výsledok bude 1. 

Na rozdiel od AND operátor, ampersand, iba vtedy, keď mám dve 1 je v rovnice, môžem skutočne dostať do vedenia 1 out. Teraz je tu niekoľko ďalších Prevádzkovatelia rovnako. Jedným z nich je trochu viac zapojiť. Tak nechaj ma ísť dopredu a vymazať to, aby sa uvoľnili nejaké miesto. A poďme sa pozrieť na strieška symbol, len na chvíľu. Toto je typicky znak môžete zadať na klávesnici SHIFT a potom jedno z čísel na vrcholku vašej USA klávesnice. 

Tak toto je exkluzívny OR operátor, exclusive OR. Takže sme práve videli prevádzkovateľom alebo. Toto je exkluzívny OR operátor. Aký je vlastne rozdiel? Tak poďme stačí sa pozrieť na vzorec, a použiť ako prísady v konečnom dôsledku. 0 XOR 0. Ja som chcel povedať, je vždy 0. To je definícia XOR. 0 XOR 1 bude 1. 1 XOR 0 bude 1, a 1 XOR 1 bude? Zlé? Alebo nie? Neviem. 0. A teraz, čo sa tu deje? No premýšľať o názov tohto operátora. Exkluzívny OR, tak ako meno, druh, naznačuje, odpoveď bude iba 1, ak vstupy sú exkluzívne, výhradne rôzne. Tak tu vstupy sú rovnaké, takže na výstupe je 0. Tu vstupy sú rovnaké, takže na výstupe je 0. Tu sú výstupy sú odlišné, sú exkluzívne, a tak výstup je 1. Takže je to veľmi podobné A je to veľmi podobné, alebo skôr je to veľmi podobné OR, ale iba v exkluzívnom spôsobom. Táto je už nie je 1, pretože máme dve 1 je, a nie výlučne, len jeden z nich. Dobre. A čo ostatní? No tilda, zatiaľ, je skutočne pekný a jednoduchý, našťastie. A to je unárne operátor, čo znamená, že to je aplikovaný len na jeden vstup, jedným operand, aby som tak povedal. Nie je na ľavej a pravej. Inými slovami, ak budete mať na vlnovku 0, odpoveď bude opačný. A ak budete mať vlnovky z 1, odpoveď bude naopak. Takže tilda prevádzkovateľ spôsob, ako negovanie trochu, alebo obracející kúsok od 0-1, alebo od 1 do 0 ° C. 

A to nás necháva konečne s iba dvoma konečnými operátormi, tzv doľava posun, a takzvaný doprava operátor posunu. Poďme sa pozrieť na to, ako tejto práci. Prevádzkovateľ vľavo posun, písaný s dvoma lomených zátvorkách, ako je to, pracuje nasledovne. Ak je môj vstup, alebo má operand, vľavo operátor posun je jednoducho 1. A ja potom povedať počítača na je vľavo posun, že 1, povedzme sedem miest, Výsledkom je, ako by som prijať, že 1, a presunúť ju sedem miest, viac ako na vľavo, a v predvolenom nastavení, budeme predpokladať, že priestor na pravej strane sa bude orezaný nulami. Inými slovami, 1 nechalo posun 7 sa deje aby mi, že 1, nasledovaný 1, 2, 3, 4, 5, 6, 7 nuly. Takže svojím spôsobom to vám umožní trvať malé množstvo ako 1, a jasne, aby to veľa oveľa, oveľa väčšie, týmto spôsobom, ale my sme vlastne bude vidieť múdrejší prístupy k nej namiesto toho, ako aj, 

Dobre. To je pre tri týždeň. Uvidíme sa nabudúce. To bolo CS50. 

[Prehrávanie hudby] 

Reproduktor 1: On bol u občerstvenia bar jesť hot fudge pohár. Mal to všetko cez tvár. Má na sebe, že čokoláda ako fúzy SPEAKER 2: Čo to robíš? SPEAKER 3: Hmmm? Čo? 

SPEAKER 2: Vedeli ste práve double dip? Tie double ponoril čipu. SPEAKER 3: Prepáčte. SPEAKER 2: ponoril ste čip, budete vzal sústo, a znovu ponoril. SPEAKER 3: SPEAKER 2: Takže to je ako dávať Celá vaše ústa priamo v dip. Nabudúce budete mať čip, ponoriť len raz, a nakoniec to. 

SPEAKER 3: Vieš čo, Dane? Môžete ponoriť spôsob, akým chcete ponoriť. Budem ponoriť spôsob, akým chcem ponoriť.