Ræðumaður: Allt í lagi, þetta er CS50. Þetta er endir viku þrjú, og ef þú hefur ekki nýtt sér nú þegar, veit að það mun vera hádegismatur á föstudaginn eins og venjulega, þar þú getur notið góða hegðun og mat á Fire og Ice með nokkrum af CS50 er starfsfólk og bekkjarfélaga. Höfuð á þessa slóð hér. Nú getur þú muna, eða þú gæti brátt að kynnast, þetta hér, sem eru gefin út í lok á önn fyrir mörgum bekkjum. Svokallaða exam bláa bækur, sem þú skrifar svörin við prófum. Nú hef ég hér 26 slík blár bækur, á hver þeirra er skrifað nafn, A í gegnum Z. Og örugglega nöfn eru svo einfalt, A gegnum Z. Og einn af markmið á hendi í dag er að fara að vera að halda áfram hvað við byrjuðum á mánudaginn, sem er ekki svo mikið að horfa á kóða, en í raun horfa á hugmyndum og leysa vandamál. Eitt af markmiðum og loforð þetta námskeið er að kenna þér að hugsa meira vandlega, meira skipulega, og til að leysa vandamál á skilvirkari hátt. Og reyndar, við getum gert það í raun án þess þó að snerta línu af kóða. Svo ég hafa a par af fílum upp hér í dag, appelsínugult og blátt, ef við gætum fengið einn sjálfboðaliða, kannski frá lengra aftur en venjulega. Hvernig væri rétt þar, koma niður. Markmið sem er að fara að vera að hjálpa plús gefa þessu prófi hér. Hvað er nafn þitt? Áhorfendur: Mary Beth. Ræðumaður: María Beth, koma upp. Leyfðu mér að fá hljóðnemann hér fyrir þig. Gaman að hitta þig. Áhorfendur: Gaman að hitta þig. Ræðumaður: Allt í lagi, þannig að ég hef hér blár bækur A í gegnum Z, og ég ætla að láta sem Ég hef einn af nemendum, og þeir eru að koma í nokkuð af handahófi í lok þriggja klukkustunda próf blokk, svo þeir eru að lenda í sumum hálf-handahófi röð eins og þetta. Nú er starf þitt í réttlátur a augnablik er að fara að be-- þetta er í raun hvernig þeir fá sneri í lok bekknum, líklega. Starf þitt núna er að fara að vera, alveg einfaldlega, að raða þessum bláa bækur fyrir okkur frá A gegnum Z. Áhorfendur: Ó, þetta er að fara að taka að eilífu. Ræðumaður: Og við munum horfa eins og þú gerir þetta, enginn þrýstingur. Áhorfendur: Nei, enginn þrýstingur eða neitt. Ræðumaður: Og til gamans, skulum setja upp teljara. Áhorfendur: Svo mikið gaman, svo mikið gaman. Ræðumaður: Ég get haldið á mic fyrir þig. Allt í lagi, við höfum bara tvöfaldast hraða okkar. Svo í millitíðinni, láta mig sitja hvað er fara að vera spurning fyrir Mary Beth er hvað er hún að gera, hvernig er hún að fara um að leysa þetta? Og í raun, þú might ekki hafa alltaf hugsun um eitthvað svo einfalt eins og þegar þú velur upp 26 bækur eins og þetta, sem hafa náttúrulega panta þá. Hvað er ferlið sem þú notar í raun og veru? Er það nokkuð af handahófi bara tína fyrsta sem þú sérð og setja hana á sinn stað? Ert þú að fara fyrst hendurnar í kring Útlit fyrir þá að leita að B? Ert þú að taka a líta á a par af þeim hlið við hlið og bara segja, bíddu í eina mínútu, þetta er ekki í lagi, og þá skipta um röð? Við sáum þegar á mánudaginn að það er a tala af lifnaðarhættir þar sem við getum gert þetta, og örugglega eins og við undir lok hér, Ég myndi taka mið kannski hvat Mary Beth er að gera. Við höfum nokkrar hrúgur það virðist, er stærri, þrjú smærri. Áhorfendur: Ég panta þá þegar ég finn tvo stafi sem ég veit eru saman í röð, Ég setti þá saman þannig að ég er ekki að hafa áhyggjur óður í gæsla lag af heild röð af bókum. Það er bara, ó, A er fyrst, Ég hef fengið þessa stafla hér. Ræðumaður: Svo, næstum eins og a stykki púsluspil sem hafa rétt form á passa upp með hvert annað. Áhorfendur: Nokkuð mikið, já. Ræðumaður: Allt í lagi, frábært. Og nú hvert af þessum hrúgur er væntanlega raðað? Áhorfendur: Já. Ræðumaður: Allt í lagi, A til Z. All rétt, til hamingju, þú gerðir það. Þú hefur val þitt. Blár? Allt í lagi, þakka þér fyrir það. Svo María Beth gerði leggja hvað nálgun hennar var, en hvað er annar aðferð hvernig þú gæti farið um flokkun þetta? Hvað myndir þú hafa gert? Met að slá hefði verið eina mínútu og 50 eða svo sekúndur, auk þær sem ég gleymdi að telja. Hvað myndir þú hafa gert? Já? Áhorfendur: Taktu stakkur. Byrja frá byrjun. Athugaðu blöð. Og ef efst einn er hærri en kannski eru þeir, botn einn er hærri, þá skipta þær. Ræðumaður: Allt í lagi, svo byrja efst og neðst, og þá vinna leið inn svona, skipta þá? Allt í lagi, þannig að smá svipað í anda þess sem kúla tagi, en velja öfgar ekki eru aðliggjandi pör. En stutt það er að það er vafalaust fullt af mismunandi vegu við gætum gert þetta, og hreinskilnislega, ég held þér svona samþykkt nokkrar aðferðir, ekki satt? Þú lést konar fjórum raðað hrúgur, og þá í raun sameinað þá saman. Og það er, eflaust, annar tækni að öllu leyti. Þú varst ekki að meðhöndla það eins og einn stór stafli, þú skipt vandamál í fjóra quads, ef þú vilt, og þá einhvern veginn sameinaði í lokin. Svo skulum við íhuga, að lokum, hvernig annars gætum gert þetta. Við formlegt hugmynd af kúla röðun síðasta sinn, og kúla raða muna var reiknirit sem við sjáanlegir við átta bekkjarfélaga þína upp hér, virðist af handahófi raðað í fyrstu. Og við ákváðum þá pöruðum, ef tveir þættir eru í ólagi, einfaldlega skipta á þeim. Svo fjögurra og tveir eru augljóslega út af röð, svo þessir tveir bekkjarfélagar skiptu um stöður. Og þá erum við endurtekin með fjórum og sex, átta þá sex og á hverjum endurtekning, flytja til hægri. Svo gefið átta manns, hversu margir pöruðum samanburð gerði ég á meðan gangandi frá vinstri til hægri í einni endurtekning? Hversu margir samanburð? Sjö, ekki satt? Vegna þess að ef það er átta fólk en þú hefur par þá og þú halda áfram einn step til hægri, þú ert ekki að fara að hafa átta samanburður vegna þess að þú getur ekki bera saman þáttur sjálfu sér, eða að það væri bara vera tilgangslaust, þannig að þú hefur sjö. Eða oftast, ef Við höfum n manns, við gera n mínus 1 samanburð með kúla tagi. Svo skulum nú íhuga hversu gott eða slæmur kúla tegund í raun var, og reyna að gefa okkur orðaforða með sem að gagnrýna reiknirit eins og þetta, og brátt okkar eigin. Svo í fyrstu umferð um kúla tagi, í fyrsta sinn Ég gekk frá vinstri til hægri yfir á stigi, tók mig n mínus 1 samanburð. Og það er að fara að vera minn eining mál, ekki satt? Ég var eins konar tala og göngutúrar, nokkuð hratt, nokkuð hægur, svo að telja fjölda mína sekúndum er ekki sérstaklega að segja, en að telja fjölda aðgerðir sem ég gerði á mánudaginn, bera saman tvær manneskjur, sem finnst eins og a ágætur mælieiningu. Svo n mínus 1 skref í fyrsta skipti, en hvað þá gerðist eftir það? Hvað er einn Upside of einu framhjá gegnum annað óflokkuðu lista? Hvað getur þú sagt mér um frumefni sem var alla leið þarna? Já? Það var stærsta þáttur, ekki satt? Númer átta, jafnvel þótt hún byrjaði hér, í hvert skipti sem ég samanborið hana við nágranni, hélt hún freyðandi upp til hægri hönd hlið af listanum. Og reyndar, það er þar sem reiknirit fær nafn sitt. Nú eftir að rökfræði, hversu margir samanburð þarf ég að gera á í annað sinn Ég gera það framhjá frá vinstri til hægri? n mínus 2, ekki satt? Það myndi bara vera að sóa tíma mínum ef ég halda samanburður átta gegn einhverjum annars vegna þess að við vitum nú þegar hún var á réttum stað. Svo er það hluti af óákveðinn greinir í ensku hagræðingu, þannig að næsta umferð er að fara að vera plús n mínus tvö skref, þar sem n er fjöldi fólks. Nú þú getur konar framreikna, jafnvel ef þú ert ekki tölvuna vísindamaður, hvernig þetta endar. Í lok þessa reiknirit, væntanlega þú hafir fengið bara eitt samanburður vinstri. Þú þarft að konar festa farin af listanum ef tveimur og einn eru í ólagi og ætti að vera einn og tveir, þannig að þetta nær lágmarki í auk 1 endanleg samanburður. Nú punktur, punktur, punktur konar bylgjum það er hendur á sumir af the juicier upplýsingar, en við skulum bara fara á undan og einfalda. Ef þú manst úr hár skóla, hreinskilnislega, a einhver fjöldi af þér hafði stærðfræði bækur sem höfðu smá svindl blaði á framhliðinni eða að bakhliðina sem sýndi þér hvað röð summations eins þetta á endanum bætt upp. Í almennu máli, ef þú hafa a breytu eins n, og raunar þetta, ef þú lítur á þinn gamla skólanum stærðfræði bók, þú myndir sjá að þetta í raun bætir upp til þessa upphæð hér, n sinnum n mínus 1 öllum deilt með 2. Svo nú láta mig kveða bara þetta er satt, það á áræðni, það er það sem þetta dregur til, og við gátum sanna að í almennari tilfelli. En nú skulum auka þessa út. Svo skulum margfalda þetta út, svo það er n veldi mínus n, allt deilt með 2. Það er í raun n veldi, deilt með 2, mínus n yfir 2, svo það er allt gott og áhugavert. En hvað gerist ef við nú stinga í gildi? Segjum að ég hafði ekki átta fólk, en segja milljón. Og milljón bara vegna þess að það er ansi stór tala, skulum stinga því inn og sjá hvað gerist. Svo ef ég stinga milljón inn í þessi formúlu Ég ætla að fá milljón ferningur, deilt með 2, mínus milljónir, deilt með 2. Nú hvað er að fara til að jafna? Svo 500 milljarðar, mínus 500.000. Og ef ég geri að stærðfræði út, það þýðir að flokka milljón fólk með kúla tagi gæti tekið mig 499.999.500.000 skref eða samanburður í lokin, við erum bara að framreikna. Það er ansi hægur, en hreinskilnislega mæla einu tilteknu inntak eins og þetta, er ekki allt sem að segja. En reyndar er það benda til þess að eins og n fær stærri og stærri, þetta reiknirit konar finnst verra og verri, eða þú virkilega byrja að finna fyrir sársauka af því exponentiation, að n veldi, sem bætir upp ansi hratt. Og þetta smáatriði er ekki glataður á fólk, í raun nokkur ár síðan ákveðinn þingmaður sem var berjast, settist í viðtal Eiríks Google Schmidt, forstjóri á þeim tíma, og var mótmælt með spurningu mikið eins og við erum að kanna í dag. Við skulum taka a líta. [Vídeó spilun] -Senator, Þú ert hér á Google, og ég eins og að hugsa um formennsku sem atvinnuviðtal. Nú, það er erfitt að fá starf sem forseti, og þú ert að fara í gegnum kuldahrollur núna. Það er líka erfitt að fá vinnu á Google. Við hafa spurningar, og við spyrja frambjóðendur spurninga okkar, og þetta er frá Larry Schwimmer. What-- þú krakkar hugsa ég grínast, það er hér. Hvað er skilvirkasta leiðin til að raða milljón 32-bita heiltölur? -Well-- Ég er hryggur, maybe-- Nei, nei, nei. Ég held að kúla konar væri röng leið til að fara. Svona, sem sagði honum þetta? Ég vissi ekki að sjá tölvuna vísindi í bakgrunn þinn. -We've Fékk njósnara okkar í það. -OK Skulum spyrja aðra viðtal spurning. [END vídeó spilun] Ræðumaður: Svo að tala um sérstakar tölur þó, er ekki að fara að vera allt að gagni. Það er ekki líf kennslustund sem kúla raða, gefið milljón inntak, gæti tekið eins og margir eins og 500 milljarða skrefum. Þú getur í raun ekki alhæfa of hátt frá því og gera góða ákvarðanir hönnun þegar þú skrifar forrit. Svo skulum einbeita þó á hvernig við gætum einfalda þessa niðurstöðu. Þannig að ég hef bent á gulu hér afleiðing n kvaðrat deilt með 2, svo milljón ferningur deilt með 2, og þá Ég hef hápunktur hvað fullkominn svarið var þegar við dregin burt n deilt með 2. Og krafan sem ég ætla að gera núna er sem Heck sama ef þú draga burt smá gamall n yfir 2 þegar fyrsta hluti af þessari jöfnu er svo miklu stærri? Það drottnar hinn Hugtakið, n kvaðrat deilt með 2 er svo miklu stærri, greinilega, eins og n fær stór eins og milljón, það er það í raun mikill munur á lok dags milli 500 milljarða og 499.999.500.000? Ekki í raun. Og svo það sem við erum að fara að gera eins og tölva vísindamenn er hunsa þá lægri röð skilmála og taka eitthvað eins og þetta og í raun bara einfalda það til Hugtakið sem er að fara að máli. Stærri gagnagrunna okkar fá, því stærri gagnagrunna okkar fá, því fleiri vefsíður við verðum að leita að meira vinir sem þú ert með á Facebook. Sem n fær stærra, erum við í raun fara að hugsa um stærsta tíma í slíkum greiningu reiknirit árangur okkar. Og ég ætla að segja, þú veist hvað, kúla tegund er á röð af stór O, á röð af n öðru veldi. Það er ekki nákvæmlega n kvaðrat eins og við höfum séð, en hver raunverulega annt um þá smærri hugtök, og hreinskilnislega, sem raunverulega sama ef við deilum með 2? Það er bara stöðug þáttur. Og er 500 milljarðar á móti 250 milljarða í raun það stór af a samningur? Ég gæti bara bíða eitt ár, láta fartölvuna mína bókstaflega fá tvisvar sinnum eins hratt í vélbúnaði, og þessi tegund af mismunur bara fer í burtu náttúrulega með tímanum. Það sem við þykir vænt um er tjáningu, sá hluti á tjáningu sem er að fara til að vera breytilegur sem inntak okkar fær stærri og stærri. Og reyndar, í hinum raunverulega heimi, það er það sem er að gerast í auknum mæli er inntak á vandamálum okkar og reiknirit eru að fá stærri. Svo stór O er að fara til vera the tákn, sem asymptotic rithátturinn, að vér bara nota sem tölvunarfræðingar að lýsa árangur, eða keyra tíma, af reiknirit. Svo að við getum saman reiknirit á mismunandi tölvum skrifaðar með mismunandi fólki, með því að nota sumir grundvallaratriðum svipuð mæligildi eins og fjölda samanburð sem þú ert gerð, eða kannski fjölda skiptasamninga þú ert að gera. Það sem við erum ekki að fara að Bréfafjöldi er the magn af tími sem fer á klukkuna á vegg venjulega. Það sem við erum ekki að fara að hafa áhyggjur um er hversu mikið minni þú ert að nota í dag á kosti, þó það er annar auðlind sem við gætum mæla. Við ætlum að reyna að byggja greiningu okkar á aðeins helstu aðgerðir, þær, hreinskilnislega, að þú getur séð mest sjónrænt. Svo með eitthvað eins og stór O á n kvaðrat, ég halda því fram að O n veldi er skilgreina efri mörk svokallaða gangi þegar kúla tagi. Með öðrum orðum, ef þú vildi halda því fram að það er þetta efri mörk á hversu margir stíga reiknirit gæti tekið, það er að fara að vera í stóru O á n í öðru veldi í þessu tilfelli, skilgreina efri mörk. Hvað ef ég breyti í stað þess Sagan að vera ekki um kúla tagi, en um þetta efri. Getur þú hugsa um reiknirit að við höfum horft á þegar Hvers efri, hámark mæla tíma eða starfsemi, væri að segja að afmarkast af n, línulegt fall, ekki annars stigs einn sem er boginn? Hvað er reiknirit sem alltaf tekur ekki meira en eins og n skrefum eða 2n skref eða 3N skref? Já? Áhorfendur: Að finna Stærsta talan í listanum? Ræðumaður: Perfect, finna stærsta tala í lista. Ef ég er gefið lista yfir fólk til dæmis, hver sem heldur að tala, hvað er hámarksfjöldi skref ætti að taka mig, nokkuð klár maður, að finna stærsta mann á listanum? n, ekki satt? Vegna þess að í versta tilfelli, þar gæti stærsta gildi vera? Hægri, alla leið á enda. Svo í versta falli efri bundið, gæti ég verða að fara alla leið hérna og vera eins, ó, hér er númer átta, eða hvað sem gildi. Nú það væri bara heimskulegt ef ég hélt að fara, ekki satt? Að leita að fleiri og fleiri þætti ef síðasta af þeim er þarna? Svo örugglega, n er heil efri. Ég þarf ekki að taka fleiri skref en það. Svo hvað ef í staðinn ég lagði til að það eru reiknirit í þessum heimi sem hafa hlaupandi tími sem er afmarkast af stór O frá log n, skráðu þig n? Hvar höfum við séð þetta áður? Já? Áhorfendur: Í símaskrá vandamál? Ræðumaður: Eins og símaskrá vandamál. Hver var mælikvarði á hversu mikill tími eða hversu margir, eyðir það tók mig að finna einhvern eins og Mike Smith í símaskránni? Við krafa það var log n, og jafnvel þótt ókunnur eða það að það er svolítið óljós hvað lógariþma eða veldisvísirinn var, bara muna að log n yfirleitt átt við ferli, í þessu tilfelli, af því að deila eitthvað í tvennt aftur, og aftur, og aftur, og aftur, þannig að það fær sífellt lítill eins og þú gerir það. Svo skráðu þig á n vísar, viss, að símaskránni td til tvöfaldur leit í orði, þegar við hafði raunverulegur dyr á borð, eða þegar Sean var að leita að einhverju. Ef hann hefði notað tvöfaldur leit, skráðu þig n væri efri mörk hversu mikið tími sem tekur. En þessir reiknirit sem hljóp í Annállinn n ráð hvað lykill smáatriði? Að listinn var flokkaður, ekki satt? Reiknirit er rangt ef inntak þitt er ekki raðað, og enn þú ert að nota eitthvað eins og tvöfaldur leit vegna þess að þú gætir hoppað rétt yfir frumefni án þess að átta það er örugglega það. Nú hvað gæti þetta þýtt, stór O í einu? Þetta þýðir ekki að reiknirit þinn tekur einn og aðeins eitt skref, það þýðir bara að það tekur stöðug ýmis skref. Kannski er það 1, kannski er það 10, kannski er það 1000, en það er óháð stærð vandans. Sama hversu stór n er, stöðug tími reiknirit tekur alltaf sama fjölda af skrefum. Svo hvað gæti verið reiknirit Við höfum talað um eða bara innsæi kemur að þér að alltaf rennur í svokölluðu föstu tíma? Já? Áhorfendur: Bæta tvær tölur. Ræðumaður: Bæta tvær tölur, 2 plús 2 er 4, gert. Svo það gæti vinna, hvað annað? Hvernig væri meira alvöru heiminum, já? Áhorfendur: Að finna fyrstur hlutur í listanum. Ræðumaður: Að finna fyrsta þáttur í lista, viss. Við höfum í raun verið að tala um fylki nú þegar, hvernig gera þú fá að minnsta Fyrsta þáttur í fylki, sama hversu lengi array er í C ​​kóða? Þú notar bara eins krappi núll ritháttur, Bam, þú ert þar. Og örugglega fylki, sem til hliðar, Stuðningur eitthvað almennt þekkt eins handahófi aðgang, handahófi aðgang minni, vegna þess að þú getur bókstaflega hoppa til hvaða einum stað. Við getum gert þetta jafnvel meira einfaldlega við getum baka í viku núll þegar við gerðum grunni. Hversu mikill tími fór það að taka fyrir segja blokk í grunni til að framkvæma? Bara stöðug skipti, ekki satt? Segja eitthvað, segja eitthvað, það skiptir ekki máli hversu stór klóra heimurinn er, það er alltaf að fara að taka sama magn af tíma að einfaldlega segja eitthvað. Svo er það stöðug tími, en hvað er bakhlið? Ef það var efri mörk, hvað ef við viljum að lýsa neðri mörk reiknirita okkar hlaupandi tími? Næstum besta mál hugsanlega, ef þú vilt, þó að þessi hugtök gætu sótt að bestu tilvikum verstu tilvikum, meðaltal tilvikum meira almennt, en við skulum bara einblína á lægri mörk almennt. Hvað er reiknirit sem hefur lægri bundinn af n skrefum, eða 2n skref eða 3N skref? Sumir þáttur n skrefum, það er þess neðri. Já? Áhorfendur: Bubble tegund? Ræðumaður: Bubble tegund tekur þú óverulega n skref, hvers vegna? Hvers vegna er það? Hvers vegna ætti að byrja að koma til þín innsæi, jafnvel ef það virkar ekki bara enn? Já? Áhorfendur: [inaudible]. Ræðumaður: Einmitt. Í bestu mögulegu aðstæður á kúla tagi, og mikið af reiknirita, ef ég hendi þér átta manns sem eru nú þegar raðað, það væri heimska fyrir þig, reiknirit, að fara fram og til baka oftar en einu sinni, ekki satt? Því eins fljótt og þú ganga í gegnum listann einu sinni, þú ættir að átta sig á, ó, ég gerði ekkert skiptasamninga, þessi listi er raðað, hætta. En það er að fara að taka þig n skrefum. Og öfugt, hvað er annað hugsun um það? Bubble tegund er ómega, svo að segja, af N, því ef þú lítur á færri en n þætti, hvað er grundvallaratriði þar? Þú veist ekki hvort það er raðað, satt. Við menn gætu litið á átta fólk og vera eins, ó, það er raðað, sem ekki taka mig n skref, en það gerði. Augun, jafnvel þótt þér góður af hafa stóran sjónsvið, þú horft á átta þáttum, þú horft á átta manns, það er átta þrep á áhrifaríkan hátt. Og aðeins ef ég geng í gegnum allt listi ég átta sig á, já, raðað. Ef ég stoppa á miðri leið að hugsa, allir rétt, það er frekar raðað svo langt, hvað eru líkurnar að það er ekki raðað? Að reiknirit ekki að fara að vera rétt. Gæti verið hraðar, en röng. Svo nú höfum við leið lýsa upp lægri mörk, og hvað um föstu tíma? Hvað er reiknirit sem hefur lægri bundið á gengi hennar síðan einn? 1 skref, 2 skref, 10 skref, en fasti, óháð n, stærð inntak? Já, í bakinu. Áhorfendur: printf? Ræðumaður: Hvað er það? Áhorfendur: printf? Ræðumaður: printf. Allt í lagi, viss. Þannig að það tekur ákveðinn fjölda af skrefum. Og ég ætti að now-- nú að við erum að tala um C kóða og ekki Scratch, eitthvað eins segja, með printf, við ættum að byrja að fá varkár. Vegna printf er tekið inntak, það er band, og strengir hafa tæknilega lengd. Svo ef við viljum nú að velja á þig, ef þú dont 'hugur, tæknilega gætum við halda því fram að printf þýðir að taka breytilega lengd inntak, og hlýtur það gæti tekið meira tími til að prenta streng þessu lengi, en þetta lengi. Svo hvað ef við teljum bara flokkun og leita dæmum? Hvað um Mike Smith í símanum bók, eða tvöfaldur leit almennt? Í besta tilfelli, hvað gæti gerst? Ég opna símaskrána og Bam, það er númer Mike Smith. Ég get hringt hann strax. Tók eitt skref, kannski tveimur skrefum, en stöðug tala af skrefum ef ég var heppinn. Og hreinskilnislega, sáum við á Mánudagur bekkjarfélaga þinn fá alveg heppinn tvisvar í röð. Og það var reyndar stöðug tími í neðri mörk á reiknirit sem um ræðir til að finna númer 50 á bak þeim lokað hurðir. Nú, eins og innskot, ef þú uppgötvar að bæði stór O, efri, og ómega, lægri mörk, eru einn á sama, að er það sama uppskrift í svigum, getur þú einnig segja, bara að vera fínt, að eitthvað er í þeta n eða þeta af einhverjum öðrum gildi. Það þýðir bara þegar stór O og omega eru þeir sömu. Hvað um val tagi núna? Við skulum nota þetta nýja orðaforða. Í val tagi, hvað vorum við gera aftur, og aftur, og aftur? Ég var að fara fram og til baka í gegnum lista, leita fyrir hvern? Minnsti fjöldi. Svo hversu margir stíga, hvernig margir samanburð gerði ég að gera í því skyni að reikna út hver minnsti þáttur í listanum var? n mínus 1, ekki satt? Vegna þess að ef ég byrja bara með einn sem ég er gefið og ég byrja að bera saman við honum, þá hann eða hana, hann eða hana, hann eða hana, ég getur aðeins parað þætti saman n mínus 1 sinnum. Svo val tekur tegund álíka n mínus 1 skref í fyrsta skipti. Hversu mörg skref tekur það mig til finna næstminnsta frumefni? n mínus 2, vegna þess að ég er að vera heimsk ef ég halda að horfa á sama fólkið aftur ef ég hef nú þegar valið hann eða hana og setja þá á sinn stað. Og þriðja skrefið, n mínus 3, 4 þá var n mínus. Við höfum séð þetta mynstur áður, og raunar Val tegund álíka hefur skilgreina efri mörk af n kvaðrat ef við gerum upp að samantekt. Hvað er lægri bundinn, val tegund þess? Óverulega, hversu mikill tími verður val raða taka, eins og við skilgreint það á mánudaginn? Leggja til tvo valkosti. Kannski er það n, eins og áður. Kannski er það n veldi, sem það er nú sem efri. Áhorfendur: n veldi. Ræðumaður: n veldi. Hvers vegna? Áhorfendur: Þar sem þú ert að skilgreina [inaudible]. Ræðumaður: Einmitt. Að minnsta kosti eins og ég skilgreint val konar það var nokkuð barnaleg, að halda áfram, finna minnstu frumefni. Fara aftur, finna minnstu frumefni. Fara aftur, finna minnstu frumefni. Það er engin tegund af hagræðingu þar sem gæti látið mig hætta eftir bara n eða svo skref. Svo reyndar, val raða, ómega n veldi. Hvað um Innsetningarröðun, þar sem ég tók sem ég fékk, og þá er ég plopped honum eða hana á réttum stað? Þá er ég gekk til seinni mann, plopped honum á réttum stað. Þá er næsta manneskja, plopped hann eða hana á réttum stað. Takið eftir að þetta er mjög línuleg, svo að segja. Ég er bein lína, ég er ekki að fara fram og til baka, Ég hef aldrei að horfa til baka í raun, en hvað er að gerast þegar ég setja hann eða hana í upphafi listinn sem við gerðum á mánudaginn? Hvað er að gerast? Já? Áhorfendur: [inaudible]. Ræðumaður: Já, að var aflinn, ekki satt? Þú gætir muna úr bekkjarfélagar þínir, ef þeir voru að gera allar hreyfingar með fætur þeirra, sem var aðgerð. Þannig að ef það voru þrjár manneskjur hérna og sem ný manneskja átti leið þarna, á löngu stigi svona viss, hann eða hún gæti bara farið til enda. En ef við erum að hugsa um að tölva og fjölda minni, þetta fólk er að fara að þurfa að stokka yfir að gera pláss fyrir viðkomandi. Og svo að n mínus 1 shufflings, n mínus 2 shufflings, n mínus 3 shufflings er bara svona að gerast fyrir aftan mig, ekki fyrir framan mig eins og áður, í einhverjum skilningi. Nú sem innskot, og eins þú gætir hafa séð á netinu ef þú byrjar poking í kring um konar, það er svo margar mismunandi sjálfur þarna úti, sumir þeirra betri en aðrir. Reyndar, bogosort er einn það er góður af gaman að horfa upp. Bogosort tekur mengi númer eða segja spilastokk, stokkar þau og eftirlit ef þeir eru raðað. Og ef ekki, er það aftur. Og ef ekki, er það aftur. Ef ekki, er það aftur. Ótrúlega heimskulegt. Og reyndar, ef þú lest eins og Wikipedia grein, Gælunafnið hennar er heimskur tegund. Það mun að lokum vinna, vonandi, gefinn nægur tími, en það magn af tími gæti tekið þó nokkurn tíma. Svo ef ég gæti, við skulum hraða hlutum upp úr td Mary Beth fyrr, með því að hafa nokkur fleiri atriði, en tvo örgjörva. Tveir menn, ef þér myndi ekki hug að taka þátt mér. Hvernig um 1 hérna, og skulum go-- enginn þarna? Enginn þarna? OK. Þú með svarta skyrta, já, komdu niður. Allt í lagi, hvað er nafnið þitt? Áhorfendur: Pétur. Ræðumaður: Hvað er það? Áhorfendur: Pétur. Ræðumaður: Pétur, Davíð, gaman að hitta þig. Allt í lagi, við höfum Pétur hér, ef þú vil koma inn á borð hérna. Og hvað er nafnið þitt? Áhorfendur: Elena. Ræðumaður: Elena. Allt í lagi, gaman að hitta þig. Elena hitta Pétur. Pétur, Elena. Og við þurfum Andrési upp hér eins og heilbrigður, vinsamlegast. Og áskorun er að fara að vera að raða spilastokk. Og ef ókunnur, þilfari af kortum ætti að lokum vera flokkaður smá eitthvað eins þetta þar sem við munum gera klúbba, þá sem spaða, þá hjörtu og demöntum, frá Ás sem einn, alla leið upp að konungi. Spilin sem ég ætla að gefa þér eru að fara að vera 52 í magni. Við erum að fara að álíka tími þig, á aðeins augnablik. Við erum að fara að henda Andrew upp á skjánum hér, svo sem að horfa á eins og þú gerir þetta. Og svo að öll þessi er allt meira áberandi, þetta eru spil sem ég fékk á Amazon. Svo þeir eru nú þegar af handahófi raðað, og við erum að fara að tíma þig. Og við erum að fara að halda það raunverulegt í þetta sinn, þannig að við erum að fara að reyna að þrýstingur þig því annars mun þetta fá leiðinlegur fljótt. Ef þú gætir haldið áfram að raða 52 þættir saman í gegnum sumir hætti, núna. Og aftur, eins og við horfa þær krakkar gera hvað, í lok er að fara að framleiða augljós Niðurstaðan, hugsa um raunverulega hvernig þeir eru á hverjum að gera það, hvernig þú gætir lýst því. Því aftur, þetta eru allt ferli, reiknirit að við tökum sem sjálfsögðum hlut eins og mönnum. En þú hefur sennilega lengi haft innsæi, löngu áður en þú jafnvel hugsað um að taka upp tölvunarfræði bekknum þér gæti hafa haft innsæi með sem til að leysa vandamál eins og þetta. En þegar þú kannast mynstrin og byrja að formlega skrefin sem þú ert að leysa þessi vandamál, þú munt finna að þú getur leyst mikið áhugaverðari og miklu flóknari vandamál fljótt. Svo, hvað er einhver frá áhorfendum að minnsta kosti einn þáttur í reiknirit að þeir eru að nota hérna? Áhorfendur: [inaudible] Ræðumaður: Hvað er það? Áhorfendur: Með föt. Ræðumaður: Eftir föt. Svo fyrst þeir eru Þyrping allar demöntum saman það virðist, allt að hjörtu saman það virðist, og svo framvegis, án þess að því er varðar fyrir tölur um spilin. Og nú eru þeir birtast, til dæmis, að flokka þær eftir fjölda. Mjög gott. Allt í lagi, svo hvað er að fara að vera síðasta skrefið þá hér? Þegar við höfum fjóra flokkuð föt, hvað þurfum við að gera til fjögurra hrúgur í því skyni að ná fram einn raðað þilfari, einfaldlega? Þannig að við þurfum að sameinast þeim aftur. Svo er það áhugavert hugmynd að aftur, eflaust, er mjög leiðandi, jafnvel ef þú gætir aldrei hafa löðrungur þannig merki á það. Þessi grundvallaratriði hugmynd að deila vandamálið ekki í hálfan þessum tíma, en að minnsta kosti í fjóra hluta. Solving ansi mikið grundvallaratriðum samhljóða vandamál í einangrun á hvern annan, og þá sameina niðurstöður. Og frábært, gert. Allt í lagi, stór kringlótt af lófaklapp, ef við gátum. [Applause] Ræðumaður: Ég hef ekki hugmynd um hvað þú munt gera með þetta, en hér þú fara. Þakka þér svo mikið. Svo skulum sjá, tvær mínútur og átta sekúndur, ef þú vilt áskorun vinum þínum. Hvað þá er að fara að vera tekið í burtu frá þessu að við getum skiptimynt almennt? Jæja, hugsa aftur til þetta fylki af tölum, og hugsa til baka núna til sumir af the sauðakóðanum við höfum skrifað í fortíðinni, og þetta var sauðakóðanum fyrir leysa símaskrá vandamál. Þar í sauðakóðanum I talin meiri methodical hátt að lýsa hvernig ég gerði mjög leiðandi manna reiknirit deila símann bók í tvennt, endurtaka, endurtaka, endurtaka, þar til ég finna einhvern eins og Mike Smith, ef hann er örugglega í símaskránni. En ég nota svona sem ég ætla að hringja mjög endurtekningu nálgun hér, einkum fyrirvara línu 8 og lína 11. Þeir eru vísbendingar um endurtekningu nálgun, a lykkja nálgun, því það er einmitt hegðun sem þeir framkalla. Þeir línur bæði segja að fara til lína þrír, og þú getur konar hugsa um það í þínum auga hugans eins og að vera lykkja. Það er að segja þér að fara aftur upp að stíga þrír og endurtaka aftur og aftur, og aftur. En hvað ef við nýta á takka hugmynd hér að við gerðum ekki í síðasta sinn, og einfalda línu 8 og lína 11 og nágrannar þeirra eins og bara þetta, í gulum. Það er ekki í grundvallaratriðum að stytta að sauðakóðanum mjög mikið, en það er í grundvallaratriðum að breyta eðli reiknirit mitt. Það sem ég er nú að segja í skrefi 7, í skrefi 10, er að leita að Mike í nákvæmlega sama hátt, en bara í vinstri helmingur eða hægri helminginn. Svo í öðrum orðum, ef Ég byrja frá skrefi eitt, taka upp símaskrána opin miðju af símaskránni líta á nöfn, ef Smith er meðal nafn er, kalla Mike, annars ef Smith er fyrr í bókinni, stíga sjö leita Mike í vinstri hluta bókarinnar. En þannig er eins það er afgangur mig hangandi, ekki satt? Í gulum, er kennsla, en hvernig geri ég leita Mike í vinstri helmingur símaskránni? Hvar fæ ég að reiknirit sem ég Hægt er að leita að einhverjum eins Mike Smith? Jæja, það er starandi okkur í andlitið. Ég get bókstaflega notað nákvæmlega sama program í raun að fara upp á toppinn aftur og aftur hlaupandi sömu línur af kóða. Svo jafnvel þótt þetta ætti að líða eins og a hluti af a cyclical skilgreiningu þar sem þú ert að svara einhverjum er spurning bara með svona spyrja sama spurning aftur, eins hvers vegna, hvers vegna, hvers vegna? Staðreyndin er sú að við höfum harður á dulmáli a par af sérstökum línum, skref 4, sem er ef, og skref 12, þar sem er í raun önnur útibú, vegna þess að við höfum þá stopgap ráðstafanir, þetta reiknirit mun segja ef við finna Mike, eða ef við gerum það ekki. En í skrefi 7 og 10 núna, höfum við það sem við munum kalla endurkvæma reiknirit. Og endurkvæmni er örugglega öflugur hugmynd það er smá hugur beygja í fyrstu, að við getum nú sótt þannig. Sameina raða verður síðasta tegund sem við líta á, að minnsta kosti í flokki formlega. Og það er í grundvallaratriðum öðruvísi frá þeim síðustu þremur, og vissulega síðustu fjórum, ef við eru bogosort. Hér er sauðakóðanum fyrir sameiningu tagi. Þegar um inntak n þáttum, svo gefið fylki af stærð n, ef n er minna en 2, aftur. Svo hvers vegna þarf ég að geðheilbrigði athuga fyrst? Hvað er óbeint ef ég hendi þér fylki sem lengd n er minna en 2? Það er nú þegar raðað, augljóslega, ekki satt? Vegna þess að listi hefur annaðhvort einn þáttur, sem er trivially raðað því það er það eina þar. Eða, er það af stærð núll, sem þýðir það er ekkert til að flokka, svo eðli sínu það er flokkað. Það er bara ekkert rangt þarna. Svo er það svo-kallað stöð mál okkar. Það er svipað í anda að það sem við gerðum með Mike. Ef Mike er í símaskránni, hringja í hann. Ef hann er ekki þarna, gefa upp. Það er svo-kölluð stöð að ræða, að ganga úr skugga um þetta reiknirit í lok dags mun hætta í vissum tilvikum. En hér er áræðni nú, annars, raða vinstri helming þætti, þá raða rétt helmingur af þeim þáttum, og þá sameina raðað helminga. Og hér er þar sem það finnst eins og við erum að copping út. Ég hef beðið þig að raða n þættir, og ég er segja, OK, það með því að flokka vinstri og flokkun rétt. En ég er að segja eitt annar hlutur, og þetta er lykillinn þema virðist í innsæi svona langt, það er þetta þriðja skref að sameina. Sem jafnvel þótt það virðist svo heimsk í anda, eins bara sameinast hluti saman, það virðist að vera mikilvægt skref í átt að reassembly af tveimur vandamálum sem var skipt lokum í tvennt. Svo sameinast konar, við skulum gera þetta, ef þú munt húmor mig, og enn eitt sýnikennslu, bara svo að við höfum sumir tölur til að vinna með. Get ég skipt átta streitu bolta fyrir átta manns? Allt í lagi, hvernig um þig þrír, þú fjórir í þessum kafla, fimm, sex, og við skulum gera 7, 8, koma upp. Allt í lagi, já allt í lagi. Mínus 8, þar sem við komum, plús 1. Excellent. Allt í lagi að koma á þig, við skulum fljótt að gefa þér númer. Númer tvö, númer þrjú, númer fjögur, númer fimm, sex, sjö og átta. Ég gerði átta rétt í þetta sinn. Allt í lagi, þannig að fara á undan, ef þú gætir, og skulum raða í upprunalegu röð að við höfðum í gær, sem leit eins og þetta, ef þú vilt ekki huga. Og við skulum gera það fyrir framan borðið. Allt í lagi, svo sameinast konar. Þetta er þar sem það er að fara að fá eins konar áhugavert, vegna þess að ég virðist vera að gefa mér svo mikið minni upplýsingar í dag. Svo sameinast raða fyrst af öllu á inntak n þáttum, og er augljóslega ekki minna en tveir, það er átta, svo ég hef fengið meiri vinnu til að gera. Svo nú andlega við sem bekknum eru nú í annað útibú, sem þýðir þrjú skref. Fyrst verð ég að raða vinstri helmingur af þeim þáttum. Svo hvernig á ég að fara að gera þetta? Jæja, ég ætla að eins konar andlega skipta lista hér, þú þarft ekki að líkamlega færa, og ég er að fara að einblína á vinstri helmingur af þeim þáttum hér. Svo hvernig get ég farið um flokkun listi nú stærð fjórum? Hvað er algrím mitt? Fyrst ég athuga er n minna en tveir, nei, svo ég sný mér að öðrum blokk aftur. Raða eftir helming þætti. Svo nú aftur, andlega, og þetta er þar þú þarft að safna mikið af andlega sögu, ef þú vilt. Nú er ég að flokka vinstri helmingur af vinstri helming. Allt í lagi, svo nú ég kalla sama sameinast minn flokkun reiknirit, er n minna en tvö? Nei, er það tveir, þannig að ég verð að raða vinstri helming, og hægri helminginn. Svo hér við fara, raða vinstri helming. Hvers vegna ekki þú bara taka eitt skref fram á við. Hvað er nafn þitt? Áhorfendur: Darren. Ræðumaður: Dan. Dan hefur stigið fram. Áhorfendur: Darren. Ræðumaður: Darren, gert. Sagðirðu Darren eða Dan? Áhorfendur: Darren. Ræðumaður: Darren. OK, Darren hefur stigið áfram og hann er nú flokkað. Og þetta er næstum inane krafa, ekki satt? Ég í raun ekki virðast til að vera að ná nokkuð, en við skulum halda áfram. Nú láta mig raða rétt helmingur af þeim þáttum. Hvað er nafn þitt? Áhorfendur: Luke. Ræðumaður: Luke. Komdu, stíga fram. Gert, ég hef raðað Luke. Vinstri helmingur er nú raðað og hægri helminginn er nú raðað, en aftur, það er mikilvægt skref hér. Hvað þarf ég næst að gera? Sameina raðað helminga. Nú erum við að fara að bara að hafa allir fram og til baka á þennan hátt, vegna þess að ég þarf svona sumir klóra pláss. Það er nánast eins og þetta krakkar eru á borð, og ég þarf smá pláss að færa þá í kring á. Þannig að ég ætla að fara að sameinast ykkur eftir að leita á vinstri helming og hægri hluta. Og hver augljóslega kemur fyrst, vinstri helmingur eða hægri helming? Svo hægri helminginn, þannig að við skulum fara Lúkas yfir hér að upprunalega stöðu Darren er. Og nú að sameinast vinstri helming þeirra í, Darren er að fara að flytja þarna. Svo er eins og næstum kúla konar áhrif, en grundvallaratriði reiknirit mitt, mjög mismunandi að þessu sinni. En nú er þar sem hlutirnir fá lítið pirrandi vegna þess að þú þurfa að spóla til baka andlega þar gerði ég fara burt. Ég hef bara sameinuð á flokkuð helminga, sem þýðir að ég er þar í reiknirit mitt? Ég verð að raða rétt helmingur, ekki satt? Ef þú til baka, bókstaflega á vídeó, þú munt sjá að við fengum að þessu benda á Luke og Darren með því að flokka á vinstri helmingur af vinstri helming. Þá erum við sameinuð þeim Raðað helminga, sem þýðir að næsta skref er að raða hægri helminginn af vinstri helming. Allt í lagi, þannig að við skulum gera þetta hraðar. Allt í lagi, sex, ég ætla að halda því þú ert nú raðað, komdu fram. Hvað er nafn þitt? Áhorfendur: Adriano. Ræðumaður: Adriano. Adriano er nú flokkað. Og hvað er nafnið þitt? Áhorfendur: Alex. Ræðumaður: Alex er nú flokkað. Vinstri helmingur, hægri helming, hvað er lokaskrefið? Sameinast. Pretty léttvæg, þannig að ég er að fara að sameinast í sex, taka skref til baka, átta, taka skref til baka. Og nú taka þetta er gagnlegt takeaway, hvað er nú satt um vinstri hluta sem lista, án tillits til þess hvernig við byrjuðum? Það er flokkað. Nú það er ekki raðað í stóra fyrirætlun af hlutur, en það er raðað óháð á hinn helminginn. Nú hvað skref er ég á ef ég halda trekkja hvernig sagan hófst? Nú þarf ég að raða rétt helminginn. Svo nú erum við langt aftur í upphaf sögunnar, og við skulum gera þetta hraðar. Þannig að ég ætla að fara að raða rétt helmingur af öllum listanum. Hvað er næsta skref? Raða vinstri helming hægri helming. Raða vinstri helminginn af vinstri helmingur af the réttur helmingur. Og hvað er nafnið þitt? Áhorfendur: Omar. Ræðumaður: Omar, stíga fram, gert. Vinstri helmingurinn er flokkaður. Og hvað er nafnið þitt? Áhorfendur: Chris. Ræðumaður: Chris, taka skref áfram, þú ert nú flokkað. Hvað er lykillinn skref núna? Sameinast. Svo er að fara að sameinast í stað hér, ef þú gætir tekið skref til baka, og þrír er að fara að taka skref til baka, sameinast. Þannig að vinstri helmingi af hægri helminginn, er nú flokkað. Frankly, þetta reiknirit finnst eins og við eru að sóa hátt meiri tíma en áður, en ef við gerðum þetta í rauntíma, munum við sjá hvað takeaways að fara að vera. Nú hér er ég, rétt helmingur af the réttur helmingur, láta mig fara á undan og raða vinstri helming. Stíga fram, hvað er nafnið þitt? Áhorfendur: Ramsey. Ræðumaður: Ramsey er nú flokkað. Hvað er nafn þitt? Áhorfendur: Marina. Ræðumaður: Marina er nú raðað sem vel, ef þú tekur eitt skref fram á við. Mikilvægt skref hér er nú sameinast, ég er að fara að reyta af tveimur listum mínum, vinstri og hægri. Fimm er að fara að koma fyrst, og sjö er að fara að koma næst. Og aftur, þetta er vísvitandi. Sú staðreynd að þeir eru að taka stígur fram og til baka er ætlað að tákna að við getum ekki gera þetta reiknirit í stað eins auðveldlega eins kúla tagi og val tagi, og insertion sort þar sem við bara haldið swap fólk. Ég þarf bókstaflega eins konar af grunni pappír sem að setja þessar fólkinu á meðan ég gera samruna, og þá get ég sett þá aftur á sinn stað. Og það er lykillinn af því að ég er að nota Ný úrræði, rúm, ekki bara tími. OK, þetta er ótrúlegt. Vinstri helmingurinn er raðað, hægri helminginn er raðað, nú er lykillinn sameina skref. Hvernig er ég að fara að sameina þetta? Þannig að ef þú munt fylgja mínum vinstri hönd og hægri hönd, Ég ætla að benda vinstri hendina á mér á vinstri helming, hægri hönd mín á réttum helming, og nú verð ég að ákveða skref fyrir skref sem á að sameinast í. Sem augljóslega kemur fyrst? Númer eitt. Svo koma á hérna, hér er klóra púði okkar. Svo nú númer eitt, og tilkynningu hvað ég ætla að gera með hægri hendi minni, Ég ætla að flytja mitt hægri hönd einn stíga yfir til að benda númer þrjú, og nú þarf ég að gera sama ákvörðun. Og í raun standa rétt í framan Luke hér ef þú gætir, vegna þess að þetta er klóra púði okkar. Svo sem kemur næst? Við höfum Lúkas með númer tvö eða Chris með númer þrjú. Vitanlega Lúkas, fjöldi tveir, svo þú kemur hingað. En vinstri hönd mín nú er að fara að vera hækkuð að benda á Darren, og hér er lykillinn að taka í burtu með samruna, ég ætla að halda þessu, Vitanlega, ef þú góður af fylgja rökfræði. En hendur mínar eru aldrei að fara aftur á bak, sem þýðir að ég er bara alltaf að flytja til vinstri samrunafélaganna ferli mínum, og það er að fara að vera lykill að Greining okkar á aðeins augnablik. Svo nú skulum klára þetta upp hratt. Svo þremur kemur næst, þá fjögur kemur næst, og nú fimm kemur næst, þá sex, og sjö, og þá loks átta. Líður eins og hægur reiknirit enn, en ekki ef við raunverulega keyra það á sama tagi af klukku hraða, svo að tala, með sömu tifar klukka sem áður. Hvers vegna? Jæja, við skulum taka a líta á the endir afleiðing. Við skulum fara aftur hérna, láttu mig draga upp sýning sjónrænt af því sem við gerðum bara. Zooming í hér, á þessu síðu hér, segja Firefox að við viljum að biðröð upp í þessum kassa, skulum segja kúla konar, sem við erum nú vel kunnugur, Val tegund, sem er annar nokkuð augljóst einn, og nú Mergesort dag, sem verður climactic endir okkar. Ástæðan það tók svo mikið lengur hér með mönnum og mér er munnlega, augljóslega, ég er að útskýra hvert skref. En ef þú framkvæma einfaldlega þetta, mikið eins og við gerðum kúla raða og val raða ekki aðeins sjónrænt, horfa hversu miklu skilvirkari þetta skuldsetning deild og sigra má þegar beitt til a gögnum sem er ekki einu sinni stærð átta, en jafnvel miklu, miklu stærri. Ég gef þér sameinast raða, hlið við hlið með þessum reiknirit. Þetta er að fara að fá sársaukafull fljótt, og endirinn er ekki sérstaklega climactic, þeir enda bara upp raðað. En lykillinn að taka burt er að líta hversu mikið hraðar sameinast raða var, nema þú heldur að ég bara svona að fíflast með þér. Ef við gerum þetta einn endanlega tíma, skulum endurhlaða þetta, við skulum fara aftur og velja kúla konar, og bara ánægja, skulum velja innsetningu raða, bara gott mál. Og í þetta sinn aftur, við skulum velja Mergesort og skulum í raun að keyra þessar hlið við hlið. Og það er ekki í raun einstakur. Það sem ég hef í raun gert er að ég hef skipt inntak mína í tvennt aftur, og aftur, og aftur. Og það er aðeins svo oft sem þú getur skipta inntak inn í helminga, vinstri og rétt. Hvað er uppskrift að við höldum að sjá sem lýsir skiptingu í tvennt aftur, og aftur, og aftur, og aftur? Áhorfendur: Log n. Ræðumaður: Log n. En svo er það eitt annað mikilvægt skref, þetta reiknirit er ekki skráð þig inn n skrefum. Ef það voru aðeins skrá n skref, Við vildi vera í sama vandamáli eins og áður þar sem við getum ekki verið viss raðað allt er. Þú þarft að óverulega líta á n þætti til að vera viss n þættir eru flokkuð, annars er það áræðni. Svo það er óverulega þig n skref, en hvað um þennan takka samrunafélaganna skref þar sem ég sameinuðust vinstri helmingur minn og hægri helmingur og gekk yfir sviðið? Hversu mörg skref er að að sameina? Það er n, en ég gerði ekki bara sameinast endanlega tíma. Á hverjum þessara hreiður símtöl á hverjum af þeim hreiður sameinast, raðað ég enn. Ég sameinuðust þessir tveir gaurar, þá eru þessir tveir krakkar, þá eru þessir tveir gaurar og svo framvegis. Svo ég gerði sameina aftur, og aftur. Hversu oft? Svo í hvert skipti sem ég skipt á lista í tvennt, ég gerði sameinast. Skiptið lista í tvennt, gera sameinast. Þannig að ef skipta á lista er hægt að gera Log N sinnum, og sameiningu tekur að lokum n skref, hvað gæti verið nú efri bundinn á gangi tími reiknirit okkar? n log n. Og reyndar, það er það við höfum náð hér. Svo finnst sem þú sérð sjónrænt þegar þessir þrír hlutir hlaupa hlið við hlið er n veldi gegn n kvaðrat gegn n log n. Sem í grundvallaratriðum við munum sjá, ekki aðeins í dag heldur í framtíðinni, er miklu, miklu hraðar. A umferð af lófaklapp fyrir þessar krakkar, Ég mun verðlauna þau með streitu bolta. Við skulum fresta hér í dag, og Við munum sjá þig á mánudaginn.