[Powered by Google Translate] [3. týždeň, pokračovanie]
>> [David J. Malan - Harvard University]
>> [To je CS50. - CS50.TV]
>> Dobrá. Vitajte späť. To je CS50, a to je koniec týždňa 3.
>> Takže pre tých, ktorí neznámom, v minulom roku začala Harvard, čo sa nazýva Innovation Lab,
alebo i-lab, ktorý je nádherný objekt cez rieku na akademickej pôde HBS tieto
, Ktorá je otvorená pre vysokoškolákov, GSA študentov, študentov z celého areálu,
vrátane fakulty, a to je miesto, kde sa spojili, aby práce na inovatívne veci,
najmä podnikateľské veci
Ak a 0 alebo viac priateľov uvažujete o tom niečo podnikateľského
buď v priebehu tejto triedy, po tejto triedy, alebo mimo.
>> Takže jedna z vecí, ktoré robia cez obdobie J je tieto výlety,
z ktorých jedna je New York, z ktorých jeden je Silicon Valley.
Priestor je veľmi obmedzená, ale je to príležitosť k ramenám s MBA
a postgraduálne študenti z celého areálu a skutočne tráviť čas v týchto jednotlivých oblastiach
chatovanie up rozjazd, chatovanie up podnikatelia a podobne.
Takže v prípade záujmu, pozrite sa na túto adresu tu.
Je tiež k dispozícii na snímkach on-line.
>> Mohli by sme zmierniť domu audio len trochu?
Ak by ste sa k nám pripojiť na obed tento piatok, 13:15 ohňa a ľadu, prosím zamierte tam.
Ospravedlňujem sa, ak je formulár vyplnený už v čase, keď sa tam dostanem.
Ale budeme pokračovať v tejto tradícii ďalej.
>> Dnes budeme pokračovať vyššej úrovne diskusiu o rôznych problémoch, ktoré môžeme riešiť,
zameraním oveľa menej, prinajmenšom dnes, na kóde a oveľa viac na nápady.
Takže myslíte, že späť do týždňa 0, keď sme vytrhol telefónny zoznam v polovici,
ktorého cieľom bolo urobiť niečo, síce trochu dramatické
ale poslať myšlienku, že hľadanie nemusí byť nutne,
ako je zrejmé na prvý pohľad, ako si možno myslíte.
A riešenie problémov všeobecne nemusí vždy nutne byť najlepší -
Najviditeľnejšie riešenie nemusí byť nutne najlepší.
Takže sme mali telefónny zoznam, a úprimne povedané, my všetci v tejto miestnosti mal inštinkty,
s najväčšou pravdepodobnosťou, kto v stredu pri hľadaní Mike Smith a potom ísť vľavo alebo vpravo
zakladať na akékoľvek písmeno abecedy sme náhodou skončiť na.
>> Ale to jednoduchá myšlienka, že my ľudia vzali za samozrejmé tak dlho
Naozaj by sa mal začať do popredia svojej mysle
pretože, ako problémy dostať oveľa zložitejšie, ako telefónny zoznam,
tie isté jednoduché, brilantné postrehy sú, čo sa deje, aby nám
riešiť oveľa zložitejšie a zaujímavejšie problémy,
medzi nimi niektoré veci berieme ako samozrejmosť už v týchto dňoch.
Miliardy webových stránok tam, a napriek tomu Google a Bing a podobne
sú schopní nájsť veci pre nás takto.
To sa nestane pomocou lineárnej hľadanie, prehľadávať všetky možné webových stránok.
Facebook je schopný povedať, kto všetko z vašich priateľov sú alebo priatelia priateľov,
a že tiež môže byť vykonané zdanlivo v okamihu v týchto dňoch
aj keď majú milióny užívateľov.
>> A tak, ako sme vlastne riešiť problémy na tej váhe sa nakoniec zníži
k myšlienkam sme sa zamerali na v týždni 0 a trochu viac dnes.
Nebudeme znova spustiť tento algoritmus, ale spomínam si tiež robil v týždni 0 tomto cvičení
kde sme sa všetci postaviť, vziať na číslo 1,
a potom sme mali všetci self-počítanie škárovaním off, pridaním čísla dohromady,
potom polovica z gangu sa posadil na každej iterácii.
Tak sme išli od 500 študentov 250 - 125 a tak ďalej.
Ale ako sme povedali v pondelok, silná myšlienka, že
bolo, že keď sa zdvojnásobil veľkosť tohto problému
a všetky deti z dvora alebo EC 10 sa vrátil do izby a pripojil sa k nám,
dobre, mohli by sme pravdepodobne počítať, že celý celkovú skupinu
iba s 1 viac veľkom opakovaní slučky, pretože by len možno zdvojnásobiť veľkosť
alebo v EC 10 je prípad trochu viac ako dvojnásobok veľkosti.
A tak by sme museli stráviť trochu viac času,
ale my by sme nemali míňať 400 alebo 700 ďalšie kroky.
>> Len maľovať tento obrázok spôsobom, ktorý je trochu menej abstraktné, nech to nie je už všetci vstať.
Ale ak ti z vás, ktorí sa rozhodli sedieť v orchestri dnes by mi nevadilo postojačky,
uvidíme, či sa nám podarí zistiť z vás, ktorí najvyššej osoba
tým, že robí rovnaký druh porovnávacej algoritmus.
Takže ak sedíte v orchestri, ospravedlňujem sa, ale krok 1, vstať;
krok 2, pár off s nikým blízkosti vás,
zistiť, kto je vyššie, a sadnúť ak ste kratšie.
Potom opakujte.
[Študenti reptania]
>> Dobre.
Dobre. Jeden zostane stáť. Ako sa voláte? Andrew >>.
>> Andrew, si najvyšší osoba v sekcii orchestra dnes.
>> Gratulujeme. [Potlesk a jasot] Dobre. Posaďte sa. Tak sme našli Andrew.
Ako dlho by trvalo mi, napríklad, nájsť Andrew
v tomto orchestri časti 50 + alebo tak ľudí?
Mohol som zobrať pomerne jednoduchý prístup a začať tu.
A ja som 2 ľudia vstať a ja som porovnať ich,
a potom som povedal na toho, kto je o niečo kratšia, "Dobre, si sadnete,"
a budem si pamätať, kto vyššia osoba.
Potom som opakovať, opakovať, opakovať, a ja zavesiť na najvyššej osobe
až nájdem niekoho, o niečo vyššie ako oni, na ktorom mieste
mierne kratšie osoba musí sadnúť.
Ale v tomto algoritmu v tejto časti orchestra, či je n vás,
koľko krokov je to, že algoritmus bude trvať? >> [Študent] N.
>> Bude to trvať n, P, pretože v najhoršom prípade, tak povediac,
najvyššia osoba je úplne posledný človek, ktorého som si len náhodným smolu.
Takže v najhoršom prípade, doba chodu tohto algoritmu je lineárna, je to n,
kde n je celkový počet osôb v priestore, veľkosť problému.
Čo o tomto algoritmu?
Skutočnosť, že ste všetci vstali a potom zase polovica z vás posadil,
polovica z vás sa posadil, polovica z vás posadil.
Koľko krokov by malo, ku ktorým v prípade, že je n z vás?
[Študent] N log n To >> by bolo ešte horšie. Prihlásiť n
>> Takže log n, aj keď nie celkom si spomenúť, čo logaritmus je,
teraz, len oceniť, že sa týka nejako to znížiť a znížiť na polovicu a
Nemusí to byť faktor 2. Mohlo by to byť faktor 3.
Ale to je to opakovanie rovnakého druhu faktora tak, že veľkosť problému začína tu
ale potom okamžite prejde tu, potom tu, potom tu, potom tu.
Nie ste pričom malé uhryznutie z problému, ste naozaj sekanie ďaleko na to
s veľkou ranou zakaždým.
Takže sme mali 50 ľudí, potom 25, potom 12 ½ alebo 13 ľudí stojí,
potom 6 ½ a tak ďalej, až nakoniec len Andrew zostala stáť.
Takže budeme hovoriť, že záznam o n, a môžete si to predstaviť takto.
Pripomeňme tento obrázok tu, kde lineárny algoritmus je ako červenú čiaru tam,
žltá linka bola počítanie 2s algoritmu, ktorý sme použili pre počítanie študentov
v minulosti, ale dnes svätý grál bude aj naďalej táto zelená linka
kde, ak sme zdvojnásobili počet ľudí v orchestri oddielu alebo práve povedal,
sakra, poďme si všetci v celej miestnosti postaviť, nie je tak veľký problém
pretože sme zhruba zdvojnásobí, koľko ľudí je tu dole,
1 ďalšie iterácie, nie je problém.
>> Zistili sme, že Andrew alebo ten, kto sa stane byť vyššia ako Andrew
v medziposchodí alebo na balkón.
Takže tento jednoduchý nápad, že sme sa za niečo tak samozrejmé v telefónnom zozname,
si uvedomiť, že existuje toľko rôznych miest, na ktorých môžeme uplatniť.
Len dať facku nejaký žargón - v skutočnosti skôr než žargón prvý,
nechaj ma ísť na obrázku tu.
Práve teraz sme hovorili o n a n / 2 a potom sa prihláste n,
ale určite prísť, ako budeme v priebehu semestra,
iný druh matematických vzorcov popísať túto všeobecnú predstavu jazdné doby.
Jedná sa mimo kontext pre teraz, pretože uvidíme onedlho
algoritmy, ktoré tieto skutočnosti predstavujú.
>> Ale všimnite si tu lineárne vedenie n, priamka, je v skutočnosti veľmi nízka ukázal práve teraz.
To je niečo ako optické ilúzie, že sme len zmeniť to, čo os x predstavuje
a osi y, a môžeme priamku bod v ktoromkoľvek smere chceme.
Ale dôvod, prečo je to tak zdanlivo byt teraz
je, pretože sme potrebovali, aby sa priestor na tomto grafe oveľa pomalší časoch prevádzky.
Pre túto chvíľu, viem, že tam sú niektoré docela zlé algoritmy v živote,
z ktorých niektoré neberú n kroky, alebo ešte lepšie, log n kroky, ale viac.
Tak nad líniu n tu dole oznámenia je tu n-krát log n,
a uvidíme, čo to znamená onedlho.
Nad tým je n na druhú, a my sme nevideli žiadne n štvorcov algoritmy, ale zatiaľ sa chystáme.
A to vyzerá naozaj zle.
Je tu 2 na n, niečo exponenciálny, ktoré sa cítia ešte horšie.
A napriek tomu, zvedavo, potom je tu n kocky, ktoré, ak ste trochu myslieť dopredu,
Ak typ si to spočítajte, 2 na n skutočne stane veľa rovnejšie,
oveľa vyššie ako n kocky, keď sa pozriete na osiach dosť ďaleko von.
Takže všimnete hneď tieto osi sú ľubovoľne 2-10 na osi x.
>> A čo to znamená?
To znamená, že 2 osoby do 10 ľudí v miestnosti.
To je všetko znamená x: veľkosť problému, bez ohľadu na kontext.
A vertikálna os práve teraz je počet sekúnd, alebo počet krokov -
niektoré jednotku času.
Ale si všimnúť, že je to 0-60 a 0-10.
Ale ak sme trochu vzdialite, ako by ste si mohli v programe Excel alebo nejaké mapovať softvér,
a my sme ísť až na 200.000, zistíte, že niečo ako 2 na n
bude úplne premôcť prevádzkové časy n na druhú,
n kocky, n log n - všetko, čo sme hovorili o tom tak ďaleko.
A napriek tomu úlovok je, keď začnete hovoriť o veciach, ako je Facebook
kde ste veľa, veľa, veľa ľudí všetko je prepojené,
ste n ľudí, môže každý z nich má toľko ako priatelia n
ak všetci je trochu buddy-buddy na svete,
dobre, že to n krát n už tak, že je n štvorcov možné priateľstvo,
aspoň v 1 smere, n mocnín možných priateľstvom.
Takže už naznačuje, že hľadá Facebook je sociálna graf, aby som tak povedal,
môže začať byť vyjadrená v týchto typoch vzorcov.
>> Vrátime sa a robiť to oveľa konkrétnejšie,
ale teraz, cieľ pre budúci mnoho týždňov
bude nesmiete ísť o vykonávacích algoritmov alebo kód
že skončí užívaním toľko času ako niečo ako toto.
Ale fascinujúce vec, o informatike, ak budete pokračovať na v tejto oblasti
pričom triedy ako CS121, CS124, z ktorých oba sú teórie kurzy,
je to, že tam sú vlastne niektoré problémy, ktoré existujú v tomto svete
ktoré zásadným spôsobom, ako ďaleko ako my vieme, nemôže byť vyriešený rýchlejšie
ako najhoršie z týchto grafov skutočne naznačuje.
Takže tam je veľa otvorených problémov v tomto svete, ako to urobiť oveľa lepšie, než ľudia majú tak ďaleko.
>> Tak začnime potom s týmto príkladom.
Videli sme Sean boj s touto kamerou, až príliš nemotorne na videu.
Ale realita bola, keď bol Sean úlohu nájsť na palube takhle číslo 7,
pripomenúť, že som povedal, že "tam je niekde za týmito kúskami papiera alebo biele dvere
"Číslo 7. Sean, nájsť pre nás."
A bolo to úžasne trápne sledovať
pretože on bol naozaj snaží s týmto problémom.
Ale realita bola Sean urobil rovnako ako niekto v miestnosti mohol urobiť.
Vzal niečo dlhšie ako typického človeka môže mať,
ale on predpokladal, že tam bol nejaký trik, aby sa tomuto problému,
on predpokladal, že niečo chýba.
A to nepomáhalo, že stovky očí sa rúti na neho.
>> Ale realita bola, ak vstup do problému, je banda náhodných čísel
a vy ste bol žiadal, aby našiel 1 také číslo,
najlepšie, čo môžete urobiť, je lineárna hľadanie.
Začnite na ľavej strane, presuňte vpravo, alebo začať vpravo, presuňte doľava.
Spätne, môžeme myslieť, "Sean, prečo si jednoducho začať z druhého konca?"
No, mohla 7 sa rovnako ľahko tu náhodne,
ale zámerne som to tam dal, lebo som usúdil, že to nebude začať na konci.
Tak som trochu manipulovať situáciu, ale náhody 7 by mohol byť kdekoľvek.
Takže od pravého konca by mohol byť lepší ako,
ale čo keď budúci rok som sa presunúť 7 inde?
To nie je úplne nové riešenie problému -
od 1 konci, alebo iné - keď ste rovnako žiadne iné predpoklady.
Takže Sean začal hľadať prostredníctvom čísla a on povedal: "5. To tu nie je."
Potom išiel sem a videl 19, potom sa zastavil asi na 20 sekúnd,
potom otvoril to pre 13, a potom sa ukázalo,
že sa nezdá byť vzorec.
Nebolo 1, 2, 3, 4 alebo podobne. Tam boli medzery v číslach, ktoré nepomohlo.
A tiež skutočnosť, že som použil tieto lacné kúsky papiera, aby zakryli čísla
je vlastne úmyselné, pretože keď som odstránil všetky tieto kúsky papiera,
väčšina z nás, Sean vrátane, pravdepodobne by sa pozrel trochu makroskopicky
na tabuľu a povedal: "Ach, 7 je samozrejme tu." Urobili sme to okamžite.
>> A to môže byť spôsob, ako ľudský mozog funguje do istej miery,
ale v skutočnosti, jeho oči alebo myseľ bola pravdepodobne skimming čísla sprava doľava,
zľava doprava, stredné na von - niečo sa deje fyziologicky
také, že pocit, že sa deje okamžite,
ale štatistiky sú ešte vnútorne tam bol nejaký druh metodiky k nájdeniu 7.
A skutočne, teraz hovoríme o poliach a dátových štruktúr
a pamäť vo vnútri počítača, môže jediná vec, my ľudia robia
, Je pozrieť sa na jednotlivé pamäťových miest 1 naraz.
>> Takže každý iné umiestnenie by bolo dobré byť poistený s nejakým kusom papiera
pretože nemôžeme vidieť rovnako. Môžeme robiť len 1 vec naraz.
Takže v tomto prípade, v prípade Seana, išli sme tu a potom sme išli sem
a potom sme išli sem, tu, tu, tu, dostal šikovný do konca
a tak nejako preskočil túto svojvoľne a našiel 7 tam.
Tahle nebola nijako zvlášť výnimočná. To taky bola mimo prevádzky.
Ale nakoniec našiel 7.
Ale teraz takeaway je naozaj to najlepšie, čo môžete urobiť, keď rovnako žiadne informácie
iné ako náhodne zoradená čísel je začať zľava alebo začať sprava.
Alebo sakra, môžete náhodne otvoriť dvere, ale aj potom to, čo to znamená byť náhodné?
No, museli by sme nejako formalizovať, čo to znamená začať tu,
potom kliknite tu, potom kliknite tu. Sean si skvele, a to bolo len zábavné sledovať.
Čo keď namiesto toho budeme meniť je problém trochu a vychovávať tohtoročné Seana, ak chcete?
By niekto byť pohodlné prísť na pódium a riešenie trochu iný problém
a objaviť sa pred kamerou?
>> Poďme za orchestra vy boli docela zapojení už dnes.
Ako asi v ružovej, v klobúku? Poď dole. Aké je vaše meno? >> Alex. >> Alex. Dobre.
Takže Alex bude tohtoročná Sean a objaví sa v najbližších niekoľkých rokoch
hodnote CS50 prednášok.
Alex, rád vás spoznávam. >> Teší ma taky.
Výzva na ruky pre vás je, že ste to trochu jednoduchšie
v tom, že som ti hovorím rovnaké čísla sú tu, ale oni sú teraz zoradené.
Takže teraz vaším cieľom je nájsť číslo 7.
A skutočne, mali by sme naozaj, aby to - Si druh podvádzanie, ako počítač, že nie,
pri pohľade na to, čo tieto čísla bola pred chvíľou.
S kriedou to vlastne je nepomôže tak moc,
ale poďme predstierať, že neviete, čo je pôvodný poľa je.
Všetko, čo viem teraz, je, že máte celý rad zoradená čísel
ktoré by mohli mať medzery medzi nimi, a vaším cieľom je nájsť číslo 7.
Ako by ste, rozumný človek, ísť o zistenie, že počet 7?
>> Prejsť od najnižšej k najvyššej? Dobre >>. Prejsť nízkej na vysokú.
A to netrhá je preč. Poďme zdvihnúť tak môžeme znovu použiť.
Dobre, tak 1. Počkajte. Pred ďalej, to bolo 1, zjavne nesprávne.
Tak čo sa deje skrze svoju myseľ ďalej? Aký je váš ďalší krok?
Ten budúci. Dobre >>. Ten budúci. Dobré. 3, takže nesprávne. Aký je váš ďalší krok?
Pokračovať ďalej. >> Dobre. Pokračovať ďalej. 5.
Takže pokračuj v ceste, a dovoľte mi, aby som vám to odovzdať potomkom.
7. Vynikajúci >>. Veľmi dobrá. Nájdených číslo 7. [Potlesk]
Takže to bolo dobré, ale Sean tiež našiel číslo 7.
A tvrdím, že ste naozaj zneužil túto dodatočnú informáciu,
čo je skutočnosť, že tieto čísla sú zoradené.
Takže môžeme urobiť lepšie? Nejaké návrhy tu? Jo, vzadu.
[Študent] Binárne vyhľadávanie. >> Nemám potuchy, čo binárne hľadanie je.
>> [Študent] Dátum v stredu. Začnite >> v stredu. Dobre. Tak uvidíme, či sa tam môžeme dostať.
Takže ak namiesto toho ste povedal, štart z polovice, choďte do toho a otvoriť prostredné dvere.
Tam je 8 z nich, takže budete mať ľubovoľne vybrať ten
mierne vľavo alebo vpravo. Dobre. 7! [Potlesk] Very nice.
Dobre, ale kde sme ísť s tým?
Predpokladajme, že len preto, aby pretrhnúť ste začali tu
preto, že rovnako by sa stalo tiež.
Práve sme sa náhodou vedieť, že 7 je tam. Tak toto je 13.
Takže ak sú zoradené a začali sme v strede,
čo by optimálne ďalší krok boli?
Prejsť na ľavej. A tak tu je telefónneho zoznamu príklad znovu.
Ak 13 je tu a my vieme, že zoznam je zoradený,
potom všetky tieto kúsky papiera sa nezaujíma nás teraz
pretože už vieme, že 7 musí byť vľavo
ak sú tieto čísla sú zoradené a našli sme 13.
>> Takže aký je tvoj ďalší ťah tu? >> Choďte vľavo. >> Dobre, dobre.
Takže choďte doľava, a - počkajte, hej, hej, hej. To je podvod.
Takže ste našli 7, ale to, čo bolo algoritmus sme práve žiada?
Začnite v stredu. Dobrý >>. Takže to, čo je logickým pokračovaním toho istého nápadu?
Oh, len toto. Presne >>. >> Tak som začať tu. Dobrý >>.
Takže teraz sme išli mierne naľavo znova. Je to 3.
Ale zaujímavé takeaway teraz je, ktorý z nich to nemusíte starať o?
Tieto 2. Tieto 2 >>. Takže teraz to môžeme ísť preč, môže človek ísť preč.
Teraz je problém, že je 8 potom bol veľkosť 4 je teraz veľkosť 2.
Dostávame sa veľmi blízko. Opäť, choďte do stredu týchto 2 prvkov.
>> Dobre. Takže je to trochu škoda, že teraz sme vždy odišiel, pretože sme zaokrúhľovanie smerom nadol.
Ale to je v poriadku, pretože teraz budeme hádzať to preč a všetko ostatné, takže nás len 7.
Dajme potlesk. Našli sme 7 znova. [Potlesk] Dobre. Iste.
Vydrž len 1 sekundu.
Aj napriek tomu, že ďalší proces druh trvalo trochu dlhšie, než sme cítili, že by,
úprimne povedané, vaše prvé inštinkty boli najlepšie, nie? Našli sme 7 okamžite.
Ale my by sme našli 7 rýchlejšie, bez ohľadu na to, čo je v tomto prípade oproti tento jeden
pretože ak sú čísla zoradené všetky, rovnako ako stránky v telefónnom zozname,
môžete naozaj kosiť polovicu problému znovu a znovu a znovu.
A to nie je zďaleka tak jednoduché, aby tento sa len 8 čísiel
na rozdiel od 1000-stránkové telefónny zoznam, kde naozaj vidíte to vizuálne,
ale v tomto prípade, kedy tu Sean hľadal 7,
koľko krokov v najhoršom prípade by to vzali ho? >> [Študent] 7.
7 v najhoršom prípade. No, v najhoršom prípade nie je 7 v prípade, že je to 8 dvere tu.
To by trvalo mu 8 krokov.
>> Takže ak je n dvere, to by mohlo vziať Seana pred pár rokmi n krokov.
Teraz, vo vašom prípade, Alex, pretože tieto čísla sú zoradené -
a môžeme trochu vyvodzujú tohto odkiaľ sme boli tak ďaleko v tomto príbehu -
Čo je doba chodu viac inteligentný algoritmus Alešova
z od stredu a potom zopakovaním?
[Študent] 3. >> Tak to bude 3, hrubo, keď idete 8-4 na 2 až 1.
Takže 3 krokoch, alebo všeobecnejšie, že je log n znovu.
Kedykoľvek ste na polovicu a znížiť na polovicu a a znížiť,
že je vyjadrením tejto myšlienky log n
A tak to by zabralo vám iba 3 kroky, a naozaj to urobil
akonáhle sme otvorili dvere polovicu a znížiť,
vzhľadom k tomu, by to vzali Sean asi 7 alebo 8 krokov.
Takže ďakujem za to, že s nami v tomto roku. >> Ďakujem. Tešilo ma.
Ďakujem Alex. Podobne >>. [Potlesk]
>> Čo je potom skutočný dôsledok toho?
A teraz si predstavte, že to nie je 8 dvere, ktoré, úprimne povedané, to všetko by mohlo z nás nájsť niečo
za 8 dvere docela rýchlo len tým, trhať kusy papiera a ísť s našimi inštinkty.
Ale čo keď je to jeden milión dvere? Čo keď je to 4000000000 dvere?
V prípade 4000000000 dverí, ste naozaj bude chcieť ísť s algoritmom Alešova,
binárne vyhľadávanie podľa začneme volať, alebo rozdeľ a panuj, všeobecnejšie,
kde budete mať polovicu a znížiť problém,
pretože ak máte 4000000000 dvere, môžete koľkokrát ste nakrájame 4000000000 v polovici?
[Študent] 32. >> Je to vlastne 32. Môžete pracovať sa na to na kus papiera alebo vo vašej hlave.
Idete 4 miliardy až 2 miliardy to 1 miliarda pol miliardy, na 250000000, bodka, bodka, bodka.
A ak si z spočítajte, budete skutočne dostať 32,
a že sa v skutočnosti týka informatiky, pretože sme väčšinou počítajú v právomoci 2.
2 k 32 sa stane, že 4 miliardy.
Takže tam je veľa význam pre tieto druhy právomocí 2 v informatike.
>> Ale čo asi 8 miliárd? Koľko krokov je to, že bude trvať, pokiaľ existujú 8000000000 dvere?
[Študent] 33. Tak >> 33. Čo keď tam 16000000000 dvere? Koľko krokov je to, že bude trvať?
[Študent] 34. >> 34. Mohli by sme trochu pokračovať do omrzenia. Ale to je mocná vec.
Môžete zaviesť miliardy viac vstupov na váš problém, ale žiadny veľký problém,
stačí vziať 1 ďalšie sústo z nej, a tak nám dáva niečo ako binárne vyhľadávanie
alebo rozdeľ a panuj, všeobecnejšie.
Ale ja som trochu podvádzal, že jo?
V prípade algoritmu Alex, mala výhodu oproti Seanovi.
Vedela, že tieto čísla boli zoradené, ale Alex nemusel radiť im sama.
Aj v predstihu prišiel k tabuli a druhu sa uistiť,
že som kreslil je všetko v zoradené poradí, potom som doľahla je papierom.
Ale koľko práce to trvalo ma?
Keby sme vyrazili s týmito číslami v niektorých zdanlivo náhodnom poradí -
V tomto prípade táto jednoduchšie čísla, 1 až 8 tu -
ako sme sa ísť o triedení týchto hodnôt?
Ak ste boli človek, rovnako túto úlohu, čo by druh intuitívny prístup budete mať
na triedenie veľa čísel?
Tieto veci boli vyložené ako dieliky puzzle. Jo.
>> [Študent] Ja by som sa jednotlivé čísla a porovnať ho každému
a ďalej doľava. >> Dobre, dobre.
Tak sa každé číslo, prirovnávať to k tej vedľa nej,
a potom už len ďalej pozdĺž zoznamu, typu rejiggering veci tak, ako to je.
Takže tu máme šancu na možno niekoľko viac ľudí zapojiť sa.
Máme 8 ďalšie dobrovoľníkov, ktorí by radi, aby prišli?
Trochu menší tlak, pretože ty nie si jediná. 1, 2, 3, 4, 5, 6, 7, 8.
Poď dole. Vy sa chystáte byť čísla 1 až 8.
Poďme sa pozrieť, či nemôžeme urobiť triedenie pre Alexa veľa rovnakým spôsobom som to urobil v predstihu.
1, 2, 3, 4.
Nehanbite sa a keby ste, line up na javisku medzi hudobným stánku a ja tu
v rovnakom poradí ako na snímke na obrazovke.
Uh-oh.
Budeme s vami pracovať na ďalšom príklade. Oh, počkať, počkať. Ideme na to. Počkajte.
Ďalší príklad je teraz. Tu to máš. Číslo 8. Poď hore.
Dobrá. Triediť sami podľa toho.
Posunutím len malý kúsok na stranu hudby stojí tu.
Takže máme 4, 2, 6 - sa tam dostať, tu, tu - 3.
Jo. Dobre. Môžete ísť sem. Nie, zostaň tam.
Jo, tu. Nie, som v poriadku. Presne tam. Dobre, veľmi dobre. Dobre.
Tak teraz poďme triediť ich do vzostupnom poradí.
>> Ako môžem ísť asi robí?
Algoritmus, ktorý bol navrhnutý pred chvíľou bol dôvod, prečo sa jednoducho tieto
že ľudia, ktorí sú trochu vedľa seba a potom opraviť prípadné chyby,
pohybujúce sa zľava doprava.
Takže tu máme 4 a 2, zrejme mimo prevádzky. Poďme vymeniť vás. Dobre.
Takže teraz budem pohybovať dole riadok. 4 a 6, uzlíkom. [Smiech]
6 a 8, celkom dobre. 8 a 1, dovoľte mi, aby som vám vymenia chlapci. Dobrá.
Takže 8 a 3, vymeniť chlapi.
8 a 7, dovoľte mi, aby som vám vymenia chlapci. 5 a 8, výborná.
Dám vám zoradený zoznam.
Dobrá. Takže nie tak celkom.
Ale je to lepšie, pretože väčší počet - prípadové v bode 8 -
sa druh bublala hore zľava cez doprava.
Tak som dostal 1 z nich pravdu, ale je to pocit, ako že to nie je úplne vyriešiť problém.
>> Takže to, čo by ste navrhol budeme robiť ďalej? >> [Študent] Majte robí. >> Držíme to robí.
A uvedomiť si, opäť, sme sa vydali veci tým, že len majú všetkých ľudí
druh inteligentne dohovoriť sa na základe tohto obrázku,
ale teraz musíme byť oveľa metodicky.
Musíme byť algoritmické o tom, ako by sme písať kód -
v tomto prípade slovnej pseudokódu.
Dovoľte mi teda jednoducho skúste to znova. To fungovalo celkom dobre. Nebolo to vyrieši.
Ale keď to pochybujem, skús a skúste to znova. Takže 2 a 4, nepomohlo už.
4 a 6. Ah! 6 a 1, mierne lepšie.
6 a 3, dobrá. 6 a 7, 7 a 5, 7 a 8, dobrá.
A viete, som asi ignorovať 8 teraz, pretože je na konci zoznamu.
Možno nemáme starať o niekoho, ísť okolo neho.
Ale uvidíme, či je to bezpečný predpoklad.
Teraz je zoznam - sakramentsky - nie je zoradená. Skúsme to znovu.
Takže 2 a 4, 4 a 1, 4 a 3.
4 a 6, dobrý. 6 a 5, dobrá.
6, 7 a 8, dobrá. Ale upozornenie, môžem len zastaviť tu a tu zastaviť teraz?
[Študent] Áno. Jo >>?
Čo ak jeden z vás bol číslo 9 po celú cestu tam?
To by boli roztriedené. Dobrý >>. To by boli roztriedené na prvýkrát.
Dobré. Tak poďme späť. Už tam skoro sme.
1 a 2, 2 a 3, 3 a 4, 4 a 5, 5 a 6, 6 a 7, 7 a 8.
>> Ja som urobil, ale teraz, opäť som počítač, ktorý môže robiť len to, čo som povedal na to,
a moja jediná spomienka je, že teraz som vlastne len urobil trochu práce.
Niečo zmenilo tu.
Tak som sa technicky potvrdené vizuálne alebo algoritmické, že tento zoznam je naozaj zoradené.
Takže len pre istotu, len preto, aby sa análny o tom, poďme urobiť 1 viac času.
Tak 1 a 2, 2 a 3, 3 a 4. A viete čo?
Len pre istotu, budem sledovať na ruke tentoraz
koľko swapy urobím len preto, že viem, koľko práce som vlastne urobil.
3 a 4, 4 a 5, 5 a 6, 6 a 7, 7 a 8. Žiadne swapy.
Takže teraz by som oprávnene idiot to urobiť znovu
pretože keď som žiadnu prácu prostredníctvom tejto priechodu ľuďmi,
potom jasne, že sa to stane znova, ak žiadny z nich nie je nejako náhodne
adversarially pohybujúce sa okolo. Takže teraz môžem zastaviť.
Teraz poďme položiť otázku, koľko práce sa to vlastne so mnou?
Koľko krokov to trvalo? >> N druhú.
Jo, tak n na druhú. Kde beriete n na druhú z?
Musíte sa kontrolovať každý num -
K dispozícii je n čísel, a budete musieť skontrolovať jednotlivé čísla s ostatnými n čísel.
Dobré. Takže >> je to n na druhú. Dobrý >>.
>> Takže to vyzerá, že by mohla byť veľmi dobre n na druhú, nie?
Tam je n z týchto chlapci, 8 konkrétne v tomto prípade,
ale zakaždým, keď som prechádzal tohto zoznamu som bol porovnaním prvej osobe, proti druhej,
jednak proti tretej znovu a znovu a znovu,
a keď som sa dostal na koniec, čo som urobil? Aj prerobil ho.
Takže ak budeme zovšeobecňovať toto vysvetlenie, sme n ľuďom
a ja robím, samozrejme, 8 krokov, n kroky, zakaždým som sa prejsť tohto algoritmu.
Ale koľkokrát v najhoršom prípade musím prejsť tento zoznam ľudí?
[Študent] N krát. Pravdepodobne >> n, P, pretože v najhoršom prípade,
Čo je asi najhorší prípad usporiadania týchto chalanov z get-go?
Ak sa to úplne obrátenom poradí
pretože práve Predpokladám duševne, let 's - Ako sa voláte? >> Bowen.
Bowen. Dobre. Tak Bowen, poď sem na chvíľu.
>> Predpokladajme, že Bowen bol tu na začiatku algoritmu,
a my nevieme, čo všetci ostatní, ale Bowen tu, podľa tohto algoritmu -
a ak chcete len prechádzať so mnou - bude bubliny hore, ako to urobil na prvýkrát,
celú cestu až do konca.
Ale predpokladám, že osoba vedľa Bowen bol číslo 7.
Musím sa vrátiť a dostať číslo 7, čo znamená, že budem musieť ísť celú cestu sem.
Teraz musím mať rovnaký prechádzku s osobou, ktorá je číslo 7.
Ale čo keď bude číslo 6 bol vedľa neho rovnako?
Potom som sa vrátiť a získať 6.
Takže znovu, na každej iterácii tohto cyklu som hovoriť s každým z n ľudí,
a budem musieť urobiť n týchto prechádzky, aby sa ubezpečil som ťahanie
všetky z najväčších prvkov zadnej a späť a späť na samom konci zoznamu.
Takže n vecí n krát, je len n krát n alebo n na druhú.
>> Tak tu už máme algoritmus, ktorý je už n, to je už log n,
je to vlastne ešte horšie, ako čokoľvek, čo sme robili predtým.
Takže Alex druh šťastie v tom, že som všetky práce zrejme do prednej pre ňu,
všetky drahé práce, tak, že sa môže užiť v tomto binárnom algoritmu,
ktorý je log n
Ale to je v súlade s témou pondelkového.
Dali sme o trochu viac priestoru, sme použili viac bitov, s cieľom urýchliť náš hrací čas.
Toľko, ako by ich to kompromis medzi časom a priestorom,
tu môže tiež byť len kompromisy medzi čas strávený sa predné druh na získanie veci pripravený ísť
a skutočne behu algoritmu, ako je vyhľadávanie. Skúsme iný.
Ak ste to nevadilo len rýchlo preskupiť sami tak, aby zodpovedala znovu,
Poďme skúsiť niečo trochu iné, ak to nie je tak jednoduché,
ako len opraviť všetky párové chyby, čo je výborný intuitívne.
Poďme namiesto toho byť trochu viac úmyselné a urobiť to.
To tiež by som navrhnúť, je asi dosť intuitívne.
>> Poďme vyberte najmenší osobu zo zoznamu znovu a znovu. Tak ideme na to.
4, vy ste najmenší človek, ktorého som tak videl tak ďaleko,
takže budem psychicky si uvedomiť, že tým, že len ukazuje na teba teraz.
2. Ooh! Zabudnite na číslo 4. Našiel som nový najmenší prvok v tomto zozname.
Idem na druhu pamäti, že. 6, 8.
Ooh! 1. Dovidenia. Takže teraz budem pamätať číslo 1.
Vieme, že 1 je najmenší, ale ja som počítač. Čo keď tam 0?
Čo keď tam -1? Musím ísť ďalej.
Takže 3, 7, 5, uzlíkom. Dobre. Takže číslo 1 bol najmenší.
Dovoľte mi, aby som vás vybrať zo zoznamu - Dáme ísť touto cestou -
a ťa ľubovoľne na začiatku zoznamu.
Teraz, počkaj. Tak nejako som podvedený.
Ak títo ľudia predstavujú nie zoznam 8 ľudí, ale pole,
8 kusy súvislé pamäte - nevadí vám ustúpil len na chvíľu?
Je tu vlastne žiadny priestor pre vás tu.
Tak ako sme sa vytvoriť priestor pre - Ako sa voláte? >> Sammy. >> Sammy.
Ako sme tak priestor pre Sammy?
>> Sťahujeme sa n, ktoré sú predo mnou. Dobre >>.
Takže by sme mohli presunúť n ľudí, ktorí sú pred ním,
takže ak ste chcieť vziať 1 úmyselné, dramatický krok doľava.
Všetci robili, že v súzvuku, ale minule som písal nejaký kód,
nemôžete nejako pohnúť veľa vecí naraz.
Mohli by sme to urobiť v slučke, pohybujúce sa každý raz za čas.
Takže ak ste to nevadilo ustúpil doprava,
a Sammy, ak by ste mohli krok späť, pretože je tu ešte žiadny priestor pre vás,
Teraz ideme na to. Ak bol Sammy pred chvíľou? Presne tam.
Takže tam je medzera tam. Takže by ste mohli presunúť do miesta Sammyho.
Teraz ďalšia osoba a teraz ďalší človek, teraz ďalšia osoba. Teraz máme priestor pre Sammyho.
Teraz, niekto z publika - to bolo dobré, že bolo správne,
bolo to trochu časovo náročné - to, čo je rýchlejšie? Jo.
[Študent] nové pole? >> Čo je to? >> [Študent] nové pole? >> Dobre, dobre.
>> Takže v súlade s touto tematikou len kompromisy, prečo jednoducho nemôžem urobiť nové pole
a potom Sammy bude plávať v priestore pred týmito ľuďmi, napríklad,
a my môžeme len začať vyplnením nové pole úplne. To taky bude fungovať.
Ale ja nemám záujem tráviť viac priestoru dnes. Čo je to iný prístup?
[Študent] Swap. Dobre >>. Mohli by sme vymeniť tieto 2 ľudí. Ako sa voláte?
Mario. >> Mario. Takže Mario, si práve tu.
Sammy, môžete zálohovať len na chvíľu? Mario je tu.
Nemáme priestor pre vás už, takže ak by vám nevadilo ísť na miesto, kde Sammy je,
dáme Sammy tu, a teraz by som tvrdiť, že Sammy je vymieňať operácia bola oveľa rýchlejšia.
Urobili sme 1 operáciu vymeniť týchto ľudí, alebo možno 2 vymeniť týchto ľudí,
ale my sme to neurobili 1, 2, 3, 4, takže sa cítia lepšie. Teraz, počkaj.
Tak nejako som robil problém ešte horšie, pretože číslo 4 bolo celkom blízko k začiatku.
Teraz číslo 4 je o niečo bližšie k tomuto cieľu, ale ja som naozaj nevedel, alebo sa starať o to.
Takže je to len smola, že číslo 4 je o kúsok ďalej od svojho určeného miesta.
Takže poďme sa teraz opakovať tento algoritmus.
>> Zhrnúť, tak dlho, ako ten príbeh bol, všetko, čo sme urobili, bolo prejsť zoznam
hľadá pre najmenších číslované osoby.
Tak teraz poďme urobiť to znova. Nemáme sa báť Sammy už.
Môžeme len ísť sem. Ooh! Číslo 2. To je dosť malé číslo.
6, 8, 4, 3, 7, 5. Dobre, dobre.
A našťastie, zhodou okolností, nemám sa pohybovať - ​​>> Willie.
Willie preto, že je na jeho pravé miesto teraz.
Poďme to urobiť znovu a ignorovať tieto 2 ľudí.
6. To je dosť malé číslo. Ooh! 8 je určite väčšia.
4. Zamerajme sa na 4. Ooh! 3 je ešte lepší.
7 a 5. Tak čo teraz budeme robiť s - >> Roger. >> Roger?
Poďme vymeniť ho s číslom 6.
Takže ak 6 a 3 by chceli vymeniť,
sme teraz trochu dostal šťastie v tom 6 je bližšie k miestu, kde by mal byť,
ale je to len náhoda tu. Takže poďme sa teraz ísť sem.
8 je dosť malé číslo. Ooh! 4 je menšie.
6, 7, 5. Čo budeme teraz robiť? >> Swap. Presne >>.
Tak teraz poďme urobiť tento druh rýchlejšie.
8, 6, 7, 5. Kam 5 ísť? Dobré. Dobre.
6, 7, 8. 6 dostane zostať, kde je. Ako sa voláte? >> Rosalie.
Rosalie dostane zostať, kde je. 7 dostane - Poďme sa pozrieť,. 7, 8. Dobre.
Takže 7 dostane zostať, kde je. Ako sa voláte? >> Amna. >> Amna.
>> Takže Amna dostane zostať, kde je, a číslo 8 je už tam, kde sa teraz malo byť.
Dobre, dobre. Pocit, ako sme len vytvárať prácu pre seba tu, hoci.
Čo je to nakoniec doba chodu tohto algoritmu?
Ak budeme uvažovať o týchto ľuďoch nie ako 8, ale ako n? >> Je to n
Je to n krokov, ale my sme kontrolu zakaždým.
Dobre. N, ale máte kontrolu zakaždým?
Dobre, ale ak je to n krokov, nemal som bol schopný triediť vás len tak 1, 2, 3, 4?
Oh! Dobre, to je veľký rozdiel.
Tak n štvorcový prečo? Čo sa vlastne deje?
Tam je n ľudí v tomto zozname, ale nájsť najmenší osobu v zozname
v najhoršom prípade, koľko krokov musím vziať? N. >>
>> N, P, pretože v najhoršom prípade, číslo 1 je úplne tam,
takže musím ísť ho alebo ju.
A potom, keď som sa konečne uvedomiť, 1 bol najmenší, potom je to celkom rýchlo vymeniť je.
Ale teraz musím začať od začiatku a pozrieť sa na koho?
Ďalšie Najmenší človek, ktorý je 2. Ak sa v najhoršom prípade je 2?
Ach, môj Bože. Je to všetko tak tu na konci.
Takže teraz som práve urobil ďalší n krokov, ďalšie n kroky.
A ak máme n ľudí a v najhoršom prípade najmenšie osoba n krokov,
to je zase n-krát n, a tak sme opäť sa n na druhú.
To nie je pocit tak dobre.
A v skutočnosti, dokonca v najlepšom prípade - predpokladám, že začať zoradené -
koľko krokov to trvať pre mňa použitie tohto algoritmu pre triedenie týchto n ľudí?
N vzpriamil. >> Počul som n na druhú. Prečo n štvorcový?
Pretože stále máte skontrolovať zakaždým. Jo >>.
A vy budete musieť vymeniť je. >> Aj keď my, ľudia sú trochu vševediaci
v tom zmysle, vizuálne, že môžeme len tak vidieť, že je to zoradená,
počítač nie je tak šikovný.
Bude to vyzerať tu a tu a tu,
ale ak to, čo hľadá, je najmenší prvok,
si len, že ste našiel najmenší prvok tým, čo ide? Akonáhle ste na konci.
Ale v tomto bode ste len našli práve najmenší prvok.
Nemusíte nutne vedieť niečo o stave sveta.
Takže budete musieť ísť znova a znova a znova.
>> Takže tentoraz som naozaj vyzerať hlúpy, pretože som kontrolu, v poriadku, 2, si najmenší,
ale ja neviem, že celkom zatiaľ.
3, 4, 5, 6, 7, 8. Dobre, dobre. 2 bol naozaj najmenší.
Teraz poďme nájsť ďalšie najmenší. Dobre.
3, ste v súčasnej dobe najmenší. Poďme sa pozrieť,. 4, 5, 6, 7, 8. Dobre, mám šťastie znova.
3 bol naozaj na správnom mieste. Ale budem to robiť znova a znova a znova.
Ako môžeme urobiť niekedy tak trochu lepšie?
Namiesto toho, aby ľudia vyvierajú po dvoch od najmenšej k najväčšej
a namiesto toho tam a späť v zozname výberu vtedy najmenší osobu,
prečo sa namiesto toho vložiť tých ľudí do nového zoznamu krok za krokom?
Skúsme to. Teraz mi dovoľte volať túto vec vloženie radenie.
Tak tu sme tu. Číslo 1. Ja sa nestarám o nikoho iného v tomto zozname.
Mojím cieľom teraz je, aby číslo 1 na začiatku triedeného zoznamu.
A ja budem navrhovať, pretože mám iba 8 kusy pamäti,
ľubovoľne teraz som múr medzi moje údajne netriedeného zoznamu,
a každý, kto je za mnou budem tvrdiť, je zoradená.
Takže teraz máme číslo 1.
Chcem vložiť ho do môjho zoznamu zoradené, takže som len tak pohnúť múru tu,
a teraz tvrdím, tento zoznam je triedený, je tento zoznam netriedené - aspoň pokiaľ viem.
Nevidím všetky čísla naraz.
>> Teraz som náhodou stretnúť číslo 2. Čo mám robiť s ním?
Aj vložiť ťa teraz do triedeného zoznamu. Ale všimnite si, ako jednoduché to bolo.
Len som sa pozrieť. Číslo 1 je tam. Jo, samozrejme 2 ide na stranu číslo 1.
Teraz, čo mám robiť s 3? Aj vložiť ťa do triedeného zoznamu. Ale to bolo super ľahké.
To je super ľahké, to je super ľahké, to je super ľahké, super ľahké, super ľahké.
A teraz všetko je vyriešené za mnou, a koľko krokov to trvalo?
[Študenti] N. >> Tak je to len n Mali sme šťastie.
To bolo len n prečo? >> [Študent] Vzhľadom k tomu, že bol zoznam zoradené.
Zoznam už je zoradený. Takže sme mali šťastie.
Ale sme navrhli algoritmus, tentoraz ktorá využíva tento druh šťastia,
že najlepším prípade tým, že strácať zbytočne čas.
Takže teraz máme, čo budeme hovoriť bublina druhy
kde ľudia druh bubliny do párových.
Teraz máme výber druhu, kde sme vytrhnúť najmenší osoba znovu a znovu.
A teraz máme textový druh, kde sme trochu aktívne dať ľuďom tam, kam patrí
v stále triedenom zozname.
Ak by sme mohli, potlesk pre týchto ľudí tu. [Potlesk]
Poďme vziať našu 5-minút prestávku tu.
A keď sa vráti, budeme fúkať všetky tieto algoritmy z vody
s niečím lepším. Dobrá. Díky moc. Môžete udržať tie ako suveníry.
Dobrá. Sme späť.
>> A zhrnúť veľmi rýchlo, museli sme tieto 3 rôzne prístupy k triedenia,
celý bod, ktorý bol sa dostať do bodu, kedy niekto ako Alex
mohol vyhľadávať zoznam čísel rýchlejšie ako niekoho, ako je Sean mohol.
A aj keď máme také jednoduché príklady s číslami 8,
môžete extrapolovať ľahko až 8 webových stránok, 8 miliárd webových stránok,
alebo 800000000 priateľov na Facebooku.
Takže tieto algoritmy možno určite škálovať až na tie druhy hodnôt,
a myšlienky sú nakoniec rovnaký.
Takže bublina sort bola prvá, kde sme trochu bublala do najvyššej osobu
úplne vpravo tým, že vymení ľudí po dvoch.
Potom sme mali, čo budeme hovoriť výber druhu, kde som trochu viac úmyselne
stále hľadá v zozname, výberom najmenšie číslo znovu a znovu a znovu,
logickým výsledkom je, že zoznam je nakoniec zoradené.
Potom v tretej, vložil som ľudí do ich vhodnom mieste,
a sme veľmi vymyslel príklad v tom, že zoznam bol už je zoradený,
ale to bolo pre odoslanie správy, že v vkladacieho radiť tieto veci,
môžete mať šťastie.
Ak sú čísla už je zoradený, je to len bude vás n kroky na potvrdenie toľko,
vzhľadom k tomu, výberu radiť ste trochu tunelové videnie
a nemusíte vôbec uvedomiť, že zoznam už je zoradený.
Tak uvidíme, bublina radenie v akcii tu.
V nasledujúcom príklade, chystáme sa objaviť zvislé pruhy
ktorých výška predstavujú čísla, takže môžeme nejako Vizualizácia triedenia sa stalo.
Čím menší bar, tým menšie je číslo, tým väčšia bar, tým väčší počet.
>> A budeme hrať v tomto implicitné rýchlosť.
Bude to presunúť trochu rýchlo pre túto chvíľu, ale červená je to, čo sa ukazuje 2 tyče
je v porovnaní vedľa seba.
A keď sa budete pozerať pozorne, čo sa stane, je, že ak bary sú mimo prevádzky,
menší z nich sa presunie doľava, ten väčší vpravo,
a potom budete mať postupujúci.
Takže keď sme to znova a znova, zistili, že najmenšie tyče
sa bude držať tipovacej svoju cestu doľava
a najväčšie tyče budú držať tipovacej svoju cestu vpravo.
A skutočne, začíname vidieť vzor celú cestu na pravej strane
rovnako ako sme videli 8 a potom 7 nakoniec vyviera až na koniec nášho ľudského zoznamu.
Takže to bude veľmi rýchlo dostať trochu únavné, tak nech mi to zastaviť na chvíľu.
Dovoľte mi, aby som meniť rýchlosť je oveľa rýchlejší.
Nie som zmenu algoritmu, ja len robiť animácie stalo rýchlejšie.
Napriek tomu bublina sort, rovnaký algoritmus,
ale teraz môžete vidieť oveľa rýchlejšie ako naša slovná demonštrácie
že najväčší prvky sú naozaj bublať až na vrchol.
>> Ako stranou, tieto malé štvorčeky v ľavom dolnom rohu a pravom dolnom
sú len malé pripomenutie ako na to, koľko porovnaní robíte.
Ale teraz, môžeme sa sústrediť na pyramídy, ktorý je formuje, a tam to ide.
Najmenší prvok je na ľavej strane, najväčší na pravej strane, a všetko ostatné medzi tým.
Teraz poďme miesto sa pozrieť na výber druhu.
Chystám sa ísť dopredu a udrel Stop. Budeme si novú náhodnú sadu tyčí.
Výber druhu, odvolanie, prechádza v zozname znovu a znovu a znovu,
šklbanie sa na najmenší prvok. Takže tu je výber sort.
Vyzerá to, že tam je menej práce sa deje teraz, pretože nie sme nákupný párovaný
ale my sme tak nejako zneužité najmenšie prvky sprava doľava.
To trvalo veľmi málo času, takže je dichotómia už.
Len preto, že algoritmus je povedal, aby n štvorcový čas, rovnako ako bubliny radiť
a ako výber druhu, ktoré sú naozaj najhorší prípad doby chodu.
Napríklad, v prípade, povedzme, výber druhu,
Vlastne som som výber najmenšie osobu a dávať ho alebo ju sem,
potom som to zase robíš, potom som to zase robíš,
ale došlo k miernemu optimalizácia som mohol robiť.
>> Akonáhle som sa presťahoval číslo 1 tu - Sammy v tomto prípade -
čo som potrebné urobiť s ním potom? >> [Študent] Nechajte ho.
Nechajte ho, že jo? Nič.
Nepotreboval som, aby niekedy hovoriť s Sammyho znova, pretože keď som vybrala najmenší prvok
a dal ho sem, prečo strácať čas ísť na koniec celom mojom zozname?
Na ďalšej iterácii dovoľte mi, aby som skutočne pohybovať len číslo 2, iba čísla 3.
Takže v skutočnosti, som nerobil n veci n časy.
Robil som n vecí, potom n - 1 veci, potom n - 2 veci, potom n - 3 veci,
potom n - 4, bodka, bodka, bodka.
Máme trochu geometrickom rade, ktorá práve znamená
pridávate do postupne menší počet.
Nie n + n + n + n, ale n + 7 + 6 + 5 + 4 + 3 + 2 + 1.
A čo, že všeobecne funguje ako -
Idem pokaziť mojej doske tu len na chvíľu -
že to bude fungovať, že je niečo ako n (n - 1) / 2
keby sme tak nejako pohľad na zadnej časti učebnice matematiky, kde máte všetky ťaháky
Ku vzorcom.
Ak ste práve pridaním niečo n + n - 1 + n - 2, to vyjde za niečo také.
A ak by sme to proste množia na to, že je n na druhú mínus n / 2.
Stále som hovoril n na druhú, aj keď, a to preto, že som bol trochu pri duševnej skratky
pretože v skutočnosti, n na druhú mínus n deleno 2 je naozaj skutočný počet krokov
že algoritmus ako výber druhu by sa, ak naozaj sčítajú
Zo všetkých týchto porovnaní a všetky malé rušné prácu, ktorú sme robili.
Ale úprimne povedané, akonáhle sa dostane n byť ako milión alebo miliardu, kto to sakra zaujíma
ak robíte miliardu na druhú mínus miliardy rozdelenej 2?
Miliardy na druhú je obrovské množstvo.
Môžete si vziať ďalšie miliardy z nej s - n Nie je to tak veľký problém.
Takže čím väčšie čísla sa, že menej dôležité tieto nižšie objednané termíny sú.
Koho zaujíma, či ste deliť 2, ak hovoríte o kvadriliony o počte krokov?
>> Takže všeobecne, počítačoví odborníci majú tendenciu vyhadzovať všetko, ale najväčšie termín,
a my sme tak nejako zjednodušiť svet a povedať, že algoritmus
sa zhruba n druhú kroky. To je doba chodu algoritmu.
Takže sa vrátime k tomu za chvíľu s niektorými konkrétnymi príkladmi,
ale teraz, že je to niečo ako intuitívne motivácie za práve zjednodušenie náš svet
a hovorí o najdôležitejších pojmov, skôr než dostať sa do všetkých týchto fantázie vzorcov.
Takže to bol výber triedenia, a máme trochu šťastia tam.
Poďme sa pozrieť na vloženie radiť. Nechaj ma ísť napred a začať túto rovnako.
Teraz si všimnite vzor, ​​ktorý sa deje, je trochu iný,
a začali sme s náhodnými číslami,
ale ak sme skutočne počítať počet krokov v najhoršom prípade,
v prípade, že zoznam začal úplne v správnom poradí,
by sme trvať len n kroky k realizácii toľko.
>> Ale v prípade, že sú v skutočnosti zoznam dozadu - napríklad, v tomto prípade sa tu -
potom všimnete skutočnosti máme urobiť oveľa viac práce v tomto prípade.
A to by malo trochu pocit, pre Vás, ako toto je druh pracovať usilovnejšie
dostať tie menšie prvky vľavo, a to preto, že sme sa dostali smolu.
Zoznam bol zoradené náhodne opačne.
Naopak, s vloženie radiť keby sme napodobňovať to, čo sme urobili s našimi ľuďmi tu
tým, že začína s každým zoradené a potom začať, je to celkom dobrý algoritmus, nie?
Je to už v skutočnosti, sú zoradené.
Takže poďme sa pokúsiť zhrnúť, koľko času tieto veci berú nám
zavedením len trochu žargónu alebo notácie, ktorá je v skutočnosti oveľa jednoduchšie,
ako fanciness druh naznačuje.
To, čo tu, tento veľký O na obrazovke, je to, čo počítačový vedec bude všeobecne používať
popísať najhoršie čas behu algoritmu.
>> Opäť, v najhoršom prípade, je to úplne závislé na kontexte.
Čo máme na mysli najhoršom prípade úplne sa líši v závislosti na probléme hovoríme o
Ale v prípade triedenia, čo je najhorší možný scenár?
Všetko je pospiatky, pretože to jednoducho pripadá ako to znamená veľa práce za nás.
Ja som poznačil niekoľko algoritmov, ktoré sme videli doteraz:
lineárne vyhľadávanie, binárne vyhľadávanie ako s telefónnom zozname alebo kúsky papiera,
potom bublina sort, výber sort, a vloženie sort, ako sme videli s našimi ľuďmi,
a potom 1 oznámi, že to nakoniec bude nazývaný zlúčenie radenie.
Takže v lineárne hľadanie v najhoršom prípade, koľko krokov to trvať nájsť číslo 7
ak existujú n dvere ako Sean Tvárou v tvár? >> [Študent] N.
N. Takže budeme písať veľkú O n.
Idem len vyplniť v niektorých medzier. To je len mriežka polotovarov.
Ale v najlepšom prípade s lineárnou hľadanie, možno 7 boli na samom začiatku zoznamu,
a Sean mohol začať pozerať na začiatku zoznamu.
Takže ak používate lineárne vyhľadávanie a len kontrolovať zľava doprava alebo možno sprava doľava -
sú rovnocenné - v najlepšom prípade, koľko krokov by mohol lineárne vyhľadávanie,
ako algoritmus Seana, vziať? Len 1 krok.
>> Tak som chcel povedať, že je to omega notácie.
To je len hlavné omega.
Omega je len sexy spôsob, ako povedať najlepšom prípade jazdnej doby.
Takže v najlepšom prípade hrací čas je jeden krok, alebo konštantný počet krokov -
1 v tomto prípade - ale v najhoršom prípade, veľký O, to je vlastne n krokov.
A tento tu, theta, my vlastne ani pozerať na práve teraz.
To nie je relevantné pre tento konkrétny príklad.
Ale teraz skúsme binárne vyhľadávanie.
V najhoršom prípade sa binárne vyhľadávanie, koľko krokov je to bude trvať nájsť číslo 7
alebo čokoľvek, čo ste hľadali? >> [Študent] Log n
Stále bude trvať log n, pretože rovnako ako Alex dostal smolu
keď sme naozaj pracovali cez problému metodicky
a ona nenašla číslo 7 až do poslednej dverí sa pozrel na,
aj keď, v spravodlivosť, dostala vyhodiť niektoré dvere pozdĺž cesty,
binárne hľadanie v najhoršom prípade má hrací čas log n
A opäť, že hovorí k tomuto deleniu a dobývania.
Ale čo v najlepšom prípade?
A Alex vlastne zažil, že najlepšia vec pravdu, keď prišla na pódium.
Koľko krokov to trvalo v binárnom vyhľadávaní? >> [Študent] 1.
1, len preto, že mali šťastie.
Ale to je v poriadku, pretože omega sa týka najlepších scenárov,
najlepšom prípade vstupov, aj keď je to len náhodný nemé šťastie.
>> Teraz, toto príliš budeme len druh Ponechajte prázdne pre teraz.
Ako teraz bublina trochu?
V najhoršom prípade sa bubliny radiť, každý je v opačnom poradí,
takže musíme urobiť veľa bublín.
Ale koľko krokov je to, že bude trvať v najhoršom prípade? >> [Študent] N druhú.
To bolo n na druhú, pretože ak si myslíte, že o tom,
ak je zoznam úplne dozadu - 8 je tu, 1 je tu -
ako vec, začnú bubliny, číslo 8 sa bude pohybovať takto, takto,
Týmto spôsobom, týmto spôsobom, ale kde je číslo 7 v najhoršom prípade?
Tu je stále tam. Tak sme to urobiť znovu a znovu.
A to je miesto, kde sme si n krokov, potom n - 1 krokov, potom n - 2 stupne.
A ak budete mať svoje slovo pre to - že ak druh množiť to,
je to zhruba n opracované na konci s niektorými ďalšími podmienkami, ktoré budeme jednoducho ignorovať zatiaľ -
potom v najhoršom prípade druhu bublinkové je n na druhú, dávať alebo brať.
Ale čo najlepšom prípade s bublinou radiť?
Aký je najlepší možný scenár? Všetky čísel sú zoradené už.
A čo bolo heuristický som, trik som použil,
uvedomiť si, že som urobil žiadnu prácu, a mohol preto zastaviť skôr?
[Študent] Skontrolujte raz. Skontrolujte >> raz. Ale čo som robil na ceste?
Bol som sledovanie, koľko swapy som.
A uvedomil som si, či som nepočítal žiadne swapy na prstoch, potom som urobil žiadnu prácu.
Určite by sa nemala snažiť robiť žiadnu prácu znova, tak som si jednoducho prestať.
>> Takže v najlepšom prípade bublín druhu, ak je už zoznam zoradené,
čo by ste povedali zápis omega je, v najlepšom prípade beží čas?
Je to len n Musíme urobiť nejakú prácu, ale máme len urobiť 1 prechádzku stojí za prácu.
A tu taky budem dovolenky v tejto časti prázdne.
A teraz výber sort.
Výber radenie sa mi, že zahrá na najmenšie osoba znovu a znovu.
A čo na to hovoríme, že doba chodu to bolo?
To bolo n narovnal v najhoršom prípade.
A bohužiaľ, v najlepšom prípade je to tiež n na druhú
pretože nemám ten typ vševedúci pohľadu celého sveta;
Ja len viem, na úplné opakovanie, že som skutočne našiel najmenší osobu.
Takže výber druh druh nasáva v tomto zmysle,
ale Výhodou je je to trochu intuitívne.
Je to celkom jednoduché kód, pretože všetko, čo musíte urobiť, je napísať pár vnorených slučiek pre,
typicky, ktorá prechádza hľadá najmenší prvok
a umiestni najmenší prvok kam patrí na konci zoznamu.
Takže aj tu to bude trade-off.
Množstvo času to trvá vám premýšľať a skutočne vyvinúť niečo o písaní kódu
môže veľmi dobre mať viac času, ak chcete lepšie algoritmus a rýchlejší výkon.
>> Ale ak ste naozaj len trochu kódu niečo do rýchle a špinavé
a tak nejako sa tá najhlúpejší možnú predstavu si môžete myslieť,
, Ktoré by mohli trvať aj niekoľko minút kódu, ale s veľkými súbormi dát
Vaša algoritmus môže trvať niekoľko hodín bežať.
A dokonca som v postgraduálnom štúdiu by niekedy robiť tieto kompromisy.
Bolo by 3am, som sa snažil analyzovať niektoré veľmi veľké dátové sady
vzťahujúce sa k výskumu bezpečnosti som robil, a to bol jeden stráviť 5 minút
ladením svoj program analyzovať dáta a ísť spať
alebo stráviť 8 hodín ako sa to práve preto, že beží okamžite a ísť spať.
A tak tam taky je to trochu z vedomého rozhodnutia.
Menej doba vývoja, viac spánku.
V spätnom pohľade, by som asi nemala podporovať, aby
keď cieľom je optimalizovať kvalitu kódu,
ale aj to v reálnom svete, je veľmi rozumné trade-off.
Menej času, menej výkonu alebo naopak.
Takže tu máme konečne šancu hovoriť o theta.
Theta notácie je niečo, čo počítačoví experti môžu priniesť v rozhovore
keď veľké O a omega náhodou rovnaké.
Hovoríte, že theta naozaj poslať správu, že toto je pevne viazaný.
Bez ohľadu na to, či scenár je dobré alebo zlé, je to n na druhú.
Tak to jednoducho nie je relevantné v týchto príbehoch tu.
Vloženie druh je posledný sme sa na,
kde som bol jednoduchým vložením každého na správnom mieste.
V najlepšom prípade to, čo bolo doba chodu inzercia druhu, ako sme to videli tu?
[Študent] Najlepší prípad? >> Najlepší prípad.
>> To bolo n preto, že v najlepšom prípade všetci sú zoradené,
a Sammy a nikto iný naozaj musel pohybovať vôbec.
Boli už v ich správnom mieste.
Takže vloženie radenie v najlepšom prípade je v tomto prípade, n
Ale v najhoršom prípade je to trochu n na druhú. Prečo?
Ak môj zoznam ľudí je v opačnom poradí,
Prvýkrát som začať s číslom 8 a vložím ho alebo ju do správnej polohy, čo je tu.
Aj druh pohybu do strany. Títo chalani sú netriedené, že on alebo ona je zoradený.
Ale teraz som sa náhodou zistiť, kto ďalší? >> [Študent] 7.
7 v najhoršom prípade, pretože je to v opačnom poradí.
>> Takže tu je 7. Kde 7 patrí? Určite za mnou.
Ale teraz 7 vlastne patrí nie je bezprostredne za mnou, ale za číslom 8,
tak musím povedať: "Prepáčte, číslo 8, môžete mi prosím presunúť túto cestu
"Aby sa vytvoril priestor pre 7?" Teraz som stretávajú 6.
"Ach, prepáčte, číslo 8 a číslo 7, môžete prejsť, aby sa priestor pre 6?"
Takže inými slovami, s vloženie radiť, aj keď nerobím moc pohybu,
ľudia za mnou robia oveľa viac práce, a to má stáť niekoho čas.
Bude to stať sa počítačového času.
Takže v prípade vloženia radiť stále trpí.
Ak začnete pridávať do celkového počtu krokov, sme skončiť biť nahrubo opracované n
pretože títo ľudia potrebujú, aby sa priestor pre človeka byť vložený späť do tohto zoznamu.
A tak je v tomto prípade theta jednoducho nie je použiteľná pre konkrétneho príbehu po ruke.
To je všetko pekné a dobré. Máme tieto 3 rôzne spôsoby hovoril o dobe chodu.
Ale čo to vlastne znamená v reálnych podmienkach, ak sa skutočne snaží, aby kód sa algoritmus?
>> Dovoľte mi, aby som navrhla, že tam je to ešte lepšie algoritmus tam
, Ktorý sám má nejaké kompromisy.
Budeme hovoriť, že zlúčenie druh, a to trochu tohto čarovného algoritmu
že práve pracuje rýchlejšie nejako, a je to tak jednoduché vyjadriť, aspoň v pseudokódu.
Vykonávanie tohto druhu algoritmu merge bude takto.
Keď ste rovnako n prvkov - N čísla, n ľudí, bez ohľadu na - prvý je tu zdravý rozum kontrola.
Ak je n menšie ako 2, zlúčiť už len zastaví. To sa vráti, aby som tak povedal.
Prečo by ste zastaviť, ak n je menší ako 2? >> [Nepočuteľné Študent odpoveď]
Právo. A opäť, n nie je číslo v zozname, n je veľkosť zoznamu.
Ak je n je menší ako 2, to znamená, že je zoznam buď 1,
kde ste zrejme zoradená, ak je to 1 číslo,
alebo 0, v tom prípade nie je čo triediť,
takže potrebujeme tento druh základné veci.
Ak je zoznam je tak krátka, že tam je jednoducho nič robiť, doslova sa nič robiť. Návrat.
Inak radiť ľavú polovicu prvkov, potom triediť pravú polovicu prvkov,
potom zlúčiť 2 zoradené polovice.
>> Tento druh sa javí ako malý podvod, kedy som sa ťa pýtam, ako radiť prvky
a vy mi hovoríte, "Zoradiť ľavú polovicu, triediť pravú polovicu."
Som rád, "v poriadku. Ako triediť ľavú polovicu?"
"Zoraďte ľavú polovicu ľavej polovici, triediť pravú polovicu ľavej polovice, a potom urobil."
Ste typ cyklicky definovať, čo to znamená triediť,
ale ukazuje sa, že je to skutočne geniálny v tomto prípade.
To nie je naozaj to začarovaný kruh, ktorý nikdy nekončí
pretože to končí, keď? >> [Študent] Keď sa dostanete 1 vec.
Keď sa dostanete 1 vec.
Takže aj keď ste možno začať s 8 ľudí a ja som povedal, "Zoradiť ľavú polovicu týchto ľudí,
tieto 4 ľudí, "potom hovorím," Ako môžete triediť ľavú polovicu? "
"No, triediť 2 ľudí tu." A potom si ako: "Dobre, dobre."
"Ako môžete triediť ľavú polovicu z tých ľudí?"
"Len triediť tento 1 osobu tu." Čo je to brilantný odhalenie teraz?
Musím triediť 1 osobu. Hotovo. Nemám k tomu žiadnu prácu.
Ale teraz musím vyriešiť túto osobu, ale sú jedna osoba, čo robiť.
>> Takže mágia je zrejme v tomto treťom kroku: zlúčiť zoradené polovice.
Takže zlúčiť druh má túto výnimočnú možnosť nahliadnuť, že ak porušíte veľký problém sa
do 2 menších, rovnako veľkých problémov
a potom sa len druh lepidla menšie riešenie spoločne na konci,
Navrhujem, že môžeme urobiť oveľa, oveľa lepší [odposluch zvuk]
ako ktorýkoľvek z výberového druhu alebo vloženie zoradiť.
Ja som skutočne ignorovať, že za pol hodiny, ale ja naozaj neviem, čo sa deje
mimo dnes. [Vrčanie zvuku] [smiech]
Tak uvidíme, či môžeme vidieť to s trochou pomoci od nášho kamaráta Rob Bowden.
K dispozícii sú 2 veľké kroky v procese druhu korešpondencie.
Po prvé, neustále rozdelí zoznam šálok do polovice
kým nebudeme mať veľa zoznamov iba s 1 šálkou v nich.
Nebojte sa, ak zoznam obsahuje nepárny počet
a nemôžete urobiť dokonale čistý rez medzi nimi.
Len ľubovoľne vybrať, ktoré uvádzajú, aby zahŕňala ďalšie šálku dovnútra
Takže poďme rozdeliť tieto zoznamy.
Teraz máme 2 zoznamy.
Teraz máme 4 zoznamy.
Teraz máme 8 zoznamov s jedným šálkou v každom zozname.
Tak to je to v 1. kroku.
Pre kroku 2 sme opakovane spojí dva zoznamy algoritmom zlúčenie sme sa naučili predtým.
Zlúčenie 108 a 15 sme nakoniec s prehľadom 15, 108.
Zlúčenie 50 a 4 skončíme s 4, 50.
Zlúčenie 8 a 42 sme skončili s 8, 42.
A zlúčenie 23 a 16 sme skončili s 16, 23.
Teraz sú všetky naše zoznamy sú veľkosti 2.
Všimnite si, že každý z 4 zoznamoch zoradené,
takže môžeme začať zlúčením dvojice zoznamov znova.
Zlúčenie 15 a 108 a 4 a 50 sme prvýkrát zobrať 4, potom 15,
potom 50, potom 108.
Zlúčenie 8, 42 a 16, 23 sme prvýkrát vziať 8, potom 16,
potom 23, potom 42.
Takže teraz máme len 2 zoznamy veľkosti 4, je zoradená z ktorých každý.
Takže teraz sme zlúčiť tieto 2 zoznamy.
Najprv vezmeme 4, potom vezmeme 8, potom vezmeme 15
a 16 a 23 a 42 a 50 a 108.
A sme hotoví. Teraz máme zoradený zoznam.
>> Rob bol druh využitie niečoho, čo sme ešte neurobili.
To bolo navrhol, ale my sme sa vlastne robiť to.
Robil niečo fyzicky s poháre, ktoré naznačuje,
trávil nejaký zdroj vedľa času. >> [Študent] Space. >> To bol priestor.
Skutočnosť, že mal tento druh bi-úrovni stola, kde mal priestor až sem
a priestor sa tu skutočne znamenať, že on je použitie dvakrát toľko miesta
ako niektorý z našich algoritmov tak ďaleko - vloženie sort, bubble sort, alebo výber sort -
ale on bol využitia tohto dodatočného priestoru pre druh sa veci pohli dopredu a dozadu
pri zachovaní veci do poriadku.
A aj keď je to pocit, ako by sme sa dostali na zoradený zoznam, ktorý cítil, ako by to trvalo dlho.
V skutočnosti to, čo Rob robil, bolo presne to algoritmus.
On najprv vzal problém veľkosti n, delí ju na ľavej polovici a pravej polovice.
To je, keď sa presťahoval do šálok. Potom sa opakoval tento proces.
Rozdelil 4 do 2 sady 2 tu a tu.
Potom sa opakoval, že proces a delí 2 do 2 sady 1 pre každú z týchto rôznych pohárov.
A to je miesto, kde geniálny naskytne príležitosť.
V tomto bode príbehu, Rob mal 8 zoznamov veľkosti 1,
z ktorých všetky boli zoradené už.
>> Takže to, čo urobil pokračovať robiť?
Pairwise vzal túto zoradený zoznam a túto zoradené zoznam a spojil ich.
Potom vzal to a spojil ich, potom si to a spojil ich,
potom jeden a spojil ich.
A čo potom urobil ďalší?
On potom re-sa spojil s väčšou zoznamy a potom re-sa spojil s väčšou zoznamy.
A ak si myslíte, že o tom len intuitívne teraz, čo sa naozaj robí?
Bol rozdelenie problému na polovicu, v polovici, na polovicu, v polovici
aby sa tieto mimoriadne malý zoznamov.
Potom bol láskavý kombinácia double, double, double, double.
Takže on bol robil dvakrát toľko práce, ako sme videli doteraz
s ničím zahŕňajúce rozdeľ a panuj, ale žiadny veľký problém.
Dvakrát toľko práce nie je tak veľký problém. Je to len konštantný faktor.
A podobne ako náš aritmetický výraz pred, ja len tak vyškrtnúť konštantné faktory
ako vždy 2. Koho to zaujíma? Ak je to 2 miliardy krát 2, to je ešte veľa krokov.
Takže to zlúčenie krok sa zdá byť kľúčový vhľad.
Prejdime to len číselne pred - Oh, to nie je potrebné pokračovať ešte.
Prejdime toto číselne, len aby skutočne vidieť, ako to dopadne.
To je väčšinou len trochu chudáka animácie.
Poďme navrhnúť túto.
Doba chodu radiť zlúčenie - len je potrebné spôsob, ako hovoriť o tom.
To nie je matematika, to je len trochu stručného spôsobu vyjadrovania.
Takže T predstavuje čas a n predstavuje čo? >> [Študent] veľkosť -
>> [Malan] veľkosť problému, počet ľudí.
Takže som tvrdil, že beží čas triediť n ľudí bude 0 množstvo času
ak n je menší ako 2, pretože ak máte 1 šálku alebo šálky žiadne, budete mať čo triediť.
Ale všeobecne, budem navrhovať, aby doba chodu triediť n prvkov
bude čas to trvá radiť ľavú polovicu plus pravá polovica
plus - Čo je to ďalší + n? >> [Študent] Merge sort.
[Malan] Je to vlastne prelínajú, pretože ak máte n / 2 prvkov tu
a máte n / 2 prvkov tu, koľko času trvá zlúčiť?
Rovnako ako Rob, musíte trhať tento tu, možno trhať tu,
trhať tu, trhať tu, trhať tu.
Tie majú dotknúť každého z téglikov raz.
A ak je 4 šálky plus 4 šálky, že je to 8 šálok
alebo, všeobecnejšie, 8 n šálok.
Takže zlúčenie krok, ktorý môžeme vyjadriť ako n,
a že doslova zahŕňa koľkokrát Robert fyzicky dotkne
jeden z tých polystyrénu pohárov.
Takže poďme sa teraz urobiť ľubovoľný príklad.
Ak je 16 šálok, čo je doba chodu radenia, používanie Robova algoritmus, 16 šálok?
Je to 2 krát množstvo času, ktoré trvá triediť 8 šálok
pretože máme 8 šálok tu, 8 šálok tu.
Neviem, ako dlho to trvá, takže sme zobecňující ako T pre túto chvíľu.
Kto vie, čo to je?
Ale teraz môžem nejako rekurzívne alebo opakovane položiť rovnakú otázku.
Koľko času zaberie triediť 8 šálok?
8 šálok budem hovoriť trvá množstvo času to berie triediť 4 šálky plus 4 čaše,
potom zlúči dohromady.
Fine. Sme stále v cykle už. Ako dlho trvá, než si vybrať 4 šálky?
Čas potrebný k radeniu 4 šálky je 2 šálky plus 2 šálky radenie plus zlúčenie procesu.
Fine. Ako dlho trvá, než si vybrať 2 šálky?
2 šálky je množstvo času, ktoré trvá triediť 1 šálka plus čas potrebný na radenie jeden šálka
a množstvo času, ktoré trvá zlúčiť, čo je len 2.
>> Fine. Posledná otázka. Ako dlho trvá, než si vybrať 1 šálku?
Tu je základná pravda, že sme predpokladali by sme hit skôr.
Skutočnosť, že to trvá žiadnu prácu vôbec triediť najmenší z problémov
znamená, že teraz, druh škole štýlu,
môžeme len tak začať zapojenie týchto čísel späť dovnútra
Teraz vieme, čo T 1 je, a tak som si zapojiť 0 pre T z 1.
To mi dá odpoveď na T 2, ktorý som potom môžete pripojiť vo vyšších poschodiach.
To mi dá T 4, ktorý som si plug in vo vyšších poschodiach.
To mi dá T 8, ktoré môžem pripájať aj vo väčšom up.
A keď som vlastne robiť na to, že matematiku zapojením týchto odpovedí,
Potom som si T z 16 je 64.
A čo 64 predstavuje?
Ak T je 16, jo, to je 16 krát 4.
Tak som teraz tvrdí, že doba chodu tejto veci tzv zlúčenie druhu -
a to sa bude najmódnejšie z tých, ktoré sme videli doteraz -
sa bude nazývaný n log n
pretože koľkokrát môže Rob rozdeliť veľa pohárov v polčase? Prihlásiť n
Je to rovnaké, ako napríklad v telefónnom zozname, je to rovnaké ako self-počítanie napríklad.
>> Koľkokrát môžete rozdeliť niečo na polovicu?
Avšak, tam je to zlúčenie krok.
Možno budete musieť rozdeliť šálky do polovice znovu a znovu a znovu,
ale zakaždým, keď budete musieť zlúčiť.
A my sme povedali už skôr, že zlúčenie n šálky berie n kroky
pretože budete musieť vytrhnúť šálka, vytrhnúť šálka, a vy budete musieť dotknúť každej šálky raz,
rovnako ako Rob urobil.
Takže ak robíme niečo protokol n krát a robíme n veci na každom z týchto iterácií,
každej z týchto halvings, máme n krát log n
Takže ak zapojíme do 16 v tomto príklade, 16 krát protokol o 16 -
nebojte sa o tom, prečo tomu tak je pre túto chvíľu, pretože som to nakreslil základňu -
ale log základu 2 16 je 4, 16 krát 4 je 64.
Ale naopak, ak sme použili bublina radenie alebo výber radenie alebo vloženie radenie s 16 číslami,
čo by sa tým doba chodu bolo, keby n je 16?
Bolo by 16 na druhú, čo je 256, ktorý aj keď sa úplne nasledovali všetky spočítal,
256 je väčší než 64. To je naozaj čarovný takeaway tu.
A uvedomiť si, že práca cez to v menších príkladoch, ako budete na PSet
je to všetko oveľa intuitívnejšie.
To však v skutočnosti znamená, pokiaľ ide o vzhľad tohto algoritmu je tento:
Ak sa skutočne pozrieť na druhu korešpondencie tu - dovoľte mi, aby som vytiahnite ju v tomto okne tu -
To je trochu iný príklad, keď máme všetky 3 z týchto algoritmov -
bublina, výber, a zlúčiť - len vedľa seba.
>> Majú všetko začalo s náhodnými bary, a to je dobre.
Nikto nemá zásadnú výhodu nad ostatnými.
Idem za chvíľu kliknite na každú z týchto animácií - Štart, Spustiť, Spustiť -
tak rýchlo, ako je to, aby si, hrubo, všetci začínajú na rovnakú dobu,
a uvažujme, že bublina radiť tieto horší prípad beží čas je to, čo? >> [Študent] N druhú.
N vzpriamil. Výberom Triediť najhorší prípad doby prevádzky je? N vzpriamil.
A merge sort je zrejme - aj keď nie úplne sledovať všetky matematiku teraz,
to bude stáť oveľa intuitívnejšie priebehu času - je, že sme tvrdí, n-krát log n
A pretože log n je ostro menší ako n, akonáhle budeme mať veľké množstvo,
n-krát log n je menšie ako časoch n n alebo n na druhú.
Takže to, čo to je, keď skutočne lepší algoritmus, pokiaľ ide o dobu prevádzky,
n-krát log n ako protichodný k n na druhú? Ideme na to. Kliknite na tlačidlo, cvak, cvak.
>> To je to, čo to znamená použiť niečo ako druh hromadnej korešpondencie.
Máme chvíľku. Poďme sa pozrieť, čo sa deje tu.
[Smiech] Čí peniaze na bubliny radiť?
To, závisí na vstupe niekedy.
Poďme sa pozrieť,.
Poď. Pripadá mi to ako, že to doháňa. >> [Študent] Choď, bublinková druh!
[Študenti reptania]
[Malan] Jo, jo.
[Študenti reptania] Bež, bež, bež!
[Všetky jásající] [potlesk]
Takže teraz s 1 posledným, záverečnom demo, či je to trochu zložitejšie zabaliť svoju myseľ okolo matematiky
alebo druh vizualizácie tam, môžete skutočne počuť rýchlosti
rôznych algoritmov odlišne.
To je animácia niekto urobil, že skutočne združuje znie
s procesom odkladanie a výška stĺpcov.
Ako uvidíme, je tu ešte pár triedenia algoritmy, ktoré tam ľudia si mysleli.
To prvé, kto sa bude vloženie triediť, a to bude lietať
a dá vám počuteľné pocit ako tieto rôzne algoritmy pracujú.
Tu je vloženie sort.
[Elektronický pípanie]
[Malan] Bubble sort.
[Rýchlejšie elektronické pípanie]
[Malan] Výber sort.
[Rýchlejšie elektronické pípanie]
[Malan] Merge sort.
[Elektronický pípanie]
[Pípanie spomaľuje] [smiech]
[Malan] Gnome sort.
[Elektronický pípanie]
>> To je CS50. Uvidíme sa budúci týždeň. [Potlesk a jasot]
>> [CS50.TV]