SPEAKER: Olgu, see on CS50. See on nädala lõpuks kolm, ja kui Te ei ole kasutanud juba, tean, et seal on lõunasöögi Selle reede nagu tavaliselt, kus saate nautida head vestlust ja toidu Fire ja Ice mõned CS50 on töötajate ja klassikaaslastega. Head selle URL siia. 

Nüüd te võib-olla mäletate, või sa võib peagi tundma, neid asju siin, mis antakse välja lõpuks Euroopa poolaasta paljudes klassides. Niinimetatud eksami sinine raamatud, kus Sa kirjutad oma vastused eksamid. Nüüd on mul siin 26 sellist sinine raamatud, igal neist on kirjutatud nimi, kuni Z. Ja tõepoolest nimed on nii lihtne, läbi Z. Ja üks eesmärke käepärast täna saab olema jätkata, mis meil algas esmaspäeval, mis ei ole nii palju, vaadates koodi, kuid tegelikult vaadates ideid ja probleemide lahendamine. Üks eesmärke ja lubadusi selle kursuse on õpetada teid mõtlema hoolikalt, rohkem metoodiliselt, ja lahendada probleeme tõhusamalt. Ja tõepoolest, me saame teha, et tegelikult ilma et isegi liigutav rida koodi. Nii et mul on paar elevanti täna siin, oranž ja sinine, Kui me saaksime ühe vabatahtliku, äkki kaugemalt tagasi kui tavaliselt. Kuidas seal, tule alla. Eesmärk, mis saab olema aitab lisaks manustada selle eksami siin. Mis su nimi on? 

Sihtrühm: Mary Beth. SPEAKER: Mary Beth, tule üles. Las ma mikrofoni siin teile. Meeldiv kohtuda. 

Sihtrühm: Meeldiv kohtuda. SPEAKER: Olgu, ma pean siin sinine raamatud läbi Z, ja ma teesklen, et Mul on üks üliõpilased, ja nad tulevad üsna juhuslikult aasta lõpus kolme tunni eksam blokaad, nii nad jõuavad teatud semi-juhuslikus järjekorras niimoodi. Nüüd teie töö on ainult hetk läheb olema-- see on tegelikult, kuidas nad saavad lahkus lõpus klass, kõige tõenäolisem. Sinu töö nüüd saab olema üsna lihtsalt, et sorteerida need sinine raamatuid meile alates kuni Z. 

Sihtrühm: Oh, see on kavatseme igavesti. 

SPEAKER: Ja me vaadata kui sa seda teed, ei rõhu. Sihtrühm: Ei, mingit survet või midagi. 

SPEAKER: Ja lõbu, paneme üles ehitatud taimer. 

Sihtrühm: nii lõbus, nii lõbus. 

SPEAKER: ma ei hoia mic teile. Olgu, me oleme lihtsalt kahekordistunud meie kiirus. Nii et vahepeal, andke mulle kujutada, mida on saab olema küsimus Mary Beth on see, mida ta teeb, kuidas on Ta läheb umbes lahendada see? Ja tegelikult, ei pruugi teil olla kunagi mõelnud midagi nii lihtne, kui valite kuni 26 raamatut niimoodi, mis ei ole loomulik tellimisel neile. Mis on protsess mida te kasutate? Kas see on üsna juhuslik lihtsalt korjamine esimene näete ja panna see oma koht? Kas te esmalt liigutada oma käsi ümber otsin siis otsin B? Kas te võtate pilk paari neid kõrvuti ja lihtsalt öelda, oota, see ei ole õige, ja siis swap järjekorras? Nägime juba esmaspäeval et seal on mitmeid viise kus me saame seda teha, ja tõepoolest, kui me lähedal lõpuks siin, Võtaksin teadmiseks ehk mida Mary Beth teeb. Meil on mõned vaiad tundub, suurem üks, kolm väiksemad. 

Sihtrühm: käsin ma neid kui ma leian kaks tähte et ma tean, et on koos jada, Ma panin need kokku, nii et ma ei pea muretsema hoida jälgida kogu rida raamatuid. See on lihtsalt, oh, on esimene, Mul on see korstna siin. SPEAKER: Niisiis, peaaegu nagu puzzle tükki, et on õige kujuga kohakuti üksteist. Sihtrühm: Päris palju, jah. SPEAKER: OK, väga hea. Ja nüüd iga nimetatud vaiad on arvatavasti järjestatud? 

Sihtrühm: Jah. 

SPEAKER: Olgu, läbi Z. Kõik Olgu, palju õnne, sa tegid seda. Sul on valik. Blue? Olgu, tänan teid selle eest. Seega ei saa Mary Beth ei ettepanekud mida tema lähenemine oli aga mis on teine ​​lähenemine, kuidas te võiks minna sorteerimine neid asju? Mida te olete teinud? Rekord võita oleks olnud üks minut ja 50 või nii sekundi pluss need, ma unustasin loota. Mida te olete teinud? Jah? Sihtrühm: Võtke pinu. Alusta algusest. Kontrolli oma paberid. Ja kui ülemine on suurem kui, äkki on need, alt üks on kõrgem, siis lüliti neid. 

SPEAKER: OK, nii algab ülaosas ja allosas, ja seejärel töö teed sissepoole nagu, et vahetada neid? OK, nii et natuke sarnane vaimus, et mull sorteerida, kuid valides äärmuse ei külgneva paari. Aga lühike on see, et seal on kindlasti hunnik erinevaid viise me võiks seda teha, ja ausalt öeldes, ma arvan, et sa selline vastu paar lähenemisviise, eks? Tegid mingi neli sorteeritud vaiad, ja siis tõhusalt ühendada neid koos. Ja see, daresay teine tehnikat kokku. Sa ei käsitle seda nagu üks suur hunnik, sa jagada probleem neljaks ATVde, kui soovite, ja siis kuidagi liitis need lõpuks. 

Nii Vaatleme lõpuks kuidas muidu me võiksime seda teha. Me formaliseeritud mõiste mull omamoodi viimane kord, ja mull omamoodi tagasikutsumine algoritm, mis me visualiseerida kaheksa oma klassikaaslastega siin, pealtnäha juhuslikult järjestatud alguses. Ja siis otsustasime paarikaupa, kui kaks tegurit on rikkis, lihtsalt vahetada neid. Nii et neli ja kaks on ilmselt rikkis, Nii et need kaks klassikaaslased vahetas kohad. Ja siis me korrata neli ja kuus, siis kuus kuni kaheksa, iga iteratsiooni liigub paremale. 

