[Powered by Google Translate] [Viikko 3, jatkuu] 

[David J. Malan - Harvardin yliopisto] 

[Tämä on CS50. - CS50.TV] 

Selvä. Tervetuloa takaisin. Tämä on CS50 ja tämä on loppuviikosta 3. 

Joten ne tunne, viime vuonna Harvardin käynnistänyt mitä kutsutaan Innovation Lab, tai i-lab, joka on ihana rakennuksen koko joen HBS: n kampuksella joka on avoin opiskelijoiden, GSA opiskelijoita, opiskelijoita eri puolilta kampuksella, lukien tiedekunnan, ja se on paikka kokoontua työskennellä innovatiivisia asioita, erityisesti yrittäjyyteen asiat jos ja 0 tai enemmän ystäviä ajatellut tehdä jotain yrittäjyyteen joko aikana tässä luokassa, sen jälkeen kun tämän luokan, tai sen jälkeen. 

Joten yksi niistä asioista, he tekevät yli J aikavälillä on näitä matkoja, joista yksi on New York, joista yksi on Silicon Valley. Avaruus on hyvin rajallinen, mutta se on mahdollisuus hieroa hartioita MBA ja jatko-opiskelijoille eri kampuksella ja todella viettää aikaa näillä alueillaan chattailuun up startups, chattailuun yrittäjien ja vastaavat. Eli jos kiinnostaa, tutustu tähän URL täällä. Se on saatavilla myös dioja verkossa. 

Voisimmeko lieventää House Audio vain vähän? Jos haluat liittyä meihin lounas perjantaina, 13:15 Fire & Ice, ota suunnata sinne. Pahoittelut jos lomake on jo täytetty, kun pääset sinne. Mutta me jatkamme tätä perinnettä eteenpäin. 

Tänään jatkamme korkeampi keskustelua erilaisista ongelmista, että voimme ratkaista, keskitytään paljon vähemmän, ainakin tänään on koodi ja paljon ideoita. Joten muistelen viikolla 0, kun me repäisi puhelinluettelon kahtia, jonka tavoitteena oli tehdä jotain, tosin hieman dramaattinen mutta lähettää siihen pisteeseen, että hakua ei tarvitse olla välttämättä, yhtä selvää ensi silmäyksellä kuin luulisi. Ja ongelmanratkaisussa yleensäkin eivät välttämättä aina paras - Ilmeisin ratkaisu ei välttämättä olla paras. Joten meillä oli tämä puhelinluettelosta ja suoraan sanottuna, me kaikki tässä huoneessa oli vaistot, todennäköisimmin, alkaa keskellä etsiessään Mike Smith ja siirry sitten vasemmalle tai oikealle perustua johonkin kirjainmerkki meidän sattui päätyä. 

Mutta pelkkä ajatus, että me ihmiset olemme itsestään niin kauan oikeastaan ​​pitäisi alkaa tulemaan eturintamassa mieltäsi koska sillä ongelmia saada paljon monimutkaisempi kuin puhelinluettelo, samat yksinkertainen, loistava oivallukset ovat mitä aiot antaa meille ratkaista paljon monimutkaisempi ja enemmän mielenkiintoisia ongelmia, joukossa joitakin asioita itsestäänselvyyksinä jo näinä päivinä. Miljardeille verkkosivuille siellä, ja silti Google ja Bing ja vastaavat pystyvät löytämään asioita meille tuollaista. Se ei tapahdu käyttämällä lineaarista hakua hakemalla kaikki mahdolliset verkkosivuja. Facebook voi kertoa kuka kaikki ystäväsi ovat tai ystävien, ja sekin voidaan tehdä näennäisesti hetkessä näinä päivinä vaikka heillä on miljoonia käyttäjiä. 

Ja niin miten todella ratkaisemaan ongelmia, jotka mittakaavassa lopulta vähentää ajatuksiin me katsoimme viikolla 0 ja hieman tänään. Emme uudelleen suorittaa tämän algoritmi, mutta muistuttaa teimme myös viikolla 0 tämän harjoituksen missä olimme kaikki seisomaan, ottaa numero 1, ja sitten meillä oli kaikki itsensä count pariksi pois, lisäämällä numerot yhteen, Sitten puolet jengi istui joka iteraation. Menimme 500 opiskelijaa 250-125 ja niin edelleen. Mutta kuten sanoimme maanantaina, voimakas ajatus siellä oli se, että jos me kaksinkertaistunut koko ongelman ja kaikki lapsia Justice tai EY 10 tuli takaisin huoneeseen ja liittyi meihin, No, voisimme ehkä laskea, että koko yhteenlaskettu ryhmän vain 1 enemmän suuria iterointia silmukan koska ne olisivat vain ehkä kaksinkertaiseksi tai EC 10 tapauksessa hieman yli kaksinkertainen koko. Ja niin meillä olisi viettää vähän enemmän aikaa, mutta meidän ei tarvitse viettää 400 tai 700 enemmän vaiheita. 

Vain maalata tätä kuvaa tavalla, joka on hieman vähemmän abstrakti, älkäämme ovat kaikki seisomaan. Mutta jos ne teistä, jotka päättivät istua orkesterin tänään panisi pahakseni seisomaan, Katsotaan jos voimme selvittää teistä, jotka korkein henkilö on tekemällä samanlaista vertailevan algoritmin. Joten jos olet istuu orkesteri, anteeksi, mutta askel 1, stand up; vaihe 2, paria pois kenenkään lähellä sinua, selvittää kuka on pitempi, ja istua alas, jos olet lyhyempi. Toista sitten. [Opiskelijat sorinaa] 

Okei. Okei. Yksi jää pystyyn. Mikä sinun nimesi on? >> Andrew. 

Andrew, olet korkein henkilö orkesterissa osiossa tänään. 

Onnittelut. [Aplodit ja hurraa] Okei. On istuin. Joten löysimme Andrew. Mutta kuinka kauan se olisi ottanut minua esimerkiksi löytää Andrew Tässä orkesteri osassa 50 + tai niin ihmiset? Olisin voinut ottaa melko yksinkertainen lähestymistapa ja aloita täältä. Ja olen 2 henkilöä seisomaan ja minä vain vertailla niitä, ja sitten sanon kuka on hieman lyhyempi, "Okei, istut alas," ja aion muistaa kuka pitempi henkilö oli. Sitten toistan, toistan, toistan, ja minä roikkua kiinni korkein henkilö kunnes löydän jonkun hieman pitempi kuin niitä, jolloin hieman lyhyempi henkilö on istuutua. Mutta että algoritmi tämän orkesterin osassa, jos on n sinusta, kuinka monta askelta on, että algoritmi vie? >> [Opiskelija] N. 

Se vie n, oikealle, koska pahimmassa tapauksessa, niin sanotusti, korkein henkilö on viimeinen henkilö, että saan vain satunnaisesti huonoa onnea. Joten pahimmassa tapauksessa käyntiaika, että algoritmi on lineaarinen, se on n, jossa n on koko joukko ihmisiä tilassa, koko ongelmaa. Mitä tästä algoritmi? Se, että te kaikki nousivat seisomaan ja sitten taas puolet istuit alas, puolet istuit alas, puolet istuit alas. Kuinka monta askelta on, että on ryhdyttävä, jos siellä n. teistä täällä? [Opiskelija] N log n. >> Se olisi huonompi. Log n. 

Joten log n, vaikka et ihan muista mitä logaritmi on, nyt, vain ymmärtää, että se liittyy jotenkin tähän puolittaa ja puolittaa ja puolittaa. Se ei tarvitse olla tekijä, 2. Se voisi olla tekijä 3. Mutta se on tämän samojen sellainen tekijä, että koko ongelman alkaa tästä mutta sitten heti menee tässä, niin tässä, niin tässä, niin tässä. Et ota pieniä puree pois ongelman, olet todella hakkaamalla pois sitä isolla iskulla kerta. Joten meillä oli 50 ihmistä, sitten 25, sitten 12 ½ tai 13 ihmistä seisoo, Sitten 6 ½ ja niin edelleen, kunnes lopulta vain Andrew jäi seisomaan. Joten aiomme soittaa että log n, ja voit visualisoida tämän seuraavasti. Recall Kuvan täällä missä lineaarinen algoritmi on kuin punainen viiva siellä, keltainen viiva oli laskenta by 2s algoritmi, jota käytimme laskemista opiskelijoille aikaisemmin, mutta tänään pyhä Graal aikoo pysyä tämän vihreän linjan jos jos kaksinkertaistui ihmisten määrä orkesterin osassa tai vain sanoi, helvetti, nyt on kaikille koko huoneeseen seisomaan, ei niin iso juttu koska suunnilleen kaksinkertaistaa kuinka monet ihmiset ovat täällä, 1 lisää iteraatio, ei ole ongelma. 

Olemme huomanneet Andrew tai kuka sattuu olemaan pitempi kuin Andrew on mezzanine tai parvekkeella. Joten tämä yksinkertainen ajatus, että teimme paljon itsestäänselvyytenä puhelinluettelosta, ymmärtää, että on olemassa niin monia erilaisia ​​paikkoja, joissa voimme soveltaa sitä. Vain lyödä joitakin ammattikieltä - oikeastaan ​​pikemminkin kuin ammattikieltä ensin anna minun mennä tätä kuvaa tänne. Juuri nyt puhuimme n ja n / 2 ja kirjaudu sitten N, mutta voimme varmasti keksiä, koska me aikana lukukauden, muitakaan matemaattisia kaavoja kuvaamaan tätä yleistä käsitettä ajoaikaan. Nämä ovat asiayhteydestään nyt, koska näemme ennen pitkää algoritmeja että nämä todella ovat. 

Mutta huomaa täällä lineaarinen viiva n, suora, on oikeastaan ​​hyvin vähän osoittaa juuri nyt. Se on eräänlainen optinen harha, että me vain muuttaa mitä x-akseli edustaa ja y-akseli, ja voimme tehdä suoran pisteen mihin suuntaan tahansa haluamme. Mutta syy, että se on niin näennäisesti tasainen nyt on, koska tarvitsimme tehdä tilaa tätä kuvaajaa paljon hitaammin käyntiaikoja. Nyt tiedämme, että on olemassa joitakin melko huonoja algoritmeja elämässä, joista osa ei oteta n toimiin tai, vielä parempaa, log n toimia, mutta enemmän. Joten yläpuolelle n täällä alaosassa huomautus siellä n kertaa log n, ja näemme, mitä tämä tarkoittaa ennen pitkää. Yläpuolella on n potenssiin, ja emme ole nähneet mitään n potenssiin algoritmit vielä, mutta olemme aikeissa. Ja se näyttää todella pahalta. On 2 n, jotain eksponentiaalinen, joka tuntuu vieläkin pahempi. Ja vielä, kumma kyllä, sitten on n kuutioitu, jotka, jos olet tavallaan ajatellen, jos sellainen tehdä matematiikkaa, 2 n todella tulee paljon suorempi, huomattavasti ylempänä kuin n kuutioitu jos tarkastellaan akselit tarpeeksi pitkälle ulos. Joten huomaa nyt nämä akselit ovat mielivaltaisesti 2-10 x-akselilla. 

