Puhuja: Okei, tämä on CS50. Tämä on viikon lopussa kolme, ja jos et ole hyödyntäneet jo, tietää, että siellä on lounas perjantaina kuten tavallista, jos voit nauttia hyvä keskustelu ja ruokaa Fire and Ice joidenkin CS50: n henkilöstö ja luokkatoverit. Suunnata tätä URL täällä. 

Nyt ehkä muistatte, tai et saattaa pian olla perehtynyt, näitä asioita täällä, mikä annetaan ulos lopussa lukukauden monta luokkaa. Ns tentti sininen kirjoja, joissa kirjoitat vastauksia tentit. Nyt minulla on täällä 26 tällaista sininen kirjoja, kummallakin niistä on kirjoitettu nimi, Z. Ja todellakin nimet ovat niin yksinkertaista, Z. Ja yksi tavoitteet käsillä tänään tulee olemaan jatkossakin mitä aloitimme maanantaina, joka ei ole niin paljon katsot koodin, mutta oikeastaan pohtivat ja ongelmanratkaisuun. Yksi tavoitteista ja lupaukset Kurssin on opettaa sinut ajattelemaan enemmän huolellisesti, enemmän suunnitelmallisesti, ja ratkaisemaan ongelmia tehokkaammin. Ja todellakin, voimme tehdä, että todella ilman edes kosketa riviä koodia. Joten minulla on pari norsuja täällä tänään, oranssi ja sininen, jos voisimme saada yksi vapaaehtoinen, ehkä alkaen kauemmaksi kuin normaalisti. Entä tuolla, tule alas. Päämääränä tulee olla auttaa sekä hallinnoida tätä tentti täällä. Mikä sinun nimesi on? 

Yleisö: Mary Beth. Puhuja: Mary Beth, tule ylös. Otan mikrofonin täällä sinua varten. Hauska tavata. 

Yleisö: Hauska tavata. Puhuja: Okei, joten minulla on tässä sininen kirjoja Z, ja aion teeskennellä, että Minulla on yksi opiskelijoista, ja he tulevat jokseenkin satunnaisesti lopussa kolmen tunnin tentti lohko, joten he päätyvät joidenkin semi-satunnaisessa järjestyksessä näin. Nyt työsi vain hetki on menossa to olet-- tämä on todella miten he saavat kääntyi lopussa luokka, todennäköisimmin. Työsi nyt tulee olemaan varsin yksinkertaisesti, lajitella nämä siniset kirjat meille alkaen Z. 

Yleisö: Voi, tämä on vie ikuisesti. 

Puhuja: Ja me seuraamme kun teette tämän, ei paineita. Yleisö: Ei mitään painetta tai jotain. 

Puhuja: Ja hauskaa, Katsotaanpa sietää ajastin. 

Yleisö: niin hauskaa, niin hauskaa. 

Puhuja: Voin pitää mikrofoni sinulle. Okei, olemme juuri kaksinkertaistaneet nopeutta. Joten sillä välin, haluan aiheuttaa mitä olemaan kysymys Mary Beth on mitä hän tekee, miten on hän menee noin ratkaista tämä? Ja itse asiassa, sinulla ei ehkä ole koskaan ajatellut jotain niin yksinkertainen kuin noudettaessa jopa 26 kirjoja, kuten tämä, joka ei ole luonnollinen tilaamalla niitä. Mikä on prosessi joita käytät? Onko se melko sattumanvaraisesti vain poiminta ensimmäinen näet ja laitat sen paikoilleen? Oletteko ensin liikuttaa käsiäsi ympäri HAKU sitten etsivät B? Oletteko katsomaan pari vierekkäin ja vain sanoa, hetkinen, tämä ei ole oikein, ja sitten vaihtaa tilauksen? Näimme jo maanantaina että on olemassa useita tapoja jossa voimme tehdä tämän, ja todellakin kuten olemme lähellä loppua täällä, Ottaisin merkille ehkä mitä Mary Beth tekee. Meillä on muutama paalut näyttää siltä, isompi, kolmen pienemmän. 

Yleisö: Käsken heitä kun löydän kaksi kirjainta että tiedän ovat yhdessä järjestyksessä, Laitoin ne yhteen niin, että en tarvitse murehtia pitää Seuraa koko rivi kirjoja. Se on vain, oi, on ensimmäinen, Minulla tämä pino täällä. Puhuja: Niin, melkein kuin palapelin palaset on oikeus muodon sovittaa toisiinsa. Yleisö: Aika paljon, joo. Puhuja: OK, erinomainen. Ja nyt jokainen näistä paalut on oletettavasti lajitellaan? 

Yleisö: Joo. 

Puhuja: Okei, Z. Kaikki oikea, onnittelut, teit sen. Sinulla on valintasi. Sininen? Okei, kiitos siitä. Joten Mary Beth ei ehdottamaan mitä hänen lähestymistapa oli, mutta mikä on toinen lähestymistapa miten voisi mennä noin lajittelu näitä asioita? Mitä sinä olisit tehnyt? Ennätys maalia olisi ollut yhden minuutin ja 50 tai niin sekuntia, plus ne unohdin laskea. Mitä sinä olisit tehnyt? Joo? Yleisö: Ota pino. Aloittaa alusta. Tarkista paperit. Ja jos alkuun yksi on korkeampi kuin, ehkä he ovat, alempi on korkeampi, sitten vaihtaa niitä. 

Puhuja: OK, niin alkaa ylhäältä ja alhaalta, ja sitten työ tiesi sisäänpäin niin, vaihtamalla niitä? OK, joten vähän samanlainen hengeltään kupla lajitella, mutta valinta ääripäitä ei vierekkäiset. Mutta lyhyt se on, että siellä on varmasti joukko eri tavoin voisimme tehdä tämän, ja rehellisesti, mielestäni sinun eräänlainen hyväksyi pari lähestymistapoja, eikö? Teit tavallaan neljä lajitellun paalut, ja sitten käytännössä sulautettiin yhteen. Ja se, daresay, toinen tekniikka kokonaan. Et käsittele se yksi iso kasa, voit jakaa ongelman neljään neloset, jos haluatte, ja sitten jotenkin yhdistettiin ne lopulta. 

Joten harkita, lopulta, Miten muuten voisimme tehdä tämän. Me virallistettiin käsite kupla lajitella viime kerralla, ja kupla lajitella takaisinkutsu algoritmi että me visualisoidaan kahdeksan oppilastoverisi tänne, näennäisen satunnaisesti lajitellaan ensin. Jolloin päätimme pairwise, jos kaksi tekijää ovat epäkunnossa, yksinkertaisesti vaihtaa niitä. Joten neljä ja kaksi ilmeisesti epäkunnossa, joten nämä kaksi luokkatoverit kytketty kantoja. Ja sitten me toistettiin neljä ja kuusi, sitten kuusi ja kahdeksan, on jokaisen iteraation, siirtymässä oikealle. 