Nii et antud kaheksa inimest, kui palju paarikaupa võrdlusi ma tegin käies alates vasakult paremale üks selline iteratsiooni? Mitu võrrelda? Seven, eks? Sest kui seal on kaheksa inimesi, kuid teil on paar neid ja te edasi liikuda üks hop paremale, sa ei kavatse on kaheksa võrdlusi, sest sa ei saa võrrelda element iseenda vastu, või oleks see lihtsalt mõttetu, nii et teil on seitse. Või üldisemalt kui meil n inimesed, me teha n miinus 1 võrdlused Bubble sort. 

Nii Vaatleme nüüd, kuidas hea või halb mull omamoodi tegelikult oli, ja proovige andma endale sõnavara mis on kriitika algoritme nagu see, ja varsti meie oma. Nii esimese läbida mull sorteerida, esimest korda Läksin vasakult paremale üle etapis võttis mind n miinus 1 võrdlusi. Ja see saab olema minu mõõtühik, eks? Ma nagu räägin ja uitav, veidi kiire, veidi aeglane, nii lugedes minu number sekundiga ei ole eriti tähenduslik, kuid loendades toiminguid, mis ma tegin esmaspäeval, võrrelda kahte inimest, kes tunneb tore mõõtühik. 

Nii n miinus 1 punkte esmakordselt aga mis siis juhtus pärast seda? Mis on üks tagurpidi ühe söödu läbi muidu sorteerimata nimekirja? Mida saab räägi mulle element kes oli kogu tee seal? Jah? See oli suurim osa, eks? Number kaheksa, kuigi ta algas siin, iga kord, kui ma võrreldes tema vastu naaber, ta hoida vahustamine kuni õige servas nimekirja. Ja tõepoolest, see on kui Algoritmi saab oma nime. 

Nüüd selle loogika, kui palju võrdlusi pea ma omale teist korda Ma teen selle käigu vasakult paremale? n miinus 2, eks? See oleks lihtsalt raiskad oma aega, kui ma hoida võrreldes kaheksa kellegi vastu muud, sest me juba teame ta oli õiges kohas. Nii et see on natuke optimeerimist, nii järgmisel liigu saab olema pluss n miinus kaks sammu, kus n on hulk inimesi. Nüüd saad liiki üldistusi, isegi kui sa ei ole arvuti teadlane, kuidas see lõpeb. Lõpus see algoritm, arvatavasti sul on lihtsalt üks võrdlus vasakule. Sa pead liiki määrata loendi alguses, kui kaks ja üks on rikkis ning peaks olema üks ja kaks, nii see põhjani läbi pluss 1 lõplik võrdlus. 

Nüüd dot, dot, dot tüüpi lained on käed mõned mahlasem üksikasjad, kuid olgem lihtsalt minna ja lihtsustada. Kui te mäletate kõrge kooli, ausalt, palju sa oli matemaatika raamatuid, mis olid vähe petma lehte Esikaanel on või tagakaas, mis näitas sulle Mis seeria kohtuvaidlust nagu Selle lõpuks liita. Üldises juhul, kui teil on varieeruv nagu n ja tõepoolest see üks, kui sa vaatasid oma vana kooli matemaatika raamat, sa näeksid, et see tegelikult lisab kuni selle summa siin n korda n miinus 1 kõik jagatud 2. Nii et nüüd las ma ette näha, see on tõsi, et on liigaasta usu, see on, mida see võtab kuni, ja me võiksime tõestada, et üldisemal juhul. Aga nüüd lähme laiendada seda. Korrutame selle välja, nii et see n ruudus miinus n, kõik jagatud 2. See on tõesti n ruudus jagatud 2 miinus n üle 2 nii et kõik on tore ja huvitav. Aga mis juhtub siis, kui me nüüd plug-in väärtust? Oletame, et ma ei ole kaheksa inimesi, kuid öelda miljonit. Ja miljonit lihtsalt sellepärast, see on päris suur arv, olgem pistik, et ja vaata, mis juhtub. Nii et kui ma ühendan miljonit sellesse valem Ma lähen miljonit ruudus, jagatud 2 miinus miljonit eurot, mis on jagatud 2. Mis nüüd, et läheb võrdsed? Nii et 500 miljardit miinus 500,000. Ja kui ma tegelikult teha et matemaatika läbi, et vahend sorteerimise miljonit inimeste mull omamoodi võib võtta mind 499999500000 meetmeid või võrdlusi eesmärgil me lihtsalt ekstrapoleerimisel. 

See tundub üsna aeglane, kuid ausalt öeldes mõõtes ühe teatava sisendi nagu see, ei ole nii kõnekas. Aga tõesti see oletada, et kui n muutub suuremaks ja suuremaks, seda algoritmi selline enesetunne halveneb ja hullem, või sa tõesti enesetunne valu, et astendamine, et n ruudus mis lisab kuni päris kiire. Ja see detail ei ole kadunud inimesed tegelikult mõned aastad tagasi teatud senaator, kes oli agitatsiooni, istus intervjuu Google'i Eric Schmidt, tegevjuht ajal, ja oli vaidlustada küsimus meelega uurime täna. Võtame pilk. 

[VIDEO PLAYBACK] 

-Senaator, Et sa siin oled Google, ja mulle meeldib mõelda eesistujariigi nagu tööintervjuu. Nüüd on raske saada töö presidendina ja sa lähed läbi külmavärinad nüüd. Samuti on raske saada tööd Google. Meil on küsimusi, ja me Küsi meie kandidaatide küsimusi, ja see üks on Larry Schwimmer. Mida-- te arvate, et ma olen nalja, see on siin. Mis on kõige tõhusam viis sorteeri miljonit 32-bitise täisarvu? 

-Well-- 

Mul on kahju, maybe-- 

Ei, ei, ei. Ma arvan, et mull omamoodi oleks vale tee. 

Tule, kes rääkis talle seda? Ma ei näe arvuti Teadus oma taustast. 

-Meil Meie spioonid on. 

-OK, Olgem küsida erinevat intervjuu küsimus. 

[END VIDEO PLAYBACK] 

SPEAKER: Nii räägivad konkreetsed numbrid küll, ei kavatse olla kõik, mis kasulik. See ei ole elu õppetund, et mull sort, arvestades miljonit sisendite võib võtta nii palju kui 500 miljardit samme. Sa ei saa tõesti üldistada liiga tõhusalt, et ja teha head disaini otsuseid kirjutamise programme. Nii et olgem keskenduda sellele, kuidas me võiks seda lihtsustada tulemus. 