Ja mitä se tarkoittaa? Tämä tarkoittaa 2 henkilöä 10 henkilöä huoneessa. Siinä kaikki x keinoin: koko ongelma, mitä konteksti on. Ja pystyakseli nyt on monta sekuntia tai useita vaiheita - Joissakin aikayksikössä. Mutta huomaa, että se on 0-60 ja 0-10. Mutta jos me tavallaan loitontaa, kuten ehkä Excelissä tai jotkut kartoitus ohjelmisto, ja menemme jopa 200000, huomaat, että jotain 2-N on menossa kokonaan hukuttaa käyntiaikoja n potenssiin, n kuutioitu n log n - kaikki olemme puhuneet toistaiseksi. Ja silti saalis on, kun aletaan puhua asioista, kuten Facebook missä olet monia, monia, monia ihmisiä kaikki toisiinsa, Sinulla on n ihmistä, joista kukin voi olla niin monta kuin n kanssa jos kaikki on eräänlainen kaveri-kaveri maailmassa, No, se on n kertaa n jo, joten on n: n potenssiin mahdollista ystävyyssuhteita, ainakin 1 suuntaan, N neliö mahdollista ystävyyssuhteita. Niin, että jo nyt, että etsimällä Facebook sosiaalinen kuvaaja, niin sanotusti, voi aloittaa ilmaistaan ​​tällaisia ​​kaavoja. 

Palaamme ja tekevät paljon konkreettisempaa, mutta nyt tavoite seuraavalle monta viikkoa tulee olemaan varmasti ei edetä toteuttamisessa algoritmeja tai koodi että päätyvät ottaen niin paljon aikaa kuin jotain tällaista. Mutta kiehtova juttu tietojenkäsittelytiede jos jatkaa tällä alalla ottaen luokkia kuten CS121, CS124, jotka molemmat ovat teoriassa kursseja, on, että itse asiassa joitakin ongelmia, joita tässä maailmassa että pohjimmiltaan, sikäli kuin tiedämme, ei voida ratkaista yhtään nopeammin kuin pahin nämä kuvaajat todella ehdottaa. Joten siellä paljon avoimia ongelmia tässä maailmassa tehdä paljon paremmin kuin ihmisillä on toistaiseksi. 

Joten aloitetaan sitten tämän esimerkin. Näimme Sean kamppailevat tämän kameran, aivan liian hankalasti videon. Mutta todellisuus oli kun Sean pyrki löytämään taululle näin numero 7, Muistutan, että olen sanonut, että "On jossain takana paperinpaloja tai valkoiset ovet "Numero 7. Sean, löytää se meille." Ja se oli ihanan hankala katsella koska hän oli todella kamppailevat tämän ongelman kanssa. Mutta todellisuus oli Sean tekivät samoin kuin kuka tahansa huoneeseen olisi voinut tehdä. Hän otti hieman kauemmin kuin tavallinen ihminen voi olla, mutta hän olettaa, että siellä oli joitakin temppu tähän ongelmaan, Hän olettaa, että hän puuttuu jotain. Ja se ei auta, että sadat silmät otetaan alas häneen. 

Mutta todellisuus oli, jos tulo ongelma on joukko satunnaisia ​​numeroita ja sinua pyydetään löytämään 1 sellainen määrä, parasta mitä voi tehdä on lineaarinen haku. Aloita vasemmalta, siirry oikealle tai aloita oikealla, siirrä vasemmalle. Takautuvasti, saatamme ajatella, "Sean, mikset vain aloittaa toisesta päästä?" No, 7 voinut yhtä hyvin ollut täällä satunnaisesti, mutta en tietoisesti laittaa sen sinne, koska en tajunnut hän ei aio aloittaa lopussa. Joten minä tavallaan käsitellä tilannetta, vaan Sattumiin 7 voinut missään. Joten alkaen oikeasta päästä olisi ollut parempi silloin, mutta mitä jos ensi vuonna muutan 7 muualle? Se ei pohjimmiltaan uusi ratkaisu ongelmaan - alkaen 1 loppu tai muu - kun olet antanut muita oletuksia. Joten Sean aloitti katsomalla numeroita ja hän sanoi: "5. Se ei ole täällä." Sitten hän meni täällä ja näki 19, sitten hän pysähtyi noin 20 sekuntia, Sitten hän avasi 13, ja sitten kävi ilmi että ei näytä olevan kuvion täällä. Se ei ollut 1, 2, 3, 4 tai vastaava. Siellä oli aukkoja numeroita, joita ei ole apua. Ja myös, että käytin näitä halpoja paperinpaloja peitellä numerot on todella tahallinen, sillä jos olen poistanut kaikki nämä paperinpaloja, useimmat meistä, Sean mukana, luultavasti olisi vilkaisi eräänlainen makroskooppisesti klo liitutaulu ja sanoi: "Voi, 7 on tietysti oikeassa." Me teimme sen heti. 

Ja että voisi olla tapa ihmisen aivot toimii jossain määrin, mutta todellisuudessa hänen silmänsä tai mielessä oli todennäköisesti kuorimalla numerot oikealta vasemmalle, vasemmalta oikealle, keskelle on out - jotain oli tekeillä fysiologisesti sellainen, että tuntui kuin se tapahtui hetkessä, mutta kertoimet ovat jopa sisäisesti siellä oli jonkinlainen menetelmien löytämiseksi 7. Ja todellakin, nyt kun puhumme paneelit ja tietorakenteet ja muisti sisällä tietokoneen, ainoa asia meidän ihmisten tehdä on tarkastella yksittäisten muistipaikkojen 1 kerrallaan. 

Joten jokainen muu paikka voisi yhtä hyvin kuulua jopa joidenkin paperinpala koska emme voi nähdä sitä muutenkaan. Voimme vain tehdä 1 asia kerrallaan. Eli tässä tapauksessa Sean tapauksessa, menimme täällä ja sitten menimme täällä ja sitten menimme täällä, täällä, täällä, täällä, mutta taitava loppuun mennessä ja juuri sellainen väliin tämän yhden mielivaltaisesti löytyi 7 siellä. Tämä yksi ei ollut erityisen erityinen. Sekin oli epäkunnossa. Mutta hän viimein löytyi 7. Mutta nyt takeaway todellakin on, että parasta mitä voi tehdä, kun antaa mitään tietoja muut kuin satunnaisesti lajitella numeroita on aloittaa vasemmalle tai aloita oikealta. Tai pahus, voit satunnaisesti avata ovia, mutta silloinkin mitä se tarkoittaa olla satunnaisia? No, meillä olisi jotenkin virallistaa mitä se tarkoittaa aloittaa täällä, sitten mennä tänne, mene sitten tänne. Sean hienosti, ja se oli vain hauska katsella. Mitä jos vaan muutamme ongelman hieman ja tuoda esille tämän vuoden Sean, jos tulee? Olisiko kukaan olla mukava tulossa lavalle ja ratkaisemiseen hieman erilainen ongelma ja näkyä kamera? 

Mennään pidemmälle orkesteri, koska te olette ollut täysin mukana jo tänään. Entä vaaleanpunainen, vuonna hattu? Tule alas. Mikä on nimesi? >> Alex. >> Alex. Okei. Joten Alex tulee tämän vuoden Sean ja ilmestyy seuraavan useita vuosia arvoinen CS50 luentoja. Alex, nice to meet you. >> Hauska tavata myös. Haasteena käsillä teille on, että sinulla on se hieman helpompaa että kerron teille samat numerot ovat täällä, mutta nyt ne lajitellaan. Joten nyt sinun tehtäväsi on löytää numero 7. Ja itse asiassa, meidän pitäisi todella tehdä tämän - Eipä tällaista huijausta, kuten tietokone ei, katsomalla, mitä numerot olivat hetki sitten. Liidulla tämä todellisuudessa ei auta kovin paljon, mutta älkäämme teeskennellä, että et tiedä mitä alkuperäinen matriisi on. Kaikki te tiedätte nyt, että sinulla on joukko lajiteltu numerot että voi olla aukkoja välillä, ja sinun tehtäväsi on löytää numero 7. Miten, kohtuullinen ihminen, mene noin löytää numero 7? 

Siirry pienestä suureen? >> Okei. Siirry pienimmästä suurimpaan. Ja älä revi niitä pois. Toivotaan vain nostaa ne ylös, jotta voimme käyttää niitä uudelleen. Okei, niin 1. Odota. Ennen kuin jatkakaa, joka oli 1, selvästi väärä. Joten mitä mielesi läpi seuraavaksi? Mitä seuraavaksi? Seuraava. >> Okei. Seuraava. Hyvä. 3, joten virheellinen. Mitä seuraavaksi? Pitää käynnissä. >> Selvä. Pitää käynnissä. 5. Joten pitää käynnissä, ja haluan ojentaa sinulle tämän jälkipolville. 7. >> Erinomainen. Erittäin hyvä. Löytyi numero 7. [Aplodit] Joten se oli hyvä, mutta Sean liian löytynyt numero 7. Ja väitän, että et ole oikeasti hyödyntää tätä ylimääräistä tieto, joka on, että nämä luvut on lajiteltu. Joten me voisimme tehdä paremmin? Kaikki ehdotukset tänne? Niin, takaisin. [Opiskelija] Binary search. >> Minulla ei ole aavistustakaan, mitä binäärihakupuu on. 

[Opiskelija] Aloita keskellä. >> Aloita keskellä. Okei. Joten katsotaanpas jos saamme sinne. Joten jos vaan käsketään alkavat keskeltä, mennä eteenpäin ja avata keskiovesta. On 8 heistä, joten olet menossa on mielivaltaisesti valita yhden hieman vasemmalle tai oikealle. Okei. 7! [Aplodit] Very nice. Okei, mutta minne olimme menossa tähän? Oletetaan vain murtaa tie aloitit täällä koska yhtä voinut tapahtua yhtä hyvin. Me vain sattui tietämään että 7 oli siellä. Tämä on siis 13. Joten jos he lajitellaan ja me vain alkoi keskellä, mitä optimaalinen seuraavaksi on? Mene vasemmalle. Ja niin tässä tulee puhelinluettelon esimerkki uudelleen. Jos 13 on täällä ja me tiedämme lajitellaan, Sitten kaikki nämä palaset paperin mielenkiinnoton meille nyt koska me tiedämme jo, että 7 on vasemmalla Jos nämä numerot lajitellaan ja löysimme 13. 