Joten annettiin kahdeksan ihmistä, kuinka monta pairwise vertailuja tein kävellessä alkaen vasemmalta oikealle yksi tällainen iteraatio? Kuinka monta vertailuja? Seitsemän, eikö? Koska jos siellä on kahdeksan ihmisiä, mutta sinulla on pari heitä ja olet liikkeessä yksi hop oikealle, et aio olla kahdeksan vertailuja, koska et voi verrata elementti itseään vastaan, tai se olisi vain olla turhaa, joten sinulla on seitsemän. Tai yleisemmin, jos meillä n ihmisiä, me tehdä n miinus 1 vertailut kupla lajitella. 

Joten Tarkastellaan nyt miten hyvä tai paha kupla lajitella todellisuudessa oli, ja yritä antaa itsellemme sanaston josta kritiikki algoritmeja näin, ja pian omamme. Joten ensimmäinen läpi kupla lajitella, ensimmäisen kerran Kävelin vasemmalta oikealle poikki vaiheessa, vei minut n miinus 1 vertailuja. Ja se tulee olemaan minun mittayksikkö, eikö? Olin sellainen puhuminen ja kiertelevä, jonkin verran nopea, hieman hidas, joten laskemalla minun monta sekuntia ei ole erityisen vahva, mutta lukumäärää laskettaessa toiminnot, jotka tein maanantaina, vertaamalla kahta ihmistä, joka tuntuu kuten mukava mittayksikkö. 

Joten n miinus 1 askeleen ensimmäistä kertaa, mutta mitä sitten sen jälkeen tapahtui? Mikä on yksi ylösalaisin yhden pass kautta muuten lajittelemattomat lista? Mitä voit kertoa elementti joka oli aina siellä? Joo? Se oli suurin tekijä, eikö? Numero kahdeksan, vaikka hän talla, joka kerta kun verrannut häntä vastaan naapuri, hän piti kuplii oikealle laidassa luettelon. Ja todellakin, sinne algoritmi on saanut nimensä. 

Nyt tämän logiikan, kuinka monta vertailut tarvitseeko minun tehdä siitä toisen kerran Teen joka syötön vasemmalta oikealle? n miinus 2, eikö? Se olisi vain tuhlaa aikaani, jos en pitää vertaamalla kahdeksan henkilöä vastaan muuten koska tiedämme jo Hän oli oikeassa paikassa. Niin, että vähän optimointi, joten seuraava pass tulee olemaan plus n miinus kaksi vaihetta, jossa n on määrä ihmisiä. Nyt voit sellaista ekstrapoloida, vaikka jos et ole tietojenkäsittelytieteessä, miten tämä päättyy. Lopussa tämän algoritmin, oletettavasti sinulla vain yksi vertailu jäljellä. Sinun täytyy tavallaan korjata alussa luettelon tapauksessa kaksi ja yksi on epäkunnossa ja sen pitäisi olla yksi ja kaksi, joten tämä on pohjassa osoitteessa plus 1 lopullinen vertailu. 

Nyt piste, piste, piste sellainen aallot sen kädet joitakin mehukkaampi yksityiskohtia, mutta haluan vain mennä eteenpäin ja yksinkertaistaa. Jos muistatte korkea koulu, rehellisesti, monet teistä oli matematiikan kirjoja, jotka oli hieman lunttilappua kannessa tai takakansi että näytin sinulle mikä sarja summations kuten tämä lopulta lisätään enintään. Yleisessä tapauksessa, jos sinulla on muuttuja kuten n, ja todellakin tämä, jos katsoit vanhan koulun matematiikan kirjan, voit nähdä, että tämä todella lisää jopa tämän summan täällä, n kertaa n miinus 1 kaikki jaettuna 2. Joten nyt haluan vain säätää tämä on totta, niin on uskonharppaus sitähän tämä kiteyttää asti, ja voisimme todistaa, että yleisempi tapaus. Mutta nyt katsotaanpa laajentaa tätä. Joten kerrottava tämä pois, niin se on n potenssiin miinus n, kaikki jaettuna 2. Se on todella n potenssiin, jaettuna 2, miinus n yli 2, niin että kaikki kiva ja mielenkiintoinen. Mutta mitä tapahtuu, jos me nyt plug-in arvo? Oletetaan En ole kahdeksan ihmiset, mutta sanovat miljoonaa euroa. Ja miljoona vain siksi se on aika iso määrä, katsotaanpa plug että ja katso mitä tapahtuu. Joten jos kytken miljoonaa tuohon kaava Aion saada miljoona potenssiin, jaettuna 2, miinus euroa, jaettuna 2. Mitä nyt se sujuu yhtä suureksi? Joten 500 miljardia, miinus 500000. Ja jos minä itse tehdä että matematiikka ulos, että välineet että lajittelu miljoonaa ihmiset kupla lajitella Ottaa minut 499999500000 vaiheet tai vertailuja varten me vain päättelemällä. 

Joka tuntuu melko hidas, mutta suoraan sanottuna mittaamalla tietyn tulo näin, ei ole kovin kuvaava. Mutta tosiaan se tarkoittaa kuitenkin sitä, että n saa suurempia, tämä algoritmi tavallaan tuntuu huonompi ja pahempaa, tai todella alkaa tuntea kipua, joka eksponenttilausekkeet, että n potenssiin, joka lisää jopa melko nopeasti. Ja näin yksityiskohtaisia ​​tietoja ei ole menetetty ihmisiä, itse asiassa joitakin vuosia sitten tietty senaattori, joka oli kampanjointi, istui haastatteluun Googlen Eric Schmidt, toimitusjohtaja tuolloin, ja altistettiin kysymys aivan kuten me tutkia tänään. Katsotaanpa katsomaan. 

[VIDEOTOISTOSTA] 

-Senaattori, Olet täällä Google, ja pidän ajatella puheenjohtajakauden kuin työhaastattelu. Nyt on vaikea saada työtä presidenttinä, ja olet menossa läpi jäykkyys nyt. On myös vaikea saada työpaikan Google. Meillä on kysymyksiä, ja me kysy ehdokkaita kysymyksiä, ja tämä yksi on Larry Schwimmer. What-- te olette mieltä olen leikkiä, se on täällä. Mikä on tehokkain tapa lajitella miljoonaa 32-bittisiä kokonaislukuja? 

-Well-- 

Olen pahoillani, maybe-- 

Ei, ei, ei. Mielestäni kupla lajitella olisi väärä tie. 

Tule, jotka kertoivat hänelle tämän? En nähnyt tietokonetta tiede teidän taustalla. 

-Olemme Saimme vakoojia siellä. 

-OK, Kysytään eri haastattelu kysymys. 

[END VIDEOTOISTOSTA] 

Puhuja: Niin puhuvat tietty määrä kuitenkin ei tule olla kaikki hyödyllisiä. Se ei ole elämän oppitunti että kuplan lajitella, annetaan miljoonan tulot, voi kestää jopa 500 miljardia vaiheita. Ettehän te voi yleistää liian tehokkaasti, että ja tehdä hyvää suunnittelua koskeviin päätöksiin kirjoitettaessa ohjelmia. Joten keskitytään kuitenkin siihen, miten voisimme yksinkertaistaa tätä tulosta. 

