>> [Musiikki soi]
DAVID MALAN: Okei.
Okei, tervetuloa takaisin.
Joten tämä on viikolla 4, alussa sen jo.
Ja voit muistaa, että viime viikolla, laitamme koodata varattu vain vähän
ja aloimme puhua hieman korkean tason, asioita, kuten
etsiminen ja lajittelu, joka tosin hieman yksinkertaisia ​​ideoita, ovat
tyypillinen luokan ongelmia alatte ratkaista erityisesti
kun alkaa miettiä lopullinen hankkeisiin ja mielenkiintoisia ratkaisuja sinulle
ehkä reaalimaailman ongelmia.
Nyt kupla tavallaan oli yksi yksinkertaisin tällaisia ​​algoritmeja, ja se
työskenteli ottaa nämä pienet numerot luettelon tai matriisin sellainen
kupla tiensä ylös, ja suuret numerot siirtää alas
loppuun luetteloon.
>> Ja muistuttaa, että voisimme visualisoida kupla tavallaan hieman
jotain tällaista.
Joten anna minun mennä eteenpäin ja napsauta Käynnistä.
Olen ennalta kupla tavallaan.
Ja jos muistatte, että pitempi sininen linjat edustavat suuret numerot, pieni
siniset viivat edustavat pienien kuin käymme läpi tämän uudestaan ​​ja uudestaan ​​ja
uudelleen, vertaamalla kaksi baaria vierekkäin toinen punainen, aiomme vaihtaa
suurin ja pienin, jos ne ovat epäkunnossa.
>> Joten tämä menee päälle ja mennä ja mennä on, ja näet, että suurempi
elementit tiensä oikealle, ja pienemmät elementit ovat
tiensä vasemmalle.
Mutta aloimme määrällisesti tehokkuutta,
laatu tämä algoritmi.
Ja sanoimme, että pahimmassa tapauksessa tämä algoritmi kesti
suunnilleen kuinka monta askelta?
>> Joten n potenssiin.
Ja mikä oli n?
>> Yleisö: elementtien määrä.
>> DAVID MALAN: Joten n oli useita tekijöitä.
Ja niin me teemme tätä usein.
Aina me haluamme puhua koko ongelma tai kokoa
tulo tai aikaa kuluu tuottaa tuotos, me vain
yleistynyt riippumatta tulo on kuin n.
Joten takaisin viikolla 0, numero sivujen puhelinluettelosta, oli n.
Opiskelijoiden määrä huone oli n.
Niin täälläkin, olemme jälkeen että kuvio.
>> Nyt n potenssiin ei ole erityisen nopeasti, joten yritimme tehdä paremmin.
Ja niin me katsoimme pari muita algoritmeja, joista
oli valinta lajitella.
Joten valinta tavallaan oli hieman erilainen.
Se oli melkein yksinkertaisempaa, uskallan sanoa, jolloin aloitin alussa
luettelo meidän vapaaehtoisille ja minä vain kerran ja uudestaan ​​ja uudestaan ​​meni läpi
lista, nyppiminen pois pienin elementti kerrallaan ja työnsivät tai
hänen alussa luettelosta.
>> Mutta tämäkin, kun aloimme ajatella läpi matematiikka ja isompi
kuva, ajatellut kuinka monta kertaa Olin menossa edestakaisin ja takaisin
edestakaisin, totesimme pahimmassa tapauksessa valinta lajitella, liian, oli mitä?
n potenssiin.
Nyt todellisessa maailmassa, se saattaa todella vähän nopeammin.
Koska taas, en tarvitse pitää vetäytymistä kerran olin lajiteltu
pienin elementtejä.
Mutta jos ajattelemme hyvin suuri n ja jos tavallaan tehdä pois matematiikasta sen
Tein pöydällä, jossa n potenssiin miinus jotain, kaikki muu
lisäksi n potenssiin, kun n saa todella suuri, ei
oikeastaan ​​väliä niin paljon.
Niin tietotekniikan tutkijoita, me tavallaan ummistaa silmänsä pienempi
tekijät ja keskittyä vain tekijä lauseke, joka tulee tehdä
Suurin ero.
>> No, lopuksi, me katsoimme klo lisäyslajittelu.
Ja tämä oli hengeltään samanlainen, mutta eikä mene läpi iteratiivisesti ja
Valitse pienin elementti yksitellen aikaa, olen sen sijaan otti käsi I
oli käsitelty, ja päätin, kaikki oikeassa, sinä kuulut tänne.
Sitten minä siirryin seuraavaan elementtiin ja päätti, että hän tai
hän kuului täällä.
Ja sitten muutin ja.
Ja voisin sen, matkan varrella, siirtää nämä kaverit, jotta
tehdä tilaa heille.
Niin, että oli tavallaan henkistä kääntyminen valinnan sellaista, että me
nimeltään lisäyslajittelu.
>> Joten näitä aiheita esiintyy todellisessa maailmassa.
Vain muutama vuosi sitten, kun tietty senaattori käynnissä presidentiksi,
Eric Schmidt, tuolloin toimitusjohtaja Google, todella oli mahdollisuus
haastattelemaan häntä.
Ja ajattelimme jakaa tämän YouTube clip sinua täällä, jos voisimme kääntää ylös
äänenvoimakkuutta.
>> [VIDEOTOISTOSTA]
>> -Senaattori, olet täällä Google, ja haluan ajatella puheenjohtajakauden
kuin työhaastattelu.
>> [Naurua]
>> -Nyt on vaikea saada työtä presidenttinä.
Ja olet menossa läpi jäykkyys nyt.
On myös vaikea saada työpaikan Google.
Meillä on kysymyksiä ja pyydämme meidän ehdokkaita kysymyksiä.
Ja tämä yksi on Larry Schwimmer.
>> [Naurua]
-Luuletteko olen tosissasi?
Se on täällä.
Mikä on tehokkain tapa lajitella miljoonaa kahden bitin kokonaislukuja?
>> [Naurua]
>> -No, öh -
>> -Olen pahoillani.
Ehkä meidän pitäisi -
>> -Ei, ei, ei, ei, ei.
>> -Se ei ole -
OK.
>> -Mielestäni kupla semmoista on väärä tapa edetä.
>> [Naurua]
>> [Hurraavat ja suosionosoituksia]
>> -Tule, jotka kertoivat hänelle tämän?
OK.
>> [END VIDEOTOISTOSTA]
>> DAVID MALAN: Siinäpä se.
Joten aloimme määrällisesti näiden käynnissä kertaa, niin sanotusti, jotain
kutsutaan asymptoottinen merkintätapa, joka on tarkoita pelkästään meidän eräänlainen käännekohta
silmänsä ne pienet tekijät ja tarkastellaan vain ajoaika
suorituskykyä näiden algoritmien N saa todella suuren ajan.
Ja niin me otettiin iso O. Ja iso O edustaa jotain, ajattelimme
AS ylärajana.
Ja todella, Barry, voimme laskea kuin mic vähän?
>> Ajattelimme tämän on yläraja.
Joten iso O n potenssiin tarkoittaa, että Pahimmassa tapauksessa jotain
valinta sort veisi n potenssiin vaiheet.
Tai jotain lisäyslajittelu olisi n potenssiin vaiheet.
Nyt jotain paikoilleen lajitella, mikä oli pahin?
Koska joukko, mikä on pahin mahdollinen skenaario, että saatat löytää
itsesi edessä?
>> Se on täysin taaksepäin, eikö?
Koska jos se on täysin taaksepäin, sinun täytyy tehdä paljon työtä.
Koska jos olet täysin taaksepäin, olet menossa löytää
Suurin osa täällä, vaikka se kuuluu sinne.
Joten aiot sanoa, okei, kello tällä hetkellä, et kuulu tänne,
niin jätät sen yksin.
>> Niin huomaat, oh, damn, minun on siirtää tätä hieman pienempi tekijä
vasemmalla teistä.
Sitten minun täytyy tehdä se uudestaan ja uudestaan ​​ja uudestaan.
Ja jos minä kävelin edestakaisin, sinä olisi tavallaan tuntuu suorituskykyä
että algoritmi, koska jatkuvasti olen laahustavat kaikki muutkin alas
array tehdä sille tilaa.
Niin, että pahimmassa tapauksessa.
>> Sen sijaan -
ja tämä oli jännitysnäytelmä viimeisen kerran -
sanoimme, että lisäyslajittelu oli omega, mitä?
Mikä on parhaassa tapauksessa käynnissä aika lisäyslajittelu?
Joten se on todella n.
Se oli tyhjä, että lähdimme taululle viimeisen kerran.
>> Ja se on omega n koska miksi?
No, parasta tapauksessa mitä lisäyslajittelu aiotaan luovuttaa?
No, luettelo, joka on täysin lajiteltu jo vähän työtä tehdä.
Mutta mitä on siisti noin lisäyslajittelu on, että koska se alkaa täällä
päättää, oh, olet numero yksi, sinä kuulut tänne.
Voi, mikä onni.
>> Olet numero kaksi.
Sinulla on myös kuulu tänne.
Numero kolme, jopa parempi, et kuulu tänne.
Heti kun se saa loppuun lista, per lisäyslajittelu n pseudokoodina
että kävelimme läpi suullisesti Viimeisen kerran, se on tehty.
Mutta valinta lajitella, sen sijaan, pidetään tekee mitä?
>> Piti läpi lista uudestaan ​​ja uudestaan ​​ja uudestaan.
Koska keskeinen oivallus oli vain kun olet etsinyt aina
luettelon loppuun voit olla varma että elementti valitsemasi oli
todellakin tällä hetkellä pienin elementti.
Niinpä nämä eri ajattelumallien lopussa up saatiin hyvin reaalimaailman
eroja meille, sekä näiden teoreettinen asymptoottinen eroja.
>> Joten vain kertaus, sitten iso O n potenssiin, olemme nähneet muutamia tällaisia
algoritmeja toistaiseksi.
Big O n?
Mitä algoritmi, joka voisi sanoa olevan iso O n?
Pahimmassa tapauksessa, se kestää lineaarinen useita vaiheita.
>> OK, lineaarista hakua.
Ja pahimmassa tapauksessa, jossa on elementti etsit, kun
soveltamalla lineaarista hakua?
>> OK, pahimmassa tapauksessa, se ei ole edes olemassa.
Tai toiseen pahimmassa tapauksessa se on aina lopulta, joka on
plus-tai miinus-yksi-vaihe ero.
Joten lopussa päivä, Voimme sanoa, että se lineaarinen.
Big O n olisi lineaarinen haku, sillä pahimmassa tapauksessa,
elementti ei ole edes olemassa tai se on koko matkan lopussa.
>> No, iso O log n.
Emme puhuneet hyvin yksityiskohtaisesti noin , mutta olemme nähneet tämän ennenkin.
Mikä toimii ns logaritminen aikaa, pahimmassa tapauksessa?
>> Joo, niin binäärihaku.
Ja binäärihaku pahimmassa tapauksessa saattaa olla tekijä jossain
keski-tai jonnekin sisällä array.
Mutta et vain löydä sitä kerran jakaa listan kahtia, vuonna
puoli, puoli, puoli.
Ja sitten voila, se on olemassa.
Tai jälleen, pahimmassa tapauksessa se ei ole edes olemassa.
Mutta et tiedä, että se ei ole siellä kunnes tavallaan päästä, että viime
alimmaisen elementtejä puolittamalla ja puolittaa ja puolittaa.
>> Big O 1.
Joten voisimme iso O 2, iso O 3.
Milloin haluat vain vakiomäärä, me vain eräänlainen vain yksinkertaistaa
että iso O 1.
Vaikka jos realistisesti, se kestää 2 tai jopa 100 askeleen, jos se on
jatkuvasti useita vaiheita, me vain sanoa iso O 1.
Mitä algoritmi, joka on iso O 1?
>> Yleisö: Finding pituus muuttujan.
>> DAVID MALAN: Finding pituus muuttuvan?
>> Yleisö: Ei, pituus jos se on jo järjestetty.
>> DAVID MALAN: Hyvä.
OK, niin löytää pituus jotain jos pituus, että jotain, kuten
array, tallennetaan joissakin muuttuja.
Koska voit lukea muuttujan tai tulostaa muuttujan tai
vain yleisesti käyttää muuttuja.
Ja voila, että kestää jatkuvaa aikaa.
>> Sen sijaan muistelen raapia.
Muistelen ensimmäisellä viikolla C, soittaa vain printf ja tulostus
jotain ruudulla on kiistatta vakioaikaisia, koska se vain vie
joitakin määrä suorittimen käytön näyttää että tekstiä ruudulla.
Tai odota - eihän?
Miten muuten voisimme mallintaa suorituskykyä printf?
Voisiko joku olla eri mieltä, että ehkä se ei ole oikeastaan ​​jatkuvaa aikaa?
Missä mielessä voisi printf juoksee aikaa, oikeastaan ​​tulostaa merkkijonon
näyttö, olla jotain muuta kuin vakio.
>> Yleisö: [kuultavissa].
>> DAVID MALAN: Joo.
Joten se riippuu meidän näkökulmasta.
Jos me todella ajattelemme panos printf olevan merkkijonon, ja
Siksi me mittaamme koko kyseisen syöttää sen pituus - joten kutsukaamme
että pituus n sekä -
Ilmeisesti printf on itse iso O n koska se vie sinut n toimet
tulostaa kaikki nämä n merkkiä, todennäköisesti.
Ainakin siltä osin, että oletamme että ehkä se käyttää silmukka
alla huppu.
>> Mutta meidän olisi tarkasteltava, että Koodi ymmärtää sitä paremmin.
Ja todellakin, kun kaverit alkaa analysoida omia algoritmeja, sinun
kirjaimellisesti tehdä juuri niin.
Lajittele silmämunan koodi ja ajatella noin - kaikki hyvin, minulla on tämä silmukka
tässä tai minulla on sisäkkäisiä silmukoita täällä, että aikoo tehdä n asioita n kertaa,
ja voit lajitella järjen tiesi koodin läpi, vaikka se on
pseudokoodina eikä varsinainen koodi.
>> Entä omega n potenssiin?
Mikä on algoritmi, joka on paras tapauksessa edelleen otti n potenssiin vaiheet?
Niin?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: Joten valinta lajitella.
Koska tämä ongelma todella vähentää siihen, että jälleen, en tiedä
Olen löytänyt nykyisen pienin asti Olen tarkistanut kaikki hiton elementtejä.
Joten omega vaikkapa n, me tuli juuri yksi.
Lisäyslajittelu.
Jos luettelo sattuu lajitella jo, parhaassa tapauksessa meidän on vain
tehdä kerralla läpi, jolloin emme varmasti.
Ja sitten, että voidaan sanoa olla lineaarinen, varmasti.
>> Entä omega 1?
Mitä, parhaassa tapauksessa saattaa kestää jatkuva useita vaiheita?
Joten lineaarinen haku, jos vain onnekas ja elementin etsit
on aivan listan alkuun, jos se jos olet aloittamassa
lineaarinen läpikäyminen luetteloon.
>> Ja tämä on totta useita asioita.
Esimerkiksi jopa binary haku on omega 1.
Koska mitä jos saat todella hiton onnekas ja ihan keskellä
levyjärjestelmän on määrä etsit?
Joten voit saada onnekas siellä samoin.
>> Tämä yksi, lopuksi omega n log n.
Joten n log n, emme oikeastaan puhua vielä, mutta -
>> Yleisö: Merge sort?
>> DAVID MALAN: Merge sort.
Se oli jännitysnäytelmä viime aikaa, jossa ehdotimme, ja osoitimme
visuaalisesti, että on olemassa algoritmeja.
Ja yhdistää tavallaan vain yksi tällainen algoritmi, joka on pohjimmiltaan nopeampi
kuin jotkut näistä muista tyyppejä.
Itse asiassa, yhdistää lyhyt ei ainoastaan Parhaassa tapauksessa n log n, pahimmassa
tapauksessa n log n.
Ja kun sinulla on tämä sattuma omega ja iso O on sama asia?
Voimme itse kuvata, että mitä kutsutaan theta, vaikka se on
hieman harvinaisempia.
Mutta se tarkoittaa vain kaksi bounds, tässä tapauksessa ovat samat.
>> Joten yhdistää tavallaan, mitä tämä todella pohjimmiltaan meille?
No, muistaa motivaatio.
Saanen vetää toinen animaatio emme katso viimeinen kerta.
Tämä yksi, sama idea, mutta se on hieman suurempi.
Ja aion mennä eteenpäin ja huomauttaa Ensimmäinen - meillä on lisäyslajittelu on
vasemmassa yläkulmassa, niin valinta lajitella, kupla lajitella, pari muunkinlaisia ​​-
kuori ja nopea - että emme ole keskustelleet noin, ja kasaan ja yhdistää tavallaan.
>> Joten ainakin yrittää keskittyä silmäsi kärkikolmikkoon vasemmalle ja sitten
yhdistää eräänlainen kun klikkaa Tämä vihreä nuoli.
Mutta minä annan ne kaikki ajaa, vain antaa sinulle tunteen monimuotoisuuden
algoritmeja, että olemassa maailmassa.
Aion antaa tämän nousun vain muutaman sekunnin.
Ja jos keskittyä silmäsi - pick algoritmi, keskittyä siihen vain
sekuntia - voit alkaa nähdä kuvio, että se toteuttaa.
>> Yhdistä lajitella, ilmoitus on tehty.
Heap lajitella, nopeasti lajitella, kuori -
joten se näyttää esittelimme kolme pahin algoritmit viime viikolla.
Mutta se on hyvä, että olemme täällä tänään katso yhdistäminen lajitella, joka on yksi
helpommalla on tarkastella, vaikka vaikka se todennäköisesti taipuu mielesi
vain vähän.
Täällä voimme nähdä, kuinka paljon valinta lajitella perseestä.
>> Mutta kääntöpuoli, se on todella helppo toteuttaa.
Ja ehkä P Set 3, joka on yksi algoritmeja valitsit toteuttaa
standardin painos.
Hienosäätää, aivan oikeassa.
>> Mutta jälleen kerran, kun n saa suuret, jos päättää panna nopeammin algoritmi
kuin sulautua lajitella, kertoimet ovat suurempia ja Suuremmat tulot, koodi on vain
menossa ajaa nopeammin.
Sivuston tulee toimimaan paremmin.
Käyttäjät tulevat olemaan onnellisempi.
Ja niin on nämä vaikutukset todella antaa
meille hieman syvemmällä ajatellut.
>> Joten katsomaan mitä sulautua sort on oikeastaan ​​kyse.
Viileä asia on, että sulautuvat sort on juuri tämä.
Tämä on taas mitä me olemme kutsuneet pseudokoodit pseudokoodina olento
Englanti-syntaksi.
Ja yksinkertaisuus on tavallaan kiehtovaa.
>> Joten tulo n elementtejä - niin, että tarkoittaa vain sitä, tässä on jono.
Se sai n asioita siinä.
Siinä kaikki sanomme siellä.
>> Jos n on pienempi kuin 2, palaa.
Joten se on vain vähäpätöinen asia.
Jos n on pienempi kuin 2, niin ilmeisesti se on 1 tai 0, jolloin asia
on jo järjestetty tai olematon, niin vain palata.
Ei mitään tekemistä.
Niin, että yksinkertainen asia nyppiä pois.
>> Else, meillä on kolme vaihetta.
Lajitella vasen puoli elementtejä, lajitella oikealla puolella elementtejä,
ja sitten yhdistää lajiteltu puolikkaat.
Mielenkiintoista tässä on se, että Olen sellainen punting, eikö?
On sellainen pyöreä määritelmän Tämän algoritmin.
Missä mielessä tämä algoritmi määritelmä pyöreä?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: Joo, minun lajittelu algoritmi, kaksi sen vaiheet ovat "tavallaan
jotain. "Ja niin, että herättää kysymys, hyvin, mitä aion käyttää
lajitella vasen puoli ja oikea puoli?
Ja kauneus tässä on se, että vaikka kerran, tämä on aistiharhoja
osa mahdollisesti voit käyttää samaa algoritmi lajitella vasen puoli.
>> Mutta hetkinen.
Kun olet kertonut lajitella vasen puoli, mitkä ovat kaksi
vaiheet tulee seuraavaksi?
Me lajitella vasen puoli vasen puoli ja oikea
puolet vasen puoli.
Hitto, miten voin lajitella nämä kaksi puolikkaat tai neljännekset, nyt?
>> Mutta se on OK.
Meillä on Lajittelualgoritmi täällä.
Ja vaikka saatat huolehtia ollenkaan Aluksi tämä on eräänlainen ääretön
silmukka, se on sykli, joka ei ole koskaan ehdi - se on menossa
päättyy, kun mitä tapahtuu?
Kun n on pienempi kuin 2.
Joka lopulta tulee tapahtumaan, koska jos pitää puolittaa ja
puolittaa puolittamaan nämä puolikkaat, varmasti lopulta olet menossa loppuun
jopa vain 1 tai 0 elementtejä.
Jolloin tämä algoritmi sanoo olet valmis.
>> Joten todellinen taika tässä algoritmi näyttää olevan
että viimeinen vaihe, yhdistäminen.
Tämä yksinkertainen ajatus vain yhdistämällä kaksi asioita, se mitä lopulta tapahtuu
jotta voimme järjestää erilaisia, sanotaanko, kahdeksan elementtejä.
Olen siis kahdeksan enemmän stressiä palloja ylös täällä kahdeksan paperille, ja yksi
Google Glass -
jonka saan pitää.
>> [Naurua]
>> DAVID MALAN: Jos voisimme ottaa kahdeksan vapaaehtoisia, ja katsotaan jos voimme
pelata tätä ulos, niin.
Vau, OK.
Tietotekniikassa on tulossa hauskaa.
Selvä.
Niin miten te kolme, Suurin käsi ylös.
Neljä takana.
Ja miten me teemme sinulle kolme tällä rivillä?
Ja neljä edessä.
Joten te kahdeksan, tule ylös.
>> [Naurua]
>> DAVID MALAN: Olen oikeastaan ole varma, mitä se on.
Onko stressi pallot?
Kirjoituspöydän lamput?
Materiaalia?
Internet?
>> OK.
Joten tule ylös.
Kuka haluaisi -
tulee koko ajan.
Katsotaanpa.
Ja tämä asettaa sinut paikkaan -
olet paikalla yksi.
Uh-oh, odota hetki.
1, 2, 3, 4, 5, 6, 7 - OH, hyvä.
Okei, olemme hyviä.
Okei, joten jokainen on paikka, mutta ei Google Glass.
Saanen jonottaa nämä ylös.
Mikä sinun nimesi on?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle?
Okei, saat näyttää pelle, jos se on OK.
No, minä myös, oletan, vain hetken.
Okei, valmiustilassa.
Olemme yrittäneet keksiä käyttää tapauksessa Google Glass, ja me
ajattelin että olisi hauskaa vain tehdä Tässä kun ihmiset ovat lavalla.
Me tallentaa maailman heidän näkökulmastaan.
Selvä.
Ei luultavasti mitä Google tarkoitettu.
Okei, jos et mielessä yllään Tämän seuraavan hankala minuuttia,
Se olisi hienoa.
>> Okei, joten meillä on täällä joukko elementtejä, ja että array, kohti
paperinpaloja nämä ihmiset " kädet, on tällä hetkellä lajittelematta.
>> MICHELLE: Voi, se on niin outoa.
>> DAVID MALAN: Se on aika paljon satunnaisia.
Ja vain hetken, aiomme kokeilla toteuttaa yhdistää tavallaan yhdessä
ja katso, että keskeiset oivallus on.
Ja temppu täällä merge sort on jotain, että emme ole oletettu vielä.
Me todella tarvitsemme lisätilaa.
Joten mitä tulee olemaan erityisen mielenkiintoista tässä on se, että nämä
kaverit ovat menossa liikkua hieman vähän, koska aion olettaa, että
siellä on ylimääräistä joukko tilaa, sanoa, oikealla takana.
>> Joten jos he takana tuoli, se toissijainen array.
Jos he istuvat täällä, se on ensisijainen jono.
Mutta tämä on voimavara, että meillä on ei velkarahalla toistaiseksi kupla
lajitella, jossa valinta lajitella, kanssa lisäyslajittelu.
Recall viime viikolla, kaikki vain Tällainen sekoitetaan paikallaan.
He eivät käytä mitään lisämuistia.
Teimme tilaa ihmisten liikkuvat ihmiset ympärillä.
>> Joten tämä on keskeinen oivallus, too.
Ei tämä kompromissi, yleisesti tietojenkäsittelytiede, resursseja.
Jos haluat nopeuttaa jotain kuten aika, olet menossa
on maksettava hinta.
Ja yksi näistä hinnoista on hyvin usein tilaa, muistin määrän tai kova
levytilaa, että käytät.
Tai suoraan sanoen määrä ohjelmoija aikaa.
Kuinka paljon aikaa se vie, ihmisten, todella toteuttaa joitakin enemmän
monimutkainen algoritmi.
Mutta tänään, kauppa-off on aikaa ja tilaa.
>> Joten jos te voisi vain pitäkää numerot, jotta voimme nähdä, että olet
todellakin vastaa 4, 2, 6, 1, 3, 7, 8.
Erinomainen.
Joten aion yrittää johdatella asioita, jos te voitte vain
noudattaa esimerkkiäni täällä.
>> Joten aion toteuttaa, ensin, ensimmäisessä vaiheessa pseudokoodi, joka on
syötettyjen n osia, jos n on alle 2, palaa sitten.
On selvää, että ei apply, joten siirrymme.
Joten lajitella vasemmalla puolella elementtejä.
Niin se tarkoittaa, aion keskittyä minun huomiota vain hetken seuraavilla
neljä kaveria täällä.
Okei, mitä teen seuraavaksi tehdä?
>> Yleisö: lajitella vasen puoli.
>> DAVID MALAN: Joten nyt minun täytyy lajitella vasen puoli nämä kaverit.
Koska taas olettaa itse Tavoitteena on lajitella vasen puoli.
Miten teet sen?
Seuraa ohjeita, vaikka vaikka teemme sen uudestaan.
Joten lajitella vasen puoli.
Nyt olen lajittelu nämä kaksi kaveria.
Mitä seuraavaksi?
>> Yleisö: lajitella vasen puoli.
>> DAVID MALAN: lajitella vasen puoli.
Joten nyt nämä, tämä paikka täällä, on lista koko 1.
Ja mikä sinun nimesi olikaan?
>> PRINCESS DAISY: Prinsessa Daisy.
>> DAVID MALAN: Prinsessa Daisy on täällä.
Ja niin hän on jo järjestetty, koska luettelo on koko 1.
Mitä seuraavaksi tehdä?
OK, palaa, koska luettelo on koko 1, joka on pienempi kuin 2.
Mikä sitten on seuraava askel?
Ja nyt sinulla on sellainen takapakkia mielessäsi.
>> Lajitella oikea puoli, joka on -
Mikä sinun nimesi on?
>> LINDA: Linda.
>> DAVID MALAN: Linda.
Ja niin mitä teemme nyt, että meillä on lista koko 1?
>> Yleisö: Return.
>> DAVID MALAN: varovainen.
Palaamme ensimmäinen, ja nyt kolmas askel - ja jos olen sellainen kuvaavat sitä
käsittää kaksi paikkaa nyt, nyt minä on yhdistää nämä kaksi asiaa.
Joten nyt valitettavasti elementtejä ovat epäkunnossa.
Mutta siitähän yhdistämismenettelystä alkaa saada pakottavia.
>> Joten jos te voisi nousta vain hetki, aion tarvitsevat teitä,
hetkellä vaiheeseen takana tuolin.
Ja jos Linda, koska 2 on pienempi kuin 4, mikset
tulet noin ensin?
Pysy siellä.
Joten Linda, tulet noin ensin.
>> Nyt todellisuudessa se on vain joukko voisimme siirtää hänet reaaliajassa
Tämän tuolin tällä paikalla.
Joten kuvitella, että kesti jonkin jatkuvaa useita vaiheita 1.
Ja nyt -
mutta meidän täytyy laittaa sinut ensimmäisen sijainnin tässä.
>> Ja nyt jos voisit tulla noin, samoin, aiomme
olla paikalla kaksi.
Ja vaikka tämä tuntuu se ottaen samalla, mitä mukavaa nyt
että vasen puoli vasen puoli on nyt järjestetty.
Joten mikä oli seuraava askel, jos me nyt kelaa edelleen tarina?
>> Yleisö: Oikea puoli.
>> DAVID MALAN: lajitella oikea puoli.
Joten te täytyy tehdä tämä, samoin.
Joten jos voisitte seisomaan vain hetken?
Ja mikä on nimesi?
>> JESS: Jess.
>> DAVID MALAN: Jess.
OK, joten Jess on nyt vasen puolet oikealla puolella.
Ja niin hän on luettelo koko 1.
Hän ilmeisesti lajitellaan.
Ja sinun nimesi olikaan?
>> MICHELLE: Michelle.
>> DAVID MALAN: Michelle on tietenkin luettelo koko 1.
Hän on jo järjestetty.
Joten nyt taika tapahtuu, yhdistämismenettelystä.
Joten kuka tulee ensiksi?
Ilmeisesti Michelle.
Joten jos voisit tulla ympäri takaisin.
Tilaa meillä on käytettävissä hänen nyt on oikeassa takana tuolin täällä.
Ja nyt jos voisit palata sekä, meillä on nyt, on selvää, kaksi
puolikkaat, kukin kooltaan 2 -
ja vain kuvaus vuoksi, jos voisi tehdä vähän tilaa -
yksi jäljellä puoli täällä, yksi oikea puoli täällä.
>> Kelaa edelleen tarina.
Mikä vaihe on seuraava?
>> Yleisö: Yhdistä.
>> DAVID MALAN: Nyt meidän täytyy yhdistää.
Joten OK, joten nyt onneksi meillä vain vapautti neljä tuolia.
Joten olemme käyttäneet kaksi kertaa enemmän muistia, mutta voimme antaa flip-flopping välillä
kaksi paneelit.
Joten mikä numero on tulla ensin?
Joten Michelle, tietenkin.
Joten tulevat ympäri ja ottaa Varmista paikkasi.
Ja sitten numero 2 on ilmeisesti seuraava, niin tulet tänne.
Numero 4, numero 6.
Ja vielä, vaikka siellä vähän kävelyä mukana,
todella, nämä voi tapahtua hetkessä, siirtämällä yhtä -
OK, hyvin pelattu.
>> [Naurua]
>> DAVID MALAN: Ja nyt me olemme hyvässä kunnossa.
Vasen puoli koko tulo on nyt lajiteltu.
Okei, niin nämä kaverit oli etu minun -
miten se lopulta kaikki tytöt vasemmalle ja kaikki pojat oikealla?
>> OK, joten kaverit vuoro nyt.
Joten en opastaa nämä vaiheet.
Näemme, jos voimme hakea uudelleen Sama pseudokoodina.
Jos haluat mennä eteenpäin ja seisomaan, ja te, minä annan sinulle mic.
Katso jos et voi jäljitellä mitä me vain teimme täällä
muut listan loppuun.
Kuka tarvitsee puhua ensin, perusteella algoritmi?
Joten selittää, mitä olet tekemässä ennen teet jalka liikkeitä.
>> SPEAKER 1: Okei, joten sillä Olen vasen puoli
vasen puoli, palaan.
Oikea?
>> DAVID MALAN: Hyvä.
>> SPEAKER 1: Ja sitten -
>> DAVID MALAN: Kuka tekee mic mennä seuraavaksi?
>> SPEAKER 1: Seuraava numero.
>> SPEAKER 2: Olen siis oikea puoli ja vasen puoli
vasen puoli, ja palaan.
>> DAVID MALAN: Hyvä.
Palaat.
Joten nyt mitä seuraavaksi ylös sinulle kaksi?
>> SPEAKER 2: Haluamme nähdä, kuka on pienempi.
>> DAVID MALAN: Aivan.
Haluamme yhdistää.
Tilaa aiomme käyttää sulautua sinut, vaikka he
ilmeisesti lajitellaan jo aiomme noudattaa samaa algoritmia.
Kuka menee ensin takaisin?
Joten 3, ja sitten 7.
Ja nyt mic menee Näiden kaverit, OK?
>> SPEAKER 3: Olen siis oikea puoli vasen puoli, ja minun n on pienempi kuin
1, joten olen juuri menossa ohi -
>> DAVID MALAN: Hyvä.
>> SPEAKER 4: Olen oikea puoli oikea puoli oikea puoli, ja olen
Lisäksi yksi henkilö, joten olen aio palata.
Joten nyt olemme yhdistäminen.
>> SPEAKER 3: Eli menemme takaisin.
>> DAVID MALAN: Eli menet takaisin.
Joten 5 menee ensin, sitten 8.
Ja nyt yleisö, joka on vaiheeseen meidän on nyt kelata
takaisin mielessämme?
>> Yleisö: Yhdistä.
>> DAVID MALAN: yhdistäminen vasen puoli ja oikea puolet alkuperäisestä vasen puoli.
Joten nyt -
ja vain tehdä tämän selväksi, tehdä hieman tilaa
välillä te kaksi kaveria.
Joten nyt on kaksi listaa, vasemmalle ja oikealle.
Miten siis nyt sulautua te osaksi eturivin paikkaa uudelleen?
>> 3. menee ensin.
Sitten 5, tietenkin.
Sitten 7, ja nyt 8.
OK, ja nyt me olemme?
>> Yleisö: Ei tehty.
>> DAVID MALAN: Ei tehty, koska tietenkin, siellä on yksi askel jäljellä.
Mutta jälleen kerran, syy Käytän tätä sanastoa kuten "taaksepäin mielessäsi"
se on koska se on todella mitä tapahtuu.
Menemme läpi kaikki nämä vaiheet, mutta olemme tavallaan pysähtyen
hetki, sukellus syvemmälle algoritmi, pysähtyen hetkeksi,
sukellus syvemmälle algoritmin, ja nyt meillä on tavallaan taaksepäin meidän
mielissä ja kumoa kaikki nämä kerrokset että olemme tavallaan pitoon.
>> Meillä on nyt siis kaksi luetteloa koko 4.
Jos te voisi nousta viimeisen kerran ja tehdä vähän tilaa täällä
tehdä selväksi, että tämä on vasen puoleen alkuperäisestä,
oikeus puolet alkuperäisestä.
Kuka ensimmäinen numero että täytyy vetää takaisin?
Michelle, tietenkin.
>> Joten laitoimme Michelle täällä.
Ja kuka on numero 2?
Numero 2 syttyy takaisin samoin.
Numero 3?
Erinomainen.
Numero 4, numero 5, numero 6, numero 7 ja numero 8.
>> OK, joten se tuntui paljon vaiheita, varmasti.
Mutta nyt katsotaanpas jos emme voi vahvistaa eräänlainen intuitiivisesti, että tämä
algoritmi pohjimmiltaan, erityisesti n saa todella suuri, kuten olemme nähneet
kanssa animaatioita, on pohjimmiltaan nopeammin.
Joten Väitän tämä algoritmi pahimmassa tapauksessa ja jopa parhaassa tapauksessa
on iso O n kertaa log n.
Eli siellä on joitakin osa tätä algoritmi, joka vie n askelta, mutta
on toinen näkökohta jossain että iteraatio, että kiehkura, että
otetaan log n vaiheet.
Voimmeko laittaa sormi mitä ne kaksi numeroa viittaavat?
No, jos -
Minne mic mennä?
>> SPEAKER 1: Olisiko log n on rikkomatta meidät kahteen -
jakamalla kaksi lähinnä.
>> DAVID MALAN: Aivan.
Aina näemme missään ollen algoritmi mennessä siellä on ollut tämä malli
jakamalla, jakamalla, jakamalla.
Ja se yleensä vähenee jotain, joka on
logaritminen, logaritmina 2.
Mutta se voisi todella olla mitä tahansa, mutta logaritmi 2.
>> Mutta mites n?
Näen, että meillä sellainen jaettu sinua kaverit - jakaa teille, jakaa teille,
jakaa teille, jakaa teille.
Mistä lopulta tulee?
>> Joten se yhdistämistä.
Koska mieti sitä.
Kun yhdistät kahdeksan ihmistä yhdessä, jolloin puolet on asetettu neljä
ja toinen puoli ovat toinen Neljä, miten edetä
noin tekee yhdistäminen?
No, te teitte sen melko intuitiivisesti.
>> Mutta jos sen sijaan teki siitä hieman suunnitelmallisesti, olisin suunnattu
vasemmanpuoleisin henkilö ensin minun vasen käsi, huomautti vasemmalla henkilö
Kyseisen puolet minun oikealle puolelleni, ja vain myöhemmin käveli
lista, osoittaen pienimmän alkion joka kerta, liikkuvat minun sormella ja
yli tarpeen koko lista.
Mutta mitä näppäintä tästä sulautuvan prosessi on olen vertaamalla näitä paria
elementtejä.
Oikean puolen ja vasemman puoli, en kertaakaan vetäytymistä.
>> Joten yhdistäminen on itse tuossa enintään n askelta.
Ja kuinka monta kertaa olen tehdä, että yhdistäminen?
No, enintään n, ja me vain näki, että lopullinen yhdistämisen.
Ja niin jos teet jotain, joka vie log n askelta n kertaa, tai päinvastoin,
se tulee antamaan meille n kertaa log n.
>> Ja miksi tämä on parempi?
No, jos me jo tiedämme, että log n on parempi kuin n - eikö?
Näimme binäärihaku, puhelinluettelo Esimerkiksi log n oli ehdottomasti
parempi kuin lineaarinen.
Joten se tarkoittaa n kertaa log n on ehdottomasti parempi kuin n kertaa toisen
n, AKA n potenssiin.
Ja sitähän me lopulta tuntuu.
>> Joten aplodit, jos Voisimme nämä kaverit.
>> [APPLAUSE]
>> DAVID MALAN: Ja jakaus lahjat - voi pitää numerot,
jos haluat.
Ja jakaus lahja, kuten tavallista.
Niin, ja me lähetämme sinulle kuvamateriaalia, Michelle.
Kiitos.
Selvä.
Auta itseäsi stressipallo.
>> Ja haluan vetää, sillä välin, ystävämme Rob Bowden tarjota
hieman erilaisen näkökulman tähän, koska voit ajatella näitä
vaiheet tapahtuu hieman eri tavalla.
Itse asiassa, set-up, mitä Rob on noin näyttää meille olettaa, että olemme
jo jakamista ja iso lista kahdeksaan pieniä luetteloita,
kukin koko 1.
>> Joten me muutumme pseudokoodina hieman vain tavallaan saada aikaa
ydinajatuksena miten yhdistäminen toimivat.
Mutta ajoaika mitä hän on aikeissa tehdä, on edelleen
olemaan sama.
Ja vielä, set-up on, että hän on alkanut kahdeksan luettelot koko 1.
Joten olet jäänyt osa, jossa hän on todella tehneet log n, log n, log n
jakamalla tulo.
>> [VIDEOTOISTOSTA]
>> -Se on se ensimmäinen vaihe.
Vaiheessa kaksi, toistuvasti yhdistää paria luetteloita.
>> DAVID MALAN: Hm.
Vain ääni on tulossa pois minun tietokone.
Kokeillaan tätä uudelleen.
>> -Aivan mielivaltaisesti valita, - Nyt meillä on neljä luettelot.
Lue ennen.
>> DAVID MALAN: Siellä mennään.
>> -Yhdistäminen 108 ja 15, päädymme kanssa luettelon 15, 108.
Yhdistäminen 50 ja 4, me päätyä 4 50.
Yhdistäminen 8 ja 42, me päätyä 8, 42.
Ja yhdistämällä 23 ja 16, me päätyä 16, 23.
>> Nyt kaikki luettelot ovat kooltaan 2.
Huomaa, että kukin neljä luettelot lajitellaan.
Joten voimme aloittaa sulautuvan paria luettelot uudelleen.
Yhdistäminen 15 ja 108 ja 4 ja 50, me toteuttaa ensin 4, sitten 15, sitten
50, sitten 108.
Yhdistäminen 8, 42 ja 16, 23, ensin ottaa 8, sitten 16, sitten 23,
sitten 42.
>> Joten nyt meillä on vain kaksi luetteloa koko 4, joista kukin on järjestetty.
Nyt siis yhdistää nämä kaksi luetteloa.
Ensin otamme 4, niin otamme 8, sitten otamme 15, sitten 16, sitten
23, sitten 42, sitten 50, sitten 108.
>> [END VIDEOTOISTOSTA]
>> DAVID MALAN: Jälleen ilmoituksen, hän ei koskaan kosketti tietyn kuppi useamman kuin yhden kerran
jälkeen etenee pidemmälle.
Joten hän ei ole koskaan toistuvan.
Niin hän on aina siirtymässä puolelle, ja se jos saimme n.
>> Miksi ei anna minun vetää yksi animaatio että näimme aiemmin, mutta tällä kertaa
keskitytään vain merge sort.
Anna minun mennä eteenpäin ja zoomata sisään täällä.
Ensinnäkin haluan valita satunnainen tulo, tämä korostuu, ja voit tavallaan nähdä
mitä otimme itsestäänselvyytenä, aiemmin, yhdistää tavallaan todella tekee.
>> Niin huomaat että saat nämä puolikkaat tai neljännesvuoden tai näiden kahdeksasosaa
ongelma, että yhtäkkiä alkaa ottaa hyvässä kunnossa.
Ja lopulta, näet at aivan lopussa, että bam,
kaikki on sulautunut yhteen.
>> Joten nämä ovat vain kolme eri vie samaan ideaan.
Mutta avain oivalluksia, kuten kuilu ja valloittaa aivan ensiluokkainen,
oli, että päätimme jotenkin jakaa Ongelma tulee jotain suurta, osaksi
jotain tavallaan sama henki, mutta pienempiä ja pienempiä
ja pienempiä.
>> Nyt toinen hauska tapa tavallaan ajatella näistä, vaikka se ei ole
aio antaa teille saman intuitiivinen ymmärtäminen, on
seuraava animaatio.
Joten tämä on video joku koota että liittyvät eri
äänet eri toimintojen lisäyslajittelu varten yhdistäminen lajitella ja
ja pari muuta.
Joten hetki, aion lyödä Play.
Se on noin minuutin pituinen.
Ja vaikka et voi vielä nähdä kuvioita tapahtuu, tällä kertaa voit
myös kuulla, miten nämä algoritmit ovat suorittaa eri tavoin ja
hieman erilaisia ​​kuvioita.
>> Tämä on lisäyslajittelu.
>> [TONES PLAYING]
>> DAVID MALAN: Se taas yrittää lisätä jokaisen elementin
siitä, mihin se kuuluu.
Tämä on kupla tavallaan.
>> [TONES PLAYING]
>> DAVID MALAN: Ja voit tavallaan tuntuu miten suhteellisen vähän työtä se tekee
kussakin vaiheessa.
Tämä on mitä tediousness kuulostaa.
>> [TONES PLAYING]
>> DAVID MALAN: Tämä on valinta lajitella, jossa valitse elementti haluamme by
läpi uudestaan ​​ja uudestaan ​​ja uudestaan ja laittoi pallon alussa.
>> [TONES PLAYING]
>> DAVID MALAN: Tämä on yhdistää tavallaan, joka voit todella alkaa tuntea.
>> [TONES PLAYING]
>> [Naurua]
>> DAVID MALAN: Jotain nimeltään gnome lajitella, joita emme ole katsonut.
>> [TONES PLAYING]
>> DAVID MALAN: Niin anna minun nähdä, nyt hajamielinen kun toivottavasti ovat by
musiikkia, jos voin luistaa hieman vähän matematiikkaa täällä.
Joten on neljäsosa tavalla, että voimme miettiä, mitä se tarkoittaa, että nämä
toimintoja nopeammin kuin niitä että olemme nähneet ennen.
Ja jos olet tulossa kurssin matematiikan tausta, voit
oikeastaan ​​tiedä ehkä jo, että olet voi isku aikavälillä tähän tekniikkaan -
eli rekursio, toiminto että jotenkin kutsuu itseään.
>> Ja vielä, muistaa, että yhdistäminen lajitella pseudokoodina oli rekursiivinen mielessä
että yksi Merge sort askeleet oli soittaa tavallaan -
se on, itse.
Mutta onneksi, koska pidimme soittamalla lajitella tai yhdistää lajitella,
Erityisesti on pienempiä ja pienempi lista, me lopulta
pohjansa ansiosta mitä me kutsumme pohja tapauksessa koodattu niin, että
sanoi, että jos lista on pieni, alle 2 siinä tapauksessa, palaa heti.
Jos meillä ei ole, että erikoistapaus, algoritmi olisi koskaan pohja pois,
ja sinulla olisi todellakin päästä päättymättömään silmukkaan todella ikuisesti.
>> Mutta oletetaan, että halusimme nyt laittaa joitakin numeroita tässä, jälleen käyttäen n
kuin koko panos.
Ja halusin kysyä teiltä, ​​mitä kokonaisaika mukana
käynnissä Yhdistämisen tavallaan?
Tai yleisemmin, mitä kustannukset sen ajoissa?
>> No se on melko helppo mitata sitä.
Jos n on pienempi kuin 2, aikaa mukana lajittelussa n elementtejä,
jossa n on 2, on 0.
Koska me vain palata.
Ei ole tehtävää.
Nyt luultavasti, ehkä se on yksi askel tai kaksi vaiheet selvittää määrä
työtä, mutta se on tarpeeksi lähellä 0, että Olen juuri menossa sanoa mitään työtä ei
vaadita, jos lista on niin pieni on mielenkiinnoton.
>> Mutta tämä tapaus on mielenkiintoinen.
Rekursiivinen tapaus oli haara pseudokoodina että mainittu muuta, sort
vasen puoli, lajitella oikea puoli, yhdistää kaksi puolikasta.
Nyt miksi tämä ilmaus edustaa että kuluja?
No, T n vain sitä, aikaa selvittää n elementtejä.
Ja sitten oikealla puolella yhtäläisyysmerkkiä siellä, T n jaettu
2 viittaa kustannukset mitä?
Lajittelu vasen puoli.
Muut T n jaettuna 2 on oletettavasti viitaten kustannukset
lajitella oikea puoli.
>> Ja sitten plus n?
Onko yhdistämistä.
Koska jos sinulla on kaksi listaa, yksi koko n yli 2 ja toisen koko on n
yli 2, sinun on olemukseltaan jokainen näistä seikoista, kuten Rob
kosketti molempia kupit, ja vain kuten jo jokaisessa
vapaaehtoiset lavalla.
Joten n on kustannuksella yhdistämistä.
>> Nyt valitettavasti tämä kaava on myös itse rekursiivinen.
Joten jos kysyi, jos n on vaikkapa 16, jos siellä on 16 ihmistä lavalla
tai 16 kupillista video, kuinka monta yhteensä vaiheet kestää järjestellä
Yhdistäminen lajitella?
Se on oikeastaan ​​ole selvää vastausta, koska nyt sinulla on tavallaan
rekursiivisesti vastata tähän kaavaan.
>> Mutta se on OK, koska haluan ehdottaa että teemme seuraavat.
Aikaa mukana lajitella 16 henkilöä tai 16 kuppia tulee olla edustettuna
yleisesti T 16.
Mutta joka vastaa saamiemme edellinen kaava, 2 kertaa enemmän
aikaa kuluu lajitella 8 kuppia plus 16.
Ja vielä, plus 16 on aika yhdistää, ja kaksi kertaa T 8 on
aikaa selvittää vasen puoli ja oikea puoli.
>> Mutta jälleen kerran, tämä ei riitä.
Meidän täytyy sukeltaa syvemmälle.
Tämä tarkoittaa, että meidän on vastattava kysymys, mikä on T 8?
No T 8 on vain 2 kertaa T 4 +8.
No, mitä T 4?
T 4 on vain 2 kertaa T 2 plus 4.
No, mitä T 2?
T 2 on vain 2 kertaa T 1 plus 2.
>> Ja vielä, olemme tavallaan saada juuttunut tämä sykli.
Mutta se on osumassa, että ns base tapauksessa.
Koska mitä T 1, ei me väitämme?
0.
Joten nyt vihdoin, voimme työskennellä taaksepäin.
>> Jos T 1 on 0, voin nyt palata edelliselle linja tämä kaveri täällä, ja voin
plug in 0 T 1.
Niin se tarkoittaa, se vastaa 2 kertaa nolla, joka tunnetaan myös 0, plus 2.
Ja niin, että koko ilmaisua on 2.
>> Nyt jos otan T 2, jonka vastaus on 2, kytke se keskilinjaa, T
4, joka antaa minulle 2 kertaa 2 plus 4, joten 8.
Jos en kytke 8 edelliseen line, joka antaa minulle 2 kertaa 8, 16.
Ja jos me sitten jatkaa, että 24 lisäämällä, 16, me vihdoinkin
arvo 64.
>> Nyt sinänsä tavallaan puhuu mitään n merkintä,
iso O, omega, että olemme puhuneet.
Mutta näyttää siltä, ​​että 64 on todellakin 16, koko syöttö,
logaritmi 2 16.
Ja jos tämä on hieman tuntematon, vain muistelen, ja se tulee takaisin
sinulle lopulta.
Jos tämä on logaritmina 2, se on kuin 2 nostetaan mitä saat 16?
Voi, se on 4, niin se on 16 kertaa 4.
>> Ja vielä, se ei ole iso juttu, jos tämä on eräänlainen utuinen muisti nyt.
Mutta nyt, ottaa uskossa että 16 log 16 on 64.
Ja niin tosiaan, tämä yksinkertainen järki Tarkista, olemme vahvistaneet -
mutta ei osoittautunut muodollisesti -
että ajoaika Yhdistämisen sort on todellakin n log n.
>> Joten ei paha.
Se on ehdottomasti parempi kuin algoritmeja olemme nähneet tähän mennessä, ja
se on koska olemme velkarahalla, yksi, tekniikkaa kutsutaan rekursion.
Mutta mielenkiintoisempaa kuin, että käsitettä jakamalla ja valloittaa.
Jälleen todella viikolla 0 kamaa, että jo nyt on toistuva
enemmän pakottavia tavalla.
>> Nyt hauskaa vähän liikuntaa, jos olet koskaan tehnyt tätä - ja luultavasti
ei olisi, koska tavallaan normaalia ihmiset eivät usko tähän.
Mutta jos menen google.com ja jos Haluan oppia jotain
rekursio, Anna.
>> [Naurua]
[Naurua]
DAVID MALAN: Bad vitsi hitaasti leviää.
[Naurua]
DAVID MALAN: Vain siinä tapauksessa, että se on siellä.
En kirjoittaa sen väärin, ja siellä on vitsi.
Selvä.
Selitä sitä ihmisille vieressäsi jos Se ei ole aivan napsautetaan vielä.
Mutta rekursio yleisemmin viitataan prosessia toiminto soittaa
itse, tai yleisemmin, väliseinä ongelma jotain, joka voi olla
ratkaista vähitellen ratkaisemalla identtisiä edustaja ongelmia.
>> No, vaihtohammaspyöriä vain hetken.
Haluamme lopettaa tiettyjen cliffhangers, joten aloitamme asettaa
vaiheessa useita minuutteja, on hyvin yksinkertainen idea -
että vaihtava kahdesta osasta, eikö?
Kaikki nämä algoritmit olemme olleet puhumme parin viime
luentoja osallistuu noin tavallaan vaihtamalla.
Tänään se oli visualisoitu niitä saada ylös niiden puheenjohtajat ja
käveleminen, mutta koodi, olisimme ota elementti yhdestä array
ja plop se toiseen.
>> Miten siis edetä näin?
No, anna minun mennä eteenpäin ja kirjoittaa nopea ohjelma täältä.
Aion mennä eteenpäin ja tehdä tätä seuraava.
Kutsun tätä -
mitä haluamme kutsua tämä?
>> Oikeastaan ​​ei.
Minäpä taaksepäin.
En halua tehdä sitä jännitysnäytelmä vielä.
Se pilaa hauskaa.
Tehdään tämä sijaan.
>> Oletetaan, että haluan kirjoittaa hieman ohjelma ja että nyt kattaa tämän
Ajatus rekursio.
Olen sellainen sai ennen itseäni siellä.
Aion tehdä seuraavasti.
>> Ensinnäkin, nopea ovat standardin io.h, sekä include of cs50.h.
Ja sitten aion mennä eteenpäin ja julistaa int main void
tavalliseen tapaan.
Tajusin olen väärin nimetty tiedosto, niin haluan vain lisätä. c laajennus täällä niin
että voimme kääntää sen oikein.
Aloittaa tämän toiminnon pois päältä.
>> Ja toiminto Haluan kirjoittaa, varsin yksinkertaisesti, on yksi, joka kysyy
käyttäjän numero ja lisää jopa kaikki numerot välillä että
numero ja vaikkapa 0.
Ensin aion mennä eteenpäin ja julistaa int n.
Sitten voin kopioida koodia että olemme käyttäneet jonkin aikaa.
Vaikka jokin on totta.
Tulen takaisin hetken päästä.
>> Mitä haluat tehdä?
Haluan sanoa printf positiivinen kokonaisluku kiitos.
Ja sitten aion sanoa n saa saada int.
Joten jälleen, jotkut boilerplate koodi että olemme käyttäneet ennen.
Ja aion tehdä tämän kun n on pienempi kuin 1.
Joten näin varmistetaan, että käyttäjä antaa minulle positiivinen kokonaisluku.
>> Ja nyt aion tehdä seuraavaa.
Haluan lisätä jopa kaikki numerot välillä 1 ja ja n, tai 0 ja n,
yhtäpitävästi, saada kokonaissummasta.
Joten iso sigma symboli että saatatte muistaa.
Joten aion tehdä tämän ensimmäistä tehtäväänsä toiminto nimeltään sigma,
kulkee sen n, ja sitten aion sanovat printf, vastaus on oikeassa.
>> Joten lyhyt, saan ja int käyttäjältä.
Varmistan se on positiivista.
Julistan muuttuja nimeltä vastausta int ja säilytä se tuotto
arvo sigma, ohimennen n tulona.
Ja sitten tulostaa, että vastaus.
>> Valitettavasti, vaikka sigma kuulostaa jotain, joka voisi olla
math.h tiedosto, sen julistuksen, se ei todellisuudessa ole.
Niin se on OK.
Voin toteuttaa tämän itse.
Aion toteuttaa toiminto nimeltään sigma, ja se tulee ottaa
parametri -
Haluan vain kutsua sitä m, vain joten se on erilainen.
Ja sitten täällä, aion sanoa, hyvin, jos m on pienempi kuin 1 - tämä on
erittäin mielenkiinnoton ohjelma.
Joten aion mennä eteenpäin ja välittömästi palautettava 0.
Se vain ei ole mitään järkeä lisätä jopa kaikki numeroita välillä 1 ja m, jos m
itse 0 tai negatiivinen.
>> Ja sitten aion mennä eteenpäin ja tehdä tämän hyvin iteratiivisesti.
Aion tehdä tällaista vanhan koulukunnan, ja aion mennä eteenpäin
ja sanoa, että aion julistaa summa on 0.
Sitten aion olla varten silmukka int -
ja anna minun tehdä se vastaamaan meidän jakelu-koodi, joten sinulla on kopio
kotona. int i saa 1 asti i on pienempi tai yhtä suuri kuin m.
i plus plus.
Ja sitten sisällä tämän silmukan -
olemme melkein perillä -
summa saa summan plus 1.
Ja sitten aion palata summa.
>> Tein nopeasti, melko tosin.
Mutta jälleen kerran, päätehtävä on melko suoraviivainen perustuva koodi olemme
kirjoitettu tähän mennessä.
Käyttää kaksoislenkin saada positiivista int käyttäjältä.
Sitten tapahtui, että int uusi toiminto kutsutaan sigma, kutsuen sitä taas, n.
Ja minä tallentaa palauttaa arvo, vastaus alkaen musta laatikko hetkellä
tunnettu sigma, muuttujaan nimeltään vastaus.
Sitten voin tulostaa sen.
>> Jos me nyt jatkaa tarinaa, miten sigma toteutetaan?
Ehdotan toteuttaa seuraavasti.
Ensin hieman virheentarkistava varmistaa, että käyttäjä ei ole
Messing minun kanssani ja kulkee joitakin negatiivisia tai 0-arvo.
Sitten Julistan muuttuja nimeltä Yhteenvetona ja aseta se 0.
>> Ja nyt alkaa siirtyä i vastaa 1 aina enintään m,
koska haluan sisällyttää kaikki numerot yhdestä kautta m, mukaan lukien.
Ja sisällä tämä silmukka, en vain summa saa mitä se on nyt, plus
arvo i.
Plus arvo i.
>> Sivuhuomautuksena, jos et ole nähnyt tätä ennen, on joitakin syntaktisia sokeria
tällä linjalla.
Voin kirjoittaa tätä plus vastaa i, vain säästää itseäni muutamalla näppäimen painalluksella
ja näyttää hieman viileämpi.
Mutta siinä kaikki.
Se on toiminnallisesti sama asia.
>> Valitettavasti tämä koodi n aio laatia vielä.
Jos juoksen tehdä sigma 0, miten am Olen menossa huusin?
Mitä se aikoo pidä?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: Joo, en julistaa toiminto ylös, eikö?
C on typerää, että se on omiaan tekee mitä kerrot sen tehdä, ja sinun
on tehtävä se tässä järjestyksessä.
Joten jos osuin Anna tähän, aion saada varoituksen sigma implisiittinen
ilmoitus.
>> Voi, ei ole ongelma.
En voi mennä ylös, ja voin sanoa, okei, odota hetki.
Sigma on funktio, joka palauttaa int ja se odottaa
int syötteenä, puolipiste.
Tai voisin laittaa koko toiminto Edellä tärkein, mutta yleensä olin
Suosittelen vastaan, että koska se on kiva aina tärkein yläreunassa niin
voit sukeltaa suoraan ja tietää, mitä Ohjelma tekee lukemalla tärkein ensin.
>> Joten nyt haluan tyhjentää näytön.
Remake sigma 0.
Kaikki näyttää tarkistaa.
Saanen ajaa sigma 0.
Positiivinen muun.
Annan sen numeron 3. pitää se yksinkertainen.
Niin, että pitäisi antaa minulle 3 plus 2 plus 1, niin 6.
Anna, ja olen todellakin saat 6.
>> Voin tehdä jotain suurempaa -
50, 12, 75.
Aivan kuten tangentti, aion tehdä jotain naurettavaa kuin todella iso
numero, Oh, joka todella toiminut -
eh, en usko, että on oikeassa.
Katsotaanpa.
Katsotaanpa todella sotkea sitä.
>> Se on ongelma.
Mitä on tekeillä?
Koodia ei ole niin paha.
Se on edelleen lineaarinen.
Vihellys hyvä vaikutus, vaikka.
Mitä on tekeillä?
>> Ole varma, jos olen kuullut sen.
Joten se kääntyy pois - ja tämä on niin syrjään.
Tämä ei ole ydin Ajatus rekursio.
On käynyt ilmi, koska yritän edustavat niin iso numero, useimmat
todennäköisesti se tulkitaan väärin by C ole positiivinen luku,
mutta negatiivinen luku.
>> Emme ole puhuneet tästä, mutta se Osoittautuu olemassa negatiivisia lukuja
maailman lisäksi positiiviseen numeroita.
Ja keinoja, joilla voit edustavat negatiivinen luku
pohjimmiltaan on, käytät yhden erityisen vähän osoittamaan
ylijäämäisenä negatiivinen.
Se on hieman monimutkaisempi kuin, että mutta se perusajatus.
>> Joten valitettavasti jos C on hämmentävä yksi näistä bittejä todella tarkoittaa,
Voi, tämä on negatiivinen luku, minun loop tässä, esimerkiksi, on itse asiassa koskaan
menossa lopettaa.
Joten jos olisin itse tulostaa jotain uudelleen ja uudelleen, olisimme
nähdä paljon.
Mutta jälleen kerran, tämä on lisäksi kohta.
Tämä on oikeastaan ​​vain eräänlainen älyllinen uteliaisuus, että tulemme
takaisin lopulta.
Mutta nyt, tämä on oikea täytäntöönpanon jos oletamme, että
Käyttäjä antaa ints että mahtuvat ints.
>> Mutta väitän, että tätä koodia, rehellisesti, voitaisiin tehdä paljon yksinkertaisemmin.
Jos tavoitteena käsillä on ottaa useita kuten m ja lisätä jopa kaikki
numeroita sen ja 1 tai päinvastoin välillä 1 ja se, Väitän
että voin lainata tätä ajatusta, jotka sulautuvat lajitella oli, joka otti ongelman
Tämän koko ja jakamalla se osaksi jotain pienempää.
Ehkä ei puoli, mutta pienempiä, mutta edustavasti sama.
Sama idea, mutta pienempi ongelma.
>> Joten olen todella - haluan tallentaa tiedoston kanssa eri versionumero.
Soitamme tämän version 1 sijasta 0.
Ja väitän, että voin itse reimplement tämä tämäntyyppisiin
aistiharhoja tavalla.
>> Aion jättää osa sitä yksin.
Aion sanoa, jos m on vähemmän kuin tai jopa yhtä suuri kuin 0 -
Olen vain olemaan hieman enemmän anaali tällä kertaa
minun virheentarkistukset -
Aion mennä eteenpäin ja palata 0.
Tämä on mielivaltainen.
Olen vain yksinkertaisesti päättää, jos käyttäjä antaa minulle negatiivinen luku, olen
palaavat 0, ja ne olisi pitänyt lukea asiakirjat tarkemmin.
>> Else -
huomaa, mitä aion tehdä.
Else Aion palata m plus -
mikä on sigma m?
No, sigma m plus m miinus 1, plus m miinus 2, plus m miinus 3.
En halua kirjoittaa kaiken tuon pois.
Miksi en vain potkaista?
Rekursiivisesti kutsua itseäni hieman pienempi ongelma, puolipiste,
ja lopettaa tältä päivältä?
>> Oikea?
Nyt täälläkin, saatat tuntea tai huolehtia että tämä on loputon silmukka, että olen
asiakkuutta, jolloin olen täytäntöönpanosta sigma soittamalla sigma.
Mutta se on täysin OK, koska olen ajattelin eteenpäin lisätty mitkä linjat?
>> Yleisö: [kuultavissa].
>> DAVID MALAN: 23-26, jotka on minun, jos kunnossa.
Koska mitä mukavaa noin vähennyslaskua täällä, koska pidän
luovuttamalla sigma pienempiä ongelmia, pienempiä ongelmia, pienempi - se ei ole
puolet pienempi.
Se on vain vauva pykälää pienempi, mutta se on OK.
Koska lopulta, hoidamme Matkalla alas 1 tai 0.
Ja kun osuimme 0, sigma ei ole aikoo kutsua itseään enää.
Se tulee välittömästi palata 0.
>> Joten vaikutus, jos sellainen tuulen tämän up mielessäsi, on lisätä m +
m miinus 1, plus m miinus 2, plus m miinus 3, plus piste, piste, piste, m miinus
m, lopulta antaa sinulle 0, ja vaikutus on viime kädessä lisätä kaikkien
nämä asiat yhdessä.
Joten meillä ei ole, ja rekursio, ratkaista ongelma, että me
ei ratkaista ennen.
Todellakin, versio 0 tämän ja jokainen Ongelmana on tähän asti ollut ratkaistavissa
vain käyttämällä silmukoita tai kun silmukoita tai vastaavia rakenteita.
>> Mutta rekursio, Luulen, antaa meille erilainen tapa ajatella
ongelmia, jolloin jos voimme ottaa ongelma, jakaa sitä jotain
suurehko jotain hieman pienempi, Väitän, että voimme ratkaista sen
ehkä hieman tyylikkäästi kannalta suunnittelu, vähemmän koodia,
ja ehkä jopa ratkaisemaan ongelmia, jotka olla vaikeampaa, kuten tulemme lopulta
katso, ratkaista puhtaasti iteratiivisesti.
>> Mutta jännitysnäytelmä, että tein halua lähteä meitä oli tämä.
Anna minun mennä eteenpäin ja avata up tiedosto -
todella, anna minun mennä ja tehdä tämän todella nopeasti.
Anna minun mennä eteenpäin ja ehdottaa seuraavat.
Tämän päivän koodi on tämä tiedosto tästä.
Tämä yksi täällä, noswap.
>> Joten tämä on typerä pieni ohjelma, joka Olen lyöty jopa joka väittää tehdä
seuraavat.
Main, se ilmoittaa ensin int kutsutaan x ja määrittää sen
arvon 1.
Sitten se ilmoittaa, int y ja määrittää sen arvo 2.
Sitten se tulostaa mitä x ja y on.
Sitten se sanoo, vaihtamalla, dot dot dot.
>> Sitten se väittää vaatii toimia nimeltään swap, ohimennen x ja
y, ajatus on, että toivottavasti x ja y tulevat takaisin
eri, päinvastoin.
Sitten se väittää vaihdettu!
huutomerkki.
Sitten se tulostaa x ja y.
>> Mutta näyttää siltä, ​​että tämä hyvin yksinkertainen esittelyä alas
täällä on todella buginen.
Vaikka olen julistamisesta väliaikainen muuttuja ja tilapäisesti käyttöön vuonna
sitä, niin olen vaihtaminen mille b: n arvo -
joka tuntuu kohtuullinen, koska olen tallennettu kopio temp.
Sitten voin päivittää b yhdenvertaiseen mikä oli temp.
Tällainen kuori peli liikkuvat osaksi b ja b osaksi käyttämällä tätä
keski-mies nimeltä temp tuntuu täysin järkevää.
>> Mutta väitän, että kun juoksen tämän koodi, kuten minä teen nyt -
anna minun mennä eteenpäin ja liitä se täällä.
Soitan tämän noswap.c.
Ja kuten nimestä voi päätellä, tämä ei ole olemaan oikea ohjelma.
Tee noswap. / Ei swap.
x 1, y on 2, vaihtamalla, vaihdoin.
x on 1, y on 2.
Tämä on täysin väärä, vaikka vaikka tämä vaikuttaa täysin
järkevää minulle.
Ja siellä on syy, mutta emme ole aikoo paljastaa syy vielä.
>> Nyt toinen jännitysnäytelmä halusin jätä sinua on tämä,
ilmoitus tapaisena kuponkikoodeista.
Innovaatioiden myöhään päivää tänä vuonna on herättänyt ei-triviaali määrä
kysymyksiä, jotka oli Tarkoituksemme ei ole.
Tarkoituksena näistä kuponkikoodeista, jolloin jos teet osa ongelmaa
asettaa aikaisin, mikä saada ylimääräinen päivä, oli todella auttaa teitä auttaa
itse aloittaa aikaisin, sort ja palkitsemalla sinua.
Auttaa meitä jakamaan kuormaa poikki virka paremmin niin, että
se on eräänlainen win-win.
>> Valitettavasti luulen ohjeet ei ole ollut tähän mennessä hyvin kirkas, niin
Menin takaisin tänä viikonloppuna ja päivitetään spec suurempi, rohkeampi teksti
selittää luoteja kuin nämä.
Ja vain sanoa sen avoimempi, jonka Oletuksena ongelma sarjaa johtuvat torstai
keskipäivällä, per oppimäärän.
Jos aloitat varhain, viimeistely osa ongelma asettamat keskiviikkona klo 12:00
PM, osa, joka liittyy kuponki koodi, ajatus on, että voit laajentaa
teidän määräaika P asettaa vasta perjantaina.
Eli hieman pois pieni osa P asettaa siihen, mitä on tyypillisesti
suurempi ongelma, ja ostat itse ylimääräinen päivä.
Jälleen, se saa sinut ajattelemaan Harjoitus, saa sinut
virka nopeammin.
Mutta kuponkikoodi ongelma on edelleen tarvitaan, vaikka et lähetä se.
>> Mutta enemmän pakottavan on tämä.
(Stage Whisper) Ja ne ihmiset lähtevät alussa tulet katumaan sitä.
Koska ovat seudullamme parvekkeella.
Pahoittelen jo etukäteen seudullamme parveke syistä, jotka on
tyhjentää vain hetken.
>> Joten olemme onnekkaita olla yksi CS50: n entinen johtaja opetus Fellows
yritys nimeltä dropbox.com.
He ovat hyvin anteliaasti lahjoitti kuponkikoodi täällä näin paljon tilaa,
joka on ylös tavallisesti 2 gigatavua.
Joten mitä ajattelin tekisimme tästä Viimeinen huomautus on tehdä vähän kylkiäinen,
jolloin vain hetki, me paljastaa voittaja ja joka on kuponki
koodia, jota voi sitten mennä heidän verkkosivuilla, kirjoita se, ja voila, saada
paljon enemmän Dropbox tilaa laite ja henkilökohtaiset tiedostot.
>> Ja ensimmäinen, joka haluaa osallistua tässä piirustuksessa?
OK, nyt joka tekee siitä entistä hauskempaa.
Henkilö, joka saa tämän 25 gigatavun kuponkikoodi - joka on kaukana
enemmän pakottavia kuin myöhään päivän ajan, kenties -
on se, joka istuu päälle istuinosan alla, joka on
että kuponkikoodi.
Voit nyt katsoa alla oman istuintyynyn.
>> [VIDEOTOISTOSTA]
>> -Yksi, kaksi, kolme.
>> [SCREAMING]
>> -Saat auton!
Saat auton!
>> DAVID MALAN: Tulemme näkemään keskiviikkona.
>> -Saat auton!
Saat auton!
>> DAVID MALAN: Parveke ihmiset, tulevat tänne eteen,
jossa meillä on extrat.
>> -Jokainen saa auton!
Jokainen saa auton!
>> [END VIDEOTOISTOSTA]
>> Kertoja: Seuraavassa CS50 -
>> SPEAKER 5: Jestas Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh Gosh -
>> [Ukelele PLAYS]