Joten mitä sinun seuraavaksi täällä? >> Mene vasemmalle. >> Okei, hyvä. Joten mene vasemmalle, ja - odota, hei, hei, hei. Se pettää. Joten olet löytänyt 7, mutta mitä algoritmia me juuri sovellettu? Aloita keskellä. >> Hyvä. Joten mitä looginen jatke saman idean? Voi vain nämä. >> Aivan. >> Joten aloitan täällä. >> Hyvä. Joten nyt mentiin hieman vasemmalle uudelleen. Se on 3. Mutta mielenkiintoinen takeaway nyt kumpi teillä ei tarvitse välittää? Nämä 2. >> Nämä 2. Joten nyt tämä voi mennä pois, tämä voi mennä pois. Nyt ongelma oli 8 silloin oli koko 4 on nyt koko 2. Saamme melko lähellä. Jälleen, mene keskelle näiden 2 elementtiä. 

Okei. Joten se on tavallaan valitettavaa, että nyt olemme aina menossa vasemmalle, koska olemme pyöristäminen alaspäin. Mutta se on hienoa, koska nyt meillä heittää tämän pois ja kaikesta muusta, jättäen meille vain 7. Annetaan aplodit. Löysimme 7 uudelleen. [Aplodit] Okei. Toki. Odota vain 1 sekunti. Vaikka tämä seuraava prosessi sellainen kesti hieman kauemmin kuin se tuntui, rehellisesti, ensimmäinen vaistojen paras, eikö? Löysimme 7 välittömästi. Mutta olisimme löytäneet 7 nopeammin, ei väliä mitä, tässä esimerkissä verrattuna tämä koska jos kaikki numerot ovat lajitellaan, aivan kuten sivujen puhelinluettelosta, voit todellakin pilkkoa puolet ongelmasta ulos uudestaan ​​ja uudestaan ​​ja uudestaan. Ja se ei ole aivan niin helppoa nähdä tämä vain 8 numeroa toisin kuin 1000-sivun puhelinluettelon, jossa olet todella nähdä sen visuaalisesti, mutta tässä tapauksessa tänne, kun Sean oli etsimässä 7, kuinka monta askelta pahimmassa tapauksessa se olisi ottanut hänet? >> [Opiskelija] 7. 7 pahimmassa tapauksessa. No, pahimmassa tapauksessa 7 jos siellä 8 ovia täällä. Se olisi vienyt hänet 8 askelmaa. 

Joten jos siellä on n ovia, se olisi voinut Sean pari vuotta sitten n askelta. Nyt sinun tapauksessasi, Alex, sillä nämä luvut lajitellaan - ja voimme sellaista päättelevät tästä, josta olemme olleet toistaiseksi tämän tarinan - mitä käyntiaika Alexin enemmän älykäs algoritmi ja aloittaen keskeltä ja sitten toistamalla? [Opiskelija] 3. >> Joten se tulee olemaan 3, karkeasti, jos menet 8-4 to 2-1. Joten 3 askelta tai yleisemmin se log n uudelleen. Aina olet puolittamista ja puolittaminen ja puolittaa ja puolittamisen, se ilmaus ajatus log n. Ja jotta olisi kestänyt vain 3 askelta, ja se todellakin teki kun avasimme ovet puolittaa ja puolittaa, tämä olisi ottanut Sean noin 7 tai 8 vaiheita. Joten kiitos siitä, että meille tänä vuonna. >> Kiitos. Kiva tavata. Kiitos Alex. >> Samoin. [Aplodit] 

Mikä on sitten todellinen seuraus tästä? Nyt kuvitella, että se ei ole 8 ovia, jotka suoraan sanottuna kaikki voisimme löytää jotain takana 8 ovien melko nopeasti vain repimällä paperilappuja ja menossa meidän vaistoja. Mutta mitä jos se on miljoona ovet? Mitä jos se on 4000000000 ovea? Kun kyseessä 4000000000 ovea, olet todella menossa halua mennä Alexin algoritmi, binary search alamme soittaa sitä tai hajoita ja hallitse, yleisemmin, missä pidät puolittaa ja puolittaa ongelma, koska jos olet 4000000000 ovea, kuinka monta kertaa voit pilkkoa 4 miljardin puoli? [Opiskelija] 32. >> Se on oikeastaan ​​32. Voit työskennellä tämän ulos paperille tai pään. Menet 4000000000-2 miljardia to 1 miljardista puoli miljardia, 250 miljoonaa, piste, piste, piste. Ja jos et ulos matematiikka, aiot todellakin päästä 32, ja tosiasiallisesti liittyy tietojenkäsittelytieteessä, koska me yleensä lasketa toimivalta 2. 2 32 sattuu olemaan 4000000000. Joten siellä paljon merkitystä tällaisia ​​valtuuksia 2 tietotekniikassa. 

Mutta entä 8000000000? Kuinka monta askelta on, että vie jos on 8000000000 ovia? [Opiskelija] 33. >> So 33. Mitä jos 16000000000 ovet? Kuinka monta askelta on joka vie? [Opiskelija] 34. >> 34. Voisimme tavallaan jatkaa tätä kyllästymiseen. Mutta se voimakas asia. Voit ottaa miljardeja enemmän tuotantopanosten ongelman, mutta ei ole iso juttu, te vain ottaa 1 ylimääräisen purra irti ja siten antaa meille jotain binäärihakupuu tai hajoita ja hallitse, yleisemmin. Mutta olen tavallaan pettää täällä, eikö? Tapauksessa Alex algoritmi, hänellä oli etulyöntiaseman Sean. Hän tiesi, että nämä luvut olivat lajiteltu, mutta Alex ei tarvitse lajitella niitä itse. Olen etukäteen tulivat taululle ja millaisia ​​varmisti että Piirsin ne kaikki ulos lajitellaan järjestyksessä, sitten peitti heidät paperilla. Mutta kuinka paljon työtä ei se ota minua? Jos olisimme alkoi nämä numerot joissakin näennäisesti satunnaisessa järjestyksessä - Tässä tapauksessa näistä yksinkertaisemmista numeroita 1: stä 8 täällä - Miten me edetä lajittelua näistä arvoista? Jos olisit ihmisen tietyn tehtävän, millaisia ​​intuitiivisen lähestymistavan otat lajitteluun koko joukko numeroita? Nämä asiat olivat vahvistetut kuin palapelin palaset. Joo. 

[Opiskelija] Ottaisin jokaisen numeron ja verrata sitä jokainen ja jatka vasemmalle. >> Okei, hyvä. Joten ota jokainen numero, vertaa sitä yksi sen vieressä, ja sitten vain pitää liikkuvat pitkin luettelon, millaisia ​​rejiggering asioita kuten mennä. Joten tässä meillä on mahdollisuus ehkä muutama enemmän ihmisiä sekaantua. Onko meillä 8 enemmän vapaaehtoisia, jotka haluaisivat keksiä? Hieman vähemmän paineita, koska et ole ainoa. 1, 2, 3, 4, 5, 6, 7, 8. Tule alas. Te aiotaan numerot 1: stä 8. Katsotaan jos emme voi tehdä tätä lajittelu Alex pitkälti samalla tavalla tein sen etukäteen. 1, 2, 3, 4. Menkää ja jos olisi, riviin lavalle välillä nuottiteline ja minä täällä samassa järjestyksessä kuin dia näytössä. Uh-oh. Autamme sinua seuraavassa esimerkissä. Odota, odota. Täällä mennään. Odota. Seuraavassa esimerkissä on nyt. Tässä mennään. Numero 8. Tule ylös. Selvä. Sort itsenne tämän mukaan. Työnnä vain hieman sivuun musiikin seistä täällä. Joten meillä on 4, 2, 6 - päästä sinne, tänne, tuolla - 3. Joo. Okei. Voit mennä tänne. Ei, sinä siellä. Joo, oikeassa. No olen väärässä. Tuolla. Okei, hyvä. Okei. Joten nyt mennään lajitella ne nousevaan järjestykseen. 

Miten voin mennä noin tekee näin? Algoritmi, joka ehdotti hetki sitten oli, miksi emme vain verrata ihmiset, jotka ovat tavallaan vierekkäin ja sitten korjata mahdolliset virheet, liikkuvat vasemmalta oikealle. Joten tässä meillä on 4 ja 2, ilmeisesti epäkunnossa. Mennään swap sinua. Okei. Joten nyt aion siirtyä ruodussa. 4 ja 6, nope. [Naurua] 6 ja 8, melko hyvä. 8 ja 1, haluan vaihtaa kaverit. Selvä. Joten 8 ja 3, vaihtaa kaverit. 8 ja 7, haluan vaihtaa kaverit. 5 ja 8, erinomainen. Annan teille lajiteltu luettelo. Selvä. Joten ei aivan. Mutta se on parempi koska isompi numerot - tapaukseen 8 - ovat eräänlainen kuplina ylös vasemmalle yli oikealle. Joten sain 1 niistä oikealle, mutta se tuntuu tämä ei kuitenkaan ratkaise ongelmaa. 

Joten mitä ehdottaisit teemme seuraavaksi? >> [Opiskelija] pitää tehdä se. >> Pidämme tehdä se. Ja ymmärtää, jälleen, asetamme asioita joita vain ottaa kaikki ihmiset tavallaan älykkäästi järjestää itse perustuu tuon kuvan, mutta nyt meidän on oltava paljon suunnitelmallista. Meidän on oltava algoritmiseen siitä ikään kuin olemme kirjoittaa koodia - Tässä tapauksessa sanallinen pseudokoodilla. Joten haluan vain kokeilla uudestaan. Tämä sujui varsin hyvin. Se ei ratkaise sitä. Mutta kun se Epäilen vain yrittää ja yrittää uudelleen. Joten 2 ja 4, ei auta enää. 4 ja 6. Ah! 6 ja 1, hieman parempi nyt. 6 ja 3, hyvä. 6 ja 7, 7 ja 5, 7 ja 8, hyvä. Ja tiedätkö, voin varmaan jättää 8 nyt, koska hän oli listan loppuun. Ehkä meidän ei tarvitse huolehtia siitä, että joku menee ohi. Mutta katsotaanpa, jos se on turvallinen oletus. Nyt lista on - pahuksen - ei lajitella. Kokeillaan uudestaan. Niin 2 ja 4, 4 ja 1, 4 ja 3. 4 ja 6, hyvä. 6 ja 5, hyvä. 6, 7 ja 8, hyvä. Mutta ilmoitus, voin vain lopettaa täällä nyt ja lopettaa täällä nyt? [Opiskelija] Kyllä. >> Niin? Mitä jos joku teistä ollut numero 9 kaikki tuonne? Se on lajiteltu. >> Hyvä. Se on lajiteltu ensimmäisellä kerralla. Hyvä. Mennään takaisin. Olemme melkein siellä. 1 ja 2, 2 ja 3, 3 ja 4, 4 ja 5, 5 ja 6, 6 ja 7, 7 ja 8. 