Joten olen korostettu keltaisella täällä tuloksena n ruudutettu jaettuna 2, joten miljoona potenssiin jaettuna 2, ja sitten Olen korostanut, mitä lopullinen vastaus oli kun meillä vähennetään pois n jaettuna 2. Ja väite aion tehdä nyt, kuka helkutti cares jos vähennetään pois pieni vanha N yli 2, kun ensimmäinen osa tätä kaavaa niin paljon isompi? Se hallitsee muita Termi, n ruudutettu jaettuna 2 on niin paljon suurempi, selvästi, koska n saa suuri kuin miljoona, että on olemassa todella suuri ero on Päivän päätteeksi välillä 500 miljardia ja 499999500000? Ei oikeastaan. Ja niin mitä aiomme niin kuin tietotekniikan tutkijoita on sivuuttaa nämä alemman asteen termit ja ottaa jotain tällaista ja todella vain yksinkertaistaa sen Termi että menee väliä. Isompi meidän aineistoja saat, isompi tietokantamme saat, enemmän verkkosivuja meidän täytyy etsiä, enemmän ystäviä sinulla Facebookissa. 

Kuten n suurenee, olemme todella menossa välitä suurin aikavälillä tällainen analyysi algoritmien suorituskykyä. Ja aion sanoa, tiedätkö mitä, kupla lajitella on luokkaa iso O, suuruusluokkaa n potenssiin. Se ei ole aivan n potenssiin kuten olemme nähneet, mutta kuka todella välittää noista pienempi ehdot, ja rehellisesti, kuka oikeastaan kiinnostaa, jos jaamme 2? Se on vain vakiokertoimella. Ja on 500 miljardia vs. 250 miljardia todella niin iso juttu? Voisin vain odottaa vuoden, anna minun laptop kirjaimellisesti saat kaksi kertaa nopeammin laitteisto, ja tuollainen ero vain menee pois luonnollisesti ajan myötä. 

Mitä me välitämme on lauseke, osa lausekkeen, joka tulee vaihdella meidän tulo saa isompia ja isompia. Ja todellakin, todellisessa maailmassa, niinhän tapahtuu yhä on tulot ongelmiimme ja algoritmit ovat yhä suurempia. Niin iso O tulee olemaan merkintä, asymptoottinen merkintä, että me vain käyttää tietotekniikan tutkijoita kuvaamaan suorituskykyä, tai käyntiaika, algoritmin. Jotta voimme vertailla algoritmeja eri tietokoneissa kirjallisen eri ihmiset, käyttämällä Joissakin pohjimmiltaan samanlaisia ​​metrinen kuten vertailujen lukumäärä olet tehdä, tai ehkä useita swap teet. 

Mitä me aio määrä on aikaa joka kulkee kellon seinälle tyypillisesti. Mitä emme aio huolehtia siitä, kuinka paljon muistia käytät tänään Ainakin, vaikka se on toisen resurssin voisimme mitata. Aiomme yrittää perustaa analyysimme on vain perustoiminnot, ystävät, rehellisesti, että voit nähdä visuaalisesti. Joten jotain iso O n potenssiin, Väitän, että O n potenssiin on yläraja on niin kutsuttu ajoaika kupla lajitella. Toisin sanoen, jos halunnut väittää, että on olemassa tämä yläraja kuinka monta vaiheet algoritmi voi kestää, se tulee olemaan iso O n potenssiin tässä tapauksessa yläraja. 

Mitä jos sen sijaan muuttaa Tarina saa olla noin kupla lajitella, mutta tästä yläraja. Keksitkö algoritmin että teimme jo jonka yläraja, maksimi mitata aikaa tai toimintaa, olisi sanoa rajoittamalla n: llä, lineaarinen funktio, ei neliöllisesti joka on kaareva? Mikä algoritmi, joka aina kestää enempää kuin esimerkiksi n välein, tai 2n vaiheet, tai 3n vaiheet? Joo? 

Yleisö: löytäminen Suurin numero luettelossa? 

Puhuja: Perfect löytäminen suurin numero luettelosta. Jos olen antanut luettelon ihmiset esimerkiksi jokainen, joka on tilalla numero, mikä on enimmäismäärä vaiheita se ottaa minua, kohtuullisen älykäs henkilö, löytää suurin henkilö kyseisessä luettelossa? n, eikö? Koska pahimmassa tapauksessa, jossa ehkä suurin arvo on? Aivan, aivan lopussa. Niin pahimmassa tapauksessa yläraja, voisin täytyy mennä aina tänne ja olla, Voi, tässä on numero kahdeksan, tai mitä se arvo on. Nyt olisi vain tyhmä jos pidin menossa, eikö? Etsitkö enemmän ja enemmän elementtejä jos viimeinen niistä on tuolla? Niin varmasti, n on yläraja. Minun ei tarvitse ottaa enemmän vaiheita kuin. 

Joten mitä jos sen sijaan ehdotin olemassa algoritmeja tässä maailmassa on käynnissä aika, joka on rajoittamalla iso O log n, log n? Missä olemme nähneet tämän ennenkin? Joo? 

Yleisö: puhelinluettelosta ongelma? Puhuja: Kuten puhelinluettelo ongelma. Mikä oli mitata, kuinka paljon aikaa tai kuinka monta kyyneleet se vei minut löytää joku Mike Smith puhelinluettelosta? Me väittivät olevan log n, ja vaikka tunne tai se on hieman utuinen mitä logaritmi tai eksponentti oli, vain muistaa, että log n viittaa yleisesti prosessiin, Tässä tapauksessa jakamisesta jotain puoli uudestaan, ja uudestaan, ja uudestaan, ja uudestaan, niin että se saa yhä pienempiä kuin sinä, että. 

Joten päiväkirjaa n viittaa, varma, puhelinluetteloon esimerkiksi binary search teoriassa, kun oli virtuaalinen ovet aluksella, tai kun Sean oli etsii jotain. Jos hän olisi käyttänyt binäärihaku, log n olisi yläraja sille, kuinka paljon aika kestää. Mutta ne algoritmeja, jotka juoksivat log n oletetaan mitä avain yksityiskohtaisesti? Että luettelo on lajiteltu, eikö? Sinun algoritmi on väärä, jos oma panos ei lajitella, ja vielä käytät jotain Binäärihaku koska saatat hypätä oikeus yli elementin tajuamatta sitä on todellakin siellä. 

Nyt mitä tämä voisi tarkoittaa, iso O yhden? Tämä ei tarkoita, että algoritmi otetaan yksi ja vain yksi askel, se vain tarkoittaa se kestää jatkuvasti useita vaiheita. Ehkä se on 1, ehkä se 10, ehkä se on 1000, mutta se on riippumaton Ongelman laajuutta. Ei ole väliä kuinka suuri n on, jatkuva algoritmi ottaa aina sama määrä vaiheita. Joten mikä voisi olla algoritmi olemme puhuneet tai vain intuitiivisesti, että tulee teille, että aina toimii ns vakioaikavälein? Joo? 