Nii et ma olen Kollased siin tulemusena n ruudus jagatud 2 nii miljoni ruuduline jagatuna 2, ja seejärel Olen rõhutanud, mida lõplik vastus oli kui me lahutatakse maha n jagatud 2. Ja väide Ma teen praegu, kes kurat huvitab, kui sa lahutad maha natuke vana n üle 2 mil esimene Osa selle valem on nii palju suurem? Domineerib muu perspektiivis n ruudus jagatud 2 on nii palju suurem, selgelt, kui n saab suur nagu miljon, see on tõesti suur vahe juures lõpu päeval vahemikus 500 miljardit ja 499999500000? Mitte eriti. Ja nii me läheme teha kui arvuti teadlased on ignoreerida neid madalamat järku tingimused ja võtta midagi sellist ja tegelikult lihtsalt lihtsustab see termin, mis läheb midagi. Suurem meie andmekogud saada, seda suurem Meie andmebaasis saada, rohkem veebilehti meil otsida, seda enam sõpru sul on Facebook. 

Nagu n muutub suuremaks, et me oleme tõesti läheb hooli suurim perspektiivis sellise analüüsi meie algoritmide jõudlust. Ja ma ütlen, et tead, mida, mull sorteerida on suurusjärgus suur O, suurusjärgus n ruudus. See pole just n ruuduline nagu me oleme näinud, kuid kes tõesti hoolib umbes väiksematele mõttes ja ausalt, kes tegelikult huvitab, kui me jagame 2? See on lihtsalt konstandiks. Ja on 500 miljardit versus 250 miljardit tõesti nii suur probleem? Ma ei suutnud lihtsalt ootama ühe aasta, lase mu arvuti sõna otseses mõttes saada kaks korda kiiremini riistvara, ja et mingisugune vahe lihtsalt kaob aja jooksul loomulikul teel. 

Mida me hoolime on väljendus, osa väljend, mis läheb muutuda kui meie panus muutub suuremaks ja suuremaks. Ja tõepoolest, reaalses maailmas, see on, mida juhtub üha on sisendid meie probleemidele ja algoritmid on üha suurem. Nii suur O saab olema märge, asümptootiliseks märke, et me lihtsalt kasutada arvuti teadlased, et kirjeldada täitmisel või sõiduaega, ning algoritm. Nii et saame võrrelda algoritmide erinevates arvutites kirjutatud erinevad inimesed, kasutades mõned täiesti sarnane mõõdik nagu võrdluste arv oled tegemist, või äkki arvu vahetustehingud sa teed. 

Mida me ei kavatse arv on aja mis läbib kella seinal tavaliselt. Mida me ei hakka muretsema umbes kui palju mälu te kasutate täna vähemalt, kuigi see on teine ​​ressurss võiksime mõõta. Me läheme püüdma rajada oma analüüse just põhilisi toiminguid, need, ausalt, et sa näed kõige visuaalselt. Nii et midagi nagu suur O n ruuduline, Väidan, et O n ruudus on ülemise piiri niinimetatud sõiduaega mull omamoodi. Teisisõnu, kui te tahtsin väita, et seal on see ülemine piir, kui palju samme algoritm võib võtta, see saab olema suur O n ruudus sel juhul ülemise. 

Mis siis, kui ma selle asemel muuta lugu olla ei räägi mull sorteerida, aga selle ülemise. Kas te arvate algoritm et me vaatasime juba mille ülemine piir, maksimaalne mõõta aega või toiminguid, oleks öelnud, et olla piiratud n, lineaarne funktsioon, ei quadratic üks, mis on kaardus? Mis on algoritm, mis alati ei kesta kui nagu n samme, või 2n samme või 3n sammud? Jah? 

Sihtrühm: Leida Kõige rohkem on nimekirjas? 

SPEAKER: Perfect leidmine Kõige rohkem nimekirjas. Kui mulle on antud nimekiri inimesed näiteks igaüks, kes hoiab number, Mis on maksimaalne arv samme peaks ta mulle, mõistlikult arukas inimene, leida suurim isik selles nimekirjas? n, eks? Sest halvimal juhul, kui võivad suurim väärtus olla? Right, kõik viis lõpuks. Nii et halvimal juhul ülemist piiri, ma võiks pean minema kogu tee siin ja olla nagu, oh, siin on number kaheksa, või mis iganes, et väärtus on. Nüüd see oleks lihtsalt rumal kui ma elus hoida, eks? Otsite rohkem ja rohkem elemente kui viimane neist on seal? Nii kindlasti, n on ülemine piir. Ma ei pea võtma rohkem samme kui see. 

Mis siis, kui selle asemel ma ettepaneku, et on algoritmide selles maailmas, mis on sõiduaega, mis on piirneb suur O log n log n? Kus me oleme seda varem näinud? Jah? 

Sihtrühm: In telefoniraamat probleem? SPEAKER: Like telefoniraamatust probleem. Mis oli mõõta, kui palju aega või kui palju pisaraid ta võttis mul leida keegi nagu Mike Smith telefoniraamatust? Oleme väitnud, et see oli samamoodi n ja isegi siis, kui võõras või see, et see on natuke udune, mida logaritmi või eksponent oli, Pea meeles, et log n Üldiselt viitab protsessile, sel juhul, jagades midagi veel pooleks ja jälle ja uuesti ja uuesti, nii et see muutub üha väike nagu te teete seda. 

Nii log n viitab, muidugi, telefoniraamat näiteks kahekomponentsete otsing teoreetiliselt kui me oli virtuaalne uksed laual, või kui Sean oli otsivad midagi. Kui ta oli kasutanud binaarne otsing, log n Oleks ülemise kui palju aega, mis võtab. Aga need algoritmid, mis jooksis sisse log n oletada milline võti detail? See loetelu on järjestatud, eks? Teie algoritm on valesti, kui Teie panus on sorteerimata, ja veel sa kasutad midagi binaarne otsing sest te võite hüpata õigus üle element märkamata, et see on tõepoolest olemas. 

Nüüd, milline võiks see tähendab, suur O ühe? See ei tähenda, et teie algoritm võtab üks ja ainult üks samm, see tähendab, et see võtab pidev mitmeid samme. Võib-olla see on 1, võib-olla see on 10, võib-olla on see 1000, aga see on sõltumatu suurus probleem. Ükskõik kui suur n on konstantse ajaga algoritmi võtab alati sama arvu. Niisiis, milline võiks olla algoritm me rääkisime või lihtsalt intuitiivselt, et tegemist on teile, et alati töötab nn konstantse ajaga? Jah? 