Olen tehnyt nyt vaan, taas, olen tietokoneella, joka voi vain tehdä, mitä olen kertonut tehdä, ja ainoa muistikuva on, että nyt olen itse juuri tehnyt vähän työtä. Jotain muuttui täällä. Joten en ole teknisesti vahvistaneet visuaalisesti tai algoritmisesti että luettelo on todella lajitellaan. Eli vain hyvä toimenpide, vain olla anaali tästä, tehdään tämä 1 enemmän aikaa. Joten 1 ja 2, 2 ja 3, 3 ja 4. Ja tiedättekö mitä? Vain hyvä toimenpide, aion seurata minun käteen tällä kertaa kuinka monta swap voin tehdä juuri niin, että tiedän, miten paljon työtä olen itse tehnyt. 3 ja 4, 4 ja 5, 5 ja 6, 6 ja 7, 7 ja 8. Ei swapit. Joten nyt olisin oikeutetusti idiootti tehdä tätä uudelleen koska jos en ole työtä kautta läpikulun ihmisille, sitten selvästi, että tulee tapahtumaan uudelleen, jos mikään niistä ei tavallaan satunnaisesti adversarially liikkuvat itse noin. Joten nyt voin lopettaa. Nyt kysyä, kuinka paljon työtä ei oikeastaan ​​viedä minut? Kuinka monta askelta ei se kestää? >> N potenssiin. Joo, niin n neliö. Mistä saat n potenssiin alkaen? Sinun täytyy tarkistaa jokaisen num - On n numeroita, ja sinun täytyy tarkistaa kunkin numeron kanssa muiden n numerot. Hyvä. >> Joten se on n: n potenssiin. >> Hyvä. 

Joten se tuntuu se voisi hyvinkin olla n potenssiin, eikö? Siellä on N näitä tyyppejä, 8 erityisesti tässä tapauksessa, mutta joka kerta menin läpi tämän listan olin vertaamalla ensimmäinen henkilö vastaan ​​toisen, Toisen kolmatta uudestaan ​​ja uudestaan ​​ja uudestaan, ja kun sain loppuun, mitä minä tein? I redid sen. Joten jos me yleistää tämä selitys, olemme on n ihmisiä ja olen tekemässä, tietenkin, 8 askelmaa, n askelta, aina kun menen läpi tämän algoritmin. Mutta kuinka monta kertaa pahimmillaan minun täytyy käydä läpi tämä luettelo ihmisistä? [Opiskelija] N kertaa. >> Luultavasti n, oikealle, koska pahimmassa tapauksessa, mikä luultavasti pahimmassa tapauksessa järjestely nämä kaverit get-go? Jos he täysin päinvastainen järjestys koska vain olettaa henkisesti, let's - Mikä on nimesi? >> Bowen. Bowen. Okei. Joten Bowen, tule tänne hetkeksi. 

Oletetaan, että Bowen oli tässä alussa algoritmin, ja emme tiedä mitä kaikki muu on, mutta Bowen täällä, tämän algoritmin - ja jos haluat vain kävellä kanssani - tulee kupla ylös, niin kuin hän teki ensimmäisellä kerralla, aina loppuun. Mutta oletetaan, että henkilö vieressä Bowen oli numero 7. Minun täytyy mennä takaisin ja saada numero 7, mikä tarkoittaa, että minun täytyy mennä aina takaisin tänne. Nyt minun täytyy olla, että sama kävelylle henkilön kanssa, joka on numero 7. Mutta entä jos sitten numero 6 oli hänen vieressään samoin? Sitten minun täytyy mennä takaisin ja saat 6. Joten jälleen, joka iteroinnin tämän silmukan Puhun kunkin n ihmisiä, ja saisin tehdä n näitä kävelyretkillä varmista olen vetämällä kaikki suurimmat osat takaisin ja takaisin ja takaisin aivan listan loppuun. Joten n asioita n kertaa on vain n kertaa n tai n neliöön. 

Joten tässä on jo meillä algoritmi, joka ei enää n, se ei enää log n, se on oikeastaan ​​pahempi kuin mitä olemme tehneet aiemmin. Joten Alex eräänlainen onnekas, että tein kaiken työn ilmeisesti edessä hänen, kaikki kallista työtä, jotta hän voisi nauttia tässä binäärihakupuu algoritmi, joka on log n. Mutta tämä on sopusoinnussa maanantain teema. Annoimme hieman enemmän tilaa, käytimme enemmän bittejä, jotta nopeuttaa meidän käyntiaika. Niin paljon kuin on tämä kompromisseja aikaa ja tilaa, saattaa myös vain olla kompromisseja aika edessä jonkinlainen saada asioita valmiina ja tosiasiassa ajetaan algoritmi haku. Kokeillaan toista. Jos teillä ei ole mielessä vain nopeasti järjestämällä itseänne vastaamaan, että taas Kokeillaan jotain hieman erilaista, jos se ei ole aivan niin yksinkertainen koska vain korjata kaikki pareittain virheitä, mikä on erittäin intuitiivinen. Katsotaanpa sen sijaan olla hieman tarkoituksellista ja tehdä tämän. Tämäkin ehdotan on luultavasti melko intuitiivinen. 

Katsotaanpa valitse pienin henkilön luettelosta uudestaan ​​ja uudestaan. Joten tässä sitä mennään. 4, olet pienin ihminen olen siis nähnyt tähän mennessä, joten aion henkisesti muistaa että juuri osoittamalla sinua nyt. 2. Ooh! Unohda numero 4. Löysin juuri uuden pienin elementti tässä luettelossa. Aion sellaista muistaa. 6, 8. Ooh! 1. Näkemiin. Joten nyt aion muistaa numero 1. Tiedämme, että 1 on pienin, mutta olen tietokoneella. Mitä jos 0? Mitä jos siellä -1? Minun täytyy jatkaa. Joten 3, 7, 5, nope. Okei. Niin numero 1 oli pienin. Saanen valitse sinut listalta - we'll go näin - ja laittaa te mielivaltaisesti alussa luettelosta. Nyt, odota hetki. Olen sellainen petetty. Jos nämä kaverit ovat ei luetteloa 8 henkilöä, mutta jono, 8 paloina yhtenäistä muistia - älä viitsi tehostamalla takaisin hetkeksi? Ei oikeastaan ​​ole tilaa teille täällä. Joten miten teemme tilaa - Mikä on nimesi? >> Sammy. >> Sammy. Miten teemme tilaa Sammy? 

Siirrymme n, jotka ovat ennen minua. >> Okei. Jotta voisimme siirtyä n ihmisiä, jotka ovat ennen häntä, joten jos te haluatte ottaa 1 tahallinen, dramaattinen askel vasemmalle. He kaikki tekivät, että ääneen, mutta viime kerralla Kirjoitin koodin, et voi tavallaan siirtää monia asioita kerralla. Voisimme tehdä sen silmukan, liikkuu jokainen kerran kerrallaan. Joten jos te panisi pahakseni tehostamalla takaisin oikealle, ja Sammy, jos voisit askel taaksepäin, koska siellä on vielä sijaa teille, nyt tehdään tämä. Jos oli Sammy hetki sitten? Tuolla. Joten on aukko siellä. Joten voisit siirtyä Sammyn paikalla. Nyt seuraava henkilö ja nyt seuraava henkilö, nyt seuraava henkilö. Nyt meillä on tilaa Sammy. Nyt joku yleisöstä - että oli hyvä, että oli oikein, tuntui vähän aikaa - mikä on nopeampi? Joo. [Opiskelija] Uusi array? >> Mikä tuo on? >> [Opiskelija] Uusi array? >> Okei, hyvä. 

Joten sopusoinnussa tämän teeman vain kompromisseja, miksi en vain tehdä uuden taulukon  ja sitten Sammy on uima tilaa edessä nämä ihmiset, esimerkiksi ja voimme vain alkaa täyttää uuden array kokonaan. Sekin toimisi. Mutta en ole kiinnostuneita käyttämään enemmän tilaa tänään. Mikä on toinen lähestymistapa? [Opiskelija] Swap. >> Okei. Voisimme vain vaihtaa nämä 2 kaverit. Mikä sinun nimesi on? Mario. >> Mario. Joten Mario, olit nyt täällä. Sammy, voit varmuuskopioida vain hetkeksi? Mario oli täällä. Meillä ei ole tilaa teille enää, joten jos et mielessä aio missä Sammy on, laitamme Sammy täällä, ja nyt olin sitä mieltä, että Sammyn vaihtava toiminta oli paljon nopeampaa. Teimme 1 operaatio vaihtaa näitä tyyppejä, tai ehkä 2 vaihtaa näitä tyyppejä, mutta emme tee 1, 2, 3, 4, niin että tuntuu paremmalta. Nyt, odota hetki. Olen sellainen tehnyt ongelma pahempi, koska numero 4 oli tavallaan lähellä alkua. Nyt numero 4 on hieman lähempänä tätä, mutta en todellakaan tiedä tai välitä siitä. Joten tämä on vain huonoa tuuria, että numero 4 on hieman kauempana sen tarkoitettu paikka. Joten nyt toista algoritmi. 

Voit kertaus, kunhan tarina oli, annoimme kävelee luetteloa etsii pienimmän numeroitu henkilö. Joten nyt tehdään se uudestaan. Meillä ei tarvitse murehtia Sammy enää. Voimme vain mennä tänne. Ooh! Numero 2. Se on aika pieni määrä. 6, 8, 4, 3, 7, 5. Okei, hyvä. Ja onneksi, sattumalta, minun ei tarvitse liikkua - >> Willie. Willie koska hän on hänen oikeassa paikassa nyt. Tehdään tämä uudestaan ​​ja sivuuttaa nämä 2 kaverit. 6. Se on aika pieni määrä. Ooh! 8 on varmasti isompi. 4. Keskitytään 4. Ooh! 3 on vielä parempi. 7 ja 5. Joten mitä me teemme nyt - >> Roger. >> Roger? Katsotaanpa vaihtaa hänet numero 6. Joten jos 6 ja 3 haluaisi vaihtaa, olemme nyt tavallaan saanut onnekas, että 6 on lähempänä missä hän olisi, mutta se on vain sattumaa täällä. Joten nyt mennä tänne. 8 on melko pieni määrä. Ooh! 4 on pienempi. 6, 7, 5. Mitä me nyt teemme? >> Vaihda. >> Aivan. Joten nyt tehdään tämä tavallaan nopeammin. 8, 6, 7, 5. Jos ei 5 mennä? Hyvä. Okei. 6, 7, 8. 6 saa jäädä missä hän on. Mikä sinun nimesi on? >> Rosalie. Rosalie saa jäädä missä hän on. 7 saa - Katsotaan. 7, 8. Okei. Joten 7 saa asua missä hän on. Mikä sinun nimesi on? >> Amna. >> Amna. 

