>> [Muusika mängib]
>> DAVID J. Humala: See on CS50.
Ja see on algusest nädalal kolm.
Nii on meil palju põnevaid asju katteks täna.
Palju võimalusi vabatahtlike laval.
Ja lõpuks, täna on ei tähenda koodi üldse.
Aga see on umbes ideid ja see on umbes algoritme,
ja tegelikult toob tagasi mõned õppetunnid nädalal null,
kus mäletate, me tutvustas seda Kaameus.
Ka laenamine inspiratsiooni sellest, et alustada
lahendada üha keerukamaid probleeme algoritmiliselt.
Aga kõigepealt paar teadaandeid.
Nii et üks, kui soovid liituda CS50 töötajad ja klassikaaslastega lõunasöögi
sel reedel, nii siin kui Cambridge ja New Haven,
külasta kursuse veebileht, kus URL võib leida.
Loeng seda kolmapäeval ei ole siin Sanders.
See on ainult võrgus, nii et häälestama CS50 veebisaidil
kas siin Cambridge või New Haven samuti.
>> Ja siis probleem seatud kaks on juba pihus.
Kui te ei ole sukeldus veel, lubage mul pakkuda tugevalt sõnastatud ettepanek
et eriti nüüd, kui probleem seab ette,
sa tõesti tahad hakata nüüd, kui ei ole võõpama natuke nädalavahetusel või enne
kui nad esimest korda minema Reedeti, sest sa oled
leiavad, et nad ei ole tingimata saada enam või rohkem väljakutseid kohta
se.
Ma arvan, et sa leiad, et Üldiselt nad kipuvad võtma umbes
umbes sama palju aega.
Aga see sõltub kindlasti õpilase ja see
sõltub mõtteviisi kellega läheneda.
Aga alati, sa lähed eel vastu mõne seina,
ja sa lähed lüüa mõned bug, ja sa oled lihtsalt
ei hakka saama sellest üle saada mingil ajahetkel.
Ja see on väga väärtuslik, et oleks võimalik sammu kaugusel, tulevad tagasi järgmisel päeval,
minna tööaega postitust CS50 Arutle vms, tegelikult saada vabastada.
Nii et hoidke seda silmas pidades.
Alates esimesel võimalusel on parim asi, mida saate teha.
Nii et siin on, kust me alustasime klassi, üle nädala null.
Ja me saame vabatahtlikuna siin, et aidata mul leida mikrofoni?
OKEI.
Püsti juba.
Tule üles.
Arvan, et see, kuidas see läheb tööle.
Mis su nimi on?
ALAN ESTRADA: Alan Estrada.
DAVID J. Humala: Alan Estrada.
Tule üles.
Meeldiv tutvuda.
ALAN ESTRADA: Meeldiv kohtuda.
DAVID J. Humala: Ja siin olid meiega nädalal null, muidugi.
ALAN ESTRADA: olin.
Ma olin.
>> DAVID J. Humala: Nii võiks minna käia ja leida meile Mike Smith,
nii kiiresti kui võimalik?
Nii kiiresti kui võimalik.
Sõna otseses mõttes pisaravool probleem poole kui vaja.
>> ALAN ESTRADA: Um.
DAVID J. Humala: Sõna-sõnalt pisaravool probleemi poole.
>> ALAN ESTRADA: Oh.
Mm.
Väga hasti.
>> DAVID J. Humala: OK.
Väga hea.
Aitäh.
ALAN ESTRADA: Väga hea.
OKEI.
>> DAVID J. Humala: Ja nii nüüd, olete whittled see alla
poolega Probleemi suurus.
Nüüd me oleme alla veerandi.
Kas olete pöörates tähelepanu millisel poolel me hoida?
>> [Naerab]
>> ALAN ESTRADA: Jah, ma think--
>> DAVID J. Humala: Mis osa on meil?
ALAN ESTRADA: sallid, nii.
>> DAVID J. Humala: OK.
Aga Mike Smith läheb olla pärast sallid.
So--
>> [Naerab]
>> Hästi.
ALAN ESTRADA: Kus me otsime?
DAVID J. Humala: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. Humala: Nüüd me oleme kirurgia.
Nüüd, arstid.
Now--
>> ALAN ESTRADA: Let's- lähme päris.
Real.
>> DAVID J. Humala: Real.
OKEI.
Kui teil on vaja Real.
Nüüd, mil moel on Mike Smith?
>> ALAN ESTRADA: Nii.
>> DAVID J. Humala: Millist teed?
ALAN ESTRADA: Oota.
M on-- õige?
Alustasime with--
>> DAVID J. Humala: Jah.
Nad lahkusid.
Teie õigus.
>> ALAN ESTRADA: Jah.
>> DAVID J. Humala: Nii Mike'i siin.
ALAN ESTRADA: Mis?
>> [Naerab]
>> Bad näiteks poisid.
Vabandust.
DAVID J. Humala: See õpetab sa hüpe läbi oma toolil.
>> ALAN ESTRADA: Oh.
Oh.
Sain su kätte.
Oh.
See on-- OK, ma sain sulle.
Smith siin?
>> DAVID J. Humala: Smith, aitäh.
Nii et ma hoian soojaks Smith?
>> ALAN ESTRADA: Oh, jah.
Ei ei ei.
Oh ei.
See on minu.
>> DAVID J. Humala: Oh, sul Smith.
OKEI.
>> ALAN ESTRADA: Jah, ma sain Smith siin.
Vabandame, poisid.
Ma arvasin, et Michael-- me otsisid Michael.
Vabandust.
>> DAVID J. Humala: See on OK.
Olgu, nüüd oleme arvesse Paccini ja Pojad.
>> ALAN ESTRADA: Paccini ja pojad.
DAVID J. Humala: Ainult sina ja ma on sellel.
OKEI.
Leia meid Mike Smith.
Smith.
>> ALAN ESTRADA: Smith.
>> DAVID J. Humala: Smith.
Me oleme R prügi.
ALAN ESTRADA: Prahi.
Oh.
See läheb veidi aega võtta.
>> [Naerab]
DAVID J. Humala: Shoes.
Oleme kingad.
>> ALAN ESTRADA: Nüüd oleme gonna--
>> DAVID J. Humala: Nice.
ALAN ESTRADA: misjärjekorras
[Naerab]
Oh, see on hea.
[Naerab]
>> DAVID J. Humala: See on OK.
>> ALAN ESTRADA: Oh, see on hea.
Ma ei usu, et ma lähen on PSAT semud pärast seda.
DAVID J. Humala: Hea.
Spordi.
ALAN ESTRADA: Sporting.
Um, L, M, N, O, P.
DAVID J. Humala: OK.
Nii saab pisar see pooleks.
See on OK.
See lõpeb halvasti niikuinii, sest Mike Smith ei ole kollased leheküljed.
>> ALAN ESTRADA: Aw.
>> DAVID J. Humala: Ei, see on OK.
Aga olgem teeselda, nagu ta on sellel lehel.
Nüüd, kui olete whittled probleemi alla ühe lehekülje, ja leidsime Mike Smith.
>> [Hõiskab]
OK aitäh sulle.
OKEI.
See oli erakordne.
Aga see oli veel kiirem kui lineaarne otsing,
kus hakkame juures alguses raamat,
ja me liigume meie teed vasakult paremale, lõpuks otsin Mike Smith.
Ja nii, kui telefoniraamatus oli äkki 1000 lehekülge,
võibolla see oleks võtnud meil 10 või nii lehele pisaraid.
>> Aga sa võisid võimendatud puudutanud oletus
käigus kõik see, mis on öelda et telefoniraamatust eelnevalt oli siis?
Sihtrühm: sorteerida.
DAVID J. Humala: See on järjestatud.
Õigus?
See on tähestikulises järjekorras, nii et et kõik need nimed ja numbrid
on järjestatud alates A kuni Z ja tähestikuliselt vahel.
Aga täna on meil nüüd küsida küsimus, noh,
Kuidas Verizon või telefon Ettevõte saada see, et riik?
>> Sest see on üks asi, mida võimendada selle eelduse, mistõttu
lahendada probleemi, mille algoritmi efektiivsemalt.
Aga me kunagi küsis nädala null, noh,
kui palju see maksis Verizon või keegi teine
saada see telefoniraamat sorteeritud järjekorras?
>> Õigus?
Ei ole oluline, kui soojaks Mike Smith
on super kiire, kui see viib teid aasta sorteerida lehekülge esialgu.
Õigus?
Sa võid ka lihtsalt sõeluma läbi randomiseeritud telefoniraamat,
kui see saab olema super kallis sortida.
Nii et kui meil on veel üks vabatahtlik.
Võtame otsida siin kuidas me might-- tule up-- kuidas
me võiks minna sorteerimine neid.
>> Ja kui Jordan võiks tegelikult liitu meiega siin laval.
Tule üles hetkeks.
Mis su nimi on?
CAROLINE: Caroline.
DAVID J. Humala: Caroline, tule üles.
Ja siis saad liitus minu ja Jordaania siin.
Caroline, aitäh.
Hästi.
Mis meil siin Caroline on 26 sinine raamatud
et FAS kasutab hallata Teatud lõpueksamid.
Need saavad raske leida, aga mida me oleme teinud eelnevalt
on see, et me panime kellegi nime esiküljel kummagi,
kuid me oleme hoidnud it simple Seejärel paneb välja täisnimed.
Nii et me paneks isiku nime L, D, J, B, kõik viis A kuni Z,
kuid nad juhuslikus järjekorras.
Ja kui sa oleks, räägi oma tee läbi probleem kui
seda teha, võite minna ja sorteeri need meile A kuni Z.
>> Sihtrühm: OK, nii et L on nagu, keset.
C hakkab.
B. J enne L. B, Q.
>> DAVID J. Humala: Hoia, et arvas üks sekund.
Sest muidu on see vaid huvitav teile, mina ja Jordan.
Seal me läheme.
Sihtrühm: [kuuldamatu].
R.
DAVID J. Humala: OK.
Mida sa teed?
>> CAROLINE: M tuleb pärast O.
>> DAVID J. Humala: OK.
>> CAROLINE: O.
DAVID J. Humala: O, hea.
>> CAROLINE: E.
>> DAVID J. Humala: E, F. Jah.
>> CAROLINE: T, U, V
>> DAVID J. Humala: V, T, U, V Seega Tundub, et sa oled making-- edasi.
Tundub, et sa üritad suur kuhi siin,
ja selline suur kuhi seal.
Nii et esimene pool tähestikku, teisel poolel tähestikku.
OKEI.
Väga hea.
Kind of jagada probleem kaks.
M, N, X. Jah.
CAROLINE: K.
DAVID J. Humala: OK.
K. Nii et sa oled selline valides neid üksteise järel,
paneb see kas vasakule või paremale, või Z läheb põrandale.
OKEI.
>> CAROLINE: Z läheb põrandale.
>> DAVID J. Humala: OK.
Y läheb põrandale.
Nüüd saame panna X.
>> CAROLINE: G.
DAVID J. Humala: G läheb vasakule.
S läheb paremale.
Olgu A läheb kogu tee vasakule.
>> CAROLINE: A, B, C, D.
>> DAVID J. Humala: Nüüd hea.
Meil A, B, C W läheb sinna.
Olgu, T.
>> CAROLINE: H, I, J.
DAVID J. Humala: H, I, J. hea.
CAROLINE: Keskel, ma gonna--
DAVID J. Humala: OK.
Nüüd, me ei kavatse sellist ning ühendada need erinevad vaiad.
Nii A-C, siis ma näen D, ja E, F, ja G ja H ning I. Nice.
J, K. Ja siis see pakk on tagurpidi, kuid see on OK.
Muidugi.
Me ei lõigata mõned nurgad.
OKEI.
Ja siis me peame W, X, Y, Z.
>> CAROLINE: Jah.
>> DAVID J. Humala: Suurepärane.
Nii suur aitäh Caroline sorteerimiseks neid.
>> [Hõiskab]
>> Aitäh.
Tänan teid väga.
Nüüd Vaatleme korraks kuidas Caroline läks seda teed, et
ja mida täpselt me suutsid mina-- kuidas me
suutsid lahendada seda probleem siis, kui me olime lihtsalt
antud terve hunnik juhuslikult sisendeid.
>> Noh, tundub, et seal oli natuke süsteem seal?
Õigus.
Nii et varasemad kirjad tähestiku, ta
pani vasakule, ja hiljem tähed tähestikus,
ta paneb õigesse.
Ja niipea, kui ta leidis, mõned proksimaalne tähed, need
et minna paremale üksteise kõrval, ta paneks neid selleks.
Ja nii me pidime need väikesed hunnikud sorteeritud mille sagedus.
>> Ja nii see on päris see, mida enamik meist inimesed teeksid.
Meil oleks justkui sõeluma läbi, ja me tahaks sellist olema mehhanism.
Aga see võib olla raske kirjutada Kirjutage see valem per se.
Tundus veidi rohkem orgaanilisi kui see.
Vaatame, kas me saame nüüd seotud Probleemi vähemate sisendeid.
>> Selle asemel, et 26, olgem midagi märksa vähem
lihtsalt öelda, seitse, taga Nende uste niiöelda.
Kas on ainult seitse numbrid?
Ja kui eesmärk nüüd Samas on leida väärtus,
Vaatame, kuidas tõhusalt saame minna seda teed.
Ja vaatame, kas me saame nüüd hakkavad kehtima mõned numbrid,
või mõne valemid kellega kirjeldamiseks tõhusust meie telefoniraamat
algoritm, meie eksam raamat algoritm, ja üldisemalt informatsiooni leidmine.
>> Nii see, lubage mul minna, ja puuteekraanil siin,
panna veebibrauser, mis on just need seitse uksed.
Ja kui me saaksime veel ühe vabatahtlikuna tulge siia,
Ma panin need samad uksed siin.
Quick vabatahtlikuna.
>> See one-- demos ei kavatse kiiremale ja kiirem nüüd.
Tule alla.
Mis su nimi on?
Trevor: Trevor.
>> DAVID J. Humala: Trevor?
Olgu, Trevor, tule alla.
Nii Trevor on vabatahtlikult siia teha sarnane probleem, kuid see on
kitsam ja mis läheb et saaksime proovida vormistama nüüd
Protsessi sorteerimiseks need numbrid.
>> Nii Trevor, nice to meet you.
Nii et siin on massiiv, nii et rääkida, nimekirja seitsmest uksed.
Lase käia ja leida meile number 50.
Ja siis pärast fakti, ütle meile, kuidas sa leidsid.
Kui olla-- kõik korras.
Jah, see on üks siin?
Uh-oh.
OKEI.
Sa klõpsad, et üks.
Väga hea.
>> Ja hea.
Nüüd sa klõpsasid seda.
Ja las ma annan teile mikrofoni, nii, et teil on see hetk.
Lase käia ja klõpsake kõrvalmajas, et te kavatsete.
Jah, hea.
Trevor: Kas ma unclick uks?
DAVID J. Humala: Ei, sa ei saa unclick.
Trevor: OK.
See.
DAVID J. Humala: Kuhu sa tahad minna?
Milline?
>> Trevor: See üks.
>> DAVID J. Humala: Ei
>> Trevor: OK.
See.
>> DAVID J. Humala: Jah.
See oli hea.
Hästi.
Mis oli teie algoritm või kord seda teed, Trevor?
>> Trevor: Ma lihtsalt läks läbi uksed, kuni leidsin 50.
DAVID J. Humala: OK.
Suurepärane algoritm.
Nii et trahvi.
Sest tegelikult, kui ma paljastada, mis on taga kaks ust, mida
me leiame siin on see, et meil on ainult juhuslik sisend.
Nii et tegelikult oli nii hea, kui sa võiksid saada.
Ja tegelikult, et sul parem kui ammendavalt otsivad kogu massiiv,
sest see oleks olnud tõesti õnnetu, kui sa tabanud number
50 päris viimase ukse.
Aga mis siis, kui me selle asemel saatis sulle oletus.
Oletame, ma justkui kõik Nende uste ümber,
nii, et teil on numbrid järjestatud seekord
kuid seekord on see tegelikult erinevalt-- seekord
see on tegelikult järjestatud teile.
Ja nüüd eesmärgiks käepärast on tabanud number 50.
>> Trevor: OK.
>> DAVID J. Humala: Mis on Sinu algoritmi saab olema?
>> Trevor: Noh, kui see on sorteeritud, see kas lähed
to olla-- kui suurim on suurim, alanevas, siis saad olla esimene,
või kui see on vastupidine, see saab olema viimane.
Nii et ma lihtsalt puuduta seda ust, ja siis puuduta lihtsalt valikut viimase ukse.
DAVID J. Humala: Suurepärane.
Hästi.
Nii leidsime number 50.
Nii kiiresti sa teadsid nad on sorteeritud, me
suutsid võimendada see eeldus.
Nii nad on liiga palju nagu telefoniraamatust näiteks.
Niipea, kui teil on, isegi väike probleem selline,
Sinu sisendite eelnevalt sorteeritud, saame tegelikult leida väärtus vaieldamatult
efektiivsemalt.
>> Ja ma ei saa öelda, kas see oli järjestatud väike suur või suur, et väike,
ja nii see oli väga mõistlik alustada ühes otsas või teine
tegelikult leiavad, et sihtväärtust.
Nii tänada, et Trevor samuti.
Ja ma propose-- ilusti tehtud.
Meil on väike klipp, tegelikult, et on üks meie lemmik hetki CS50,
kusjuures mõnikord need demod ei ole päris kavakohaselt minema.
Ja tõepoolest just nüüd, ma tõmmata vale liidesega
kellega kasutada puuteekraani.
Nii et oli minu viga seal.
>> Nii see teha Järgmise aasta klambrit
miks ma klikkides oma ekraanil.
Aga olgem võtta Kiire pilk mis juhtus eelmisel aastal
Jay, kes tulid, palju nagu Trevor siin vabatahtlikult,
ja selle lühikese klipi, näete kuidas see sama demo ei ole päris
näitavad sama õppetunnid.
[Video taasesitus]
-Kõik Ma tahan, et sa nüüd on leida mind, ja meie jaoks,
tõesti, number 50 üks samm korraga.
>> -The Number 50?
>> -The Number 50.
Ja saate paljastada, mis on taga kõik need uksed
lihtsalt puudutades sõrmega.
Pagan võtaks.
>> [Naerab]
>> [Taasesituse lõpetamiseks]
DAVID J. Humala: Nii et läks väga hästi.
Need olid sorteerimata uksed.
Ja Jay, muidugi, leidis, et see kõik liiga kiiresti.
Trevor tegi palju paremat tööd nii õpetusliku hetk,
niiöelda, sel aastal võttes enam leida.
Muidugi, siis andsime Jay teist võimalust,
kusjuures me järjestatud uksed, niisama tegime Trevor,
ja Trevor tegi super hästi seekord.
Aga Jay tegi seda poole nii kiiresti.
[Video taasesitus]
-The Eesmärk nüüd on ka meid leida number 50,
kuid seda algoritmiliselt ja ütle meile, kuidas sa tahad seda.
>> -OKEI.
>> -Ja Kui leiate, et teil hoida filmi.
Kui sa ei leia seda, siis anna seda tagasi.
>> -Mees.
>> Oh!
>> - [Kuuldamatu] OK.
Nii et ma lähen kontrollida otsad kõigepealt kindlaks teha, kas there's-- Oh.
>> [APPLAUSE]
>> [Taasesituse lõpetamiseks]
DAVID J. Humala: OK.
Nii sorteerimine uksed selgelt toob kaasa suurema tõhususe.
Ja nii kaks korda kiiremini on see, mida ma mõtlesin seal.
Ja nii Jay vedas mõlemal korral.
Ja ta sai ka õnnelik, et viimase aastal, ma tellisin mõned Blu-ray kettad
tegelikult välja anda.
Vabandust sel aastal oleme ei ole sama, Trevor.
Aga veel parem oli paar aastat tagasi.
Ja mõned teist ehk teavad seda mehe, Sean, kes siis, kui ta oli CS50,
vaidlustati täpne Sama probleem, kuigi SD,
kui saate kohe näha, juba järgmisel päeval.
Ja sa leiad, et mitte ainult ei Ta võtab pisut rohkem kui Jay,
veidi enam kui Trevor, see oli tegelikult see suurepärane võimalus
tegeleda peaaegu kõigile Rahvas a la Hind on õigus, julgustades
teda leida number olime otsib.
Olgem. võtta Kiire pilk.
>> [Video taasesitus]
>> -OKEI.
Nii et teie ülesanne siin, Sean, on järgmine.
Olen taga peidus need uksed arv seitse.
Aga peitunud mõned neist uksed samuti on ka teisi negatiivseid numbreid.
Ja teie eesmärk on mõelda Selle esirea numbrid
lihtsalt massiivi, või lihtsalt jada paberitükke
numbrite taga.
Ja teie eesmärk on ainult kasutades tippu massiivi siin, leida mulle number seitse.
Ja me siis läheb kritiseerida kuidas sa minema umbes teeb seda.
-Hästi.
-Leia meile number seitse, palun.
Ei.
Viis, 19, 13.
>> [Naerab]
>> See ei ole konksuga küsimus.
Üks.
>> [Naerab]
Sel hetkel, oma skoori ei ole väga hea, et sa võiksid samuti edasi.
Kolm.
>> [Naerab]
>> Mine edasi.
Ausalt, ma ei saa aidata, kuid ei tea, mida sa isegi mõelda, so--
>> [Naerab]
Ainult ülemises reas, nii sul kolm vasakule.
Nii leia mind seitse.
>> [Naerab]
17.
Seitse.
>> [APPLAUSE]
>> Hästi.
>> [Taasesituse lõpetamiseks]
>> DAVID J. Humala: et me saaksime vaadata neid kogu päeva pikkune.
Ja muidugi, mõned Tänavuse demos ehk
Nüüd lõpuks järgmise aasta video ka.
Vaatame nüüd tegelikult keskenduda algoritme
siin, ja vaata, kui me ei saa Nüüd hakkavad vormistama
kuidas me saame minna saan oma andmed sellesse riik, mis see on järjestatud,
nii et lõpuks saame tegelikult search efektiivsemalt.
Ja kuigi me ei kavatse kasutada üsna väike andmekogumid
nagu kaheksa numbrit me on siin laual,
lõpuks need samad ideed, mida kohaldatakse 1000 sisendid, miljon sisendid,
4 miljardit sisendid, sest algoritmid saab olema põhiolemuselt sama.
>> Ja nii see on meie viimane võimaluse vabatahtlikele täna
aga võib-olla kõige kaasatud üks, mille eest me peame kaheksa vabatahtlikud
tulla ja kõndida meid läbi Protsessi sorteerimine mida varsti
olla nende muusika seisab siin.
Lubage mul alustada siia tagasi.
>> Nii et üks on turquoise-- roheline on?
Kas olete toime?
Kaks.
Tule alla.
OKEI.
Kolm.
Neli.
Lubage mind-- OK, viis.
Sa oled nimetab oma sõbraks.
Kuus, seitse, kaheksa.
Tule üles.
Hästi.
Suur tänu.
Tule üles.
>> Hästi.
Mis meil siin-- ja selle on üks ebamugav need,
kuna see nõuab, et sa huumor mind natuke aega.
Sa peab olema number üks.
Mis su nimi on?
>> ANNAN: Annan.
>> DAVID J. Humala: Annan.
David.
Mis su nimi on?
>> JOSEPH: Joseph.
>> DAVID J. Humala: Joseph, sa oled number kaks.
>> SERENA: Serena, number kolm.
Stefan, number neli.
CYNTHIA: Cynthia.
DAVID J. Humala: Cynthia, number viis.
[Kuuldamatu]
DAVID J. Humala: [kuuldamatu].
David, number kuus.
MATT: Matt.
DAVID J. Humala: Matt number seitse.
Ja?
>> WAVERLY: Waverly.
>> DAVID J. Humala: Waverly, number kaheksa.
Hästi.
Kui te could-- whoops.
Kui te kõik, sest teie Esimene väljakutse, seal
Kaheksa muusika seisu siin ees publik.
Kui sa võiksid panna oma numbrid Nende muusika seisu nii
et nad rivistama koos samad numbrid laual.
Nii et ise nägema, et pannes oma numbrid nende muusika
seisab siin.
Suurepärane siiani.
>> Suurepärane.
OKEI.
Nüüd, me ei kavatse küsida Küsimus on mitu erinevat võimalust.
Kuidas me saame minna sorteerimine need inimesed siin?
Kuna meil oli paar lähenemisviise varem, kusjuures me olime
Selline tegemist kahe erineva ämbrid.
Ja siis me üldiselt lõikuva asju koos.
Niipea kui nägime kaks numbrit mis kuulus kokku
paneme need kokku.
Kaks tähte, mis kuuluvad kokku.
>> Aga vaatame, kui me ei saa ametlikult selle,
nii et me lõpuks on mõned pseudo-koodi sisestamist,
millega saab neid probleeme lahendada.
Nüüd, ma otsin välja neid numbreid siin.
Ja ma näen terve hulk vigu.
Lõpuks, ma tahan ühte kohta vasakule ja kaheksa paremal.
>> Ja nii ma vaatan Nende kahe, nelja ja kaks.
Ja milles probleem, ilmselt?
Jah.
So.
Kaks ilmselt tuleb enne neli, nii et sa tead, mida?
Lubage mul kõigepealt ahne lähenemist, kui sa meelega probleem
määrata one-- kui te mäletate alates Standard Edition Ülesanded Üks,
kus ma lihtsalt kohapeal lahendada probleemi mis on siin minu ees
ja vaata kuhu see viib mind.
>> OKEI.
Nii kaks ja neli, lase mul minna käia ja lihtsalt vahetada teie kaks.
Kui te ei füüsiliselt liigutada ise ja oma paberi,
Mulle tundub, et oleme saanud nimekirja paremas olukorras.
>> Nüüd nad on head.
Ma lähen edasi liikuda, neli ja kuus, näeb hea välja.
Pole probleemi.
Kuus ja kaheksa OK.
Kaheksa ja üks, teine ​​probleem.
Sest see, mis on tõsi umbes kaheksa ja üks?
Üks on enne kaheksa, ja mis siis peaksime tegema?
Olgem vahetada need kaks.
Üks ja kaheksa.
Ja nüüd, ma lähen edasi.
Ma lähen hoida eel.
Ja vaatame, mis juhtub.
Kaheksa ja kolm, on Muidugi, rikkis.
Olgem swap.
Kaheksa ja seitse muidugi.
Korrast ära.
Olgem swap.
Kaheksa ja viis, muidugi, olgem swap.
Hästi.
Nimekiri on sorteeritud.
jah?
>> OK, ilmselt mitte.
Aga see on natuke parem, eks?
Sest teate, mis juhtus.
Iga kord, kui me läbi swap, väiksem number selline kurnatud, et viis,
ja suurem number percolated sel viisil, või me tulen
alustada öeldes mullidena kuni vasakule või mullidena paremale.
>> Nüüd, see ei ole piisav, sest parimal number võiks
liikunud ühest kohast edasi, või halvimal juhul
number võib olla kolis ühe koha peal edasi.
Nii et sa tead, mida seda laadi ning töötas päris hästi siiani.
Lubage mul lihtsalt proovida seda uuesti.
Kaks ja neli, on nad OK.
Neli ja pool on nad OK.
Kuus ja üks, rikkis.
Nii saab vahetada teie kaks.
Ja nüüd, märka probleemi on hakanud natuke parem uuesti.
Kuus ja kolm, rikkis.
Olgem vahetada teie kaks.
Kuus ja seitse, sa oled hea.
Seitse ja viis muidugi rikkis.
Seitse ja kaheksa korda.
Ja nüüd, ma võib olla vaja Selleks paar korda.
Ja tegelikult arvan endile ehk mitu korda maksimaalselt
võiks mul käia edasi-tagasi?
>> Me tuleme tagasi selle.
Nii kaks ja neli on ikka OK.
Neli ja üks, nope.
Niisiis, oletame, swap.
Ja jälle märgata visuaalselt üks on selline kihisevat
vasakule, kus see peaks olema.
Neli ja kolm swap.
Neli kuni kuus.
Kuus ja viis swap.
Kuus ja seitse.
Seitse ja kaheksa on hea.
>> Väga hea.
Saame isegi parem.
Vaatame.
Nüüd on meil kaks ja üks.
Muidugi vahetada.
Teist ja kolmandat kolme ja nelja, nelja ja viis, kuus ja seitse, seitse ja kaheksa.
Väga hea.
Ja tead mis?
Sest ma tegin ühe muutus seal, lubage mul teha üks meelerahu kontrolli.
Lubage mul minna kogu tee tagasi algusesse.
OKEI.
Üks, two-- yup, näed?
Midagi oli valesti.
Kolm, neli, viis, kuus, seitse, kaheksa.
Ja see viimane pass, on sa rahul minu nüüd
väites, et see on järjestatud?
OKEI.
Visuaalselt, see on tõsi.
Aga funktsionaalselt, mida ei ka lihtsalt juhtub
et viimase pass, mis võimaldab teil kinnitada, et see nimekiri on tõepoolest
järjestatud?
>> Mida ma tegin või ei tee seda viimase pass?
Sihtrühm: muutusi ei toimunud.
DAVID J. Humala: Vabandust?
Sihtrühm: No muudatusi.
DAVID J. Humala: muutusi ei toimunud.
Seega oleks rumal minust teha sama algoritmi uuesti
kui ma ei tee muudab esmakordselt.
Ja riik ei ole muutunud.
Kindlasti ma ei kavatse teha Kõik muudatused teist korda.
Ja nii, et see on ohutu nüüd öelda, nimekirja sorteeritakse.
>> Ja tõepoolest, see on nüüd midagi, mida me tulen üldiselt
kõne mull sorteerida, millega paarikaupa, sa parandada vigu korrata,
ja uuesti ja uuesti, ja sa hoida läheb edasi ja tagasi,
ja edasi-tagasi, kuni olete ei tee selliseid vahetustehingud, misjärel
võite olla kindlad, jah, ma lõpetanud, millega kõik vigu.
Olgem nullida ja proovida teistsugust lähenemist.
Kui te poisid võiks minna tagasi järjekorras sa olid hetk tagasi,
mis nägi välja selline.
Nüüd saab võtta lähenemise alusel veidi nagu eksam raamat,
kusjuures me olime pidevalt Valides täht
et me mingi tahtsime tegelema järgmisel.
Võib-olla oli see suur kiri, nagu A, või väike täht Z.
>> Nii et igaüks on tagasi selles järjekorras.
Ja nüüd lubage mul seda teha.
Vaatame, ma tean, et ma ei Kaheksa numbrid siin.
Ma lähen edasi minna ja lihtsalt teadlikult valida
väikseim elemente.
Õigus?
See tundub intuitiivselt liiga.
Miks ma ei leia väikseim element, pane see, kui ta kuulub,
siis saan järgmisel väikseim element, panna see, kuhu see kuulub, ja lihtsalt korrata.
>> Kuna intuitiivselt, mis peaks toimima ka.
Nii neli, mis on üsna väike number.
Ma mäletan, kui see on.
Oota hetk.
Kaks on väiksemad.
Lubage mul nüüd meeles pidada, kus kaks on, ja unustada neli.
Me tegeleme sellega hiljem.
Kuus, ma ei ole huvitatud.
Kaheksa, ma ei ole huvitatud.
Üks on minu uus väike number.
Nii et ma lähen mäleta, kus üks on.
Kolm, ei huvita.
Seitse, ei huvita.
Viis, ei huvita.
>> Nii ilma allakukkumist laval sel aastal
Ma lähen haarata number one-- ja mis oli su nimi oligi?
>> ANNAN: Annan.
>> DAVID J. Humala: Annan.
Ja kui sa võiksid ühineda minuga Alguses nimekirja,
paneme sind, kuhu sa kuulud.
Unfortunately-- mis su nimi on?
>> STEFAN: Stefan.
>> DAVID J. Humala: Stefan on viis.
Nii et enne Stefan lahendab selle Probleem, mida me peaksime tegema?
Mida me teeme Stefan?
>> Sihtrühm: [kuuldamatu].
DAVID J. Humala: OK.
Nii et me võiks seda teha.
Võiksime omamoodi võtta Stefan ja tema neli, ja lihtsalt panna see muutujale
ja hoidke seda Mõnes aega,
muutes ruumi number üks.
Ja see pole halb.
Ma võiks oletada, miks mitte me lihtsalt panna Stefan siin?
Miks võib see rikkuda üks ideid alustasime
räägime viimasel ajal eelmisel nädalal?
Jah?
>> Sihtrühm: [kuuldamatu].
>> DAVID J. Humala: Ei ole indeks ta.
Kui te arvate sellest, tõepoolest, kui massiiv, see on nagu negatiivne,
seega ei ole mälu tegelikult siin, kui see on tõepoolest massiivi,
nagu me kuulutas eelmisel nädalal loengu.
Nii et me ei peaks seda tegema.
Me võime salvestada see muutujale.
>> Või sa tead, mida?
Kuulsin kellegi soovitan seda.
Mida võiks veel teha Stefan?
Miks me lihtsalt ei tõstma teda ja pani ta selle üle, kus number üks oli.
Nii et kui sa tahad minna sinna.
Ja tõepoolest, see on päris hea lahendus.
Nüüd ühelt poolt, ma olen lahke on teinud probleemi hullemaks.
Neli on nüüd kaugemal kust see peaks olema.
Peaks olema poole käesoleva poole.
>> Aga tead mis?
See oleks võinud olla halb õnn.
Võib-olla number kaheksa oli siin.
Ja nii, võibolla oleksime saanud õnnelik,
ning lükatakse kaheksa lõpule lähemale.
Nii et lõpuks päev, see omamoodi kõik tasakaalustub.
Me ei pea hooli neli.
Kõik hoolin just nüüd on valides väikseim element.
>> Ja nüüd, mida ma lähen teha, on unustada number üks
püsivalt, sest ma tean nimekirja minu taga on nüüd järjestatud.
Nii et minu nimekirjas oli varem suurus kaheksa.
Nüüd on nende suurusest seitse.
Nii et minu probleem muutub väiksem, ehkki lineaarselt.
Nüüd ma lähen valima Praeguse väikseim element, kaks.
Kuus, kaheksa, nelja, kolme, seitsme, viie.
See oli väikseim element.
Mida ma nüüd tegema with-- Mis oli su nimi oligi?
>> JOSEPH: Joseph.
>> DAVID J. Humala: Joseph?
Me läheme lahkuda Joseph paigas.
Nüüd ma lähen teeselda et need kutid are-- hästi,
Ma tean, et need kaks on juba järjestatud.
Olgem nüüd keskenduda Ülejäänud nimekirjas.
Kuus on praegune väikseim.
Kaheksa on suurem.
Neli on nüüd praeguse väikseim.
Kolm on nüüd praeguse väikseim.
Ja nii nüüd ma lähen valima kolm, kes on-- mis su nimi oligi?
SERENA: Serena.
DAVID J. Humala: Serena, kui sa saaksid Haara number ja swap with--
KALSANG: Kalsang.
DAVID J. Humala: Kalsang.
Tule tagasi, ja me oleme läheb vahetada need kaks.
Ja nüüd, paneme selle autopiloot.
Ma lähen ja jätan teiega et valida järgmine väikseim elemente.
Dun Dun Dun Dun.
Number neli, mida teha?
Suurepärane.
Nüüd ma lähen tegema teise pass.
Dun Dun Dun Dun.
Näen viis on järgmine kahanevas järjekorras.
Nüüd ma lähen võtma teise pass.
Dun Dun Dun Dun.
Kuus on väikseim.
Väga hea.
Seitse on väikseim.
Ei muutu.
Kaheksa on väikseim.
Valmis.
>> Nii et me oleme lihtsalt teha korduvalt valides ühe elemendi teise järel
on ellu midagi, mis me oleme läheb vormistama kui valikut omamoodi.
Ja see on võib-olla isegi lihtsam selgitada,
et sõna otseses mõttes kõik, mida tahan teha, on lihtsalt hoida
läheb edasi ja tagasi läbi nimekirja valides, suuruselt järgmine kahanevas element,
kuni sa oled teinud.
>> Nii et see on isegi lihtsam, võib-olla intuitiivselt, kui eelmisel.
Proovime üks viimane.
Kui te poisid võiksid nullida ise arvesse järgmisi positsioone
lõplikult maha, vaatame, kui me ei saa nüüd vormistama üks teine ​​lähenemine.
Tegelikult peaks keegi seal suggest
kuidas muidu me võiksime minna seda teed?
Ilma visklemine välja buzzwords või järjesta vastuseid, mis on juba teada,
lihtsalt intuitiivselt, mida saaksime teha?
>> Sihtrühm: [kuuldamatu].
DAVID J. Humala: Jah.
Nii et mõned suured intuitsiooni seal.
Head asjad tunduvad juhtuda seni infotehnoloogia, kui me jagame
ja vallutada probleemi jagades see pooleks ja pool ja pool.
Ja nii tõesti, me võiks alustada seda teha.
Ja tegelikult, et see saab olema, siis me vaata, üks meie parimaid lahendusi veel.
Aga tulgem tagasi, et enne pikk.
Tegelikult me ​​teeme et veidi hiljem sel nädalal.
Mida võiks me lahendada seda?
Nii et igaüks siin on näiliselt juhuslikus järjekorras.
Tead mida?
Selle asemel, et minna edasi ja tagasi, edasi ja tagasi, edasi ja tagasi
Iga kord, see tunne Ma teen palju jalgsi.
Miks ma just ei alusta Alguses nimekirja,
ja lihtsalt panna neli kuhu ta kuulub?
Nii et lubage mul oletame hetkeks, et minu nimekiri on ainult see esimene element.
Kas neli järjestatud sel ajahetkel, kui ma hoolin on siin kõik?
See on omamoodi triviaalne, eks?
Nagu nimekirjast, mis sisaldab ühe numbri ja et number neli on ilmselt järjestatud.
>> Lubage mul ette näha selle nimekirja sorteerida.
Aga nüüd on mul ülejäänud seda nimekirja.
Nüüd, ma kogevad kaks.
Kust kaks ilmselt kuuluvad seoses nelja?
Enne neli.
Mida ma saan teha siin?
Mis su nimi oligi?
>> JOSEPH: Joseph.
>> DAVID J. Humala: Joseph, kui sa saaksid sammu tagasi
hetkeks oma number.
Ja nüüd, milline peaks Stefan teha siin?
Lähme minema Stefan siin.
Ja nüüd, lase Joseph siia tulla.
Ja nüüd, las ma väita, et kõik siin on järjestatud.
Niisiis, sarnase tulemuse, kuid fundamentaalselt erinevat lähenemist.
Ma pole isegi vaadanud, mis on seal.
Ma muudkui võttes elemendid kui nad kätte mulle,
ja nendega toime tulla.
>> Nüüd näen number kuus.
Kuhu see number kuus kuuluvad?
Meil on kaks, neli, kuus.
Täpselt, kus ta on praegu.
Nii saab jätta, et üksi, ja nüüd väidavad, et see osa loetelu
Nüüd on järjestatud.
Ja nii see tundub täiesti erinevad, et ma olen lihtsalt
liigub läbi nimekirja siin lineaarselt, ja ma ei ole kunagi kahekordistada tagasi.
Jah.
Hästi.
Nii kaheksa, kus Te kuulute?
Siin samas.
Perfect.
Nüüd, üks.
Uh-oh.
See kõik tundub nii saab olema kallis.
Nüüd eelmisel algoritmi, Ma vahetasin inimesi.
Nii et ma võiks panna teda kogu tee juures alguses, kuid siis kolis Joseph.
Aga kui ma liigun Joseph, nüüd Mis saab olema vale?
>> Nüüd ma olen omamoodi undone-- Olen võtta üks samm edasi ja siis
üks samm tagasi, sest nüüd Joseph oleks rikkis.
Nii teeme seda.
Kui sa saaksid võtta number üks ja tagasi astuda hetkeks.
Kuidas me saame put-- mida oli su nimi oligi?
>> ANNAN: Annan.
>> DAVID J. Humala: Annan olemas?
Mida peab toimuma suhtes kahele, neli, kuus, kaheksa?
Nad kõik peavad minema.
Nii et kui kaheksa tahaks minna Esimene, siis kuus, siis neli, siis kaks.
Ja siis Annan, kui soovite tahaks siia tulla, hea.
Aga siin, me oleme lihtsalt Selline makstud hind
erinevas punktis algoritmi.
Kui eelmisel aja valikut sorteerida ja isegi mull sorteerida,
Ma kõnnin ja tagasi edasi, edasi ja tagasi,
mis on kindlasti liitmist ajalist ja sõna otseses mõttes sammhaaval.
>> Insertion sorti, esimesel lühidalt, näeb välja nagu see on
super targemaks, et ma olen lihtsalt muutes aeglaselt ja järk-järgult edusamme,
aga ma ei hakka seda edasi ja tagasi.
Aga kui keegi on tõepoolest rikkis, teate
kõik tööd ma lihtsalt pidin tegema.
Mul oli liikuda pool nimekirja lihtsalt, et teha ruumi number üks.
Nii et see on sama palju töö siiani seda
tunneb, vaid teistsugust tööd tegema.
>> Jätkame.
Nüüd me teame, et kõik üks kuni kaheksa on järjestatud.
Siin on mul number kolm.
Kui soovite kiirenemist number kolm, samm tagasi üks.
Ja mis te poisid peavad tegema?
Yep.
Nii et on veel üks, kaks, kolm sammu.
Kolm ajaühikutes, et lihtsalt maksma mulle, et kolme saab nüüd sobi.
Lõpuks seitse.
>> Lähme edasi ja on sa astuda samm tagasi.
See on ainult kavatse meile maksma ühe ajaühiku, kuid see on OK.
Ja nüüd, viis läheb olla natuke kallim.
Kui soovite sammu tagasi.
Me peame liikuma kaheksa, seitse ja kuus.
Ja siis kõik on nüüd järjestatud.
Nii suur käsi meie vabatahtlike siin.
Suur tänu.
>> [APPLAUSE]
>> Tänan teid kõiki.
Tänan teid kõiki.
Vaatame nüüd, kuidas kulukad kõik see oli.
Vaatleme ehk Lihtsaim neist, mull omamoodi.
Ja ma ütlen lihtsam, ainult sellepärast, saab seda lahendada aplalt lihtsalt
määrata paarikaupa probleem.
Kinnitage paarikaupa probleem siin, ikka ja jälle
ja jälle, korrates nii palju korda, kui tegelikult vaja.
>> Nii selgub, et koos mull sorteerida, noh,
kui palju samme pean võtma esimene pass selle algoritmi?
Ma võiks Vőta olgem see-- üks, kaks, kolm, neli, viis, kuus, seitse.
Ja seal on kaheksa elemente siin.
Nii et see on nagu n miinus 1 samme saada algusest nimekiri
lõpuni nimekirja.
>> Kuid valikut omamoodi, meelde tuletada, et ma olen valides elemendid ja jälle
ja jälle, et on väikseim, Ma panen oma kohale,
aga siis ma ei ole otsin minu taga uuesti.
Nii et ma arvan, et see on natuke selgem siis esimest korda, ma võin
võtma kõik n miinus 1 etappe leida kõige väikseim element.
Siis panin need paika, ja ma tõstma kes oli siin varem.
>> Aga siis ma ei pea hoida vaadates seda element,
sest ma tean, et see juba väikseim.
Nüüd, ma ei saa vaadata ainult seitse elemente, siis kuus elementi,
Seejärel viis tegurit, siis nelja elementi.
Ja nii matemaatiliselt, kui n on elementide arv või numbrid
et alustasime, võite ette kujutada et see on sama nagu n miinus 1,
pluss n miinus 2 sammu, pluss n miinus 3 astet,
plus n miinus 4 samme, kõik tee alla vaid üks samm.
Ja ma olen minu viimane inimene.
>> Ja kui te mäletate, et palju stats raamatuid või matemaatika raamatud
on need valemid kõvakaaneline tagasi või nende ees,
Selgub, et selles seerias saab väljendada lihtsamalt
kui n korda n miinus 1 jagatud 2.
Ja see on hea, kui see ei ole esirinnas meelt.
Aga see on tõsi.
See on lihtsalt lihtsam viis kirjutamist.
Ja siis, kui te arvate, tagasi algkool,
kui sa lihtsalt alustada korrutades asju teha, seda muidugi
on lihtsalt n ruudus miinus n jagatud 2.
Kõik, mida ma olen teinud on laiendada väljendid seal.
Ja nii kirjutame selle uuesti natuke teistmoodi.
See on n ruudus jagatud 2 miinus n / 2.
>> Nii jälle, ma olen lihtsalt selline kohaldamisel mõned aritmeetika reeglitega.
Aga teate nüüd, et suurim perspektiivis Selles väljendus, kui nii võib öelda,
on see, et n ruudus.
Nii et jah, see on n ruudus jagatuna 2 miinus n / 2.
>> Aga üldiselt, kui n on saab olema suur väärtus,
Ma lähen väidavad, et n ruudus saab olema domineeriv tegur.
See on lihtsalt saab olema suurem toetaja
to sammude arvu kui n / 2.
Mida ma öelda?
Proovime lihtne näide, isegi kuigi matemaatikat saab natuke suur.
>> Nii Oletame, et meil oli 1 miljon inimest laval, või 1 miljon asja
et me soovime sortida.
Olgem plug miljonit arvesse just seda valemit
näha, kuidas paljud sammud kulub kokku sorteeri miljoni elemente kasutades näiteks
valikut omamoodi.
>> Nii et me tahaks olla sama valemit nagu enne.
Ma ühendan miljonit, nii et ma saan miljon ruudus jagatud 2,
miinus miljon jagatuna 2.
Kui ma seda teen matemaatikat ette siin on meil 500 miljardit
miinus 500.000, mis annab meile 499999500000,
mis on päris darn suur.
>> Tegelikult, kui sa võrdled nüüd 499000000000 999 miljonit
500,000 vastu meie esialgsest väärtusest, 500 miljardit, see on nii kuradi tihe.
Õigus? n ruudus jagatud 2 annab us-- või pigem n ruudus jagatud 2
andis meile 500 miljardit.
See on päris darn lähedal to 499999500000,
mis tähendab, lahutades maha 500.000, või üldisemalt lahutades off
n ruudus, ei ole tõesti suur asi.
N ruudus muudab need numbrid kasvavad väga kiiresti.
>> Nüüd, see on oluline vaid niivõrd, nagu meie, arvuti teadlased,
üldiselt ei kavatse hooli nii palju umbes nüansse need valemid
ja täpselt täpne vastused on.
Me hoolime ainult, et sa tead, mida?
Lõpus päeval, see valem on järjekorras n ruudus.
>> Jah, me jagame 2 seal.
Jah, me lahutades maha n miinus 2.
Aga lõpus päeval, termin et on tõesti valus juures ja maksab meil
palju samme, et ruudu mõiste.
Ja mis siis arvuti teadlane läheb tavaliselt teha
on ignoreerida kõiki neid väiksem järku,
ja lihtsalt vaadata mis aitab kõige kuludega.
>> Ja see on tore, sest me suudame nüüd rääkida palju suurem üldisus
umbes algoritmide ja võib neid võrrelda.
Ja see, et ma olen kasutades seda O on tahtlik.
Kui ma ütlen tellimusel ja ma olen just
viidates midagi Big O. Ja suur O
on märge, et arvuti teadlane kasutab kirjeldada
ülemine piir midagi.
>> Nii et kui sa ütled, et algoritm on suur O n ruudus
nagu ma pakutud vaid Hetk tagasi, et vahendid
mis mõttes oma jooksvaid aega või oma tõhusust,
kulub tellimusel n ruudus samme.
Võib-olla rohkem, võibolla vähem.
Aga see, mis järjekorras n ruudus.
Ja see on ülemise.
Ta ei kavatse olla valusam kui see.
Ta ei kavatse olla n kuubis, või 2 astmes n, või midagi palju suurem.
See on ülemine piir mida iganes, et kulu on.
Nii sest olgem kaaluda vaid mõned näited.
Ja see on vaid piiratud nimekirja väga sage töötab korda
algoritmi, mis on mõeldud illustreerivad mõningaid asju me oleme
näinud juba.
>> Nii näiteks juhul, valikut sorteerida, mida ma väidan siin
on see, et valikut omamoodi jooksvate aeg on järjekorras n ruudus.
Halvimal juhul, ma lähen terve hulk juhuslikke numbreid siin.
Ja nagu me nägime matemaatiliselt, kui ma saan jalgsi
loendis kaudu nimekirja, valides järgmiseks väikseim
element uuesti ja uuesti, kui ma tegelikult kirjutada kõik sammud
Ma viin nagu ma ettepaneku formulaically enne, see on suurusjärgus n ruudus
samme, et ma olen võttes.
>> Ja selgub, et mull sorteerida ning sisestamise omamoodi
on lihtsalt nii aeglane halvimal juhul.
Võtame näiteks sisestamise sorteerida, väga viimane algoritm käsil,
mis oli meil vaadata element, ja paigaldage siis, kui ta kuulub.
Ja siis me vaatasime järgmise elemendi, ja lisada see, kuhu see kuulub.
>> Nii leiavad parima stsenaariumi.
Oletame, mul oli mu vabatahtlike rivistama sõna otseses mõttes nagu see üks läbi kaheksa,
juba järjestatud.
Mitu sammu on sisestamise omamoodi kavatseme sorteerida kaheksa inimest,
kui nad jõuavad lavale niimoodi välja?
>> Kaheksa inimest on juba järjestatud.
Ja ma kasutan sisestamise omamoodi.
See viimane algoritme.
Noh, olgem taaskehtestada päris kiiresti.
Nii et kui ma hakkan siin, ma näen ühte.
Kuhu see üks kuulub?
See kuulub siin.
Näen kahte.
Kust kaks kuulute?
Siin samas.
Ma näen kolme.
Kust kolm kuuluvad?
Siin samas.
>> Ma näen nelja.
Siin samas.
Viis, kuus, seitse, kaheksa.
Ei ole mingit põhjust ennast kordama.
Ja nii mitu sammu on see, et nii n?
See tellimusel n samme, eks? n miinus 1.
Aga ma võtsin lineaarne number samme, ja nüüd ma olen teinud.
Nii et parimal juhul küll.
Aga halval juhul?
Mis kaheksa olid seal, ja seitse olid seal,
ja üks ja kaks olid siin, nii et nimekiri oli tõesti vastupidine?
>> Noh, mis juhtub tõepoolest kas see on number?
Ja me teeme vaid paar näidet.
Mis siis, kui tõepoolest arv kaheksa on siin, ja number-- whoops.
Mis siis, kui tõepoolest arv Kaheksa on kõik teed siin,
ja ma kasutan sisestamise omamoodi?
>> OKEI.
Väidan hetkel on olemas.
Aga nüüd, seven-- kus ei seitse minna?
Muidugi, see läheb siia.
Nii et ma pean liikuma kaheksa üle ühest kohast.
Nüüd kuus, kus see läheb?
Noh, eks.
Nüüd ma pean liikuma kaheksa üle koht, ja seitse üle koht,
ja siis ma sulpsti maha kuus.
>> Nii esmakordselt seda kulu mul üks samm fikseerida asju,
siis see maksab mulle kaks sammu asju parandada.
Mitu sammu on ta aega võtab, et määrata
asju panna viis õiges kohas?
Kolm.
Sest nüüd ma pean liikuda üks, kaks, kolm.
Mitu sammu on see aega võtab panna neli õiges kohas?
4 pluss 5, pluss 6, pluss 7.
>> Ja nii see on matemaatiliselt identne mida me kirjeldatud valikut omamoodi.
Meil on selles sarjas See on lihtsalt suureneb.
1 pluss 2 pluss 3 pluss 4, või vastupidi, 7 plus 6
pluss 5 pluss 4 lisab kuni tänase eesmärgil tellimusel n ruudus.
>> Nii et lubage mul ette näha ka seda, et mull sorteerida on ka n ruudus.
Kuna mull sorteerida, iga kord, kui ma nimekiri läbi,
Ma võtan umbes kui palju samme?
Iga kord, kui ma sõna otseses mõttes sealt jalutada seal?
Umbes n samme.
Aga mitu korda võiks ma pead minema läbi nimekirja?
>> Noh, umbes n korda.
Võib-olla n miinus 1, kuid umbes n korda.
Noh, miks see nii on?
Noh, mull sorteerida, kui hakkame koos mull sorteerida,
loetelule halvim võimalik olukord, mis omakorda on täiesti
tagasi, mida juhtub?
Lähen läbi nimekirja ja number üks kuulub kogu tee sinna.
>> Kuid mull sorteerida, kui kaugele ei üks liikuda minu esimese läbida nimekirja?
Mitu laigud ei ta saada lähemale õige koht?
Ainult üks.
Nii et kui sa mingi põhjus selle kaudu, iga kord läbi selle algoritmi,
Davidi võttes umbes n samme.
Aga kui palju läbib loendis on see
aega võtab ühe mull vasakul kui ta kuulub?
>> Tal on liikuda nagu, n ruumid sel viisil.
Nii lihtsalt teha sorteerimise nimekirja, Mul on kõndida edasi-tagasi n korda.
Ja iga kord, ma olen vaadates n elementi.
Nii et ärge n asju n korda järjekorras n ruudus.
>> Nüüd me näeme mõnedes on lühikesed püksid, mis
on põimitud CS50 järgmise probleemi määrata, teine ​​lähenemine on need,
aga nüüd, lähme lihtsalt kaaluda mõned muud jooksvad korda
eriti kui sortimine ones võtta natuke aega imbuma.
Mis algoritmi oleme näinud juba mis võtab tellimusel n sammud?
>> Mida peaks lineaarne number samme, et me oleme näinud siiani?
Mis see on?
Telefoni kataloogi otsingu.
Esimene algoritm.
Õigus?
Kus me oleme lineaarselt otsivad Mike Smith?
Tõepoolest.
Nädalast null, kui hakkasin keerates ühe lehekülje korraga
ja ma isegi öelda, et see oli selline lineaarse tunnet algoritmi,
ja meil oli, et pilti papi otse punase joone
ja sirge kollane line, need olid tõepoolest
algoritme, mis on suurte O n.
>> Sest leida Mike Smith telefon raamat n lehti, halvimal juhul,
võiks mind n samme.
Aga võttes käimist?
Üks, kaks, kolm, neli, viis, kuus.
Mis on töötamise aeg selle algoritm võttes käimist?
Big O n, sest teoreetiliselt I on juhtida kõik ruumis.
>> Nüüd kui kõrvale, kuidas on lood teiste optimeerimine nädalast null?
Kaks, neli, kuus, kaheksa, 10, 12.
Arvuti teadlane oleks mõistma, oodake minut,
see tellimusel n jagatud kahte etappi.
Õigus?
Sest ma teen kaks inimest korraga.
Aga me ei kavatse ignoreerida need väiksemad mõttes,
ja me lihtsalt läheb visata jagage 2,
ja lihtsalt öelda, suur O n sel algoritmi samuti.
>> Aga see?
Me vahele üle mõned neist, kuid mida oli algoritmi, mis oli samamoodi n?
Mis võttis umbes samamoodi n sammud?
Lõhe ja vallutada.
Täpselt.
Nagu telefoniraamatust näiteks nädal null ja täna,
kus me jagada probleem uuesti ja uuesti ja uuesti.
Me juhtis ta laual nädal null kõvera roheline joon,
ja me ütlesime, et päev oli logaritmiline algoritm.
>> Ja tõepoolest, astmete arv on võtab täita jaga ja valitse,
või Kahendotsingupuu kui hakkame nimetades seda, kui telefoniraamatus,
on järjekorras log ja samme.
Ja see on natuke imelik ühe.
>> Mis teeb ühe sammu või täpsemalt
pidev mitmeid samme?
Võib-olla on kaks, äkki see on kolm, kuid arvuti teadlane lihtsalt
lihtsustab see nii suur O 1, mõned pidev mitmeid samme.
Mis on midagi, mida võiks teha, et võtab pidev mitmeid samme?
>> Mis on töötamise aeg plaksutamine?
Pidev aega.
Õigus?
Like, milline on töötamise aeg tee midagi, mis võtab vaid üks
laadsete printida F Hello World.
See võiks öelda, et pidev aega, kui ei ole vähem nurgas puhul print F,
Millised võivad sõiduaega prindi F tegelikult olla?
Ja miks?
Mis on n mõõtmist sellisel juhul?
>> Sihtrühm: [kuuldamatu].
DAVID J. Humala: Täpselt.
Märkide arv tahame trükkida.
Nii et see on väga kontekstitundlik.
Täna oleme olnud suunatud partii tähed ja numbrid siin laual.
Aga see võib olla ka tegelaste tegelik string.
Nii selgub ka teine meede, mis hakkab hooliv,
ja see on vastupidine suur O, nii rääkida.
>> See on omega märke.
Arvestades suur O tähendab, mis on, on ülemist piiri peal oma sõiduaega?
Maksimaalselt, kui palju aega võiks midagi teha?
Omega-- sorry see hoiab tulemas up-- on vastupidine,
kusjuures see on alumise piiri ajaga midagi võiks võtta.
>> So. Näiteks milline on algoritmi mis võtab alati n ruudus sammud?
Noh, üks algoritme oleme näinud Täna, tegelikult võib olla, et hästi.
Valik omamoodi.
Valik omamoodi päris loll.
Isegi kui algorithm-- kahju isegi Kui massiiv on juba sorteeritud,
valikut omamoodi läheb hoida jalgsi läbi nimekirja
veendumaks, et see on kõige väiksem element uuesti ja uuesti ja uuesti.
Ja kuigi sa inimesed on publik teab, et oodake minut,
sa juba möödas väikseim element, arvuti
ei tea, et enne, kui see näeb välja kõik teed läbi nimekirja.
Samuti alampiiri, mis Samuti võib arvesse võtta
võib olla lineaarne aeg.
>> Kui palju aega läheb aega, et Sorteeri n elementi parim
Juhul kasutades midagi mull omamoodi?
Oletame, et teie loend on juba järjestatud.
Me ütlesime mull omamoodi võtab järjekorras n ruudus samme.
Aga mis siis, kui see on juba järjestatud?
Mis siis, kui sa mõistad pärast üks läbida massiivi
mis sa oled teinud ühtegi vahetustehingud?
Kas teil on vaja hoida muutes möödub?
>> Ei.
Nii alampiiri mull omamoodi Võib öelda, et lineaarne.
Omega n.
Ja me võime vaadata teised neist samuti.
Võtame pilgu just visualiseerimine siin
näha, kuidas need eristuda.
Ma lähen siin sellesse leht, mis on saadaval C50 kodulehel
kuid see on valu, et saada tööd, kuna ta kasutab tehnoloogiat nimega
Javat, mis on suuresti toeta nendel päevadel,
vähemalt Chrome ja teatud teised.
>> Ja lubage mul minna ja kiirendada selle up ja seletada, mis toimub.
See on demonstratsioon mull Sorteeri esimene algoritm me vaatasime.
Ja see on visualiseerimine, et iga Nende baarid tähistab number.
Mida suurem on baar, mida suurem number.
Mida väiksem on baar, väiksem number.
Ja mida näed visuaalselt, isegi kuigi see läheb super kiire,
on see, et punane riba on nagu mina, jalgsi edasi-tagasi millega probleeme.
Näete, et suurem elemendid tõepoolest mullitava kuni paremalt
ja väiksematele elemendid on vahustamine kuni vasakule.
Ja siin, kui me tegelikult lähemalt,
me saame tegelikult loota võrdluste arv ja vahetustehingud
mis olid tehtud.
>> Kuid selle asemel, vaatame teisel algoritm
me vaatasime varem meie vabatahtlikud, valiku omamoodi.
Visuaalselt on tal väga erinev mõju.
Aga see on jällegi väga intuitiivne, in et me peame valides järgmise väikseim
element, ja me saime natuke õnne.
See tundus täiesti kiiremini.
Aga kui me jooksime seda uuesti ja uuesti ja jälle palju sisendeid,
me näeme, et see on tõepoolest ikka suur O n ruudus.
>> Teeme ühe Viimane Siin sisestamise sorteerida,
mis oli kolmas algoritmi me vaatasime, ja tagasikutsumine
et see üks tegeleb elemente kui tal tekib neile
kuid siis äkki vahetuses asjad üle, et teha ruumi,
sisestades elemente, kuhu nad kuuluvad.
>> Ja ka see jõuab andes lõpptulemust. Nüüd kõik kolm neist
tunda päris kiire.
Ja tõepoolest, ma jooksin neid kell päris hea klipp.
Aga põhimõtteliselt on nad kõik päris jube, kui aus olla.
Kõik need algoritmid seni mis töötavad suure O n ruudus
võtab üsna natuke aega joosta lõpus.
>> Ja tõepoolest, me näeme ja tundub, et see lõpuks
kui ma tõmba see kolmas ja viimane demo.
See on veel üks visualiseerimine, et läheb
näidata mull omamoodi vasakul, valikut omamoodi keskel,
ja midagi, kui üht meie Samas tekitab varem soovitanud,
ühendada sorteerida õige.
Jaga ja valitse strateegia paremal.
Ja see on tegelikult see, mida me oleme läheb vaadata kolmapäeval.
Aga olgem aega neid paralleelselt.
On ligikaudu sama arvu elemente, kõik töötavad samal ajal.
Bubble omamoodi vs valikut Sorteeri vs ühendamine omamoodi.
>> Nüüd on nad kõik töötavad teoreetiliselt samaaegselt.
Protsessor töötab sama kiirusega, kuid te
tunda, kuidas igav on väga kiiresti hakkab muutuma,
ja kuidas kiiresti kui me süstida natuke nädalas
null algoritmid saab me asju kiirendada.
>> Ja nüüd lähme võrrelda Nende ühe viimase kujul.
Ma lähen edasi minna et CS50 veebisaidil kus
meil on see viimane lüli täna, kus keegi internetis
sõbralikult kokku pandud video, mis lööb mida erinevad sorteerimine
algoritme tunduda.
See on sisestamise omamoodi.
>> [Piiksumine]
>> Millest sa rakendades sagedus põhineb tulba kõrgus baar.
See on mull omamoodi.
>> [WARPED piiksumine]
>> Järgmisena on-- tulevad kuni järgmise on-- valikut omamoodi,
kus jälle, me valides Järgmise väikseim element,
ja me näeme seda kasvavate vasakult paremale.
>> Merge omamoodi, meie võitja seni täna.
Pane tähele, kuidas see jagatakse asju arvesse [kuuldamatu] poole ja kvartalites.
Gnome omamoodi, mis meil ei ole rääkisime, ja loob visuaalselt
ja audally natuke erineva kuju ja heli.
Läheb edasi ja tagasi, puhastamise asju.
Tutvuge ka heapsort Selle mehe kodulehel.
>> Ja see ongi kõik.
Me näeme järgmine kord.
>> [Whooshing JA MUUSIKA]