Sihtrühm: Lisa kaks numbrit. SPEAKER: Lisa kaks numbrit, 2 pluss 2 võrdub 4, tehtud. Nii et võiks töötada, mida veel? Kuidas rohkem reaalses maailmas, jah? 

Sihtrühm: Leida esimese asjana nimekirja. SPEAKER: Leida esimene element nimekirja, kindlasti. Me oleme tegelikult rääkinud umbes massiivid juba, kuidas sa saad at esimene element massiivi ükskõik kui kaua massiiv on C-koodi? Sa lihtsalt kasutada nagu sulg null märke, BAM, sa oled seal. Ja tõepoolest paneelid kõrvale, toetust midagi üldtuntud kui muutmälu, muutmälu mälu, sest sa võid sõna otseses mõttes hüpata suvalisele kohale. Me saame seda teha isegi rohkem lihtsalt saame tagasi kerida nädal null kui me tegime Scratch. Kui palju aega kulus eest öelda ploki Scratch täita? Just pidev aeg, eks? Ütle midagi öelda midagi, see ei ole oluline kui suur Kriimustused maailm, see on alati aega võtab sama palju aega lihtsalt midagi öelda. 

Nii et see on pidev aja Aga mis on klapp poolel? Kui see oli ülemine piire, mis siis, kui me tahame kirjeldamiseks alumised piirid meie algoritme ajal? Peaaegu parimal juhul potentsiaalselt, kui soovite, kuigi need mõisted, mida kohaldatakse kõige paremini juhul, halvemal juhul keskmine juhtudel rohkem üldiselt, kuid olgem keskenduda ainult madalama piire üldisemalt. Mis on algoritm, mis on alampiir n samme, või 2n samme või 3n sammud? Mõned teguriga n samme, see on selle alumine piir. Jah? 

Sihtrühm: Bubble sort? 

SPEAKER: Bubble sort võtab sa minimaalselt n samme, miks? Miks see nii on? Miks peaks, et start tulevad sind intuitiivselt, isegi kui see ei ole lihtsalt veel? Jah? 

Sihtrühm: [kuuldamatu]. SPEAKER: Täpselt. Parimal võimalikul stsenaariumil mull sorteerida, ja palju algoritme, kui ma käe kaheksa inimest kes on juba valmis, oleks rumal teile, algoritm, minna edasi ja tagasi rohkem kui üks kord, eks? Sest niipea kui kõndida läbi nimekirja kord, sa peaksid mõistma, et oh, ma ei teinud vahetustehingud, see nimekiri on sorteeritud, exit. Aga see aega võtab teid n samme. 

Ja vastupidi, mis on teise mõtlemine on? Bubble sort on omega, nii rääkida, n, sest kui te vaatate vähem kui n elementi, mida on oluline küsimus on? Sa ei tea, kas see on järjestatud, eks. Meie, inimesed, võiks pilgu kaheksa inimesi ja olla nagu, oh, see on sorteeritud, et ei võtnud mind n samme, kuid ta tegi. Su silmad, kuigi sa lahke kohta on suur vaateväli, sa vaatasid kaheksa elemente, sa vaatasid kaheksa inimest, see on kaheksa samme tõhusalt. Ja ainult siis, kui ma kõnnin läbi kogu list Kas ma mõistan, jah, järjestatud. Kui ma poole peal mõtlesin, kõik Olgu, see on päris järjestatud nii kaugele, Mis on tõenäosus, et see ei ole järjestatud? See algoritme ei kavatse olla õige. Võiks olla kiirem, kuid vale. 

Nii et nüüd on meil võimalus kirjeldades alammäär ja kuidas on pidev aja? Mis on algoritm, mis on madalam kohustatud oma sõiduaega üks? 1. samm, 2 sammu, 10 sammu, kuid konstantne, sõltumatu n suurus sisend? Jah, on tagasi. 

Sihtrühm: printf? SPEAKER: Mis see on? Sihtrühm: printf? SPEAKER: printf. OK, muidugi. Nii et see võtab kindla arvu. Ja ma peaks nüüd-- nüüd, et me räägime C kood ja ei kriimusta midagi nagu näiteks koos printf, peaksime hakkama saada ettevaatlik. Kuna printf ei võta sisend, see on string, ja stringid ei tehniliselt on pikkus. Nii et kui me nüüd tahame valida teile, kui te ei pahanda, tehniliselt võiksime väita, et printf ei võta muutuva pikkusega sisend, ja kindlasti see võib võtta rohkem aeg printida string nii kaua, kui seda kaua. 

Mis siis, kui me arvestame ainult sorteerimine ja otsimine näiteid? Aga Mike Smith telefoni raamat või binaarne otsing üldisemalt? Parimal juhul, mis võib juhtuda? Ma avan telefoniraamatu ja põmm, seal on Mike Smith number. Ma ei nimetaks teda kohe. 

Astus sammu, võib-olla kaks sammu, kuid pidev sammude arv kui mul vedas. Ja ausalt öeldes, me nägime Esmaspäev pinginaabri saada üsna õnnelik kaks korda järjest. Ja see oli tõesti pidev korda alumised piirid aasta algoritmi küsimuse kategooria number 50 taga need suletud uksed. 

Nüüd, kui kõrvale jätta, kui sa avastad, et nii suur O, ülemise, ja omega, alampiir, on üks sama, mis on sama valemit sulgudes, saate ka öelda, lihtsalt olla väljamõeldud, et midagi on teeta n või teeta mõne muu väärtusega. See tähendab lihtsalt seda, kui suur O ja omega on sama. Nüüd kuidas valikut sort? Kasutame seda uut sõnavara. In valiku sort, mis oli meil teed uuesti ja uuesti ja uuesti? Ma läksin edasi ja tagasi nimekirja, otsin kellele? Kõige vähem. 

Nii mitu sammu, kuidas palju võrdlusi tegin ma pead tegema selleks, et aru saada, kes väikseim element nimekiri oli? n miinus 1, eks? Sest kui ma alustan ühe olen antud ja ma hakkan võrrelda teda, siis tema, ta või tema, tema, ma saab siduda elemendid koos n miinus 1 korda. Nii et valik omamoodi sarnaselt võtab n miinus 1 sammude esmakordselt. 

