[Musiikkia] David J. MALAN: Tämä on CS50. Ja tämä on alku viikolla kolme. Joten meillä on paljon jännittäviä asiat kattamaan tänään. Paljon mahdollisuuksia vapaaehtoisille lavalle. Ja lopulta, tänään on ei noin koodia ollenkaan. Mutta se on noin ideoita, ja se on noin algoritmeja, ja itse asiassa tuoda takaisin joitakin saadut kokemukset viikko nolla, jossa muistaa, me esitteli tämän monstrosity. Ja lainanotto inspiraatio siitä, aloittaa ratkaisemaan yhä kehittyneempiä ongelmia algoritmisesti. Mutta ensin pari ilmoituksia. Joten, jos haluat liittyä CS50: n henkilökunta ja luokkatoverit lounaalla perjantaina, sekä täällä että Cambridge, ja New Haven, käy kurssin sivusto, jossa URL löytyy. Luento tämä keskiviikkona ei olla täällä Sanders. Se on verkossa vain, niin virittää klo CS50 n verkkosivuilla, onko täällä Cambridge tai New Haven samoin. Ja sitten ongelma asettaa kaksi on jo käsissäsi. Jos et ole syöksyi vielä, haluan tarjota tiukkasanainen ehdotus että, varsinkin nyt, kun ongelma asettaa etukäteen, et todellakaan halua aloittaa nyt, jos ei harrastella vähän viikonloppuna tai ennen kun he ensin mennä ulos Perjantaisin, koska sinun toteavat, että ne eivät ole välttämättä pitenevät tai haastavampaa kohden SE. Luulen löydät että Yleensä ne yleensä ottaa karkeasti noin saman verran aikaa. Mutta se varmasti riippuu opiskelijan, ja se riippuu ajattelutapa jolla voit lähestyä sitä. Mutta poikkeuksetta, olet menossa olla ristiriidassa joitakin seinää, ja aiot lyödä jotkut bug, ja olet vain ei tule pystyä päästä sen yli jossain vaiheessa. Ja se on erittäin arvokas pystyä vaiheeseen pois, tule takaisin seuraavana päivänä, mennä virka, viesti CS50 Keskustele tai kuten, todella saada vapautetuksi. Niin pitää tämä mielessä. Alkaen aikaisintaan mahdollisimman on parasta, mitä voit tehdä. Joten tässä on, jos aloimme luokka, yli viikolla nolla. Ja saamme vapaaehtoinen täällä auttaa minua löytämään mikrofonit? OK. Seisomaan jo. Tule ylös. Arvaa niin se tulee toimimaan. Mikä on nimesi? ALAN ESTRADA: Alan Estrada. DAVID J. MALAN: Alan Estrada. Tule ylös. Kiva tavata. ALAN ESTRADA: Hauska tavata. DAVID J. MALAN: Ja olit täällä kanssamme viikolla nolla, tietenkin. ALAN ESTRADA: Olin. Minä olin. DAVID J. MALAN: Joten voisitteko mennä eteenpäin ja löytää meille Mike Smith, niin nopeasti kuin voit? Niin nopeasti kuin voit. Kirjaimellisesti repiminen ongelma kahtia niin sinun täytyy. ALAN ESTRADA: Um. DAVID J. MALAN: Kirjaimellisesti repiminen ongelma kahtia. ALAN ESTRADA: Oh. Mm. Oikein hyvä. DAVID J. MALAN: OK. Hyvä. Kiitos. ALAN ESTRADA: Erittäin hyvä. OK. DAVID J. MALAN: Ja nyt, olet supistetaan sen alas puolet koko ongelman. Nyt olemme alas neljänneksellä. Oletko kiinnittämällä huomiota millä puolella olemme pitää? [Nauraa] ALAN ESTRADA: Kyllä, minä think-- DAVID J. MALAN: Mitä jakso olemmeko? ALAN ESTRADA: vaimentimet, niin. DAVID J. MALAN: OK. Mutta Mike Smith on menossa olla jälkeen vaimentimet. So-- [Nauraa] Selvä. ALAN ESTRADA: Missä me etsimme? DAVID J. MALAN: Mike Smith. ALAN ESTRADA: Mike Smith. DAVID J. MALAN: Nyt olemme kirurgisen. Nyt, lääkärit. Now-- ALAN ESTRADA: Let's- mennään todellisia. Real. DAVID J. MALAN: Real. OK. Jos tarvitset Real. Nyt, mikä tapa on Mike Smith? ALAN ESTRADA: Näin. DAVID J. MALAN: Mihin suuntaan? ALAN ESTRADA: Odota. M is-- oikea? Aloitimme with-- DAVID J. MALAN: Joo. He vasemmalle. Sinun oikea. ALAN ESTRADA: Joo. DAVID J. MALAN: Eli Mike täällä. ALAN ESTRADA: Mitä? [Nauraa] Huono esimerkki, kaverit. Anteeksi. DAVID J. MALAN: Tämä opettaa voit hypätä pois oman tuolin. ALAN ESTRADA: Oh. Oi. Minä sain sinut. Minä sain sinut. Oi. Oi. Tämä is-- OK, sain sinut. Smith täällä? DAVID J. MALAN: Smith, kiitos. Joten aion pitää etsimisessä Smith? ALAN ESTRADA: Ai, joo. Ei Ei ei. Voi ei. Tämä on minun. DAVID J. MALAN: Voi, sinulla Smith. OK. ALAN ESTRADA: Joo, minä sai Smith täällä. Anteeksi, kaverit. Luulin Michael-- me etsivät Michael. Anteeksi. DAVID J. MALAN: Se on OK. Okei, nyt olemme osaksi Paccini ja Sons. ALAN ESTRADA: Paccini ja poikia. DAVID J. MALAN: Vain sinä ja minä olemme tästä. OK. Löydä meidät Mike Smith. Smith. ALAN ESTRADA: Smith. DAVID J. MALAN: Smith. Olemme R roskaa. ALAN ESTRADA: Roskaa. Oi. Tämä vie aikaa. [Nauraa] DAVID J. MALAN: Kengät. Olemme kengät. ALAN ESTRADA: Nyt olemme gonna-- DAVID J. MALAN: Nice. ALAN ESTRADA: Which-- [Nauraa] Voi, tämä on suuri. [Nauraa] DAVID J. MALAN: Se on OK. ALAN ESTRADA: Voi, tämä on hyvä. En usko, aion on PSAT ystäviä jälkeen. DAVID J. MALAN: Hyvä. Sporting. ALAN ESTRADA: Sporting. Um, L, M, N, O-, s DAVID J. MALAN: OK. Joten repiä tämän kahtia. Se on ok. Tämä päättyy huonosti muutenkin, koska Mike Smith ei keltaiset sivut. ALAN ESTRADA: Aw. DAVID J. MALAN: Ei, se on OK. Mutta katsotaanpa teeskennellä kuten hän on tällä sivulla. Joten nyt, olet supistetaan ongelma alas yhdelle sivulle, ja löysimme Mike Smith. [Hurraavat] OK kiitos. OK. Se oli ihmeellistä. Mutta se oli edelleen nopeampaa kuin lineaarinen haku, jossa aloitamme kirjan alussa, ja siirrymme tiemme vasemmalta oikealle, lopulta etsivät Mike Smith. Ja niin, jos puhelinluettelo oli ehkä 1000 sivua, ehkä se olisi ottanut meille 10 tai niin sivu kyyneleitä. Mutta sinulla voi olla velkarahalla kosketti oletus aikana, kaikki se, mikä on sanoa että puhelinluettelon etukäteen oli mitä? Yleisö: Lajittelu. DAVID J. MALAN: Se on lajiteltu. Oikea? Se aakkosjärjestyksessä, joten että kaikki nämä nimet ja numerot lajitellaan luvulta Z: n, ja aakkosjärjestyksessä välillä. Mutta tänään, nyt kysyä kysymys, hyvin, kuinka teki Verizon tai puhelin yritys saada se tuohon tilaan? Koska se on yksi asia hyödyntää että oletus, ja siksi, ratkaista ongelma algoritmi tehokkaammin. Mutta emme koskaan todella kysyi viikolla nolla, hyvin, kuinka paljon se maksoi Verizon tai joku muu saada, että puhelinluettelon lajitellut järjestyksessä? Oikea? Sillä ei ole väliä, jos looking up Mike Smith on huippunopea, jos se vie vuosi lajitella sivuja aluksi. Oikea? Voit myös vain siivilöidä kautta satunnaistettu puhelinluettelosta, jos se tulee olemaan erittäin kallista lajitella. Joten jos voimme olla toinen vapaaehtoinen. Otetaanpa etsiä täällä miten me might-- tulla up-- miten voisimme mennä noin lajittelu näistä. Ja jos Jordan voisi todella liittyä meihin täällä lavalla. Tule ylös vain hetken. Mikä on nimesi? CAROLINE: Caroline. DAVID J. MALAN: Caroline, tule ylös. Ja sinun on liittynyt minun ja Jordan täällä. Caroline, kiitos. Selvä. Joten mitä meillä täällä Caroline on 26 sininen kirjoja FAS käyttää hallinnoida tiettyjä loppukokeet. Nämä saavat vaikea löytää, mutta mitä olemme tehneet etukäteen on, että olemme laittaa jonkun nimi edessä kunkin näistä, mutta olemme pitäneet sitä yksinkertaista sitten ojentaen täydelliset nimet. Joten haluaisimme laittaa henkilö, jonka nimi L, D, J, B, aina A-Z, mutta ne satunnaisessa järjestyksessä. Ja niin jos voisitte, puhuminen teidän läpi ongelma kun tehdä se, voit mennä eteenpäin ja järjestää meille, A: sta Z Yleisö: OK, joten L on kuin, keskellä. C alkaa. B. J ennen L. B, Q. DAVID J. MALAN: Pidä että Vaikka yhden sekunnin. Koska muuten, tämä on vain kiinnostaa sinua, minua, ja Jordania. Siellä mennään. Yleisö: [äänetön]. R. DAVID J. MALAN: OK. Mitä olet tekemässä? CAROLINE: M tulee jälkeen O. DAVID J. MALAN: OK. CAROLINE: O. DAVID J. MALAN: O, Hyvä. CAROLINE: E. DAVID J. MALAN: E, F. Joo. CAROLINE: T, U, V. DAVID J. MALAN: V, T, U, V. Joten se näyttää olet making-- jatkaa. Näyttää siltä, ​​teet iso kasa tänne, ja tavallaan iso kasa tuolla. Joten alkupuoliskolla aakkoset, jälkipuoliskolla aakkoset. OK. Hyvä. Kind of halkaisu ongelma kahdessa. M, N, X Joo. CAROLINE: K. DAVID J. MALAN: OK. K. Joten olet tavallaan valitsemalla ne yksi toisensa jälkeen, laittoi pallon joko vasemmalle tai oikealle, tai Z on menossa lattialle. OK. CAROLINE: Z tapahtuu lattialle. DAVID J. MALAN: OK. Y on menossa lattialle. Nyt voimme laittaa X. CAROLINE: G. DAVID J. MALAN: G: n menossa vasemmalle. S on menossa oikeaan. Hyvä on, menee koko matkan vasemmalle. CAROLINE: A, B, C, D DAVID J. MALAN: Nyt, hyvä. Meillä, B, C W: n menossa sinne. Selvä, T. CAROLINE: H, I, J DAVID J. MALAN: H, I, J Hyvä. CAROLINE: Keskustassa, olen gonna-- DAVID J. MALAN: OK. Joten nyt, aiomme eräänlainen ja yhdistää nämä eri paaluilla. Joten kautta C, niin näen D, ja E, ja F, ja G ja H, ja I. Nizza. J, K. Ja sitten, tämä kasa on ylösalaisin, mutta se on OK. Kaikin mokomin. Voimme leikata joitakin kulmat. OK. Ja meidän on W, X, Y, Z. CAROLINE: Joo. DAVID J. MALAN: Erinomainen. Joten iso kiitos Caroline lajitteluun näitä. [Hurraavat] Kiitos. Kiitos paljon. Joten nyt Tarkastellaan hetki miten Caroline meni noin tekee, että ja mitä me pystyivät to-- miten me pystyivät ratkaisemaan että ongelma, kun olimme juuri annetaan koko joukko satunnaisia ​​panoksia. No, näyttää siltä, ​​että oli hieman järjestelmässä? Oikea. Joten aiemmin kirjaimet aakkosissa, hän oli laskemisesta vasemmalle, ja myöhemmin kirjaimia, hän laittoi oikeaan. Ja kun hän löysi jotkut proksimaalinen kirjeitä, niistä jotka menevät oikeus vierekkäin, hän laittaa ne kunnossa. Ja niin me tavallaan oli näitä pieniä kasoittain lajitellun siihen syötetään. Ja niin se on aivan kuin mitä useimmat meistä ihmiset tekisi. Haluamme tavallaan käydä läpi sitä, ja olisimme sellainen on mekanismi. Mutta se voi olla vaikea kirjoittaa sen alas kaavassa sinänsä. Se tuntui hieman enemmän orgaanista kuin. Joten, jos voimme nyt sidottu ongelma vähemmän tuloa. Sen sijaan 26, katsotaanpa tehdä jotain paljon vähemmän vain sanoa, seitsemän, takana nämä ovet, niin sanoakseni. Onko vain seitsemän numeroa? Ja jos tavoite nyt käsi on löytää arvo, Katsotaanpa, miten tehokkaasti voimme edetä tässä. Ja katsotaan, jos voimme nyt alkaa soveltaa joitakin numeroita, tai joitakin kaavoja, joiden avulla voidaan kuvata tehokkuuteen puhelinluettelo algoritmi, meidän tentti kirja algoritmi, ja yleisemmin löytää tietoa. Joten tämä, anna minun mennä eteenpäin, ja kosketusnäytöllä tänne, sietää selain, joka on juuri näiden seitsemän ovet. Ja jos voisimme saada yksi muu vapaaehtoisesti tulla tänne, Laitoin nämä samat ovet tänne. Nopea vapaaehtoinen. Tämä one-- demot ovat menossa on nopeampi ja nopeampi nyt. Tule alas. Mikä on nimesi? TREVOR: Trevor. DAVID J. MALAN: Trevor? Hyvä, Trevor, tule alas. Joten Trevor on vapaaehtoisesti tästä tehdä samanlainen ongelma, mutta se on suppeampi, ja että menee jotta voimme yrittää virallistaa nyt prosessi lajittelun näitä numeroita. Joten Trevor, mukava tavata. Joten tässä on jono, niin puhua, luettelon seitsemästä ovet. Menkää ja löytää meidät numero 50. Ja sitten sen jälkeen se, Kerro meille miten löysit sen. Jos be-- kunnossa. Joo, tämä on yksi täällä? O-ou. OK. Valitsit, että yksi. Hyvä. Ja hyvä. Nyt valitsit, että yksi. Ja minä annan sinulle mikrofoni, niin että sinulla on se vain hetken. Menkää ja napsauta vieressä, että aiot. Kyllä hyvä. TREVOR: Voinko tyhjennä ovi? DAVID J. MALAN: Ei, et voi tyhjennä. TREVOR: OK. Tämä. DAVID J. MALAN: Missä haluat mennä? Mikä? TREVOR: Tuo. DAVID J. MALAN: Ei. TREVOR: OK. Tämä. DAVID J. MALAN: Kyllä. Se oli hyvä. Selvä. Joten mikä oli algoritmi tai menettely teet tämän, Trevor? TREVOR: Minä vain meni läpi ovet kunnes löysin 50. DAVID J. MALAN: OK. Erinomainen algoritmi. Niin se käy hyvin. Koska itse asiassa, jos paljastan mitä Näiden takana muut ovet, mitä me löydämme tässä että meillä on vain satunnainen tulo. Joten se oli todella niin hyvä kuin sinä. Ja itse asiassa, sinulla parempi kuin tyhjentävästi etsivät koko joukko, koska se olisi ollut todella epäonninen jos olisit osunut numero 50 aivan viime ovi. Mutta mitä jos me sen sijaan antoi sinulle oletus. Kai tavallaan kaikki nämä ovet ympäri, niin että sinulla on numerot lajiteltu tällä kertaa, mutta tällä kertaa se on todella different-- tällä kertaa, se on todella lajiteltu sinulle. Ja nyt tavoite käsillä on lyödä numero 50. TREVOR: OK. DAVID J. MALAN: Mikä algoritmisi olemaan? TREVOR: No, jos se on lajiteltu, se on joko menossa jotta be-- jos suurin suurimpaan, laskeva, se tulee olemaan ensimmäinen, tai jos se on päinvastainen, se on viimeinen. Niin minä vain koskettamalla tätä ovea, ja sitten napauttamalla viimeinen ovi. DAVID J. MALAN: Erinomainen. Selvä. Joten löysimme numero 50. Niin heti kun tiesit ne lajiteltiin, me pystyivät hyödyntämään tätä oletusta. Joten he ovat liian paljon puhelinluettelon esimerkki. Heti kun on, vaikka pieni ongelma näin, teidän tuloa esilajiteltuina, voimme itse löytää arvo todennäköisesti tehokkaammin. Ja en kertonut sinulle, jos se oli lajiteltu pienistä isoihin, tai iso pienille, ja niin se oli hyvin kohtuullinen aloittaa toisessa päässä tai muita todella löytää että tavoitearvo. Joten kiitos Trevor samoin. Ja minä propose-- hienosti tehty. Meillä on hieman leikkeen, todella, että on yksi meidän suosikki hetkiä CS50, jolloin joskus demoja eivät aivan mene suunnitelmien mukaan. Ja todellakin juuri nyt, minä revitä väärä liitäntä jolla voidaan käyttää kosketusnäyttöä. Niin että oli minun vikani siellä. Joten tämä tekee varten ensi vuoden leike nimellä miksi olin klikkaamalla oman näytön. Mutta sallikaa vilkaista mitä tapahtui viime vuonna Jay Hän tuli, paljon kuten Trevor täällä, vapaaehtoisesti, ja tässä lyhyen pätkän, näet miten tämä sama demo ei aivan paljastavat samoja opetukset. [VIDEOTOISTOSTA] -Kaikki Haluan sinun tehdä nyt on löytää minulle, ja meille, todella, numero 50 askel kerrallaan. -The Numero 50? -The Numero 50. Ja voit paljastaa mitä takana jokainen näistä ovet yksinkertaisesti koskettamalla sitä sormella. Perkele. [Nauraa] [Lopeta toisto] DAVID J. MALAN: Niin että meni hyvin. Ne olivat lajittelemattoman ovet. Ja Jay, tietenkin, löytyi kaiken liian nopeasti. Trevor teki paljon paremmin kannalta oppivainen hetki, niin sanoakseni, tänä vuonna kauemmin löytää se. Tietenkin, sitten annoimme Jay toisen mahdollisuuden, jolloin me lajiteltu ovet, aivan kuten teimme Trevor, ja Trevor teki Super hyvin tällä kertaa. Mutta Jay teki sen puoli yhtä nopeasti. [VIDEOTOISTOSTA] -The Tavoitteena on nyt myös löytää meidät numero 50, mutta ei se algoritmisesti, ja Kerro meille miten aiot siitä. -OK. -Ja Jos löydät sen, pidät elokuvan. Jos et löydä sitä, annat sen takaisin. -karstaamattomista. -Oi! - [Kuultavissa] OK. Joten aion tarkistaa päät ensimmäinen onko there's-- Oh. [APPLAUSE] [Lopeta toisto] DAVID J. MALAN: OK. Joten lajittelu ovet selvästi johtaa suurempaan tehokkuuteen. Ja niin, kaksi kertaa niin nopeasti on mitä tarkoitin siellä. Ja niin Jay onnisti molemmilla kerroilla. Ja hän sai myös onnekas, että viime vuosi, Tilasin Blu-ray-levyjä todella antaa ulos. Olen pahoillani tänä vuonna, me ei ollut sama, Trevor. Mutta vielä parempi oli muutama vuosi sitten. Ja jotkut teistä ehkä tietävät tämän kaveri, Sean, kuka kun hän oli CS50, altistettiin tarkka Sama ongelma, vaikkakin SD, niin voit pian nähdä, takaisin seuraavana päivänä. Ja huomaat, että ei ainoastaan hän kestää hieman kauemmin kuin Jay, hieman kauemmin kuin Trevor, se oli Oikeastaan ​​tämä loistava tilaisuus harjoittaa lähes kaikki Yleisö la hinta on oikea, kannustamalla hänet löytää numero olimme etsivät. Katsotaanpa. vilkaista. [VIDEOTOISTOSTA] -OK. Joten teidän tehtävänne täällä, Sean, on seuraava. Olen piilossa nämä ovet numero seitsemän. Mutta makaavat joissakin näistä ovet sekä muita negatiivisia lukuja. Ja sinun tehtäväsi on ajatella Tämän ylärivin numerot kuten juuri array, tai vain sekvenssi paperinpaloja numerot niiden takana. Ja tavoitteena on, vain käyttämällä alkuun array täällä, etsi minulle numero seitsemän. Ja olemme sitten menee kritiikkiä miten edetä tee sitä. -Selvä. Find meille numero seitsemän, kiitos. Ei. Viisi, 19, 13. [Nauraa] Se ei ole temppu kysymys. Yksi. [Nauraa] Tässä vaiheessa, sinun pisteet ei ole kovin hyvä, joten voit yhtä hyvin jatkaa. Kolme. [Nauraa] Jatka. Suoraan sanottuna, en voi olla ihmettelemättä mitä olet edes ajatellut, so-- [Nauraa] Vain ylärivi, joten sinulla kolme vasemmalle. Joten löytää minut seitsemän. [Nauraa] 17. Seitsemän. [APPLAUSE] Selvä. [Lopeta toisto] DAVID J. MALAN: jotta voisimme katsella näitä koko päivän. Ja tietenkin, jotkut Tämän vuoden demoja ehkä nyt päätyvät ensi vuoden video samoin. Joten Nyt todella keskitytään algoritmien täällä, ja katso jos emme voi nyt alkaa virallistaa miten voimme mennä noin saada tietomme tähän tilaan, että se on lajiteltu, niin että lopulta voimme todella etsiä sitä tehokkaammin. Ja vaikka me aiomme käyttää melko pieniä aineistoja, kuten kahdeksan numeroa meillä on tässä pöydällä, lopulta nämä samat ajatukset voitaisiin soveltaa 1000 tuloa, miljoonaa tuloa, 4000000000 tuloa, koska algoritmit tulevat olemaan pohjimmiltaan sama. Ja niin tämä on meidän viimeinen tilaisuus vapaaehtoisia tänään, mutta ehkä kaikkein mukana yksi, josta meillä tarvitsevat kahdeksan vapaaehtoisia keksiä ja kävellä meitä prosessi lajittelu mitä pian olla seuraavilla musiikki seisoo täällä. Aloitan takaisin tänne. Joten yksi turquoise-- vihreä on se? Oletko syyllistyneet? Kaksi. Tule alas. OK. Kolme. Neljä. Anna me-- OK, viisi. Olet parhaillaan nimeämä ystäväsi. Kuusi, seitsemän ja kahdeksan. Tule ylös. Selvä. Kiitos paljon. Tule ylös. Tule ylös. Selvä. Joten mitä meillä here-- ja tämä on yksi enemmän hankala niistä, koska tämä edellyttää, että olet huumori minulle vain vähän aikaa. Sinun on ykkönen. Mikä on nimesi? Annan: Annan. DAVID J. MALAN: Annan. David. Mikä on nimesi? JOSEPH: Joseph. DAVID J. MALAN: Joseph, olet numero kaksi. SERENA: Serena, numero kolme. Stefan, numero neljä. CYNTHIA: Cynthia. DAVID J. MALAN: Cynthia, numero viisi. [Äänetön] DAVID J. MALAN: [äänetön]. David, numero kuusi. MATT: Matt. DAVID J. MALAN: Mattin numero seitsemän. Ja? WAVERLY: Waverly. DAVID J. MALAN: Waverly, numero kahdeksan. Selvä. Jos could-- oho. Jos kaikki, kuin Ensimmäinen haaste, siellä kahdeksan Nuottitelineet tässä yleisöön päin. Jos voit laittaa numerot nämä musiikki seisoo siten että he riviin Sama numerot taululle. Joten tehdä itse näyttää, että laittamalla numerot seuraavilla musiikki seisoo täällä. Erinomainen toistaiseksi. Erinomainen. OK. Joten nyt, me pyydämme kysymys muutamalla eri tavalla. Kuinka voimme edetä lajittelu nämä ihmiset täällä? Koska meillä oli muutamia lähestymistapoja aikaisemmin, jolloin olimme sellainen tehdään kaksi eri kauhat. Ja sitten olimme yleisesti vähitellen luonut asioita yhdessä. Heti kun näimme kaksi lukua jotka kuuluivat yhteen, laitamme ne yhteen. Kaksi kirjainta, jotka kuuluvat yhteen. Mutta katsotaanpa, jos me voi virallistaa tätä, jotta voimme lopulta jotkut pseudo-koodi haluatte, jolla voit ratkaista nämä ongelmat. Joten nyt, etsin ulos näitä numeroita täällä. Ja näen koko joukko virheitä. Lopulta haluan yksi vasemmalle ja kahdeksan oikealla. Ja niin Etsin nämä kaksi, neljä ja kaksi. Ja mikä on ongelma, ilmeisesti? Joo. So. Kaksi ilmeisesti tulee ennen neljä, niin tiedät mitä? Haluaisin ensin ottaa ahne lähestymistapa, jos haluatte, aivan kuten ongelma asettaa one-- jos muistan Standard Edition Harjoitus One, missä minä vain paikallisesti ratkaista ongelma se täällä edessäni ja katso mihin se johtaa minua. OK. Joten kaksi ja neljä, anna minun mennä eteenpäin ja vain vaihtaa te kaksi. Jos voit fyysisesti liikkua itsenne ja paperi, Olen ilmeisesti saanut luetella paremmassa kunnossa. Nyt he ovat hyviä. Aion siirtyä, neljä ja kuusi, näyttää hyvältä. Ei ole ongelma. Kuusi ja kahdeksan, OK. Kahdeksan ja yksi, toinen ongelma. Sillä mitä on totta noin kahdeksan ja yksi? Yksi tulee ennen kahdeksaa, ja niin mitä meidän pitäisi tehdä? Katsotaanpa vaihtaa nämä kaksi. Yksi ja kahdeksan. Ja nyt, aion jatkaa. Aion pitää Jatkossakin. Ja katsotaan mitä tapahtuu. Kahdeksan ja kolme, ja Tietenkin epäkunnossa. Katsotaanpa swap. Kahdeksan ja seitsemän, tietenkin. Epäkunnossa. Katsotaanpa swap. Kahdeksan ja viisi, tietenkin, katsotaanpa swap. Selvä. Lista on järjestetty. kyllä? OK, ei tietenkään. Mutta se on hieman parempi, eikö? Koska ilmoitus mitä tapahtui. Joka kerta teimme swap, pienempi määrä sellainen percolated näin, ja isompi numero percolated näin, tai käymme alkavat sanoa kuplina on vasemmalle tai kuplia oikealle. Nyt, se ei riitä, koska parhaimmillaan luku saattaa ovat siirtyneet yksi paikalla eteenpäin, tai pahimmillaan, numero voi olla siirretty yhdellä paikalla edelleen. Niin tiedät mitä, tällainen on toiminut melko hyvin tähän asti. Sallikaa minun vain kokeilla sitä uudelleen. Kaksi ja neljä, he OK. Neljä ja kuusi, ne ovat OK. Kuusi ja yksi, epäkunnossa. Joten vaihtaa te kaksi. Ja nyt, huomaa ongelma: n alkaa saada hieman paremmin taas. Kuusi ja kolme, epäkunnossa. Katsotaanpa vaihtaa sinulle kaksi. Kuusi ja seitsemän, olet hyvä. Seitsemän ja viisi, tietenkin, epäkunnossa. Seitsemän ja kahdeksan, jotta. Ja nyt, minä ehkä tehdä tämän muutaman kerran. Ja itse asiassa ajatella itsellenne ehkä kuinka monta kertaa maksimaalisesti voisin kävellä edestakaisin? Palaamme tähän. Joten kaksi ja neljä ovat vielä OK. Neljä ja yksi, nope. Joten, nyt swap. Ja vielä, havaitse yksi on sellainen kuplivaa vasemmalle, missä sen pitäisi olla. Neljä ja kolme swap. Neljä ja kuusi. Kuusi ja viisi swap. Kuusi ja seitsemän. Seitsemän ja kahdeksan ovat hyviä. Hyvä. Saamme jopa parempi. Katsotaanpa. Nyt meillä on kaksi ja yksi. Tietenkin, vaihtaa. Kaksi ja kolme, kolme ja neljä, neljä ja viisi, kuusi ja seitsemän, seitsemän ja kahdeksan. Hyvä. Ja tiedätkö mitä? Koska olen tehnyt yhden muutoksen siellä, anna minun tehdä yksi järki tarkistaa. Anna minun mennä aina alkuun. OK. Yksi, two-- Joo, katso? Jotain oli vialla. Kolme, neljä, viisi, kuusi, seitsemän, kahdeksan. Ja tässä viime taaksepäin, ovat viihtyisää minun nyt väittämällä lajitellaan? OK. Visuaalisesti se on aivan totta. Mutta toiminnallisesti, mitä ei myös vain tapahdu että viime pass, jonka avulla voit vahvistaa, että tämä luettelo on todellakin lajiteltu? Mitä olen tehnyt tai ei tehdä tätä viime pass? Yleisö: ei tapahtunut muutoksia. DAVID J. MALAN: Anteeksi? Yleisö: Ei muutoksia. DAVID J. MALAN: ei tapahtunut muutoksia. Joten olisi typerää minua tehdä samaa algoritmia uudelleen jos en tee mitään muuttaa ensimmäistä kertaa. Ja valtio ei ole muuttunut. Totisesti, en aio tehdä Muutoksista toisen kerran. Ja niin, se on turvallista nyt sanoa, Lista on järjestetty. Ja todellakin, tämä on nyt jotain, että me will yleisesti puhelu kuplalajittelu, jolloin pareittain, voit korjata virheitä uudelleen, ja uudestaan, ja uudestaan, ja sinä jatka edestakaisin, ja edestakaisin, kunnes tehdä tällaista swap, jossa vaiheessa voit olla varma, joo, minä päättynyt vahvistamisesta kaikki virheet. Katsotaanpa nollata ja kokeile toista lähestymistapaa. Jos te voisi mennä takaisin tilaus olit hetki sitten, joka näytti tältä. Nyt, ottaa lähestymistapa hieman enemmän kuin tentti kirja, jolloin olimme jatkuvasti valitsemalla kirjain että me eräänlainen halusimme käsitellä seuraavaksi. Ehkä se oli korkea kirjeen, kuten tai alhainen kirjain Z. Joten kaikki on taas tässä järjestyksessä. Ja nyt haluan tehdä tätä. Katsotaanpa Tiedän, että olen kahdeksan numeroa täällä. Aion mennä eteenpäin ja vain tarkoituksella valitse pienin elementtejä. Oikea? Tämä tuntuu intuitiivinen liikaa. Miksi en löydä pienimmän elementti, laita se minne se kuuluu, sitten saada seuraavaksi pienin elementti, laittaa se mihin se kuuluu, ja vain toista. Koska intuitiivisesti, että pitäisi toimia myös. Niin neljä, se on aika pieni määrä. Aion muistaa, missä tämä on. Hetkinen. Kaksi on pienempi. Saanen nyt muista missä kaksi on, ja unohtaa neljä. Me käsitellä myöhemmin. Kuusi, en ole kiinnostunut. Kahdeksan, en ole kiinnostunut. Yksi on minun uusi pieni määrä. Joten aion muistaa missä yksi on. Kolme, ei kiinnosta. Seitsemän, ei kiinnosta. Viisi, ei kiinnosta. Joten putoamatta vaiheessa tänä vuonna, Aion napata numero one-- ja mikä oli nimesi uudelleen? Annan: Annan. DAVID J. MALAN: Annan. Ja jos voisi liittyä minua listan alkuun, Laitetaan minne kuulut. Unfortunately-- mikä on nimesi? STEFAN: Stefan. DAVID J. MALAN: Stefan on tiellä. Joten ennen Stefan ratkaisee tämän ongelma, mitä meidän pitäisi tehdä? Mitä teemme Stefan? Yleisö: [äänetön]. DAVID J. MALAN: OK. Jotta voisimme tehdä sen. Voisimme tavallaan ottaa Stefan ja hänen neljä, ja vain laittaa se muuttuja ja pitää kiinni sitä jonkin verran aikaa, jolloin tilaa ykkönen. Ja se ei ole huono. Voisin ehdottaa, miksi ei me vain laittaa Stefan täällä? Miksi tämä voisi rikkoa yksi ideoita aloimme puhumme viimeisen kerran, viime viikolla? Joo? Yleisö: [äänetön]. DAVID J. MALAN: Ei ole indeksiä varten se. Jos luulet tämän, todellakin, kuten array, tämä on kuin negatiivinen, joten ei ole muistia oikeastaan tässä jos tämä on todellakin joukko, kuten me julisti viime viikolla luento. Joten meidän ei pitäisi tehdä tätä. Saatamme tallentaa sen muuttujaan. Tai tiedätkö mitä? Kuulin joku muu ehdottaa sitä. Mitä muuta voisimme tehdä Stefan? Miksi emme vain häätää hänet ja laittaa hänet jossa ykkönen oli. Joten jos haluat mennä sinne. Ja itse asiassa tämä on melko hyvä ratkaisu. Nyt toisaalta, olen kiltti on tehty ongelman pahempi. Neljä on nyt kauempana josta se pitäisi olla. Sen pitäisi olla kohti tätä puolet. Mutta tiedätkö mitä? Se olisi voinut olla huonoa onnea. Ehkä numero kahdeksan oli täällä. Ja niin, ehkä olisimme saanut onnekas, ja työnsi kahdeksan lähemmäksi loppua. Joten loppujen lopuksi, se tavallaan kaikki keskiarvot ulos. Meidän ei tarvitse välittää neljä. Kaikki välitän juuri nyt on valitaan pienin elementti. Ja nyt, mitä aion do on unohtaa numero yksi pysyvästi, koska tiedän lista takanani on nyt järjestetty. Joten minun lista oli aiemmin koko kahdeksan. Nyt on koosta seitsemän. Joten minun ongelma on tulossa pienempi, vaikkakin lineaarisesti. Joten nyt, aion valita nykyinen pienin elementti, kaksi. Kuusi, kahdeksan, neljä, kolme, seitsemän, viisi. Se oli pienin elementti. Joten mitä olen menossa tekemään with-- mikä oli nimesi uudelleen? JOSEPH: Joseph. DAVID J. MALAN: Joseph? Aiomme jättää Joseph paikallaan. Nyt aion teeskennellä että nämä kaverit are-- hyvin, Tiedän, että nämä kaksi on jo järjestetty. Katsotaanpa nyt keskittyä Loput luettelon. Kuusi on nykyinen pienin. Kahdeksan on suurempi. Neljä on nyt nykyinen pienin. Kolme on nyt nykyinen pienin. Ja nyt, aion valita kolme, kuka is-- mikä on nimesi uudelleen? Serena: Serena. DAVID J. MALAN: Serena, jos voisit napata numero ja swap with-- Kalsang: Kalsang. DAVID J. MALAN: Kalsang. Tule takaisin, ja olemme menossa vaihtaa nämä kaksi. Ja nyt, nyt laittaa tämä autopilotilla. Aion mennä ja jättää sen te Valitse seuraavaksi pienin elementtejä. Dun, Dun Dun Dun. Numero neljä, mitä pitäisi tehdä? Erinomainen. Nyt, aion tehdä toinen omille. Dun, Dun Dun Dun. Näen viisi on seuraavaksi pienin. Nyt aion ottaa toisen omille. Dun, Dun Dun Dun. Kuusi on pienin. Hyvä. Seitsemän on pienin. Ei muutosta. Kahdeksan on pienin. Tehty. Joten mitä olemme juuri tehneet iteratiivisesti valitaan yksi elementti toisensa jälkeen on toteuttaa jotain, että olemme menossa virallistaa niin valinta lajitella. Ja se on ehkä jopa yksinkertaisempaa selittää, että kirjaimellisesti kaikki mitä haluat tehdä, on vain pitää menee edestakaisin luetteloa valinnassa, seuraavaksi pienin elementti, kunnes olet valmis. Joten se on jopa helpompaa, ehkä intuitiivisesti, kuin viime. Kokeillaan yksi viimeinen. Jos te voisi palauttaa itse seuraaviin kannat viimeistä kertaa, katsotaanpa jos emme voi nyt virallistaa yksi muu lähestymistapa. Itse asiassa, olisi joku siellä haluavat ehdottaa Miten muuten voisimme edetä tässä? Ilman tossing ulos iskulauseita tai lajitella vastauksia, jotka ovat jo tiedossa, vain intuitiivisesti, mitä voisimme tehdä? Yleisö: [äänetön]. DAVID J. MALAN: Joo. Joten ei hienoja intuitio siellä. Hyvät asiat näyttävät tapahtuvan toistaiseksi tietotekniikassa kun jaamme ja valloittaa ongelma jakamalla se puoliksi ja puolet ja puolet. Ja niin todellakin, me voisi alkaa tehdä niin. Ja itse asiassa, että tulee olemaan, me katso, yksi parhaita ratkaisuja vielä. Mutta katsotaanpa palata että ennen pitkää. Itse asiassa, aiomme tehdä että hieman myöhemmin tällä viikolla. Mitä muuta voisi teemme ratkaista tämän? Joten jokainen täällä on näennäisesti satunnaisessa järjestyksessä. Arvaa mitä? Eikä mennä edestakaisin, edestakaisin, edestakaisin joka kerta, tämä tuntuu Teen paljon kävelyä. Miksi en vain alkaa klo listan alkuun, ja vain laittaa neljä minne se kuuluu? Sallikaa minun olettaa tällä hetkellä, että lista on vain tämä ensimmäinen elementti. On neljä järjestetty tällä hetkellä, jos kaikki Välitän on kaikki täällä? Tämä on tavallaan triviaalisti totta, eikö? Kuten listan, joka sisältää yhden numeron, ja että numero neljä on ilmeisesti lajitellaan. Joten haluan vain määrätä että tämä lista lajitellaan. Mutta nyt minulla on loput tästä luettelosta. Joten nyt, I kohtaavat kaksi. Mistä kaksi ilmeisesti kuuluvat suhteen neljä? Ennen neljä. Mitä voin tehdä täällä? Mikä nimesi olikaan? JOSEPH: Joseph. DAVID J. MALAN: Joseph, jos voisit askel taaksepäin vain hetki puhelinnumerosi. Ja nyt, mitä pitäisi Stefan tehdä täällä? Katsotaanpa siirtää Stefan täällä. Ja nyt, anna Joseph tänne. Ja nyt, haluan väittää, että kaikki täällä lajitellaan. Joten, samanlainen tulos, mutta täysin eri lähestymistapaa. En ole edes tutkinut, mitä siellä. Minä vain pitää ottaen elementit koska he ojensi minulle, ja käsitellä niitä. Joten nyt, näen numero kuusi. Mistä numero kuusi kuuluu? Meillä on kaksi, neljä, kuusi. Tarkalleen missä hän on nyt. Joten jätä että yksin, ja nyt väittävät, että tämä osa luettelon on nyt järjestetty. Ja niin, tämä tuntuu pohjimmiltaan erilainen, että olen vain liikkuvat läpi listan täällä lineaarisesti, ja olen koskaan kaksinkertaistaa takaisin. Kyllä. Selvä. Niin kahdeksan, jossa sinä kuulut? Juuri täällä. Täydellinen. Joten nyt, yksi. O-ou. Tämä tuntuu se tulee kalliiksi. Nyt, edellisessä algoritmi, Minä vain vaihtoivat ihmisiä. Niin voisin laittaa hänet aina osoitteessa alussa, mutta sitten muutti Joseph. Mutta jos muutan Joosef, nyt mitä tulee olla väärässä? Nyt, olen tavallaan undone-- olen otetaan yksi askel eteenpäin ja sitten yksi askel taaksepäin, koska nyt Joseph olisi epäkunnossa. Joten tehdään tämä. Jos voisit ottaa numero yksi ja askel taaksepäin vain hetken. Miten voimme put-- mitä oli nimesi uudelleen? Annan: Annan. DAVID J. MALAN: Annan paikallaan? Mitä täytyy tapahtua suhteen kaksi, neljä, kuusi ja kahdeksan? He kaikki tarvitsevat siirtää. Joten jos kahdeksan haluaa siirtää ensin, sitten kuusi, sitten neljä, sitten kaksi. Ja sitten Annan, jos haluat haluavat tulla tänne, hyvä. Mutta täällä, olemme juuri Tällainen maksettu hinta on eri vaiheessa algoritmi. Kun viime aikaa valinta lajitella, ja jopa kuplalajittelu, Kävelen takaisin ja edestakaisin, edestakaisin, joka on varmasti laskemalla ajallisesti, ja kirjaimellisesti vaiheittain. Lisäyslajittelun, aluksi silmäyksellä, näyttää se Super fiksumpia, että olen vain hitaasti, vähitellen edistystä, mutta en aio tätä edestakaisin. Mutta jos joku on todellakin epäkunnossa, ilmoitus kaikki työ oli ihan pakko tehdä. Minulla oli siirtyä puoliskon vain tehdä tilaa ykkönen. Joten se on sama määrä Työn toistaiseksi se tuntuu, vain eri tyyppistä työtä. Jatketaan. Joten nyt me tiedämme, että jokainen yhdestä kahdeksan lajitellaan. Täällä minulla on numero kolme. Jos haluat poimia numero kolme, askel taaksepäin yksi. Ja mitä te tarvitse tehdä? Jep. Niin, että on toinen, kaksi, kolme vaihetta. Kolme aikayksikköinä että vain maksaa minua, joten kolme voivat nyt sovi. Lopuksi, seitsemän. Mennään eteenpäin ja on voit ottaa askel taaksepäin. Tämä on vain tulee maksamaan meille yhden yksikön aikaa, mutta se on OK. Ja nyt, viisi on menossa olla hieman kalliimpaa. Jos haluat askel taaksepäin. Meidän on edettävä kahdeksan, ja seitsemän, ja kuusi. Ja sitten kaikki on nyt järjestetty. Joten iso käsi meidän vapaaehtoisille täällä. Kiitos paljon. [APPLAUSE] Kiitos kaikille. Kiitos kaikille. Katsotaanpa nyt, kuinka kalliiksi kaikki tämä oli. Tarkastellaan ehkä Yksinkertaisin näistä, kuplalajittelu. Ja sanon yksinkertaisin, vain koska voit ratkaista sen ahnaasti vain hieman korjata pareittain ongelma. Korjaa pareittain ongelma täällä, uudestaan ​​ja uudestaan ja uudelleen, toistamalla niin monta kertaa kuin itse tarvitse. Joten käy ilmi, että jossa kuplalajittelu, hyvin, kuinka monta askelta minun täytyy ottaa ensikierron saman algoritmin? Saatan take-- nyt see-- yksi, kaksi, kolme, neljä, viisi, kuusi, seitsemän. Ja siellä on kahdeksan elementtejä täällä. Joten se on kuin n miinus 1 toimenpiteet saada listan alkuun loppuun luettelosta. Mutta valinta lajitella, muistaa, että olen valitsemalla elementit uudelleen ja uudelleen ja taas se on pienin, Laitan sen paikallaan, mutta sitten en ole looking takanani uudelleen. Niin mielestäni se on hieman selkeä sitten, että ensimmäinen kerta, voisin on otettava kaikki n miinus 1 vaiheet löytää pienin alkio. Sitten laitoin ne paikoilleen, ja minä häätää kuka oli täällä aiemmin. Mutta sitten ei tarvitse pitää tarkastella tätä elementtiä, koska tiedän, että se on jo pienin. Joten nyt, en voi katsoa vain seitsemän elementtejä, sitten kuusi elementtejä, sitten viisi elementtiä, sitten neljä osatekijää. Ja niin matemaattisesti, jos n on alkioiden lukumäärä tai numerot että aloitimme, voit kuvitella että tämä on sama kuin n-miinus 1, plus n miinus 2 askelta, plus n miinus 3 vaiheet, plus n miinus 4 askelmaa, kaikki alas vain yhden askeleen. Ja olen viimeinen henkilö. Ja jos muistaa, että paljon ja tilastot kirjoja tai matematiikka kirjoja on niitä kaavojen kovakantinen takaisin tai niiden edessä, käy ilmi, että tämä sarja voidaan ilmaista yksinkertaisemmin kuten n kertaa n miinus 1 yli 2. Ja se on hienoa, jos se ei ole eturintamassa mieltäsi. Mutta tämä on totta. Se on vain yksinkertaisempi tapa kirjoittaa se. Ja sitten jos luulet takaisin alakoulussa, kun vain aloittaa kertomalla asioita, tämä tietenkin, on vain n potenssiin miinus n jaettuna 2. Kaikki Olen tehnyt on laajentaa ilmaisuja siellä. Ja niin katsotaanpa kirjoittaa tämä hieman eri tavalla. Joka on n neliöidystä jaettuna 2 miinus n / 2. Joten jälleen, olen juuri sellainen soveltamisesta jotkut aritmeettinen säännöt siellä. Mutta huomaa nyt, että suurin termi tässä ilmaisua, niin sanoakseni, on, että n potenssiin. Joten kyllä, se on n potenssiin jaettuna 2, miinus n / 2. Mutta yleensä, jos n on olemaan iso arvo, Aion väittää n potenssiin tulee olemaan määräävä tekijä. Se on vain olemaan isompi avustaja ja useita vaiheita kuin n / 2. Joten mitä minä tarkoitan tällä? Kokeillaan yksinkertainen esimerkki, vaikka vaikka matematiikka saa hieman iso. Joten Oletetaan meillä oli 1.000.000 ihmistä lavalla tai 1000000 asiat että haluamme lajitella. Katsotaanpa plug miljoonaa osaksi juuri, että kaava kuinka monta askelta kestää yhteensä lajitella miljoona elementtejä käyttäen sanoa, valinta lajitella. Joten meillä olisi sama kaava kuin ennen. Olin plug miljoonaa, niin että saan miljoona neliöidystä jaettuna 2, miinus miljoona jaettuna 2. Jos en, että matematiikka etukäteen täällä, meillä on 500 miljardin miinus 500000, joka antaa meille 499999500000, joka on tosi iso. Itse asiassa, jos vertaa nyt 499000000000, 999000000, 500000 vastaan ​​meidän alkuperäisestä arvosta, 500000000000, se on niin pirun lähellä. Oikea? n neliöidystä jaettuna 2 antaa us-- tai pikemminkin, n ruudutettu jaettuna 2 antoi meille 500000000000. Se on tosi lähellä on 499999500000, toisin sanoen vähentämällä pois 500000, tai yleisemmin, vähentämällä pois n potenssiin, ei oikeastaan ​​iso juttu. N potenssiin tekee nämä numerot kasvavat todella nopeasti. Nyt, tämä on tärkeää vain sikäli kuten me, kuin tietotekniikan tutkijoita, yleensä aio välitä niin paljon noin vivahteita näiden kaavojen ja mitä täsmällisiä vastauksia ovat. Välitämme vain että, tiedätkö mitä? Lopussa päivän, tämä kaava on suuruusluokkaa n neliö. Kyllä, olemme jakamalla 2 siellä. Kyllä, olemme vähentämällä pois n miinus 2. Mutta lopussa päivän, aikavälin että todella satuttaa meitä ja maksaa meille runsaasti portaita on, että neliö aikavälillä. Ja niin mitä tietojenkäsittelytieteessä aikoo yleensä tehdä on sivuuttaa kaikki nämä pienempi asteen termit, ja katsokaa joka vaikuttaa eniten kustannuksia. Ja tämä on mukavaa, koska voimme nyt puhua paljon enemmän yleispätevyyttä noin algoritmeja, ja voi vertailla niitä. Ja se, että olen tällä O on tahallista. Kun sanon määräyksestä on, olen nimenomaan viittaa jotain sanottujen suurten O. ja Big O on merkintä, että tietokone tiedemies käyttää kuvaamaan yläraja jotain. Joten jos sanot että algoritmi on iso O n potenssiin, kuten ehdotin juuri hetki sitten, että välineet että mitä sen käynnissä aikaa tai sen tehokkuus, se ottaa tilauksen n potenssiin vaiheita. Ehkä enemmän, ehkä vähemmän. Mutta se on suuruusluokkaa n neliö. Ja se on yläraja. Se ei tule olemaan enemmän tuskallista kuin että. Se ei tule olemaan n kuutioitu, tai 2 ja n, tai jotain paljon suurempi. Tämä on yläraja siitä mitä se kustannus on. Niin sillä, katsotaanpa harkita vain muutamia esimerkkejä. Ja tämä on vain rajallinen luettelo on hyvin yleinen käynnissä kertaa algoritmeja, jotka on tarkoitus olla havainnollistavat joitakin asioita olemme nähty jo. Niin esimerkiksi, kun kyseessä on valinta lajitella, mitä olen väittäen täällä on, että valinta lajitella n käynnissä aika on suuruusluokkaa n neliö. Pahimmassa tapauksessa aion olla koko joukko satunnaisia ​​numeroita täällä. Ja kuten näimme matemaattisesti, jos pidän kävely luetteloa, kautta luettelo, valitaan seuraavaksi pienin elementti uudelleen ja uudelleen, jos en oikeastaan ​​kirjoittaa kaikki vaiheet Otan kuten ehdotin formulaically ennen, se on luokkaa n potenssiin vaiheet että otan. Ja käy ilmi, että kupla lajitella ja lisäyslajittelun ovat yhtä hitaita pahimmassa tapauksessa. Mieti esimerkiksi lisäyslajittelun, viimeinen algoritmi käsittelimme, joka oli meitä katsomaan elementti, ja aseta se mihin se kuuluu. Ja sitten me katsoimme seuraavaan elementtiin, ja lisätään se mihin se kuuluu. Joten harkita paras mahdollinen skenaario. Oletetaan Olin minun vapaaehtoisille riviin kirjaimellisesti näin, yksi kautta kahdeksan, jo järjestetty. Kuinka monta askelta on lisäyslajittelun aikoo ryhtyä lajitella kahdeksan ihmistä, jos he saapuvat lavalla näköisenä tämä? Kahdeksan ihmistä jo järjestetty. Ja käytän lisäyslajittelun. Että viimeinen algoritmeja. No, katsotaanpa uudelleen säätää todella nopeasti. Joten jos aloitan täällä, näen yksi. Jos ei yksi kuuluu? Se kuuluu täällä. Näen kaksi. Missä kaksi kuuluu? Juuri täällä. Näen kolme. Mistä kolme kuuluu? Juuri täällä. Näen neljä. Juuri täällä. Viisi, kuusi, seitsemän, kahdeksan. Ei ole mitään syytä toistaa itseäni. Ja niin, kuinka monta askelta on, että mitä n? Se on järjestyksessä n vaiheet, eikö? n miinus 1. Mutta otin lineaarinen numero vaiheita, ja nyt olen valmis. Niin, että parhaassa tapauksessa, vaikka. Entä pahimmassa tapauksessa? Mitkä kahdeksan oli siellä, ja seitsemän oli siellä, ja yksi ja kaksi oli täällä, joten että luettelo oli todella päinvastainen? No, mitä tapahtuu todella jos tämä on numero? Ja teemme vain pari esimerkkiä. Mitä jos todellakin numero kahdeksan on täällä, ja number-- oho. Joten mitä jos todellakin numero kahdeksan on aina tänne, ja olen käyttäen lisäyslajittelun? OK. Väitän tällä hetkellä se on paikallaan. Mutta nyt, seven-- mistä seitsemän mennä? Tietenkin, se menee tänne. Joten minun täytyy siirtää kahdeksan yli yhteen paikkaan. Nyt kuusi, jossa se kulkee? No, hyvä on. Nyt minun täytyy siirtää kahdeksan yli paikka, ja seitsemän yli paikka, ja sitten minä plop alas kuusi. Joten ensimmäistä kertaa, se maksaa minulle yksi askel korjata asioita, sitten se maksoi minulle kaksi askelta korjata asioita. Kuinka monta askelta on se vie korjata asiat laittaa viisi oikeassa paikassa? Kolme. Koska nyt minun täytyy siirtää yksi, kaksi, kolme. Kuinka monta askelta se aikoo ottaa laittaa neljä oikeassa paikassa? 4 + 5 + 6, ja 7. Ja niin se on matemaattisesti identtinen mitä me kuvattiin valinta lajitella. Meillä on tämä sarja Se on vain kasvussa. 1 plus 2 plus 3 plus 4, tai päinvastoin, 7 ja 6 plus 5 plus 4 lisää jopa nykypäivän tarkoituksiin luokkaa n neliö. Haluan siis määrätään myös, että kuplalajittelu on myös n potenssiin. Nimittäin kuplalajittelu, kukin kun menen läpi listan, Otan suunnilleen kuinka monta askelta? Joka kerta olen kirjaimellisesti kävellä sieltä siellä? Noin n vaiheet. Mutta kuinka monta kertaa pitää I täytyy mennä läpi listan? No, karkeasti n aikaa. Ehkä n miinus 1, mutta karkeasti n kertaa. No, miksi? No, kuplalajittelu, jos aloitamme kuplalajittelu, kanssa alalta pahin mahdollinen tilanne, joka taas on täysin taaksepäin, mitä tulee tapahtumaan? Käyn läpi listan, ja numero yksi kuuluu aina tuolla. Mutta kuplalajittelu, kuinka pitkälle ei yksi siirtyä minun ensimmäinen läpi listan? Kuinka paljon pisteitä hän saa lähemmäksi oikeaan paikkaan? Vain yksi. Joten jos sellainen syy kautta, joka kerta kautta tämä algoritmi, Daavidin ottaen karkeasti n toimiin. Mutta kuinka monta vaihetta luetteloa on se vie yhdestä kupla vasemmalle minne se kuuluu? Hänen täytyy liikkua kuten, n tilat tällä tavalla. Joten tehdä lajittelu luettelon, Minun täytyy kävellä edestakaisin n kertaa. Ja joka kerta, olen katsot n elementtiä. Niin n asioita n kertaa järjestys n neliö. Nyt näemme joissakin ja shortsit että on upotettu CS50 seuraava ongelma set, toinen lähestymistapa näitä, mutta nyt haluan vain harkita joitakin muita käynnissä aikoina, varsinkin jos lajittelu niistä ottaa vähän aikaa uppoavat. Mikä algoritmi olemme nähneet jo joka vie suuruusluokkaa n vaiheet? Mitä pitäisi lineaarinen numero vaiheita, jotka olemme nähneet tähän mennessä? Mikä tuo on? Puhelinluettelo haku. Ensimmäinen algoritmi. Oikea? Missä olemme lineaarisesti etsivät Mike Smith? Todellakin. Viikosta nolla, kun aloin kääntämällä yhden sivun kerrallaan, ja olen jopa sanoi, että se oli eräänlainen lineaarisen tunne algoritmia, ja meillä oli, että kuva aluksella suora punainen viiva ja suora keltainen linja, ne olivat todellakin algoritmeja, jotka ovat Big O n. Koska löytää Mike Smith puhelimessa kirja n sivuja, pahimmassa tapauksessa, Ottaa minut n toimiin. Entä kun läsnäolo? Yksi kaksi kolme neljä viisi kuusi. Mikä käyntiaika tämän algoritmi ottaa läsnäolo? Big O n, koska teoriassa I on kohta kaikki huoneessa. Nyt kun syrjään, entä muut optimointi viikosta nolla? Kaksi, neljä, kuusi, kahdeksan, 10, 12. Tietojenkäsittelytieteessä olisi ymmärtää, odota minuutti, joka on luokkaa n jaettuna kahdessa vaiheessa. Oikea? Koska mulla kaksi ihmistä kerrallaan. Mutta aiomme sivuuttaa ne alemman asteen termit, ja olemme juuri menossa heittää pois jaa 2, ja vain sanoa, iso O n että algoritmi samoin. Entä tämä? Me ohittaa joitakin näistä, mutta mitä oli algoritmi, joka on log-n? Se kesti noin log n vaiheet? Hajota ja hallitse. Aivan. Kuten puhelinluettelon esimerkki viikko nolla ja aiemmin tänään, jossa jaoimme ongelma uudestaan ​​ja uudestaan ​​ja uudestaan. Me veti sen taululle viikolla nolla kaareva vihreä linja, ja sanoimme, että päivä oli logaritminen algoritmi. Ja todellakin, useita vaiheita se vie suorittaa hajoita ja hallitse, tai binäärihakupuu kuin aloitamme kutsuen sitä, kuten puhelinluettelossa, on luokkaa tukin ja vaiheita. Ja tämä on hieman outo yksi. Mitä ottaa yhden askeleen, tai erityisemmin jatkuva useita vaiheita? Ehkä se on kaksi, ehkä se kolme, mutta tietokone tiedemies juuri yksinkertaistaa sitä iso O 1, jotkut jatkuva useita vaiheita. Mikä jotain voisi tehdä, että vie jatkuva useita toimia? Mikä ajoaika taputus? Jatkuva aika. Oikea? Kuten, mitä ajoaika tee mitään, joka vie vain yksi toiminta, kuten tulostaa F Hello World. Se voidaan sanoa olevan vakio ajan, ellei vähemmän nurkassa tapauksessa tulostaa F, Mikä voisi käyntiaika tulostaa F todella? Ja miksi? Mikä on n mitta tässä tapauksessa? Yleisö: [äänetön]. DAVID J. MALAN: Aivan. Merkkien määrä haluamme tulostaa. Joten on erittäin tilannekohtaisia. Tänään olemme keskittyneet erän kirjaimia ja numeroita tässä taululle. Mutta se voi olla merkkejä todellinen merkkijono. Joten se kääntyy pois on toinen toimenpide, joka alkaa välittämistä, ja se on päinvastainen iso O, niin sanoakseni. Se on omega merkintää. Kun taas iso O tarkoittaa mitä, yläraja teidän aika? Maksimaalisesti, kuinka paljon aikaa ehkä jotain kestää? Omega-- anteeksi tämä pitää tulossa up-- on vastakohta, että jolloin se on alaraja on aikaa jotain saattaa kestää. So. esimerkiksi, mitä algoritmia joka vie aina n potenssiin vaiheet? No, yksi algoritmien olemme nähneet tänään, itse asiassa, voi olla, että yhtä hyvin. Valinta lajitella. Valinta sort on melko typerää. Vaikka algorithm-- pahoillani, jopa jos jono on jo järjestetty, valinta lajitella aikoo pitää kävelevän lista varmista, että se on pienin elementti uudestaan ​​ja uudestaan ​​ja uudestaan. Ja vaikka ihmisille yleisö tietää, että hetkinen, olet jo läpäissyt pienin alkio, tietokone ei tiedä, että ennen kuin se näyttää kaikki läpi listan. Vastaavasti, alaraja, joka voi myös otettava huomioon voisi olla lineaarinen aika. Kuinka kauan kestää lajitella n elementtejä paras tapauksessa käyttäen jotain kuplalajittelu? Oletetaan lista on jo järjestetty. Sanoimme kuplalajittelu ottaa järjestys n neliö vaiheita. Mutta mitä jos se on jo järjestetty? Mitä jos huomaat jälkeen yksi läpi array että olet tehnyt mitään swap? Tarvitseeko sinun pitää tehdä enemmän kulkee? Ei. Joten alaraja kuplalajittelu voidaan sanoa olevan lineaarinen. Omega n. Ja voimme tarkastella toiset näistä samoin. Joten ottaa vilkaista juuri visualisointi täällä miten nämä erottuvat. Aion mennä alas täällä tähän sivu, joka on saatavilla C50: n verkkosivuilla, mutta se on tuskaa saada työ, koska se käyttää tekniikkaa kutsutaan Java-sovelmat, joka on pitkälti tueta näinä päivinä, ainakin Chrome ja tietyt muut. Ja anna minun mennä eteenpäin ja nopeuttaa tätä ylös ja selittää, mitä on tekeillä. Tämä on osoitus kupla lajitella, ensimmäinen algoritmi tarkastelimme. Ja se on visualisointi, että kukin Näiden baareja on luku. Isompi baari, isompi numero. Pienempi palkki, pienempi numero. Ja mitä näet visuaalisesti, jopa vaikka tämä on menossa huippunopea, on, että punainen palkki on kuin minä, kävely edestakaisin vahvistamisesta ongelmia. Voit nähdä, että isompi elementit todellakin kuplii oikealle, ja pienemmät elementit ovat kuplii vasemmalle. Ja tänne, jos me todella lähemmin, voimme todella luottaa määrä vertailuja ja swap joita tehdään. Mutta sen sijaan, katsotaanpa toisessa algoritmi me katsoimme aiemmin meidän vapaaehtoisia, valinta lajitella. Visuaalisesti se on hyvin erilainen vaikutus. Mutta se on, jälleen, hyvin intuitiivinen, vuonna että pidämme valitaan seuraavaksi pienin elementti, ja saimme hieman onnekas. Joka tuntui pohjimmiltaan nopeampaa. Mutta jos me juoksi tätä uudelleen ja uudelleen ja jälleen paljon panoksia, näkisimme, että se on todellakin edelleen iso O n neliö. Tehdään yksi viimeinen täällä, lisäyslajittelun, joka oli kolmas algoritmi me katsoimme, ja muistuttaa että tämä yksi käsittelee elementtejä se kohtaa niitä, mutta sitten se ehkä vuorossa asioita yli tehdä tilaa, lisäämällä elementtejä jos ne kuuluvat. Ja tämäkin päätyy antamaan lopputulokseen. Nyt kaikki kolme näistä tuntui melko nopeasti. Ja todellakin, juoksin heitä klo aika hyvä leike. Mutta pohjimmiltaan, he kaikki aika kamala, olla rehellinen. Kaikki nämä algoritmit toistaiseksi että nousun sisään Big O n potenssiin ottaa melko vähän aika juosta lopulta. Ja todellakin, voimme nähdä ja tuntea tämä lopuksi jos vedän ylös tämä kolmas ja viimeinen demo. Tämä on toinen visualisointi että menee näyttää kuplalajittelu vasemmalla, valinta lajitella keskellä, ja jotain, koska yksi käytetyt herättää aiemmin ehdottanut, yhdistää lajitella oikealla. Hajota ja hallitse strategia oikealla. Ja se on itse asiassa mitä olemme menossa katsomaan keskiviikkona. Mutta katsotaanpa aikaa nämä rinnakkain. Se on suunnilleen sama määrä elementtejä, kaikki käynnissä samaan aikaan. Kuplalajittelu vs valinta lajitella vs Yhdistämisen lajitella. Nyt he kaikki käynnissä teoriassa samalla. CPU on käynnissä samalla nopeudella, mutta sinä voi tuntea kuinka tylsää tämä on hyvin nopeasti tulossa, ja kuinka nopeasti, kun me pistää vähän viikko nolla n algoritmeja voidaan me nopeuttaa asioita. Ja nyt Katsotaanpa vertailla nämä yhdessä viime muodossa. Aion mennä eteenpäin että CS50 verkkosivuilla, jossa meillä on tämä viimeinen lenkki tänään, jos joku internetissä ystävällisesti koota video, joka kaappaa mitä eri lajittelu algoritmeja kuulostaa. Tämä on lisäyslajittelun. [Piippaa] Jolloin olet soveltamalla taajuus perustuu korkeus bar bar. Tämä on kuplalajittelu. [Warped piippaa] Tulossa seuraavaksi is-- tulevina seuraavaksi is-- valinta lajitella, jossa jälleen, olemme valitsemalla seuraavaksi pienin elementti, ja voimme nähdä sen kasvaa vasemmalta oikealle. Yhdistä lajitella, meidän voittaja toistaiseksi tänään. Huomaa, miten se jakaa asioita osaksi [äänetön] puoli ja neljäsosaa. Gnome lajitella, jotka emme ole puhui, ja luo visuaalisesti ja audally hieman eri muotoisia ja ääni. Going edestakaisin, puhdistaa asioita. Tutustu myös Kekojärjestäminen tämän kaveri verkkosivuilla. Ja se on siinä. Tulemme näkemään ensi kerralla. [Whooshing ja musiikki]