Yleisö: Lisää kaksi numeroa. Puhuja: Lisää kaksi numeroa, 2 plus 2 on yhtä kuin 4, tehnyt. Jotta voisi toimia, mitä muuta? Entä enemmän todellisessa maailmassa, joo? 

Yleisö: löytäminen ensimmäinen asia listalla. SPEAKER: Finding ensimmäinen elementti luettelosta varma. Olemme oikeastaan ​​puhuneet noin paneelit jo, miten saat osoitteessa Ensimmäinen elementti array, ei väliä kuinka kauan array on C-koodia? Käytät vain kuten kiinnike nolla merkintä, bam, olet siellä. Ja todellakin paneelit, kuten syrjään, tukea jotain yleisesti tunnettua suorasaantiin, random access muistiin, koska voit kirjaimellisesti siirtyä mihin tahansa yhteen paikkaan. Voimme tehdä tämän vielä yksinkertaisemmin voimme kelata viikko nolla kun teimme Scratch. Kuinka kauan se kestää varten sanoa lohko Scratch toteuttaa? Vain jatkuva aika, eikö? Sano jotain, sano jotain, sillä ei ole väliä kuinka suuri Naarmut maailma on, se on aina vie saman verran aikaa yksinkertaisesti sanoa jotain. 

Niin, että jatkuva aika, mutta mitä kääntöpuoli? Jos se oli ylempi rajoja, mitä jos me haluamme kuvaamaan alarajojen meidän algoritmien ajoaika? Melkein paras asia mahdollisesti, jos haluatte, vaikka näitä termejä voidaan soveltaa parhaiten tapauksissa, pahimmassa tapauksessa keskimäärin tapausta enemmän yleisesti, mutta haluan vain keskittyä on alarajojen yleisemmin. Mikä algoritmi, joka on alarajan n vaiheita, tai 2n vaiheita, tai 3n vaiheet? Jotkut tekijä n vaiheita, se on sen alaraja. Joo? 

Yleisö: Bubble sort? 

Puhuja: Bubble sort vie olet minimaalisesti n vaiheita, miksi? Miksi näin? Miksi että alku luoksesi intuitiivisesti, vaikka se ei ole vain vielä? Joo? 

Yleisö: [kuulumaton]. SPEAKER: Aivan. Parhaalla mahdollisella skenaario kupla lajitella ja paljon algoritmeja, jos annan sinulle kahdeksan ihmistä jotka ovat jo lajiteltu, olisi tyhmää sinulle, algoritmi, mennä edestakaisin useammin kuin kerran, eikö? Koska heti kävelee listalta, kun, sinun pitäisi ymmärtää, oh, en tehnyt mitään swap, tämä luettelo on järjestetty, exit. Mutta se tulee viemään sinut n toimiin. 

Ja kääntäen, mitä toinen tapa ajatella sitä? Bubble sort on omega, niin sanotusti n, koska jos tarkastellaan Alle n elementtejä, mitä on perustavanlaatuinen ongelma siellä? Et tiedä, jos se on järjestetty, oikea. Me ihmiset mahti vilkaista kahdeksan ihmisiä ja olla kuin, oh, se lajitellaan, että ei ottanut minua n toimiin, mutta se teki. Silmäsi, vaikka laji ja on suuri näkökenttä, Oletko katsonut kahdeksan elementtejä, Oletko katsonut kahdeksan ihmistä, Se on kahdeksan porrasta tehokkaasti. Ja vain jos kävelen läpi koko lista tehdä Ymmärrän kyllä, lajitellaan. Jos minä puolitiehen ajattelu, kaikki oikea, se on ihan lajitellaan toistaiseksi, mitkä ovat kertoimet se ei ole lajiteltu? Että algoritmit eivät tule olemaan oikea. Voisi olla nopeampi, mutta väärä. 

Joten nyt meillä on tapa kuvaavat alarajoja, Entä jatkuvasti ajan? Mikä on algoritmi, joka on pienempi sitoo sen käyntiaika yksi? 1 askel, 2 askelta, 10 askelta, mutta vakio, riippumaton n, koko panos? Joo, takana. 

Yleisö: printf? Puhuja: Mikä tämä on? Yleisö: printf? SPEAKER: printf. OK, varmasti. Joten se vie kiinteä useita vaiheita. Ja haluan now-- nyt puhumme C-koodi eikä Scratch, jotain kuten vaikkapa kanssa printf, meidän pitäisi alkaa saada varovainen. Koska printf ei ota tulo, se on merkkijono, ja jouset eivät teknisesti ole pitkä. Joten jos haluamme nyt hakemaan teitä, jos ette pahastu, Teknisesti voisimme väittää, että printf ei ota vaihtelevan pituuden tulo, ja varmasti se voi ottaa enemmän aika tulostaa merkkijonon tämän pitkän, kuin tämä pitkä. 

Joten mitä jos ajatellaan vain lajittelu ja etsivät esimerkkejä? Entä Mike Smith puhelimeen kirja, tai binäärihaku yleisemmin? Parhaassa tapauksessa, mitä voi tapahtua? Avaan puhelinluettelosta ja bam, siellä on Mike Smithin numero. Voin soittaa hänelle heti. 

Otti yhden askeleen, ehkä kaksi askelta, mutta jatkuva useita vaiheita jos olen onnekas. Ja suoraan sanottuna, näimme Maanantai luokkatoverisi saada varsin onnekas kahdesti peräkkäin. Ja se oli todellakin jatkuva aika alarajojen algoritmin kyseessä löytää numero 50 jälkeen lopetetuista ovet. 

Nyt, kuten syrjään, jos huomaat että sekä iso O, yläraja, ja omega, alaraja, ovat yksi ja sama, että on sama kaava suluissa, voit myös sanoa, vain olla fancy, että jotain on theta n: n tai theta jokin muu arvo. Se tarkoittaa vain sitä, kun iso O-ja omega ovat samat. Nyt Entä valinta tavallaan? Nyt käyttää tätä uutta sanastoa. Valinnassa lajitella, mitä olimme tehdä uudelleen ja uudelleen ja uudelleen? Olin menossa edestakaisin läpi lista, etsii kenelle? Pienin luku. 

Niin kuinka monta askelta, kuinka monia vertailuja tein on tehtävä voidakseen selvittää, kuka pienin elementti listassa oli? n miinus 1, eikö? Koska jos vain aloittaa yhden olen annettu ja aloitan vertaamalla häntä, Sitten häntä, häntä tai hänen, häntä, minä voi parittaa elementtejä yhdessä n miinus 1 kertaa. Joten valinta tavallaan samalla otetaan n miinus 1 vaiheet ensimmäisen kerran. 

