[TÓNLIST spila] DAVID J. Malan: Þetta er CS50. Og þetta er upphaf viku þrjú. Þannig að við höfum fengið fullt af spennandi atriði sem þarf að ná í dag. A einhver fjöldi af tækifærum fyrir sjálfboðaliðar upp á sviðinu. Og að lokum, í dag er ekki um kóða yfirleitt. En það er um hugmyndir, og það er um reiknirit, og í raun koma aftur sum í kennslustundum lært af viku núll, þar muna, við kynna þessa monstrosity. Og lántökur innblástur frá því, til að byrja til að leysa sífellt flóknari vandamál algorithmically. En fyrst, a par af tilkynningum. Svo einn, ef þú vildi eins og til að taka þátt Starfsfólk CS50 og bekkjarfélagar í hádeginu á föstudaginn, bæði hér og í Cambridge, og í New Haven, skaltu fara á námskeið er website, þar sem URL er að finna. Fyrirlestur þessi miðvikudagur mun ekki vera hér í Sanders. Það verður að vera á netinu bara, svo lag í á vefsíðu CS50 er, hvort hér í Cambridge eða New Haven eins vel. Og þá vandamálið sett tvö er nú þegar í höndum þínum. Ef þú hefur ekki bætti enn leyfa mér að bjóða upp á mjög orðuð tillögu að, sérstaklega nú, eins og vandamálið setur fyrirfram, þú virkilega vilt að byrja núna, ef ekki notaði svolítið um helgina eða áður þegar þeir fara fyrst út á Fridays, vegna þess að þú munt finna að þeir eru ekki endilega fá lengri eða meira krefjandi fyrir SE. Ég held að þú munt komast að því að í Almennt, þeir hafa tilhneigingu til að taka u.þ.b. um sama tíma. En það fer örugglega á nemanda, og það veltur á hugarfari sem þú nálgast það. En ávallt, ætlar þú að fara að hlaupa upp á móti einhverju vegg, og þú ert að fara að lemja sumir galla, og þú ert bara ekki að fara að vera fær um að komast yfir það á einhverjum tímapunkti. Og það er gríðarlega mikils virði að vera fær um að stíga í burtu, koma aftur næsta dag, fara til skrifstofutíma birti á CS50 Ræddu eða þess háttar, til að raunverulega fá bannlista. Svo halda að í huga. Byrjar fyrsta og mögulegt er það besta sem þú getur gert. Svo er hér þar sem við byrjuðum bekknum, yfir í viku núll. Og getum við fengið sjálfboðaliða hér til að hjálpa mér að finna mics? OK. Standa upp nú þegar. Komdu upp. Giska á það er hvernig það er að fara að vinna. Hvað heitir þú? ALAN ESTRADA: Alan Estrada. DAVID J. Malan: Alan Estrada. Komdu upp. Gaman að hitta þig. ALAN ESTRADA: Gaman að hitta þig. DAVID J. Malan: Og þú værir hér með okkur í viku núll, að sjálfsögðu. ALAN ESTRADA: Ég var. Ég var. DAVID J. Malan: Svo væri hægt að fara á undan og finna fyrir okkur Mike Smith, eins hratt og þú getur? Eins hratt og þú getur. Bókstaflega rífa vandamálið í tvennt eins og þú þarft að. ALAN ESTRADA: Um. DAVID J. Malan: Bókstaflega rífa vandamál í tvennt. ALAN ESTRADA: Oh. Mm. Mjög gott. DAVID J. Malan: OK. Good. Þakka þér fyrir. ALAN ESTRADA: Mjög gott. OK. DAVID J. Malan: Og svo nú, þú hefur tálga það niður að helmingur the stærð af the vandamál. Nú erum við niður í fjórðung. Ert þú að borga eftirtekt til hvaða hlið við erum að halda? [Hlæjandi] ALAN ESTRADA: Já, think-- I DAVID J. Malan: Hvað kafla erum við í? ALAN ESTRADA: treflar, svo. DAVID J. Malan: OK. En Mike Smith er að fara að vera eftir Mufflers. So-- [Hlæjandi] Allt í lagi. ALAN ESTRADA: Hvar erum við að leita? DAVID J. Malan: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. Malan: Nú erum við í skurðaðgerð. Nú, læknar. Now-- ALAN ESTRADA: Let's- skulum fara með alvöru. Real. DAVID J. Malan: Real. OK. Ef þú þarft alvöru. Nú, hvaða leið er Mike Smith? ALAN ESTRADA: Þessa leið. DAVID J. Malan: Hvaða leið? ALAN ESTRADA: Bíddu. M is-- satt? Við byrjuðum with-- DAVID J. Malan: Já. Þeir eru eftir. Rétt þinn. ALAN ESTRADA: Já. DAVID J. Malan: Svo Mike er hér. ALAN ESTRADA: Hvað? [Hlæjandi] Bad dæmi, krakkar. Sorry. DAVID J. Malan: Þetta mun kenna þú þarft að stökkva út úr stólnum. ALAN ESTRADA: Oh. Oh. Ég fékk þig. Ég fékk þig. Oh. Oh. Þetta is-- OK, fékk ég þig. Smith hérna? DAVID J. Malan: Smith, þakka þér. Svo ég ætla að halda áfram að leita upp Smith? ALAN ESTRADA: Ó, já. Nei, nei, nei. Ó nei. Þetta er mitt. DAVID J. Malan: Oh, fékk Smith þú. OK. ALAN ESTRADA: Já, ég fékk Smith hérna. Því miður, krakkar. Ég hélt Michael-- við voru að leita að Michael. Sorry. DAVID J. Malan: Það er allt í lagi. Allt í lagi, nú erum við í Paccini og sona. ALAN ESTRADA: Paccini og synir. DAVID J. Malan: Aðeins þú og ég erum í á þessu. OK. Finna okkur Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. Malan: Smith. Við erum í R fyrir rusl. ALAN ESTRADA: Slæm. Oh. Þetta er að fara að taka smá stund. [Hlæjandi] DAVID J. Malan: Skór. Við erum í skóm. ALAN ESTRADA: Nú erum við gonna-- DAVID J. Malan: Nice. ALAN ESTRADA: Which-- [Hlæjandi] Oh, þetta er frábært. [Hlæjandi] DAVID J. Malan: Það er allt í lagi. ALAN ESTRADA: Oh, þetta er gott. Ég held ekki að ég ætla að hafa PSAT verðandi eftir þetta. DAVID J. Malan: Good. Sporting. ALAN ESTRADA: Sporting. About, L, M, N, O, P. DAVID J. Malan: OK. Svo skulum rífa þetta í tvennt. Það er allt í lagi. Þetta endar illa samt, því Mike Smith mun ekki vera í gulu síðurnar. ALAN ESTRADA: Aw. DAVID J. Malan: Nei, það er í lagi. En við skulum láta eins og hann er á þessari síðu. Svo nú hefur þú tálga vandamál niður að einni síðu, og við fundum Mike Smith. [Uppörvandi] Allt í lagi þakka þér. OK. Það var ótrúlega. En það var samt hraðar en línuleg leit, þar sem við byrjum á upphafi bókar, og við færa leið okkar frá vinstri til hægri, loksins að leita að Mike Smith. Og svo, ef símaskrá hafði kannski 1.000 síður, kannski það hefði tekið US 10 eða svo page tár. En þú gætir hafa skuldsett snert forsendu á allt það, sem er að segja að síminn bóka fyrirfram var það? Áhorfendur: Raðað. DAVID J. Malan: Það er flokkaður. Ekki satt? Það er raðað í stafrófsröð, svo að allir þeir nöfn og númer eru flokkuð frá A er til Z er, og í stafrófsröð á milli. En í dag, við biðjum nú spurningin, vel, hvernig var Regin eða síminn fyrirtæki fá það inn í þessi ríki? Vegna þess að það er eitt að nýta sú forsenda, og því, leysa vandamál með að reiknirit skilvirkari. En við aldrei raunverulega spurði í viku núll, vel, hversu mikið var það kostnaður Regin eða einhver annar að fá að símaskrána í raðaða röð? Ekki satt? Það skiptir ekki máli ef horfa upp Mike Smith er frábær fljótur, ef það tekur þig að ári til að raða síðum í upphafi. Ekki satt? Þú might eins og heilbrigður bara sigta í slembiraðaðri símaskránni, ef það er að fara að vera frábær dýrt að flokka það. Svo ef við getum haft aðra sjálfboðaliða. Við skulum taka a líta upp hér á hvernig við might-- koma á up-- hvernig við gætum farið um flokkun þessara. Og ef Jordan gæti reyndar tengja okkur upp hér á sviðinu. Komdu upp fyrir réttlátur a augnablik. Hvað heitir þú? CAROLINE: Caroline. DAVID J. Malan: Caroline, koma á upp. Og þú munt vera tengdur af mér og Jórdaníu hér. Caroline, þakka þér. Allt í lagi. Svo það sem við höfum hér fyrir Caroline er 26 blár bækur sem FAS notar til að stjórna ákveðin endanleg próf. Þetta eru að fá erfitt að finna, en það sem við höfum gert í fyrirfram er að við höfum sett nafn einhvers framan á öllum þessum, en við höfum haldið það einfalt með þá setja út fullt nafn. Þannig að við myndum setja mann með nafni L, D, J, B, alla leið A í gegnum Z, en þeir eru í handahófskenndri röð. Og svo ef þú vilt tala þínum leið í gegnum vandamál sem þú gera það, getur þú farið á undan og raða þeim fyrir okkur, frá A til Z. Áhorfendur: OK, svo er L eins, miðju. C er farin. B. J áður L. B, Q. DAVID J. Malan: Haltu sem hélt í eina sekúndu. Vegna þess að annars, þetta er aðeins áhugavert að þér, mér, og Jórdaníu. Það sem við förum. Áhorfendur: [inaudible]. R. DAVID J. Malan: OK. Hvað ertu að gera? CAROLINE: M kemur eftir O. DAVID J. Malan: OK. CAROLINE: O. DAVID J. Malan: O, Good. CAROLINE: E. DAVID J. Malan: E, F. Já. CAROLINE: T, U, V. DAVID J. Malan: V, T, U, V. Svo það lítur út eins og þú ert making-- halda áfram. Það lítur út eins og þú ert að gera stór stafli hérna, og góður af a stór stafli þarna. Svo fyrsta hluta stafrófinu, seinni hluta stafrófsins. OK. Good. Tegund skipta vandamál í tvennt. M, N, X. Já. CAROLINE: K. DAVID J. Malan: OK. K. Svo þú ert góður að velja þá einn eftir annan, setja það annaðhvort vinstri eða hægri, eða Z er að fara á gólfið. OK. CAROLINE: Z er að gerast á gólfinu. DAVID J. Malan: OK. Y er að fara á gólfið. Nú getum við sett X. CAROLINE: G. DAVID J. Malan: G er að fara til vinstri. S er að fara rétt. Allt í lagi, A er að fara alla leið til vinstri. CAROLINE: A, B, C, D. DAVID J. Malan: Nú, gott. Við höfum fengið A, B, C. W er að fara þarna niður. Allt í lagi, T. CAROLINE: H, I, J. DAVID J. Malan: H, I, J. Good. CAROLINE: Í miðju, ég er gonna-- DAVID J. Malan: OK. Svo nú erum við að fara að eins konar af sameinast þessar mismunandi hrúgur. Svo A gegnum C, þá get ég séð D, og E, og F, og G, og H, og I. Nice. J, K. Og þá, þetta stafli er hvolfi, en það er allt í lagi. Viss. Við getum skera nokkrar horn. OK. Og þá þurfum við W, X, Y, Z. CAROLINE: Já. DAVID J. Malan: Excellent. Svo stór þakka þér að Caroline fyrir flokkun þessara. [Uppörvandi] Þakka þér fyrir. Þakka þér kærlega. Svo nú skulum við íhuga um stund hvernig Caroline gekk um, gjörði það, og hvað nákvæmlega við gátu to-- hvernig við gátu til að leysa það vandamál þegar við vorum bara gefið a heild búnt af handahófi aðföngum. Jæja, það lítur út eins og það var a hluti af a kerfi þar? Hægri. Svo fyrri bréfum í stafrófinu, hún var að setja til vinstri, og síðar bréf í stafrófinu, hún var að setja í hægri. Og um leið og hún fann sumir aðlægan bréf, sjálfur að fara við hliðina á hvort öðru, hún myndi setja þá í röð. Og svo við höfðum eins konar þessir litlu hrúgur af flokkaður aðföngum viðburður. Og svo er það alveg eins og það Flest okkar menn myndu gera. Við viljum konar sigta í gegnum það, og við myndum konar hafa kerfi. En það gæti verið erfitt að skrifa það niður í formúlu per se. Það var aðeins meira lífræn en það. Svo við skulum sjá hvort við getum nú bundið vandamálið með færri aðföngum. Í stað þess að 26, við skulum gera eitthvað sem færri með bara segja, sjö, á bak þessar hurðir, svo að segja. Eru bara sjö tölur? Og ef markmiðið nú vegar er að finna gildi, við skulum sjá hversu duglegur við getum farið að gera þetta. Og við skulum sjá hvort við getum núna byrja að beita nokkrar tölur, eða sumir formúlur sem lýsa skilvirkni bókinni okkar sími reiknirit, exam bók reiknirit okkar, og almennt, að finna upplýsingar. Svo fyrir þetta, láta mig fara á undan, og á snertiskjánum hérna, setja upp a vefur flettitæki sem hefur nákvæmlega þessi sjö hurðir. Og ef við gætum fengið eitt annað sjálfboðaliða til að koma á hérna, Ég hef sett þessar sömu dyr hérna. Quick sjálfboðaliði. Þessi one-- demo eru að fara að hraðari og fljótari núna. Koma niður. Hvað heitir þú? TREVOR: Trevor. DAVID J. Malan: Trevor? Allt í lagi, Trevor, koma niður. Svo Trevor hefur boðist hér til gera svipuð vandamál, en sá sem er þrengri að umfangi, og það er að fara til að leyfa okkur að reyna að móta nú aðferð til að flokka þessar tölur. Svo Trevor, gaman að hitta þig. Svo hér er fylki, svo að tala, lista yfir sjö hurðir. Fara á undan og finna okkur númer 50. Og þá eftir því, segðu okkur hvernig þú fannst það. Ætti be-- allt í lagi. Já, þetta er einn hér? Uh-ó. OK. Þú smelltir þessari. Good. Og gott. Nú þú smelltir þessari. Og láta mig gefa þér hljóðnema, svo að þú hafir það í bara smá stund. Fara á undan og smelltu á í næsta húsi sem þú ætlar. Já, gott. TREVOR: Get ég unclick dyr? DAVID J. Malan: Nei, þú getur ekki unclick. TREVOR: OK. Þetta einn. DAVID J. Malan: Hvar viltu fara? Hver þeirra? TREVOR: Það eitt. DAVID J. Malan: No. TREVOR: OK. Þetta einn. DAVID J. Malan: Já. Það var gott. Allt í lagi. Svo það var reiknirit eða aðferð til að gera þetta, Trevor? TREVOR: Ég fór bara í gegnum hurðir fyrr en ég fann 50. DAVID J. Malan: OK. Excellent reiknirit. Svo er það í lagi. Því að í raun, ef ég sýna hvað er á bak við þessar tvær aðrar hurðir, hvað við munum finna hér er að við höfum aðeins handahófi inntak. Svo sem var í raun eins og góð og þú gætir fengið. Og í raun, fengið þér betri en tæmandi leita á ýmiss, vegna þess að það hefði verið mjög óheppinn ef þú hefðir högg fjölda 50 á allra síðustu dyrnar. En hvað ef við staðinn gaf þér forsendu. Ég geri ráð konar allt þessar hurðir kring, þannig að þú hefur tölur raðað í þetta sinn, en í þetta skiptið það er í raun a different-- þetta sinn, það er í raun raðað fyrir þig. Og nú markmiðið hendi er að slá númerið 50. TREVOR: OK. DAVID J. Malan: Hvað er reiknirit þinn að fara að vera? TREVOR: Jæja, ef það er raðað, það er annað hvort að fara að be-- ef stærsta til stærsta, niður, verður það að vera sá fyrsti, eða ef það er hið gagnstæða, það verður það síðasta. Þannig að ég ætla bara að tappa þessa hurð, og þá bara tappa síðustu dyrnar. DAVID J. Malan: Excellent. Allt í lagi. Svo fundum fjölda 50. Svo um leið og þú vissir þeir voru flokkuð, við voru fær um að nýta þessa forsendu. Svo þeir eru of mikið eins og símaskrá dæmi. Um leið og þú hefur, jafnvel með lítið vandamál eins og þetta, inntak pre-raðað, við getum í raun að finna gildi að öllum líkindum skilvirkari. Og ég var ekki að segja þér ef það var flokkaður lítil og stór, eða stór til lítil, og svo það var mjög sanngjarnt til að byrja á annan endann eða öðrum að í raun finna þessi markgildi. Svo þakka að Trevor eins og heilbrigður. Og ég ætla að propose-- fallega gert. Við höfum smá bút, reyndar, það er meðal uppáhalds augnablikum okkar í CS50, þar stundum þessar kynningar ekki alveg að fara samkvæmt áætlun. Og reyndar núna, ég dreginn upp rangt tengi sem á að nota snertiskjáinn. Svo það var mér að kenna þar. Þannig að þetta mun gera fyrir myndband á næsta ári eins og hvers vegna ég var að smella á skjánum mínum. En við skulum taka a fljótur líta á það sem gerðist á síðasta ári með Jay, kom sér, mikið eins Trevor hér, bauðst, og í þessari stuttu myndband, munt þú sjá hvernig þetta sama kynningu ekki alveg sýna sömu kennslustundum lært. [Vídeó spilun] -Öll Ég vil að þú að gera núna er að finna fyrir mig, og fyrir okkur, í raun, fjölda 50 eitt skref í einu. -The Númer 50? -The Númer 50. Og þú geta sýna hvað er á bak við hvert af þessum hlerum einfaldlega með því að snerta það með fingri. Fari það. [Hlæjandi] [END spilun] DAVID J. Malan: Svo að gekk mjög vel. Þeir voru óflokkaðar hurðir. Og Jay, að sjálfsögðu, fann það allt of fljótt. Trevor gerði miklu betur í skilmálum teachable stund, svo að segja, á þessu ári í taka lengri tíma að finna það. Auðvitað, þá gáfum Jay annað tækifæri, þar sem við raðað dyr, bara eins og við gerðum fyrir Trevor, og Trevor gerði frábær vel að þessu sinni. En Jay gerði það helmingi fljótt. [Vídeó spilun] -The Markmiðið er nú einnig finna okkur númer 50, en gera það algorithmically og segðu okkur hvernig þú ert að fara um það. -OK. -Og Ef þú finnur það, halda þér myndina. Ef þú finnur ekki það, þú gefur það aftur. -Man. -OH! - [Inaudible] OK. Þannig að ég ætla að athuga enda fyrst að ákveða hvort there's-- Oh. [Applause] [END spilun] DAVID J. Malan: OK. Svo flokkun dyr greinilega leiðir til meiri skilvirkni. Og svo, tvisvar eins hratt er það sem ég þýddi það. Og svo Jay fékk heppinn bæði skiptin. Og hann fékk einnig heppinn í því síðasta ári, pantaði ég nokkrar Blu-geisli diskur að í raun að gefa út. Fyrirgefðu þessu ári, við ekki hafa það sama, Trevor. En betra samt var fyrir nokkrum árum. Og sumir af þú might vita þetta náungi, Sean, sem hann var í CS50, var mótmælt með nákvæmlega Sama vandamál, að vísu í SD, eins og þú munt fljótlega sjá, aftur í dag. Og þú munt komast að því að ekki aðeins var hann taka aðeins lengri tíma en Jay, aðeins lengur en Trevor, það var reyndar þetta frábæra tækifæri til að taka þátt næstum alla í mannfjöldi a la verðið er rétt, hvetja honum að finna fjölda sem við vorum að leita að. Skulum. taka a fljótur líta. [Vídeó spilun] -OK. Svo þitt verkefni hér, Sean, er eftirfarandi. Ég hef falið á bak við þessar hurðir fjöldi sjö. En matur burt í sumum þessara hurðir sem eru önnur neikvæðar tölur. Og markmið þitt er að hugsa af þessum efstu röð af tölum sem bara fjölda, eða bara röð af stykki af pappír með tölur á bak við þá. Og markmið þitt er, aðeins að nota efst array hér, finna mér númer sjö. Og við erum svo að fara að gagnrýna hvernig þú ferð að gera það. -Allt í lagi. -Find Okkur Talan sjö, takk. Nei Fimm, 19, 13. [Hlæjandi] Það er ekki bragð spurning. Einn. [Hlæjandi] Á þessum tímapunkti, skora er ekki mjög gott, svo þú might eins og heilbrigður að halda áfram. Þrjú. [Hlæjandi] Haltu áfram. Frankly, ég get ekki annað en furða það sem þú ert jafnvel að hugsa um, so-- [Hlæjandi] Aðeins efsta röð, svo þú hefur fengið þrjú vinstri. Svo að finna mér sjö. [Hlæjandi] 17. Seven. [Applause] Allt í lagi. [END spilun] DAVID J. Malan: Svo við gátum horfa þetta allan daginn. Og auðvitað, sum demo þessu ári kannski mun nú endað í næsta video ári eins og heilbrigður. Svo nú skulum raunverulega leggja áherslu á reiknirit hér, og sjá hvort við getum ekki nú byrja að móta hvernig við getum farið um að fá gögn okkar í þessu ástandi að það er raðað, svo að lokum, getum við í raun leita það á skilvirkari hátt. Og jafnvel þó að við erum að fara að nota nokkuð lítið gagnagrunna, eins átta tölurnar við hafa hér á borð, lokum þessir sömu hugmyndir gæti átt 1.000 aðföngum, milljón inntak, 4 milljarða inntak, því reiknirit eru að fara að vera í grundvallaratriðum sú sama. Og svo er þetta síðasta vor tækifæri fyrir sjálfboðaliða í dag, en kannski helst koma einn, sem við þurfum átta sjálfboðaliða að koma upp og ganga okkur í gegnum Ferlið flokkun hvað mun brátt vera á þessum tónlist stendur hér. Leyfðu mér að byrja aftur hér. Svo einn í turquoise-- græna er það? Ert þú að fremja? Two. Koma niður. OK. Þrjú. Four. Láta me-- OK, fimm. Þú ert að vera tilnefndur af vini þínum. Sex, sjö og átta. Komdu upp. Allt í lagi. Þakka þér kærlega fyrir. Komdu upp. Komdu upp. Allt í lagi. Svo það sem við höfum here-- og þetta er meðal fleiri óþægilega sjálfur, þar sem þetta krefst þess að þú húmor mér fyrir réttlátur a lítill hluti af tími. Þú skalt vera númer eitt. Hvað heitir þú? Annan: Annan. DAVID J. Malan: Annan. David. Hvað heitir þú? JOSEPH: Joseph. DAVID J. Malan: Joseph, þú ert númer tvö. SERENA: Serena, númer þrjú. Stefan, númer fjögur. CYNTHIA: Cynthia. DAVID J. Malan: Cynthia, númer fimm. [Inaudible] DAVID J. Malan: [inaudible]. David, númer sex. MATT: Matt. DAVID J. Malan: fjöldi Matt er sjö. Og? WAVERLY: Waverly. DAVID J. Malan: Waverly, númer átta. Allt í lagi. Ef þú could-- Úpps. Ef ykkur öllum, eins og þinn Fyrsta áskorunin, það eru átta tónlist stendur hér frammi fyrir áhorfendur. Ef þú gætir sett tölur þínar á þessum tónlist stendur á þann hátt að þeir stilla upp með sömu tölur á borðinu. Svo að þér líta út eins og að með því að setja tölur þínar á þessum tónlist stendur hér. Excellent svo langt. Excellent. OK. Svo nú erum við að fara að spyrja Spurningin í nokkrum mismunandi vegu. Hvernig getum við farið um flokkun þessi fólkinu hérna? Því við vorum nokkrar aðferðir fyrr, þar sem við vorum konar að gera tvær mismunandi hópa. Og þá vorum við yfirleitt piecing hlutina saman. Um leið og við sáum tvær tölur sem átti saman, við setjum þá saman. Tvö bréf sem tilheyra saman. En við skulum sjá hvort við getur ekki móta þetta, þannig að við höfum á endanum sumir gervi-númerið sem þú vilt, sem þú getur leyst þetta vandamál. Svo nú er ég að leita út á þessar tölur hér. Og ég sé allt fullt af mistökum. Á endanum, ég vil einn á vinstri og átta ofan. Og svo ég er að leita á þessir tveir, fjórir og tveir. Og hvað er vandamálið, augljóslega? Já. So. Two kemur augljóslega áður fjórir, svo þú veist hvað? Leyfðu mér að taka fyrst gráðugur nálgun, ef þú vilt, eins vandamálið setja one-- ef þú manst frá Standard Edition af Problem Set One, þar sem ég bara á staðnum að leysa vandamál sem er hérna fyrir framan mig og sjá hvar það leiðir mig. OK. Svo tveggja og fjögurra, láta mig fara undan og bara skipta þér tvo. Ef þú getur líkamlega færa ykkur og pappír þinn, Ég virðist hafa fengið að skrá í betri stöðu. Nú, þeir gott. Ég ætla að fara, fjögur og sex, lítur vel út. Ekki vandamál. Sex og átta, OK. Átta og eitt, annað vandamál. Vegna þess að það er satt um átta og einn? Einn kemur fyrir átta, og svo hvað eigum við að gera? Við skulum skipta þessar tvær. Einn og átta. Og nú ætla ég að fara að halda áfram. Ég ætla að halda að leita á undan. Og við skulum sjá hvað gerist. Átta og þrír, af Auðvitað út af röð. Skulum skipti. Átta og sjö, auðvitað. Bilað. Skulum skipti. Átta og fimm, auðvitað, við skulum skipta. Allt í lagi. List er raðað. já? OK, augljóslega ekki. En það er lítið betra, ekki satt? Vegna tilkynning hvað gerðist. Hvert skipti sem við framkvæmdu skipti, minni Fjöldi konar percolated þannig, og stærri tala percolated þessa leið, eða við munum byrja að segja í loftbólum til vinstri eða í loftbólum til hægri. Nú, það er ekki nóg, því í besta falli númer gæti hafa flutt eitt blettur fram, eða í versta falli, a tala gæti hafa flutti eitt blettur frekar. Svo þú veist hvað af þessu tagi af unnið ágætlega hingað til. Leyfðu mér að reyna bara aftur. Tveggja og fjögurra, þeir OK. Fjögur og sex, þá eru þeir í lagi. Sex og einn, út af röð. Svo skulum skipta þér tvær. Og nú, eftir að vandamálið er farin að fá smá betri aftur. Sex og þrír, út af röð. Við skulum skipta þér tvær. Sex og sjö, þú ert góður. Sjö og fimm, að sjálfsögðu, út af röð. Sjö og átta, í því skyni. Og nú gæti ég þurft að gera þetta nokkrum sinnum. Og í raun held sjálfir kannski hversu oft hámarks gæti ég þurft að ganga fram og til baka? Við munum koma aftur að því. Svo tveir og fjórir eru enn í lagi. Fjögur og eitt, nei. Svo skulum skipti. Og aftur, eftir sjónrænt einn er góður af freyðandi til vinstri, þar sem það ætti að vera. Fjögur og þrjú skipti. Fjögur og sex. Sex og fimm skipti. Sex og sjö. Sjö og átta eru góð. Good. Við erum að fá jafnvel betri. Svo skulum sjá. Nú höfum við tvö og einn. Auðvitað, skipta. Tveir og þrír, þrír og fjórir, fjórir og fimm, sex og sjö, sjö og átta. Good. Og þú veist hvað? Vegna þess að ég gerði eina breytingu þar, Leyfðu mér að gera eitt geðheilsu stöðva. Leyfðu mér að fara alla leið aftur á byrjun. OK. Einn, two-- jamm, sjá? Eitthvað var rangt. Þrír, fjórir, fimm, sex, sjö, átta. Og í þessu síðasta framhjá, eru þú ánægð með minn núna segja að það er raðað? OK. Sjónrænt, það er alveg satt. En virkni, hvað gerði líka bara gerst í þeirri síðustu umferð sem gerir þér til að staðfesta að þessi listi er örugglega flokkaður? Hvað gerði ég gera eða ekki gera þetta síðasta framhjá? Áhorfendur: Það voru engar breytingar. DAVID J. Malan: Svo? Áhorfendur: Engar breytingar. DAVID J. Malan: Það voru engar breytingar. Svo það væri heimskulegt af mér að gera það sama reiknirit aftur ef ég vissi ekki að allir breytir í fyrsta skipti. Og ríkið hefur ekki breyst. Víst, ég er ekki að fara að gera Allar breytingar í annað sinn. Og svo, það er óhætt núna að segja, lista er raðað. Og reyndar, þetta er nú eitthvað sem við munum almennt kalla kúla tegund, þar gefnar, þú leiðrétta mistök aftur, og aftur, og aftur, og þú halda áfram fram og til baka, og fram og til baka, þar til þú gera engar slíkar skiptasamninga, á hver benda þú getur verið viss um, já, ég lauk ákveða allar mistökum. Við skulum endurstilla og reyna nýja nálgun. Ef þú krakkar gætu farið aftur í röð þú varst í smá stund síðan, sem leit út eins og þetta. Nú, við skulum taka nálgast aðeins meira eins og próf bók, þar sem við vorum stöðugt velja bókstaf sem við vildum konar að takast á við næsta. Kannski var það mikil bréf, eins A, eða lágt bréf Z. Svo er allir aftur í þessari röð. Og nú langar mig að gera þetta. Við skulum sjá Ég veit að ég hef átta tölur hér. Ég ætla að fara á undan og bara vísvitandi að velja minnstu atriði. Ekki satt? Þetta virðist innsæi líka. Hvers vegna get ég ekki fundið minnstu þáttur, setja það þar sem það tilheyrir, þá fá næsta minnstu þáttur, setja það þar sem það tilheyrir, og bara endurtaka. Vegna innsæi, sem ætti að virka líka. Svo, það er fjórir ansi lítill fjöldi. Ég ætla að muna hvar þetta er. Bíddu aðeins. Tveggja er minni. Leyfðu mér að muna nú að hvar sem tveir er, og gleyma um fjögur. Við munum takast á við það seinna. Sex, ég hef ekki áhuga. Átta, ég hef ekki áhuga á. Eitt er nýr lítill númerið mitt. Þannig að ég ætla að muna hvar maður er. Þrír, ekki áhuga. Seven, ekki áhuga. Fimm, ekki áhuga. Svo án þess að detta stigi á þessu ári, Ég ætla að grípa fjölda one-- og hvað hét aftur? Annan: Annan. DAVID J. Malan: Annan. Og ef þú gætir komið með mér á upphaf listanum, við skulum setja þig þar sem þú tilheyrir. Unfortunately-- hvað er nafnið þitt? STEFAN: Stefan. DAVID J. Malan: Stefan er á leiðinni. Svo áður en Stefan leysa þetta Vandamálið, hvað eigum við að gera? Hvað gerum við við Stefan? Áhorfendur: [inaudible]. DAVID J. Malan: OK. Þannig að við gætum gert það. Við gætum konar taka Stefan og hans fjögur, og bara setja það í breytu og halda í það fyrir talsverða tíma, þannig að gera pláss fyrir númer eitt. Og það er ekki slæmt. Ég gæti bent, hvers vegna ekki við setjum bara Stefan hér? Hvers vegna gæti þetta brjóta eitt af þeim hugmyndum sem við byrjuðum að tala um síðustu tíma, í síðustu viku? Já? Áhorfendur: [inaudible]. DAVID J. Malan: Það er engin Vísitala fyrir það. Ef þú hugsa um þetta, örugglega, eins og óákveðinn greinir í ensku array, þetta er eins neikvætt einn, þannig að það er ekkert minni í raun hér ef þetta er örugglega fylki, eins og við lýst í síðustu viku í fyrirlestri. Svo við ættum ekki að gera þetta. Við gætum geyma það í breytu. Eða þú veist hvað? Ég heyrði einhver annar benda henni. Hvað annað gætum við gert með Stefan? Hvers vegna eigum við ekki að evict bara hann og setti hann yfir þar númer eitt var. Svo ef þú vilt fara þarna. Og reyndar, þetta er nokkuð góð lausn. Nú á annars vegar hef ég góður af gerði vandamálið verra. Fjögur er nú lengra í burtu frá þar sem það ætti að vera. Það ætti að vera til þessa hluta. En þú veist hvað? Það gæti hafa verið óheppni. Kannski númer átta var hér. Og svo, kannski við gerðum hafa fengið heppinn, og ýtt átta nær til loka. Svo í lok dagsins, það svona allt meðaltöl út. Við þurfum ekki að hugsa um fjögur. Allt sem ég hugsa um núna er velja minnstu þáttur. Og nú, hvað ég ætla að gera er að gleyma um númer eitt varanlega, því ég veit að Listinn aftan mig er nú flokkaður. Svo minn listi var áður stærð átta. Nú er það á stærð sjö. Svo vandamálið mitt er að verða minni, að vísu línulega. Svo nú er ég að fara að velja núverandi minnsti þáttur, tveir. Sex, átta, fjórir, þrír, sjö, fimm. Það var minnsta þáttur. Svo hvað er ég að fara að gera with-- Hvað hét aftur? JOSEPH: Joseph. DAVID J. Malan: Joseph? Við erum að fara að yfirgefa Jósef í stað. Nú ætla ég að þykjast að þessir krakkar are-- vel, Ég veit að þessir tveir eru þegar raðað. Beinum nú sjónum á Afgangurinn af listanum. Six er núverandi minnsta. Átta er stærri. Fjögur er nú núverandi minnstu. Þrjú er nú núverandi minnstu. Og svo nú, ég ætla að velja þrjá, sem is-- hvað er nafnið þitt aftur? SERENA: Serena. DAVID J. Malan: Serena, ef þú gætir grípa þitt og skipti with-- KALSANG: Kalsang. DAVID J. Malan: Kalsang. Koma á aftur, og við erum fara að skipta þessir tveir. Og nú, við skulum setja þetta á Autopilot. Ég ætla að fara og fara með hana til ykkur til að velja næsta minnstu atriði. Dun Dun Dun Dun. Númer fjögur, hvað ættir þú að gera? Excellent. Nú, ég ætla að gera annað framhjá. Dun Dun Dun Dun. Ég sé fimm er næsta lítill. Nú, ég ætla að taka aðra sendingu. Dun Dun Dun Dun. Six er minnsti. Good. Seven er minnsti. Engin breyting. Átta er minnsti. Lokið. Svo það sem við höfum bara gert með því að iteratively að velja einn þáttur á eftir öðrum er framkvæma eitthvað sem að við erum að fara að móta og val tagi. Og það er jafnvel einfaldara að útskýra, í að bókstaflega allt sem þú langar að gera er bara að halda fara fram og til baka í gegnum listann velja, næsta lítill þáttur, þar til þú ert búinn. Svo það er jafnvel einfaldara, kannski innsæi, en í fyrra. Við skulum reyna í síðasta einn. Ef þú krakkar gætu endurstilla ykkur í eftirfarandi stöður Eitt síðasta sinn, við skulum sjá hvort við getum ekki nú formlega eitt annað nálgun. Í raun, myndi einhver þarna eins og að leggja hvernig annars gætum við farið að gera þetta? Án kasta út buzzwords eða tegund af svörum sem eru nú þegar þekkt, bara innsæi, hvað getum við gert? Áhorfendur: [inaudible]. DAVID J. Malan: Já. Svo er það einhver mikill innsæi þar. Góðir hlutir virðast gerast svona langt í tölvunarfræði þegar við skipta og sigra vandamál af því að deila það í tvennt og tvennt og tvennt. Og svo reyndar, við gæti byrjað að gera það. Og í raun, það er að fara að vera, við munum sjá, einn af bestu lausnir okkar enn. En við skulum koma aftur til að áður en langur. Í raun erum við að fara að gera sem stuttu seinna í þessari viku. Hvað annað gætum við gert til að leysa þetta? Svo er allir hér í virðist af handahófi röð. Veistu hvað? Frekar en að fara fram og til baka, fram og til baka, fram og til baka í hvert sinn, þetta er eins og Ég er að gera a einhver fjöldi af gangandi. Hvers vegna get ég ekki að byrja bara á upphaf listanum, og bara setja fjögur þar sem það tilheyrir? Svo láta mig gera ráð fyrir stundu að minn listi er bara þetta fyrsti þáttur. Er fjögurra flokkaður á þessari stundu í tíma, ef allt sem ég hugsa um er allt hér? Þetta er tegund af trivially satt, ekki satt? Eins listanum inniheldur eitt númer, og sem tala fjögur er augljóslega flokkaður. Svo láta mig kveða bara að þessi listi er flokkaður. En nú hef ég restina af þessum lista. Svo nú, lendir I tvö. Hvar er tvö augljóslega tilheyra með tilliti til fjórum? Áður fjórum. Svo hvað get ég gert hér? Hvað er nafnið þitt aftur? JOSEPH: Joseph. DAVID J. Malan: Joseph, ef þú gætir stíga til baka fyrir aðeins augnablik með númerið þitt. Og nú hvað ætti Stefan gera hér? Við skulum skipta Stefan hérna. Og nú skulum Joseph koma hér. Og nú, láta mig halda því fram að allt hér er flokkað. Svo, að svipuð niðurstaða, en grundvallaratriðum ólík nálgun. Ég hef ekki einu sinni litið hvað er þarna niðri. Ég halda bara að taka þá þætti eins og þeir eru afhent mér, og takast á við þá. Svo nú, ég sjá númer sex. Hvar er númer sex tilheyra? Við höfum tvær, fjórar, sex. Nákvæmlega þar sem hún er núna. Svo skulum fara það eitt og sér, og nú halda því fram að þessum hluta af the listi er nú flokkað. Og svo, þetta finnst grundvallaratriðum mismunandi í því að ég er bara fara í gegnum listann hér línulega, og ég er aldrei tvöföldun aftur. Já. Allt í lagi. Svo átta, þar tilheyra þér? Hérna. Perfect. Svo nú, einn. Uh-ó. Þetta er eins og það er að fara að vera dýrt. Nú, í fyrri reiknirit, Ég skipti bara fólk. Þannig að ég gæti sett hann alla leið á upphaf, en flutti Jósef. En ef ég flyt Jósef, nú hvað er að fara að vera rangt? Nú hef ég svona undone-- ég hef tekið eitt skref fram á við og þá eitt skref til baka, vegna þess að nú Joseph vildi vera út af röð. Svo skulum gera þetta. Ef þú gætir tekið númer eitt og stíga til baka fyrir aðeins augnablik. Hvernig getum við put-- það var heitirðu aftur? Annan: Annan. DAVID J. Malan: Annan í stað? Hvað þarf að gerast með tilliti að tveir, fjórir, sex og átta? Þeir þurfa að skipta. Svo ef átta langar til að skipta fyrst, þá sex, þá fjórir, þá tvö. Og þá Annan, ef þú vilt eins og til að koma hingað, góð. En hér, höfum við bara konar greitt verð á öðrum stað í reiknirit. En síðast þegar við val flokka, og jafnvel kúla tegund, Ég er að ganga til baka og fram, fram og til baka, sem er vissulega að bæta upp tími-vitur, og bókstaflega þrepum. Innsetning tegund, fyrst sýn, lítur út eins og það er frábær klárari, með því að ég er bara gera hægur, stigvaxandi framfarir, en ég ætla ekki að fara þetta fram og til baka. En ef einhver er örugglega út af röð, tilkynningu alla vinnu sem ég þurfti bara að gera. Ég þurfti að fara helminginn af listanum bara til að gera pláss fyrir númer eitt. Svo er það sama upphæð vinnu svona langt það finnst bara öðruvísi tegund af vinna. Við skulum halda áfram. Svo nú vitum við að allir milli einn og átta eru flokkuð. Hér hef ég númer þrjú. Ef þú vilt að taka upp númer þrjú, stíga til baka einn. Og hvað þú krakkar þarft að gera? Jebb. Svo er það annað, tveir, þrjú skref. Þrjár einingar af tíma sem bara kosta mér, svo að þrír geta nú passa. Að lokum, sjö. Við skulum fara á undan og hafa þú taka skref til baka. Þetta er bara að fara að kosta okkur ein eining af tíma, en það er allt í lagi. Og nú, fimm er að fara að vera svolítið dýrari. Ef þú vilt að stíga til baka. Við þurfum að fara átta, og sjö og sex. Og þá munu allir er nú flokkaður. Svo stór hönd sjálfboðaliða okkar hér. Þakka þér kærlega fyrir. [Applause] Þakka ykkur öllum. Þakka ykkur öllum. Svo skulum sjá nú bara hvernig dýr allt sem var. Við skulum íhuga kannski Einfaldasta þeirra, kúla tegund. Og ég segi einfaldasta, bara vegna þess að þú getur leyst það græðgislega bara með laga pöruðum vandamál hér. Festa pöruðum vandamál hér, aftur og aftur og aftur, endurtaka eins og margir oft og þú þarft í raun að. Svo kemur í ljós að með kúla tagi, vel, hversu mörg skref þarf ég að taka á fyrsta umferð þess reiknirit? Ég gæti take-- skulum see-- einn, tveir, þrír, fjórir, fimm, sex, sjö. Og það er átta þætti hér. Svo það er eins og n mínus 1 skref til fá frá upphafi listanum til loka listanum. En með val tagi, muna að ég er að velja þá þætti aftur og aftur og aftur er það minnsta, Ég er að setja það í stað, en þá er ég ekki leita á bak við mig aftur. Þannig að ég held að það sé svolítið skýrari þá í fyrsta skipti, gæti ég að taka alla n mínus 1 skref að finna minnstu frumefni. Og ég setti þá í stað, og ég evict hver var hér áður. En þá þarf ég ekki að halda að leita á þennan þátt, vegna þess að ég veit að það er þegar minnsti. Svo nú get ég líta á bara sjö þætti, þá sex þætti, þá fimm þætti, þá fjóra þætti. Og svo stærðfræðilega, ef n er fjöldi staka eða númer að við byrjuðum með, getur þú ímyndað þér að þetta er það sama og n mínus 1, plús n mínus 2 skref, plús n mínus 3 skref, plús n mínus 4 skref, öll leið niður í aðeins eitt skref. Og ég er á síðasta mann minn. Og ef þú manst að mikið af stats bækur eða stærðfræði bækur hafa þessir formúlur á Hardcover aftur eða framan af þeim, það kemur í ljós að þessari röð er að lýsa einfaldlega sem n sinnum n mínus 1 yfir 2. Og það er allt í lagi ef það er ekki í fremstu röð á huga þinn. En þetta er örugglega satt. Það er bara einfaldara leið til að skrifa hana. Og svo ef þú heldur að aftur í grunnskóla, þegar þú byrjar bara að margfalda það út, þetta er auðvitað, er bara n veldi mínus n deilt með 2. Allt sem ég hef gert er að auka orðalagið þar. Og svo skulum umrita þetta svolítið öðruvísi. Það er n kvaðrat deilt með 2 mínus N / 2. Svo aftur, ég er bara svona að beita sumir tölur reglur þar. En takið nú að stærsta tíma í þessari tjáningu, svo að segja, er að n veldi. Svo já, það er n veldi deilt með 2, mínus N / 2. En almennt, ef n er að fara til vera a stór gildi, Ég ætla að halda því fram að n veldi er að fara að vera ráðandi þáttur. Það er bara að fara að vera stærri framlög til fjölda skrefum en n / 2. Svo hvað ég meina með þessu? Við skulum reyna einfalt dæmi, jafnvel þótt stærðfræði fær smá stór. Svo býst við höfðum 1 milljón manns á sviðinu, eða 1 milljón hlutum sem við viljum að raða. Skulum stinga milljón í nákvæmlega þeirri formúlu að sjá hversu mörg skref sem það tekur samtals að raða milljón þætti með segja, val tegund. Þannig að við myndum hafa sömu formúlu og áður. Ég myndi stinga milljón, þannig að ég fæ milljón kvaðrat deilt með 2, mínus milljón deilt með 2. Ef ég geri það stærðfræði fyrirfram hér höfum við 500 milljarða mínus 500.000, sem gefur okkur 499999500000, sem er laglegur fjári stór. Í staðreynd, ef þú bera saman núna 499000000000, 999 milljónir, 500.000 á móti upprunalegu gildi okkar, 500 milljarðar, það er svo fjandinn nálægt. Ekki satt? n kvaðrat deilt með 2 gefur us-- eða öllu heldur, n kvaðrat deilt með 2 gaf okkur 500 milljarða. Það er nokkuð fjári nálægt að 499,999,500,000, sem er að segja að draga burt 500.000, eða oftast draga burt n veldi, í raun ekki stór samningur. The n veldi gerir þetta tölur vaxa mjög hratt. Nú, þetta er mikilvægt aðeins að því marki eins og við, eins og tölva vísindamenn, eru almennt ekki að fara að hugsa svo mikið um blæbrigði þessum formúlum og nákvæmlega hvað nákvæmar svör eru. Við sama bara það, þú veist hvað? Í lok dags, þetta uppskrift er á röð af n veldi. Já, við erum að deila með 2 í það. Já, við erum að draga burt n mínus 2. En í lok dagsins, hugtakið sem raunverulega særir okkur og kostar okkur a einhver fjöldi af stíga er að veldi tíma. Og svo það sem tölvunarfræðingur er að fara að gera almennt er hunsa alla þá minni pöntun hugtök, og bara líta á einn sem stuðlar mest að kostnaði. Og þetta er gott, vegna þess að við getum nú tala í mun meiri almenn um reiknirit, og er að bera þá. Og sú staðreynd að ég er nota þessa O er vísvitandi. Þegar ég segi á röð um, ég er sérstaklega vísa til eitthvað heitir stór O. Og stór O er merki sem tölvan vísindamaður notar til að lýsa efri bundið á eitthvað. Svo ef þú segir að reiknirit er í stórum O n veldi, eins og ég lagði bara áðan, það þýðir að í skilmálar af gangi hennar tíma eða skilvirkni þess, það tekur á röð af n veldi skrefum. Kannski meira, kannski minna. En það er á röð n veldi. Og það er efri. Það er ekki að fara að vera meira sársaukafullt en það. Það er ekki að fara að vera n cubed, eða 2 í n, eða eitthvað miklu stærra. Þetta er að skilgreina efri mörk á hvað sem kostnaður er. Svo í ljósi þess, við skulum íhuga bara nokkur dæmi. Og þetta er bara tímabundið listi mjög algengar í gangi sinnum fyrir reiknirit sem er ætlað að vera lýsandi sumum hlutum sem við höfum séð nú þegar. Svo til dæmis, í tilviki Val tegund, hvað ég er að segja hér er í gangi því vali Raða er tíminn er á röð n veldi. Í versta tilfelli, ég ætla að hafa a heild búnt af handahófi tölur hér. Og eins og við sáum stærðfræðilega, ef ég halda gangandi í gegnum listann, í gegnum lista, velja næsta minnstu þáttur aftur og aftur, ef ég í raun skrifa niður öll skrefin Ég ætla að taka eins og ég lagði formulaically áður, það er á stærðargráðunni n veldi skref sem ég er að taka. Og það kemur í ljós að kúla flokka og innsetning konar eru bara eins og hægur í versta tilfelli. Hugleiddu til dæmis, innsetning flokka, mjög síðustu reiknirit við brugðist við, sem hafði okkur að líta á frumefni, og þá setja það þar sem það tilheyrir. Og þá erum við leit á næsta frumefni, og sett það þar sem það tilheyrir. Svo telja bestu mögulegu atburðarás. Segjum að ég hefði sjálfboðaliðar mínar stilla upp bókstaflega eins og þetta, eitt til átta, þegar raðað. Hversu mörg skref er innsetning tegund að fara að taka að raða átta manns, ef þeir koma á sviðið leita svona? Átta manns þegar raðað. Og ég nota Innsetningarröðun. Að síðustu af reiknirit. Jæja, við skulum lögleiða alvöru hratt. Þannig að ef ég byrja hér, ég sé einn. Þar er einn tilheyra? Það tilheyrir hérna. Ég sé tvo. Hvar tveir tilheyra? Hérna. Ég sé þrjú. Hvar þrír tilheyra? Hérna. Ég sé þó fjóra. Hérna. Fimm, sex, sjö, átta. Það er engin ástæða til að endurtaka mig. Og svo, hversu mörg skref er að með tilliti til n? Það er á röð n skref, ekki satt? n mínus 1. En ég tók línulegt fjölda skref, og nú ég er búin. Svo er það besta mál, þó. Hvað um versta tilfelli? Hvað átta voru þarna, og sjö voru þarna niðri, og einn og tveir voru hérna, svo að listinn væri sannarlega snúið? Jæja, hvað gerist örugglega ef þetta er númer? Og við munum gera bara nokkrar af dæmum. Hvað ef, reyndar númer átta er hér, og number-- Úpps. Svo hvað ef, reyndar númer átta er alla leið hérna, og ég er að nota Innsetningarröðun? OK. Ég kröfu á því augnabliki sem það er í stað. En nú, seven-- hvar sjö fara? Auðvitað fer það hérna. Svo ég verð að fara átta yfir einum stað. Nú sex, þar er það að fara? Jæja, allt í lagi. Nú, ég verð að fara átta yfir staður, og sjö yfir stað, og þá er ég plop niður sex. Svo í fyrsta skipti, það kostar mér eitt skref til að festa það, þá kosta mig tvö skref til að festa það. Hversu mörg skref er það að fara að taka til að festa atriði sem þarf að setja fimm á réttum stað? Þrjú. Því nú verð ég að færa einn, tveir, þrír. Hversu mörg skref er það að fara að taka að setja fjögur á réttum stað? 4 plús 5, auk 6, plús 7. Og svo er það stærðfræðilega samhljóða það sem við lýst fyrir vali tagi. Við höfum þessa röð það er bara að aukast. 1 plús 2 plús 3 plús 4, eða öfugt, 7 plús 6 plús 5 plús 4 bætir upp fyrir dag er tilgangi til á röð n veldi. Svo láta mig kveða líka að kúla tegund er einnig í n veldi. Vegna þess að með kúla tagi, hvert skipti sem ég fer í gegnum listann, Ég ætla að taka það bil hversu mörg skref? Hvert skipti sem ég bókstaflega ganga þaðan til þar? Rúmlega n skrefum. En hversu oft gæti ég þurfa að fara í gegnum listann? Jæja, u.þ.b. n tíma. Kannski n mínus 1, en u.þ.b. n sinnum. Ja, hvers vegna er það? Jæja, með kúla tagi, ef við byrjum með kúla tagi, með lista í versta ástand, sem aftur er alveg aftur á bak, hvað er að fara að gerast? Ég fer í gegnum listann, og fjölda einn tilheyrir alla leið þarna. En með kúla tegund, hversu langt er einn fara á fyrsta framhjá mér í gegnum listann? Hversu margir blettir er hann að fá nær á réttan stað? Bara einn. Svo ef þú konar ástæða í gegnum þetta, í hvert skipti í gegnum þetta reiknirit, Taka u.þ.b. n skrefum Davíðs. En hversu margir fer gegnum listinn er það að fara að taka fyrir einn til að kúla til vinstri þar sem það tilheyrir? Hann fékk að fara út, n rými á þennan hátt. Svo bara að gera flokkun á listanum, Ég verð að ganga fram og til baka n sinnum. Og í hvert sinn, er ég horfa á n þáttum. Svo gera n hlutina n sinnum á röð af N veldi. Nú munum við sjá í sumum af stuttbuxur sem eru hluti í næsta vandamál CS50 er sett, nýja nálgun á þetta, en nú, við skulum íhuga bara sumir aðrir gangi sinnum, sérstaklega ef flokkun sjálfur taka smá tíma til að sökkva í. Hvað er algrím sem við höfum séð nú þegar sem tekur á röð n skrefum? Hvað ætti að taka línulega fjölda skref sem við höfum séð svona langt? Hvað er þetta? The sími skrá leit. Fyrsti reiknirit. Ekki satt? Þar sem við erum línulega leita Mike Smith? Einmitt. Frá viku núll, þegar ég byrjaði beygja eina síðu í einu, og ég sagði jafnvel að það var góður úr línulegri tilfinningu reiknirit, og við höfðum þessi mynd á borð við beina rauða línu og beina gula lína, þeir voru örugglega reiknirit sem eru í stór O í n. Því að finna Mike Smith í síma bók n síður, í versta tilfelli, gæti tekið mig n skrefum. Hvað um að taka mætingu? Einn, tveir, þrír, fjórir, fimm, sex. Hvað er í gangi þegar þetta er Reiknirit til að taka mætingu? Stór O af N, vegna þess að í kenningu I að benda öllum í herberginu. Nú sem innskot, hvað um annað hagræðingu frá viku núll? Tvær, fjórar, sex, átta, 10, 12. A tölva vísindamaður myndi gera sér grein fyrir, bíddu í eina mínútu, það er á röð n deilt með tveimur skrefum. Ekki satt? Þar sem ég er að gera tvær manneskjur í einu. En við erum að fara að hunsa þessir lægri röð hugtök, og við erum bara að fara að henda deilum með 2, og bara segja, stór O n fyrir þessi reiknirit eins og heilbrigður. Hvað um þetta? Við munum sleppa yfir sumir af þessum, en það var reiknirit sem var log n? Það tók um það bil log n skrefum? Deilum og sigra. Nákvæmlega. Eins og símaskrá td í viku núll og fyrr í dag, þar sem við skipt vandamál aftur og aftur og aftur. Við dró það á borð í vikunni núll sem boginn græna línu, og við sögðum um daginn að það væri Logarythmiskur reiknirit. Og reyndar, fjölda skref IT tekur að framkvæma skipta og sigra, eða Tvíundarleit eins og við munum byrja kalla það, sem í símaskránni, er á röð þig inn og stíga. Og þetta er hluti af a furðulegur einn. Hvað tekur eitt skref, eða nánar tiltekið stöðug tala af skrefum? Kannski er það tveir, kannski er það þrír, en tölvunarfræðingur bara einfaldar það sem stór O 1, sumir stöðug tala af skrefum. Hvað er eitthvað sem þú gætir gert það tekur stöðugt fjölda skrefum? Hvað er í gangi tími clapping? Constant tíma. Ekki satt? Eins og, hvað er í gangi tími gera eitthvað sem tekur bara einn rekstur, eins prenta F Halló heimur. Það gæti verið sagt að vera stöðug tími, nema minna horn tilfelli Prenta F, hvað gæti hlaupandi tími prenta F raunverulega vera? Og hvers vegna? Hvað er n mæla í því tilviki? Áhorfendur: [inaudible]. DAVID J. Malan: Einmitt. Fjöldi stafa við viljum prenta. Svo er það mjög samhengi næmur. Í dag höfum við verið að einblína mikið á bókstafir og tölur hér á borð. En það gæti líka verið stafir í raunverulegum streng. Svo kemur í ljós að það er annað mælikvarði sem hefst umhyggju um, og það er hið gagnstæða af stór O, svo að segja. Það er ómega tákn. En stór O þýðir hvað er, sem efri mörk keyra þinn tími? Hámarks, hversu mikinn tíma gæti eitthvað taka? Omega-- miður þetta heldur áfram að koma up-- er andstæða þess, þar sem það er neðri mörk á Fjárhæð tíma eitthvað gæti tekið. So. til dæmis, hvað er reiknirit sem tekur alltaf n veldi skref? Jæja, einn af reiknirit sem við höfum séð í dag, í raun, gæti verið þessi eins og heilbrigður. Val tegund. Val tegund er frekar heimskur. Jafnvel þótt algorithm-- miður, jafnvel ef array er þegar raðað, Val tegund er að fara að halda gangandi í gegnum listann að ganga úr skugga um að það hefur minnstu þáttur aftur og aftur og aftur. Og jafnvel þó að þú menn í áhorfendur vita að, bíddu í eina mínútu, þú staðist nú þegar Minnsta þáttur, the tölva veit ekki að fyrr en það lítur alla leið í gegnum listann. Á sama hátt, er lægri mörk sem gæti líka að taka tillit til gæti verið línuleg tími. Hversu mikinn tíma tekur það að raða n þættir í besta Málið nota eitthvað eins og kúla tegund? Segjum listinn er þegar raðað. Við sögðum kúla tegund tekur á röð n veldi skrefum. En hvað ef það er þegar raðað? Hvað ef þér grein eftir einn að fara í gegnum array sem þú hefur ekki gert neinar skiptasamninga? Þarft þú að halda að meira fer? Nei Svo lægri mörk á kúla tegund mætti ​​segja að línuleg. Omega á n. Og við getum litið á aðrir af þessum eins og heilbrigður. Svo skulum taka a fljótur líta á bara visualization hér til að sjá hvernig þetta aðgreina sig. Ég ætla að fara niður hér í þessu síðu sem er í boði á heimasíðu C50 er, en það mun vera a sársauki til að fá að vinna, þar sem það notar tækni sem kallast Java forrit, sem er mestu óstudd þessa dagana, að minnsta kosti með Chrome og tilteknum öðrum. Og láta mig fara á undan og flýta þessu upp og útskýra hvað er að gerast. Þetta er sýning á kúla tegund, fyrsta reiknirit við skoðuðum. Og það er visualization í að hver þessara börum táknar númer. The allstór bar, því stærri númer. Minni á barnum, minni númer. Og það sem þú getur séð sjónrænt, jafnvel en þetta er að fara frábær fljótur, er að rauða bar er eins og mig, ganga fram og til baka ákveða vandamál. Þú getur séð að stærri þætti eru örugglega freyðandi upp til hægri, og smærri þætti eru freyðandi upp til vinstri. Og hérna, ef við í raun líta betur, getum við í raun að telja Fjöldi samanburð og skiptasamninga sem voru gerðar. En í staðinn, við skulum líta á seinni reiknirit við skoðuðum áðan með okkar sjálfboðaliðar, val tagi. Sjónrænt, það hefur a mjög mismunandi áhrif. En það er, aftur, mjög leiðandi, í að við höldum að velja næsta minnstu þáttur, og við fengum smá heppinn. Það fannst í grundvallaratriðum hraðar. En ef við hljóp þetta aftur og aftur og aftur með fullt af inntak, myndum við sjá að það er örugglega enn í stóru O í n veldi. Skulum gera eitt síðasta eitt hér, innsetning flokka, sem var þriðja reiknirit við skoðuðum, og muna að þetta fjallar um þættir eins og það kynni þá, En þá kannski vaktir það yfir til að gera pláss, setja þætti þar sem þeir tilheyra. Og þetta endar líka upp sem gefur Endanleg niðurstaða. Nú öll þrjú af þeim fannst nokkuð hratt. Og reyndar, ég hljóp þá á mjög góðu bút. En í grundvallaratriðum, þeir eru allt nokkuð hræðilegt, að vera heiðarlegur. Öll þessi reiknirit svona langt sem keyra í stóru O á n veldi taka töluvert af tími til að hlaupa í lokin. Og reyndar, getum við séð og finnst þetta loks ef ég draga upp þessa þriðja og síðasta kynningu. Þetta er annar visualization það er að fara að sýna kúla tegund á vinstri val raða í miðju, og eitthvað, eins og einn af okkar hönd vekur fyrr leiðbeinandi, Mergesort á hægri. A skipta og sigra stefnu til hægri. Og það er í raun, hvað við erum fara að horfa á miðvikudaginn. En við skulum tíma þessar til að keyra samhliða. Það er u.þ.b. sama fjölda þætti, allt í gangi á sama tíma. Bubble konar vs val raða vs mergesort. Nú, þeir eru allir hlaupandi í kenningu á sama tíma. The CPU er í gangi á sama hraða, en þú finn hvernig leiðinlegur þetta er mjög fljótt að fara að verða, og hversu hratt þegar við sprauta smá vikunnar reiknirit Zero getur við að hraða hlutum upp. Og nú skulum bera saman þessir í eitt síðasta formi. Ég ætla að fara á undan á vefsvæðið CS50, þar við höfum þetta endanlega tengil fyrir í dag, þar sem einhver á internetinu vinsamlega setja saman vídeó sem fangar hvað mismunandi flokkun reiknirit hljóma. Þetta er innsetning tegund. [Bíphljóð] Þar sem þú ert að sækja um tíðni miðað við hæð bar bar. Þetta er kúla tegund. [Vinda Bíphljóð] Tilkoma upp næsta is-- koma upp næsta is-- val flokka, þar aftur, við erum að velja næsta minnstu þáttur, og við getum séð það vaxa frá vinstri til hægri. Mergesort, sigurvegari okkar svona langt í dag. Taktu eftir hvernig það er að deila hlutum í [inaudible] hálfleik og ársfjórðunga. Gnome tegund, sem við höfum ekki talaði um, og skapar sjónrænt og audally smá a mismunandi lögun og hljóð. Fara fram og til baka, þrífa það upp. Einnig skrá sig út heapsort á vefsíðu Þessi strákur er. Og það er það. Við munum sjá þig næst. [WHOOSHING AND MUSIC]