Mitu sammu see viib mind leida teine ​​väiksem element? n miinus 2, sest ma oleks loll kui ma saan vaadata samad inimesed uuesti, kui ma olen juba valitud teda või tema ja panna neid oma kohale. Ja kolmas samm, n miinus 3, siis n miinus 4. Me oleme näinud seda mustrit Enne ja tõepoolest valik omamoodi sarnaselt on ülemise n ruudus, kui me üles, et liitmise. Mis on selle alampiiri, valiku sort? Minimaalselt, kui palju aega peab valiku Sorteeri võtta, kui me määratleda seda esmaspäeval? Pakub välja kaks võimalust. Võibolla on see n, nagu enne. Võibolla on see n ruudus, sest see nüüd kui ülemise. 

Sihtrühm: n ruudus. SPEAKER: n ruudus. Miks? 

Sihtrühm: Kuna teil on määratleda [kuuldamatu]. 

SPEAKER: Täpselt. Vähemalt nii ma määratletud valik omamoodi see oli päris naiivne, lase edasi, Leida väikseim element. Mine uuesti Leida väikseim element. Mine uuesti Leida väikseim element. Pole mingit sorti optimeerimine on, et laseks mind katkestada pärast lihtsalt n või nii samme. Nii et tõesti, valik sort, omega n ruudus. 

Aga sisestamise sorteerida, kus ma võtsin kes mulle anti, ja siis ma plopped teda või tema õiges kohas? Siis asus teine ​​isik, plopped teda õiges kohas. Siis järgmine isik, plopped teda õiges kohas. Pange tähele, et see on väga lineaarne, nii rääkida. Ma olen sirge, ma olen ei lähe edasi ja tagasi, Ma pole kunagi tagasi vaadates tõesti, kuid Mis juhtub, kui ma sisestan teda või tema ümber algul loetelus tegime esmaspäeval? Mis toimub? Jah? Sihtrühm: [kuuldamatu]. Ettekandja: Jah, et oli saak, eks? Sa võid mäletate oma klassikaaslastega, kui nad tegid iga liikumise oma jalgu, et oli operatsioon. Nii et kui seal oli kolm inimest siin ja uus isik kuulus viis sinna, pikk etapp niimoodi, muidugi, ta või ta võib lihtsalt minema lõpuni. Aga kui me mõtleme arvuti ja hulga mälu, need inimesed hakkavad on shuffle üle et teha ruumi, et isik. Ja nii, et n miinus 1 shufflings, n miinus 2 shufflings, n miinus 3 shufflings on lihtsalt selline minu taga toimub, ei ole minu ees nagu enne, mõnes mõttes. Nüüd kui kõrvale, ja kui te olete näinud Internetis kui te hakkate poking ümber umbes kehvasti, seal on nii palju erinevaid ones seal, mõned neist paremini kui teised. Tõepoolest, bogosort on üks see on omamoodi lõbus otsida. Bogosort võtab komplekt numbrid või öelda kaardipakk, juhuslikult segab neid ja kontrollib, kas nad järjestatud. Ja kui ei, siis kas see uuesti. Ja kui ei, siis kas see uuesti. Kui ei, siis kas see uuesti. Uskumatult loll. 

Ja tõepoolest, kui sa loed nagu Wikipedia artikkel, tema hüüdnimi on rumalus. See lõpuks tööle, loodetavasti piisavalt aega, kuid sel aega võib võtta omajagu aega. Nii et kui ma saaks, olgem kiirus asjad üles Mary Beth näiteks varem lastes veel mõned elemendid, kuid veel kaks protsessorid. Kaks inimest, kui sa ei pahanda ühendab mind. Kuidas 1 üle siin, ja olgem go-- keegi seal? Keegi seal? OK. Sa musta särk, jah, tule alla. Olgu, mis su nimi on? 

Sihtrühm: Peter. 

SPEAKER: Mis see on? 

Sihtrühm: Peter. SPEAKER: Peter, David, meeldiv kohtuda. Olgu, meil on Peter siin, kui te tahan tulla lauale siin. Ja mis sinu nimi on? 

Sihtrühm: Elena. SPEAKER: Elena. OK, meeldiv kohtuda. Elena kohtuda Peter. Peter, Elena. Ja me vajame Andrew siin ka, palun. Ja teie probleem läheb et sorteerida kaardipakk. Ja kui võõras, tekk kaarte peaks lõpuks sorteerida vähe midagi see, kus me teeme klubid, siis labidad, siis südameid ja teemandid, ässast kui üks, kõik viis kuni kuningas. 

Kaarte ma annan teile saab olema 52 koguses. Me läheme samamoodi kord, vaid hetk. Me läheme visata Andrew kuni ekraanil siin et vaadata, kui sa seda teed. Ja nii, et see kõik on eriti nähtav, need kaardid sain Amazon. Nii et nad on juba juhuslikult sorteeritud, ja me läheme kord, kui sa. Ja me ei kavatse hoiab see reaalne seekord nii me ei kavatse üritada sulle survet avaldada sest muidu saad tüütu kiiresti. Kui sa saaksid minna sorteerida 52 elemendid koos läbi mõned vahendid, nüüd. 

Ja veel, kui me vaatame neid mehed tegema seda, mida lõpuks läheb toota ilmne tulemus, mõtle tegelikult kuidas nad iga tee seda, kuidas sa võiksid kirjeldada. Kuna jällegi on need kõik protsessid, algoritmid et me enesestmõistetavaks nagu inimene. Aga sa oled ilmselt pikka aega olnud intuitsiooni, ammu enne seda, kui isegi mõelnud, võttes arvutiteadus klass sa võisid intuitsiooni koos mida lahendada selliseid probleeme. Aga kui te tunnete mustrid ja alustada vormistama samme, mis sa lahendada neid probleeme, leiad, et sul on võimalik lahendada palju huvitav ja palju keerulisem probleemid kiiresti. Nii et keegi publiku, mis on vähemalt üks element algoritmi et nad kasutavad siin? 

Sihtrühm: [kuuldamatu] SPEAKER: Mis see on? Sihtrühm: ülikond. SPEAKER: ülikond. Nii et kõigepealt nad koonduvad kõik teemandid koos tundub kõik südamed koos tundub, ja nii edasi, ilma suhtes numbrite jaoks kaarte. Ja nüüd nad ilmuvad, näiteks tuleb nende sorteerimine arvust. Väga hea. 

