>> [Prehrávanie hudby]
DAVID Malan: Dobre.
Dobre, vitaj späť.
Tak toto je 4. týždeň, začiatok tejto zmluvy, už.
A budete pripomenúť, že minulý týždeň, dáme kód stranou pre len trochu
a začali sme hovoriť trochu viac na vysokej úrovni, o veci, ako je
vyhľadávanie a radenie, ktoré, hoci trochu jednoduché nápady, sú
zástupca skupiny problémov si začne riešiť najmä
ako začnete premýšľať o finále projekty a zaujímavé riešenie, ktoré
Možno budete musieť reálnych problémov.
Teraz bublina druh bol jeden z najjednoduchších Takéto algoritmy, a to
pracoval tým, že tieto malé množstvo v zozname alebo v poli typu
bublina svoju cestu až na vrchol, a vysoké čísla pohybovať ich cestu až do
koniec tohto zoznamu.
>> A pripomínajú, že by sme mohli predstaviť bubble sort trochu
niečo také.
Tak ma nechaj ísť ďalej a kliknite na tlačidlo Spustiť.
Som predvybrané bublina triedenie.
A pokiaľ si spomínam, že vyššia modrá čiary predstavujú veľké čísla, malé
Modrej čiary predstavujú malé množstvo, ako prejdeme to znova a znova a
Znovu, porovnať dve tabuľky vedľa seba ďalšie v červenej farbe, ideme k výmene
najväčšie a najmenšie, ak sú mimo prevádzky.
>> Takže to bude pokračovať ďalej a ďalej a ísť na, a uvidíte, že čím väčšia
prvky robia ich cestu k Dobre, a menšie prvky sú
aby ich cestu na ľavej strane.
Ale začali sme kvantifikovať účinnosť,
Kvalita tohto algoritmu.
A my sme povedali, že v najhoršom prípad, tento algoritmus sa
zhruba, koľko krokov?
>> Tak n na druhú.
A čo bolo n?
>> DIVÁKOV: Počet prvkov.
>> DAVID Malan: Takže n bol počet prvkov.
A tak sme si to často.
Kedykoľvek chceme hovoriť o veľkosti o probléme alebo veľkosť
vstup, alebo množstvo času, ktoré trvá produkovať výstup, budeme len
zovšeobecniť, čo vstup je pre n
Takže späť v týždni 0, počet strán v telefónnom zozname bolo n
Počet študentov v miestnosti n
Takže aj tu sledujeme že vzor.
>> Teraz n na druhú nie je obzvlášť rýchlo, takže sme sa snažili urobiť lepšie.
A tak sme sa pozreli na pár ďalšie algoritmy, z ktorých
bol výber sort.
Takže výber bol druh trochu iný.
Bolo to skoro jednoduchšie, trúfam si povedať, kedy som začal na začiatku
Zoznam našich dobrovoľníkov a ja len znova a znovu a znovu prechádzal
zoznam, olúpanie najmenší prvok v čase a dávať ho alebo
ju na začiatku zoznamu.
>> Ale aj to, keď sme začali uvažovať cez matematiku a väčšie
obraz, myslel na to, koľkokrát Bol som tam a späť a späť
a tam sme si povedali, v najhoršom prípade, Výber druhu, bola taky čo?
n na druhú.
Teraz, v reálnom svete, môžu sa v skutočnosti mierne rýchlejší.
Vzhľadom k tomu, znovu som nemusel držať backtracking, akonáhle som radené
najmenšie prvky.
Ale ak si myslíme, že o veľké n, ak si trochu urobiť z matematiky ako
Ja som na doske s n na druhú mínus niečo, všetko ostatné
okrem n na druhú, akonáhle n dostane naozaj veľký, nie je
naozaj záležať.
Takže ako počítačových vedcov, sme tak nejako prižmúriť oko menšie
faktory a sústrediť sa iba na faktora v výraz, ktorý to bude robiť
najväčší rozdiel.
>> No, nakoniec sme sa zamerali pri vkladaní druhu.
A to bol podobný v duchu, ale skôr než ísť cez opakované a
vyberte najmenší prvok jeden na Tentoraz som namiesto toho vzal za ruku, že som
bola riešená, a rozhodol som sa, všetko Dobre, sem patrí.
Potom som sa presunul na ďalší prvok a rozhodol, že on alebo
patrila tu.
A potom som sa presunul ďalej a ďalej.
A mohol by som sa, po ceste, presunúť týchto ľudí, aby sa
aby pre nich priestor.
Takže to bolo niečo ako duševná zvrat výberového druhu, ktorý sme
volal vloženie radenie.
>> Takže tieto témy sa objavujú v reálnom svete.
Ešte pred niekoľkými rokmi, kedy určité Senátor sa uchádzal o prezidenta,
Eric Schmidt, v čase, keď generálny riaditeľ Google, skutočne možnosť
aby ho vypočuť.
A my sme si povedali, že zdieľať YouTube klip pre teba, keby sa nám podarilo otočiť až
hlasitosť.
>> [PLAYBACK]
>> -Teraz, senátor, ste tu na Google, a ja som rád, že predsedníctvo
ako pohovoru.
>> [Smiech]
>> -Teraz je to ťažké sa dostať práce ako prezident.
A ty teraz prechádzaš stuhnutosť teraz.
Je to tiež ťažké získať prácu v Google.
Máme na otázky a pýtame Naši kandidáti otázky.
A toto je od Larry Schwimmer.
>> [Smiech]
-Myslíte si, že si robím srandu?
Je to tu.
Aký je najúčinnejší spôsob, ako zoradiť milión dve bit celé číslo?
>> [Smiech]
>> -No, uh -
>> Je mi ľúto.
Možno, že by sme mali -
>> Nie, nie, nie, nie, nie.
>> -To nie je -
OK.
>> -Myslím, že bublina druhu by je zlý spôsob, ako ísť.
>> [Smiech]
>> [Fandenie a potlesk]
>> -No tak, kto mu to?
OK.
>> [END PLAYBACK]
>> DAVID Malan: Tak tu to máte.
Takže sme začali kvantifikovať beh krát, aby som tak povedal, s niečím
tzv asymptotickej notácie, ktorá je len s odkazom na náš druh sústruženie
slepé oko k tým menším faktorov a len pri pohľade na dobu prevádzky,
výkon týchto algoritmov, ako n dostane naozaj veľký v priebehu času.
A tak sme zaviedli veľký O. a veľký O predstavoval niečo, čo sme si mysleli,
ako horná hranica.
A skutočne, Barry, môžeme znížiť než mic trochu?
>> Mysleli sme si, ze je to horná hranica.
Tak veľký O prostriedkov n mocnín, že najhorší prípad, niečo ako
Výber sort by sa n štvorcová kroky.
Alebo niečo podobné vloženie druhu by n na druhú kroky.
Teraz niečo ako vloženie sort, čo bolo najhoršie?
Vzhľadom k tomu, pole, čo je to najhoršie možný scenár, že by ste mohli nájsť
sám tvárou v tvár?
>> Je to úplne obrátene, nie?
Pretože ak je to úplne dozadu, čo musíte urobiť veľa práce.
Pretože ak ste úplne dozadu, budete si
najväčšia prvkom je tu, a to aj keď patrí tam.
Takže sa chystáte povedať, jo, na tento okamih v čase, patríte sem,
takže nechať to byť.
>> Potom si uvedomíte, oh, sakra, musím presunúť o niečo menšie element
naľavo od vás.
Potom som to robiť znova a znova a znova.
A keď som išiel tam a späť, je by sa nejako cítiť výkon
že algoritmus, pretože stále som miešanie všetci ostatní v
pole, aby sa priestor pre to.
Tak to je najhoršie.
>> Naproti tomu -
a to bol Cliffhanger poslednej dobe -
sme si povedali, že vloženie triedenie bola omega čoho?
Aký je najlepší-case beh čas vloženia druhu?
Takže je to vlastne n
To bol prázdny, že sme opustili na doske naposledy.
>> A je to omega n, pretože prečo?
No, v tom najlepšom prípade to, čo je vloženie triedenie bude odovzdaná?
No, zoznam, ktorý je úplne radené už minimálnu prácu robiť.
Ale to, čo je pekné o vloženie druhu je to, že z dôvodu, že tu začína a
rozhodne, oh, ty si číslo jeden, patríš sem.
Ach, to je šťastie.
>> Ty si číslo dva.
Tiež sem patrí.
Číslo tri, ešte lepšie, Patríš sem.
Akonáhle sa dostane na koniec Zoznam, na vkladacieho SORT v pseudokódu
že sme prechádzali slovne Minule sa to robí.
Ale výber druhu, naopak, stále robí čo?
>> Ďalej v zozname znova a znova a znova.
Pretože Kľúčovou myšlienkou bolo len akonáhle ste sa pozrel až do
koniec zoznamu si môžete byť istí, že prvok vyberiete bola
v skutočnosti v súčasnej dobe najmenší prvok.
Tak to rôzne mentálne modely koniec up dávať niektoré veľmi reálny svet
rozdiely u nás, ale aj v týchto teoretické asymptotickej rozdiely.
>> Takže len zhrnúť, potom veľký O n štvorcový, videli sme niekoľko takých
algoritmy tak ďaleko.
Veľký O n?
Čo je to algoritmus, ktorý by sa povedať, že veľký O n?
V najhoršom prípade to trvá lineárny počet krokov.
>> OK, lineárne hľadanie.
A v najhoršom prípade, kedy je prvok, ktorý hľadáte, ak
použitie lineárne hľadanie?
>> OK, v najhoršom prípade, to nie je ani tam.
Alebo v druhom najhoršom prípade je to úplne na konci, ktorý je
plus alebo mínus jeden krok rozdiel.
Takže na konci dňa, môžeme povedať, že je lineárna.
Veľký O n by byť lineárne vyhľadávanie, preto, že v najhoršom prípade,
prvok nie je to ani tam, alebo je to úplne na konci.
>> No, veľký O log n
Nehovorili sme veľmi podrobne o , Ale my sme videli predtým.
Čo prebieha v tzv logaritmický čas, v najhoršom prípade?
>> Jo, binárne vyhľadávanie.
A binárne hľadanie v najhoršom prípade môže mať prvok niekde
stredná, alebo niekde vnútri poľa.
Ale nájdete len raz vás rozdeliť zoznam na polovicu, v roku
polovice, na polovicu, na polovicu.
A potom ajhľa, je to tam.
Alebo znovu, v najhoršom prípade, to nie je ani tam.
Ale vy neviete, že to tam nie je kým sa nejako dostať, že posledný
zdola väčšina prvkov podľa polovicu a polovicu a znížiť.
>> Veľký O z 1.
Tak by sme mohli o veľký O 2, O 3 veľké.
Kedykoľvek budete chcieť len konštantný počet, sme tak nejako jednoducho zjednodušiť
že tak veľkú O. 1.
Aj keď, ak realisticky, je potreba 2, alebo dokonca 100 stupňov, ak je to
konštantný počet krokov, povieme veľký O z 1.
Čo je to algoritmus, ktorý je vo veľkom O. 1?
>> DIVÁKOV: Hľadanie dĺžku premenné.
>> DAVID Malan: Hľadanie dĺžka premenné?
>> DIVÁKOV: Nie, dĺžka ak už je zoradený.
>> DAVID Malan: Dobrý.
OK, takže nájsť dĺžku niečo v prípade, že dĺžka tohto niečoho, ako je
pole, je uložený v nejakej premennej.
Pretože môžete len čítať premennú, alebo vytlačiť premennú alebo
len všeobecne prístup k tejto premennej.
A voila, že trvá konštantný čas.
>> Naopak, myslím, že späť do nuly.
Spomeňte si na prvý týždeň v C, volanie len printf a tlač
niečo na obrazovke, je pravdepodobne konštantný čas, pretože to jednoducho trvá
určitý počet CPU cyklov ukázať tento text na obrazovke.
Alebo čakať - je to tak?
Ako inak by sme mohli modelovať výkon printf?
By niekto chcel nesúhlasiť, že Možno to naozaj nie je konštantný čas?
V akom zmysle by printf beží čas, v skutočnosti tlačí reťazec na
na obrazovke, bude niečo iné ako konštantný.
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: Jo.
Takže to závisí na našej perspektíve.
Ak sme vlastne myslieť na vstup do printf ako reťazec, a
Preto meriame veľkosť, ktorá Vstup jeho dĺžkou - tak hovorme
že dĺžka n i -
pravdepodobne, printf je samo o sebe veľký O n , Pretože to bude trvať n kroky
tlačiť každý z týchto n znaky, s najväčšou pravdepodobnosťou.
Aspoň do tej miery, že predpokladáme, že možno to pomocou slučky for
pod kapotou.
>> Ale budeme musieť pozrieť na to kód pochopiť lepšie.
A skutočne, akonáhle ste začať analyzovať svoje vlastné algoritmy, budete
doslova robiť len to.
Druh oka kódu a myslím, o - v poriadku, mám túto slučku
tu alebo mám vnorené slučky tu že bude robiť veci n n-krát,
a môžete zoradiť rozumu cestu prostredníctvom kódu, aj keď je to
pseudokódu, a nie skutočný kód.
>> A čo omega-n na druhú?
Čo bol algoritmus, ktorý v najlepšom prípad, trvalo ešte n na druhú kroky?
Jo?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: Takže výber sort.
Vzhľadom k tomu, v tomto probléme veľmi znížená k tomu, že opäť neviem
Našiel som najmenší prúd, kým Skontroloval som všetky čertovsky prvky.
Tak omega, povedzme, n, sú Prišiel s jedným.
Vloženie sort.
Keď je zoznam sa stane byť radené už v najlepšom prípade budeme musieť
aby jeden priechod cez to, na ktorom mieste sme si istí.
A potom by sa dalo povedať byť lineárne, pre istotu.
>> Čo je Omega 1?
Čo, v najlepšom prípade, môže trvať konštantný počet krokov?
Takže lineárne vyhľadávanie, ak ste práve šťastie a prvok, ktorý hľadáte
je hneď na začiatku zoznamu, či je to to, kam spustenie
lineárny priechod z tohto zoznamu.
>> A to je pravda rad vecí.
Napríklad, aj binárne hľadanie omegou 1.
Pretože čo ak naozaj čertovsky šťastie a plácnutí DAB uprostred
vaša pole je číslo ste hľadali?
Takže môžete mať šťastie tam, rovnako.
>> Ten konečne, omega n log n
Tak n log n, my sme naozaj hovoriť o tom, ešte nie, ale -
>> DIVÁKOV: Zlúčiť druh?
>> DAVID Malan: Merge sort.
To bol Cliffhanger poslednej dobe, kde sme navrhli, a ukázali sme
vizuálne, že existujú algoritmy.
A zlúčiť druh len jeden taký algoritmus, ktorý je v podstate rýchlejší
ako niektoré z týchto ostatných chalanov.
V skutočnosti, je krátky spojiť nielen najlepšom prípade n log n, v najhoršom
Prípad n log n
A keď máte túto koincidencii omega a veľké O je to isté?
Môžeme vlastne popisovať to ako to, čo je tzv theta, keď je to
trochu menej časté.
Ale to znamená len dve medze, V tomto prípade, sú rovnaké.
>> Takže zlúčiť druh, čo to Naozaj sa redukuje na pre nás?
No, spomínam motiváciu.
Dovoľte mi, aby som vytiahnuť ďalšie animáciu, ktorá sme sa nepozeral na minule.
Ten, rovnaký nápad, ale je to trochu väčšie.
A ja idem ďalej a poukázať na Prvý - máme kurzor na druh
vľavo hore, potom výber triedenie, bublina triedenie, pár ďalších druhov -
shell a rýchlo - že sme spolu nehovorili o, a halda a zlúčiť druh.
>> Tak sa aspoň pokúsiť zamerať svoj pohľad na prvé tri vľavo a potom
zlúčiť druh, keď kliknem táto zelená šípka.
Ale nechám všetky z nich spustiť, len aby dá vám pocit rozmanitosti
algoritmy, ktoré existujú vo svete.
Chystám sa nechať to plynúť len na pár sekúnd.
A ak sa sústredíte vaše oči - vyberte si algoritmus, sústrediť sa na to len za
sekúnd - Začnete vidieť vzor, ​​ktorý to vykonáva.
>> Merge sort, oznámenia, je hotovo.
Heap sort, Quick sort, shell -
takže sa zdá, sme predstavili tri najhoršie algoritmy minulý týždeň.
Ale to je dobre, že sme tu dnes sa na druhu korešpondencie, ktorý je jedným z
koncentrácia je ľahšie je pozrieť sa na, a to aj aj keď to asi bude ohýbať vaša myseľ
len trochu.
Tu môžeme vidieť, ako moc Výber trochu naštve.
>> Ale na druhú stranu, je to veľmi ľahko implementovať.
A možno pre sadu P 3, to je jedna z algoritmy ste sa rozhodli realizovať
pre štandardnú verziu.
Úplne v poriadku, úplne správne.
>> Ale opäť, ako n sa zväčší, ak sa možnosť vykonať rýchlejší algoritmus
chcel zlúčiť druh, šance sú väčšie a väčšie vstupy, váš kód je len
bude bežať rýchlejšie.
Váš web bude fungovať lepšie.
Vaši užívatelia sa bude šťastnejší.
A tak sú tieto účinky skutočne dáva
nám niektoré hlbšie myšlienka.
>> Takže poďme sa pozrieť na to, čo zlúčiť Triedenie je vlastne všetko okolo.
Super vec je, že zlúčenie Triedenie je práve tento.
To je opäť to, čo sme tzv pseudokódu, pseudokódu bytosť
Angličtina-ako syntax.
A jednoduchosť je druh fascinujúce.
>> Takže na vstupe n prvkov - tak, že jednoducho znamená, tu je pole.
Je tu n veci v ňom.
To je všetko, čo hovoríme tam.
>> Ak je n menšie ako 2, vrátiť.
Tak to je len triviálne prípad.
Ak je n menšie ako 2, potom samozrejme je to 1 alebo 0, v tomto prípade ide o to
už je zoradený alebo neexistujúce, takže stačí vrátiť.
Nie je nič robiť.
Takže je to jednoduchý prípad trhať off.
>> Inak máme tri kroky.
Radenie ľavú polovicu prvkov, triedenie pravá polovica prvkov,
a potom zlúčiť zoradené polovice.
Čo je zaujímavé je to, že Som trochu plaviť, že jo?
Je to niečo ako definícia v kruhu do tohto algoritmu.
V akom zmysle je tento algoritmus je definícia kruhové?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: Jo, môj algoritmus triedenia, dvaja z jeho kroky sú "druh
niečo. "A tak to pozdáva otázka, no, čo budem používať
triediť ľavú polovicu aj pravá polovica?
A najlepšie je, že aj keď Znovu, toto je myseľ-ohýbanie
časť potenciálne, môžete použiť rovnaké algoritmus pre triedenie ľavú polovicu.
>> Ale počkajte chvíľku.
Keď ste povedal, triediť ľavá polovica, čo sú dva
kroky bude ďalej?
Vyriešime ľavú polovicu ľavá polovica a právo
polovica ľavej polovici.
Sakra, ako to mám vyriešiť tie dva Polovičky alebo štvrtiny, teraz?
>> Ale to je v poriadku.
Máme triediace algoritmus tu.
A aj keď by ste mohli starať vôbec Spočiatku to tak trochu nekonečný
slučky, je to cyklus, ktorý nikdy skončí - to bude
koniec raz, čo sa stane?
Akonáhle n je menej ako 2.
Ktorý nakoniec sa stane, pretože ak budete mať na polovicu a
znížiť na polovicu týchto polovíc, určite nakoniec sa chystáte na koniec
s len 1 alebo 0 prvkov.
V tom okamihu, tento algoritmus hovorí, že je hotovo.
>> Takže mágie v tejto algoritmus sa zdá byť v
že posledný krok, zlučovanie.
To jednoduchá myšlienka len zlúčenie dvoch veci, to je to, čo nakoniec bude
ktoré nám umožnia vyriešiť rad, povedzme, osem prvkov.
Takže mám ďalších osem stresovej loptičky tu osem kúsky papiera, a jeden
Google Glass -
ktoré som sa udržať.
>> [Smiech]
>> DAVID Malan: Keby sme mohli mať osem dobrovoľníkov, a uvidíme, či to pôjde
hrať sa na to, tak.
Wow, OK.
Počítačová veda je stále baviť.
Dobrá.
Tak čo vy traja, Najväčšia ruka hore.
Štyri v chrbte.
A čo budeme robiť vás tri v tejto rade?
A štyri v prednej časti.
Takže si osem, ísť hore.
>> [Smiech]
>> DAVID Malan: V skutočnosti som nie ste istí, čo to je.
Je to stresové gule?
Na stolové lampy?
Materiál?
Internet?
>> OK.
Tak poď hore.
Kto by chcel -
udržať prichádza.
Poďme sa pozrieť.
A to vám dáva lokalite -
ste na mieste jeden.
Uh-oh, počkaj.
1, 2, 3, 4, 5, 6, 7 - Oh, dobre.
Tak jo, sme v pohode.
Dobre, takže všetci majú sídlo, ale nie na sklo Google.
Dovoľte mi, aby som do fronty tieto hore.
Ako sa voláte?
>> Michelle Michelle.
>> DAVID Malan: Michelle?
V poriadku, dostanete vyzerať geek, či je to OK.
No, ja tiež, myslím, len na chvíľu.
Dobre, v pohotovostnom režime.
Snažili sme sa prísť s prípad použitia pre Google skla a my
si myslel, že by bolo zábavné sa jednoducho to keď sú ľudia na javisku.
Budeme zaznamenávať svet z ich pohľadu.
Dobrá.
Nie je asi to, čo Google určený.
Dobre, ak vám nevadí, že na sebe na dobu najbližších nepríjemných minút,
že by bolo báječné.
>> Dobre, takže tu máme rad prvky, a že pole, podľa
kúsky papiera v týchto ľuďoch " ruky, je v súčasnej dobe netriedený.
>> Michelle: Oh, to je tak divné.
>> DAVID Malan: Je to do značnej miery náhodné.
A za chvíľu sa budeme snažiť realizovať zlúčiť dohromady akúsi
a zistiť, kde ten kľúč je vhľad.
A trik tu sa druhu korešpondencia je niečo, čo sme sa doteraz predpokladalo.
Potrebujeme teda nejaký priestor navyše.
Tak čo to bude najmä Zaujímavé na tom je, že sa jedná
chlapci budú trochu pohybovať bit, pretože budem predpokladať, že
je tam navyše poľa priestoru, povedzme, hneď za nimi.
>> Takže ak sú za ich predsedami, to je sekundárna pole.
Ak ste tu sídlil, to je primárne polia.
Ale to je zdroj, ktorý máme nevyužívajú pákový efekt, tak ďaleko s bublinou
druhu, s výberom druhu, s vkladacie druhu.
Pripomeňme si minulý týždeň, všetci len druh miešané na mieste.
Nemali používať žiadnu ďalšiu pamäť.
Urobili sme priestor pre ľudí tým, pohybujúce sa ľudia okolo.
>> Tak to je kľúčový vhľad taky.
Tam je to kompromis, všeobecne v výpočtová technika, zdrojov.
Ak chcete urýchliť niečo napríklad čas, budete
musieť zaplatiť cenu.
A jedna z týchto cien je veľmi často priestor, množstvo pamäte alebo pevného
disku, ktorý používate.
Alebo, úprimne povedané, vyššie programátor času.
Ako dlho to trvá vám, človek, skutočne realizovať niektoré ďalšie
komplikovaný algoritmus.
Ale pre dnešok, trade-off je čas a priestor.
>> Takže ak ste mohol len zdvihnúť vaše čísla, takže môžeme vidieť, že ste
skutočne zodpovedajúce 4, 2, 6, 1, 3, 7, 8.
Výborný.
Takže budem snažiť organizovať veci, ak môže ste práve
za mnou tu.
>> Takže budem realizovať jednak Prvým krokom tohto pseudokódu, ktorý je
na vstupe prvkov n, pokiaľ je n menej ako 2, potom sa vrátiť.
Je zrejmé, že nie je Použiť, takže sme ďalej.
Takže radiť ľavú polovicu prvkov.
Takže to znamená, že budem zamerať svoje pozornosť na chvíľu o týchto
štyri chlapi.
Tak jo, čo mám nabudúce urobiť?
>> DIVÁKOV: Radenie ľavú polovicu.
>> DAVID Malan: Takže teraz musím vyriešiť Ľavá polovica týchto chalanov.
Pretože opäť predpokladajme, že na seba na Cieľom je zoradiť ľavú polovicu.
Ako to robíte, že?
Stačí sledovať inštrukcie, a to aj keď robíme to znova.
Takže radiť ľavú polovicu.
Teraz som triedenie títo dvaja.
Čo bude nasledovať?
>> DIVÁKOV: Radenie ľavú polovicu.
>> DAVID Malan: Radenie ľavú polovicu.
Takže teraz ty, toto sedadlo tu je zoznam veľkosti 1.
A čo že sa to voláš?
>> PRINCESS DAISY: Princess Daisy.
>> DAVID Malan: Princezná Daisy je tu.
A tak už je zoradený, pretože Zoznam je veľkosti 1.
Čo mám robiť ďalšie?
OK, návrat, pretože tento zoznam je veľkosť 1, ktorý je menší ako 2.
Tak čo je ďalší krok?
A teraz ste si na druh ustúpiť vo vašej mysli.
>> Radenie pravú polovicu, čo je -
Ako sa voláte?
>> LINDA: Linda.
>> DAVID Malan: Linda.
A tak to, čo budeme robiť teraz, máme zoznam o veľkosti 1?
>> DIVÁKOV: Návrat.
>> DAVID Malan: Opatrne.
Vrátime sa prvý, a teraz tretia krok - a keď som sa trochu popísať ju
zahŕňa dve miesta teraz, teraz som majú zlúčiť tieto dva prvky.
Takže teraz bohužiaľ prvky sú mimo prevádzky.
Ale to je miesto, kde proces zlúčenia začína byť presvedčivé.
>> Takže ak ste mohol postaviť len za Okamih, budem ťa potrebujem, v
okamih, krok za svojho kresla.
A ak Linda, pretože 2 je menšie ako 4, prečo nie
Prídete okolo prvej?
Zostaň tam.
Takže Linda, prídete asi prvý.
>> Teraz v skutočnosti, ak je to len pole sme mohli len presunúť ju v reálnom čase
z tohto kresla tomto mieste.
Tak si predstavte, že sa nejaká konštanta počet krokov 1.
A teraz -
ale musíme dať do Na prvom mieste je tu.
>> A teraz, ak by ste mohli prísť okolo, rovnako, budeme
byť v mieste dvoch.
A aj keď to pocit, že je to pričom na chvíľu, čo je pekné je teraz
že ľavá polovica ľavá polovica je teraz radené.
Takže aký bol ďalší krok, keď sme teraz previnúť ďalej v príbehu?
>> Divákov: Pravá polovica.
>> DAVID Malan: Triediť pravú polovicu.
Takže vy musíte urobiť to rovnako.
Takže ak by ste mohli postaviť len na chvíľu?
A Ako sa voláte?
>> JESS: Jess.
>> DAVID Malan: Jess.
OK, takže Jess je teraz vľavo polovica pravej polovici.
A tak je zoznam veľkosti 1.
Ona samozrejme radené.
A voláte?
>> Michelle Michelle.
>> DAVID Malan: Michelle je samozrejme Zoznam veľkosti 1.
Už je triediť.
Takže teraz mágia stane, proces zlúčenia.
Takže kto príde ako prvý?
Je zrejmé, Michelle.
Takže ak ste prišiel zadom.
Priestor máme k dispozícii pre ňu teraz je hneď za téhle stoličku tu.
A teraz, keď sa môže vrátiť tiež, teraz máme, aby bolo jasno, dva
polovice, každá o veľkosti 2 -
a len pre zobrazenie jeho záujmu, ak by mohlo byť trochu priestoru -
zostala polovica tu, jeden Pravá polovica tu.
>> Rewind ďalej v príbehu.
Čo krok ďalej?
>> Divákov: Zlúčiť.
>> DAVID Malan: Takže teraz musíme spojiť.
Takže OK, takže teraz, našťastie sme práve uvoľnil štyri stoličky.
Takže sme použili dvakrát toľko pamäte, ale môžeme dať flip-flope medzi
dve polia.
Takže, aké číslo je na prvom mieste?
Takže Michelle, samozrejme.
Tak poď sa okolo seba a vziať vaše sídlo tu.
A potom číslo 2 je zrejme Ďalej, ak ste sem prišiel.
Číslo 4, číslo 6.
A opäť, aj keď je trochu chôdze zapojený,
Naozaj, mohli by stáť okamžite, pohybom jedného -
OK, dobre hral.
>> [Smiech]
>> DAVID Malan: A teraz sme v dobrom stave.
Ľavá polovica celého Vstup bol teraz radené.
Dobre, takže títo ľudia mali Výhodou môjho -
ako to skončí všetky dievčatá na doľava a všetci chlapci na pravej strane?
>> OK, takže chlapci 'sa teraz.
Nebudem vás prevedie tieto kroky.
Uvidíme, či sa nám podarí znovu rovnaký pseudokódu.
Ak chcete ísť dopredu a vstať, a vy, dovoľte mi, aby som vám mikrofón.
Uvidíme, či nemôže replikovať to, čo Jednoducho sme tu na
Druhý koniec zoznamu.
Kto potrebuje hovoriť ako prvý, na základe algoritmu?
Takže vysvetliť, čo robíte, ako vykonáte nohy pohyby.
>> SPEAKER 1: Dobre, takže od tej doby Som Ľavá polovica
ľavá polovica, vrátim.
Je to tak?
>> DAVID Malan: Dobrý.
>> SPEAKER 1: A potom -
>> DAVID Malan: Kto mic ísť ďalej?
>> SPEAKER 1: Ďalšie číslo.
>> SPEAKER 2: Tak som pravá polovica na ľavej polovici
ľavá polovica, a ja som sa vrátiť.
>> DAVID Malan: Dobrý.
Vrátite sa.
Takže teraz, čo je ďalší pre vás dvoch?
>> SPEAKER 2: Chceme zistiť, kto je menšia.
>> DAVID Malan: Presne tak.
Chceme spojiť.
Priestor budeme používať k zlúčeniu vás do, aj keď sú
samozrejme radené už ideme podľa rovnakého algoritmu.
Tak kto ide späť ako prvý?
Takže 3 a potom 7..
A teraz ide mic na tých chlapov, OK?
>> SPEAKER 3: Takže som pravá polovica ľavá polovica, a moja je n menšie ako
1, takže som len tak prejsť -
>> DAVID Malan: Dobrý.
>> SPEAKER 4: Som pravá polovica pravá polovica pravej polovici, a ja som
tiež jeden človek, takže som chystá k návratu.
Takže teraz sme zlúčiť.
>> SPEAKER 3: Tak ideme naspäť.
>> DAVID Malan: Takže idete do chrbta.
Takže 5 ide prvý, a potom 8.
A teraz publikum, čo je krok musíme sa pretočiť
späť v našich mysliach?
>> Divákov: Zlúčiť.
>> DAVID Malan: Zlúčenie ľavej a pravej polovice polovicu pôvodného ľavej polovici.
Takže teraz -
a len preto, aby to bolo jasné, aby trochu priestoru
medzi vami dvaja chlapci.
Takže teraz, že to sú dva zoznamy, doľava a doprava.
Tak ako sme sa spojiť tých ľudí do Predný rad sedadiel znova?
>> 3. ide prvý.
Potom 5, samozrejme.
Potom 7, 8 a teraz.
OK, a teraz sme?
>> Divákov: nerobí.
>> DAVID Malan: Nie je urobil, pretože samozrejme, je tu jeden krok zostáva.
Ale znovu, dôvod, prečo som pomocou tohto žargóne ako "dozadu vo vašej mysli,"
je to preto, že je naozaj čo sa deje.
Ideme cez všetky tieto kroky, ale my sme trochu odmlčal
moment, potápanie hlbšie do algoritmus, zastavil sa na okamih,
potápanie hlbšie do algoritmu a teraz musíme nejako dozadu v našom
myseľ a vrátiť späť všetky tieto vrstvy že sme trochu podrží.
>> Takže teraz máme dva zoznamy veľkosti 4.
Ak ste mohol postaviť jeden posledný čas a aby sa trochu priestoru tu
bolo zrejmé, že sa jedná o ľavú polovica z originálu,
Pravá polovica originálu.
Kto je prvé číslo, ktoré sme musí vytiahnuť na zadnej?
Michelle samozrejme.
>> Takže sme dali Michelle tu.
A kto má číslo 2?
Číslo 2 je na zadnej strane rovnako.
Číslo 3?
Výborný.
Č 4, č 5, č 6, číslo 7 a č 8.
>> OK, tak to pripadalo ako veľa krokov, pre istotu.
Ale teraz uvidíme, či nemôžeme potvrdiť, nejako intuitívne, že tento
algoritmus zásadne, najmä pokiaľ n dostane naozaj veľký, ako sme videli
s animáciou, je zásadne rýchlejší.
Takže tvrdím, tento algoritmus, v najhoršom prípad a dokonca v najlepšom prípade,
je veľký O n žurnál n krát.
To znamená, že tam je nejaký aspekt tohto Algoritmus, ktorý má n krokov, ale
je tu ďalší aspekt, niekde že iterácie, že slučky, že
trvá log n krokov.
Môže dáme prst na to, čo tí dve čísla sú na mysli?
No, kde -
Kde mic ísť?
>> Reproduktor 1: Malo by log n je lámanie nás do dvoch -
delenie dvoma, v podstate.
>> DAVID Malan: Presne tak.
Kedykoľvek vidíme v každom algoritme teda Zatiaľ tam bol tento vzor
delenie, delenie, delenie.
A je to typicky znížený na niečo, čo je
logaritmické, log základ 2.
Ale mohlo by to byť naozaj čokoľvek, ale prihlásiť základ 2.
>> Teraz, čo o n?
Vidím, že sme trochu rozdeliť vás chlapci - delí vás delí vás,
delí vás delí vás.
Kde sa koniec pochádza?
>> Takže je to zlúčenie.
Pretože o tom premýšľať.
Pri zlúčení osem ľudí dohromady, pričom polovica z nich je sada štyroch
a druhá polovica sú ďalšie sada štyroch, ako sa vám ísť
o tom zlúčenie?
No, vy ste to urobil pomerne intuitívne.
>> Ale keby som to robil namiesto toho trochu viac metodicky, možno som už uviedol v
vľavo osoba najprv po mojej ľavici ruku, ukázal na ľavom osoby
tejto polovice sa mojej pravici, a len následne prešiel
Zoznam a ukázal na najmenší prvok zakaždým, pohybujúce sa cez môj prst a
viac ako v prípade potreby v celom zozname.
Ale čo je kľúčové o tomto zlúčení proces som porovnanie týchto párov
prvkov.
Z pravej polovice a zľava polovice, som ani raz cúvať.
>> Takže zlúčenie sám je pri nie viac ako n krokov.
A koľkokrát to mám k tomu, že zlúčenie?
No, nie viac ako n, a my sme videl, že s konečnou zlúčenie.
A tak, ak robíte niečo, čo trvá log n krokov n-krát, alebo naopak,
to nám dá n log n krát.
>> A prečo je to lepšie?
No, keď už vieme, že protokol n je lepší ako n - P?
Videli sme v binárnom vyhľadávanie v telefónnom zozname Napríklad log n rozhodne
lepšie ako lineárny.
Tak, že znamená, že n-krát log n je rozhodne lepšie ako n krát iný
n, n AKA druhú.
A to je to, čo sme nakoniec pocit.
>> Tak veľký potlesk, keď Mohli by sme týchto ľudí.
>> [APPLAUSE]
>> DAVID Malan: A vaša rozlúčka darčeky - môžete držať čísla,
ak by ste chceli.
A váš dar na rozlúčku, ako obvykle.
Jo, a my vám radi zašleme zábery, Michelle.
Ďakujem.
Dobrá.
Poslúžte stresu loptu.
>> A dovoľte mi vytiahnuť, do tej doby, náš priateľ Rob Bowden ponúknuť
trochu odlišný pohľad na to, pretože si môžete myslieť o týchto
kroky sa dejú v trochu odlišným spôsobom.
V skutočnosti, set-up, čo Rob je asi aby nám ukázal, predpokladá, že máme
už vykonáva delenie na veľký zoznam do ôsmich menších zoznamov,
každý z veľkosti 1.
>> Takže Meníme pseudokódu trochu, len aby nejako dostať
Základnou myšlienkou, ako sa zlúčenie práce.
Ale doba chodu čo sa chystá urobiť, je stále
bude rovnaká.
A opäť, set-up je, že je začala s ôsmimi zoznamov veľkosti 1.
Takže ste vynechal tú časť, kde je to vlastne urobil log n, log n log n,
delenie vstupu.
>> [PLAYBACK]
>> -A je to pre krok jedna.
Na druhom kroku, a to opakovane spojí dva zoznamy.
>> DAVID Malan: Hm.
Iba zvuk prichádza z môjho počítača.
Skúsme to znova.
>> -Len ľubovoľne vybrať, ktoré - Teraz máme štyri zoznamy.
Naučte predtým.
>> DAVID Malan: Tak ideme.
>> Zlúčenie-108 a 15, sme sa nakoniec s zoznam 15, 108.
Zlúčenie 50 a 4, sa skončiť s 4, 50.
Zlúčenie 8 a 42, sa skončiť s 8, 42.
A zlúčenie 23 a 16, sa skončiť s 16, 23.
>> Teraz sú všetky naše zoznamy sú o veľkosti 2.
Všimnite si, že každý z štyri zoznamy sa triedi.
Takže môžeme začať zlúčenie pary opäť kompletný zoznam.
Zlúčenie 15 a 108 a 4 a 50, sa prvá sa na 4, potom 15, potom
50, potom 108.
Zlúčenie 8, 42 a 16, 23, najprv sa 8, potom 16, potom 23,
potom 42.
>> Takže teraz máme len dva zoznamy veľkosti 4, z ktorých každý je triedený.
Takže teraz sme zlúčiť tieto dva zoznamy.
Najprv zoberieme 4, potom sa 8, potom budeme mať 15, potom 16, potom
23, potom 42, potom 50, potom 108.
>> [END PLAYBACK]
>> DAVID Malan: Opäť, oznámenia, nikdy dotkol danej šálka viac ako raz
po postupuje za ňou.
Takže nikdy opakovať.
Takže je vždy v pohybe do strany, a to je, kde sme dostali náš n
>> Prečo nie, dajte mi vytiahnuť jednu animáciu ktoré sme videli predtým, ale tentoraz
zameriava iba na druhu korešpondencie.
Nechaj ma ísť dopredu a zoom do toho tu.
Najprv mi dovoľte, aby som si vybrať náhodný vstup, zväčšiť to, a môžete nejako vidieť
to, čo sme považovali za samozrejmé, skôr, zlúčiť druh skutočne robí.
>> Tak zistíte, že vám tieto polovice alebo Tieto štvrtí alebo tie osminy
problém, ktorý sa z ničoho nič začnú mať dobrú formu.
A nakoniec, uvidíte na veľmi koniec, ktorý bam,
všetko je spojil.
>> Tak to sú len tri rôzne sa na rovnakú myšlienku.
Ale hlavný pohľad, rovnako ako rozdelenie a podmaniť si hneď v prvej triede,
bolo to, že sme sa rozhodli nejako rozdeliť problém do niečoho veľkého, do
niečo trochu identické v duchu, ale menšie a menšie a menšie
a menšie.
>> Teraz ďalší zábavný spôsob, ako nejako myslieť o nich, aj keď to nie je
bude vám rovnako intuitívne porozumenie, je
Nasledujúci animácie.
Tak toto je video niekto dať dohromady aké sú spojené rôzne
zvukov s rôznymi operáciami vloženie druhu, pre druh korešpondencie a
na pár ďalších.
Takže vo chvíli, idem zasiahnuť Play.
Je to asi minútu dlhý.
A aj keď stále môžete vidieť vzory deje, tentoraz si môžete
tiež počuť, ako tieto algoritmy sú vykonávanie odlišne a s
trochu rôzne vzory.
>> To je druh vloženie.
>> [TÓNY PLAYBACK]
>> DAVID Malan: Opäť sa snažia vložiť každý prvok
na tam, kam patrí.
To je bublina druh.
>> [TÓNY PLAYBACK]
>> DAVID Malan: A môžete tak nejako pocit ako relatívne málo práce to robí
na každom kroku.
To je to, čo znie ako nudnost.
>> [TÓNY PLAYBACK]
>> DAVID Malan: Toto je výber druhu, kde vyberte element, ktorý chceme do
prechádza znova a znova a znova a uvedenie na začiatku.
>> [TÓNY PLAYBACK]
>> DAVID Malan: Toto je zlúčiť druh, ktorý môžete naozaj začať cítiť.
>> [TÓNY PLAYBACK]
>> [Smiech]
>> DAVID Malan: Niečo s názvom gnome triedenie, ktoré sme sa pozrel na.
>> [TÓNY PLAYBACK]
>> DAVID Malan: Tak sa ukážte, teraz, roztržitý, ako ste snáď sú vo
hudba, či môžem skĺznuť trochu Trocha matematiky tu.
Takže tam je štvrtý spôsob, ktorý môžeme premýšľať o tom, čo to znamená, že tieto
funkcií, ktoré sú rýchlejšie ako tie že sme nevideli.
A ak idete na kurze od matematika pozadia, môžete
vlastne viete, možno už, že ste môže udrieť termín na tejto technike -
to rekurzia, funkcie že tak nejako volá sama seba.
>> A opäť pripomenúť, že druh korešpondencie pseudokódu bol rekurzívne v tom zmysle,
že jeden z Merge sort v krokoch nazval druh -
to znamená, že sama o sebe.
Ale našťastie, pretože sme si nechali volanie triediť, alebo zlúčiť druh,
špecificky, na menšie a menšie a menšie zoznam, nakoniec sme
dna vďaka, čo budeme nazývať referenčný prípad, pevne platí, že
povedal, že ak je zoznam je malý, menší než 2 V takom prípade si okamžite vráti.
Ak by sme nemali mať tento osobitný prípad, Algoritmus by nikdy dna,
a vy by ste naozaj dostať do nekonečná slučka naozaj navždy.
>> Ale predpokladajme, že sme chceli, aby sa dal niektoré čísla na to, opäť za použitia n
ako veľkosť vstupu.
A chcel som sa vás opýtať, čo je celkový čas zúčastňuje
spustenie hromadnej korešpondencie druh?
Alebo všeobecnejšie, čo je náklady na neho v čase?
>> No, je to celkom jednoduché zmerať to.
Ak je n menšie ako 2, času potrebného pre v triedení n prvkov,
kde n je 2, je 0.
Pretože sme jednoducho vrátiť.
Neexistuje žiadna práce je potrebné urobiť.
Teraz pravdepodobne, možno je to jeden krok alebo dva kroky, aby zistili množstvo
práca, ale je to dosť blízko 0, že Len som chcel povedať, nie práca
vyžaduje chcete zoznam je tak malý, byť nezaujímavé.
>> Ale v tomto prípade je zaujímavé.
Rekurzívne prípad bol odbor pseudokódu, ktorý povedal inde, triedenie
ľavá polovica, triediť právo polovice, zlúčiť dve polovice.
A teraz, prečo sa tento výraz predstavujú, že náklady?
No, T n len znamená, Doba triediť n prvkov.
A potom na pravej strane znamienko rovnosti tam, T n delí
o 2 odkazuje na cenu čo?
Radenie ľavú polovicu.
Druhý T n delené 2 je pravdepodobne sa odkazovať na náklady
zoradiť pravú polovicu.
>> A potom n a?
Je zlúčenie.
Vzhľadom k tomu, ak máte dva zoznamy, jeden z veľkosti n na 2 a ďalšie veľkosti n
viac ako 2, máte v podstate dotýkať každý z týchto prvkov, rovnako ako Rob
dotkol každého z košíčkov, a len ako sme upozornili na každej
Dobrovoľníci na javisku.
Tak n je náklad zlúčenie.
>> Teraz bohužiaľ, tento vzorec je tiež sám rekurzívne.
Takže ak sa pýtal, ak je n je, povedzme, 16, v prípade, že je 16 ľudí na javisku
alebo 16 šálok na video, koľko celkom kroky je potrebné, aby triediť
Pomocou Zoradiť korešpondencie?
Je to vlastne nie je jasná odpoveď, pretože teraz budete musieť nejako
rekurzívne odpovedať na tento vzorec.
>> Ale to je v poriadku, pretože mi dovoľte navrhnúť, čo robíme nasledujúce.
Času potrebného pre triedenie alebo 16 ľudí 16 šálok sa bude zastúpený
všeobecne ako T zo 16..
Ale to sa rovná, podľa našich predchádzajúci vzorec, 2 násobok sumy
čas potrebný k radeniu 8 šálok plus 16.
A opäť, a 16 je čas spojiť, a dvakrát T z 8. je
Doba triediť ľavú polovicu a pravej polovice.
>> Ale znovu, to nestačí.
Musíme sa do toho ponoriť hlbšie.
To znamená, že musíme odpovedať otázka, čo je t 8?
No T z 8 sa nachádza len 2 Časy T z 4 plus 8.
No, čo sa t 4?
T 4 je len 2 krát T z 2 plus 4.
No, čo je t 2?
T 2 je len 2 krát T z 1 plus 2.
>> A opäť sme trochu dostať uviazol v tomto cykle.
Ale je to o tom, že zasiahnuť tzv referenčný prípad.
Pretože to, čo je t 1, sme sa tvrdí?
0.
Takže teraz konečne môžeme pracovať pospiatky.
>> Je-li T 1 je 0, teraz môžem vrátiť do jedného linky na toho chlapa tu, a môžem
zapojte 0 pre T z 1..
Takže to znamená, že sa rovná 2 krát nula, inak známy ako 0, + 2.
A tak, že celý výraz je 2..
>> Teraz, keď som si na T 2, ktorých odpoveď je 2, zapojte ho do prostrednej radu, T
zo 4., že mi dáva 2 krát 2 a 4, tak 8..
Keď som potom pripojíte 8 na predchádzajúcu linka, ktorá mi dáva 2 krát 8, 16.
A ak budeme pokračovať, že sa 24, tým, že do 16 rokov, sa konečne dostať
hodnota 64.
>> Teraz, keď sám o sebe trochu hovorí nič na zápis n,
veľký O, omega, že máme o tom hovorili.
Ale ukazuje sa, že 64 je naozaj 16, veľkosť vstupu,
prihlásiť základňu 2 16 rokov.
A ak je to trochu neznáma, rovnako spomínať, a to vrátim
vám nakoniec.
Ak je to log základ 2, je to ako 2 zvýšil na to, čo vám dáva 16?
Oh, to je 4, takže je to 16 krát 4.
>> A opäť, nie je to veľký problém, ak to je trochu hmlisté pamäti teraz.
Ale teraz, sa na základe viery že 16 protokolu 16 je 64.
A tak sa skutočne s týmto jednoduchým zdravého rozumu Skontrolujte, sme potvrdená -
ale ukázalo formálne -
že doba chodu zlúčenie Triedenie je naozaj n log n
>> Takže to nie je zlé.
Je to určite lepšie, než algoritmy sme videli doteraz, a
je to preto, že sme zadlžujú, jedným, techniku ​​zvanú rekurzia.
Ale zaujímavejšie než to, že Pojem delenie a dobývanie.
Opäť platí, že naozaj veci, ktoré týždeň 0 aj dnes sa opakujúce v
presvedčivejšie spôsobom.
>> Teraz trochu zábavy cvičenia, ak ste nikdy nerobil - a pravdepodobne
by nemal, pretože akosi normálne ľudia si nemyslím, že to urobiť.
Ale keď idem do google.com, a ak Chcem sa dozvedieť niečo o
rekurzia, Enter.
>> [Smiech]
[Ďalšia smiech]
DAVID Malan: Bad joke pomaly šíri.
[Smiech]
DAVID Malan: Len v prípade, že tam je.
Nechcel som to zle píše, a tam je ten vtip.
Dobrá.
Vysvetlite ľuďom vedľa vás, či to nie je úplne klikol len zatiaľ.
Ale rekurzia, všeobecne sa odkazuje do procesu a volania funkcií
sama o sebe, alebo všeobecnejšie, delenie problém do niečoho, čo môže byť
rieši po častiach pri riešení zhodné reprezentatívny problémy.
>> Dobre, poďme preradiť len na chvíľu.
Radi by sme skončiť na určitých cliffhangers, takže poďme začať s nastavením
fáze, po dobu niekoľkých minút, na veľmi jednoduchom nápadu -
to prehodenie dvoch prvkov, nie?
Všetky tieto algoritmy sme boli hovorí o posledných pár
Prednášky zahŕňajú niektoré druh vymieňať.
Dnes to bolo vizualizovať ich získavanie sa zo svojich stoličiek a
chodia, ale v kóde, by sme len sa prvok z jedného poľa
a PLOP to do druhého.
>> Tak ako sme sa ísť asi robí?
No, dovoľte mi ísť ďalej a písať rýchly program tu.
Chystám sa ísť ďalej a robiť to je napríklad nasledovné.
Povedzme to -
Čo chceme volať toto?
>> V skutočnosti, no.
Nechaj ma dozadu.
Nechcem k tomu, že Cliffhanger ešte.
To bude kaziť zábavu.
Poďme na to miesto.
>> Dajme tomu, že chcem napísať niečo program, a teraz zahŕňa tento
Myšlienka rekurzia.
Tak nejako som sa dostal pred seba tam.
Chystám sa vykonať nasledujúce kroky.
>> Po prvé, je rýchly štandardný IO.H, rovnako ako patrí v cs50.h.
A potom budem pokračovať a vyhlásiť za neplatné int main
obvyklým spôsobom.
Uvedomil som si, som nesprávne pomenovaný súbor, takže dovoľte mi pridať. c príponu, takže tu
že môžeme zostaviť správne.
Spustite túto funkciu vypnúť.
>> A funkcie chcem napísať, docela Jednoducho povedané, je ten, ktorý žiada
užívateľ pre číslo a potom spočíta všetky čísla, ktorá medzi
číslo a, povedzme, 0.
Takže v prvom rade budem pokračovať a vyhlasujú, int n
Potom som skopírovať nejaký kód, ktorý sme použili na chvíľu.
Aj keď je niečo pravda.
Vrátim sa k tomu za chvíľu.
>> Čo chcem robiť?
Chcem povedať printf pozitívny celé číslo, prosím.
A potom budem povedať, n dostane sa int.
Takže znova, niektorí štandardizovaný kód že sme použili predtým.
A ja idem na to keď n je menšia ako 1.
Takže to bude zabezpečiť, že používateľ mi dáva kladné celé číslo.
>> A teraz budem robiť nasledujúce.
Chcem sa sčítať všetky čísla medzi 1 a a n, alebo 0 a n,
ekvivalentne, aby celkový súčet.
Takže veľká sigma symbol ktoré by vás mohli vyvolať.
Takže budem robiť, tým prvým volanie volaná funkcia sigma,
prechádzať skrz n, a potom budem hovoria printf, odpoveď je tu.
>> Takže v skratke, som si a int od užívateľa.
Ja sa zabezpečilo, že je to pozitívna.
Prehlasujem premennú s názvom odpoveď typ int a uložiť v ňom návrat
hodnota sigma, odovzdaním n ako vstup.
A potom som vytlačiť túto odpoveď.
>> Bohužiaľ, aj keď znie sigma ako niečo, čo by mohlo byť v
math.h súboru, jeho vyhlásenie, je to v skutočnosti nie je.
Tak to je v poriadku.
Môžem vykonanie tohto sám.
Chystám sa realizovať názvom funkcie sigma, a že to bude trvať
parameter -
Povedzme, že m, len tak to je niečo iné.
A potom tu, budem hovoriť, a, ak je m je menšia ako 1 - jedná sa o
veľmi nezaujímavý program.
Takže budem pokračovať a bezodkladne vrátiť 0.
To jednoducho nedáva zmysel sčítať všetky čísla medzi 1 a M, ak m
je sám o sebe 0 alebo negatívne.
>> A potom budem pokračovať a to veľmi iteratívne.
Chystám sa robiť takéto starej školy, a ja idem do toho
a hovoria, že budem deklarovať sumu za 0.
Potom budem mať pre sláčiky int -
a nechaj ma to urobiť tak, aby zodpovedala Our distribúcia kód, takže máte kópiu
doma. int aj dostane až na 1 i je menšie ako alebo rovná m
aj plus plus.
A potom vnútri tohto cyklu for -
Už sme skoro tam -
Súčet dostane čiastku plus 1.
A potom idem vrátiť čiastku.
>> Tak som to urobil tak rýchlo, celkom pravda.
Ale znovu, ktorého hlavnou funkciou je dosť jednoduchý, založený na kóde sme
napísal tak ďaleko.
Používa dvojaký slučku, aby sa pozitívne int od užívateľa.
Potom som sa prejsť, že int do novej funkcie tzv sigma, volať to opäť n
A ja uložiť návratovú hodnotu, odpoveď z čiernej skrinky v súčasnosti
známy ako Sigma, v premennej volal odpoveď.
Potom som vytlačiť.
>> Ak by sme teraz pokračovať v príbehu, ako je sigma realizovaný?
Navrhujem urobiť takto.
Najprv trochu kontroly chýb aby sa ubezpečil, že používateľ nie je
preberať sa mnou a odovzdaním niektoré negatívne alebo hodnota 0.
Potom som deklarovať premennú s názvom zhrnúť a nastavte ju na hodnotu 0..
>> A teraz sa začne pohybovať aj zo rovná 1 celú cestu až do m,
pretože chcem, aby zahŕňala všetky čísla od jednotky do m vrátane.
A vnútri tohto cyklu for, som jednoducho Súčet dostane, čo je teraz, a
hodnota i
Navyše hodnota i
>> Mimochodom, ak ste to ešte nevideli skôr, je tu nejaký syntaktickú cukor
pre túto linku.
Môžem prepísať ako a rovná i, len zachrániť seba niekoľko klávesových skratiek
a pozrieť sa trochu chladnejšie.
Ale to je všetko.
Je to funkčne to isté.
>> Bohužiaľ, tento kód je nebude kompilovať ešte.
Keď som bežať, aby sigma 0, ako pm Budem sa dostať kričal na?
Aké to bude nepáči?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: Jo, ja nepriznal funkcie až hore, vpravo?
C je tak trochu blbosť, v tom, že iba robí to, čo poviete to urobiť, a vy
musíte urobiť to v tomto poradí.
A tak keď som stlačte klávesu Enter tu, idem dostať varovanie o sigma implicitné
vyhlásenie.
>> Oh, nie je problém.
Môžem ísť až na vrchol, a môžem hovoria, dobre, počkaj.
Sigma je funkcia, ktorá vracia int a očakáva, že
int ako vstup, bodkočiarkou.
Alebo by som mohol dať celú funkciu nad hlavnou, ale všeobecne, tak by som
neodporúčame, pretože to je pekné vždy hlavné hornej časti, aby sa
môžete ponoriť priamo a viem, čo Program robí čítaním hlavnej najskôr.
>> Takže teraz mi dovoľte vyčistiť obrazovku.
Remake sigma 0.
Všetko vyzerá, že check-out.
Dovoľte mi spustiť sigma 0.
Pozitívne inter.
Dám to číslo 3, aby to jednoduché.
Tak, že by mi 3 plus 2 plus 1, tak 6.
Zadajte, a naozaj som si 6.
>> Môžem urobiť niečo väčšieho -
50, 12, 75.
Rovnako ako dotyčnicu, budem robiť niečo smiešne ako naozaj veľký
číslo, Oh, to skutočne dopadlo -
eh, ja si nemyslím, že je to pravda.
Poďme sa pozrieť.
Poďme naozaj si s ním.
>> To je problém.
Čo sa deje?
Kód Nie je to tak zlé.
Je to stále lineárna.
Pískanie je dobrý účinok, hoci.
Čo sa deje?
>> Nie je si istý, či som to počul.
Tak to dopadá - a to je stranou.
To nie je jadrom Myšlienka rekurzia.
Ukazuje sa, pretože ja sa snažím predstavujú tak veľké množstvo, väčšina
pravdepodobne je to byť mylne o C, ako to kladné číslo,
ale záporné číslo.
>> Nehovorili sme o tom, ale je to Ukazuje sa, že sú záporné čísla
vo svete navyše do kladných čísel.
A prostriedky, ktoré môžete predstavujú záporné číslo
v podstate je, že môžete použiť jeden špeciálny bit pre indikáciu
pozitívne na negatívne.
Je to trochu zložitejšie, než to, ale to je základná myšlienka.
>> Takže bohužiaľ, ak C je mätúce z týchto bitov je v skutočnosti znamená,
oh, to je záporné číslo, moja slučka Tu, napríklad, je v skutočnosti nikdy
bude ukončená.
Takže keď som bol vlastne tlače niečo znovu a znovu, by sme
vidieť veľa.
Ale opäť, to je vedľa bodu.
To je naozaj len akýmsi intelektuálne zvedavosť, že prídeme
späť nakoniec.
Ale teraz je to správne Implementácia ak budeme predpokladať, že
užívateľ bude poskytovať ints ktoré zapadajú do ints.
>> Ale tvrdím, že tento kód, úprimne povedané, by sa dalo urobiť oveľa jednoduchšie.
Ak je cieľom po ruke, je prijať rad ako m a sčítať všetky
čísla medzi ním a 1, alebo naopak medzi 1 a, tvrdím,
že môžem požičať myšlienku, že zlúčenie druh mal, ktorý bol s problémami
tejto veľkosti a oddeľujúcich do niečoho menšieho.
Možno nie polovica, ale menšie, ale reprezentatívne rovnaké.
Rovnaký nápad, ale menší problém.
>> Takže som vlastne - dovoľte mi, aby som tento súbor uložiť s iným číslom verzie.
Zavoláme túto verziu 1 miesto 0.
A tvrdím, že som si vlastne reimplement to v tomto druhu
myseľ-ohýbanie cesta.
>> Chystám sa opustiť jeho časť samostatne.
Chystám sa povedať, či m je menej než alebo sa môže dokonca rovnať 0 -
Ja len bude trochu viac análny tentoraz
s mojou kontrolu chýb -
Chystám sa ísť dopredu a vráti 0.
To je ľubovoľná.
Som proste rozhodne, či používateľ mi dáva záporné číslo, ja som
vracia 0, a mali by Prečítal dokumentácie podrobnejšie.
>> Else -
Všimnite si, čo budem robiť.
Inak sa budem vracať M plus -
čo je sigma m?
No, sigma M plus M mínus 1, a m mínus 2 plus mínus 3 m
Nechcem písať všetky tie von.
Prečo proste nemôžem pramice?
Rekurzívne volať sám s mierne menší problém, bodkočiarku,
a nazývať to deň?
>> Je to tak?
Teraz tu taky, možno máte pocit, strach alebo že sa jedná o nekonečnú slučku, že som
vyvolávajúce, kedy som vykonávacích sigma sigma volaním.
Ale to je úplne v poriadku, pretože som myslel dopredu pridal ktoré riadky?
>> DIVÁKOV: [nepočuteľné].
>> DAVID Malan: 23 až 26, ktoré ak je môj stav.
Pretože to, čo je pekné o odčítanie tu, pretože som sa udržať
rozdávajú sigma menšie problémy, menšie problémy, menšie - to nie je
polovičnej veľkosti.
Je to len krôčik menšie, ale to je v poriadku.
Pretože nakoniec, budeme pracovať naša cesta nadol na hodnotu 1 alebo 0.
A akonáhle sa dostaneme 0, sigma nie je zavolá sám už nie.
Bude to okamžite vráti 0.
>> Takže efekt, ak ste trochu vetra tento vo vašej mysli, je pridať M plus
m mínus 1 plus mínus m 2 plus mínus m 3 plus bodka, bodka, bodka, m mínus
m, ktorá vám nakoniec 0, a účinok je nakoniec pridať všetky
tieto veci dohromady.
Takže nemáme s rekurzia, vyriešiť problém, že sa
nemôže vyriešiť skôr.
V skutočnosti, verzia 0 tohto, a každý problém k dnešnému dňu, bol riešiteľný
len s použitím slučky, alebo keď slučky alebo podobné konštrukty.
>> Ale rekurzia, trúfam si povedať, nám dáva iný spôsob uvažovania o
Problémy, ktorým môžeme ak sa problém, rozdeliť ju z niečoho
trochu veľký na niečo trochu menšie, tvrdím, že môžeme vyriešiť
možno trochu viac elegantne, pokiaľ ide konštrukcie, s menej kódu,
a možno aj riešiť problémy, ktoré by bude ťažšie, pretože my budeme nakoniec
vidieť, riešenie čisto iteratívne.
>> Ale Cliffhanger, že som chcieť nechať nás na to bolo.
Nechaj ma ísť dopredu a otvorte sa súbor z -
vlastne, nechaj ma ísť a urobiť naozaj rýchlo.
Nechaj ma ísť napred a navrhnúť nasledujúce.
Medzi dnešné kódu je tento súbor tu.
Tenhle, noswap.
>> Tak to je hlúpy malý program, ktorý Prudko som sa, že tvrdí, že to
nasledujúce.
V zásade sa najprv deklaruje int x volal a priradí ju
hodnota 1.
Potom vyhlási, int y a priradí mu hodnotu 2.
Potom to vytlačí, čo x a y je.
Potom hovorí, vymieňať, dot dot dot.
>> Potom tvrdia, že je volanie funkcie tzv swapu a odovzdať x a
y, myšlienka je, že snáď x a y sa vráti
inak, naopak.
Potom to tvrdí zameniť!
s výkričníkom.
Potom sa vytlačí x a y.
>> Ale ukazuje sa, že práve táto jednoduchá demonštrácia dole
tu je vlastne buggy.
Aj keď som vyhlásil dočasný variabilné a dočasne uvedení v
to, potom som prerozdelenie hodnota b -
ktoré sa cítia rozumné, pretože som uložili kópiu na teplote.
Potom som aktualizovať b rovná všetko, čo bolo v temp.
Tento druh hazardnú hru pohybujúce sa do b a b na použitie tohto
stredného muž menom temp cíti absolútne rozumné.
>> Ale tvrdím, že keď som tento príkaz kód, ako budem robiť teraz -
nechaj ma ísť dopredu a vložte ho sem.
Zavolám tento noswap.c.
A ako už názov napovedá, že to nie je Bude to správny program.
Urobiť noswap. / Nie swap.
x 1, y 2, vymieňať, prehodené.
x je 1, y je 2..
To je zásadná chyba, a to aj aj keď sa to zdá úplne
primerané ku mne.
A je tu dôvod, ale nie sme chystá odhaliť príčinu len zatiaľ.
>> Pre túto chvíľu druhý Cliffhanger som chcel nechať sa je to,
Oznámenie druhov na kupon kódov.
Naše inovácie v neskorých dní tento rok vyvolalo netriviálne počet
otázok, ktorý bol Nie je naším zámerom.
Zámerom týchto kupon kódov, pričom ak tak urobíte časť problému
na začiatku, a tým získať ďalší deň, Bolo to naozaj pomôcť vy pomôcť
sami začať čoskoro, triediť vedľajších motivácie vám.
Nám pomáha distribuovať zaťaženie medzi úradné hodiny tak, aby lepšie
Je to niečo win-win.
>> Bohužiaľ si myslím, že moje inštrukcie neboli do dnešného dňa, veľmi jasné, takže
Vrátil som sa o tomto víkende a aktualizované spec väčšie, odvážnejšie textu na
vysvetliť guľky, ako sú tieto.
A práve to povedať viac verejne, a predvolené, základné problémové okruhy sú dané štvrtok
na poludnie, podľa sylabu.
Ak začnete skoro, dokončovacie časť problém nastaviť v stredu o 12:00
PM, tá časť, ktorá sa vzťahuje k kupón kód, myšlienka je, že môžete rozšíriť
Váš termín pre P nastaviť až do piatku.
To znamená, že odhryzol malú časť P nastaviť voči tomu, čo je zvyčajne
väčší problém a kúpiť si deň naviac.
Opäť platí, že vás dostane premýšľať o tom, Problém set, dostane vás do
úradné hodiny skôr.
Ale kupónu problém je stále potrebné, aj keď nemáte predloží ju.
>> Ale presvedčivo to je.
(Šepot) A tí ľudia odchádza Už sú to ľutovať.
Ako sú ľudia na balkóne.
Ospravedlňujem sa vopred na ľudí na balkón z dôvodov, ktoré budú
jasné, za chvíľu.
>> Tak sme to šťastie, že jeden z CS50 bývalí kolegovia hlava výučby na
spoločnosť s názvom dropbox.com.
Majú veľmi veľkoryso darovali kupon kód tu pre túto toľko miesta,
ktorá je oproti obvyklé 2GB.
Takže to, čo som myslel, že by to na to Posledná poznámka je to trochu prezradí,
pričom za chvíľu budeme odhaliť víťaz a kto má kupón
kód, ktorý potom môžete ísť na ich webové stránky, zadajte do, a voila, získať
oveľa viac priestoru pre vašu Dropbox zariadení a osobných súborov.
>> A prvý, kto by sa chceli zúčastniť v tomto obrázku?
OK, teraz, že je to ešte väčšia zábava.
Osoba, ktorá dostane tento 25-gigabyte kupon kód - čo je oveľa
presvedčivejšie než neskoro dni teraz, možno -
je ten, kto sedí na vrchole sedák, pod ktorým je
že kupónu.
Teraz sa môžete pozrieť pod Váš sedák.
>> [PLAYBACK]
>> -Jeden, dva, tri.
>> [SCREAMING]
>> -Ty si auto!
Získate auto!
>> DAVID Malan: Uvidíme ste v stredu.
>> -Ty si auto!
Získate auto!
>> DAVID Malan: Balkón ľudí, no sem na prednej strane,
kde máme naviac.
>> -Každý dostane auto!
Každý dostane auto!
>> [END PLAYBACK]
>> Rozprávač: V ďalšom CS50 -
>> SPEAKER 5: Ach môj bože bože bože bože bože bože bože bože bože bože -
>> [Ukulele HRY]