Kuinka monta askelta se vie minut löytää toiseksi pienin elementti? n miinus 2, koska olen olla tyhmä jos pidän katsot samat ihmiset uudelleen, jos olen jo valinnut hänet tai hänen ja laita ne paikoilleen. Ja kolmas vaihe, n miinus 3, sitten n miinus 4. Olemme nähneet tämän kuvion ennen, ja todellakin valinta tavallaan samalla on yläraja n: n potenssiin jos teemme ylös että summattu. Mikä on sen alaraja, valinta lajitella? Minimaalisesti, kuinka paljon aikaa must valinta lajitella ottaa, koska määrittelimme sen maanantaina? Ehdottaa kahta vaihtoehtoa. Ehkä se on n, kuten ennen. Ehkä se on n potenssiin, koska se on nyt ylärajana. 

Yleisö: n potenssiin. Puhuja: n potenssiin. Miksi? 

Yleisö: Koska sinulla on määritellä [kuultavissa]. 

SPEAKER: Aivan. Ainakin minä määritellyt valinta tavallaan se oli aika naiivi, jatkakaa, löytää pienin elementti. Mennä uudestaan, löytää pienin elementti. Mennä uudestaan, löytää pienin elementti. Ei ole tavallaan optimointi siellä, että ehkä haluaisin keskeyttää jälkeen vain n tai niin vaiheita. Joten todellakin, valinta lajitella, omega n potenssiin. 

Entä lisäyslajittelun, jossa otin joka minulle annettiin, ja sitten minä plopped häntä tai hänen oikeassa paikassa? Sitten aloin toinen henkilö, plopped hänelle oikea paikka. Sitten seuraava henkilö, plopped hänelle oikea paikka. Huomaa, että tämä on erittäin lineaarinen, niin sanoakseni. Olen suora, olen aio edestakaisin, En ole koskaan taaksensa todella, mutta mitä tapahtuu, kun asetan hänet tai hänet alkuun lista kuten teimme maanantaina? Mitä tapahtuu? Joo? Yleisö: [kuulumaton]. Puhuja: Joo, että oli saalis, eikö? Saatat muistamme luokkatoverit, jos ne tekivät mitään liikettä niiden jalat, jotka oli toiminnassa. Joten jos siellä oli kolme ihmistä täällä ja uusi henkilö kuului tuonne, pitkällä vaiheessa näin, varma, hän tai hän voi vain mennä loppuun asti. Mutta jos ajattelemme tietokone ja erilaisia ​​muistia, nämä ihmiset ovat menossa joutua sekoittamaan yli tehdä tilaa, että henkilö. Ja niin, että n miinus 1 shufflings, n miinus 2 shufflings, n miinus 3 shufflings on vain eräänlainen tapahtuu takanani, ei edessäni kuten ennen, jossain mielessä. Nyt syrjään, ja kuten Olet ehkä nähnyt netissä jos alkaa tönäisi ympäri noin lajittelee, siellä on niin paljon erilaisia ​​itse siellä, jotkut heistä paremmin kuin toiset. Todellakin, bogosort on yksi että on aika hauskaa etsiä. Bogosort vie joukon numeroita tai sanoa korttipakan, satunnaisesti sekoittaa niitä, ja tarkastukset jos he lajiteltu. Ja jos ei, tekee sen jälleen. Ja jos ei, tekee sen jälleen. Jos ei, ei sitä uudelleen. Uskomattoman typerä. 

Ja todellakin, jos luette kuten Wikipedia, sen lempinimi on tyhmä tavallaan. Se lopulta toimii, toivottavasti, annetaan riittävästi aikaa, mutta että aikaa voi kestää jonkin aikaa. Joten jos voisin, nyt nopeus asioita ylös Mary Beth esimerkiksi aikaisemmin, saamalla muutamia elementtejä, mutta kaksi prosessoria. Kaksi ihmistä, jos panisi pahakseni liittyä minua. Entä 1 tänne, ja Katsotaanpa go-- kukaan tuolla? Kukaan tuolla? OK. Sinulle musta paita, kyllä, tule alas. Okei, mikä on nimesi? 

Yleisö: Peter. 

Puhuja: Mikä tämä on? 

Yleisö: Peter. Puhuja: Peter, David, hauska tavata. Okei, meillä on Peter täällä, jos haluavat tulla pöydälle tänne. Ja mikä on nimesi? 

Yleisö: Elena. SPEAKER: Elena. OK, kiva tavata. Elena tavata Peter. Peter, Elena. Ja me tarvitsemme Andrew täällä myös, kiitos. Ja haaste on menossa olla lajitella korttipakan. Ja jos tunne, kannella korttien pitäisi lopulta järjestellä vähän jotain Tässä missä me teemme seurat, sitten pataa, niin sydämet ja timantteja, ässästä kuin yksi, kaikki tavalla jopa kuningas. 

Kortteja aion antaa teille tulevat olemaan 52 määrä. Aiomme samalla kerran, vain hetken. Aiomme heittää Andrew ruudulle täällä, niin katsella kuin teet tämän. Ja niin, että kaikki tämän on vielä näkyvämpää, nämä ovat kortteja sain Amazon. Joten ne ovat jo satunnaisesti lajitellaan, ja aiomme ajoittaa sinua. Ja me aiomme pitää se todellinen tällä kertaa, joten aiomme yrittää painostaa sinua koska muuten tämä saa ikävä nopeasti. Jos voisit edetä lajitella 52 tekijät yhdessä kautta joitakin keinoja, nyt. 

Ja taas, kun katselemme näitä teette mitä, lopulta aikoo tuottaa ilmeistä tulos, mieti todella miten he kukin tekevät sitä, miten voit kuvailla sitä. Koska jälleen, nämä ovat kaikki prosessit, algoritmit että otamme itsestäänselvyytenä kuin ihmisen. Mutta olet todennäköisesti jo pitkään ollut intuitio, kauan ennen kuin edes ajatellut ottaa tietojenkäsittelytiede luokka sinua ehkä ollut intuitio kanssa joka ratkaista tämänkaltaisia ​​ongelmia. Mutta kun tunnistat kuvioita ja alkaa virallistaa vaiheet, joita olet ratkaisemaan näitä ongelmia, huomaat, että voit ratkaista paljon mielenkiintoinen ja paljon monimutkaisempi ongelmat nopeasti. Niin joku yleisöstä, mikä on ainakin yhden elementin algoritmin että he käyttävät täällä? 

Yleisö: [kuulumaton] Puhuja: Mikä tämä on? Yleisö: By puku. Puhuja: By puku. Joten ensin ne clustering kaikki timantit yhdessä se näyttää, kaikki sydämet yhdessä näyttää siltä, ja niin edelleen, ilman kunnioitusta varten numerot kortteja. Ja nyt ne näkyvät esimerkiksi voidaan lajittelu lukumäärästä. Erittäin hyvä. 

Okei, joten mitä tulee on viimeinen askel sitten täällä? Kun meillä on neljä lajiteltua puvut, mitä meidän täytyy tehdä neljä paalut jotta saavutetaan yksi lajiteltu kannella, yksinkertaisesti? Joten meidän täytyy yhdistää ne uudelleen. 