Olgu, mis hakkab oleks viimane etapp, siis siin on? Kui meil on neli sorteeritud ülikonnad, mis me peame tegema, et neli vaiad saavutamiseks ühe järjestatud teki, lihtsalt? Seega on meil vaja liita need uuesti. 

Nii et seal on huvitav idee, jälle daresay, on väga intuitiivne isegi kui sa ei oleks kunagi laksu selline silt peal. See põhiline mõiste jagades probleemiks mitte pooleks seekord kuid vähemalt neljaks osaks. Probleemide päris palju põhimõtteliselt identsed probleemid isoleerituna üksteisest ja seejärel ühineb tulemusi. Ja väga hea, tehtud. Olgu, suur ümmargune aplaus, kui saime. 

[APPLAUSE] 

SPEAKER: ma ei tea, mida sa pistmist, küll aga lahke. Tänan sind nii palju. Vaatame, kaks minutit kaheksa sekundi Kui soovite, et väljakutse oma sõpradele. Mis siis saab olema ära võtta selle et saame kasutada enam üldiselt? Noh, arvan, et tagasi Selle massiivi numbrid, ja arvan, et nüüd tagasi mõned pseudokoodi oleme kirjutanud ka varem, ja see oli pseudokoodi võtta lahendamise telefoniraamatust probleem. Mille sisse pseudokoodi I loetletud rohkem metoodiliselt kirjeldada, kuidas ma tegin väga intuitiivne inimese algoritm jagades telefoni Broneeri pooleks, kordan, kordan, kordan, kuni ma leian kellegi, nagu Mike Smith, kui ta on tõepoolest telefoniraamatust. 

Aga ma sellist, mida kasutatakse, mida ma helistan väga kordusmeetod siin eriti teate rida 8 ja liin 11. Need on tõendeid korduv lähenemine, silmukoiminen lähenemine, sest see on täpselt käitumist nad esile kutsuda. Need read nii öelda minna line kolm, ja te saate objekti arvad, et sinu vaimusilmas nagu oleks loop. Ta räägib sulle, et minna tagasi üles astuma kolm ja kordan uuesti ja uuesti, ja jälle. 

Aga mis siis, kui me võimendada Põhiidee siin, et me ei ole viimane kord, ja lihtsustada rida 8 ja line 11 ja nende naabrid kui ainult see, et kollane. See ei ole põhimõtteliselt lühendamine pseudokoodi väga palju, aga see on põhimõtteliselt muutumas milline mu algoritm. Mis ma nüüd öelda, etapis 7, etapis 10, on otsida Mike aastal Täpselt samamoodi kuid igaks vasakul pool või paremal pool. 

Nii teisisõnu, kui Lähtun samm üks, korja telefoniraamat, avatud keskel telefoniraamatu, vaadata nimesid, kui Smith on üks nime, helistada Mike, teine kui Smith on varem raamat, astu seitse otsi Mike vasaku poole raamatust. Aga selline tunne ta lahkub mind rippus, eks? Kollane, on juhendamise, kuid kuidas ma otsi Mike vasakul pool telefoniraamatust? Kuhu ma pean algoritmi, mis ma otsida keegi nagu Mike Smith? Noh, see on jõllis meid ees. Võin sõna otseses mõttes kasutada täpselt sama programmi tõhusalt tõuseb tippu uuesti ja uuesti jooksvate sama rida koodi. 

Nii et kuigi see ei tohiks tunda nagu natuke tsükliline määratlus kuhu vastates keegi on Küsimus, mida justkui küsides sama küsimust uuesti, nagu miks, miks, miks? Reaalsus on, sest me oleme kõva kodeeritud paar erilist read, etapp 4, mis on siis ja samm 12, mis on tegelikult teise filiaali, sest meil on need asetäitja meetmed, Selle algoritmi lõpeb, kui me leida Mike, või kui me seda ei tee. Aga etapis 7 ja 10 Siiani oleme mida me nimetame rekursiivne algoritm. Ja rekursioon on tõepoolest võimas idee et see on natuke meeles painutamine alguses, et saame nüüd taotleda järgmiselt. 

Merge sort on viimane sort, mis vaatame, vähemalt klassi ametlikult. Ja see on täiesti erinev neist viimase kolme ja kindlasti Viimase nelja, kui me kaasame bogosort. Siin pseudokoodi ühendamisväljundil sort. Kui sisendi n elementi, et anda massiivi suuruse n, kui n on väiksem kui 2, tagasi. Miks ma pean selle meelerahu kõigepealt kontrollida? Mis tähendas, kui ma käe massiivi, mille pikkus n on väiksem kui 2? See on juba sorteeritud, loomulikult, eks? Kuna nimekiri kas on üks element, mis on triviaalselt järjestatud, sest see on Ainuke asi seal. Või on see suurus null, mis tähendab, seal on midagi sorteerida, nii et oma olemuselt see on järjestatud. Seal on lihtsalt midagi valesti seal. Nii et see on meie nn aluspõhimõtted. 

See on sarnase sisuga et mida me tegime koos Mike. Kui Mike telefoniraamatus, helista talle. Kui ta ei ole seal, loobuma. See on niinimetatud baas juhul veenduda, Selle algoritmi lõpus päeval peatub teatud tingimustel. 

Aga siin on liigaasta usu praegu, teine, sorteerida vasakul poolel elemendid siis saad õige pool elemente, ja siis liita järjestatud pooleks. Ja siin on koht, kus ta tunneb, nagu me copping välja. Ma palusin teil sorteerida n elementi, ja ma olen öelda, OK, ei see sorteerimine vasakule ja sorteerimine õigus. Aga ma ütlen üht Teine asi, ja see on peamine teema tundub aastal intuitsiooni seni seal on see kolmas järk ühinevad. Milline kuigi see tundub nii tobe vaimus nagu lihtsalt ühendada asjad koos, tundub olla oluline samm uuesti kokku kaks probleemi, mis jagati lõppkokkuvõttes pooleks. 

Nii ühendada sorteerida, teeme seda, kui sa huumor mulle veel üks meeleavaldus, just nii, et meil on mõned numbrid töötada. Kas ma saan vahetada kaheksa stress pallid kaheksa inimest? Olgu, kuidas on teil kolm, siis neli Käesolevas paragrahvis, viis, kuus, ja olgem ei 7, 8, tule üles. OK, jah OK. Miinus 8, seal läheme, pluss 1. Suurepärane. Olgu tule üles, olgem kiiresti teile numbreid. Number kaks, number kolm, number neli, number viis, kuus, seitse, kaheksa. Ma tegin kaheksa õigesti seekord. 