Joten Amna saa jäädä missä hän on, ja numero 8 on jo missä hän nyt olisi. Okei, hyvä. Tuntuu kuin olisimme juuri työllistää itsemme täällä, tosin. Mikä lopulta käyntiaika tämän algoritmin? Jos ajattelemme nämä ihmiset ole yhtä 8 vaan n? >> Se on n.. Se on n askelta, mutta me tarkistaa joka ikinen kerta. Okei. N mutta olet tarkkailun joka ikinen kerta? Okei, mutta jos se on n askelta, ei minun pitänyt pystyä lajittelemaan sinulle juuri menossa 1, 2, 3, 4? Oh! Okei, se on iso ero. Joten n potenssiin miksi? Mitä todella tapahtuu? Siellä N ihmisiä tässä luettelossa, mutta löytää pienin henkilön luetteloon pahimmassa tapauksessa, kuinka monta askelta minun pitäisi ottaa? >> N. 

N, oikealle, koska pahimmassa tapauksessa, numero 1 on aina siellä, joten minun täytyy mennä hakemaan hänet. Ja sitten kun vihdoin ymmärtää 1 oli pienin, niin se on melko nopea vaihtaa niitä. Mutta nyt minun täytyy aloittaa alusta ja etsiä kuka? Seuraavaksi pienin henkilö, joka on 2. Jossa pahimmassa tapauksessa on 2? Voi luoja. Se on niin tänne lopussa. Joten nyt olen juuri tehnyt toisen n askelta, toinen n askelta. Ja jos meillä n ihmisiä ja pahimmassa tapauksessa pienin ihminen on n askeleen päässä, se taas n kertaa n, ja niin olemme taas on n potenssiin. Tätä ei tunne niin hyvin. Ja itse asiassa jopa parhaassa tapauksessa - olettaa, että ne alkaa lajitella - kuinka monta askelta se kestää minun käyttää tätä algoritmia lajitella nämä n ihmiset? N potenssiin. >> Kuulin n potenssiin. Miksi n potenssiin? Koska sinulla on vielä tarkistaa joka ikinen kerta. >> Joo. Ja sinun täytyy vaihtaa niitä. >> Vaikka me ihmiset olemme sellainen kaikkitietävä siinä mielessä visuaalisesti että voimme vain sellaista nähdä tämän lajitellaan, tietokone ei ole niin fiksu. Se tulee näyttämään täällä ja täällä ja täällä, mutta jos se, mitä se etsii on pienin elementti, vain tietää, että olet löytänyt pienimmän alkion mitä järkeä? Kun olet lopussa. Mutta siinä vaiheessa olet vain löytänyt hetkellä pienin alkio. Et välttämättä tiedä mitään muuta maailman tilasta. Joten sinun täytyy mennä uudestaan ​​ja uudestaan ​​ja uudestaan. 

Joten tällä kertaa olen todella katsoa tyhmä koska olen tarkkailun, okei, 2, olet pienin, mutta en tiedä, että yhteensä vielä. 3, 4, 5, 6, 7, 8. Okei, hyvä. 2 oli todellakin pienin. Nyt löytää seuraavaksi pienin. Okei. 3, olet tällä hetkellä pienin. Katsotaanpa. 4, 5, 6, 7, 8. Okei, onnisti jälleen. 3 oli todellakin oikeassa paikassa. Mutta aion jatkaa tätä uudestaan ​​ja uudestaan ​​ja uudestaan. Miten voimme tehdä koskaan niin hieman paremmin? Sen sijaan, että ihmiset kupla ylös pareittain pienimmästä suurimpaan ja sen sijaan menee edestakaisin luetteloa valitsemalla sitten pienin henkilö, Miksi emme sen sijaan lisätä nämä ihmiset uuden luettelon askel askeleelta? Kokeillaan tätä. Nyt haluaisin kutsua tätä asiaa insertion sort. Joten tässä me olemme täällä. Numero 1. En välitä kukaan muu tässä luettelossa. Oma tavoite tällä hetkellä on laittaa numero 1 alussa järjestetty luettelo. Ja aion ehdottaa koska minulla on vain 8 palasina muistia, mielivaltaisesti nyt olen seinämän välillä minun muka lajittelemattoman lista, ja jokainen, joka on takanani aion vaatia lajitellaan. Eli nyt on numero 1. Haluan lisätä hänet minun lajiteltu lista, joten olen juuri menossa siirtää minun seinään tänne, ja nyt Väitän tätä lajitellaan, luettelo on lajittelematta - ainakin sikäli kuin tiedän. En näe kaikkia numeroita kerralla. 

Nyt Satun kohtaavat numero 2. Mitä teen hänen kanssaan? Asetan sinut nyt osaksi järjestetty luettelo. Mutta huomaa kuinka helppoa se oli. Minun täytyy vain katsoa. Numero 1 on siellä. Voi tietenkin 2 menee puolelle numero 1. Nyt mitä teen kanssa 3? Asetan sinut järjestetty luettelo. Mutta se oli super helppo. Tämä on erittäin helppoa, tämä on erittäin helppoa, tämä on erittäin helppo, erittäin helppo, erittäin helppo. Ja nyt kaikki on lajiteltu takanani, ja kuinka monta askelta ei se kestää? [Opiskelijat] N. >> Niin se vain n. Meillä kävi tuuri. Se oli vain n miksi? >> [Opiskelija] Koska luettelo lajitellaan. Luettelo on jo järjestetty. Niinpä saimme onnekkaita. Mutta me suunniteltu algoritmi tällä kertaa, että valjaat sellaista onnea, että parhaassa tapauksessa se ei tuhlaa turhaa aikaa. Joten meillä on nyt mitä me kutsumme kupla lajittelee jossa ihmiset eräänlainen kupla ylös pareittain. Meillä on nyt valikoima lajitella jossa nyppiä pois pienin ihminen uudestaan ​​ja uudestaan. Ja nyt meillä on insertion sort jossa me tavallaan proaktiivisesti laittaa ihmisiä minne ne kuuluvat yhä lajiteltu luettelo. Jos voisimme, aplodit nämä kaverit täällä. [Aplodit] Otetaan meidän 5 minuutin tauon. Ja kun tulemme takaisin, me räjäyttää kaikki nämä algoritmit vedestä jotain parempaa. Selvä. Kiitos paljon. Voit pitää niitä matkamuistoja. Selvä. Olemme takaisin. 

Ja kertaus tosi nopeasti, meillä oli nämä 3 eri lähestymistavat lajittelu, idea oli päästä pisteeseen, jossa joku Alex voisi etsiä listan numeroita nopeammin kuin joku Sean voisi. Ja vaikka meillä on tällaisia ​​yksinkertaisia ​​esimerkkejä 8 numeroa, voit päätellä helposti 8 verkkosivuja, 8000000000 web-sivuja, tai 800000000 ystäviä Facebookissa. Joten nämä algoritmit voidaan varmasti skaalata tuollaiset arvot, ja ideat ovat lopulta sama. Joten kupla sort oli ensimmäinen, jossa me tavallaan kuplina ylös suurin henkilö aina oikealla vaihtamalla ihmisiä pareittain. Sitten meillä oli mitä me kutsumme valinta lajitella jossa olen hieman tarkoituksellisesti katseli luettelon läpi, valitaan pienin numero uudestaan ​​ja uudestaan ​​ja uudestaan, looginen seuraus on, että lista on lopulta lajitellaan. Sitten kolmas, lisäsin ihmiset oikeisiin paikkaan, ja teimme hyvin keinotekoinen esimerkki siitä, että luettelo on jo lajiteltu, mutta se oli lähettää viesti, että lisäys lajitella tapauksessa, saat onnekas. Jos numeroita on jo lajiteltu, se vain vie sinut n askelta vahvistaa niin paljon, katsoo valinta lajitella olet hieman putkinäkö ja et koskaan ymmärrä, että luettelo on jo järjestetty. Joten katsotaanpas kupla lajitella toiminnassa täällä. Seuraavassa esimerkissä aiomme nähdä pystypalkki joiden korkeudet ovat numeroita, jotta voimme tavallaan visualisoida lajittelu tapahtuu. Pienempi palkki, pienempi numero, sitä suurempi palkki, isompi numero. 

Ja me pelata sitä tällä oletuksena nopeudella. Se tulee liikkua hieman nopeasti nyt, mutta punainen on mitä näyttää 2 baaria verrataan vierekkäin. Ja jos katsot tarkkaan, mitä tapahtuu on että jos baarit ovat epäkunnossa, pienempi kukaan siirretään vasemmalle, sitä suurempi yhdellä oikealle, ja sitten pidät etenee. Joten jos teemme tämän uudestaan ​​ja uudestaan, huomaan, että pienin baarit tulevat pitämään inching tiensä vasempaan ja suurimmat baarit ovat menossa pitämään inching tiensä oikealle. Ja todellakin, olemme alkaneet nähdä kuvion koko matkan oikealla puolella kuten näimme 8 ja sitten 7 lopulta kuplii asti perällä meidän ihmisten listan. Joten tämä tulee hyvin nopeasti saada vähän tylsiä, joten haluan lopettaa tämän hetkeksi. Saanen muuttaa nopeutta olla paljon nopeampi. En muuttamalla algoritmia, olen juuri tekemässä animaatiota tapahtua nopeammin. Silti kupla lajitella, sama algoritmi, mutta nyt voit nähdä paljon nopeampi kuin sanallinen esittely että suurin elementit ovat todellakin kuplivat ylös. 

Sivuhuomautuksena, nämä pikku neliöt alareunassa vasemmalla ja alhaalla oikealla ovat vain pieniä muistutuksia siitä, kuinka monta vertailua teet. Mutta nyt voimme keskittyä pyramidin, joka on muotoutumassa, ja siellä se menee. Pienin elementti on vasemmalla, suurin oikealla, ja kaikki muu siltä väliltä. Nyt sen sijaan katsomaan valinta lajitella. Aion mennä eteenpäin ja iski Seis. Aiomme saada uusi satunnainen joukko baareja. Valinta lajitella, Recall, kulkee listan uudestaan ​​ja uudestaan ​​ja uudestaan, nyppiminen ulos pienin elementti. Joten tässä on valinta tavallaan. Näyttää siltä, ​​että on vähemmän töitä tapahtuu nyt, koska emme verrataan pareittain mutta me vain eräänlainen cherry picking pienin elementtejä oikealta vasemmalle. Se kesti hyvin vähän aikaa, joten siellä kahtiajako jo. Vain koska algoritmi on sanottu n potenssiin aikaa, kuten kupla lajitella ja kuten valinta lajitella, nämä ovat oikeastaan ​​pahin käyntiaikoja. Esimerkiksi tapauksessa, sanokaamme, valinta lajitella, Olen itse olen valinnut pienin ihminen ja laittaa hänet tänne, Sitten teen sen taas, niin teen sen taas, mutta oli hieman optimointi voisin tehdä. 

