[Tónlist spila] DAVID J. Malan: Allt í lagi. Svo velkomin aftur. Þetta er CS50, og er í lok viku þrjú. Svo muna á undanförnum vikum, við höfum verið að eyða töluvert af tími á C, á forritun, á setningafræði. Og það er alveg eðlilegt, ef þú ert enn erfiðleikum með Set Vandamál 2, að vera lemja höfðinu við vegg. Það er dulinn-útlit villa skilaboð og galla sem þú getur ekki alveg elta niður. Vegna þess, treyst, að í bara tími nokkurra vikna þú munt líta til baka á hlutir eins keisaranum og [? V-genair,?] kannski jafnvel sprunga, og grein fyrir hversu langt þú hefur komið á stuttum tíma. Þannig að ef það er einhver huggun, hanga í there fyrir nú. Í dag, þó, byrjum við að umskipti að hlutum hærra stig. Og við byrjum að taka sem sjálfsögðum hlut að þú krakkar vita hvernig á að forrita, eða á amk upphaf að þægindi stigi. Og við munum byrja að huga að því hvernig við getum fara um hanna forrit meira á áhrifaríkan hátt. Hvernig getum við farið um hagræðingu í skilvirkni reiknirit okkar, og almennt leysa meira áhugaverðar vandamál. Og byrja að taka sem sjálfsögðum hlut að, ef við vildum, gætum við kóðann upp allir af dæmunum sem við höfum í huga. Svo í dag, höfum við snerta lyklaborðið fyrir hvers konar kóða. Það verður miklu meiri, og lokum, um að leysa vandamál. Svo til að fá að þessu, láttu mig leggja að eftirfarandi sjö ferhyrninga tákna sjö hurðir, bak sem ert a heild búnt af tölur, þar á meðal er fjöldi 50. Leyfðu mér að verkefni þetta á þetta skjár hér eins vel. Og leggja til að við þurfum sjálfboðaliða til að að finna mér númerið fyrir framan Netið hér til að sjá. Komdu upp í bleiku. Allt í lagi. Hvað er nafn þitt? JENNIFER: [inaudible] DAVID J. Malan: Fyrirgefðu? JENNIFER: Jennifer. DAVID J. Malan: Jennifer. Allt í lagi, Jennifer. Gaman að hitta þig. Komdu upp. Svo þetta eru hér sjö hurðir, og hvað Mig langar að gera fyrir okkur hér, framan alla bekkjarfélaga þína, er að finna okkur á númerið 50. Að finna fjölda, getur þú gægjast á bak eitthvað af þessum hurðum með því einfaldlega að slá á einn af the dyr, og það mun sýna númer þess. Og við skulum sjá hversu fljótt þú getur fundið okkur númerið, 50. 15. 16. 50. Fallega gert. Allt í lagi. Umferð lófaklapp fyrir Jennifer. [Applause] Allt í lagi. Svo það var tækni til finna fjölda, 50? JENNIFER: Um, ég hélt kannski ef - [Inaudible] DAVID J. Malan: Oh. Gefa það eina sekúndu. Svo var tækni til finna fjölda, 50? JENNIFER: Svo ég byrja bara á því farin að sjá hvað fyrsta talan var, og þá hugsaði ég, kannski ef þeir raðað, ég bara halda slá ofar? DAVID J. Malan: OK. Og við virðumst hafa fundið að vera raunin. Þó, við skulum afhýða aftur lögin bara svolítið, og þú vilt fara undan og sýna öðrum hurðir þú gætir hafa valið? JENNIFER: Ó, elskan. DAVID J. Malan: Ah. JENNIFER: Svo ég fékk bara heppinn. DAVID J. Malan: Svo þú got heppinn. Allt í lagi. Svo ekki slæmt. En það er áhugavert innsýn, ekki satt? Ef þú ráð fyrir, og þú gerðir fá, reyndar svolítið heppinn þar. En ef þú ráð fyrir að tölurnar væru raðað, getur þú verið nákvæmari um hvernig þessi áhrif hegðun þína? JENNIFER: Svo ef þeir voru raðað, ég hélt kannski minnstu til stærstu. DAVID J. Malan: OK. JENNIFER: Eða ef þetta endaði að vera mjög stór, þá stærsta í minnsta. DAVID J. Malan: OK. Svo stærsta til minnsta, eða minnstu að stærsta. En láttu mig leggja, ráð þú hefðir fengið óheppinn, og gera ráð fyrir að þeir voru ekki í raun, raðað, hversu margir af þær hurðir gætir þú þurft að gægjast bak í því versta tilfelli? JENNIFER: Öll þau. DAVID J. Malan: Öll þau. Svo skulum alhæfa að sem n. Það gerist til að vera 7, en við skulum meira almennt segja að það er n hurðir á skjár hér. Svo í versta tilfelli, myndir þú hafa að líta á bak 7 dyr, eða N dyr. Og svo er þetta virkilega, það er hluti af heppni í dag, en það er mjög línulegt reiknirit konar, jafnvel þótt þú voru konar skipstjóri í kring. Er það sanngjarnt? JENNIFER: Já. DAVID J. Malan: Jæja, láttu mig sjá ef þinn stefnu breytingar ef ég færa okkur til Annað dæmi okkar hér með 7 mismunandi hurðir. Sömu tölur, en þetta tíma þeir eru flokkuð. Hvað er tækni hér að fara að vera, reyna að setja út af huga þínum hvað aðrar tölur voru - JENNIFER: OK. DAVID J. Malan: - fyrr? JENNIFER: Byrjum með the fyrstur einn. DAVID J. Malan: Allt í lagi. Byrja með fyrsta. 4.. Nú þar sem þú að fara að fara, og hvers vegna? JENNIFER: 4 er í raun lítil. Svo ef þeir eru svona kannski minnstu til stærsta, ætti það vera tvisvar sinnum að, og -. DAVID J. Malan: OK. Við skulum sjá, sem þér finnst? JENNIFER: Prófaðu það síðasta. Nice. DAVID J. Malan: Mjög fallega gert. Allt í lagi. [Applause] DAVID J. Malan: OK. Svo þú ert í raun að gera þetta hryllilegur, vegna þess að þú ert gera það mjög vel. Sem skilur okkur ekki gera ákveðnar stig. Þannig að við skulum reyna að rúlla aftur hingað. JENNIFER: OK. DAVID J. Malan: Mjög vel gert, engu að síður. Svo þú byrjað frá upphafi, þú sást að það var 4, þá flutti til enda. En geri ráð fyrir að þú did ekki fá heppinn þar, og geri ráð fyrir 50 var eitthvað annað. Hvað þriðja skrefið hafa verið? JENNIFER: Fara til baka í upphafi. DAVID J. Malan: Til baka á byrjun. OK, svo þú hefði snert þetta dyr, sem var 8. Allt í lagi. Svo er það ekki 50. Hvar vilt þú hafa rannsakað næst? JENNIFER: Ef ég gerði ekki vita þeir raðað. DAVID J. Malan: Rétt. Jæja, ef þú did vita þeir voru flokkaður - JENNIFER: Oh, gerði vita, já. DAVID J. Malan: - en þú gerðir ekki vita hvar 50 var enn? JENNIFER: Bara halda áfram. DAVID J. Malan: Allt í lagi. OK. Halda áfram. OK, ég get unnið með. JENNIFER: OK. DAVID J. Malan: Nú, ef þú ert bara að fara að halda áfram, hvað er þitt reiknirit devolving backed inn. JENNIFER: The línuleg -. DAVID J. Malan: Það er góður af línuleg. En láttu mig leggja, láta mér að setja á staðnum. Leyfðu mér að uppfæra síðuna. sama númer, sama fyrirkomulag, sömu dyr. En að hugsa til baka til að fyrsta degi í flokki þegar við reif símaskrá í helmingur, eiginlega, og hvað var stefnu okkar þar? JENNIFER: Byrja á miðju. DAVID J. Malan: OK. Svo byrja á miðju. Svo skulum við fara á undan og gera sér það. Byrja á miðju eftir sýna að dyrunum. Svo talan 16. Svo hvað myndi sterka strákur hefur gert, sem reif símaskrána í tvennt, að fá til the næstur giska? JENNIFER: Go þennan hálfleik. DAVID J. Malan: Og hvers vegna til hægri? JENNIFER: Ef þeir voru svona minnstu til stærsta, þá 50 að vera í því skyni. DAVID J. Malan: Gott. Algerlega sanngjarnt. Svo eins og símaskrá, þú ferð til rétt eins og öfugt við vinstri, en hér er lykillinn takeaway. Þú nú geta henda, eða rífa burt, helmingur af this vandamál, þannig að þú ekki með 7 hurðum, en í raun með bara 3. Sem er u.þ.b. helmingur af stærð vandans. Allt í lagi. Svo nú hvað þú þyrftir gert eftir að þú ferð ekki satt? JENNIFER: Svo 16 er enn nokkuð lítill, miðað við 50, svo kannski ég ætla að reyna, eins, og þessi. DAVID J. Malan: Allt í lagi. 42. Allt í lagi, svo nú er það þín eðlishvöt segja þér? JENNIFER: Ég get henda þetta og þá bara - DAVID J. Malan: OK. Góður, getur þú henda vinstri helmingur þar. JENNIFER: - velja þetta einn. DAVID J. Malan: Og rétt. JENNIFER: Já. DAVID J. Malan: Svo jafnvel þó að það er erfitt að sjá kannski þegar það er aðeins 7 hurðir, hugsa um, nú, The samræmi við Reiknirit þú sótt bara. Í fyrra tilvikinu, en þér heppinn, sem var frábært. En þú gerðir nota leitandi, Ég myndi segja. Þú notaðir konar eðlishvöt þína og vitandi það flokkað, ef það er nokkuð lítil í upphafi, augljóslega, við höfum fékk að fara meira til hægri. En í einhverjum skilningi, þú got heppinn, því kannski var þetta númer 100, og kannski 50 var meira í miðjunni. Kannski 50 var jafnvel hérna. En hvað þú gerðir svolítið öðruvísi í þetta sinn var, gerði þér það sama aftur og aftur. Og ég myndi halda því fram að það sem þú bara gerði, að vísu undir áhrifum frá símanum bók dæmi, er eitthvað mikið meira lausnarleiðar, og margt minna sérstakt cased. Miklu minna instinctive. Svo í lok dagsins, hvernig væri þú lýsa skilvirkni í Fyrsta reiknirit, þar sem þú fórst vinstri til hægri, á móti annað reiknirit hér? JENNIFER: Þessi ætti eins, kannski helminga tímann, eða jafnvel meira, já. DAVID J. Malan: OK, kannski jafnvel meira. Skulum ýta svolítið erfiðara á það. Hvað raunverulega, ef við höldum áfram þessu rökfræði, helming við ákveðið hlaupandi tíma með þessum seinni reiknirit með því að henda burt helmingi tölur, en hvað gerði við gera á næsta endurtekning, þegar Jennifer ljós seinni númer? Við helming tölur dyr aftur. Og þá hvað gerði við gera eftir það, ef voru fleiri dyr til að spila með? Við myndum helminga þá, og aftur, og aftur og aftur. Og þetta var bara eins og ykkur öll standa upp í fyrstu viku flokki, helmingur þú situr niður, helmingur af þú setjast niður, helmingur af þér sitja niður, þar til einn einn sál stóð. Og við sögðum að keyra tími þessi, the tala af skrefum sem það tók var á röð hvað? Ræðumaður 1: [inaudible] DAVID J. Malan: Svo þig stöð 2 af n, eða bara fleiri einfaldlega, skráðu þig á n. Svo eitthvað lógaritmískum. Og línurit var ekki bein lína sem bara verri og verri, það var þetta áhugavert ferill sem ekki fá svo slæmt tímanum. Þannig að við skulum halda í þessa hugmynd. Skulum þakka Jennifer. Takk svo mikið fyrir að koma upp. Og, einn sek. Engar skrifborðið lampar í dag, en við hafa CS50 streitu kúlur. JENNIFER: Yay. DAVID J. Malan: Allt í lagi, hér. Þakka þér fyrir incurring streitu upp hér. Allt í lagi. Svo við skulum sjá hvort við getum ekki núna formlega þetta aðeins meira. Svo aftur, hvað við gerðum var bara í raun það sama og við gerðum í fyrstu viku. En frekar en að enda með bara línuleg reiknirit, sem við lýst áður þar sem þetta beina línu, þar, ef við setjum eitt dyr á á skjánum, þá Jennifer myndi hafa þurft að leita, hugsanlega, bak eitt dyr. Ef við setjum tvær hurðir, gæti hún hafa að líta á bak tveimur hurðum. Og svo var þetta línuleg tengsl milli stærð af því vandamál á, segja, á x-ás og þann tíma sem það tekur að leysa á y. En myndin sem ég var að alluding fyrr var þetta græna línan. Grænt vísvitandi, því það var bara betra. Í orði, reiknirit, þegar við gerðum það með símaskránni, þegar við gerðum það með þið telja hvert annað, og í öðru lagi, þegar Jennifer bara gerði það upp hér, það var svona af grundvallaratriðum betur. Vegna þess að það var ekki bara tvisvar eins hratt. Það var ekki einu sinni fjórum sinnum eins hratt. Það var algjörlega háð því hvað stærð inntak var um hversu mörg skref sem það tók að lokum. Og svo þetta einfalda hugmynd að við tókum öll fyrir veitt með símaskránni, getur sömuleiðis að beita að eitthvað eins og this. Og þetta gæti verið frjálslegur þekktur sem, eins og þú might ímynda sér, deila og sigra. Ekki ólíkt því sem við gerðum, að sjálfsögðu, með símaskránni. En sauðakóðanum, muna, var þetta. Þannig að við munum ekki gera þetta aftur, en muna að fyrstu vikuna, allir af okkur stóð upp og þá helmingur þú settist niður, helmingur þú settist niður, helmingur þú settist niður. Að reiknirit var framkvæmd í hluti af a svindla hátt, í því, það var bara ein af mér ekki að telja, grundvallaratriðum, skilvirkari. Í því tilviki var ég að fá meira annar auðlind. Konar, margfeldi örgjörva, margar gáfur, margfeldi sviði fólk í herbergi voru að hjálpa mér að fá frá einhverju línuleg eitthvað lógaritmískum, frá einhverju rauður að eitthvað grænt. En í þessu tilfelli, Jennifer einn getur grundvallaratriðum bæta við að Afkoma fyrsta reiknirit hennar með, aftur, bara að hugsa svolítið erfiðara. Og nú, þegar það kemur tími til að framkvæma þetta, vangaveltur út hvaða línur af kóða sem þú getur skrifað svo sem þú getur endurtaka þá aftur, og aftur, og aftur, svona í lykkja tísku. Þar sem þú ert ekki að fara að hafa lúxus, eins Jennifer gerði í fyrstu, að bara hafa a heild búnt af IFS og segja, Hmm, ef þetta fyrsta númerið er 4, láta mig hoppa alla leið til enda. Ooh, ef þessi tala er of stór, láta mig fara geðþótta aftur til seinni frumefni. Þú munt komast að því að það er að fara til vera a einhver fjöldi erfiðara að móta það sem við mennirnir taka sem sjálfsögðum hlut sem mjög sanngjarnt leitandi, en tölvan er aðeins að fara að gera það sem þú segir það að gera. Nú hefur þetta mjög áhugavert afleiðingar. Þetta línurit er tegund af ætlað að raða á gagntaka sjónrænt, en tilkynning þar er bein lína í þessu grafi? Hvar er línuleg línurit sem við köllum n? Jæja, það er tegund af í átt að botn þessa mynd, ekki satt? Svo allt sem við höfum gert er að við höfum konar aðdregna út til x-ásnum og Y-ásinn til að reyna að fá tilfinningu fyrir því hvað aðrar gerðir af bugða líta út. Og the sérstakur af the stærðfræði tjáning í dag mun ekki máli svo mikið, en eftir þessi there er a einhver fjöldi af reiknirit sem eru miklu verra en eitthvað sem er línuleg. Reyndar n cubed lítur ansi slæmt. 2 til n lítur ansi slæmt. n ferningur lítur ansi slæmt. Og við munum sjá hvað sumir af þeim gæti verið í raun í dag. Og log n ekki finnst eins slæmt, en betri en n er Log stöð 2 á n. En þú veist, það hefði verið enn meira ótrúlegt ef Jennifer, eða ef við, að fyrstu vikuna, hafði komið upp með eitthvað sem er log log n. Svo í öðrum orðum, það er þetta allt svið mögulegar lausnir á vandamál, en jafnvel hér, tilkynning hvað er að fara að gerast. Þegar ég súmma út, hver af þessum línur er að fara að sanna til vera the alger verstu sjálfur á skjánum núna? Svo lítur n cubed laglegur slæmt í augnablikinu. En ef við zoom út og sjá meira af x og y-ás, sem er að fara að ráða að lokum? Svo kemur reyndar í ljós að 2 til n, og þú getur fundið þetta út með því að tengja í sumum sífellt stór tölur, og þú munt sjá að 2 við n, reyndar fær stærri miklu hraðar. Ef við zoom raunverulega út, a 2 til n reiknirit sjúga algerlega. Ég meina þetta er að fara að taka alveg smá tíma fyrir tölva til strokkur í gegnum. En þú munt sjá með tímanum, sérstaklega með framtíð setur vandamál og jafnvel lokaverkefni, er gögn þín setja fær stór, allt í lagi? Jafnvel í fyrsta útgáfa af Facebook, sem fjöldi vina, og fjöldi skráðra notenda fékk stór, þú getur flokkað af símanum í samband og framkvæma eitthvað með línulegum leit, eða mjög einfalt flokkun reiknirit, eins og við munum sjá í dag. Þú þarft að byrja að hugsa erfiðara og erfiðara um þessi vandamál. Og tegundir af vandamál stöðum eins Facebook og Google og Microsoft, og aðrir vinna á er einmitt þetta konar stór gögn konar spurningum æ þessa dagana. Allt í lagi. Svo velgengni jennifer í þeirri síðari reiknirit, hreinskilnislega, gerði hún ótrúlega vel í fyrsta skipti, en við skulum skrifa það sem heppni svo að við getur gert þetta atriði. Í seinna tilvikinu, skuldsett hún er reiknirit sem endurtekið aftur og aftur, en hún tók sem sjálfsögðum hlut að víst forsendu að við leyft henni, en hún hagnýtt nokkru nánar annað sinn sem hún hafði ekki fyrsta skipti. Sem var hvað? Að listinn var flokkað. Svo um leið og listinn var raðað, við halda því fram að Jennifer hafi tekist að gera grundvallaratriðum betur. 7 hurðir, já, er þetta ekki áhugavert, en geri ráð fyrir það sem við erum 7 milljónir hurðir. Log n er ákveðið að fara að framkvæma margt, margt hraðar í the langur hlaupa. En hún þurfti að hafa hurðir raðað fyrir hana. Nú, ég tók frelsi til að gera það fyrirfram á tölvuskjá hér, en ætla að Jennifer þurfti að gera það sjálf? Segjum að hurðir að ræða fulltrúa gögn í gagnagrunni, eða vinir skráðir á Facebook eða allir vefsíður á internetinu sem ýmsar vefsíður gætu þurft til vísitölu eða leita á. Segjum sem svo að þú hefðir bara hrár gögn setja og það var eftir að þér, eða að Jennifer að gera þessi flokkun? Það, frekar krefst að við svara spurningin vel, hvernig mikill tími hefði tekið Jennifer, eða jafnvel mig, að raða þær tölur fyrirfram svo að hún gæti farið sér að? Ekki satt? Vegna þess að vísbendingu, að sjálfsögðu, er ef það tekur mig alveg smá stund að raða tölurnar, sem Heck annt um að þú getur fundið fjölda eins 50 svo hratt, eins og í tilfelli Jennifer er, ef við meira en óvart hversu mikið af heildar tíma það tók því að flokka hluti fyrirfram? Svo við skulum sjá hvort við getum ekki mála mynd hér. Ég hafa a heild búnt meiri streitu kúlur, ef það hjálpar brjóta ísinn hér. Og ef þú vilt ekki huga, við þarf sjö sjálfboðaliða - á, OK. Vá. Þannig að við þurfum ekki að eyða á lampa skrifborðið, það virðist. Allt í lagi. Svo hvernig um þig tvær framan. Hvað um þig tveir gaurar í bak. Svo er það fjórir. Hvað um þig í framan fimm, sex og sjö. Þarna. Vinur þinn er að benda þér út, þannig að þú færð verðlaun. Allt í lagi. Komdu upp. Og hvers vegna eigum við ekki að krakkar koma á hérna. Ég ætla að gefa þér hvert númer. Og fara á undan og raða ykkur samur hvað er lýst á skjánum. [INTERPOSING raddir] DAVID J. Malan: OOP, því miður. Bug. Allt í lagi. Jæja, hér við fara. Númer fimm. Númer sex. Einn, tveir, þrír, fjórir, fimm, sex, sjö. Ó, þetta er óþægilega. Ræðumaður 2: Ég verð bara að fá -. DAVID J. Malan: Good deal. Allt í lagi. Þakka þér fyrir að taka þátt. [Applause] OK. Allt í lagi. Þannig að við höfum fjórar, tveir, sex, einn, þrír, sjö, fimm. Perfect þannig að við höfum sjö sjálfboðaliðar hér sem eru jafnir á breidd til array sem við erum að spila með fyrr. Og ég valdi sjö ástæðum sem verður bara þægilegt í smá. Og ég ætla að leggja fyrst að við að raða þessum sjö sjálfboðaliða. Ef þú vilt, fyrst, að segja halló þó. Þar sem þetta er að fara að vera óþægilega nokkrar mínútur. Kynntu ykkur. GRACE: Hæ, ég er Grace. Ég er sophomore í Leverett House. BRANSON: Hæ. Ég er Branson. Ég er að byrja í bræðslu. Gabe: Hæ. Ég er Gabe. Ég er yngri í Cabot. NEIL: Ég er Neil. Ég er að byrja í Matthews. JASON: Ég er Jason. Ég er að byrja í GREENOUGH. MIKE: Ég er Mike. Ég er að byrja í Grays. JESS: Ég er Jess. Ég er sophomore í Leverett. DAVID J. Malan: Excellent. Allt í lagi. Jæja, þakka þér að öllum okkar sjálfboðaliðar hér svona langt. Og áskorun á hönd nú er að fara að vera að raða þessum krakkar, en þá við erum að fara til verða að hugsa smá hart um hvernig á skilvirkan hátt við raun raðað þeim. Þannig að við skulum fyrst reyna þetta. Þú krakkar geta séð tölur hvers annars bara með því að setja í kringum hornum. Fara á undan og taka nokkrar sekúndur, og raða ykkur frá minnstu á vinstri til stærsta hægra megin. Fara. OK. Gott. Það var mjög fjári hratt. Nú einhver hér, hvað var reiknirit að þessir krakkar beitt? Ræðumaður 1: Minnst til mest. DAVID J. Malan: OK. Kosti að mest er í raun raða af Markmið, en ég er ekki viss um að það virkilega reiknirit. Kosti að mestu ekki segja mér skref fyrir skref hvað ég á að gera. Já? Ræðumaður 1: [inaudible] DAVID J. Malan: OK. Svo ef þú sérð mann minni en númer, þá fara til rétt þeirra. Svo það er nú að fá meiri tjáningu, meira eins og reiknirit, vegna þess að þú má segja, ef þetta, þá. Þannig að við höfum einhvers konar skilyrt reisa. Og þessir krakkar virtust gera það nokkrum sinnum, af því að sumir af þú flutt svolítið af fjarlægð. Þannig að það var væntanlega einhvers konar lykkja gerast í huga þeirra. En við skulum reyna að móta það. Ef þú krakkar gætu endurstilla aftur að þetta fyrirkomulag. Við skulum sjá hvort við getum ekki formlega þetta hluti, og þá spyrja, bara Hversu duglegur er þetta? Að sjálfsögðu, þegar við að gera þetta hægar, það er að fara að líða eins gott reiknirit, en við skulum sjá hvort við getum setja fingur okkar á nákvæman vegvísi. Svo þú tveir gaurar eru fjórir og tveir. Eða þú rétt eða rangt röð? Augljóslega rangar. Svo við skipti. Nú ætla ég að fara til hliðar hér og segja, 05:56. Ertu rétt eða rangt? Gabe: Rétt. DAVID J. Malan: Rétt. Sex og einn? Nope. Víxla. Svo er að tveir skiptasamninga. Sex og þremur? Nope. Víxla. Sex og sjö? Lítur vel út. Sjö og fimm? JESS: [inaudible] DAVID J. Malan: OK, skipti. Og raðað. Allt í lagi. Svo augljóslega ekki satt? Þannig að það var meira að fara á. En, reyndar, þessir krakkar, jafnvel bara dragast. hélt að færa. Þeir gerðu ekki bara að hætta, þegar þeir leiðrétta eitt vandamál. Svo. Reyndar er ég að fara að hafa að gera það sama. Ég ætla að hafa til að raða í baka í bak í byrjun þessa vanda, eða í upphafi þessa fjölbreytta fólk, við skulum byrja að kalla þá. Og nú hvað ætti reiknirit mín á annarri umferð vera? Ræðumaður 1: Sami hlutur. DAVID J. Malan: Sami hlutur. Og þetta, ég er farin að eins, ekki satt? Um leið og þú getur fundið sjálfur að gera sama aftur og aftur, það er verða meira eins og reiknirit, og minna manna eðlishvöt. Svo nú, hér við fara aftur. Tvö og fjögur? Nei Four og einn? Ah, það var örugglega einhver vinna enn að gera. Fyrir og þremur? Gott. Fjögur og sex? Sex og fimm? Sex og sjö? OK, nú, lokið. OK, nei. Ég verð að fara til baka. Svo nú, aftur, við erum að gera þetta smá meira af ásettu ráði. Og nú, það er bara einn heili framkvæmd þessa reiknirit. Einn CPU, ef þú vilt. Og hreinskilnislega, það er eina úrræði við erum að fara að hafa aðgang að. Og þegar við förum aftur í lyklaborðið og hafa eitthvað eins og C á okkar förgun, erum við aðeins að skrifa forrit sem getur gert eitt í einu. En þessir krakkar í smá stund síðan, við skuldsett sameiginlega brainpower þeirra eins og þú krakkar gerði í núll viku. Svo skulum halda þessu. Tveggja og einn. Tveir og þrír. Þrír og fjórir. Fjórir og fimm. Fimm og sex. Sex og sjö. Gert? Svo er ég, en láta mig spila djöfulsins talsmaður. Þarf ég, eins konar tölva sem bara gerði fara í gegnum þessa fjölbreytta fólk, veit að ég er búin? Ræðumaður 1: Nei DAVID J. Malan: Svo hvers vegna? Hvað myndi ég þurfa að gera til að álykta afgerandi að ég er að gera? Sennilega eitt framhjá. Ekki satt? Vegna allt sem ég veit af því að fyrri Skarðið er að ég leiðrétta mistök. Og það þýðir, kannski er það enn annar mistök sem ég þarf að leiðrétta. Svo ég get ekki verið viss um trekkja, og þá stöðva, 1-2, tvö og þrír, þrír og fjórir, fjórir og fimm, fimm og sex, sex og sjö. OK, nú ég gerði ekkert verk vinna. Ég get vissulega man að ég gerði ekkert vinna með eitthvað eins breytu, eins við int. Kalla það skiptasamninga, og ef skiptasamninga er 0 þegar ég fá hér, og það byrjaði að minnsta 0, þá Ég vildi bara vera heimskur til að halda áfram fram og til baka, eftirlits aftur, og aftur og aftur, ekki satt? Þar sem þú færð fastur í sumum konar óendanlega lykkju. Svo um leið og það er 0 skiptasamninga, getum við haldið því fram að þetta reiknirit er örugglega lokið. Nú, við skulum setja nafn á þetta. The reiknirit sem ég leggja til við bara framkvæmda er eitthvað sem kallast kúla tegund, þekktur sem slíkur í þeim skilningi að tölurnar sem eru stærri konar kúla leið sína upp á toppinn, eða upp til loka array af tölum. En hvernig duglegur var þetta reiknirit? Hversu mörg skref gerði ég hef líkamlega til Taka, til dæmis, til að raða þeim sjö menn? Fjögur til fimm? OK, of margir á endanum að fara að vera svarið. En jafnvel þá, er tilteknum fjölda er ekki svo áhugavert. Skulum alhæfa það sem n. Svo ef ég hefði n fólk upp hér, og þeir voru, eins konar, af handahófi á að upphafi, í því upprunalega röð. Jæja, hversu mörg skref gerði ég að taka á fyrstu umferð? Það var einn, tveir, þrír, fjórir, fimm, sex, og þeir eru sjö manns, svo það er sjö, sex - svo það er n mínus einn stíga í fyrsta sinn. Nú, hversu mörg skref gerði ég til að taka þegar ég rewound? Jæja, við í raun tvöfalda það ef okkur langaði til, en nú, ég er bara að fara að segja, allt í lagi, annar n mínus 1. Svo n mínus 1 er að fara að fá pirrandi að halda utan um, þannig að við skulum bara umferð upp smávegis. Svo 2n skref. Svo 14 skref, gefa eða taka. Hversu oft gerði ég taka skref næst? Jæja, það er 3n. í raun. Og nú, í versta tilfelli, fyrir dæmi, hversu oft hefði ég farið fram og til baka, fram og til baka, framkvæmd þessa reiknirit, skipta fólk á hverjum skarðið, u.þ.b.? Það er í raun n veldi, ekki satt? Vegna þess að í versta tilfelli, þú getur konar um að hugsa um þetta innsæi, jafnvel þó það gæti tekið smá smá tíma til að sökkva inn Í versta tilfelli, hvað myndi þetta sjö manns hafa litið út, í skilmálum fyrirkomulagi af fjölda þeirra? Alveg afturábak, ekki satt? Og bara til að líkja því, hvað var nafnið þitt aftur? MIKE: Mike. DAVID J. Malan: Mike? OK, Mike, getur þú tekið þátt bara mig yfir hér fyrir bara eina sekúndu? Reyndar ekki. Því miður Mike, baka skulum. Hvað heitirðu aftur? NEIL: Neil. DAVID J. Malan: Neil. OK, Neil, kemur þú með mig, ef þú dont 'hugur. Þannig að ég ætla að leggja til, bara til einfaldleiki, sem Neil er nú í hans versta mögulega tilfelli. En muna hvernig ég innleitt reiknirit mín. Ég er að bera saman, bera saman, bera saman, bera saman, bera saman, oh. Nú þessir krakkar eru út þess, svo ég laga. Svo þú krakkar skipti. En nú íhuga, hversu mikið lengra er Neil að fara? Það er u.þ.b. n. Þú veist, það er í raun ekki n. Það er eins og n mínus 1, en ég er að fá gramur halda utan um litla númer, þannig að við skulum bara kalla það n. Svo ef Neil færist eitt skref hámarks hver tími, og að færa Neil eitt skref, Ég verð að gera þetta virkilega leiðinlegur framhjá fram og til baka, þetta er um það bil að gera þetta, n skref, samtals n sinnum, því það er að fara að taka mig sem margir skref til að fá Neil allt leið þangað sem hann tilheyrir. Hvað þá allir aðrir ef þið voru allir not-röð eins og heilbrigður. Svo skulum kalla kúla konar n ferningur. Rekstur sinn á þessum reiknirit er Árangur af þessum reiknirit er skilvirkni þessarar reiknirit, við munum bara lýsa meira almennt n veldi. Sem er ágætur, vegna þess að ég gæti gert það Sama dæmi með átta manns, níu fólk, milljón manns, og að Svarið er ekki að fara að breytast. Þannig að ef þú krakkar vildi ekki huga, við skulum endurstilla þig þar sem þú byrjaðir. Og við skulum reyna tvær aðrar leiðir og sjá hvort við getum ekki gert grundvallaratriðum betri en þetta. Svo þessar mundir, ætla ég að leggja eins konar mismunandi reiknirit. Það var mjög snjall af okkur síðasta sinn, og þú krakkar voru rétt að hafa rétt eðlishvöt af bara góður að skipta pöruðum. En ef ég vildi virkilega að nálgast þetta einfaldlega, og markmið mitt er að færa öll litlu tölur með þessum hætti, og ýta öllum stóru tölur sem vegur, hví ekki ég bara að í mest barnaleg hátt og sjá hvort ég getur gert betur en það var nokkuð flókið reiknirit? Svo skulum sjá. Fjögur er mjög lítið númer, þannig að ég er fara að yfirgefa þig þar augnablik. Ooh, númer tvö er jafnvel betra. Svo getur þú stíga bara áfram í smástund? Þetta er nú minnsti fjöldi var minn frambjóðandi, og ég ætla að muna að með, eins og breytu. En ég ætla að halda að haka. Er einhver sem tala er minni? Six, nr. Ó, það er Neil aftur. Þannig að ég ætla að ýta þér aftur konar eðli. Neil mun koma fram. Og nú, breytu sem ég nota til að halda utan um sem hefur minnstu tala er uppfærð að innihalda Neil er staðsetning. Jæja, við skulum sjá. Þrír, sjö, fimm. OK, ég veit Neil var minnsti. Hvað er einfaldasta hlutur fyrir mig að gera núna? Ég ætla ekki að sóa tíma mínum með því bara freyðandi Neil einn blettur til vinstri. Hvers vegna get ég ekki sett bara Neil þar sem hann tilheyrir, sem er auðvitað hvar? Alla leið í upphafi. Svo Neil, komdu með mér. Og hvað var nafnið þitt aftur? GRACE: Grace. DAVID J. Malan: Grace. OK. Svo Grace, því miður, þú ert konar í leiðinni. Svo hvernig leysa við þetta vandamál? Ekki satt? Ef þetta er fylki, það er aðeins sjö stöðum. Muna að með Rob, talaði við um lýsa aldri, og við höfðum aðeins endanlegri fjölda aldri? Sama hugmynd hér. Við höfum aðeins endanlega fjölda ints. Grace er góður af í okkar vegur, svo hvernig gætum við? Einfaldasta leiðin er eins, Náð, því miður. Þú ert að fara að þurfa að fara yfir það svo að við getum gert herbergið. Nú, ef þú hugsa um þetta, kannski við gert bara vandamálið verra. Og kannski við gerðum, því hvað ef Náð var á réttum stað? En við vitum að hún er ekki, vegna þess að Annars væri hún hafi verið standa áfram í stað þess að Neil á þessum tíma, ekki satt? Við skoðuðum nú þegar númerið hennar út. Allt í lagi. Svo nú, Neil er á réttum stað, og Ég get gert smá fínstillingu. Fyrir næstu mínútu, ég ætla að hunsa Neil allt saman, svo sem ekki að sóa tíma sínum, eða tilviljun skipta honum á röngum stað. Svo nú, hvernig finn ég næsta þáttur sem er minnst? Tveir. Það er nokkuð gott númer, ef þú vilt að stíga fram og Ég man eftir þér. Sex, ekki gott. Fjórir, þrír, sjö, fimm, ekki gott. Svo láta mig fara að rétti staðurinn þinn. Og við fengum bara heppinn í þetta sinn. Nú ætla ég að hunsa þetta tveir krakkar, og nú gera eitt fara í gegnum þetta. Sex, sem frekar lítið númer. Komdu fram. Ó, fyrirgefðu. Tala Grace er betra, svo stíga á áfram. Fjórir. Því miður, Grace. Fara aftur til baka. Númer þrjú er betri. Sjö. Fimm. Og nú er það nafnið þitt aftur? JASON: Jason. DAVID J. Malan: Jason. Svo er Jason nú minnsti þáttur sem ég hef valið. Hvar er hann að fara að fara? Svo þar sex er. Og nafn þitt er aftur? Gabe: Gabe. DAVID J. Malan: Gabe. Gabe er í leiðinni. Hvað er auðveldast að gera? Skipta þessir tveir gaurar og halda áfram. Svo nú skulum sjá. Hver er minnsti? Fjórir. Leyfðu mér bara svona svindl. Fimm er að fara að vera minnsti. Mér finnst næsta, ef þú vilt að stíga fram, hvað ég þarf að gera við þessir krakkar, með Gabe? Skipta aftur. Svo nú, enn örlítið út af röð. Ég fann Gabe að vera minnsti, svo Ég skjóta honum út, færa ykkur yfir. Og gert. Svo er svarið það sama. The Niðurstaðan er sú sama. Hver af þessum tveimur reiknirit er betra? The second einn, heyrði ég. Hvers vegna? Ræðumaður 3: Það er n skref [inaudible]. DAVID J. Malan: Það er n skrefum á flestum. Áhugavert. Svo er það þó? Svo hvernig did I finna Minnsta þáttur? Hversu mörg skref var ég að taka The finna minnsta stak? Ég hafði að líta alla leið í lok, ekki satt? Vegna þess að í því versta tilfelli, hvað ef Neil voru hérna? Svo bara að finna minnstu þáttur tekur mig n stíga, eða N mínus 1. En, OK. Svo gætum Neil. Mundu að eina mínútu eða svo síðan. En hvernig gerði ég finna næsta Minnsta þáttur? Það er n mínus 1, eða n mínus 2 í raun, frá fjölda af skrefum. Svo OK. Svo ég gerði n mínus 2. Allt í lagi. Svo finnst svolítið betur. Allt í lagi. Hversu margir stíga næst að finna númer þrjú? Svo n mínus 4. Svo það er minnkandi, eitt færri stíga á hverri ítrun. Þannig að þetta er líða betur, ekki satt? Ef síðasta tíma var u.þ.b. n sinnum n, í þetta sinn það er n mínus 1, auk n mínus 2, auk n mínus 3, ásamt n mínus 4, punktur, punktur, punktur. En ef þú manst úr menntaskóla þínum kennslubækur, litli svindlari blaði á bak sem hefur formúlur, ef þú bæta upp þessa röð af tölum, hvað er heildarfjöldi skrefum að fara að vera að ég taka hér? Þetta er einn af þeim, eins og, n mínus 1, sinnum n, deilt með 2. Svo láta mig sjá hvort ég get draga þetta upp fyrir réttlátur a augnablik. Og aftur, ég konar námundun sumir tölur bara til að halda líf okkar einfalt, en eins og ég man, það er eitthvað eins og ef Ég gera N mínus 1 hluti, þá n mínus 2, þá er n mínus 3, það er um það bil eitthvað eins og þetta yfir 2, og ef ég margfalda þetta út, það er reyndar n ferningur. Það er ekki tilfinning of gott. n mínus n yfir 2. En hér er málið. Í tölvunarfræði, þegar erfiðleikar byrja að fá áhugavert er þegar n fær mjög stór. Og þegar n fær mjög stór, sem af þessi gildi er að fara að ráða öllu af öðrum? Það er góður af n veldi, ekki satt? Já, deila með 2 er nokkuð góð. En ef þú ert að tala um milljarða stykki af gögnum eða Trillions stykki af gögnum, í lagi, svo þú ert tvisvar eins hratt. En hver blíðuhót í raun ef að stór tala, ef þessi þáttur er það sem fær stærri og stærri. Og vissulega gerir það meira af munur en þetta strákur. Svo jafnvel þótt þú krakkar eru rétt, Annað reiknirit, munum við kalla það Val tagi, er í hinum raunverulega heimi, sem hluti hraðar hugsanlega, því ég er taka færri og færri skref í hvert skipti. Það er í raun ekki í grundvallaratriðum hraðar. Vegna þess að ef við spilum reyndar þetta út fyrir stór gildi n, í lok daginn, að nógu stór n, er það enn að fara að finna nokkuð hægur. Jæja, láttu mig taka einn síðustu umferð á þeim. Það er það sem ég myndi kalla val konar. Getur þú krakkar endurstilla ykkur eitt síðasta skipti? Og í þessu síðasta tilfelli, ég er að fara að leggja eitthvað kallað innsetningu konar. Innsetning konar vera, eðli, svolítið öðruvísi. Frekar en að fara fram og til baka og velja minnstu frumefni, ég bara að fara að takast á við hvert þessara krakkar sem ég lenda þeim, og settu þá í rétta stað þeirra. Þannig að ég ætla bara að fara að byrja með Grace, og ég sé að hún er númer fjögur. Hvar er númer fjögur tilheyra? Ég hef ekki byrjað flokkun neitt, svo fær Grace að vera rétt þar. Og nú ætla ég að halda því fram, ef þú gætir taka skref til hægri, þetta raðað minn listi, þetta er minn unsorted eftir lista. Svo nú ætla ég að halda áfram á næsta, og hvað er nafnið þitt aftur? BRANSON: Branson. DAVID J. Malan: Branson. Svo er Branson númer tvö. Þannig að ég ætla að taka þig út í smástund. Og nú, hvar tilheyra þér í þessu fylki? Svo til hægri Grace. Svo aftur, við erum konar að gera Grace gera a einhver fjöldi af vinna hér. Hvar set við þig? Þannig að við erum að fara að renna þér á vinstri, og setja Branson þar. En nú er ég halda því fram að þú krakkar ert. En fyrirvara, ég er ekki að nota auka rúm. Það er samt 2 atriði hér, 5 hérna. Samtals array stærð er 7, þannig að ég er ekki að svindla, allt í lagi? Svo nú höfum við, með Gabe hér, númer sex, þar tilheyrir þú? Þú got heppinn aftur. Þannig að þú færð að vera rétt þar. Bara taka smá skref til hægri bara til að gera ljóst að þú ert flokkað. Og nú höfum við Neil aftur, númer einn, hvar sem þú ferð? Og nú er þar sem við munum byrja að sjá að Þetta reiknirit, þó á fyrsta tillit, finnst nokkuð klár, horfa hvað er að fara að gerast. Ef þú gætir stíga fram. Hvar viljum við setja Neil? Svo augljóslega hér, svo hvernig fáum við Neil þar? Við skulum gera þetta skref-fyrir-skref. Gabe, þar þarft þú að fara? Já, svo taka eitt stórt skref, eða tveimur hálf-skref til að gera eitt skref þarna. Grace, þar sem þú ferð? Gott. Svo annað skref. Og að lokum, Branson? Annað skref. Og nú getum við sett Neil sinn stað. Svo nú, halda áfram þessari rökfræði. Jafnvel þótt við séum ekki að breytast Neil yfir, og aftur, og aftur, að setja hann þar sem hann fer, í versta tilfelli, næsta tala við gætum fundur gæti vera númer, segja, það var númer núll, þá erum við að fara að skipta öllum þessir krakkar. Segjum sem svo að það er tala, neikvæð einn, þá verðum við að skipta allar þessar krakkar. Þannig að við erum í raun bara svona ósvífni vandamálið í kring, þannig að við erum flytja kostnað frá val aðferð svo innsetning ferli, þannig að þið bara haft að færa það bil n mínus eitthvað fjölda af skrefum. Og þessi tala af skrefum er bara að fara að auka eins og ég að velja fleiri tölur, ef ég þarf að hafa ýting ykkur aftur, og aftur, og aftur. Svo er sorglegt hlutur nú allar þessar reiknirit eru n ferningur. Við skulum fara á undan og þökk sé þeim krakkar, og sjón þessar svolítið öðruvísi. Mjög vel gert. [Applause] Allt í lagi. Þar sem þú ferð. Takk fyrir - BRANSON: [inaudible] halda tölurnar. DAVID J. Malan: Nei, þú getur halda tölur eins vel. Allt í lagi. Fallega gert. Allt í lagi. Svo skulum sjá hvort við getum ekki nú saman hraðar og meira sjónrænt, nákvæmlega það bara gerðist hér segir. Ég ætla að fara á undan og draga upp Firefox. Við munum tengja þessa kynningu á heimasíðu námskeiðsins er. Java er dálítið pirrandi að fá að vinna í sumum vöfrum þessa dagana. Svo ef þú spilar með þetta heima, grein fyrir að þú gætir þurft að nota Firefox til að fá það að virka. Og það sem ég ætla að gera við þetta Sýnt hefur verið fram er eftirfarandi. Neðst, ég er með allt fullt af valkostir, þar á meðal að byrja og stöðva hnappinn. Einnig, eins og innskot, það virðist vera galla í þessum forritum, þar sem þú getur í raun ekki séð að hefja eða hætta hnappinn nema þú halda Command eða Alt plús og zoom í, sem forvitinn sýnir þér fleiri hnappa. Svo bara FYI ef þú spilar með þetta heima. Nú ætla ég að smella á Start í bara stund, eftir að skilgreina seinkun á, eins, 200 millisekúndur hér, bara svo við getum séð hvað gerist. Svo ég halda því fram að þetta er visualization af fyrsta reiknirit þessir krakkar gerðu, kúla tagi, þar við skipti fólk par-vitur. Lykillinn innsýn í þessa sjónsköpun er að hæð bars táknar stærð tölu. Svo hærri sem stikan er, því stærri númer. Styttra sem stikan er, minni númer. Og ef þú tekur eftir, við erum að fara í gegnum fyrsta endurtekning af þessum reiknirit, skipta stór og lítil númer, þannig að lítill fjöldi kemur fyrst og stór tala fer til hægri. Og um leið og við fáum enda fylking margra fleiri tölur en sjö, við erum að fara að fara aftur til the byrjun. Og sjá þetta. Á lengst til vinstri, þessi litli er að fara að skipta til hliðar, og þetta ferli endurtekur. Nú fær þetta visualization fljótt leiðinlegt, svo láta mig fara á undan og hætta það, breyta tefja eitthvað miklu hraðar bara til að fá nú, tilfinningu fyrir Þetta reiknirit. Svo jafnvel þó að ég hef ferð það upp, þetta er eins og uppfærsla örgjörva minn, kaupa ný tölva. Ég hef ekki breyst minn reiknirit, en þú getur örugglega séð fleiri hætti en með mönnum, að stór númer eru freyðandi upp að ofan, og litlu númer eru vellandi niður á botn. Og nú þetta raðað hér. Og sem innskot, í reitum, það er bara sumir bókhald þar til hjálpa þér að telja hversu margir samanburð, eða hversu margir skiptasamningar hafa reyndar verið gert. Jæja, við skulum reyna einn af hinir sem við sáum. Leyfðu mér að smella á tegund kúla hér, og láta mig velja, og þetta allt vefsíðu er svolítið þrjótur. Skulum taka áhættu og keyra það aftur. Þar við förum. Svo skulum gera val konar. Ég veit ekki hvers vegna valmynd birtist þarna. Skulum zoom í til að laga það padda, breyta þessu í 50. Ah, við skulum raunverulega gera sem mun hraðar. Fimm millisekúndur eða svo, og byrja. Svo er þetta val tagi. Svo aftur, hugsa um hvað við gerði með mönnum upp hér. Við fórum í gegnum fylking og valið minnsti þátturinn aftur, og aftur og aftur. Nú er ég halda því fram að enn var ansi slæmt. Það var samt n veldi, gefa eða taka, en það var, í hinum raunverulega heimi, dálítið hraðar, vegna þess að ég var örugglega að taka örlítið færri skrefum í hvert skipti. En við erum aðeins að tala hvað? Kannski 40 eða svo bars hér? Við erum ekki að tala 40 milljónir. Svo það er ekki alveg ljóst að mér að var örugglega mikil ávinningur. Leyfðu mér að fara nú aftur og breyta til okkar Þriðja algrím, sem var valið innsetning tagi. Og nú er það mjög þrjótur því valmynd í raun ætti ekki að vera þarna niðri. Svo nú að við munum fletta aftur upp hér og byrja þetta reiknirit. Whoop, byrja og hætta. Svo hefur þetta ein tegund af nokkuð mynstur við það, þar sem við erum aftur setja mennina, eða í þetta mál, súlurnar inn viðeigandi staðsetning þeirra. Og það er þegar gert áður Ég snéri. En þessi, of, í orði, er enn n ferningur. Svo skulum sjá hvort við getum ekki saman þetta segir. Ég ætla að fara á undan og bara til að gefa okkur konar sameiginlega leið að tala um þessa hluti, láttu mig kynna bara hluti af merki hér. Þú ert að fara að sjá eitthvað sem kallast stór O, vegna þess að það er bókstaflega a stór O. Og þetta er leið að tölva vísindamaður eða stærðfræðingur jafnvel notar að lýsa hlaupandi tími einhvers reiknirit. Hversu mörg skref tekur það í raun? Nú ætla ég að niðurlægja mig með rithönd mín hér í bara smá stund. En láta mig fara á undan og segja að þetta mun vera stór O hérna. Og láttu mig kynna eitt annað tákn, höfuðborg Omega. Omega er að fara að vera á móti, meginatriðum, af stór O. teknu tilliti til eftirfarandi stór O þýðir, í versta tilfelli, hversu mikinn tíma gæti einhver reiknirit taka, í hugtök af N, ómega er að fara að vera hversu mikinn tíma gæti það taka í besta tilfelli. Og við munum sjá hvað er átt við með besta mál í aðeins augnablik. Svo skulum byrja eitthvað einfalt. Leyfðu mér að byrja með línulegri leit. Svo ekki flokka. Við munum kalla þetta línulega leit. Og nú, gera a lítill borð út af þessu. Og nú, að því er varðar línuleg leit, í versta tilfelli, hversu mörg skref er það að fara að taka mig til að finna fjöldi handahófi val? Og það er n samtals hurðir eða n heildarfjölda. Versta tilfelli. Hversu mörg skref er ég að fara að hafa til að taka til að finna númerið 50 í fylki af n dyr? Og hvers vegna? Vegna þess að það gæti verið allt leið yfir á endanum. Svo mikið eins Jennifer fundur, sem númer 50 var alla leið yfir, svo í versta tilfelli línuleg leit er stór O n, munum við segja. Hvað um besta tilfelli, ef þú færð virkilega heppinn? Það er bara að fara að taka eitt skref, eða stöðug tala af skrefum. Þannig að við munum lýsa það sem 1. Þannig að þetta er nokkuð gott. Nú hvað ef við gerðum eitthvað eins tvöfaldur leit? Svo tvöfaldur leit, í versta málið, tók hversu mikinn tíma? [INTERPOSING raddir] DAVID J. Malan: Svo í raun, ég heyrði það í nokkra staði. Svo það er í raun log n, gefa eða taka, því eins og við skipta lista í tvennt aftur, og aftur, og aftur, við erum fær að finna, að lokum, gildi, ef það er þarna, en það er a grípa. Hvað er ráð fyrir að við verðum að taka sem sjálfsögðum hlut að tvöfaldur leit? Það þarf að vera flokkaður. Það er ekki raðað, þú geta kljúfa málið í helmingur aftur og aftur, og þú getur farið til vinstri, og þú getur farið til hægri og þú getur farið til vinstri og hægri, en þú ert ekki að fara að finna stak ef listinn er ekki raðað því þú gætir missa það. Vegna leitandi þinni, fyrir að fara til vinstri eða hægri er að fara til að vera gölluð ef hún er örugglega ekki raðað. Svo er það eins konar falinn kostnaður að nota eitthvað eins og this. Nú, við skulum fara inn í flokka okkar reiknirit leita ekki - ó, reyndar skulum fara í þetta eftir autt. Binary leita í besta tilfelli? Það er líka 1 ef það gerist bara til að vera í mjög miðju í fylkinu, eða um miðja símaskránni. Nú skulum gera kúla konar. Svo aftur, nú erum við að slá inn konar, en ekki leit. Í versta tilfelli, hversu mörg skref gerði við krafa kúla tegund er að fara að taka? n veldi. Þannig að ég ætla að teikna það. Ooh, rithönd mín lítur jafnvel verri þegar það er spáð að stór. Allt í lagi. Svo það er n ferningur. Og í besta tilfelli konar kúla, hversu mörg skref er það að fara að taka? 1, heyrði ég. Ræðumaður 1: n. DAVID J. Malan: n, heyrði ég. Ræðumaður 1: 2. DAVID J. Malan: 2, ég heyrði. Ég heyri 3? Allt í lagi. Svo ég hef heyrt 1, n, 2, en við skulum velja í sundur að minnsta kosti fyrsta af þeim sem tillögur, 1. Það er ekki slæm eðlishvöt, vegna þess að það konar fylgir munstur. En ef það tekur bara 1 skref, hvernig í Heimurinn gæti ég halda því fram að listinn er raðað, því ef ég er aðeins leyft að taka 1 skref, hvernig margir þættir gæti ég athuga reyndar að vera viss? Jæja, bara 1, sem þýðir að það er n mínus 1 atriði sem gæti verið út af röð, og ég ætla bara að fara á trú eftir horfa á 1. þáttur sem hlutur er raðað. Svo 1 er ekki rétt hér. Svo lítið, hversu margir þarf ég að horfa á? [INTERPOSING raddir] DAVID J. Malan: n mínus 1, eða í raun, n, því að ég þarf að horfa á hverju þáttur til að tryggja að það er ekki út af röð. En aftur, munum við raða á öldu okkar hendur á smærri tölur og ráð fyrir að, eins og n fær stór, þeir eru uninteresting samt. Svo er það kúla tegund. Og nú, við skulum gera þessa síðustu tvo. Val tagi, og þá munum við gera innsetningu konar. Og þá munum við blása þinni huga með eitthvað mikið betri en allar þessar. Allt í lagi. Hvað er versta gangi tími konar val? Ræðumaður 4: n ferningur. DAVID J. Malan: n veldi, ég heyra. En hvers vegna n veldi, innsæi? Ræðumaður 4: Þar sem við gerðum bara það. DAVID J. Malan: Vegna þess að við gerðum bara það. OK. Gott svar. En innsæi, hvers vegna er val raða n veldi? Hvað gerði við þurfum að gera aftur og aftur? Við þurftum að halda skönnun í gegnum, eru þú minnstu, þú ert lítill, þú ert minnstu. Og veitt, við varúlfur fær til að taka n skref, þá n mínus 1, þá n mínus 2. En ef þú góður af bæta þeim öllum upp, eða taka það á trú sem ég hef bætt við þá upp fyrirfram, fáum við u.þ.b. n ferningur mínus sumum minni tölur. Þannig að ég ætla að kalla þetta n ferningur. En með tegund val á bestu ræða, hversu mörg skref er að fara að taka mig? Ræðumaður 5: [inaudible] DAVID J. Malan: Það er því miður enn n veldi, ekki satt? Vegna þess að ef ég er að velja minnstu þáttur, og við höfðum sjö manns hér, Ég veit bara, þegar ég fá til the mjög endir, að ég hef fundið minnstu númer, hvar sem hann eða hún kann að hafa verið. En hvernig finn ég næst minnsti fjöldi? Ég verð að gera aðra sendingu. Svo í besta tilfelli, hvað er inntak í val tagi? Það er nú þegar konar lista, númer eitt, númer tvö, númer þrjú, númer fjögur. En ég er í tölvu. Ég get bara líta á einn hlutur í einu. Ég get ekki raðað af taka skref aftur eins og manneskju og segja: ooh, þetta lítur rétt. Ég get bara dæma réttmæti í val konar með því að velja minnsti fjöldi. En jafnvel ef ég finn númer eitt fyrst, ef ég veit ekki neitt annað um aðrar tölur, sem ég er ekki, allt sem ég veit að ég hef verið afhent fylki eða setja af dyr bak við sem eru tölur, eina leiðin sem ég veit að einn var minnsti? Ef ég fæ alla leið hingað og átta, fjandinn, var einn örugglega minnstu. En hvernig ég ákveða þá tveir er næsta lítill? Með því að gera slíkt hið sama óhagkvæmni aftur og aftur. Svo að lokum, með Innsetningarröðun, hvernig, í versta tilfelli, gerði við segjum það virkar? Það of er n ferningur. Og hvernig óður með besta tilfelli? Við munum fara að sem cliffhanger. Við munum fylla í þessi auða næst, en fyrst láta mig leggja til að við grundvallaratriðum gera betur en allt þetta, allt í lagi? Svo hugsa fyrir sjálfan þig hvað innsetning tegund er að fara til vera. Jæja, það var ekki mjög dramatísk, því að ég er sú eina sem sá breytinguna. Vá. OK. Svo hér höfum við nokkuð mismunandi sýning. Ef ég zoom í hér, munt þú sjá að á vinstri við höfum kúla tegund, í miðja höfum val konar, og á lengst til hægri, höfum við eitthvað við hafa ekki horft á enn kallað sameinast einhverskonar. En íhuga hvað við höfum verið gera hér svona langt í dag. Þegar Jennifer kom fyrst upp á sviðinu, við fórum í gegnum array af tölum aftur og aftur, með línulegri leit, og við fengum línuleg hlaupandi tími, stór O af n, svo að segja. Þegar við lítum nú í fyrstu viku flokki, þegar við höfðum skipta og sigra, og við höfðum símaskrá ofsafenginn, og Jennifer, og við sameiginlega skuldsett að lykill innsýn, sem var að endurtaka þig aftur og aftur með því einhvern veginn að henda burt, hent, hent, helmingur af the vandamál, eða almennt, deila vandamál í tvennt, og þá meðhöndla minni stykki af vandamálið sem eðli jafngildi til annarra, við fengum einhvern veginn grundvallaratriðum betur. En með tegund kúla, með val tegund, með Innsetningarröðun, höfum við getur engar slíkar innsýn sem Jennifer gerði. Við nánast bara gekk aftur og fram a heild búnt af sinnum, og við klip það svolítið, skipta í þessari röð, ef til vill setja eða velja. En í lok dagsins, ég gerði mikið af óþægilega göngu fram og til baka. Við gerðum í raun ekki skiptimynt eitthvað Smart eins Jennifer gerði eins deila og sigra. Svo sameinast raða, hins, sem við mun ekki sjá fyrr en í næstu viku, það er að fara að nýta sem lykill hugmynd með því að deila inntak, og þá halving, og þá halving, og þá halving. Og á hverjum endurtekning þeirrar lykkju, flokkun vinstri helming, og rétt helming, þá vinstri helmingur af vinstri helming, og rétt helmingur af the vinstri, þá vinstri helmingur af hægri hluta, og rétt helmingur af hægri helming. Og endurtaka aftur og aftur. Svo þú munt sjá þetta sjónrænt, en þetta er það sem bíður okkar í næstu viku. Og almennt, þegar við hugsum lítið svolítið erfiðara á slíkum vanda. Við höfum n ferningur til vinstri, n veldi í miðju, og n log n til hægri. Svo er það alvöru cliffhanger þinn. Við munum sjá þig á mánudaginn. [Applause]