OK, nii et edasi minna, kui sa saaksid, ja Lahendame esialgses järjekorras et meil oli eile, mis nägi nagu see, kui sa ei pahanda. Ja teeme seda ees laual. Olgu, liita omamoodi. See on koht, kus see läheb saada omamoodi huvitav, sest ma tundub, et olen andnud oma nii palju vähem teavet täna. 

Nii liita omamoodi kõigepealt sisendi n elementi, ja loomulikult ei ole väiksem kui kaks, siis on kaheksa, nii et mul on veel tööd teha. Nüüd vaimselt oleme nagu klassi on nüüd teine ​​haru mis tähendab kolme etappi. Esiteks, ma pean sorteerima Vasakul pool elemente. Niisiis, kuidas ma minna seda teed? Noh, ma lähen liiki vaimselt jagada nimekirja siin, Te ei pea füüsiliselt liigutada, ja ma olen kavatse keskenduda ainult Vasakul pool elemendid siin. Niisiis, kuidas ma minna sorteerimine Avalda oma suuruse neli? Mis on minu algoritm? Esiteks ma kontrollin on n vähem kui kaks, ei, nii et ma edasi veel plokk uuesti. Sorteeri vasakule poole elemente. 

Nüüd jälle, vaimselt ja see on koht, kus teil on koguda palju vaimne ajalugu, kui soovite. Nüüd ma sorteerimine vasakul poolel vasakul poolel. Olgu, nüüd ma kutsun minu sama ühendamine sorteerimine algoritm on N vähem kui kaks? Ei, see on kaks, nii et ma pean sorteeri vasakul pool ja paremal pool. Nii et siin me läheme, sorteerida vasakule poole. Miks sa lihtsalt ei võta üks samm edasi. Mis su nimi on? 

Sihtrühm: Darren. 

SPEAKER: Dan. Dan on astunud sammu edasi. 

Sihtrühm: Darren. SPEAKER: Darren, tehtud. Kas sa ütlesid Darren või Dan? 

Sihtrühm: Darren. 

SPEAKER: Darren. OK, Darren astunud edasi ja ta on nüüd järjestatud. Ja see on peaaegu Loll, õigus? Ma tõesti ei tundu olevat saavutada midagi, kuid olgem jätkata. Nüüd lubage mul sorteerida õige poolel elemente. Mis su nimi on? 

Sihtrühm: Luke. 

SPEAKER: Luke. Astuge edasi. Valmis olen järjestatud Luke. Vasakul pool on nüüd järjestatud ja paremal pool on nüüd sorteeritud, kuid jällegi, seal on oluline samm siin. Mida ma järgmiseks pean tegema? Merge järjestatud pooleks. Nüüd me lihtsalt igaüks edasi ja tagasi sel viisil sest ma nagu vaja mõned tühjalt ruumi. See on peaaegu nagu need kutid on lauale, ja mul on vaja ruumi neid liigutada edasi. Nii et ma lähen ühendada kutid vaadates vasakul pool ja paremal pool. Ja kes ilmselt on esimesel kohal, vasak pool või paremal pool? Nii et parem pool, nii et liigume Luke üle siin Darren oma algasendisse. Ja nüüd ühendada oma vasakule poole, Darren läheb liikuda seal. 

Nii et tundub, nagu peaaegu mull omamoodi mõju, kuid minu peamine algoritm, väga erinevaid seekord. Aga nüüd on koht, kus asjad natuke tüütu, sest sa pea kerida vaimselt Kust ma jätan maha. Ma olen lihtsalt liideti sorteeritud pooleks, mis tähendab, et ma olen, kus minu algoritm? Mul on sorteerida õige poole, eks? 

Kui teil kerida, sõna otseses mõttes aasta video, saate näha, et me peame seda koht Luke ja Darren sorteerimine vasakul poolel vasakul poolel. Siis ühendati need sorteeritud pooleks, mis tähendab, järgmine samm on omamoodi paremal pool vasakul poolel. Olgu, oletame, seda kiiremini. Olgu, kuus, ma väita, te nüüd järjestatud, tule edasi. Mis su nimi on? 

Sihtrühm: Adriano. 

SPEAKER: Adriano. Adriano on nüüd järjestatud. Ja mis sinu nimi on? 

Sihtrühm: Alex. 

SPEAKER: Alex on nüüd järjestatud. Vasak pool, paremal pool, mis on viimane samm? Merge. Päris triviaalne, nii et ma olen kavatse ühineda kuus, astuda samm tagasi, kaheksa, astuda samm tagasi. Ja nüüd teate see on kasulik Buffee, mida Nüüd on tõsi, umbes vasakul poolel nimekiri, sõltumata sellest, kuidas me alustasime? See on sorteeritud. 

Nüüd see ei ole sorteeritud suur kava asju, kuid on järjestatud sõltumatult ning teise poole. Nüüd sellest, mis samm peal ma olen, kui ma hoida kerivad, kuidas lugu algas? Nüüd on mul sorteerida paremal pool. Nüüd oleme viis tagasi loo alguses, ja teeme seda kiiremini. Ma lähen, et järjestada paremal pool kogu nimekirjast. Mis on järgmine samm? Sorteeri vasakule poole parem pool. Sorteeri vasakule poole vasakul pool paremal poolel. Ja mis sinu nimi on? 

Sihtrühm: Omar. 

SPEAKER: Omar, samm edasi, teha. Vasak pool on järjestatud. Ja mis sinu nimi on? 

Sihtrühm: Chris. 

SPEAKER: Chris, astuda samm edasi, siis on nüüd järjestatud. Mis on oluline samm nüüd? Merge. Nii et keegi ei kavatse ühineda paika siin, kui sa võiksid astuda samm tagasi, ja kolm läheb astuda samm tagasi, liita. Nii vasakul poolel paremale poole, on nüüd järjestatud. Ausalt, see algoritm tunne me raiskame nii rohkem aega kui varem, aga kui me seda reaalajas, paneme vaata, mis takeaways saab olema. Nüüd siin ma olen, eks poolel paremal poolel, Lubage mul minna ja sorteeri vasakul pool. Samm edasi, mis su nimi on? Sihtrühm: Ramsey. SPEAKER: Ramsey on nüüd järjestatud. Mis su nimi on? 

Sihtrühm: Marina. 

