[Musiikki soi] DAVID J. MALAN: Okei. Joten tervetuloa takaisin. Tämä on CS50, ja on viikon lopussa kolme. Joten muistaa aiemmin useita viikkoja, olemme viettää melko vähän aikaa C, ohjelmointi, syntaksi. Ja se on aivan normaalia, jos olet vielä kamppailee Harjoitus 2, on hakkaa päätäsi seinään. Se on arvoituksellinen näköinen virheilmoituksia ja bugeja että ei aivan jahtaamaan. Koska varma, että vain Muutaman viikon kuluttua voit muistella asioita, kuten Caesar ja [? V-genair,?] ehkä jopa Crack, ja ymmärtää, miten pitkälle olet tullut lyhyen ajan kuluessa. Joten jos se yhtään lohduttaa, roikkua siellä nyt. Tänään kuitenkin alamme siirtyminen asioita korkeammalla tasolla. Ja alamme itsestään selvänä, että te tiedätte, miten ohjelma, tai ainakin alkaa että viihtyvyyteen. Ja alamme pohtia, miten voimme edetä ohjelmien suunnitteluun lisää tehokkaasti. Miten voimme edetä optimoimalla tehokkuuden algoritmit, ja yleensä ratkaista enemmän mielenkiintoisia ongelmia. Ja alkaa itsestään selvänä, että jos haluaisimme, voisimme koodata mihin tahansa esimerkkien meillä on mielessä. Joten tänään, emme kosketa näppäimistöä minkäänlaiseen koodia. Se tulee olemaan paljon korkeampi, ja lopulta noin ongelmanratkaisuun. Joten päästä tähän pisteeseen, haluaisin ehdottaa että seuraavat seitsemän suorakaide edustaa seitsemän ovien takana jotka ovat koko joukko numerot, joista on numero 50. Saanen projisoida tämä tästä näytön myös täällä. Ja ehdottaa, että meidän vapaaehtoisen auttaa löytämään minua numeron edessä Internet täällä nähdä. Tule ylös, loistokunnossa. Selvä. Mikä sinun nimesi on? JENNIFER: [äänetön] DAVID J. MALAN: Anteeksi? JENNIFER: Jennifer. DAVID J. MALAN: Jennifer. Okei, Jennifer. Hauska tavata. Tule ylös. Joten nämä tässä ovat seitsemän ovea, ja mitä Haluaisin sinun tekevän meille täällä, edessä kaikki luokkatoverit, on löytää meidät numero 50. Voit löytää useita, voit kurkistaa jokin näistä ovet yksinkertaisesti koskettamalla yhdellä ovet, ja se paljastaa sen numero. Ja katsotaanpa kuinka nopeasti Löydät meidät numero 50. 15. 16. 50. Hienosti tehty. Selvä. Aplodit Jennifer. [APPLAUSE] Selvä. Joten mikä oli strategian löytää numero 50? JENNIFER: Tuota, ajattelin ehkä jos - [Äänetön] DAVID J. MALAN: Oh. Anna se yksi toinen. Joten oli teidän strategia löytää numero 50? JENNIFER: Olen siis vain alkaa alkaa nähdä, mitä ensimmäinen numero oli, ja sitten ajattelin, ehkä jos he lajitellaan, minä vain pitää napauttamalla ylempänä? DAVID J. MALAN: OK. Ja näytämme löytäneen että on kyse. Vaikka nyt Taitat kerrokset vain vähän, ja haluat mennä eteenpäin ja paljastaa muiden ovien olet voinut valita? JENNIFER: Voi, rakas. DAVID J. MALAN: Ah. JENNIFER: Joten olen vain onnekas. DAVID J. MALAN: Sait onnekas. Selvä. Joten ei paha. Mutta se on mielenkiintoista oivalluksia, eikö? Jos oletetaan, ja teit saat, todellakin hieman onnekas siellä. Mutta jos oletetaan, että luvut olivat lajitellaan, voit olla täsmällisempi siitä, miten se vaikuttaa käytöstäsi? JENNIFER: Joten jos ne lajitellaan, I Ajattelin pienimmästä isoimpaan. DAVID J. MALAN: OK. JENNIFER: Tai jos tämä päätyi todella iso, sitten suurimmasta pienimpään. DAVID J. MALAN: OK. Joten suurimmasta pienimpään, tai pienimmästä isoimpaan. Mutta haluan ehdottaa, kai oli mennyt epäonninen, ja olettaa, että ne ei, itse asiassa, lajitellaan, kuinka moni ne ovet ehkä sinulla on ollut kurkistaa jäljessä, että pahimmassa tapauksessa? JENNIFER: Kaikki. DAVID J. MALAN: Kaikki. Joten yleistää, että n. Siellä sattuu olemaan 7, mutta katsotaanpa lisää yleisesti sanoa siellä n ovet näyttö tästä. Joten pahimmassa tapauksessa olisit katsoa taakse 7 ovien tai n ovet. Ja niin tämä todella on, se on vähän onnea tänään, mutta se on todella lineaarinen algoritmi lajittelee, vaikka olivat eräänlainen ohita ympärille. Onko tämä reilua? JENNIFER: Joo. DAVID J. MALAN: No, anna minun nähdä, jos Strategian muutokset jos muutan meitä meidän toinen esimerkki täällä 7 eri ovet. Samat numerot, mutta tämä kun ne lajitellaan. Minkä strategian täällä tulee olemaan, yrittää laittaa järkesi, mitä muut numerot olivat - JENNIFER: OK. DAVID J. MALAN: - aikaisemmin? JENNIFER: Aloitetaan ensimmäisen kanssa. DAVID J. MALAN: Okei. Aloita ensimmäinen. 4. Nyt jos olet menossa, ja miksi? JENNIFER: 4 on todella pieni. Joten jos he tavallaan ehkä pienin suurimpaan, sen pitäisi olla kaksi kertaa, ja -. DAVID J. MALAN: OK. Katsotaan, mikä luulet? JENNIFER: Kokeile viimeinen. Nice. DAVID J. MALAN: Erittäin hienosti tehty. Selvä. [APPLAUSE] DAVID J. MALAN: OK. Joten olet juuri tekemässä tätä hirvittävän, koska olet tekee sen hyvin. Joka jättää meidät pysty tehdä tiettyjä kohtia. Joten yrittää heittää takaisin tänne. JENNIFER: OK. DAVID J. MALAN: Erittäin hyvin tehty kuitenkin. Joten olet aloittanut alussa, näit, että se oli 4, sitten muutti loppuun. Mutta oletetaan, et onnekas siellä, ja kai 50 oli jossain muualla. Mitä kolmas vaihe on? JENNIFER: Mene takaisin alkuun. DAVID J. MALAN: Mene takaisin alkuun. OK, niin olisit koskettanut tämä ovi, joka oli 8. Selvä. Joten se ei ole 50. Missä olet tutkinut seuraavaksi? JENNIFER: Jos en tietävät lajitellaan. DAVID J. MALAN: Oikea. No, jos et tiedä ne on järjestetty - JENNIFER: Voi, ei tiedä, joo. DAVID J. MALAN: - mutta et ole tietää, missä 50 oli vielä? JENNIFER: Jatka vain. DAVID J. MALAN: Okei. OK. Jatkakaa. OK, että voin työskennellä. JENNIFER: OK. DAVID J. MALAN: Nyt, jos olet vain menossa pitämään menossa, mikä on sinun algoritmi taantunut peräytyminen. JENNIFER: lineaarinen -. DAVID J. MALAN: Se on eräänlainen lineaarinen. Mutta haluan ehdottaa, anna Laitan paikan päällä. Saanen päivität sivun. Sama numero, sama järjestely, Sama ovet. Mutta muistelen, että ensimmäinen päivä luokassa, kun me repäisi puhelinluettelon puolet, tavallaan, ja mikä oli Strategiamme on? JENNIFER: Aloita keskellä. DAVID J. MALAN: OK. Niin alkaa keskellä. Joten mene eteenpäin ja simuloida sitä. Aloita keskeltä paljastaa, että ovi. Joten numero 16. Joten mikä olisi vahva kaveri tehnyt, joka repi puhelinluettelon kahtia, päästä seuraavalle arvaus? JENNIFER: Mene tällä puolen. DAVID J. MALAN: Ja miksi oikealle? JENNIFER: Jos ne tavallaan pienin suurimpaan, sitten 50 olisi tuossa lopussa. DAVID J. MALAN: Hyvä. Täysin kohtuullinen. Joten kuten puhelinluettelossa, menet oikeutta eikä vasemmalle, mutta tässä on avain takeaway. Nyt voit heittää pois tai repiä irti, puolet tämän ongelman, jolloin et 7-ovet, mutta oikeastaan ​​vain 3. Mikä on noin puolet Ongelman laajuutta. Selvä. Joten nyt, mitä olisi tehdä, kun menet oikealle? JENNIFER: Eli 16 on edelleen melko pieni, suhteessa 50, joten ehkä yritän, kuten tämä. DAVID J. MALAN: Okei. 42. Okei, joten nyt mikä on sinun vaisto kertoo sinulle? JENNIFER: Voin heittää pois tämä ja sitten vain - DAVID J. MALAN: OK. Hyvä, voit heittää pois vasen puoli siellä. JENNIFER: - valitse tämä. DAVID J. MALAN: Ja oikea. JENNIFER: Joo. DAVID J. MALAN: Joten vaikka se on vaikeaa nähdä ehkä kun on vain 7 ovet, ajattele nyt, johdonmukaisuus algoritmi juuri sovellettu. Edellisessä tapauksessa teit onnekas, mikä oli hienoa. Mutta et käytä heuristista, Sanoisin. Käytit tavallaan vaistosi, ja tietäen se lajitellaan, jos ihan pieni alussa, luonnollisesti, olemme täytyy mennä enemmän oikealle. Mutta jossain mielessä, sinulla onnekas, koska ehkä tämä oli numero 100, ja ehkä 50 oli keskellä. Ehkä 50 oli vielä täällä. Mutta mitä teit hieman eri tavalla tällä kertaa oli, teit sama asia uudelleen ja uudelleen. Ja väitän, että mitä vain ei tosin vaikuttaa puhelimen kirjaesimerkkiin, on jotain paljon enemmän algoritmi, ja paljon yhtä erityistä cased. Paljon vähemmän vaistomainen. Joten loppujen lopuksi, miten kuvaat tehokkuutta Ensimmäinen algoritmi, missä meni vasemmalta oikealle, vs. Toinen algoritmi täällä? JENNIFER: Tämä olisi kuin, ehkä puolittaa tai jopa enemmän, joo. DAVID J. MALAN: OK, ehkä jopa enemmän. Katsotaanpa työntää hieman vaikeampi siitä. Mitä todella, jos jatkamme tätä logiikka, me varmasti puolittui käyntiaika tämän toisen algoritmin heittämällä pois puolet numeroita, mutta mitä teemme seuraavaksi iteraatio, kun Jennifer paljasti toinen numero? Puolitimme numerot jälleen ovensa. Ja mitä sitten teimme sen jälkeen, jos oli enemmän ovia pelata? Olisimme puolittaa ne ja uudelleen, ja uudestaan, ja uudestaan. Ja tämä oli aivan kuten te kaikki seisomaan klo ensimmäisellä viikolla luokka, puoli olet istuen, puoli teistä istuen, puoli olet istuen, kunnes yksinäinen sielu seisoi. Ja sanoimme, että ajoaika että useita vaiheita kesti oli suuruusluokkaa mitä? SPEAKER 1: [äänetön] DAVID J. MALAN: Eli logaritmi 2 n, tai vain yksinkertaisemmin, kirjaudu n. Joten jotain logaritminen. Ja kuvaaja ei ollut suora viiva että juuri huonommaksi, se oli tämä mielenkiintoinen käyrä, joka ei saada niin huono ajan. Joten pitää tätä ajatusta. Katsotaanpa kiittää Jennifer. Kiitos niin paljon tulossa ylös. Ja, yhden sekunnin. Ei Kirjoituspöydän lamput tänään, mutta me ei ole CS50 stressi pallot. JENNIFER: Jee. DAVID J. MALAN: Okei, tässä. Kiitos aiheutuu stressi täällä. Selvä. Katsotaanpa, jos emme voi nyt muodollistamiseksi hieman. Joten jälleen, mitä teimme oli pohjimmiltaan sama asia kuin teimme että ensimmäisellä viikolla. Mutta sen sijaan päättyvät vain lineaarinen algoritmi, jota on kuvattu aiemmin kuin tämä suora viiva, siitä, että jos laitamme yksi ovi näytölle ja Jennifer olisi täytynyt katsoa, ​​mahdollisesti, takana yksi ovi. Jos laitamme kaksi ovea, hän olisi näyttää takana kaksi ovea. Ja niin, oli tämä lineaarinen suhde koon ongelma, eli x-akselin, ja aikaa kuluu ratkaista y-. Mutta kuva olin viittaamatta aiemmin oli tämä vihreä viiva. Green tarkoituksella, koska se vain tuntui paremmalta. Teoriassa algoritmin, kun me teimme sen kanssa puhelinluettelosta, kun me teimme sen teidän kanssa laskenta toisiaan, ja Toisessa tapauksessa, kun Jennifer vain teki sen täällä, se oli tavallaan perustaltaan paremmin. Koska se ei ollut vain kaksi kertaa niin nopeasti. Se ei ollut edes neljä kertaa niin nopeasti. Se oli täysin riippuvainen siitä, mitä koko panos oli, kuinka monta toimiin se lopulta kesti. Ja niin tämä yksinkertainen ajatus, että me kaikki otimme itsestäänselvyytenä kanssa puhelinluettelosta, voidaan samalla tavoin soveltaa jotain tällaista. Ja tämä voisi olla rennosti tunnetaan, niin saatat kuvitella, hajoita ja hallitse. Ei toisin mitä teimme, tietenkin, kanssa puhelinluettelosta. Mutta pseudokoodit muistaa, oli tämä. Joten emme tee tätä uudelleen, mutta muistuttaa että ensimmäisellä viikolla, me kaikki nousi ja sitten puolet istahti, puolet istahti, puolet istahti. Tämä algoritmi toteutettiin hieman huijaaminen tavalla, että se ei ollut vain yksi minua laskenta, pohjimmiltaan tehokkaammin. Siinä tapauksessa, olin hyödyntäen toissijaisena luonnonvarana. Lajittele, useita suorittimia, useita aivot, useita älykkäitä ihmisiä huone auttoivat minua saada jotain lineaarinen jotain logaritminen, jostakin punaisesta jotain vihreää. Mutta tässä tapauksessa, Jennifer voi yksin pohjimmiltaan parannella suorituskyky hänen ensimmäinen algoritmi, uudelleen, vain ajatella vähän vaikeampaa. Ja nyt, kun on aika toteuttaa nämä asiat, mietitään mitä riviä koodia voit kirjoittaa niin että voit toistaa niitä uudelleen, ja uudestaan, ja uudestaan, tavallaan vuonna looping tavalla. Koska et aio olla ylellisyyttä, kuten Jennifer teki aluksi, että vain koko joukko jossittelua ja sanoa, hmm, jos tämä ensimmäinen numero on 4, haluan hypätä aina loppuun. Ooh, jos määrä on liian suuri, haluan liikkua mielivaltaisesti takaisin toiseen osaan. Huomaat, että se tulee olemaan paljon vaikeampaa virallistaa mitä me ihmiset itsestäänselvyytenä erittäin kohtuullinen heuristiikka, mutta tietokone on vain tekee mitä kerrot sen tehdä. Nyt tämä on erittäin mielenkiintoinen seurauksia. Tämä kuvaaja on tavallaan tarkoitus tavallaan hukuttaa visuaalisesti, mutta huomaa, jos on suora viiva tässä kuvaaja? Missä on lineaarinen kuvaaja jota me kutsumme n? No, se on tavallaan pohjaa kohti Kuvan, eikö? Joten kaikki olemme tehneet on olemme tavallaan zoomataan ulos x-akselin ja y-akseli yrittää saada tunteen siitä, mitä muita käyrät näyttävät. Ja erityispiirteet matemaattisten ilmaisuja tänään ei niin väliä paljon, mutta huomaa, että siellä on paljon algoritmeja, jotka ovat paljon huonommat kuin jotain, joka on lineaarinen. Itse asiassa n kuutioitu näyttää pahalta. 2 n näyttää pahalta. n potenssiin näyttää pahalta. Ja näemme, mitä joidenkin saattaa olla todellisuudessa tänään. Ja log n ei tunnu niin pahalta, mutta parempi n on logaritmi 2 n. Mutta te tiedätte, se olisi ollut vielä ihmeellisempää, jos Jennifer, tai jos, että ensimmäisellä viikolla, oli keksittävä jotain, joka on log log n. Eli toisin sanoen, on tämä koko erilaisia ​​mahdollisia ratkaisuja ongelmia, mutta siinäkin, ilmoitus mitä tulee tapahtumaan. Kun minä loitontaa, mikä näistä käyrät tulee olemaan ehdoton Pahin niistä ruudulla nyt? Joten n kuutioitu näyttää aika nyt huono. Mutta jos me loitontaa ja nähdä enemmän x ja y-akseli, joka tulee hallitsevat lopulta? Joten se todella osoittautuu, että 2 n, ja voit selvittää tämän vain kytkemällä jotkut yhä suuria numerot, ja näet, että 2 n todellakin saa isompi paljon nopeammin. Jos me todella loitontaa, 2 n algoritmi aivan perseestä. Siis tämä vie melko vähän aikaa tietokone vaihtuvuus kautta. Mutta näet ajan, erityisesti tulevaisuuden ongelma sarjaa ja jopa opinnäytetyöt, on tietosi set saa suuret, okei? Jopa ensimmäinen versio Facebook, kuin joukko ystäviä, ja rekisteröityneiden käyttäjien saivat suuret, voit lajitella puhelimen sen ja toteuttaa jotain lineaarista hakua, tai hyvin yksinkertainen lajittelu algoritmi, kuten näemme tänään. Sinun täytyy alkaa ajatella kovemmin ja vaikeampi näistä ongelmista. Ja tyyppisiä ongelmia paikoissa, kuten Facebook ja Google ja Microsoft, ja muut työtä on juuri nämä tavallaan iso tietojen kysymyksistä on yhä näinä päivinä. Selvä. Joten Jennifer menestys, että toinen algoritmi, rehellisesti, hän teki hämmästyttävän hyvin ensimmäisen kerran, mutta katsotaanpa kirjoittaa sitä onnea, jotta me voi tehdä tässä vaiheessa. Toisessa tapauksessa hän velkarahalla algoritmi, joka toistuu uudestaan ​​ja uudelleen, mutta hän otti itsestäänselvyytenä tiettyjä oletukseen, että annoimme häntä, mutta hän hyödyntää joitakin yksityiskohtia toisen kerran, että hän ei ole ensimmäisen kerran. Joka oli mitä? Tämä lista on lajiteltu. Joten kun luettelo on lajiteltu, me väittävät, että Jennifer pystyi tekemään pohjimmiltaan paremmin. 7 ovet, kyllä, ei ole niin kiinnostavaa, mutta kai se olemme 7000000 ovet. Log n on ehdottomasti menossa tehdä paljon, paljon nopeammin pitkällä aikavälillä. Mutta hän piti olla ovet lajitellaan häntä. Nyt otin vapauden tehdä se etukäteen tietokoneen näytöllä täällä, mutta olettaa, että Jennifer täytyi tehdä itse? Oletetaan, että ovet kyseessä edustettuina tiedot tietokantaan tai ystävät rekisteröity Facebook, tai kaikkia verkkosivuja Internetissä, jotka eri verkkosivustoja ehkä indeksoida tai etsi yli. Oletetaan, että olet juuri ollut raakadatan asettaa ja se jäi sinulle, tai Jennifer tehdä lajittelemalla? Se pikemminkin edellyttää, että me vastaamme kysymys, hyvin, kuinka paljon aikaa olisi ottanut Jennifer tai jopa minua, lajitella nämä numerot etukäteen, jotta että hän voisi hyödyntää sitä? Oikea? Koska vaikutuksia, on tietenkin jos se vie minut jonkin aikaa lajitella numerot, jotka helkutti kiinnostaa, että olet löytyy useita, kuten 50 niin nopeasti, kuten Jennifer tapauksessa, jos yli hukkua määrä kokonaisaika kesti lajittelemalla asioita etukäteen? Katsotaanpa, jos emme voi maalaa kuva täällä. Minulla on koko joukko enemmän stressiä pallot, jos se auttaa murtaa jään tänne. Ja jos et mielessä, me tarvitsevat seitsemän vapaaehtoinen - on, OK. Wow. Joten meidän ei tarvitse käyttää työpöytä valaisimet, miltä se näyttää. Selvä. Niin miten te kaksi edessä. Entä te kaksi kaverit takana. Niin, että neljä. Miten sinusta edessä viisi, kuusi ja seitsemän. Tuolla. Ystäväsi osoittaa sinua ulos, niin saat palkinnon. Selvä. Tule ylös. Ja miksi emme ole sinulle miehet ovat tulleet tänne. Aion antaa sinulle jokaisen numeron. Ja mennä eteenpäin ja järjestää itse identtisen mitä kuvattu ruudulla. [Interposing ÄÄNTÄ] DAVID J. MALAN: Oop, sorry. Bug. Selvä. No, tässä sitä mennään. Numero viisi. Numero kuusi. Yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän. Voi, tämä on hankala. SPEAKER 2: Minä saan vain -. DAVID J. MALAN: Good deal. Selvä. Kiitos osallistumisesta. [APPLAUSE] OK. Selvä. Joten meillä on neljä, kaksi, kuusi, yksi, kolme, seitsemän, viisi. Perfect joten meillä on seitsemän vapaaehtoisia täällä, jotka ovat yhtä leveä array, että me pelaamme kanssa aiemmin. Ja päätin seitsemän syistä joka on vain kätevä vähän. Ja aion ehdottaa ensin, että me lajitella nämä seitsemän vapaaehtoisia. Jos haluat, ensimmäinen, tervehtimään vaikka. Koska tämä tulee olemaan hankala useita minuutteja. Esitellä itsenne. GRACE: Hei, olen Grace. Olen toisen vuoden opiskelija Leverett House. BRANSON: Hei. Olen Branson. Olen fuksi Weld. GABE: Hei. Olen Gabe. Olen juniori Cabot. NEIL: Olen Neil. Olen fuksi Matthews. JASON: Olen Jason. Olen fuksi Greenough. MIKE: Olen Mike. Olen fuksi Grays. JESS: Olen Jess. Olen toisen vuoden opiskelija Leverett. DAVID J. MALAN: Erinomainen. Selvä. No, kiitos kaikille Vapaaehtoiset toistaiseksi. Ja haaste käsillä nyt on menossa olla tavallaan nämä kaverit, mutta sitten aiomme täytyy ajatella hieman kova, miten tehokkaasti me oikeastaan ne on lajiteltu. Joten ensin kokeilla tätä. Te voi nähdä toistensa numerot vain sijoittamalla kulmien ympäri. Mennä eteenpäin ja kestää muutaman sekunnin, ja lajitella itsenne pienimmistä jää suurin oikealla. Go. OK. Hyvä. Se oli todella hiton nopeasti. Nyt joku täällä, mikä oli algoritmi että nämä kaverit sovelletaan? SPEAKER 1: Korkeasta suurin. DAVID J. MALAN: OK. Ainakin suurin on todella tavallaan tavoite, mutta en ole varma, että se todella algoritmi. Ainakin suurin ei kerro minulle askel askeleelta mitä tehdä. Niin? SPEAKER 1: [äänetön] DAVID J. MALAN: OK. Joten jos näet henkilön pienempi kuin numerosi, sitten siirtyä oikea niistä. Niin, että nyt saada enemmän ilmeikäs, enemmän kuin algoritmi, koska voi sanoa, jos tämä, niin se. Joten meillä on jonkinlainen ehdollinen rakennelma. Ja nämä kaverit näyttivät tehdä muutamia kertaa, koska jotkut teistä muuttanut hieman ja etäisyyden. Joten oli oletettavasti jonkinlainen looping tapahtuu heidän mielessään. Mutta yritetään virallistaa että. Jos te voisi palauttaa takaisin Tämän järjestelyn. Katsotaan, jos emme voi virallistaa tämän bittinen, ja sitten kysyä, vain kuinka tehokas tämä on? Tietenkin, kun teemme tätä hitaammin, se tulee tuntea niin hyvää algoritmi, mutta katsotaan jos voimme laittaa sormet tarkka vaiheet. Joten te kaksi olette neljä ja kaksi. Tai sitten oikea tai väärä järjestys? Selvästi virheellinen. Joten vaihdoin. Nyt aion siirtyä sivuun ja sanoa neljästä kuuteen. Oletko oikea tai väärä? GABE: Oikea. DAVID J. MALAN: Oikea. Kuusi ja yksi? Ehei. Swap. Niin, että kaksi swap. Kuusi ja kolme? Ehei. Swap. Kuusi ja seitsemän? Näyttää hyvältä. Seitsemän ja viisi? JESS: [äänetön] DAVID J. MALAN: OK, vaihtaa. Ja lajitellaan. Selvä. Joten ilmeisesti ei, eikö? Joten oli enemmän tekeillä. Mutta tosiaan, nämä kaverit, vaikka vain vaistomaisesti. pidettävä liikkeessä. He eivät vain lopettaa, kun ne korjattu yksi ongelma. So. Itse aion olla tehdä sama asia. Aion olla tavallaan taaksepäin takaisin alkuun tämän ongelman tai alussa joukko ihmiset, aloitamme kutsuvan heitä. Ja nyt, mitä pitäisi minun algoritmi Toisessa läpiviennissä on? SPEAKER 1: Sama juttu. DAVID J. MALAN: Sama juttu. Ja tämä, olen alkanut pitämään, eikö? Heti kun löydät itsesi tekemässä sama asia uudestaan ​​ja uudestaan, se on tulossa enemmän kuin algoritmin ja vähemmän ihmisen vaisto. Joten nyt, tässä sitä taas. Kaksi ja neljä? Ei. Neljä ja yksi? Ah, siellä oli todellakin joitakin työtä on vielä tekemättä. Sillä ja kolme? Hyvä. Neljä ja kuusi? Kuusi ja viisi? Kuusi ja seitsemän? OK, nyt tehdään. OK, no. Minun täytyy mennä takaisin. Joten nyt taas, teemme tätä hieman tarkoituksella. Ja nyt siellä on vain yksi aivojen täytäntöönpanosta tämän algoritmi. Yksi CPU, jos haluatte. Ja suoraan sanottuna, se on ainoa resurssi aiomme saada. Ja kun emme mene takaisin näppäimistö ja on jotain C meidän hävittäminen, olemme vain ohjelman kirjoittaminen joka voi tehdä yksi asia kerrallaan. Sekä katsoo, nämä kaverit hetki sitten, me velkarahalla kollektiivista aivokapasiteetti kuten teitte kaverit viikolla nolla. Joten pitää tehdä tätä. Kaksi ja yksi. Kaksi ja kolme. Kolme ja neljä. Neljä ja viisi. Viisi ja kuusi. Kuusi ja seitsemän. Tehty? Joten olen, mutta anna minun pelata paholaisen asianajajana. Voin, tällainen tietokone, joka vain teki ohittamaan tämän joukko ihmiset, tietävät, että olen tehnyt? SPEAKER 1: No DAVID J. MALAN: Miksi? Mitä minun pitää tehdä, jotta päätellä ratkaisevasti, että olen tehnyt? Luultavasti yksi syöttö. Oikea? Koska kaikki Tiedän, että edellinen pass on, että korjasin virheen. Ja se tarkoittaa, ehkä siellä on vielä toisen virheen että minun täytyy korjata. Joten voin vain olla varma uudelleenrullaamalla, ja sitten tarkistaa, yksi kaksi, kaksi ja kolme, kolme ja neljä, neljä ja viisi, viisi ja kuusi, kuusi ja seitsemän. OK, nyt tein mitään työtä. Voin varmasti muistaa, että tein mitään työskennellä jotain muuttuja, kuten int. Soita se swap, ja jos swap on 0, kun olen tänne, ja se alkoi 0, niin Haluan vain olla tyhmä pitää käynnissä edestakaisin, tarkistaa uudelleen, ja uudestaan, ja uudestaan, eikö? Koska saat kiinni joissakin Tällainen päättymättömään silmukkaan. Joten kun siellä on 0 koronvaihtosopimukset, voimme väittää, että tämä algoritmi on todellakin täydellinen. Nyt, laita nimi tähän. Algoritmi, että ehdotan me vain täytäntöön on jotain kutsutaan kupla lajitella, sinänsä tunnettuja siinä mielessä, että numeroita, jotka ovat suurempia sellainen kupla tiensä ylös, tai jopa loppuun joukko numeroita. Mutta miten tehokas oli tämä algoritmi? Kuinka monta askelta minä fyysisesti on ottaa esimerkiksi lajitella nämä seitsemän ihmisiin? Neljä viisi? OK, liikaa on viime kädessä olemaan vastaus. Mutta silloinkin, tietty määrä ei ole niin kiinnostavaa. Katsotaanpa yleistää sitä n. Joten jos olisin n ihmisiä täällä, ja ne olivat, tavallaan, satunnaisessa järjestyksessä alussa, että alkuperäisessä järjestyksessä. No, kuinka monta askelta minun tarvinnut ottaa ensikierron? Se oli yksi, kaksi, kolme, neljä, viisi, kuusi, ja ne seitsemän henkilöä, joten se on seitsemän, kuusi -, niin se on n miinus yksi vaiheet ensimmäisen kerran. Nyt, kuinka monta askelta minun tarvinnut ottaa kun kelata? No, voisimme todella kaksinkertainen, jos halusimme, mutta nyt olen juuri menossa sanoa, okei, toinen n miinus 1. Joten n miinus 1 on menossa ärsyttävää seurata, joten katsotaanpa vain pyöristää ylöspäin hieman. Joten 2n vaiheet. Joten 14 vaiheet, antaa tai ottaa. Kuinka monta kertaa otan askel seuraavan kerran? No, se on 3n. todella. Ja nyt, pahimmassa tapauksessa Esimerkiksi kuinka monta kertaa olisin mennyt edestakaisin, edestakaisin, täytäntöönpanosta tämän algoritmin, vaihtamalla ihmiset jokaisen syötön, suunnilleen? Se on oikeastaan ​​n potenssiin, eikö? Koska pahimmassa tapauksessa voit sellaista ajattelevat tästä intuitiivisesti, vaikka se saattaa kestää hieman vähän aikaa upota sisään Pahimmassa tapauksessa, mitä olisi nämä seitsemän ihmistä näyttäneet, vuonna Järjestelyssä niiden numerot? Täysin taaksepäin, eikö? Ja vain simuloida, että mikä sinun nimesi olikaan? MIKE: Mike. DAVID J. MALAN: Mike? OK, Mike, voisitko liittyä minua täällä vain hetken? Oikeastaan ​​ei. Sorry Mike, katsotaanpa taaksepäin. Mikä sinun nimesi olikaan? NEIL: Neil. DAVID J. MALAN: Neil. OK, Neil, tulet minulle, jos et pahastu. Joten aion ehdottaa, vain yksinkertaisuus, että Neil on nyt hänen pahin mahdollinen tapaus. Mutta muistaa miten toteutetaan minun algoritmi. Olen vertaamalla, vertaamalla, vertaamalla, vertaamalla, vertaamalla, oh. Nyt nämä kaverit ovat poissa järjestyksessä, niin voin korjata. Joten te vaihtaa. Ajatelkaa nyt, kuinka paljon kauemmas ei Neil täytyy mennä? Se on suunnilleen n. Tiedäthän, se ei ole oikeastaan ​​n. Se on kuin, n miinus 1, mutta Saan harmissaan pitää kirjaa vähän numero, joten haluan vain kutsua sitä n. Joten jos Neil siirtyy askeleen maksimaalisesti kunkin aikaa, ja siirtyä Neil askeleen, Minun täytyy tehdä tämä todella ikävä pass edestakaisin, tämä on karkeasti Näin n askelta, yhteensä n kertaa, koska se vie minut että monet askeleen päästä Neil kaikki tapa, mihin hän kuuluu. Puhumattakaan kaikki muutkin, jos te olivat kaikki väärin tilata samoin. Joten soita kupla lajitella n potenssiin. Käyntiaika tämän algoritmin, suorituskyky tämän algoritmin tehokkuutta tämän algoritmin, meillä on vain kuvata enemmän yleisesti n potenssiin. Mikä on mukavaa, koska en voinut tehdä Sama esimerkiksi kahdeksan ihmistä, yhdeksän ihmisiä, miljoona ihmistä, ja että vastaus ei tule muuttaa. Joten jos te panisi pahakseni, katsotaanpa palauttaa sinut missä aloitit. Ja koetamme kaksi muuta lähestymistapoja ja katso jos emme voi tehdä pohjimmiltaan parempi kuin tämä. Joten tällä kertaa, aion ehdottaa eräänlainen eri algoritmia. Se oli erittäin taitava meistä viime kerralla, ja olitte oikeus saada oikeus vaistot juuri sellainen vaihtava pareittain. Mutta jos halusin lähestyä tätä yksinkertaisesti, ja minun tavoite on siirtää kaikki pikku numerot tällä tavalla, ja työntää kaikki suuret numerot, että Muuten, miksi en vain tehdä, että Useimmissa naiivi mahdollisella tavalla ja nähdä, jos olen voi tehdä paremmin kuin mitä oli melko monimutkainen algoritmi? Katsotaanpa. Neljä on melko pieni määrä, joten olen aio jättää sinua siellä hetki. Ooh, numero kaksi on vielä parempi. Joten voitte vain askel eteenpäin hetkeksi? Tämä on tällä hetkellä minun pienin numeroitu ehdokas, ja aion muistaa että niinku muuttuja. Mutta aion pitää tarkistaa. Onko joku, jonka määrä on pienempi? Kuusi, no. Voi, on Neil uudelleen. Joten aion työntää sinut takaisin tavallaan käsitteellisesti. Neil tulee eteen. Ja nyt, muuttuja että olen käyttävät seurata kuka on pienin numero päivitetään sisältämään Neil sijainti. No, katsotaanpa. Kolme, seitsemän, viisi. Tunnen Neil oli pienin. Mikä on yksinkertaisin asia minun tehdä nyt? En aio tuhlata aikaani vain kuplivaa Neil yksi paikka vasemmalle. Miksi en vain laittaa Neil jossa hän kuuluu, mikä on tietysti missä? Koko matkan alussa. Joten Neil, tule. Ja mikä sinun nimesi olikaan? GRACE: Grace. DAVID J. MALAN: Grace. OK. Joten Grace, valitettavasti, olet Tällainen tavalla. Miten siis ratkaista tämän ongelman? Oikea? Jos tämä on jono, siellä on vain seitsemällä paikkakunnalla. Muista, että, Rob, puhuimme julistaa ikäisiä, ja meillä oli vain äärellinen määrä ikäisille? Sama ajatus täällä. Meillä on vain rajallinen määrä ints. Grace on tavallaan meidän tavalla, niin miten me korjata? Yksinkertaisin tapa on kuin, Grace, anteeksi. Olet menossa on mennä yli siellä niin voimme tehdä tilaa. Nyt, jos ajattelee tätä, ehkä Olemme juuri tehnyt ongelma pahempi. Ja ehkä teimme, koska mitä jos Grace oli oikeassa paikassa? Mutta me tiedämme, hän ei ole, koska muuten hän olisi ollut seisoo eteenpäin sijaan Neil tällä kertaa, eikö? Meillä on jo tarkistanut hänen numeronsa ulos. Selvä. Joten nyt, Neil on oikeassa paikassa, ja Voin tehdä hieman optimointia. Seuraavan minuutin, aion sivuuttaa Neil kaikki yhdessä, jotta ei tuhlaa aikaansa, tai vahingossa vaihtaa hänet väärään paikkaan. Joten nyt, miten löydän seuraavan elementti, joka on pienin? Kaksi. Se on aika hyvä määrä, jos Haluatko astua esiin ja Minä muistan sinut. Kuusi, ole hyvä. Neljä, kolme, seitsemän, viisi, ei hyvä. Joten anna minun siirtää sinut oikea paikka. Ja me vain onnekas tällä kertaa. Nyt aion jättää nämä Kaksi miestä, ja nyt vielä yhden läpi tämän. Kuusi, että melko pieni määrä. Tule eteenpäin. Anteeksi. Grace numero on parempi, joten astua eteenpäin. Neljä. Anteeksi, Grace. Mene takaisin. Numero kolme on parempi. Seitsemän. Viisi. Ja nyt, mitä sinun nimesi olikaan? JASON: Jason. DAVID J. MALAN: Jason. Joten Jason on nyt pienin elementti Olen valinnut. Jos hän aikoo mennä? Joten missä kuusi on. Ja sinun nimesi on jälleen? GABE: Gabe. DAVID J. MALAN: Gabe. Gabe on tiellä. Mikä on helpoin asia tehdä? Vaihda nämä kaksi kaveria ja jatkaa. Joten nyt katsotaanpas. Kuka pienin? Neljä. Haluan vain sellainen huijata. Viisi tulee olemaan pienin. Minusta seuraava, jos haluat astua eteenpäin, mitä minun täytyy tehdä nämä kaverit, joiden Gabe? Vaihda uudelleen. Joten nyt vielä hieman epäkunnossa. I todettiin Gabe olevan pienin, niin Olen pop syötöllään, siirrä te yli. Ja tehty. Joten vastaus on sama. Lopputulos on sama. Kumpi näistä kahdesta algoritmeja on parempi? Toinen, kuulin. Miksi? SPEAKER 3: Se n askelta [kuultavissa]. DAVID J. MALAN: Se n vaiheet eniten. Mielenkiintoista. Niin on se kuitenkin? Joten miten löydän pienimmän alkion? Kuinka monta askelta ei minun on otettava löytää pienimmän alkion? Olin näyttää aina lopussa, eikö? Koska että pahimmassa tapauksessa, mitä jos Neil olivat täällä? Joten vain löytää pienimmän alkion vie minut n askelta, tai n miinus 1. Mutta, OK. Korjatkaa Neil. Muista, että minuutti sitten. Mutta miten saan seuraavan pienimmän alkion? Se n miinus 1 tai n miinus 2 todella, alkaen useita vaiheita. Niin OK. Joten en n miinus 2. Selvä. Niin että tuntuu hieman paremmin. Selvä. Kuinka monta askelta seuraavan kerran löytää numero kolme? Joten n miinus 4. Joten se on laskussa, yksi vähemmän astua jokaisen iteraation. Joten tämä ei tuntea paremmin, eikö? Jos viime kerralla se oli noin n kertaa n, tällä kertaa se n miinus 1, plus n miinus 2, plus n miinus 3, plus n miinus 4, piste, piste, piste. Mutta jos muistatte omasta lukion oppikirjat, vähän huijata arkki takaisin, että on kaavojen avulla, jos lisäät tätä numerosarja, mikä on portaiden kokonaismäärää olemaan, että otan täällä? Tämä on yksi niistä, kuten, n miinus 1 kertaa n, jaettuna 2. Joten anna minun nähdä, jos voin vetää tähän asti vain hetken. Ja vielä, olen sellainen pyöristys joidenkin numerot vain pitää elämäämme yksinkertainen, mutta muistaakseni se on jotain, jos En n miinus 1 asioita, niin n miinus 2, niin n miinus 3, se on suurin piirtein jotain tällaista yli 2, ja jos minä moninkertaistaa tämän, se on todella n neliö. Se ei tunne liian hyvä. n miinus n yli 2. Mutta tässä on asia. Tietotekniikassa, kun ongelmia alkaa saada mielenkiintoista on kun n saa todella suuri. Ja kun n saa todella suuri, mikä Näiden arvojen tulee hallitsemaan kaikkia ja muut? Se on tavallaan n potenssiin, eikö? Kyllä, jakamalla 2 on melko hyvä. Mutta jos puhut miljardeja paloja tietoja tai miljardeja datakappaleesta, OK, niin olet kaksi kertaa niin nopeasti. Mutta kuka todella välittää, jos suuri määrä, jos tämä seikka on mitä saa isompi ja isompi. Ja varmasti, se tekee enemmän ero kuin tämä kaveri. Joten vaikka te olette oikeassa, Toinen algoritmi, me kutsumme sitä valinta lajitella, on, todellisessa maailmassa, hieman nopeampi mahdollisesti, koska olen ottaen yhä harvempi askeleen kerrallaan. Se ei ole oikeastaan ​​pohjimmiltaan nopeammin. Koska jos me todella pelata tätä ulos suuret n: n arvoilla, lopussa päivä, tarpeeksi suuri n, se on silti menossa tuntea melko hidasta. No, anna minun ottaa yksi viime pass tuohon. Sitä minä kutsuisin valinta lajitella. Voisitteko palauttaa itseänne viimeisen kerran? Ja tässä viime tapauksessa aion ehdottaa jotain nimeltään lisäyslajittelu. Lisäyslajittelu on käsitteellisesti vähän erilainen. Sijaan menee edestakaisin ja valitsemalla pienimmän alkion, olen juuri menossa käsitellä kutakin näistä kaverit kuin minä kohtaavat heitä, ja aseta ne osaksi oikeassa paikassa. Joten olen juuri menossa aloittaa Grace, ja näen, että hän on numero neljä. Mistä numero neljä kuuluu? En ole alkanut lajittelu mitään, niin Grace saa jäädä oikeassa. Ja nyt aion vaatia, jos voisit ottaa askel oikealla, tämä minun lajiteltu lista, tämä on minun lajittelemattoman jäljellä lista. Joten nyt aion edetä seuraavaan, ja mikä sinun nimesi olikaan? BRANSON: Branson. DAVID J. MALAN: Branson. Joten Branson on numero kaksi. Joten aion viedä sinut pois hetkeksi. Ja nyt, jos kuulut Tässä array? Joten oikeus Grace. Joten jälleen olemme tavallaan tehdä Grace tehdä paljon työtä täällä. Minne laitamme sinut? Joten aiomme liukumaan sinua vasemmalle ja aseta Branson siellä. Mutta nyt Väitän, että te olette tehneet. Mutta huomaa, en käytä lisätilaa. Se on edelleen 2 elementtiä täällä, 5 tänne. Yhteensä jonon pituus on 7, joten olen ei huijaa, kaikki hyvin? Joten nyt meillä on, ja Gabe täällä, numero kuusi, jossa sinä kuulut? Olet onnekas uudelleen. Niin saat pysyä oikeassa. Ota vain hieman askel oikeaan vain tehdä selväksi, että olet lajitellaan. Ja nyt meillä on Neil uudelleen, numero yksi, minne menet? Ja nyt on, jos alamme nähdä, että tämä algoritmi, vaikka ensimmäisen silmäyksellä, tuntuu aika fiksu, katsella mitä tulee tapahtumaan. Jos voisit askel eteenpäin. Missä haluamme laittaa Neil? Joten ilmeisesti täällä, niin miten saamme Neil siellä? Tehdään tämä askel-askeleelta. Gabe, mistä sinun täytyy mennä? Jep, niin ottaa yksi iso askel, tai kaksi puolen toimiin, jotta yksi askel tuolla. Grace, missä mennään? Hyvä. Joten toinen vaihe. Ja lopuksi, Branson? Toinen vaihe. Ja nyt voimme Neil paikoilleen. Joten nyt jatkaa tätä logiikkaa. Vaikka emme ole siirtymässä Neil yli, ja yli, ja yli, laittaa hänet missä hän menee, pahimmassa tapauksessa seuraava numero saatamme kohdata voitaisiin olla numero, eli siellä oli useita nolla, niin aiomme siirtää kaikki nämä kaverit. Oletetaan, että on olemassa useita, negatiivinen , sitten meidän täytyy siirtyä kaikki nämä kaverit. Olemme siis oikeastaan ​​vain sellainen käännetään ongelman ympärillä, niin että olemme siirtämällä kustannuksella alkaen valintaprosessi joten lisäys prosessi, niin että te vain oli liikkua karkeasti n miinus jotain useita vaiheita. Ja että useita vaiheita on vain menee kasvavan valitsen enemmän numeroita, jos minun täytyy pitää työntämään teitä takaisin, ja takaisin, ja takaisin. Niin surullista nyt on kaikki nämä algoritmit ovat n potenssiin. Mennään eteenpäin ja kiitos näistä kaverit, ja visualisoida nämä vähän eri tavalla. Hyvin tehty. [APPLAUSE] Selvä. Siellä mennään. Kiitos - BRANSON: [kuultavissa] pitää numerot. DAVID J. MALAN: Ei, voit pitää numerot samoin. Selvä. Hienosti tehty. Selvä. Katsotaanpa, jos emme voi nyt tiivistää nopeammin, ja visuaalisesti, mitä juuri tapahtui tässä seuraavasti. Aion mennä eteenpäin ja vedä ylös Firefox. Liitämme tämän esittelyn kurssin verkkosivuilla. Java on vähän ärsyttävää saada työ Joissakin selaimissa näinä päivinä. Joten jos et pelata tätä kotona, ymmärtää, saatat joutua käyttämään Firefox saada se toimimaan. Ja mitä aion tehdä tämän esittelyä on seuraava. Alareunassa, minulla on koko joukko valikon vaihtoehdot, kuten alku-ja STOP-painiketta. Lisäksi, kuten syrjään, siellä näyttää olevan bug näissä ohjelmissa, jolloin voit ei voi itse nähdä alusta tai lopettaa painiketta ellet pidä Command tai Alt plus ja zoomaus, joka uteliaana näyttää enemmän painikkeita. Joten FYI jos pelaat tämän kotona. Nyt aion valitse Käynnistä vain hetkellä, kun määritellään viive, kuten 200 millisekuntia täällä, vain jotta voimme nähdä, mitä tapahtuu. Olen siis väittävät, että tämä on visualisointi Ensimmäisen algoritmin nämä kaverit tekivät, kupla lajitella, jolloin Vaihdoimme ihmiset pareittain. Keskeinen oivallus tähän visualisointi on se, että korkeus tankojen edustaa koko määrää. Joten pitempi palkki, isompi numero. Lyhyemmät baari, pienempi numero. Ja jos huomaat, olemme menossa läpi Ensimmäinen tämän algoritmin, vaihtamalla iso ja pieni määrä, jotta pieni määrä tulee ensin ja suuri määrä menee oikealle. Ja heti kun saamme loppuun array paljon enemmän numeroita kuin seitsemän, olemme menossa takaisin alkuun. Ja ennakoida tätä. Äärimmäisenä vasemmalla, että pikku kaveri on menossa vaihtaa puolelle, ja tämä prosessi toistuu. Nyt tämä visualisointi saa nopeasti tylsää, joten haluan mennä eteenpäin ja lopettaa , muuttaa viive jotain paljon nopeampi vain saada nyt tuntumaa tämä algoritmi. Joten vaikka olen nopeuttanut sitä, tämä on kuten päivittää minun prosessori, ostaa uusi tietokone. En ole olennaisesti muuttanut algoritmi, mutta voit todellakin nähdä enemmän selvästi kuin ihmisten kanssa, että iso numerot kuplii ylös, ja pienet numerot ovat kuplivaa pohjaan. Ja nyt tämä asia täällä järjestetty. Ja syrjään, toreilla, siellä vain joitakin kirjanpidon siellä auttaa laskemaan, kuinka monta vertailuja, tai kuinka monta swap on todella tehty. No, kokeile jotakin muut näimme. Saanen klikkaa kupla lajitella täällä, ja anna minun valita, ja tämä koko web-sivun on vähän buginen. Katsotaanpa hyväksyä riski ja käyttää sitä uudelleen. Siellä mennään. Tehdäänpä valinta tavallaan. En tiedä miksi valikosta näkyy tuolla. Katsotaanpa zoomata vahvistaa, että bug, muuttaa 50. Ah, nyt itse tehdä että paljon nopeammin. Viisi millisekunnin, ja Start. Joten tämä on valinta tavallaan. Joten jälleen, miettiä, mitä me teki ihmisiin täällä. Kävimme läpi array ja valitut pienimmän alkion uudelleen, ja uudestaan, ja uudestaan. Nyt Väitän, että oli vielä melko huono. Se oli vielä n neliö, antaa tai ottaa, mutta se oli, todellisessa maailmassa, hieman nopeammin, koska olin todellakin ottaen hieman vähemmän vaiheita joka kerta. Mutta me vain puhumme mitä? Ehkä 40 tai niin baareissa täällä? Emme puhu 40 miljoonaa. Joten se ei ole täysin selvää, että oli todellakin merkittävä voitto. Anna minun mennä takaisin ja muuttaa meidän Kolmas algoritmi, joka valitaan lisäyslajittelu. Ja nyt se on todella buginen, koska valikko ei todellakaan pitäisi olla siellä. Joten nyt me vierittää takaisin tänne ja aloittaa tämän algoritmi. Huutaa, käynnistää ja pysäyttää. Joten tämä yhdenlaista on melko kuvio sen, jolloin olemme taas lisäämällä ihmisten tai Tällöin baareja osaksi niiden oikeassa paikassa. Ja se on jo tehnyt ennen Käännyin ympäri. Mutta myös tämä teoriassa on vielä n potenssiin. Katsotaanpa, jos emme voi tiivistää Näiden seuraavasti. Aion mennä eteenpäin ja vain antaa meille eräänlainen yhteinen tapa puhua näistä asioista, haluan esitellä vain vähän merkintätapa täällä. Olet tulleet niin sanotun suuren O, koska se on kirjaimellisesti iso O. Ja tämä on tapa, että tietokone tiedemies tai matemaatikko edes käyttää kuvaamaan käyntiaika Joidenkin algoritmi. Kuinka monta askelta se todella ottaa? Nyt aion nolata itseni kanssa minun käsialalla täällä vain hetken. Mutta haluan mennä eteenpäin ja sanoa, että tämä on iso O tänne. Ja haluan esitellä yksi muu symboli, pääoman omega. Omega tulee olemaan päinvastainen, lähinnä iso O. katsoo iso O välineet, pahimmassa tapauksessa, kuinka paljon aikaa saattaa joissakin algoritmi toteuttaa vuonna ehtojen n, omega on menossa olla kuinka paljon aikaa saattaa se ottaa parhaassa tapauksessa. Ja näemme, mitä me tarkoitamme Parhaassa tapauksessa vain hetken. Joten aloitetaan jotain yksinkertaista. Aloitan lineaarista hakua. Joten ei lajittelu. Me kutsumme tätä lineaarista hakua. Ja nyt, tehdä vähän taulukko pois tästä. Ja nyt, kun kyseessä on lineaarinen haku, pahimmassa tapauksessa, kuinka monta askelta on se vie minut löytää määrä mielivaltainen valinta? Ja siellä n yhteensä ovet tai n kokonaismäärät. Pahimmassa tapauksessa. Kuinka monta askelta olen menossa on ottaa löytää numeron 50 array n ovet? Ja miksi? Koska se voisi olla kaikki reilusti yli kiinni loppuun. Niin paljon kuin Jennifer kohdanneet, numero 50 oli aina yli, joten Pahimmassa tapauksessa lineaarinen haku on iso O n, me sanomme. Entä parhaassa tapauksessa jos saat todella onnekas? Se tekee vain ottaa yksi askel, tai jatkuvasti useita vaiheita. Joten me kuvataan, että 1. Joten tämä on melko hyvä. Nyt mitä jos teimme jotain kuten binäärihaku? Joten binäärihaku pahimmassa tapauksessa kesti kuinka paljon aikaa? [Interposing ÄÄNTÄ] DAVID J. MALAN: Niin todella, minä kuullut sen pari paikkaa. Joten se on todella kirjautua n, antaa tai ottaa, koska sillä jaamme listan kahtia uudestaan, ja uudestaan, ja uudestaan, pystymme löytää lopulta arvosta, jos se on olemassa, mutta on kiinni. Mikä oletus, että meidän on itsestäänselvyytenä binary search? Se on järjestetty. Se ei ole lajiteltu, voit jakaa asia kahtia uudestaan ​​ja uudestaan, ja sinä voi mennä vasemmalle, ja voit mennä oikealle, ja voit mennä vasemmalle ja oikealle, mutta olet tule löytämään elementti, jos luetteloa ei lajitella, koska saatat menettää sen. Koska heuristinen menossa vasemmalle tai oikealle tulee olla virheellinen, jos se on todellakin ole lajiteltu. Niin siellä on tavallaan piilokustannuksia käyttämään jotain tällaista. Nyt mennään meidän lajittelu algoritmit etsimättä - oh, todella mennään tässä tyhjäksi. Binäärihaku parhaassa tapauksessa? Se on myös 1, jos se vain sattuu olemaan aivan keskellä array, tai keskellä puhelinluettelosta. Nyt tehdä kupla tavallaan. Joten jälleen, nyt olemme syöttämällä lajittelee, ei hakuja. Pahimmassa tapauksessa, kuinka monta askelta teimme väite kupla tavallaan vie? n potenssiin. Joten aion tehdä sen. Ooh, minun käsiala näyttää jopa pahempi kun se on ennustettu, että iso. Selvä. Niin, että N-potenssiin. Ja parhaassa tapauksessa kupla lajitella, kuinka monta askelta se aikoo ryhtyä? 1, kuulin. Kaiutin 1: n. DAVID J. MALAN: n, kuulin. SPEAKER 1: 2. DAVID J. MALAN: 2, kuulin. Kuulenko 3? Selvä. Niin olen kuullut 1 n, 2, mutta nyt valita lisäksi ainakin ensimmäinen näistä ehdotuksia, 1. Se ei ole huono vaisto, koska se Tällainen seuraa kuvio täällä. Mutta jos se kestää vain 1 askel, miten maailman voisin väittää, että luettelon lajitellaan, koska jos olen vain sallittu ottaa 1 askel, kuinka monta elementtiä voisin oikeastaan ​​varmista? No, vain 1, mikä tarkoittaa, että on n miinus 1 seikkoja, jotka voisivat olla pois järjestyksessä, ja olen juuri menossa uskoon jälkeen katsomalla 1 elementti, joka asia on järjestetty. Joten 1 ei ole korjata täällä. Joten vähän, kuinka monta minun täytyy katsoa? [Interposing ÄÄNTÄ] DAVID J. MALAN: n miinus 1, tai oikeastaan, n, koska minun täytyy tarkastella jokaisen elementti varmistaa, että se ei ole epäkunnossa. Mutta jälleen kerran, me tavallaan aalto meidän kädet pienempi määrä ja olettaa, että n saa suuria, ne ovat mielenkiinnoton muutenkin. Niin, että kupla tavallaan. Ja nyt, nyt nämä kaksi viimeistä. Valinta lajitella ja niin me hyvitämme tehdä lisäyslajittelu. Ja sitten me räjäyttää mielissä jotain paljon parempi kuin kaikki nämä. Selvä. Mikä on pahin käynnissä valintahetkellä tavallaan? SPEAKER 4: n potenssiin. DAVID J. MALAN: n neliö, kuulen. Mutta miksi n potenssiin, intuitiivisesti? SPEAKER 4: Koska me vain teimme sen. DAVID J. MALAN: Koska me vain teimme sen. OK. Hyvä vastaus. Mutta intuitiivisesti, miksi valinta sort n potenssiin? Mitä meidän on tehtävä uudestaan ​​ja uudestaan? Meidän piti pitää skannauksen kautta, ovat olet pienin, oletko pienin, oletko pienin. Ja myönsi, pystyimme ottamaan n vaiheet, niin n miinus 1, niin n miinus 2. Mutta jos sellainen lisätä ne kaikki ylös, tai ottaa sen uskon, että olen lisännyt niitä etukäteen, saamme karkeasti n potenssiin miinus joitakin pienempiä numeroita. Joten aion kutsua tätä n potenssiin. Mutta valinta lajitella paras tapauksessa, kuinka monta askelta on se vie minut? SPEAKER 5: [äänetön] DAVID J. MALAN: Se on valitettavasti vielä n potenssiin, eikö? Koska jos olen valinnut pienin elementti, ja meillä oli seitsemän ihmistä täällä, Tiedän vain, kun pääsen hyvin lopussa, että olen löytänyt pienin numero, missä hän tai joutuneensa. Mutta miten löydän seuraavan pienin määrä? Minun täytyy tehdä toinen pass. Joten parhaassa tapauksessa, mikä on valintamekanismille tavallaan? Se on jo lajitteluluetteloon, numero yksi, numero kaksi, numero kolme, numero neljä. Mutta olen tietokone. Voin vain katsoa yksi asia kerrallaan. En voi tavallaan ottaa askel takaisin kuin ihmisen ja sanoa, ooh, tämä näyttää oikein. Voin vain ratkaista oikeellisuus valinta lajitella valitsemalla pienin määrä. Mutta vaikka löydän ykkönen ensin, jos en tiedä mitään muuta muut numerot, joita en ole, kaikki I tietää, että olen kulkenut array tai joukko ovien takana, jotka ovat numerot, ainoa tapa Tiedän, että yksi oli pienin? Jos saan kaikki tänne ja ymmärtää, Hitto, yksi oli todellakin pienin. Mutta miten voin sitten päättää, että kaksi on seuraavaksi pienin? Tekemällä sama tehottomuus uudelleen ja uudelleen. Joten lopuksi, jossa lisäyslajittelu, miten, pahimmassa tapauksessa, Sanoimmeko se toimii? Sekin on n potenssiin. Ja miten paras asia? Jätämme että jännitysnäytelmä. Me täyttää että tyhjä seuraavan kerran, mutta haluan ensin ehdottaa, että pohjimmiltaan tehdä paremmin kuin kaikki nämä, okei? Ajattele itse, mitä paikoilleen sort tulee olemaan. No, se ei ollut kovin dramaattinen, koska olen vain yksi että näki muutoksen. Wow. OK. Joten tässä meillä on hieman eri esittelyä. Jos minä suurentaa täällä, näet, että Vasemmalla on kupla lajitella, vuonna keskellä meillä on valikoima lajitella, ja äärioikeisto, olemme me ole katsonut vielä nimeltään yhdistää tavallaan. Ajatelkaa mitä olemme olleet teet täällä tähän mennessä tänään. Kun Jennifer ensimmäinen tuli lavalle, kävimme läpi joukko numeroita uudestaan, ja uudestaan, lineaarinen haku, ja saimme lineaarinen käyntiaika, iso O n, niin sanoakseni. Kun me nyt harkita ensimmäisellä viikolla luokka, kun olimme hajoita ja hallitse, ja meillä oli puhelinluettelon repiminen, ja Jennifer, ja me yhdessä velkarahalla, että keskeiset oivallus, joka oli toista itseäsi uudestaan ​​ja uudestaan jotenkin heittää pois, heittää pois, heittää pois, puolet ongelma tai yleisesti, jakamalla ongelma puoli, ja sitten käsittelemällä pienempi pala ongelma käsitteellisesti vastaa Muihin me jotenkin pallo pohjimmiltaan paremmin. Mutta kupla lajitella, jossa valinta lajitella, jossa lisäyslajittelu, olemme voi tällaisia ​​oivalluksia että Jennifer teki. Olemme aika paljon vain käveli takaisin ja esiin koko joukko kertaa, ja me viritetty asioita hieman, vaihtamalla tässä järjestyksessä, ehkä lisäämällä tai valitsemalla. Mutta loppujen lopuksi, tein paljon hankala kävely edestakaisin. Meillä ei oikeastaan ​​hyödyntää jotain älykäs kuten Jennifer teki kuten jakamalla ja valloitusta. Joten yhdistää lajitella, sen sijaan, jota eivät näe vasta ensi viikolla, se menee hyödyntää, että keskeinen ajatus jakamalla tulo, ja sitten puolittaa, ja sitten puolittaa, ja sitten puolittaa. Ja jokaisen iteraation että silmukka, lajittelu vasen puoli ja oikea puoli, sitten vasen puoli on vasen puoli, ja oikealla puolella vasemmalle, sitten vasen puoli oikea puoli, ja oikea puoli oikea puoli. Ja toistamalla uudestaan ​​ja uudestaan. Niin näet tämän visuaalisesti, mutta tämä on mitä odottaa meitä ensi viikolla. Ja yleensä, kun ajattelemme hieman vähän kovemmin tällaisia ​​ongelmia. Meillä on n potenssiin vasemmalla n potenssiin keskellä, ja n log n oikealla. Joten siellä on todellinen jännitysnäytelmä. Nähdään maanantaina. [APPLAUSE]