Heti kun muutin numero 1 täällä - Sammy tässä tapauksessa - mitäs minun pitää tehdä hänen kanssaan sen jälkeen? >> [Opiskelija] Jätä hänet. Jätä hänet, eikö? Mitään. En tarvitse koskaan puhua Sammy uudelleen, koska jos olisin valinnut pienimmän alkion ja laittaa hänet tänne, miksi tuhlata aikaa menossa loppuun minun koko lista? Seuraavalla iteraation haluan tosiasiallisesti liikkua vain numero 2, vain numero 3. Joten todellisuudessa, en ollut tekemässä n asioita n kertaa. Tein n asioita, niin n - 1 asioita, niin n - 2 asioita, niin n - 3 asioita, sitten n - 4, piste, piste, dot. Meillä on hieman geometrisen sarjan, mikä juuri tarkoittaa lisäät ylös asteittain pienempiä numeroita. Ei n + n + n + n, mutta n + 7 + 6 + 5 + 4 + 3 + 2 + 1. Ja mitä se yleensä toimii osoittautua - Aion sotkea minun aluksella täällä vain hetken - että menee treenata olla jotain n (n - 1) / 2 jos me vain eräänlainen katsaus takana matematiikka kirja, jossa sinulla on kaikki huijata levyt varten kaavojen. Jos olet vain lisäämällä jotain n + n - 1 + n - 2, se toimii olla jotain tällaista. Ja jos me vain eräänlainen moninkertaistaa tämän, joka on n: n potenssiin miinus N / 2. Sanoin n potenssiin, vaikka, ja se on koska olin tavallaan ottaa henkinen oikotie koska todellisuudessa n potenssiin miinus N jaettuna 2 on todellakin totta askelmäärä että algoritmi valinta Lajittele veisi jos todella lasketaan ylös kaikki nämä vertailut ja kaikki pikku kiireinen työ olimme tekemässä. Mutta rehellisesti, kun n saa olla kuin miljoona tai miljardi, joka hitossa välittää Jos teet miljardin neliön miinus miljardi jaettuna 2? Miljardia squared on valtava määrä. Voit ottaa toisen miljardin pois sitä - n. Se ei ole niin iso juttu. Joten isompi numerot saavat, vähemmän tärkeitä nämä alemmat järjestettyä ehdot ovat. Ketä kiinnostaa, jos jaat 2 jos puhut quadrillions numerot vaiheita? 

Joten yleensä tietojenkäsittelyasiantuntijat taipumus heittää pois kaiken, mutta suurimmat aikavälillä, ja me vain eräänlainen yksinkertaistaa maailmaa ja sanoa, että algoritmi kesti noin n potenssiin vaiheita. Tuo käyntiaika algoritmin. Joten me palaamme tähän vain hetki joitakin konkreettisia esimerkkejä, mutta nyt se on eräänlainen intuitiivinen motivaatio juuri yksinkertaistamalla maailman ja puhumme tärkein eikä niinkään joutumassa kaikki nämä fancy kaavat. Joten se oli valinta lajitella, ja saimme hieman onnekas siellä. Katsotaanpa paikoilleen lajitella. Anna minun mennä eteenpäin ja aloittaa tämän yhtä hyvin. Nyt huomaa malli, joka tapahtuu on hieman erilainen, ja aloitimme satunnaislukuja, mutta jos me todella laskea portaiden lukumäärän pahimmassa tapauksessa Jos lista alkoi täysin oikeassa järjestyksessä, me kestäisi vain n toimet toteuttaa mahdollisimman paljon. 

Mutta jos luettelossa olivat todella taaksepäin - esimerkiksi tässä tapauksessa täällä - Sitten huomaa meillä on todellakin tehtävä paljon enemmän työtä tässä asiassa. Ja se olisi sellainen tunne sinua, kuten tässä on kaikenlaista valmistusta kovemmin saada ne pienet elementit vasemmalle, ja se johtuu siitä saimme epäonninen. Luettelo lajitellaan vahingossa taaksepäin. Sen sijaan insertiovektorilla sort jos me matkia mitä teimme meidän ihmisten täällä aloittamalla kaikkien kanssa lajitellaan ja käynnistä, se on aika hyvä algoritmi, eikö? Se on jo itse asiassa, lajitellaan. Joten yritä tiivistää kuinka paljon aikaa näitä asioita otetaan yhteyttä ottamalla käyttöön vain vähän ammattikieltä tai merkintää, joka on todella paljon yksinkertaisempi kuin fanciness sellaista ehdottaa. Tämä juttu täällä, tämä iso O ruudulla, mitä tietojenkäsittelytieteessä yleensä käyttää kuvaamaan pahimmassa tapauksessa käyntiaika algoritmi. 

Jälleen jota pahimmassa tapauksessa se on täysin kontekstisidonnaisia. Mitä me tarkoitamme pahimmassa tapauksessa kokonaan vaihtelee ongelmasta puhumme. Mutta kyse lajittelun, mikä on pahin mahdollinen skenaario? Kaikki on taaksepäin, koska se vain tuntuu, että merkitsee paljon työtä meille. Olen jotted alas muutamia algoritmeja, jotka olemme nähneet tähän mennessä: lineaarinen haku, binäärihakupuu kuten kanssa puhelinluettelosta tai paperinpaloja, Sitten kupla lajitella, valinta lajitella ja lisäys lajitella kuten näimme meidän ihmisten, ja sitten 1 muu, joka on lopulta olemaan nimeltään yhdistää tavallaan. Joten lineaarinen haku pahimmassa tapauksessa, kuinka monta askelta kestää löytää numero 7 jos on olemassa n ovia kuten Sean pinnoitettu? >> [Opiskelija] N. N. Niinpä aiomme kirjoittaa ison O n. Menen vain täyttää joitakin aihioita. Tämä on vain ruudukon aihioita. Mutta parhaassa tapauksessa lineaarista hakua, 7 olisi ollut aivan alussa luettelon ja Sean ehkä ovat alkaneet etsiä alussa luettelosta. Joten jos käytät lineaarista hakua ja vain tarkistaa vasemmalta oikealle tai ehkä oikealta vasemmalle - he vastaavat - parhaassa tapauksessa kuinka monta askelta voisi lineaarinen haku, kuten Sean algoritmi toteuttaa? Vain 1 askel. 

Joten aion sanoa, että se omega merkintää. Tämä on vain pääkaupunki omega. Omega on vain seksikäs tapa sanoa Parhaassa tapauksessa käyntiajan. Joten parhaassa tapauksessa käyntiaika on yhdessä vaiheessa tai jatkuvasti useita vaiheita - 1 tässä tapauksessa - mutta pahimmassa tapauksessa iso O, se on todella n askelta. Ja tämä tässä, theta, emme oikeastaan ​​ole menossa katsomaan juuri nyt. Se ei ole merkitystä tässä esimerkissä. Mutta nyt Kokeillaan binäärihakupuu. Pahimmassa tapauksessa binäärihakupuu, kuinka monta askelta se aikoo ryhtyä löytääkseen numero 7 tai mitä etsimme? >> [Opiskelija] log n. Vielä menossa ottamaan log n, koska aivan kuten Alex sai epäonninen kun me todellakin käyneet läpi ongelmaa suunnitelmallisesti ja hän ei löydä numero 7, kunnes aivan viime oven hän katseli, vaikka oikeudenmukaisuus, hän sai heittää pois tiettyjä ovia matkan varrella, binäärihakupuu pahimmassa tapauksessa on ajoaika log n. Ja vielä, että puhuu tästä jakamalla ja valloitusta. Mutta entä parhaassa tapauksessa? Ja Alex todella kokenut, että parhaassa tapauksessa oikeassa, kun hän tuli lavalle. Kuinka monta askelta ei joka toteuttaa binäärihakupuu? >> [Opiskelija] 1. 1, vain koska hän sai onnekas. Mutta se on hienoa, koska omega viittaa parhaassa tapauksessa skenaarioita, Parhaassa tapauksessa tuloa, vaikka se on vain satunnainen tyhmä onnea. 

Nyt tämäkin aiomme juuri sellainen Jätä tyhjäksi nyt. Entä nyt kupla lajitella? Pahimmassa tapauksessa kupla lajitella, kaikki on käänteisessä järjestyksessä, joten meidän täytyy tehdä paljon kuplivaa. Mutta kuinka monta askelta on joka vie pahimmassa tapauksessa? >> [Opiskelija] N potenssiin. Tämä oli n potenssiin, koska jos ajattelee sitä, jos lista on täysin taaksepäin - 8 on täällä, 1 on täällä - koska asia alkaa kupla, numero 8 tulee näin liikkua, näin, Näin tämä tapa, mutta jossa on numero 7 pahimmassa tapauksessa? Tässä hän on yhä tuolla. Joten meidän täytyy tehdä se uudestaan ​​ja uudestaan. Ja siitä saamme n askelta, niin n - 1 vaiheet, niin n - 2 askelta. Ja jos otat minun sanaani - että jos sellainen moninkertaistaa sen, Se on suunnilleen n: n neliön lopulta joidenkin muiden ehtojen että me vain sivuuttaa nyt - sitten pahimmassa tapauksessa kupla tavallaan on n potenssiin, antaa tai ottaa. Mutta entä parhaiten tapauksessa kupla lajitella? Mikä on paras skenaario? Kaikki numerot ovat järjestetty jo. Ja mikä oli heuristinen käytin, temppu käytin, ymmärtää, että olisin tehnyt mitään työtä, ja voisi näin ollen lopettaa aikaisin? [Opiskelija] Tarkista se kerran. >> Tarkista kerran. Mutta mitä teen matkan varrella? Olin pitää kirjaa kuinka monta swap tein. Ja tajusin, jos en ole laskenut mitään swap minun sormet, niin olen tehnyt mitään työtä. En todellakaan pitäisi yrittää tehdä mitään työtä jälleen, joten voin vain lopettaa. 

Joten paras jos kupla lajitella, kun luettelo on jo järjestetty, mitä sanoisit Omega notaatio on, parhaimmassa tapauksessa käyntiaika? Se on vain N. Meidän täytyy tehdä työtä, mutta meillä on vain tehtävä 1 kävelymatkan verran työtä. Ja tässäkin aion jättää tämän osan tyhjäksi. Ja nyt valinta lajitella. Valinta sort oli minulle nyppiminen pienin ihminen uudestaan ​​ja uudestaan. Ja mitä me sanomme käyntiaika se oli? Se oli n neliö pahimmassa tapauksessa. Ja valitettavasti, parhaassa tapauksessa se on myös N potenssiin koska minulla ei ole sellaista kaikkitietäviä näkymä koko maailmassa; Tiedän vain, kun koko iteraation että olen todellakin löytänyt pienin ihminen. Joten valinta tavallaan eräänlainen imee mielessä, mutta ylösalaisin on se eräänlainen intuitiivinen. Se on melko helppo koodata ylös, koska kaikki mitä tarvitsee tehdä on kirjoittaa pari sisäkkäisiä silmukoita, tyypillisesti, että menee läpi etsimässä pienimmän alkion ja sitten laittaa pienin elementti, johon se kuuluu lopussa luettelosta. Joten tässä myös siellä tulee olemaan kompromissi. Aikaa se vie sinut ajattelemaan ja todella kehittää jotain kirjoittaa koodia voisi hyvin viedä enemmän aikaa, jos haluat parempaa algoritmia ja nopeamman suorituskyvyn. 