SPEAKER: Marina on nüüd sorditud Noh, kui te võtate ühe sammu edasi. Oluline samm siin on nüüd liita, olen läheb näppima minu kaks nimekirja, vasakule ja paremale. Viis on tulemas esimene, ja seitse on tulemas järgmine. Ja veel, see on tahtlik. Asjaolu, et nad viivad sammu edasi ja tagasi on mõeldud esindama, et me ei saa seda algoritmi koht nii lihtsalt nagu mull sorteerida, ja valiku sorteerida, ja sisestamise sort, kus me lihtsalt hoida Vahetatakse inimestega. Ma sõna otseses mõttes vaja omamoodi Suttupaperi kus panna need inimesed samas ma ühinevad, ja siis ma ei pane neid tagasi. Ja see on võti, sest ma kasutan uus ressurss, ruumi ei ole lihtsalt aega. 

OK, see on hämmastav. Vasak pool on järjestatud, parem pool on sorteeritud, nüüd peamine ühinevad samm. Kuidas ma ühendada seda? Nii et kui sa järgima oma vasak käsi ja parem käsi, Ma juhtida minu vasak käsi vasakul pool, minu parem käsi õigel pool, ja nüüd pean otsustada, samm-sammult, kellega ühinevad. Kes ilmselt on esimene? Number üks. Nii et tulge siia, siin on meie muistiinpanokenttään. Nüüd number üks, ja teate mida ma teen mu paremale käele, Ma lähen, et liikuda oma parema käe üks samm üle juhtida number kolm, ja nüüd ma pean tegema Sama otsusega. Ja tegelikult paistavad õigus ees Luke siin kui sa saaksid, sest see on meie muistiinpanokenttään. Nii et kes on järgmine? Meil on Luke koos number kaks või Chris number kolm. Ilmselt Luke, number kaks, siis tule siia. 

Aga mu vasak käsi nüüd läheb suurendatakse punkti juures Darren, ja siin on võti ära võtta ühinevad, ma lähen hoida seda teed, Loomulikult, kui sa lahke ja loogikat. Aga mu käed on kunagi lähen tagasi, mis tähendab, et ma olen ainult kunagi kolimist vasakult minu ühendamise protsessi, ja mis saab olema võtmeks Meie analüüs hetk. 

Vaatame nüüd lõpetada see kiiresti. Nii et kolm tuleb järgmisena, siis neli tuleb järgmisena, ja nüüd viis on järgmine, siis kuus, ja seitse, ja siis lõpuks kaheksa. Tunne aeglaseim algoritm veel, aga mitte siis, kui me tegelikult käivitada samal sort kella kiirus, nii et rääkida, sama tiksub kella nagu enne. Miks? Noh, Võtame vaadata lõpptulemus. 

Lähme tagasi siia, las ma tõmba meeleavaldus visuaalselt mida me tegime. Suurendamine siin, sellel leht siin, ütlen Firefox et me tahame järjekorda kuni selles lahtris, olgem öelda mull sorteerida, kellega me oleme nüüd hästi kursis, valiku sorteerida, mis on teine üsna lihtne ühe, ja nüüd tänapäeva merge sort, mis on meie climactic lõpp. Põhjuseks see võttis nii palju kauem siin inimestega ja mind verbaalselt on Ilmselt ma selgitatakse igal sammul. Aga kui sa lihtsalt täita seda, palju nagu me tegime mull sorteerida ning valik Sorteeri mitte ainult visuaalselt, vaata kui palju efektiivsemalt Selle võimendades jagunemine ja vallutavad saab, kui seda kohaldada andmekogum, mis on isegi suurus kaheksa, kuid isegi palju palju suurem. Ma annan sulle liita omamoodi, külg küljel nende teiste algoritme. See ei hakka valus kiiresti ja lõpetamine ei ole eriti climactic, nad lihtsalt lõpuks sorteerida. Aga võti ära võtta on see, et Vaata, kui palju kiiremini liita omamoodi oli, kui sa arvad, et ma olen lihtsalt selline jama sulle. Kui me seda veel viimane aeg, Vaatame uuesti seda, lähme tagasi ja valida mull sorteerida, ja lihtsalt peksab, Valime sisestamise sort, lihtsalt hea meede. Ja seekord jälle, olgem vali ühendamise sorteerida ning olgem tegelikult juhivad neid kõrvuti. 

Ja see ei ole tegelikult juhus. Mida ma olen tegelikult teinud on, et ma olen jagada oma sisendi poole, jälle, ja uuesti ja uuesti. Ja seal on ainult nii palju kordi kui võimalik jagada oma panuse pooleks, vasak ja paremale. Mis on valem, mis me hoiame nähes mis kirjeldab divisjoni poole uuesti ja uuesti ja uuesti ja uuesti? 

Sihtrühm: Logi n. 

SPEAKER: Logi n. Aga seal on üks teine ​​oluline samm, Selle algoritmi ei log n samme. Kui oleks ainult log n samme, meil oleks sama probleem nagu enne, kui me ei saa olla et kõik on järjestatud. Sa pead minimaalselt vaadata n elementi olla kindel, n elemendid on järjestatud, muidu see on liigaasta usu. 

Nii et see on minimaalselt log n samme, kuid Aga see võti ühendamise samm kus ma ühinesid minu vasakul pool ja paremal poole ja kõndis üle lava? Mitu sammu on, et ühendada? See on n, aga ma ei ole lihtsalt ühendada viimast korda. Igal neist pesastatud nõuab iga nende pesastatud ühendab, ma ikka järjestatud. Ma liideti need kaks venda, siis need kaks poisid, siis need kaks ja nii edasi. 

Nii et ma ei ühinevad uuesti ja uuesti. Mitu korda? Nii et iga kord, kui ma jagatud nimekirja pooleks, tegin ühendamine. Jagage nimekirja pooleks, seda ühendamist. Nii et kui jagades nimekiri saab teha log n korda, ühendamine ja lõpuks võtab n samme, mis võivad olla nüüd üleval seondunud pooleli aega meie algoritmi? n log n. 

Ja tõepoolest, see on, mida oleme saavutanud siin. Nii tunned, et sa vaata visuaalselt kui need kolm asja joosta kõrvuti on n ruudus vastu n ruuduline vastu n log n. Mis põhimõtteliselt me ​​näeme, mitte ainult täna, vaid ka tulevikus, on palju, palju kiiremini. Aplausi need kutid, Ma premeerida neid stressi pallid. Lähme edasi lükata täna siin, ja me näeme esmaspäeval.