Joten on mielenkiintoinen ajatus, että uudelleen, daresay, on erittäin intuitiivinen jopa jos et ehkä koskaan löi tuollainen etiketin. Tämä perustavanlaatuinen käsite jakamalla ongelmaa ei puolet tästä ajasta, mutta vähintään neljään osaan. Ongelmien melko paljon pohjimmiltaan samanlaisia ​​ongelmia erillään toisistaan, ja sitten yhdistämällä tuloksia. Ja erinomainen, tehty. Okei, iso pyöreä suosionosoitukset, jos voisimme. 

[APPLAUSE] 

Puhuja: Minulla ei ole aavistustakaan, mitä sinun tehdä näillä, mutta tässä mennään. Kiitos paljon. Katsotaanpa, kaksi minuuttia ja kahdeksan sekuntia, Jos haluat haastaa ystäväsi. Mitä sitten tulee olla ottaa pois tästä että voimme hyödyntää yleisemmin? No, muistelen tämä joukko numeroita, ja muistelen nyt joihinkin pseudokoodilla olemme kirjoitettu aikaisemmin, ja tämä oli pseudokoodihajota ratkaiseminen puhelinluettelo ongelma. Jolloin pseudokoodilla I lueteltu systemaattisemmin tavalla kuvata miten tein erittäin intuitiivinen ihmisen algoritmi jakamalla puhelimen kirja puoli, toista, toista, toista, kunnes löydän jonkun kuten Mike Smith, jos hän on todellakin puhelinluettelosta. 

Mutta olen sellainen käyttää mitä soitan erittäin iteratiivinen lähestymistapa täällä, erityisesti ilmoituksen rivi 8 ja linja 11. Nämä ovat todisteita iteratiivinen lähestymistapa, kiehkura lähestymistapa, koska se on juuri käyttäydyttävä aiheuttaa. Näiden johtojen molemmat sanovat mennä rivi kolme, ja voit eräänlainen ajatella, että teidän sieluni silmin olevan silmukan. Se kertoo sinua menemään takaisin ylös vaiheeseen kolme ja toista, uudestaan ​​ja uudestaan, ja uudelleen. 

Mutta entä jos me hyödyntää keskeinen ajatus täällä, että emme viime kerralla, ja yksinkertaistaa linja 8 ja linja 11 ja niiden naapureiden koska juuri tämä, keltainen. Se ei ole olennaisesti lyhentää pseudokoodissa erittäin paljon, mutta se muuttaa olennaisesti luonne minun algoritmi. Mitä minä nyt sano vaiheessa 7, vaiheessa 10, on etsiä Mike täsmälleen samalla tavalla, mutta vain vasemman puoli tai oikea puoli. 

Eli toisin sanoen, jos En aloita vaiheesta yksi, poimia puhelinluettelosta, avoimia keskellä ja puhelinluettelosta, katso nimet, jos Smith on yksi nimeni, soita Mike, muuta jos Smith on aiemmin kirja, astu seitsemän etsi Mike vasemmalla puolella kirja. Mutta sellainen tuntuu se jätti minut roikkuu, eikö? Keltainen, on opetusta, mutta miten voin etsi Mike vasemmassa puolet puhelinluettelosta? Jossa minulla on algoritmi, jonka kanssa olen etsiä joku Mike Smith? No, se tuijottaa meitä kasvoihin. Voin kirjaimellisesti käyttää täsmälleen samaa Ohjelman vaikuttavuus menossa ylös uudelleen ja uudelleen käynnissä samaa riviä koodia. 

Joten vaikka tämä pitäisi tuntea kuin hieman suhdanteiden määritelmä jos olet vastaamalla jonkun kysymys vain eräänlainen kysyä sama kysymys uudelleen, kuten miksi, miksi, miksi? Todellisuus on, koska olemme koodattu pari erityisen linjat, vaihe 4, joka on siinä ja vaihe 12, joka on käytännössä toinen haara, koska meillä on nämä hätävara toimenpiteitä, tämä algoritmi päättyy, jos löytää Mike, tai jos emme. Mutta vaiheessa 7 ja 10 nyt, meillä on mitä me kutsumme rekursiivinen algoritmi. Ja rekursio on todella voimakas ajatus Se on hiukan mielen taivutus aluksi, että voimme nyt hakea seuraavasti. 

Merge sort on viimeinen sort että katsomme, ainakin luokassa virallisesti. Ja se on täysin erilainen Näistä kolme viimeistä, ja varmasti Viimeisten neljän jos mukaan bogosort. Tässä pseudokoodihajota yhdistämisen tavallaan. Kun tulossa n alkion, niin annetaan taulukon koko n, jos n on pienempi kuin 2, palata. Miksi minulla on, että järki tarkistaa ensin? Mikä on seuraus, jos annan sinulle taulukon, jonka pituus on n, on vähemmän kuin 2? Se on jo lajiteltu, ilmeisesti, eikö? Koska luettelo on joko yksi tekijä, joka on trivially lajiteltu koska se on Ainoa asia siellä. Tai, se on kooltaan nolla, mikä tarkoittaa mikään ei lajitella, joten luonteeltaan se lajitellaan. On vain mitään vikaa siellä. Niin, että meidän ns pohja tapaus. 

Se on samanlainen henki mitä teimme Mike. Jos Mike puhelinluettelosta, soita hänelle. Jos hän ei ole siellä, anna periksi. Se on niin sanottu emäs tapauksessa varmistaa, Tämän algoritmin lopussa päivän pysähtyy tietyissä olosuhteissa. 

Mutta tässä uskonvaraisesti nyt muuta, lajitella vasemmalla puolella elementtejä, sitten lajitella oikea puolet elementtejä, ja sitten yhdistää lajiteltu puolikkaat. Ja täällä on, jos se tuntuu kuten olemme copping ulos. Olen pyytänyt sinua lajitella n alkiota, ja olen sanoi OK, tee se lajittelemalla vasemmalle ja lajittelun oikeassa. Mutta sanon yhden Toinen asia, ja tämä on keskeinen teema näyttää vuonna intuitio toistaiseksi, on tämä kolmas vaihe sulauttaa. Joka vaikka se tuntuu niin tyhmä hengessä, kuin vain yhdistää asiat yhdessä, se näyttää olla tärkeä askel kohti Kokoa kaksi ongelmaa jaettiin lopulta kahtia. 

Joten yhdistää lajitella, tehdään tämä, jos sinulla huumori minulle, yksi enemmän esittelyä, juuri niin, että meillä on joitakin numerot työskennellä. Voinko vaihtaa kahdeksan stressiä pallot kahdeksan ihmistä? Okei, entä te kolme, neljä erilaista Tässä jaksossa, viisi, kuusi, ja lähdetään älä 7, 8, tule ylös. OK, joo OK. +8, Siellä mennään, plus 1. Erinomainen. Okei Tule ylös, katsotaanpa nopeasti saat numeroita. Numero kaksi, numero kolme, numero neljä, numero viisi, kuusi, seitsemän ja kahdeksan. Tein kahdeksan oikein tällä kertaa. 

