>> [Prehrávanie hudby]
>> DAVID J. Malan: Toto je CS50.
A to je začiatok troch týždňov.
Takže máme veľa vzrušujúce veci na pokrytie dnes.
Mnoho príležitostí pre dobrovoľníci sa na javisku.
A nakoniec, dnes je nejde o kóde vôbec.
Ale je to o myšlienkach, a je to o algoritmoch,
a vlastne prinášať späť časť poučenie z týždňa nula,
kde odvolanie, my predstavil túto obludnosť.
A výpožičky inšpirácia od toho, pre spustenie
riešiť stále sofistikovanejšie Problémy algoritmickým.
Ale najprv pár oznámenia.
Takže jeden, ak by ste sa radi pripojili CS50 personál a spolužiaci na obed
tento piatok, ako tu, tak v Cambridge a v New Haven,
navštívte kurz je webové stránky, kde je možné URL nájdená.
Prednáška bude túto stredu nemôže byť tu v Sanders.
Bude to on-line iba, takže naladiť na stránkach CS50 je,
či už tu v Cambridge alebo New Haven rovnako.
>> A potom problém nastaviť dve je už vo vašich rukách.
Ak ste sa potápal v doteraz, dovoľte mi ponúknuť ostro formulovaný návrh
, Že najmä teraz, as Problém stanovuje postup,
si naozaj chcete začať hneď, ak nie fušovať trochu na víkend alebo pred
kedy sa prvýkrát ísť na Piatky, pretože budete
zistíte, že to nemusí byť nutne stále dlhšie a náročnejšie na
sa.
Myslím, že zistíte, že v Všeobecne platí, že majú tendenciu, aby sa zhruba
zhruba rovnaké množstvo času.
Ale to rozhodne záleží na študenta, a to
závisí na myslenie s ktorým k nemu pristupovať.
Ale vždy, budete bežať proti nejaké múru,
a budete hit nejaký bug, a vy ste len
nebude môcť dostať sa cez to v určitom okamihu.
A to je veľmi cenné, aby bolo možné ustúpiť, vráť sa ďalší deň,
ísť na pracovný čas, príspevok na CS50 Diskutovať alebo podobne, aby skutočne dostať odblokovať.
Takže majte na pamäti, že.
Spustenie najskôr to bude možné je to najlepšie, čo môžete urobiť.
Tak tu je miesto, kde sme začali trieda, než v týždni nula.
A môžeme dostať dobrovoľníka tu, aby mi pomohla nájsť mikrofóny?
OK.
Stojí už hore.
Poď hore.
Hádajte, že to, ako to bude fungovať.
Ako sa voláš?
ALAN ESTRADA: Alan Estrada.
DAVID J. Malan: Alan Estrada.
Poď hore.
Rád som ťa spoznal.
ALAN ESTRADA: Teší ma.
DAVID J. Malan: A vy ste tu u nás v týždni nula, samozrejme.
ALAN ESTRADA: som bol.
Bol som.
>> DAVID J. Malan: Takže by ste mohli ísť dopredu a nájsť pre nás Mike Smith,
tak rýchlo, ako je to možné?
Tak rýchlo, ako je to možné.
Doslova trhá problém na polovicu, ako budete potrebovať.
>> ALAN ESTRADA: Hm.
DAVID J. Malan: Doslova trhanie problém na polovicu.
>> ALAN ESTRADA: Oh.
Mm.
Veľmi dobre.
>> DAVID J. Malan: OK.
Dobre.
Ďakujem.
ALAN ESTRADA: Veľmi dobre.
OK.
>> DAVID J. Malan: A tak teraz, ste orezaný dole
na polovicu veľkosti problému.
Teraz, sme až na štvrtinu.
Ste venovať pozornosť na ktorej strane držíme?
>> [Smeje sa]
>> ALAN ESTRADA: Áno, ja think--
>> DAVID J. Malan: Aká časť sme v?
ALAN ESTRADA: tlmiče, takže.
>> DAVID J. Malan: OK.
Ale Mike Smith sa deje byť po tlmiče.
Tak--
>> [Smeje sa]
>> Dobre.
ALAN ESTRADA: Kde sa to pozeráme?
DAVID J. Malan: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. Malan: Teraz sme v chirurgickej.
Teraz lekári.
Now--
>> ALAN ESTRADA: Let's- poďme s real.
Real.
>> DAVID J. Malan: Real.
OK.
Ak potrebujete skutočný.
Teraz, ktorá cesta je Mike Smith?
>> ALAN ESTRADA: Tadiaľto.
>> DAVID J. Malan: Kadiaľ?
ALAN ESTRADA: Počkajte.
M je-- pravdu?
Začali sme with--
>> DAVID J. Malan: Jo.
Oni opustili.
Vaše právo.
>> ALAN ESTRADA: Jo.
>> DAVID J. Malan: Takže Mike tu.
ALAN ESTRADA: Čo?
>> [Smeje sa]
>> Zlý príklad, chlapi.
Prepáčte.
DAVID J. Malan: To bude vyučovať vás vyskočiť zo stoličky.
>> ALAN ESTRADA: Oh.
Aha.
Mám ťa.
Aha.
To je-- OK, mám ťa.
Smith tu?
>> DAVID J. Malan: Smith, ďakujem.
Takže budem držať vzhliadol Smith?
>> ALAN ESTRADA: Oh, jo.
Nie nie nie.
Ale nie.
To je moja.
>> DAVID J. Malan: Oh, máš Smith.
OK.
>> ALAN ESTRADA: Jo, myslím, dostal Smith tu.
Ospravedlňujeme sa, chlapi.
Myslel som, že sme sa Michael-- hľadali Michaela.
Prepáčte.
>> DAVID J. Malan: To je v poriadku.
Dobre, teraz sme do Paccini and Sons.
>> ALAN ESTRADA: Paccini a synovia.
DAVID J. Malan: Iba vy a ja sme na túto tému.
OK.
Nájdite nás Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. Malan: Smith.
Sme v R pre odpadky.
ALAN ESTRADA: Odpadky.
Aha.
Bude to chvíľu trvať.
>> [Smeje sa]
DAVID J. Malan: Shoes.
Sme v topánkach.
>> ALAN ESTRADA: Teraz sme gonna--
>> DAVID J. Malan: Nice.
ALAN ESTRADA: Which--
[Smeje sa]
Oh, to je skvelé.
[Smeje sa]
>> DAVID J. Malan: To je v poriadku.
>> ALAN ESTRADA: Oh, to je dobré.
Nemyslím si, že budem majú PSAT kamarátmi po tomto.
DAVID J. Malan: Dobrý.
Sporting.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
DAVID J. Malan: OK.
Takže poďme roztrhať to na polovicu.
Je to v poriadku.
Týmto končí zle tak ako tak, pretože Mike Smith nebude v Zlatých stránkach.
>> ALAN ESTRADA: Aw.
>> DAVID J. Malan: Nie, to je v poriadku.
Ale poďme predstierať, že je na tejto stránke.
Takže teraz, že ste orezaný problém dole na jednej strane, a zistili sme, Mike Smith.
>> [Fandenie]
Dobre ďakujem.
OK.
To bol mimoriadny.
Ale to bolo ešte rýchlejšie než lineárne vyhľadávanie,
kde začneme u začiatku knihy,
a my sa pohybujú našu cestu zľava doprava, nakoniec hľadal Mike Smith.
A tak, v prípade, že telefónny zoznam Mal snáď 1000 strán,
Možno, že by to vzali us 10 alebo tak stránky slzy.
>> Ale môžete mať zadlužuje dotkol predpoklad
pri všetkých, ktoré, čo znamená že telefónny zoznam vopred bolo to, čo?
Divákov: Triedený.
DAVID J. Malan: Je to triediť.
Je to tak?
Je to radené abecedne, tak že všetky tieto mien a čísel
sú radené od A to k Z ich, a abecedne medzi tým.
Ale dnes, teraz sa opýtať otázka, dobre,
Ako sa Verizon alebo sa telefón spoločnosť dostať do tohto stavu?
>> Vzhľadom k tomu, že je to jedna vec je využiť tento predpoklad, a preto,
vyriešiť problém s algoritmus efektívnejšie.
Ale my sme nikdy spýtal sa v týždni nula, dobre,
koľko to stálo Verizon alebo niekto iný
sa dostať, že telefónny zoznam v zoradení poradí?
>> Je to tak?
Nezáleží na tom, či vzhliadol Mike Smith
je super rýchly, keď to trvá vám odkaz rok spočiatku zoradenie stránok.
Je to tak?
Tie by mohli rovnako dobre preosiať cez randomizovanej telefónny zoznam,
ak to bude byť super drahé to triediť.
Takže, či môžeme mať ďalšie dobrovoľník.
Poďme sa pozrieť tu na ako might-- poď up-- ako
môžeme ísť o triedení týchto.
>> A ak by sa skutočne Jordan Pripojte sa k nám tu na javisku.
Poďte hore len na chvíľu.
Ako sa voláš?
CAROLINE: Caroline.
DAVID J. Malan: Caroline, poď hore.
A vy budete spojené mnou a Jordánskom tu.
Caroline, ďakujem.
Dobre.
Takže to, čo sme tu Caroline je 26 modrej knihy
že FAS používa na spravovanie niektoré záverečné skúšky.
Tie sú stále ťažké nájsť, ale to, čo sme urobili v predstihu
je to, že sme vložili niečí meno na prednej strane každého z nich,
ale my sme stále to jednoduché od potom uvedenie von plná mená.
Takže by sme dať osobu s názvom L, D, J, B, celá cesta A až Z,
ale sú v náhodnom poradí.
A tak ak by ste, hovoril vašich cesta cez problém ako vy
to je, môžete ísť dopredu a triediť tieto pre nás, od A do Z.
>> Publikum: OK, takže L je ako, uprostred.
C začína.
B. J pred L. B, Q.
>> DAVID J. Malan: Držte že Myslel dobu jednej sekundy.
Vzhľadom k tomu, inak, je to len zaujímavé pre vás, ja, a Jordánskom.
Tam sme ísť.
Divákov: [Nepočuteľné].
R.
DAVID J. Malan: OK.
Čo robíš?
>> CAROLINE: M prichádza po O.
>> DAVID J. Malan: OK.
>> CAROLINE: O.
DAVID J. Malan: Ó, dobrá.
>> CAROLINE: E.
>> DAVID J. Malan: E, F. Jo.
>> CAROLINE: T, U, V.
>> DAVID J. Malan: V, T, U, V. tak to vyzerá to, že ste making-- ďalej.
Vyzerá to, že robíte veľká hromada tu,
a druh veľkú hromadu tamto.
Takže prvá polovica abecedy, Druhá polovica abecedy.
OK.
Dobre.
Druh rozdelenie problému na dve časti.
M, N, X. Jo.
CAROLINE: K.
DAVID J. Malan: OK.
K. Takže druh výberu je jeden po druhom,
uvedenie buď vľavo alebo vpravo, alebo Z deje na zemi.
OK.
>> CAROLINE: Z sa deje na zemi.
>> DAVID J. Malan: OK.
Y sa deje na zemi.
Teraz môžeme dať X.
>> CAROLINE: G.
DAVID J. Malan: G sa deje odišiel.
S bude v poriadku.
Dobre, A ide celú cestu vľavo.
>> CAROLINE: A, B, C, D.
>> DAVID J. Malan: Teraz, dobre.
Máme A, B, C, W deje tam dole.
Dobre, T.
>> CAROLINE: H, I, J.
DAVID J. Malan: H, I, J. Good.
CAROLINE: V centre, som gonna--
DAVID J. Malan: OK.
Takže teraz, budeme druhu o zlúčenie týchto rôznych pilotov.
Takže A až C, a potom vidím, D, a E a F a G a H a I. Nice.
J, K. A potom, to je hromada hore nohami, ale to je v poriadku.
Iste.
Môžeme znížiť niektoré rohy.
OK.
A potom musíme W, X, Y, Z.
>> CAROLINE: Jo.
>> DAVID J. Malan: Výborný.
Tak veľké poďakovanie Caroline pre triedenie týchto.
>> [Fandenie]
>> Ďakujem.
Ďakujem veľmi pekne.
Takže teraz uvažujme na okamih ako Caroline šiel o tom, že,
a čo presne my boli schopní to-- ako
bol schopný riešiť, že problém, keď sme boli len
vzhľadom k tomu, celá partia náhodných vstupov.
>> No, vyzerá to, že tam bol trochu tam systému?
Správne.
Takže čím skôr listy v abecede, ona
bolo uvedenie na ľavej strane, a neskôr písmen v abecede,
bola uvedenie do pravej strane.
A akonáhle zistila, že Niektoré proximálnej listy, ones
ktoré idú hneď vedľa seba, ona by dal tie v poriadku.
A tak sme trochu mali tieto malé hromady triedených vstupov vyskytujúcich.
>> A tak to je celkom rád to, čo Väčšina z nás by ľudia robia.
Radi by sme nejako preosiať cez to, a my by sme trochu mať mechanizmus.
Ale to by mohlo byť ťažké písať že sa vo vzorci, per sa.
Bolo to o niečo viac ekologická než to.
Tak uvidíme, či môžeme teraz viazaný Problém s menším počtom vstupov.
>> Namiesto toho, 26., poďme niečo ďaleko menej
s len povedať, sedem, za tieto dvere, aby som tak povedal.
Sú tam len sedem čísel?
A v prípade, že cieľ teraz na ruka je nájsť hodnotu,
pozrime sa, ako efektívne môžeme ísť asi robí.
A uvidíme, či môžeme teraz začne platiť nejaké čísla,
alebo niektoré vzorce, s ktorými popísať Účinnosť nášho telefónneho zoznamu
algoritmus, naša skúška kniha algoritmus, a všeobecnejšie, vyhľadávanie informácií.
>> Takže pre to, nechajte ma ísť dopredu, a Na dotykovej obrazovke sa sem,
dať do webového prehliadača, ktorý má presne týchto sedem dvere.
A ak by sme sa mohli dostať jednu ďalšiu dobrovoľne poď sem,
Ja som dal tieto rovnaké dvere sem.
Quick dobrovoľník.
>> Tieto one-- dema idú na rýchlejší a rýchlejší teraz.
Poď dole.
Ako sa voláš?
Trevor: Trevor.
>> DAVID J. Malan: Trevor?
Dobre, Trevor, poď dole.
Takže Trevor sa tu dobrovoľne robiť podobný problém, ale ten, ktorý je
užší rozsah, a to sa deje aby sme mohli pokúsiť formalizovať teraz
Proces triedenia týchto čísel.
>> Takže Trevor, rád vás spoznávam.
Takže tu je pole, tak hovorí, zoznam siedmich dverí.
Choďte do toho a nájsť nám číslo 50.
A potom sa po faktu, povedzte nám, ako ste ju našli.
Ak by be-- v poriadku.
Jo, to je ten tu?
Uh Oh.
OK.
Klepli že jeden.
Dobre.
>> A veľa.
Teraz ste klikli, že jeden.
A dovoľte mi, aby som vám mikrofón, takže ju máte za chvíľu.
Choďte do toho a kliknite na tlačidlo vedľa, že máte v úmysle.
Áno dobre.
Trevor: Môžem unclick dvere?
DAVID J. Malan: Nie, nemôžeš unclick.
Trevor: OK.
Toto.
DAVID J. Malan: Kam chceš ísť?
Ktorý?
>> Trevor: Tenhle.
>> DAVID J. Malan: Nie.
>> Trevor: OK.
Toto.
>> DAVID J. Malan: Áno.
To bolo dobré.
Dobre.
Takže aká bola vaša algoritmus alebo Postup tohto postupu, Trevor?
>> Trevor: Len som prešiel dvere, až som našiel 50.
DAVID J. Malan: OK.
Vynikajúci algoritmus.
Tak je to v poriadku.
Pretože v skutočnosti, keď som odhalí, čo je Za týmito dvoma ďalšími dverami, čo
zistíme je, že máme len náhodnou vstup.
Takže to bol vlastne as dobrý, ako by ste mohli dostať.
A v skutočnosti, máš lepší ako vyčerpávajúcom hľadaní celé pole,
pretože by to bolo skutočne smolu, ak ste mali hit číslo
50 na poslednú dvere.
Ale čo keby sme namiesto Dal vám predpoklad.
Dajme tomu, že nejako som všetky tieto dvere okolo,
takže máte Čísla radené tentoraz
ale tentoraz je to vlastne different-- tentoraz,
je to vlastne radené pre vás.
A teraz cieľ na dosah ruky je trafiť číslo 50.
>> Trevor: OK.
>> DAVID J. Malan: Čo je Váš algoritmus bude?
>> Trevor: No, keď je to radené, je to buď ísť
na be-- ak najväčší k najväčšej, zostupne, bude to prvý,
alebo ak je to naopak, to bude posledná.
Tak som si len kliknite na dvere, a potom stačí kliknúť na poslednú dvere.
DAVID J. Malan: Výborný.
Dobre.
Takže sme zistili, že číslo 50.
Takže akonáhle ste vedel, boli radené, my
boli schopní využiť tento predpoklad.
Takže sú veľmi rád telefónneho zoznamu príkladom.
Akonáhle budete mať, a to aj malý problém ako je tento,
vaše vstupy pre-triedené, môžeme skutočne nájsť hodnotu pravdepodobne
efektívnejšie.
>> A ja som ťa, či je to povedať radené malých až po veľké, alebo veľká, aby malé,
a tak to bolo veľmi rozumné začať na jednom konci alebo na druhú
skutočne zistiť, že cieľové hodnoty.
Takže ďakujeme Trevorom rovnako.
A ja budem propose-- pekne urobil.
Máme trochu klip, v skutočnosti, že je medzi naše obľúbené momentov CS50,
pričom niekedy tieto ukážky nie celkom podľa plánu.
A skutočne práve teraz, myslím, vytiahol zlú rozhranie
s ktorým používať dotykovú obrazovku.
Takže to bola moja chyba tam.
>> Takže to bude robiť na budúci rok klip as
prečo som sa kliknutím na moje vlastné obrazovku.
Ale poďme sa rýchlo pozrieť na to, čo sa stalo minulý rok
s Jay, ktorý prišiel, veľa ako Trevor tu, dobrovoľne,
a v tomto krátkom klipe uvidíte ako to to isté demo nie celkom
odhaľujú rovnaké ponaučenie.
[Videoprehrávanie]
-všetky Chcem, aby ste urobiť, je teraz nájsť pre mňa a pre nás,
Naozaj, číslo 50 jeden krok v čase.
>> -the Číslo 50?
>> -the Číslo 50.
A môžete odhaliť, čo je Za každú z týchto dverí
jednoduchým dotykom s prstom.
Dočerta.
>> [Smeje sa]
>> [END Prehrávanie]
DAVID J. Malan: Takže to išlo veľmi dobre.
Tí, ktorí boli netriedené dvere.
Jay a, samozrejme, našiel to všetko príliš rýchlo.
Trevor urobil oveľa lepšiu prácu v podmienkach učenlivý okamih
tak povediac, v tomto roku trvá dlhšiu dobu ju nájsť.
Samozrejme, potom sme dali Jay druhá šanca,
čím sme radené dvere, ako sme to urobili pre Trevora,
a Trevor DID Super dobre tentoraz.
Ale Jay to urobil polovicu rýchlo.
[Videoprehrávanie]
-the Cieľom je teraz tiež nájsť nám číslo 50,
ale to algoritmickým, a povedzte nám, ako budete o tom.
>> -OK.
>> -A Ak zistíte, budete mať film.
Ak nenájdete to, dať ju späť.
>> -MAN.
>> Oh!
>> - [Nepočuteľný] OK.
Takže ja idem skontrolovať koncov najprv zistiť, či there's-- Oh.
>> [APPLAUSE]
>> [END Prehrávanie]
DAVID J. Malan: OK.
Takže jasne triedenie dvere vedie k väčšej efektivite.
A tak, dvakrát rýchlejšie je to, čo som tam mal na mysli.
A tak Jay šťastie obaja časy.
A tiež šťastie v tom, že posledný rok, objednal som nejaké disky Blu-ray
skutočne rozdávať.
Je mi ľúto, tento rok sme nemal rovnaký Trevor.
Ale stále lepšie bola o niekoľko rokov späť.
A niektorí z vás možno vedia to chlapík, Sean, ktorý kedy bol v CS50,
bol napádaný s presný Rovnaký problém, aj keď v SD,
ako budete čoskoro vidieť, späť v deň.
A zistíte, že nielenže to trvať trochu dlhšie, než Jay,
o niečo dlhšie, než Trevora, to bolo vlastne to skvelá príležitosť
aby sa zapojili takmer všetci v dav a la Price is Right, povzbudzujúci
ho nájsť číslo sme hľadali.
Poďme. sa rýchlo pozrieť.
>> [Videoprehrávanie]
>> -OK.
Takže váš úlohu tu, Sean, je nasledujúci.
Som sa skrýva za tieto Dvere číslo sedem.
Ale zastrčená v niektorej z týchto dverí ako aj iné záporné čísla.
A vaším cieľom je si myslieť, tejto hornej rady čísel
len ako pole, alebo len Sekvencie kusov papiera
s číslami za nimi.
A vaším cieľom je, iba pomocou hornej array tú, nájdite mi číslo sedem.
A potom sme sa k posudku ako sa chodí robiť.
-Dobre.
-Find Nám číslo sedem, prosím.
Nie.
Five, 19, 13.
>> [Smeje sa]
>> To nie je chyták.
One.
>> [Smeje sa]
V tomto okamihu, skóre nie je príliš dobre, takže si pokojne ďalej.
Tri.
>> [Smeje sa]
>> Pokračuj.
Úprimne povedané, nemôžem si pomôcť, ale zaujímalo čo si dokonca myslieť, tak--
>> [Smeje sa]
Len horný rad, takže Máš tri doľava.
Takže mi nájsť sedem.
>> [Smeje sa]
17.
Sedem.
>> [APPLAUSE]
>> Dobre.
>> [END Prehrávanie]
>> DAVID J. Malan: Takže sme mohli Sledujte tieto celý deň.
A samozrejme, niektoré tohtoročné dema možná
bude teraz skončí v budúcom Tohtoročné videa rovnako.
Takže teraz poďme vlastne zamerať sa na algoritmoch
tu, a uvidíme, či nemôžeme Teraz začínajú formalizovať
ako môžeme ísť o získanie našich dát do tohto stavu, že je to radené,
takže nakoniec môžeme skutočne prehľadávať efektívnejšie.
A aj keď ideme použiť pomerne malé dátové súbory,
rovnako ako osem čísel, ktoré máme tu na doske,
nakoniec by sa mohli vzťahovať tie isté myšlienky 1000 vstupov, milión vstupov,
4 miliardy vstupy, pretože algoritmy sa bude v podstate rovnaké.
>> A tak to je naša posledná príležitosť pre dobrovoľníkov dnes,
ale snáď najviac zapojení, kto, pre ktoré potrebujeme osem dobrovoľníkov
prísť a ísť cez nás proces triedenia čo bude čoskoro
byť na tieto hudbu tu stoja.
Dovoľte mi začať tu.
>> Takže človek v turquoise-- Zelená je to?
Ste spáchanie?
Dva.
Poď dole.
OK.
Tri.
Štyri.
Nech me-- OK, päť.
Ste bol nominovaný váš priateľ.
Šesť, sedem a osem.
Poď hore.
Dobre.
Ďakujem ti veľmi pekne.
Poď hore.
>> Dobre.
Takže to, čo máme, a to here-- je medzi tými viac neobvyklých,
pretože to bude vyžadovať, aby ste humor pre mňa len trochu času.
Tie musia byť číslo jedna.
Ako sa voláš?
>> ANNAN: Annan.
>> DAVID J. Malan: Annan.
David.
Ako sa voláš?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, ste číslo dva.
>> SERENA: Serena, číslo tri.
Stefan, číslo štyri.
CYNTHIA: Cynthia.
DAVID J. Malan: Cynthia, číslo päť.
[Nepočuteľných]
DAVID J. Malan: [Nepočuteľné].
David, číslo šesť.
Matt: matt.
DAVID J. Malan: Mattova číslo sedem.
A?
>> WAVERLY: Waverly.
>> DAVID J. Malan: Waverly, číslo osem.
Dobre.
Ak could-- Och.
Ak sa vám všetkým, ako vaše Prvý výzvou, tam
osem hudobné stojany Tu smerom k divákom.
Ak by ste mohli dať svoje číslo na tieto hudba stojí tak,
že line up s rovnaké čísla na doske.
Tak, aby sami vyzerať, že uvedenie vaše čísla na tieto hudby
stojí tu.
Vynikajúca tak ďaleko.
>> Výborne.
OK.
Takže teraz, budeme sa opýtať otázka v niekoľkými rôznymi spôsobmi.
Ako môžeme ísť o triedení títo ľudia tu hore?
Pretože sme mali niekoľko prístupov skôr, pričom sme boli
druh výroby dvoch rôznych vedierka.
A potom sme boli všeobecne Zostavujeme veci dohromady.
Akonáhle sme videli dve čísla že patria k sebe,
sme dali dohromady.
Dva listy, ktoré patria k sebe.
>> Ale uvidíme, či budeme nemožno formalizovať to,
takže nakoniec sme sa niektorí pseudo-kód budete,
pomocou ktorého môžete vyriešiť tieto problémy.
Takže teraz, som pozeral sa na týchto číslach tu.
A vidím veľa chýb.
Nakoniec, chcem, jeden na vľavo a ôsmich na pravej strane.
>> A tak som pri pohľade na tieto dva, štyri a dva.
A v čom je problém, samozrejme?
Jo.
So.
Dva zrejme príde skôr štyri, takže viete, čo?
Dovoľte mi, aby som najprv sa chamtivý prístup, ak chcete, rovnako ako problém
nastaviť one-- ak si spomínate z Standard Edition z problému nastaviť jednu,
kde som len lokálne vyriešiť problém že je tu predo mnou
a uvidíme, kam ma to vedie.
>> OK.
Tak dva a štyri, nechajte ma ísť dopredu a len prehodiť vy dvaja.
Ak môžete fyzicky presunúť sami a váš papier,
Myslím, že som vyzrel Zoznam v lepšom stave.
>> Teraz, sú dobrí.
Chystám sa ísť ďalej, štyri a šesť, vyzerá dobre.
Žiaden problém.
Šesť a osem, na tlačidlo OK.
Osem a jeden, ďalší problém.
Vzhľadom k tomu, čo je pravda o osem a jedna?
Raz príde pred ôsmou, a tak čo by sme mali robiť?
Poďme vymeniť aj týchto dvoch.
Jeden a osem.
A teraz, budem pokračovať.
Budem hľadať ďalej dopredu.
A uvidíme, čo sa stane.
Osem a tri, z Samozrejme, mimo prevádzky.
Poďme swapu.
Osem a sedem, samozrejme.
Mimo prevádzky.
Poďme swapu.
Osem a päť, samozrejme, poďme swapu.
Dobre.
Zoznam je zoradený.
ano?
>> OK, zrejme nie.
Ale je to trochu lepšie, že jo?
Vzhľadom k tomu, upozornenie, čo sa stalo.
Zakaždým, keď sme vykonali výmenu, menšie Počet druh perkoluje takto,
a väčšie číslo perkoluje týmto spôsobom, alebo budeme
začať hovoriť bublala do vľavo alebo prebubláva doprava.
>> Teraz, to nie je dosť, pretože prinajlepšom číslo by mohol
sa posunie o jedno miesto vpred, alebo v najhoršom prípade,
číslo môže mať posunie o jedno miesto ďalej.
Takže viete, čo tento druh z fungovalo celkom dobre tak ďaleko.
Dovoľte mi, aby som to skúsiť znova.
Dva a štyri, sú v poriadku.
Štyri a šesť, sú v poriadku.
Šesť a jedným, mimo prevádzky.
Takže poďme vymeniť vy dvaja.
A teraz, Všimnite si, že problém je začína byť trochu zase lepší.
Šesť a tri, mimo prevádzky.
Poďme vymeniť vy dvaja.
Šesť a sedem, si dobrý.
Sedem a päť, samozrejme, mimo prevádzky.
Sedem a osem, v uvedenom poradí.
A teraz, by som mohol potrebovať to urobiť ešte niekoľkokrát.
A v skutočnosti, myslím, že pre seba snáď koľkokrát maximálne
Možno budem musieť chodiť sem a tam?
>> Vrátime sa k tomu.
Tak dve a štyri sú stále v poriadku.
Štyri a jeden, ani náhodou.
Takže, poďme výmenu.
A opäť si všimnite, vizuálne jeden je druh prebublávania
na ľavej strane, ak by malo byť.
Štyri a tri odkladacie.
Štyri a šesť.
Šesť a päť swapu.
Šesť a sedem.
Sedem a osem je dobré.
>> Dobre.
Dostávame ešte lepší.
Takže poďme sa pozrieť.
Teraz máme dva a jeden.
Samozrejme, vymeniť.
Dva a tri, tri a štyri, a päť, šesť a sedem, sedem a osem.
Dobre.
A viete čo?
Pretože som tam jednu zmenu, dovoľte mi urobiť jednu kontrolu zdravý rozum.
Nechaj ma ísť celú cestu späť na začiatok.
OK.
Jeden z nich, two-- Jo, vidíš?
Niečo bolo zle.
Tri, štyri, päť, šesť, sedem, osem.
A v tomto poslednom priechodu, sú pohodlné s mojím teraz
vyhlasovať, že to je triediť?
OK.
Vizuálne, že je to úplná pravda.
Ale to, čo Funkčne sa tiež len tak
V tej poslednej priechod, ktorá vám umožní potvrdiť, že tento zoznam je naozaj
radené?
>> Čo som urobil, alebo nie tento posledný pas?
Divákov: nedošlo k žiadnym zmenám.
DAVID J. Malan: Sorry?
Divákov: žiadne zmeny.
DAVID J. Malan: nedošlo k žiadnym zmenám.
Tak to by bolo hlúpe ma Urob to rovnaký algoritmus znovu
keby som neurobil akýkoľvek zmení prvýkrát.
A stať sa nezmenil.
Iste, nebudem robiť Akékoľvek zmeny druhýkrát.
A tak je to teraz v bezpečí hovoriť, zoznam je triedený.
>> A skutočne, to je teraz niečo, že budeme všeobecne
hovor bublinkové radenie, pričom po dvoch, znovu opraviť chyby,
a znova a znova, a tí udržať tam a späť,
a sem a tam, kým sa neposkytujeme žiadne také swapy, na ktorom mieste
môžete si byť istí, jo, ja dokončil upevnenie všetky chyby.
Poďme reset a skúsiť iný prístup.
Ak vy mohol vrátiť do poradie ste pred chvíľou,
ktorý vyzeral takto.
Teraz sa poďme k prístupu, ktorý trochu viac ako skúšku knihe,
kedy sme boli neustále výberom písmeno abecedy
že sme trochu chceli riešiť ďalšie.
Možno to bol vysoký list, Rovnako ako, alebo s nízkou písmeno Z.
>> Takže každý je späť v tomto poradí.
A teraz ma to urobiť.
Poďme sa pozrieť, viem, že mám osem čísla tu.
Chystám sa ísť dopredu a len zámerne zvoľte
najmenší prvky.
Je to tak?
To sa zdá byť intuitívne taky.
Prečo mi pripadá najmenšiu prvok, vložte ju tam, kam patrí,
potom dostanete ďalšie najmenší prvok, dal je tam, kam patrí, a len zopakovať.
>> Vzhľadom k tomu, intuitívne, ktorý by mal fungovať tiež.
Tak štyri, to je celkom malý počet.
Idem si spomenúť, kde to je.
Počkaj minútu.
Two je menšia.
Dovoľte mi teraz spomenúť, kde dvoch je, a zabudnúť na štyri.
Vybavíme to neskôr.
Šesť, nemám záujem.
Osem, nemám záujem.
Jedným z nich je môj nový malý počet.
Takže budem pamätať, kde jeden je.
Tri, nemám záujem.
Sedem, nemám záujem.
Five, nemám záujem.
>> Takže bez pádu fázy v tomto roku,
Chystám sa chytiť počet one-- a to, čo bolo zasa Vaše meno?
>> ANNAN: Annan.
>> DAVID J. Malan: Annan.
A keby ste sa mnou na začiatok zoznamu
poďme ťa tam, kam patríte.
Bohužel-- Ako sa voláte?
>> STEFAN: Stefan.
>> DAVID J. Malan: Stefan je v ceste.
Takže ako Stefan rieši tento Problém, čo by sme mali robiť?
Čo budeme robiť s Stefan?
>> Divákov: [Nepočuteľné].
DAVID J. Malan: OK.
Takže sme mohli urobiť.
Mohli by sme nejako vziať Stefan a jeho štyri, a len dať to do premennej
a držať sa jej za určité množstvo času,
čím sa vytvorí priestor pre číslo jedna.
A to nie je zlé.
Mohol by som navrhnúť, prečo nie sme len dať tú Stefana?
Prečo by to mohlo porušiť jeden nápadov sme začali
hovorí o minule, minulý týždeň?
Jo?
>> Divákov: [Nepočuteľné].
>> DAVID J. Malan: Neexistuje žiadny index pre neho.
Ak si myslíte o tom, naozaj, ako pole, to je ako negatívne,
takže nie je žiadna pamäťová vlastne Tu, ak je to skutočne poľa,
ako sme deklarovali minulý týždeň v prednáške.
Takže by sme nemali robiť.
Môžeme uložiť ho do premennej.
>> Alebo viete čo?
Počul som, že niekto iný to naznačujú.
Čo iného môžeme robiť s Stefan?
Prečo sme ho len vysťahovať a ho cez číslo jedna, kde bol.
Takže ak chcete ísť tam.
A skutočne, to je celkom dobré riešenie.
Teraz na jednej strane, som druh z robil problém ešte horšie.
Štyri je teraz ďalej od miesta, kde by mala byť.
To by malo byť k tomuto polovicu.
>> Ale viete čo?
To by mohlo byť smola.
Možno, že číslo osem pozeral.
A tak, možno by sme sa dostali šťastie,
a tlačil ôsmich bližšie ku koncu.
Takže na konci dňa, celkom to všetky priemery von.
Nemusíme sa starať o štyri.
Všetko o čo sa starám práve teraz výberu najmenší prvok.
>> A teraz, čo budem urobiť, je zabudnúť na číslo jedna
natrvalo, pretože viem, že Zoznam za mnou je teraz zoradené.
Takže môj zoznam bol predtým veľkosti osem.
Teraz je to o veľkosti sedem.
Takže môj problém je dostať menšie, ale napriek tomu lineárne.
Takže teraz, budem vyberte prúd najmenší prvok, dva.
Šesť, osem, štyri, tri, sedem, päť.
To bol ten najmenší prvok.
Tak čo mám robiť with-- čo bol opäť Vaše meno?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph?
Budeme nechať Jozefa na mieste.
Teraz, budem predstierať že týchto ľudí are-- dobre,
Viem, že tieto dve už je zoradený.
Poďme sa teraz zameriavajú na Zostávajúcu časť zoznamu.
Šesť je aktuálna najmenší.
Osem je väčšia.
Štyri je teraz aktuálne najmenší.
Tri je teraz aktuálne najmenší.
A tak teraz, budem vybrať tri, kto je-- aké je vaše meno znovu?
SERENA: Serena.
DAVID J. Malan: Serena, keby mohol urvat si číslo a swapu with--
Kalsang: Kalsang.
DAVID J. Malan: Kalsang.
Poď späť, a my sme chystá vymeniť tie dva.
A teraz, poďme dať na autopilota to.
Chystám sa ísť a nechať to na vás chlapci zvoliť najbližší menšie prvky.
Dún, šedivý, šedivý, dún.
Číslo štyri, čo by ste mali robiť?
Výborne.
Teraz, budem robiť ďalšie prihrávka.
Dún, šedivý, šedivý, dún.
Vidím piatich je ďalší najmenší.
Teraz, budem trvať ďalšie prihrávka.
Dún, šedivý, šedivý, dún.
Šesť je najmenší.
Dobre.
Sedem je najmenší.
Žiadna zmena.
Osem je najmenší.
Hotovo.
>> Takže to, čo sme práve vykonáva opakovane výber jedného prvku za sebou
je implementovať niečo, čo sme bude formalizovať ako výber druhu.
A to je možno aj jednoduchšie na vysvetlenie,
v tom, že doslova po vás chcieť urobiť, je len udržať
tam a späť cez zoznam výberu, ďalší najmenší prvok,
kým máte hotovo.
>> Takže je to ešte jednoduchšie, snáď intuitívne, než posledný.
Skúsme posledná jeden.
Ak vy sami mohli obnoviť do nasledujúcich polôh
jeden posledný čas, uvidíme, či nemôžeme Teraz formalizovať jednu ďalší postup.
V skutočnosti, by niekto tam chcel navrhnúť,
ako inak by sme mohli ísť asi robí?
Bez hodil out módne slová alebo zoradiť z odpovedí, ktoré sú už známe,
len intuitívne, čo sme mohli robiť?
>> Divákov: [Nepočuteľné].
DAVID J. Malan: Jo.
Takže tam je tam nejaký veľký intuície.
Dobré veci sa zdá, tak ďaleko sa stalo v oblasti počítačovej vedy, keď sme sa rozdeliť
a dobyť problém delenie je na polovicu a pol na pol.
A tak my, mohol začať robiť to.
A v skutočnosti, že to bude, budeme vidieť, jeden z našich najlepších riešení doteraz.
Ale poďme sa vrátiť k tomu onedlho.
V skutočnosti, budeme robiť že o niečo neskôr tento týždeň.
Čo iné môžeme robiť to vyriešiť?
Takže všetci tu je v zdanlivo náhodnom poradí.
Vieš čo?
Skôr ako ísť tam a späť, sem a tam, tam a späť
zakaždým, to cíti ako Robím veľa chôdze.
Prečo som sa začať na začiatok zoznamu
a len dať štyri kam patrí?
Dovoľte mi teda predpokladať, že pre túto chvíľu môj zoznam je len tento prvý prvok.
So štyrmi radené v tomto okamihu v čase, ak všetko ma zaujíma, je tu všetko?
To je trochu triviálne pravda, že jo?
Rovnako ako v zozname, ktorý obsahuje jedno číslo, a že číslo štyri je samozrejme zoradené.
>> Takže mi dovoľte stanoviť že tento zoznam je zoradený.
Ale teraz mám zvyšok tohto zoznamu.
Takže teraz, som sa stretávajú dva.
Kde sa dva zjavne patria s ohľadom na štyri?
Pred štyri.
Takže to, čo môžem robiť?
Čo sa voláš?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, ak by ste mohli krok späť
na chvíľku so svojím číslom.
A teraz, čo by mal robiť Stefan tu?
Poďme posun Stefana tu.
A teraz, nech Joseph prísť sem.
A teraz mi dovoľte, aby som tvrdia, že Všetko je tu radené.
Takže, Podobný výsledok, ale zásadne odlišný prístup.
Ani som sa pozrel, čo tam dole.
Len som pokračovať v užívaní prvky ako sa im odovzdali mi,
a vysporiadať sa s nimi.
>> Takže teraz, vidím číslo šesť.
Kde sa číslo šesť patrí?
Máme dve, štyri, šesť.
Presne tam, kde ona je práve teraz.
Takže nechajme to samo o sebe, a teraz tvrdí, že tejto časti zoznamu
Teraz je zoradený.
A tak, to cíti zásadne líšia v tom, ja som len
pohybujúce sa v zozname tu lineárne, a ja som sa nikdy zdvojnásobenie späť.
Áno.
Dobre.
Tak osem, kam patríte?
Práve tu.
Perfektné.
Takže teraz, jedným.
Uh Oh.
Tento pocit, že je to bude drahé.
Teraz, v predchádzajúcom algoritmu, Len som vymenil ľudí.
Tak som mu mohol dať celú cestu na začiatok, ale potom sa sťahoval Joseph.
Ale keď som sa presunúť Joseph, teraz čo sa deje, aby byť zle?
>> A teraz, som nejako undone-- som vziať jeden krok vpred a potom
jeden krok späť, pretože teraz Josef by bolo mimo prevádzky.
Tak ideme na to.
Ak by ste mohli mať číslo jedna a krok späť len na chvíľu.
Ako môžeme put-- čo bol opäť Vaše meno?
>> ANNAN: Annan.
>> DAVID J. Malan: Annan na mieste?
Čo sa má stať, pokiaľ ide na dve, štyri, šesť a osem?
Tí všetci potrebujú posunúť.
Takže ak ôsmich chceli posunúť prvý, potom šesť, potom štyri, potom dve.
A potom Annan, ak by ste Páči sa prísť sem, dobre.
Ale tu, práve sme druh zaplatil cenu
na inom mieste v algoritme.
Kým minule s výberom triedenie, a dokonca aj bublinkové radenia,
Idem späť a tam, tam a späť,
ktorá je určite sčítanie časovo a doslova postupne.
>> Insertion sort, najprv pohľad, vyzerá, že je to
výborný múdrejší, v tom, že som len robiť pomalý, postupný pokrok,
ale nehodlám to tam a späť.
Ale ak niekto skutočne mimo prevádzku, oznámenia
všetky práce som musel urobiť.
Musel som sa presunúť polovicu zoznamu len aby sa priestor pre číslo jedna.
Takže je to rovnaká suma práce doteraz ju
cíti, len iný druh práce.
>> Poďme pokračovať.
Takže teraz vieme, že každý medzi jedným a osem sú zoradené.
Tu mám číslo tri.
Ak máte radi vyzdvihnúť číslo tri, jeden krok späť.
A čo vy musíte urobiť?
Jo.
Tak to je ešte jeden, dva, tri kroky.
Tri jednotky času, ktorý práve stáli ma, takže tri môžu teraz zmestí.
A konečne, sedem.
>> Poďme ďalej a majú si vziať krok späť.
Toto je ešte len vo chvíli, aby nám štát jedna jednotka času, ale to je v poriadku.
A teraz, päť deje na byť o niečo drahšie.
Ak by ste chceli urobiť krok späť.
Musíme sa pohybovať osem, a sedem a šesť.
A potom sa všetci je teraz zoradené.
Tak veľká ruka našim dobrovoľníkom tu.
Ďakujem ti veľmi pekne.
>> [APPLAUSE]
>> Ďakujem vám všetkým.
Ďakujem vám všetkým.
Tak uvidíme, teraz len, ako nákladné to všetko bolo.
Poďme zvážiť možná najjednoduchšie z nich, bublinkové radenie.
A ja hovorím najjednoduchšie, len preto, môžete vyriešiť ju nenásytne obyčajným
vyriešiť pairwise problém.
Opraviť pairwise problém Tu, znovu a znovu
a znovu, opakovanie toľko koľkokrát je skutočne potrebujú, aby.
>> Tak to dopadá, že s bublinou druhu, dobre,
koľko krokov musím prijať Prvý priechod z tohto algoritmu?
Mohol by som take-- poďme see-- jedného, dva, tri, štyri, päť, šesť, sedem.
A je tu osem elementov sem.
Takže je to ako n mínus 1 krokov k sa od začiatku zoznamu
na koniec zoznamu.
>> Ale s výberom Triediť, pripomenúť, že ja som znovu a znovu Výber prvkov
a znovu to najmenšie, Dávam to na mieste,
ale potom som nie som pozerá za mnou znova.
Takže si myslím, že je to trochu jasnejšie potom, že prvýkrát, môžem
musieť vziať všetky n mínus 1 stupni nájsť najmenší prvok.
Potom som dal je na mieste, a ja vypudiť ten, kto tu bol predtým.
>> Ale potom som si nemusím držať pri pohľade na tento prvok,
pretože viem, že je to Už najmenšie.
Takže teraz, môžem sa pozrieť na práve siedmich elementov a potom šesť prvky,
potom päť prvkov, potom štyri elementy.
A tak matematicky, ak n je počet prvkov alebo čísel
že sme začali s, ktore si možno predstavit že sa jedná o rovnaké ako n mínus 1,
a n mínus 2 stupne, a n mínus 3 stupne,
plus n mínus 4 kroky, a to tým až na doraz jednom kroku.
A ja som na poslednú osobu.
>> A ak si spomínate, že veľa Štatistiky knihy alebo matematické knihy
mať tie vzorce na strane Viazaná zadné alebo predné z nich,
Ukazuje sa, že tejto sérii môže byť vyjadrená jednoduchšie
ako n krát n mínus 1 nad 2.
A to je v poriadku, ak to nie je v popredí svojej mysli.
To je však skutočne pravda.
To je len jednoduchší spôsob písania.
A potom, ak si myslíte, späť na základnej škole,
keď ste práve spustenie násobí veci, to samozrejme,
práve n druhú mínus n deleno 2.
Všetko, čo som urobil, je rozšíriť výrazy tam.
A tak sa poďme prepísať trochu inak.
To n štvorčekované delí o 2 mínus N / 2.
>> Takže znovu, som len trochu uplatnenie niektorí aritmetický pravidlá tu.
Nevšimnúť teraz, že najväčší termín v tomto výraze, aby som tak povedal,
je to, že n na druhú.
Takže áno, je to n kvadrát delené 2, mínus n / 2.
>> Všeobecne ale, ak je n je Bude to veľká hodnota,
Budem tvrdiť, že n štvorcový bude dominantným faktorom.
Je to len bude väčší prispievateľ
na počte krokov, ako n / 2.
Tak čo tým myslím?
Skúsme si jednoduchý príklad, a to aj hoci matematika dostane trochu veľký.
>> Takže predpokladám, že sme mali 1 milión ľudí na javisku, alebo 1 milión vecí
že chceme usporiadať.
Poďme zapojte milión do presne v tomto vzorci
vidieť, koľko krokov to trvá celkom triediť milión prvky pomocou povedzme,
výber triedenia.
>> Takže budeme mať rovnaký vzorec ako predtým.
Ja by som pripojiť milión, tak, že som si milión štvorčekované delené 2,
mínus jeden milión deleno 2.
Ak sa mi, že matematiku v predstihu tu máme 500 miliárd
mínus 500000, ktorý nám dáva 499999500000,
čo je sakramentsky veľký.
>> V skutočnosti, ak si porovnať teraz 499000000000, 999000000,
500000 proti našej pôvodnej hodnoty, 500000000000, je to tak sakramentsky blízko.
Je to tak? n štvorčekované deleno 2 dáva us-- alebo skôr, n štvorčekované deleno 2
dal nám 500 miliárd.
To je sakramentsky blízko na 499,999,500,000,
čo znamená, že sa odpočíta off 500000, alebo všeobecnejšie, odpočítaním off
n štvorčekované, nie je naozaj veľký problém.
N štvorcový robí tieto Čísla rastú naozaj rýchlo.
>> Teraz, to je dôležité len do tej miery ako my, ako počítačových vedcov,
sú všeobecne nebude toľko starostlivosti o nuansy týchto vzorkách
a čo presne presné odpovede.
Vieme len, že starostlivosť, viete čo?
Na konci dňa, tento vzorec je na poradie n štvorcový.
>> Áno, sme vydelením 2 v tam.
Áno, budeme odčítať z n mínus 2.
Ale na konci dňa, termín že nás naozaj bolí a stojí nás
veľa krokov, je to, že námestie termín.
A tak to, čo počítačový vedec bude všeobecne robiť
je ignorovať všetky tie menších objednávok podmienky,
a len sa pozrite na ten, ktorý najviac prispieva k nákladom.
>> A to je pekné, pretože môžeme teraz hovoriť v oveľa väčšej univerzálnosti
o algoritmy, a môžu porovnávať ich.
A skutočnosť, že som O použití tohto je zámerné.
Keď poviem, že na objednávke o, ja som konkrétne
s odkazom na niečo volal veľký O. A big O
je zápis, že počítač vedec používa na opis
horná hranica niečo.
>> Takže keď hovoríte, že algoritmus je vo veľkom O z n na druhú,
ako som navrhol len pred chvíľou, že prostriedky
že pokiaľ ide o jej chod úväzok alebo jeho účinnosť,
to znamená v poriadku n druhú krokov.
Možno viac, možno menej.
Ale to je na poradie n na druhú.
A to je horná hranica.
Nie je to bude viac bolestivé než to.
Nie je to bude n kubický, alebo 2 na n, alebo niečo oveľa väčšieho.
Jedná sa o hornú hranicu Na čo to je cena.
Takže vzhľadom k tomu, poďme zvážiť len niekoľko príkladov.
A to je len konečný zoznam veľmi časté prevádzková doba
pre algoritmy, ktorý je určený na ilustratívny niektorých vecí, ktoré sme
Videl už.
>> Tak napríklad v prípade výber triedenie, čo som tvrdil tu
je beh tejto výberom Triediť je čas je na poradie n na druhú.
V najhoršom prípade, budem mať celá partia náhodných čísel tu.
A ako sme videli matematicky, keď som chôdzi držať
v zozname, a to prostredníctvom zoznam, výber budúci najmenší
znovu a znovu prvok, ak I vlastne zapísať všetky kroky
Beriem, ako som navrhol formulaically predtým, je to na objednávku n štvorcové
kroky, ktoré beriem.
>> A ukázalo sa, že bublina triedenie a insertion sort
sú rovnako pomaly v najhoršom prípade.
Zoberme si napríklad, insertion sort, úplne posledný algoritmus sme sa zaoberali,
ktorý mal s nami pozrieť na prvok, a vložte ju tam, kam patrí.
A potom sme sa pozreli na ďalší prvok, a vložil ju tam, kam patrí.
>> Tak zváži najlepší možný scenár.
Dajme tomu, že som mal môj dobrovoľníci line up doslova ako je tento, jedna až osem,
už je zoradený.
Koľko krokov je insertion sort bude trvať triediť osem ľudí,
keď dorazí na pódiu vyzerajúce takto?
>> Osem ľudí už je zoradený.
A ja používam insertion sort.
Že posledný z algoritmov.
Dobre, poďme reenact naozaj rýchlo.
Takže keď začnem tu, vidím jeden.
Kde vôbec nepatrí?
Patrí tu.
Vidím dva.
Kde dvoch patrí?
Práve tu.
Vidím tri.
Kde Tri patrí?
Práve tu.
>> Vidím štyri.
Práve tu.
Päť, šesť, sedem, osem.
Neexistuje žiadny dôvod, aby sa opakujem.
A tak, ako veľa krokov je to, že, pokiaľ ide o n?
Je to na objednávku n schodíky, že jo? n mínus 1.
Ale vzal som lineárny číslo krokov, a teraz som urobil.
Tak to je najlepšie prípad, hoci.
Čo najhoršom prípade?
Aké bolo osem tam, a sedem bolo tam dole,
a jeden a dvaja boli tu, tak že zoznam bol skutočne zvrátiť?
>> No, čo sa deje v skutočnosti či je to číslo?
A urobíme len pár príkladov.
Čo keď, naozaj, číslo osem je tu, a number-- pokriky.
Takže to, čo v prípade, naozaj, číslo Osem je celú cestu sem,
a ja som s použitím insertion sort?
>> OK.
Tvrdím, v tejto chvíli je to na mieste.
Ale teraz, siedmej Odkiaľ siedmich ísť?
Samozrejme, že ide cez tu.
Takže som sa pohybovať cez osem jednom mieste.
A teraz šesť, kde to ide?
No, v poriadku.
Teraz musím sa pohybovať cez osem miesto, a sedem viac než na mieste,
a potom som PLOP nadol šesť.
>> Takže prvý čas, že náklady mi jeden krok veci do poriadku,
Potom ma to stálo dva kroky opraviť veci.
Koľko krokov je to bude trvať na opravu
Čo dať päť na správnom mieste?
Tri.
Pretože teraz musím presunúť jeden, dva, tri.
Koľko krokov to bude trvať dať štyri na správnom mieste?
4 a 5, a 6, a 7.
>> A tak je to matematicky totožné s to, čo sme popísali pre výber druhu.
Máme túto sériu to je len rastie.
1 plus 2 plus 3 plus 4, alebo naopak, 7 a 6
a 5 plus 4 spočíta pre dnešné účely tak, aby na poradie n na druhú.
>> Dovoľte mi tiež, že stanovuje, bublinkové radenie je tiež v n na druhú.
Vzhľadom k tomu, s perličkovou druhu, každý Tentokrát som prejsť zoznam,
Beriem zhruba koľko krokov?
Zakaždým, keď som sa doslova pešo odtiaľ tam?
Zhruba n krokov.
Ale koľkokrát by som mohol musieť prejsť zoznamu?
>> No, hrubo n čas.
Možno n mínus 1, ale zhruba n časy.
Tak prečo je to?
No, s bublinou druhu, pokiaľ začneme s bublinou druhu,
so zoznamom v ten najhorší možný situácie, čo je opäť úplne
dozadu, čo sa bude diať?
Aj prejsť zoznam, a číslo Patríte-celú cestu tam.
>> Ale s bublinou druhu, ako ďaleko sa môže stať jeden prejsť na svojom prvom prechode zoznamu?
Koľko miesta sa dostal bližšie na správne miesto?
Len jeden.
Takže ak máte trochu dôvod cez to, zakaždým, prostredníctvom tohto algoritmu,
Dávidovi, ktorí sa zhruba n krokov.
Ale koľko prechádza v zozname je to
bude trvať na jeden bublať na ľavej strane, kam patrí?
>> Má sa pohybovať podobne, n priestory Tadiaľ.
Takže stačí k tomu triedenie zoznamu, Musím chodiť sem a tam n-krát.
A zakaždým, ja som pri pohľade na n elementy.
Takže robiť veci, n n krát na poradie n na druhú.
>> Teraz uvidíme v niektorých šortiek, ktoré
sú uložené v CS50 je ďalší problém set, iný prístup na nich,
ale teraz, nech to jednoducho vziať do úvahy niektoré iné prevádzkové časy,
zvlášť v prípade, že triedenie tí brať trochu času, aby drez.
Čo je to algoritmus sme videli už , Ktorý berie na poradí n krokov?
>> To, čo by mal mať lineárny číslo krokov, ktoré sme doteraz videli?
Čo je to?
Vyhľadávanie telefónny zoznam.
Prvý algoritmus.
Je to tak?
Tam, kde sme lineárne hľadanie Mike Smith?
Naozaj.
Od týždňa nula, keď som začal sústruženie jednu stránku naraz,
a dokonca povedal som, že to bolo celkom lineárneho pocit algoritmu,
a mali sme ten obraz na strane doska s rovnou červenou čiarou
a rovný žltý linka, tie boli skutočne
algoritmy, ktoré sú vo veľkej O n.
>> Vzhľadom k tomu, nájsť Mike Smith v telefóne kniha n stránok, v najhoršom prípade,
mi n krokov môže trvať.
Čo o tom, dochádzku?
Jeden dva tri štyri päť šesť.
Aký je doba chodu tohto algoritmus pre prijatie dochádzku?
Veľký O n, pretože teoreticky I musieť bod všetci v miestnosti.
>> Teraz ako stranou, čo o ďalšia optimalizácia z týždňa nula?
Dve, ​​štyri, šesť, osem, 10, 12.
Počítač by vedec si uvedomiť, počkajte chvíľu,
to je na poradie n delené dvoch krokoch.
Je to tak?
Pretože robím dvoch ľudí naraz.
Ale budeme ignorovať tieto nižšieho rádu podmienky,
a my len tak vyhodiť priepasť o 2,
a len povedať, veľké O n pre tento algoritmus, tak.
>> A čo toto?
Budeme preskočiť niektoré z nich, ale to, čo bol algoritmus, ktorý bol log n?
To zabralo zhruba log n kroky?
Priepasť a panuj.
Presne tak.
Rovnako ako telefónneho zoznamu napríklad v týždeň nula a dnes ráno,
kde sme rozdelili problém znovu a znovu a znovu.
Čerpal sme to na tabuli v týždni nula ako zakrivený zelená linka,
a my sme povedali, že je to deň, logaritmickou algoritmus.
>> A naozaj, počet krokov IT potrebná na vykonanie rozdeľ a panuj,
alebo binárne vyhľadávanie, ako začneme volať to, rovnako ako v telefónnom zozname,
je rádovo log a len pár krokov.
A to je trochu divný jeden.
>> To, čo sa jeden krok, alebo presnejšie
konštantný počet krokov?
Možno je to dvoch, možno je to tri, ale počítačový vedec len
zjednodušuje to ako veľký O 1, niektoré konštantný počet krokov.
Čo je to niečo, čo by ste mohli urobiť, že trvá konštantný počet krokov?
>> Aký je doba prevádzky tlieskať?
Konštantný čas.
Je to tak?
Rovnako ako to, čo je doba prevádzky robiť niečo, ktorý berie len jeden
prevádzku, rovnako ako vytlačiť F Hello World.
To by mohlo byť povedal, aby bol konštantný čas, ibaže menej rohový prípade s tlačovým F,
Čo by mohlo čas beží tlače F byť v skutočnosti?
A prečo?
Čo je n meranie v tomto prípade?
>> Divákov: [Nepočuteľné].
DAVID J. Malan: Presne tak.
Počet znakov chceme vytlačiť.
Takže je to veľmi kontextová.
Dnes sme sa zameriava veľa na písmená a číslice tu na palube.
Ale môže to byť tiež znaky v skutočnom reťazci.
Tak to dopadá je tu ďalší opatrenie, ktoré začnú starať o,
a to je opak big O, aby som tak povedal.
>> To je omega notácie.
Vzhľadom k tomu, veľký O znamená, že to, čo je so horná viazané na bežiaci čas?
Maximálne, koľko času Možno niečo vziať?
Omega-- Ospravedlňujeme sa, tento stále prichádza up-- je opak toho,
čím je to dolná hranica na Množstvo času, niečo, čo by mohlo trvať.
>> So. Napríklad, čo je algoritmus ktorý berie vždy n štvorcových kroky?
No, jeden z algoritmov sme videli dnes, v skutočnosti, že môže byť tiež.
Selection sort.
Výberom Triediť to celkom hlúpe.
Aj keď sa algorithm-- ľúto, a to aj v prípade, že je pole už zoradené,
Voľba triedenie sa chystá chôdzu držať v zozname
aby sa uistil, že má najmenší prvok znovu a znovu a znovu.
A aj keď ľudia v diváci vedia, že, počkajte chvíľu,
už prešiel najmenší prvok, počítač
nevie, že až to vyzerá celú cestu v zozname.
Podobne, dolná hranica, ktorá môžu byť tiež vzaté do úvahy
by mohol byť lineárny čas.
>> Koľko času trvá triediť n prvky v najlepšej
Prípad použitia niečo ako bublina druhu?
Predpokladajme, že váš zoznam už je zoradený.
Povedali sme, bublinkové radenie berie na poradie n druhú krokov.
Ale čo keď je to už je zoradený?
Čo keď si uvedomíte, po jeden priechod cez pole
že ste urobili žiadne swapy?
Potrebujete udržať robiť viac prechádza?
>> Nie.
Takže spodnú hranicu bublinkové triedenie by mohlo byť povedal, aby bol lineárny.
Omega n.
A my si pozrieť ďalšie z nich, ako.
Takže poďme sa rýchlo pozrieť na iba vizualizáciu tu
vidieť, ako sa tieto odlíšiť.
Chystám sa ísť sem dole do toho Stránka, ktorá je k dispozícii na internetových stránkach C50 je,
ale bude to bolieť, aby si prácu, pretože používa technológiu nazvanú
Java applety, čo je z veľkej časti podporovaný v týchto dňoch,
aspoň Chrome a niektoré ďalšie produkty.
>> A dovoľte mi, aby som do toho pustite a urýchlite up a vysvetliť, čo sa deje.
To je prejavom bubliny triedenie, prvý algoritmus sme sa na.
A to je vizualizácia, že každý z týchto tyčí predstavuje číslo.
Čím väčšia je bar, Čím vyššie je číslo.
Čím menší je bar, čím menšia je počet.
A čo môžete vidieť vizuálne, a to aj aj keď to bude super rýchly,
je to, že červený pruh je ako ja, chôdza sem a tam upevnenie problémy.
Môžete vidieť, že väčšie prvky skutočne vyviera na pravej strane,
a na menších elementy vyviera doľava.
A tu dole, keby sme v skutočnosti vyzerajú lepšie,
vlastne môžeme počítať počet porovnania a swapov
ktoré boli vyrobené.
>> Ale namiesto toho, poďme sa pozrieť na druhom algoritmu
sme sa pozreli na skôr s našou dobrovoľníci, výber druhu.
Vizuálne, to má veľmi odlišný efekt.
Ale je to opäť veľmi intuitívne, v že držíme výber budúci najmenší
prvok, a dostali sme trochu šťastia.
To sa cítil zásadne rýchlejšie.
Ale keď sme bežali to znova a znova a opäť s množstvom vstupov,
videli by sme, že je to naozaj stále ešte vo veľkej O n na druhú.
>> Poďme urobiť jednu poslednú tu, insertion sort,
ktorý bol tretí algoritmus sme sa pozreli na, a odvolanie
že tento človek sa zaoberá prvky, ako to s nimi stretne,
ale potom sa to možno posuny veci, nad aby sa uvoľnilo miesto,
vkladanie prvkov tam, kam patrí.
>> A to tiež skončí dávať Konečný výsledok. Teraz všetky tri z tých,
cítil celkom rýchlo.
A skutočne, bežal som ich v celkom dobrý klip.
Ale v podstate, oni sú všetci dosť hrozné, aby som bol úprimný.
Všetky tieto algoritmy doteraz že dráha v veľký O n štvorcový
trvať docela dost čas pre spustenie v konci.
>> A skutočne, môžeme vidieť a cítiť sa to konečne
keď som vytiahnuť tento tretí a posledný demo.
To je ďalší vizualizácie, čo sa deje
ukázať bublinkové radenia na ľavej strane, výberom Triediť v stredu,
a niečo, ako jeden z našich ruka vyvoláva skôr navrhol,
merge sort na pravej strane.
Predel a panuj Stratégia na pravej strane.
A to je v skutočnosti to, čo sme ísť sa pozrieť na stredu.
Ale poďme čas tieto bežať paralelne.
To je zhruba rovnaký počet prvky, všetky beží v rovnakom čase.
Bubble sort vs výberu triediť vs zlúčenie druhu.
>> Teraz sa všetci beží teoreticky v rovnakom čase.
CPU beží na rovnakú rýchlosť, ale
Môžete cítiť, ako je to nudné veľmi rýchlo stane,
a ako rýchlo, keď sme sa vniesť trochu týždňa
algoritmy Zero môže sme sa veci urýchliť.
>> A teraz poďme porovnať tieto v poslednom forme.
Chystám sa pokračovať na webové stránky CS50, kde
máme túto konečnú odkaz pre dnešok, kde niekto na internete
láskavo dal dohromady video, ktoré zachytáva to, čo iný triedenie
algoritmy znieť.
To je insertion sort.
>> [Pípanie]
>> Pričom sa uchádzate frekvenciu založené na výške baru baru.
Je to bublina druh.
>> [Warped pípanie]
>> Pripravujeme ďalšie je-- prichádza up ďalšie je-- výber triediť,
kde opäť, my výber budúci najmenší prvok,
a my môžeme vidieť, že rast zľava doprava.
>> Merge sort, náš víťaz tak ďaleko ešte dnes.
Všimnite si, ako je to delenie vecí do [nepočuteľný] polovicu a štvrtiny.
Gnome triedenie, ktoré my nie hovoril o, a vytvára vizuálne
a audally trochu iný tvar a zvuk.
Tam a späť, čistenie veci.
Tiež check out Heapsort na webových stránkach tento chlapík.
>> A to je všetko.
Uvidíme sa nabudúce.
>> [Whooshing a hudba]