[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. Sain su kätte. Oh. 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. 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]