OK, niin mene eteenpäin jos voisit, ja Katsotaanpa lajitella alkuperäisessä järjestyksessä että meillä oli eilen jossa tarkasteltiin näin, jos et mielessä. Ja tehdään se edessä pöytä. Okei, joten yhdistää tavallaan. Tämä on, jos se menee saada sellainen mielenkiintoinen, koska en näy antavan itselleni niin paljon vähemmän tietoa tänään. 

Joten yhdistää eräänlainen ensinnäkin Tulon n alkion, ja ei tietenkään ole vähemmän kuin kaksi, se on kahdeksan, joten minulla on jonkin verran enemmän työtä. Joten nyt henkisesti me luokkana ovat nyt muuten haara, mikä tarkoittaa sitä, kolme vaihetta. Ensinnäkin minun täytyy lajitella vasen puoli elementtejä. Joten miten edetä tässä? No, aion sellaista henkisesti jakaa listan täällä, sinun ei tarvitse fyysisesti liikkua, ja olen aio keskittyä vain vasen puoli elementteinä tässä. Joten miten pääsen lajittelu lista nyt koosta neljä? Mikä on minun algoritmi? Ensin tarkistettava n alle kaksi, no, joten en jatka muuta lohkon uudelleen. Järjestä vasen puoli elementtejä. 

Joten nyt taas, henkisesti, ja tässä joudut kertyy paljon henkistä historiaa, jos haluatte. Nyt olen lajittelu vasen puolet vasen puoli. Okei, joten nyt soitan saman yhdistämisen Lajittelualgoritmi, on N alle kaksi? Ei, se on kaksi, joten minun täytyy lajitella vasen puoli ja oikea puoli. Joten tässä sitä mennään, lajitella vasen puoli. Miksi et vain ottaa yksi askel eteenpäin. Mikä sinun nimesi on? 

Yleisö: Darren. 

SPEAKER: Dan. Dan on astunut eteenpäin. 

Yleisö: Darren. Puhuja: Darren, tehty. Sanoit Darren tai Dan? 

Yleisö: Darren. 

SPEAKER: Darren. OK, Darren on lisännyt eteenpäin ja hän on nyt järjestetty. Ja tämä on melkein typerä väite, eikö? En todellakaan tunnu saavuttamaan mitään, mutta katsotaan eteenpäin. Nyt haluaisin lajitella oikea puolet elementtejä. Mikä sinun nimesi on? 

Yleisö: Luke. 

SPEAKER: Luke. Tule, astu eteenpäin. Tehty olen lajiteltu Luke. Vasen puoli on nyt lajitellaan ja oikea puoli on nyt järjestetty, mutta jälleen kerran, siellä on tärkeä askel tässä. Mitä minun seuraavaksi pitää tehdä? Yhdistä lajiteltu puolikkaat. Nyt aiomme vain jokainen edestakaisin tällä tavalla, koska olen sellainen tarvitaan Joissakin työtilaa. Se on melkein kuin nämä kaverit ovat pöydällä, ja minä tarvitsen tilaa siirtää niitä ympäriinsä. Joten aion yhdistää te tarkastelemalla klo vasen puoli ja oikea puoli. Ja joka ilmeisesti tulee ensin, vasen puoli tai oikea puoli? Joten oikea puoli, joten lähdetään Luke yli tästä Darren alkuperäiseen asentoon. Ja nyt yhdistämään vasen puoli on, Darren tulee liikkua tuolla. 

Joten tuntuu melkein kupla lajitella vaikutus, mutta perustavanlaatuinen algoritmi, hyvin erilaisia ​​tällä kertaa. Mutta nyt on, jos asiat saavat vähän ärsyttävää, koska olet täytyy kelata henkisesti Mistä lähden pois. Olen juuri yhdistänyt lajitellut puoliskot, mikä tarkoittaa Olen jos minun algoritmi? Minun täytyy lajitella oikea puoli, oikea? 

Jos kelaat, kirjaimellisesti videon, voit nähdä, että saimme tähän pisteen Luke ja Darren lajittelemalla vasemman puolet vasen puoli. Sitten yhdistimme ne lajitellut puoliskot, joka tarkoittaa seuraava askel on eräänlainen oikea puoli vasen puoli. Okei, joten katsotaanpa tehdä tämän nopeammin. Okei, kuusi, aion vaatia olet nyt selvittäneet, tule esiin. Mikä sinun nimesi on? 

Yleisö: Adriano. 

SPEAKER: Adriano. Adriano on nyt järjestetty. Ja mikä on nimesi? 

Yleisö: Alex. 

Puhuja: Alex on nyt järjestetty. Vasen puoli, oikea puoli, mikä on viimeinen vaihe? Yhdistä. Melko triviaali, joten olen menossa yhdistää kuudessa, ottaa askel taaksepäin, kahdeksan, ottaa askel taaksepäin. Ja nyt huomaa tämä on hyödyllinen takeaway, mitä on nyt totta noin vasen puoli lista, riippumatta siitä, miten aloitimme? Se lajitellaan. 

Nyt se ei ole lajiteltu suuri järjestelmässä asioita, mutta se on järjestetty itsenäisesti ja toinen puoli. Mitä nyt askel Olenko jos pidän kelauksen miten tarina alkoi? Nyt minun täytyy lajitella oikea puoli. Joten nyt olemme paluumatkalla tarinan alku, ja tehdään tämä nopeammin. Joten aion lajitella oikea puoli koko lista. Mikä on seuraava askel? Lajitella vasen puoli oikea puoli. Lajitella vasen puoli vasen puoli ja oikea puoli. Ja mikä on nimesi? 

Yleisö: Omar. 

Puhuja: Omar, askel eteenpäin, tehty. Vasen puoli on lajiteltu. Ja mikä on nimesi? 

Yleisö: Chris. 

Puhuja: Chris, ottaa askel eteenpäin, olet nyt lajitellaan. Mikä on tärkeä askel nyt? Yhdistä. Niin yksi on menossa yhdistää paikalleen täällä, jos voisit ottaa askel taaksepäin, ja kolme on menossa ottaa askel taaksepäin, yhdistää. Joten vasen puoli oikea puoli, on nyt järjestetty. Suoraan sanottuna tämä algoritmi tuntuu kuin olisimme tuhlaavat paljon enemmän aikaa kuin ennen, mutta jos emme tällä reaaliajassa, me mitä noutoruokapaikkoja olemaan. Nyt tässä olen, oikea puolet oikea puoli, anna minun mennä eteenpäin ja lajitella vasen puoli. Askel eteenpäin, mikä on nimesi? Yleisö: Ramsey. Puhuja: Ramsey on nyt järjestetty. Mikä sinun nimesi on? 

Yleisö: Marina. 