Mutta jos todella juuri sellainen koodiin jotain nopeaa ja likainen ja juuri sellainen ottaa typerin mahdollinen idea voit ajatella, jotka voivat viedä sinut muutaman minuutin koodia, mutta suuria tietomääriä algoritmisi voi kestää tunnin ajaa. Ja vaikka minä tutkijakoulussa joskus tehdä näistä kompromisseja. Olisi 3am, yritin analysoida erittäin suuri tietokokonaisuutta turvallisuuteen liittyvät tutkimus tein, ja se oli joko viettää 5 minuuttia säätämistä minun ohjelma analysoida tietoja ja mennä nukkumaan tai viettää 8 tuntia saada se juuri oikea, joten se toimii heti ja mennä nukkumaan. Ja niin siellä se tavallaan tietoisen päätöksen. Vähemmän kehityksen aikaa, enemmän unta. Jälkeenpäin en luultavasti pitäisi kannustaa, että kun tavoitteena tässä on optimoida koodin laatu, mutta sekin todellisessa maailmassa on hyvin kohtuullinen kompromissi. Vähemmän aikaa, vähemmän suorituskykyä tai päinvastoin. Joten tässä meillä vihdoinkin mahdollisuus puhua theta. Theta merkintätapa on jotain tietojenkäsittelyasiantuntijat voi tuoda esille keskustelun kun iso O-ja omega sattuvat olemaan sama. Sanot theta todella lähettää viestin, että tämä on tällainen tiukka sidottu. Ei ole väliä onko skenaario on hyvä tai huono, se on n: n potenssiin. Joten se ei vain ole merkitystä näitä tarinoita täällä. Insertion sort on viimeinen me katsoimme, jossa olin juuri laittamalla jokaiselle oikeaan paikkaan. Parhaassa tapauksessa mikä oli käyntiaika paikoilleen tavallaan kuin näimme sen täällä? [Opiskelija] Parhaassa tapauksessa? >> Parhaassa tapauksessa. 

Se oli N, koska parhaassa tapauksessa kaikki lajitellaan, ja Sammy ja kukaan muu todella oli liikkua ollenkaan. He olivat jo niiden oikeaan paikkaan. Joten insertion sort parhaassa tapauksessa, tässä tapauksessa n.. Mutta pahimmassa tapauksessa se on eräänlainen n: n neliö. Miksi? Jos lista ihmisten on käänteisessä järjestyksessä, Minä ensin aloittaa numerolla 8 ja asetan hänet oikeaan asentoon, mikä on täällä. Olen sellainen siirtyä puolelle. Nämä kaverit ovat lajittelemattomina, hän on lajiteltu. Mutta nyt satun löytää kuka seuraavaksi? >> [Opiskelija] 7. 7 pahimmassa tapauksessa, koska se on päinvastaisessa järjestyksessä. 

Joten tässä on 7. Mistä 7 kuuluu? Ehdottomasti takanani. Mutta nyt 7 todella kuuluu ei heti takanani mutta takana numero 8, joten minun täytyy sanoa, "Anteeksi, numero 8, voitteko siirtää tällä tavalla "Tehdä tilaa 7?" Nyt olen kohtaavat 6. "Anteeksi, numero 8 ja numero 7, voit siirtyä tehdä tilaa 6?" Eli toisin sanoen, lisäys lajitella, vaikka en tee paljon liikettä, ihmiset takanani tekevät paljon työtä, ja se on pakko maksaa joku kerta. Se tulee maksamaan tietokoneen aikaa. Joten jos insertion sort vielä kärsiä. Jos aloitat laskemalla kokonaismäärä vaiheita, päädymme lyömällä karkeasti n syrjätty koska nämä kaverit täytyy tehdä tilaa ihmisen lisätään takaisin tähän luetteloon. Ja niin tässä tapauksessa theta ei vain soveltaa erityistä tarinaa käsillä. Siinä kaikki kiva ja hyvä. Meillä on näitä 3 eri tapoja puhua käyntiaika. Mutta mitä tämä oikeastaan ​​tarkoittaa reaalisesti jos todella yrittää koodata jopa algoritmi? 

Saanen ehdottaa, että siellä on vieläkin parempi algoritmi siellä että itse on joitakin kompromisseja. Aiomme kutsua yhdistää lajitella, ja se on tavallaan tämän maagisen algoritmin että vain toimii nopeammin jotenkin, ja se on niin helppo ilmaista, ainakin pseudokoodilla. Täytäntöönpano algoritmin merge sort tulee olemaan seuraava. Kun olet antanut n elementit - n numerot, N ihmisiä riippumatta - ensimmäinen siellä järki tarkistaa. Jos n on pienempi kuin 2, yhdistää tavallaan vain pysähtyy. Se palaa, niin sanoakseni. Miksi lopetat jos n on pienempi kuin 2? >> [Äänetön opiskelijan vastausta] Oikea. Ja jälleen, n ei ole numeroa luettelossa, n on koko lista. Jos n on pienempi kuin 2, se tarkoittaa, että luettelo on joko 1, missä olet ilmeisesti lajitellaan jos se on 1 numero, tai 0, jolloin mikään ei lajitella, joten tarvitsemme tällaista perustapaus. Jos lista on niin lyhyt, että siellä on vain mitään tekemistä, kirjaimellisesti älä tee mitään. Return. Muuten lajitella vasen puoli elementit, sitten lajitella oikealla puolella elementtejä, sitten yhdistää 2 lajiteltu puolikkaat. 

Tällainen tuntuu hieman huijata, jossa pyydän teitä miten lajitella elementtejä ja sanot, "Lajittele vasen puoli, lajitella oikea puoli." Olen kuin, "Okei. Miten lajitella vasen puoli?" "Lajittele vasen puoli vasen puoli, lajitella oikea puoli vasemman puolen, ja sitten tehty." Olet sellainen syklisesti määritellä mitä tarkoittaa lajitella, mutta näyttää siltä, ​​että on todella loistava tässä tapauksessa. Se ei ole hyvä tämä noidankehä, joka ei lopu koskaan koska se ei pääty siihen, kun? >> [Opiskelija] Kun tulet 1 asia. Kun tulet 1 asia. Joten vaikka saatat aloittaa 8 henkilöä ja sanon, "Lajittele vasen puoli näistä ihmisistä, nämä 4 ihmistä, "sanon," Miten lajitella vasen puoli? " "No, lajitella 2 täällä." Ja sitten olet kuin "Okei, hienoa." "Miten lajitella vasemmalla puolella nuo ihmiset?" "Juuri lajitella tätä 1 henkilö täällä." Mikä loistava ilmestys nyt? Minun täytyy lajitella 1 henkilö. Valmis. Minulla ei ole tehdä mitään työtä. Mutta nyt minun täytyy selvittää tämä henkilö, mutta he yksi henkilö, ei ole mitään tekemistä. 

Joten taika ilmeisesti on tässä kolmannessa vaiheessa: yhdistää lajiteltu puolikkaat. Joten yhdistää tavallaan vie tämä loistava oivallus, että jos rikot iso ongelma alas osaksi 2 pienempää, identtisesti kokoinen ongelmia ja sitten vain eräänlainen liima pienempiä ratkaisuja yhdessä lopussa, Ehdotan, että voimme tehdä paljon, paljon parempi [napauttamalla ääni] kuin mikään valinta lajitella tai insertion sort. Olen itse ollut piittaamatta, että puoli tuntia, mutta en todellakaan tiedä mitä tapahtuu ulkopuolella tänään. [Surinaa] [naurua] Joten jos voimme nähdä tätä vähän apua ystävämme Rob Bowden. On 2 suuria askeleita prosessissa merge sort. Ensinnäkin, jatkuvasti jakaa luettelon kupit kahtia kunnes meillä on nippu luetteloita vain 1 kuppi niihin. Älä huolestu, jos luettelo sisältää parittoman määrän ja et voi tehdä täysin puhdas leikkaus välillä. Aivan mielivaltaisesti valita mikä lista sisältää ylimääräisiä kupin sisään Joten jakaa näitä listoja. Nyt meillä on 2 luetteloita. Nyt meillä on 4 luetteloita. Nyt meillä on 8 luettelot yhden kupin kussakin luettelossa. Niin, että se vaihe 1. Vaiheessa 2 me toistuvasti yhdistää paria luetteloiden avulla yhdistämisen algoritmia opimme ennen. Yhdistyminen 108 ja 15 päädymme luettelon 15, 108. Yhdistyminen 50 ja 4 päädymme 4, 50. Yhdistyminen 8 ja 42 päädymme 8, 42. Ja yhdistämällä 23 ja 16 päädymme 16, 23. Nyt kaikki luettelot ovat kooltaan 2. Huomaa, että kukin 4 luetteloiden on lajiteltu, jotta voimme aloittaa yhdistämällä paria luetteloiden uudelleen. Yhdistämällä 15 ja 108 sekä 4 ja 50 me toteuttaa ensin 4, sitten 15, sitten 50, sitten 108. Yhdistyminen 8, 42 ja 16, 23 ensin ottaa 8, sitten 16, sitten 23, sitten 42. Nyt meillä on siis vain 2 luettelot koko 4, joista kukin on järjestetty. Joten nyt me yhdistää nämä 2 luetellaan. Ensin otamme 4, niin otamme 8, niin otamme 15 ja 16 ja 23 sekä 42 ja 50 ja 108. Ja olemme tehneet. Meillä on nyt lajiteltu luettelo. 

Rob oli eräänlainen hyödyntää jotain, että emme ole vielä tehneet. Ehdotettiin, mutta emme todella tehdä sen. Hän tekee jotain fyysisesti kupit joka viittaa hän vietti jonkin resurssin lisäksi aikaa. >> [Opiskelija] Space. >> Se oli tilaa. Se, että hänellä oli tällainen kahden tason taulukko, jossa hän oli tilaa täällä ja tilaa täällä todella ymmärtää, että hän käyttää kaksi kertaa niin paljon tilaa koska kaikki meidän algoritmeja toistaiseksi - lisäys lajitella, kupla lajitella tai valinta lajitella - mutta hän oli hyödyntäen tätä ylimääräistä tilaa eräänlainen siirrellä edestakaisin pitäen asiat järjestyksessä. Ja vaikka se tuntuu saimme järjestetty luettelo, että tuntui kuin se kesti jonkin aikaa. Todellisuudessa Rob teki oli juuri tämä algoritmi. Aluksi hän otti ongelman koko n, jaettu sen vasen puoli ja oikea puoli. Silloin hän muutti kupit. Sitten hän toisti, että prosessi. Hän jakoi 4 tulee 2 sarjaa 2 tänne ja tänne. Sitten hän toisti prosessi ja jaetaan 2 tulee 2 sarjaa 1 kussakin eri kupit. Ja siitä loistava tilaisuuden tullen. Tuossa vaiheessa tarinan, Rob oli 8 luettelot koko 1, jotka kaikki järjestetty jo. 