Puhuja: Marina on nyt lajitellaan hyvin, jos otat yhden askeleen eteenpäin. Tärkeä askel tässä on nyt yhdistää, olen menossa nyppiä minun kaksi listaa, vasemmalle ja oikealle. Viisi näistä tulee ensin, ja seitsemän on tulossa seuraavaksi. Ja vielä, tämä on tarkoituksellista. Se, että he ottavat astuu esiin ja takaisin on tarkoitus edustaa, että emme voi tehdä tämän algoritmin sijasta yhtä helposti kuten kupla lajitella, ja valinta lajitella, ja lisäyslajittelun missä vain säilytetään vaihtamalla ihmiset. Olen kirjaimellisesti tarvitse lajitella tyhjästä paperi, jossa laittaa nämä ihmiset Vaikka en yhdistäminen, ja sitten voin laittaa ne takaisin paikoilleen. Ja se on avain, koska käytän uusi resurssi, tila, eikä vain kerran. 

OK, tämä on hämmästyttävä. Vasen puoli lajitellaan, oikea puoli on lajitellut, nyt kun avain sulautuvan askel. Miten minä sulauttamisesta? Joten jos voit seurata minun vasen käsi ja oikea käsi, Aion tuoda vasempaan käteeni vasemmalla puolen, minun oikea käteni oikealla puolen, ja nyt minun täytyy päättää askel askeleelta kenen yhdistyä. Joka ilmeisesti tulee ensin? Numero yksi. Joten tule tänne, tässä on meidän muistilehtiö. Joten nyt ykköseksi, ja huomautus mitä teen minun oikealle puolelleni, Aion siirtyä minun oikea käteni yksi askel yli kohtaan numero kolme, ja nyt minun täytyy tehdä saman päätöksen. Ja seisoa aivan edessä Luke täällä jos voisit, koska tämä on meidän muistilehtiö. Joten kuka tulee seuraavaksi? Meillä Luukas on numero kaksi tai Chris numerolla kolme. Ilmeisesti Luke, numero kaksi, niin tulet tänne. 

Mutta minun vasen käsi nyt on menossa kasvatetaan pisteeseen Darren, ja tässä on avain ottaa pois yhdistäminen, aion jatkaa tätä, tietenkin, jos sellainen ja noudata logiikkaa. Mutta käteni ovat koskaan menossa taaksepäin, mikä tarkoittaa En vain koskaan siirtymässä jää minun yhdistäminen prosessi, ja että tulee olemaan avain Analyysissä vain hetken. 

Joten nyt Lopetetaan tämä ylös nopeasti. Joten kolme tulee seuraavaksi, sitten neljä tulee seuraavaksi, ja nyt viisi tulee seuraavaksi, sitten kuusi, ja seitsemän, ja sitten lopulta kahdeksan. Tuntuu hitain algoritmi vielä, mutta ei jos me todella sen käydä samanlaista kellon nopeus, niin puhua, joilla on sama tikittävä kello kuten ennen. Miksi? No, Otetaanpa katso lopputulos. 

Mennään takaisin tänne, haluan vedä ylös esittelyä visuaalisesti mitä me vain teimme. Suurentamalla täällä, tässä sivu täällä, kertoo Firefox että haluamme jonoon ylös tähän kohtaan, katsotaanpa sanoa kupla lajitella, jonka kanssa olemme nyt hyvin tuttu, valinta sort, joka on toinen melko selkeältä yksi, ja nyt tänään yhdistämisen sort, joka on meidän loppuhuipennukseen. Siksi kesti niin paljon kauemmin täällä ihmisiin ja minua sanallisesti on, tietenkin, olen selittää jokainen askel. Mutta jos vain suorittaa tämän, paljon kuten teimme kupla lajitella ja valinta lajitella paitsi visuaalisesti, watch kuinka paljon tehokkaammin tämä hankittua jako ja valloittaa voi, kun sitä käytetään tietojen joukko, joka on ei edes koko kahdeksan, mutta jopa paljon, paljon suurempi. Annan sinulle yhdistää lajitella, rinta puolelta näitä muita algoritmeja. Tämä on menossa tuskallista nopeasti, ja loppu ei ole erityisen huipussaan, ne vain päätyvät lajiteltu. Mutta avain ottaa pois on se, että Katso kuinka paljon nopeammin yhdistää lajitella oli, ellet usko, että olen juuri sellainen pilailin. Jos teemme tämän viimeisen kerran, Katsotaanpa lataa tämä, mennään takaisin ja valitse kupla lajitella, ja ihan vain huvin vuoksi, valitkaamme lisäys lajitella, vain hyvä toimenpide. Ja tällä kertaa taas, nyt Valitse Yhdistämisen lajitella ja lähdetään todella ajaa näitä rinnakkain. 

Ja se ei ole, itse asiassa onnenpotku. Mitä olen noudattanut tätä on olen jaettu minun panos puoli, jälleen, ja uudestaan, ja uudestaan. Ja siellä on vain niin monta kertaa voit jakaa teidän panos kahtia, vasen ja oikea. Mikä kaava, että meillä pitää nähdä joka kuvaa jako kahtia uudestaan, ja uudestaan, ja uudestaan, ja uudestaan? 

Yleisö: log n. 

Puhuja: log n. Mutta sitten on yksi toinen tärkeä askel, tämä algoritmi ei log n vaiheita. Jos se oli vain log n vaiheita, meillä olisi sama ongelma kuin ennen, jossa emme voi olla että kaikki on järjestetty. Sinun täytyy vähän katsoa n osia olla varma n elementit lajitellaan, muuten se uskonvaraisesti. 

Joten se on vähän log n vaiheita, mutta Entä tämä avain yhdistäminen vaihe jossa olen sulautunut minun vasen puoli ja oikea puoli ja käveli poikki vaiheessa? Kuinka monta askelta on, että yhdistää? Se on n, mutta en vain yhdistää viimeisen kerran. Kullekin näistä sisäkkäisiä puheluita, kullakin Näiden sisäkkäisiä yhdistämisiä, olen edelleen lajitellaan. Olen yhdistettiin nämä kaksi kaveria, niin nämä kaksi kaverit, niin nämä kaksi kaveria ja niin edelleen. 

Joten en sulautuvat uudestaan, ja uudestaan. Kuinka monta kertaa? Niin joka kerta olen jakanut alalta puoli, tein yhdistämisen. Jakaa listan kahtia, tehdä yhdistämisen. Joten jos jakamalla luettelo voidaan tehdä log n kertaa, ja yhdistäminen lopulta vie n vaiheet, mikä voisi olla nyt ylemmän sidottu käynnissä aika meidän algoritmi? n log n. 

Ja todellakin, niinhän olemme saaneet aikaan täällä. Niin tuntuu että näet visuaalisesti, kun nämä kolme asiaa kulkevat rinnakkain on n potenssiin vastaan ​​n potenssiin vastaan ​​n log n. Joka pohjimmiltaan näemme, ei vain tänään, vaan myös tulevaisuudessa, on paljon, paljon nopeammin. Aplodit nämä kaverit, Aion palkita heitä stressiä pallot. Katsotaanpa lykätä täällä tänään, ja näemme sinut maanantaina.