Joten mitä hän jatkaa tehdä? Parittainen hän otti tämän järjestetty luettelo, ja tämä lajiteltu luettelo ja yhdistettiin ne. Sitten hän otti tämän yhden ja yhdistettiin ne, niin tämä yksi ja yhdistettiin ne, Sitten tämä yksi ja yhdistettiin ne. Ja mitä sitten hän teki seuraavaksi? Hän sitten uudelleen yhdistyivät isompi luettelot ja sitten uudelleen yhdistyivät isompi luettelot. Ja jos ajattelet tästä juuri intuitiivisesti nyt, mitä hän oikeasti tekee? Hän oli jakamalla ongelma puoli, on puoli, on puoli, että puoli saadakseen nämä tosi pieni luettelot. Sitten hän oli tavallaan yhdistyvät double, double, double, double. Niinpä hän teki kaksi kertaa niin paljon työtä kuin olemme nähneet tähän mennessä mitään mukana hajota ja hallitse, mutta no big deal. Kaksinkertainen työ ei ole niin iso juttu. Se on vain vakio. Ja aivan kuten meidän aritmeettinen lauseke ennen, olen juuri menossa yliviivata vakio tekijät kuten kertaa 2. Ketä kiinnostaa? Jos se on 2 miljardia kertaa 2, että on vielä paljon vaiheita. Joten tämä yhdistäminen vaihe näyttää olevan keskeinen oivallus. Kävellään kautta juuri numeerisesti ennen - Sepä ei saa jatkaa vielä. Kävellään kautta numeerisesti vain todella nähdä miten tämä soittaa ulos. Tämä on useimmiten vain pienen köyhän miehen animaatio. Mennään ehdottaa tätä. Käyntiaika merge sort - meidän täytyy vain tapa puhua tästä. Tämä ei ole matematiikkaa, tämä on vain eräänlainen ytimekkään tapa ilmaista itseämme. Joten T edustaa aikaa ja n edustaa mitä? >> [Opiskelija] koko - 

[Malan] koko ongelman, ihmisten määrä. Joten olen väittäen käyntiaika lajitella n ihmisiä tulee olemaan 0 aikaa jos n on pienempi kuin 2, koska jos sinulla on 1 kuppi tai no kupit, sinulla ei ole mitään lajitella. Mutta yleisemmin, aion ehdottaa, että käyntiaika lajitella n osia tulee olemaan se aika lajitella vasemmalle puoli plus oikea puoli plus - mitä tämä ylimääräinen + n? >> [Opiskelija] Merge sort. [Malan] Se on oikeastaan ​​sulautuvat, koska jos sinulla on n / 2 alkiota täällä ja sinulla on n / 2 alkiota täällä, kuinka paljon aikaa se kestää yhdistää ne? Aivan kuten Rob, sinun täytyy nyppiä tämä tänne, ehkä nyppiä tänne, nyppiä tänne, nyppiä tänne, katkomaan tänne. Sinun täytyy koskettaa jokaisen kupit kerran. Ja jos siellä on 4 kuppia ja 4 kupillista, eli 8 kupillista tai yleisemmin 8 N kuppia. Joten yhdistäminen askel voimme ilmaista kuin n, ja että kirjaimellisesti liittyy monta kertaa Rob fyysisesti kosketti yksi niistä Styrofoam kupit. Joten nyt tehdä mielivaltaisen esimerkin. Jos on 16 kuppia, mitä ajoaika lajittelu käyttäen Rob algoritmi, 16 kuppia? Se on 2 kertaa aikaa kuluu lajitella 8 kuppia koska meillä on 8 kuppia täällä, 8 kuppia täällä. En tiedä, kuinka kauan se kestää, joten olemme yleistäen sen t tällä hetkellä. Kuka tietää, mitä se on? Mutta nyt voin tavallaan rekursiivisesti tai toistuvasti kysyä saman kysymyksen. Kauanko kestää lajitella 8 kuppia? 8 kupillista aion sanoa vie aikaa kuluu lajitella 4 kupillista plus 4 kuppia, sitten yhdistämällä ne yhteen. Hieno. Olemme joutumassa aikana jo. Kuinka kauan kestää lajitella 4 kupillista? Aika kuluu lajitella 4 kupillista on 2 kuppia plus 2 kuppia lajittelun lisäksi sulautuvien prosessia. Hieno. Kuinka kauan kestää lajitella 2 kuppia? 2 kuppia on aikaa kuluu lajitella 1 kuppi plus aika kuluu lajitella toiseen kuppiin plus paljon aikaa se vie yhdistämistä, joka on vain 2. 

Hieno. Viimeinen kysymys. Kuinka kauan kestää lajitella 1 kuppi? Tässä on perusskenaariossa että ennustettu olimme osuma aiemmin. Se, että se ei ota työtä lainkaan lajitella pienin ongelmista tarkoittaa, että nyt tavallaan alakoulussa tyyli, voimme vain mennä aloittaa kytkemällä näitä numeroita takaisin sisään Tiedämme nyt, mitä T 1 on, niin voin kytkeä 0 T 1. Se antaa minulle vastaus T 2, jonka sitten voi kytkeä ylempänä. Se antaa minulle T 4, jonka voin kytkeä ylempänä. Se antaa minulle T 8, jonka voin kytkeä ylempänä. Ja jos minä itse tehdä, että matematiikka kytkemällä näitä vastauksia, Sitten saat T 16 on 64. Ja mitä 64 edustaa? Jos T on 16, joo, se on 16 kertaa 4. Olen siis väittävät nyt, että käyntiaika tämä asia sanottu yhdistää sort - ja tämä tulee olemaan fanciest ja niistä olemme nähneet tähän mennessä - aiotaan kutsutaan n log n sillä kuinka monta kertaa voi ryöstää jakaa koko joukko kupillista puoli? Log n. Se on sama kuin puhelinluettelon esimerkissä se on sama kuin itse laskenta esimerkin. 

Kuinka monta kertaa voit jakaa jotain puoli? Kuitenkin on olemassa tämä yhdistäminen askel. Saatat joutua jakaa kupit osaksi puoli uudestaan ​​ja uudestaan ​​ja uudestaan, mutta joka kerta olet menossa täytyy yhdistää. Ja me sanoimme aiemmin, että sulautuvan n kupit kestää n askelta koska olet nyppiä pois cup, nyppiä pois kuppi, ja sinun täytyy koskettaa jokaista kuppi kerran, aivan kuten Rob teki. Eli jos teemme jotain log n kertaa ja teemme n asioita kunkin iteraation jokainen näistä halvings, meillä on n kertaa log n. Joten jos me kytkeä 16 tässä esimerkissä, 16 kertaa log 16 - älä ole huolissasi, miksi näin on nyt, koska en ole kiinnittänyt Base - mutta log pohjan 2 16 on 4, 16 kertaa 4 on 64. Mutta sitä vastoin, jos olisimme käyttäneet kupla lajitella tai valinta lajitella tai lisäys lajitella kanssa 16 numeroa, mitä käyntiaika on jos n on 16? Se olisi 16 potenssiin, joka on 256, joka vaikka et ole aivan seurannut matematiikka, 256 on suurempi kuin 64. Se on todella maaginen takeaway täältä. Ja ymmärtää, että työtä tällä pienissä esimerkeissä kun tahdon PSET tekee kaiken paljon enemmän intuitiivinen. Mutta mitä se oikeastaan ​​tarkoittaa kannalta tuntuu tämä algoritmi on tämä: Jos me todella katsoa merge sort täällä - haluan vetää sitä tässä ikkunassa täällä - Tämä on hieman erilainen esimerkki, jossa meillä on kaikki 3 näistä algoritmeista - kupla, valinta, ja yhdistää - vain vierekkäin. 

He ovat kaikki alkoi satunnainen baareja, ja se on hyvä. Kukaan ei perustavanlaatuinen etu yli muiden. Aion hetken napsauta jokaista näistä animaatioita - Käynnistä Start, Start - niin nopeasti kuin voin siten, että karkeasti, ne kaikki alkavat samaan aikaan, ja mennään mielestä kupla lajitella n Pahimmassa käyntiaika on mitä? >> [Opiskelija] N potenssiin. N potenssiin. Valinta sort pahin tapaus käyntiaika on? N potenssiin. Ja yhdistää sort on ilmeisesti - vaikka ei aivan noudata kaikkia matematiikka nyt, siitä tulee paljon enemmän intuitiivinen ajan - on, väitämme, n kertaa log n. Ja koska log n on ehdottomasti alle n. kerran meillä on suuria lukuja, n kertaa log n on pienempi kuin n kertaa n tai n neliöön. Joten mitä se tuntuu todella olla parempi algoritmi kannalta ajoaikaan, n kertaa log n sijasta n neliö? Täällä mennään. Valitse, klik, klik. 

Sitähän se tarkoittaa käyttää jotain merge sort. Meillä on hetki. Katsotaan mitä tapahtuu täällä. [Naurahtaa] Kenen rahaa on kupla lajitella? Se pikemminkin riippuu tulon joskus. Katsotaanpa. Tule. Tuntuu kuin hän kiinni. >> [Opiskelija] Mene, kupla lajitella! [Opiskelijat sorinaa] [Malan] Joo, joo. [Opiskelijat sorinaa] Mene, mene, mene! [Kaikki hurraavat] [aplodit] Joten nyt 1 viimeinen, lopullinen demo, jos se on vähän hankala wrap mieltäsi noin matematiikka tai tavallaan visualisoinnin siellä, voit itse kuulla nopeudet eri algoritmien eri tavoin. Tämä on animaatio joku teki tosiasiallisesti yhdistää kuulostaa prosessin vaihtava ja korkeus baareissa. Kuten näemme täällä, siellä on muutama enemmän lajittelualgoritmeja siellä, että ihmiset ovat ajatelleet. Tämä ensimmäinen tulee olemaan lisäys lajitella, ja tämä lentää läpi ja antaa sinulle kuultavissa tunteen siitä, miten nämä eri algoritmeja työtä. Tässä on lisäys tavallaan. [Elektroninen merkkiäänen] [Malan] Bubble sort. [Nopeampi sähköinen piippaus] [Malan] Selection sort. [Nopeampi sähköinen piippaus] [Malan] Merge sort. [Elektroninen merkkiäänen] [Merkkiäänen hidastaa] [naurua] [Malan] Gnome tavallaan. [Elektroninen merkkiäänen] 

Tämä on CS50. Nähdään ensi viikolla. [Aplodit ja hurraavat] 

[CS50.TV]