[Powered by Google Translate] [3 jakso - Lisää Mukava]
[Rob Bowden - Harvardin yliopisto]
>> [Tämä on CS50. - CS50.TV]
>> Joten ensimmäinen kysymys on oudosti muotoiltu.
GDB voit "debug"-ohjelma, mutta täsmällisemmin, mitä se antaa sinun tehdä?
Minä vastaan, että yksi, ja en tiedä mitä tarkalleen odottaa,
joten olen vierasta se on jotain tapaan sen avulla voit askel askeleelta
kävellä ohjelman vuorovaikutuksessa sen kanssa, eri muuttujien, tehdä kaikki nämä asiat -
pohjimmiltaan täysin hallita ohjelman suorituksen
ja tarkasta tahansa osaa ohjelman täytäntöönpanon.
Joten nämä ominaisuudet voit debug asioita.
Okei.
Miksi binäärihakupuu edellyttävät array lajitella?
Kuka haluaa vastata tähän?
[Opiskelija] Koska se ei toimi, jos se ei ole lajiteltu. >> Joo. [Naurua]
Jos se ei ole lajiteltu, niin se on mahdotonta jakaa sen kahtia
ja tiedämme, että kaiken vasemmalla on vähemmän ja kaikki oikealle
on suurempi kuin keskimmäinen arvo.
Joten se on ratkaistava.
Okei.
Miksi kupla lajitella O n neliö?
Onko kukaan haluaa ensin antaa hyvin nopeasti korkean tason yleiskuvan siitä, mitä kuplan sort on?
[Opiskelija] Olet periaatteessa käydä läpi jokaisen elementin ja voit tarkistaa muutaman ensimmäisen elementtejä.
Jos he ovat poissa missä vaihtaa niitä, niin tarkista tulevina elementit ja niin edelleen.
Kun tulet loppuun, niin tiedät, että suurin osa on sijoitettu lopussa
niin ohitat että yksi sinun pitää käydä läpi,
ja joka kerta täytyy tarkistaa yksi vähemmän elementti kunnes teet mitään muutoksia. >> Joo.
Sitä kutsutaan kupla lajitella koska jos kääntää array kyljelleen niin se on ylös ja alas, pystysuora,
Sitten suuret arvot vajoavat pohjaan ja pienet arvot tulee kupla ylös.
Niin se on saanut nimensä.
Ja joo, juuri läpi.
Pidät läpi array, vaihtamalla suuremman arvon
saada suurimmat arvot pohjaan.
>> Miksi se O n neliö?
Ensinnäkin, ei kukaan halua sanoa miksi se on O n neliö?
[Opiskelija] Koska jokaisen ajon se menee n kertaa.
Voit olla varma, että olet ottanut suurimman elementin kokonaan alas,
sinun on toistettava, että niin monta elementtiä. >> Joo.
Joten pitää mielessä, mitä Big O tarkoittaa ja mitä iso Omega keinoin.
Big O on kuin yläraja kuinka hidas se voi todella ajaa.
Joten sanomalla, että se on O n potenssiin, se ei ole O n tai muuten se voisi ajaa
lineaarisessa ajassa, mutta se on O n kuutioitu
koska se rajoittuu O n kuutioitu.
Jos se rajoittuu O n neliö, niin se rajoittuu myös N kuutioitu.
Joten se on n potenssiin, ja ehdoton pahimmassa tapauksessa se ei voi tehdä paremmin kuin n potenssiin,
minkä vuoksi se on O n: n neliö.
Joten nähdä hieman matematiikkaa, miten se tulee ulos n potenssiin,
jos meillä on viisi asiaa listalta, ensimmäistä kertaa kuinka monta swap voisimme mahdollisesti täytyy tehdä
Jotta saat tämän? Katsotaanpa oikeastaan ​​vain -
Kuinka monta swap aiomme täytyy tehdä ensimmäisen ajaa kupla lajitella array?
[Opiskelija] n - 1. >> Joo.
>> Jos on 5 elementtejä, olemme menossa tarvitse tehdä n - 1.
Sitten toinen kuinka monta swap aiomme pitää tehdä?
[Opiskelija] n - 2. >> Joo.
Ja kolmas tulee olemaan n - 3, ja sitten mukavuussyistä aion kirjoittaa kaksi viimeistä
koska silloin olemme menossa tarvitse tehdä 2 swapit ja 1 swap.
Oletan viimeinen tai ei oikeastaan ​​tarvitse tapahtua.
Onko se swap? En tiedä.
Nämä ovat siis kokonaismäärät swap tai ainakin vertailuja sinun täytyy tehdä.
Vaikka et vaihtaa, tarvitset silti verrata arvoja.
Joten on n - 1 vertailut ensimmäisen ajon kautta array.
Jos järjestellä näitä asioita, mennään todella tehdä kuusi asiaa niin asiat pärjää hienosti,
ja sitten minä teen 3, 2, 1.
Joten järjestämässä näitä summia, haluamme nähdä kuinka monta vertailuja teemme
koko algoritmi.
Joten jos saamme nämä kaverit täällä,
Sitten me vielä vain yhteenlaskua kuitenkin monia vertailuja siellä oli.
Mutta jos me kerätä ne ja me kerätä ne ja me kerätä ne,
se on edelleen sama ongelma. Me vain todeta kyseisiä ryhmiä.
>> Joten nyt olemme yhteenlaskua 3 N: n. Se ei ole vain 3 N: n.
Se on aina olemaan n / 2 n-luvulla.
Joten tässä meillä sattuu olemaan 6.
Jos meillä oli 10 asiaa, niin voisimme tehdä tämän ryhmittymän 5 eri paria asioita
ja lopulta n + n + n + n + n.
Joten olet aina menossa n / 2 n: n, joten tämä me hiukkaakaan ulos n neliö / 2.
Ja niin vaikka se tekijä puoli, joka sattuu tulla
koska se seikka, että läpi jokaisen iteraation aikana array me vertaamme 1 vähemmän
Niin, että miten saamme yli 2, mutta se on silti n: n potenssiin.
Emme välitä vakio tekijä puoli.
Joten paljon Big O tavaraa kuten tämä perustuu vain sellaista tekemässä tällaista matematiikkaa,
laskutoimitusten summia ja geometrisen sarjan juttuja,
mutta useimmat niistä tällä kurssilla ovat melko yksinkertaisia.
Okei.
Miksi lisäys lajitella Omega n? Mitä omega tarkoittaa?
[Kaksi opiskelijaa puhuu kerralla - käsittämätön] >> Joo.
Omega voit ajatella kuin alaraja.
>> Joten ei ole väliä kuinka tehokas lisäyskohdan lajitella algoritmi on,
riippumatta luettelon, joka on hyväksytty vuonna, se on aina verrata ainakin n asioita
tai se on toistaa yli n. asioita.
Miksi näin?
[Opiskelija] Koska jos luettelo on jo järjestetty, sitten läpi ensimmäistä iterointia
voit vain taata, että ensimmäinen osa on vähiten,
ja toisen iteroinnin voit vain varmistaa kaksi ensimmäistä ovat
koska et tiedä, että loput lajitellaan. >> Joo.
Jos ohitat täysin järjestetty luettelo, ainakin sinun täytyy mennä yli kaikki elementit
nähdä, että mitään ei tarvitse liikutella.
Joten kulkevan listan ja sanoi oi, tämä on jo lajiteltu,
on mahdotonta tietää, se lajitellaan kunnes tarkistaa kunkin elementin
nähdä, että ne ovat lajiteltu järjestyksessä.
Joten alaraja sijoittamista tavallaan on Omega n.
Mitä pahimmassa tapauksessa käyntiaika merge lajitella,
Pahimmassa tapauksessa on iso O uudelleen?
Joten pahimmassa tapauksessa miten merge sort ajaa?
[Opiskelija] N log n. >> Joo.
Nopein yleinen lajittelualgoritmeja ovat n log n. Et voi tehdä paremmin.
>> On olemassa erityisiä tapauksia, ja jos meillä on aikaa tänään - mutta luultavasti won't -
näimme, joka tekee paremmin kuin n log n.
Mutta yleisessä tapauksessa, et voi tehdä paremmin kuin n log n.
Ja yhdistää tavallaan sattuu olemaan yksi sinun pitäisi tietää tämä tietenkin, että on n log n.
Ja niin me oikeastaan ​​täytäntöönpanossa että tänään.
Ja lopuksi, on enintään kolme virkettä, miten valinta tavallaan työtä?
Onko joku haluaa vastata, ja minä laske teidän lauseita
sillä jos menemme yli 3 -
Muistaako kukaan valinta lajitella?
Valinta sort on yleensä melko helppo muistaa vain nimestä.
Sinä vain toistaa yli array, löytää mitä suurin arvo on tai pienin -
missä järjestyksessä olet lajittelu sisään
Joten sanokaamme me lajittelun pienimmästä eniten.
Voit toistaa yli array, etsivät riippumatta minimi elementti on,
valitse se, ja sitten vain vaihtaa se mitä on ensimmäinen paikka.
Ja sitten toisen kulkevat array, etsiä pienin alkio uudelleen,
valitse se, ja sitten vaihtaa se mitä toisessa asennossa.
Joten me vain poiminta ja valitsemalla vähimmäisarvot
ja työntämällä ne etuosaan array, kunnes se on järjestetty.
Kysymyksiä tästä?
>> Nämä väistämättä näkyvät lomakkeet täytyy täyttää, kun olet esittää PSET.
Nämä ovat pohjimmiltaan vastauksia näihin.
Okei, joten nyt koodaus ongelmia.
Olen jo lähettänyt sähköpostissa - Näkikö kukaan saa sitä sähköpostilla? Okei.
Olen jo lähetetty sähköpostissa tilaa, että aiomme käyttää,
ja jos klikkaat nimeni - niin mielestäni aion olla pohjassa
koska taaksepäin R - mutta jos klikkaa nimeni näet 2 revisions.
Versio 1 aiotaan Olen jo kopioida ja liittää koodi Spaces
Haun asia aiot tarvitse toteuttaa.
Ja Versio 2 on tavallaan asia, että toteutamme sen jälkeen.
Joten voit napsauttaa minun Versio 1 ja työskennellä siellä.
Ja nyt me haluamme toteuttaa binäärihakupuu.
>> Haluaako joku vain antaa pseudokoodi korkean tason selitys
mitä aiomme pitää tehdä haun? Joo.
[Opiskelija] Sinä vain ottaa keskelle array ja katso jos mitä etsit
on pienempi kuin tai enemmän.
Ja jos se on vähemmän, menet puoli, joka on vähemmän,
ja jos se on enemmän, voit mennä puoli, joka on enemmän ja Voisitko toistaa kunnes vain yksi asia.
[Bowden] Joo.
Huomaa, että numerot taulukko on jo lajiteltu,
ja niin se tarkoittaa, että voimme hyödyntää tätä ja voisimme tarkista ensin,
Okei, etsin numero 50.
Joten voin mennä keskelle.
Keskellä on vaikea määritellä, kun se on vielä monia asioita,
mutta sanotaanko me aina katkaista sen keskelle.
Joten tässä meillä on 8 asioita, joten keskimmäinen olisi 16.
Etsin 50, joten 50 on suurempi kuin 16.
Joten nyt voin periaatteessa hoitaa minun array kuin nämä tekijät.
Voin heittää pois kaiken 16 yli.
Nyt minun array on vain nämä 4 elementtiä, ja toistan.
Joten haluan löytää keskeltä uudestaan, mikä tulee olemaan 42.
42 on alle 50, joten voin heittää pois nämä kaksi elementtiä.
Tämä on minun jäljellä array.
Aion löytää keskeltä uudestaan.
Luulen 50 oli huono esimerkki, koska olin aina heittää pois asioita vasemmalle,
mutta samalla mitalla, jos etsin jotain
ja se on pienempi kuin elementin Olen tällä hetkellä katsot,
Sitten aion heittää pois kaiken oikealle.
Joten nyt meidän täytyy toteuttaa se.
Huomaa, että meidän kulkea koko.
Voimme myös ei tarvitse koodata koko.
Joten jos pääsemme eroon että # define -
Okei.
Miten kauniisti selvittää, mitä numeroiden koko array hetkellä on?
>> Kuinka monta elementtiä ovat numeroita array?
[Opiskelija] Numbers, suluissa. Pituus?
[Bowden] Tämä ei esiinny C.
Tarvitsevat. Pituus.
Arrays ei ole ominaisuuksia, joten ei ole mitään pituus omaisuutta pakat
joka vain antaa sinulle kuitenkin kauan se sattuu olemaan.
[Opiskelija] Katso kuinka paljon muistia se on ja jakaa kuinka paljon - >> Joo.
Joten kuinka voimme nähdä kuinka paljon muistia se on? >> [Opiskelija] sizeof. >> Joo, sizeof.
Sizeof on operaattori, joka tulee palauttaa numeroiden koko jono.
Ja se tulee olemaan kuitenkin monta kokonaislukua on aikoja koko kokonaisluku
sillä se, kuinka paljon muistia se todella aloittamisesta.
Joten jos haluan monia asioita array,
Sitten aion haluat jakaa koolla kokonaisluku.
Okei. Niin että antaa minulle kulkea koko täällä.
Miksi minun täytyy kulkea koko ollenkaan?
Miksi en voi vain tehdä tänne int koko = sizeof (heinäsuovasta) / sizeof (int)?
Miksi tämä ei toimi?
[Opiskelija] Se ei ole globaali muuttuja.
[Bowden] heinäsuovasta olemassa, ja olemme ohimennen numerot heinäsuovasta,
ja tämä on eräänlainen esikuva mitä on tulossa. Joo.
[Opiskelija] heinäsuovasta on vain viittaus siihen, niin se palaisi kuinka suuri tämä viittaus on.
Joo.
Epäilen luennossa, että olet nähnyt pino vielä todella, eikö?
Olemme juuri puhuneet siitä.
Joten pino on, jos kaikki muuttujat aiotaan varastoida.
>> Jokainen muisti, joka on varattu paikallisia muuttujia on menossa pinoon
ja jokaisen toiminnon saa oman tilan pino, oma pino runko on mitä se on nimeltään.
Niin tärkein on sen pinokehys, ja sen sisällä on menossa olemassa tämän numerot array,
ja se tulee olemaan koon sizeof (numerot).
Se tulee olemaan kooltaan numeroiden jaettuna kokoa elementtejä,
mutta kaikki elämänsä sisällä tärkeimmät n pinokehys.
Kun me kutsumme haussa, saa oman pinokehys,
omaa tilaa tallentaa kaikki paikalliset muuttujat.
Mutta nämä väitteet - joten heinäsuovasta ei kopio tästä koko ryhmän.
Emme luovuta koko levyjärjestelmän kopioida haku.
Se vain kulkee viittaus kyseiseen array.
Joten haku voi käyttää näitä numeroita läpi tämä viittaus.
Se käyttää yhä asioita, jotka elävät sisällä tärkeimpien n pinokehys,
mutta pohjimmiltaan, kun saamme osoittimia, joiden pitäisi olla pian,
tämä on mitä osoittimet ovat.
Osoittimet ovat vain viittauksia asioita, ja voit käyttää osoittimia pääsyn asioita
jotka ovat muiden muassa "pino kehyksiä.
Joten vaikka numerot on paikallinen tärkein, voimme silti käyttää sitä kautta osoitin.
Mutta koska se on vain osoitin ja se on vain viite,
sizeof (heinäsuovasta) palaa aivan koko viite itse.
Se ei palauta koko asia se osoittaa.
Se ei palauta todellinen koko numeroita.
Ja niin tämä ei tule toimimaan haluamme sen.
>> Kysymyksiä tästä?
Osoittimet on mennyt huomattavasti enemmän kammottava yksityiskohtia tulevien viikkojen aikana.
Ja siksi paljon asioita, jotka näet, kaikkein haku asioita tai lajitella asioita,
he lähes kaikki menossa tarvitse tehdä todellinen taulukon koko,
koska C, meillä ei ole aavistustakaan, mitä taulukon koko on.
Sinun täytyy manuaalisesti siirtää sen sisään
Ja et voi manuaalisesti siirtää koko joukko, koska olet vain ohimennen viite
ja se ei voi saada koko vertailutasosta.
Okei.
Joten nyt me haluamme toteuttaa mitä selitettiin ennen.
Voit työskennellä sen hetken,
ja sinun ei tarvitse pelätä kaiken täydellisesti 100% työskentely.
Vain kirjoittaa ylös puoli pseudokoodi miten luulet sen pitäisi toimia.
Okei.
Ei tarvitse olla täysin tehdä tätä vielä.
Mutta ei kukaan Viihdyn mitä he ovat tähän asti,
jotain voimme työskennellä yhdessä?
Haluaako joku tehdä vapaaehtoistyötä? Tai en valitse sattumanvaraisesti.
Sen ei tarvitse olla oikeus kaikilla mittareilla, mutta emme voi muuttaa osaksi toimivaan tilaan.
[Opiskelija] Toki. >> Okei.
Joten voit säästää tarkistuksen klikkaamalla pikku Tallenna-kuvaketta.
Olet Ramya, eikö? >> [Opiskelija] Joo. >> [Bowden] Okei.
Joten nyt voin nähdä tarkistamista ja jokainen voi vetää tarkistamista.
Ja täällä meillä on - Okei.
Niin Ramya meni rekursiivinen ratkaisu, joka on ehdottomasti pätevä ratkaisu.
On kaksi tapaa voit tehdä tämän ongelman.
Voit joko tehdä sen toistuvasti tai rekursiivisesti.
Useimmat ongelmat kohtaat voidaan tehdä rekursiivisesti voi tehdä myös iteratiivisesti.
Joten tässä olemme tehneet sen rekursiivisesti.
>> Onko joku haluaa määritellä, mitä se tarkoittaa tehdä toiminnon rekursiivinen?
[Opiskelija] Kun olet funktion kutsua itseään
ja sitten soittaa itse kunnes se tulee ulos tosi ja totta. >> Joo.
Rekursiivinen funktio on vain funktio, joka kutsuu itseään.
On kolme suurta asiaa, että rekursiivinen funktio on.
Ensimmäinen on tietysti se kutsuu itseään.
Toinen on perustapaus.
Niin jossain vaiheessa funktion täytyy pysäyttää kutsuu itseään,
ja sitähän perustapaus on.
Joten tässä me tiedämme, että meidän pitäisi lopettaa, meidän pitäisi luopua meidän haku
kun alku vastaa loppua - ja me mennä yli, mitä se tarkoittaa.
Mutta lopulta, viimeinen asia, joka on tärkeä rekursiiviset funktiot:
toimintoja on jotenkin lähestyä perustapaus.
Kuten jos et itse päivittää mitään, kun teet toisen rekursiivinen puhelun,
jos olet kirjaimellisesti vain kutsumalla funktiota uudelleen samat argumentit
eikä globaalien muuttujien ovat muuttuneet tai mitään,
et koskaan pääse perustapaus, jolloin se on paha.
Se tulee olemaan loputtoman rekursion ja pinon ylivuoto.
Mutta tässä näemme, että päivitys tapahtuu, koska me Päivitämme aloittaa + loppuun / 2,
olemme päivittää loppua argumentti täällä, me päivittäminen alusta argumentti täällä.
Joten kaikki rekursiivinen puhelut Päivitämme jotain. Okei.
Haluatko kävellä meille läpi ratkaisu? >> Toki.
Käytän SearchHelp niin että aina kun teen tätä toimintoa puhelun
Olen alusta missä Etsin pakassa ja loppu
, missä Etsin array.
>> Jokaisessa vaiheessa, jossa se sanoo se keskimmäinen elementti, joka on alku + loppu / 2,
että sama mitä etsimme?
Ja jos on, niin löysimme sen, ja luulen, että saa siirtää ylös tasoa rekursion.
Ja jos se ei ole totta, niin voimme tarkistaa onko keskimmäinen arvo joukko on liian suuri,
jolloin katsomme vasen puoli array menemällä alusta keskeltä indeksi.
Ja muuten teemme loppu puoli.
[Bowden] Okei.
Kuulostaa hyvältä.
Okei, joten pari asiaa, ja itse asiassa, tämä on erittäin korkean tason juttu
että sinun ei tarvitse koskaan tietää tämän kurssin, mutta se on totta.
Rekursiivinen toimintoja, aina kuulla, että he ovat huono sopimus
koska jos rekursiivisesti kutsua itseäsi liian monta kertaa, saat pinon ylivuoto
sillä, kuten aiemmin sanoin, jokainen toiminto saa oman pinokehys.
Joten jokainen kutsu rekursiivinen funktio saa oman pinokehys.
Joten jos teet 1000 rekursiivinen puheluja, saat 1000 pino kehyksiä,
ja nopeasti te johtaa liian monta pino kehyksiä ja asiat vain rikkoa.
Joten siksi rekursiiviset toiminnot ovat yleensä huonoja.
Mutta on mukava osajoukko rekursiiviset funktiot kutsutaan hännän rekursiiviset toimintoja,
ja tämä sattuu olemaan esimerkiksi sellainen, jossa jos kääntäjä huomaa tämän
ja se pitäisi mielestäni - in clang jos ohitat sen, O2 lippu
se huomaa tämä on häntä rekursiivinen ja tehdä asioita hyvin.
>> Se käyttää samaa pinokehys yhä uudelleen ja uudelleen kullekin rekursiivista puhelun.
Ja niin, koska käytät samaa pinokehys, sinun ei tarvitse pelätä
koskaan pino täynnä, ja samaan aikaan, kuten sanoit aiemmin,
Jos kerran palaat totta, se on palautettava kaikkia näitä pinon kehyksiä
ja 10. kutsun SearchHelp on palata 9th, on palata 8..
Niin että ei tarvitse tapahtua, kun toimintoja häntä rekursiivisia.
Ja niin mitä tekee tämä toiminto häntä rekursiivinen on ilmoitus, että minkä tahansa puhelun searchHelp
rekursiivinen puhelu, että se tekee mitä se palaa.
Niinpä ensimmäisen puhelun SearchHelp, me joko välittömästi palauttaa false,
välittömästi palauttaa true tai teemme rekursiivinen kutsu SearchHelp
missä me olemme palaamassa mitä se puhelu on palaamassa.
Ja me ei tehdä tätä, jos teimme jotain int x = SearchHelp, paluu x * 2,
vain joitakin satunnaisia ​​muutoksia.
>> Joten nyt tämä rekursiivinen puhelun, tämä int x = SearchHelp rekursiivinen puhelun
ei enää häntää rekursiivinen, koska se todella ei tarvitse palata
takaisin edelliseen pinokehys niin että edellinen puhelu toiminto
voi sitten tehdä jotain tuottoarvo.
Joten tämä ei ole häntää rekursiivinen, mutta mitä meillä oli ennen on mukavasti häntä rekursiivinen. Joo.
[Opiskelija] Pitäisikö toisen tukiaseman tapauksessa tarkistetaan ensin
sillä voisi olla tilanne, jossa kun ohitat sen väitteen
olet start = lopussa, mutta ne ovat neulan arvoa.
Kysymystä emme voi törmätä jos pää on neula arvo
tai start = loppu, asianmukaisesti, aloita = loppu
ja et ole itse tarkistanut kyseisen arvon vielä,
sitten aloittaa + pää / 2 on vain olemaan sama arvo.
Mutta olemme jo palannut vääriä emmekä koskaan tarkastetaan arvoa.
Joten ainakin, että ensimmäinen puhelu, jos koko on 0, niin haluamme palauttaa false.
Mutta jos koko on 1, niin käynnistys ei tule yhtä loppuun,
ja me ainakin tarkistaa yksi elementti.
Mutta mielestäni olet oikeassa, että voimme päätyä tapauksessa aloittaa + loppuun / 2,
käynnistys päätyy on sama kuin alku + lopussa / 2,
mutta emme koskaan tarkistanut, että elementti.
>> Joten jos ensin tarkistettava keskimmäinen elementti arvo etsimme,
voimme heti palata totta.
If he yhtä, niin ei ole mitään järkeä jatkaa
koska olemme juuri menossa päivittää tapauksessa olemme yhden elementin array.
Jos tämä yksittäinen tekijä ei ole yksi etsimme,
Sitten kaikki on väärin. Joo.
[Opiskelija] Olennaista on, että koska koko on itse asiassa suurempi kuin elementtien määrä array,
on jo offset - >> Niin käy koko -
[Opiskelija] Sano, jos matriisi oli koko 0, niin SearchHelp todella tarkistaa haystack 0
ensimmäisen puhelun.
Array koko on 0, joten 0 on - >> Joo.
On toinen asia, että - se voisi olla hyvä. Ajatellaanpa.
Joten jos ryhmä oli 10-elementtejä ja keskimmäinen aiomme tarkistaa indeksinumero 5,
joten olemme tarkkailun 5, ja sanotaan, että arvo on pienempi.
Joten me heittää kaiken pois 5 eteenpäin.
Niin alkaa + pää / 2 tulee olemaan uusi loppu,
niin joo, se on aina menossa pysyä päättymisen jälkeen jono.
Jos se on, jos se on parillinen tai pariton, niin voisimme tarkistaa, sanoa, 4,
mutta olemme silti heittää pois -
Niin joo, pää on aina olemaan pidemmälle todellisen loppuun array.
Eli elementit keskitymme, pää on aina olemaan yksi jälkeen.
Ja niin jos alusta ei koskaan yhtä loppuun, olemme joukko koko 0.
>> Toinen asia Ajattelin on Päivitämme voidaan aloittaa aloittaa + loppuun / 2,
joten tämä on asia, joka minulla on ongelmia, jos aloittaa + pää / 2
on elementti olemme tarkkailun.
Sanotaan meillä oli 10-elementti array. Whatever.
Niin alkaa + pää / 2 tulee olemaan jotain tällaista yksi,
ja jos se ei ole arvoa, sanovat haluamme päivittää.
Arvo on suurempi, joten haluamme tarkastella tätä puolta array.
Joten miten olet päivittämässä alku, me päivittäminen alkaa nyt olla tätä elementtiä.
Mutta tämä voi silti toimia, tai ainakin voit tehdä alku + loppu / 2 + 1.
[Opiskelija] Sinun ei tarvitse aloittaa + pää [kuulumattomissa] >> Joo.
Olemme jo tarkistanut tämän elementin ja tietää se ei ole yksi etsimme.
Joten meidän ei tarvitse päivittää alkaa olla tätä elementtiä.
Voimme vain ohittaa sen ja päivittää alkavat olla tätä elementtiä.
Ja onko koskaan tapaus, sanotaanko, että tämä oli varten
niin käynnistä olisi tämän käynnistämällä + pää / 2 olisi tässä,
alkaa + loppu - Joo, mielestäni se voi päätyä loputtoman rekursion.
Sanotaan se on vain joukko kokoa 2 tai joukko koko 1. Mielestäni tämä toimii.
Joten nyt, alku on se elementti, ja loppu on 1 sen ulkopuolella.
Joten elementti, että me aiomme tarkistaa tämä yksi,
ja sitten kun me päivittää alusta, olemme päivittäminen alkaa olla 0 + 1/2,
joka tulee päättymään meidät takaisin alkaa olla tätä elementtiä.
>> Joten me tarkistaa saman elementin uudestaan ​​ja uudestaan.
Joten tämä on asia, jossa jokainen rekursiivinen puhelu on todella päivittää jotain.
Joten meidän täytyy tehdä alku + loppu / 2 + 1, tai muuten siellä asia
jos emme oikeastaan ​​päivittää alkua.
Jokainen nähdä, että?
Okei.
Onko kellään kysyttävää tähän ratkaisuun tai enemmän kommentteja?
Okei. Onko kellään iteratiivinen ratkaisu, että me kaikki voimme katsoa?
Oliko me kaikki teemme sen rekursiivisesti?
Tai myös Oletan, jos olet avannut omansa, niin saatat olla ohittaa teidän edellinen.
Onko se automaattisesti tallentaa? En ole varma.
Onko kellään iteratiivinen?
Voimme kävellä sen läpi yhdessä, jos ei.
Ajatus tulee olemaan sama.
Iteratiivinen ratkaisu.
Aiomme haluavat periaatteessa tehdä sama ajatus
jossa haluamme seurata uuden vuoden jono ja uusi alku on array
ja tehdä sen uudestaan ​​ja uudestaan.
Ja jos me olemme tarkkailemalla kuin alku ja loppu koskaan leikkaavat,
silloin emme löydä sitä, ja me voimme palata vääriä.
Joten miten voin tehdä sen? Kellään ehdotuksia tai koodia minun vetää ylös?
[Opiskelija] Do while-silmukka. >> Joo.
Olet menossa halua tehdä silmukka.
>> Oliko sinulla koodin voisin vetää ylös, tai mitä aioit ehdottaa?
[Opiskelija] Luulen niin. >> Selvä. Tämä helpottaa asioita. Mikä oli nimesi?
[Opiskelija] Lucas.
Revision 1. Okei.
Matala me kutsuimme aloittaa ennen.
Up ei ole aivan mitä vaadimme loppua ennen.
Oikeastaan, loppu on nyt sisällä array. Se osa meidän pitäisi harkita.
Niin alhainen on 0, ylös on koko array - 1,
ja nyt looping, ja olemme tarkkailun -
Oletan, voit kävellä sen läpi.
Mikä oli sinun ajattelu kautta? Kävele meihin koodi.
[Opiskelija] Toki. Katsokaa heinäsuovasta arvo keskeltä ja verrata sitä neulaa.
Joten jos se on suurempi kuin neula, sitten haluat - oh, todella, että pitäisi olla taaksepäin.
Olet menossa halua heittää pois oikea puoli, ja niin joo, se olisi tie.
[Bowden] Joten tämä olisi vähemmän? Onko se mitä sanoit? >> [Opiskelija] Joo.
[Bowden] Okei. Vähemmän.
Joten jos mitä me tarkastelemme on pienempi kuin mitä me haluamme,
Sitten joo, me haluamme heittää pois vasen puoli,
mikä tarkoittaa Päivitämme kaiken harkitset
siirtämällä alhainen oikealle jono.
Tämä näyttää hyvältä.
Mielestäni se on sama asia, sanoimme edellinen,
jos jos pieni on 0 ja ylös on 1, niin pieni + ylös / 2 on menossa perustamaan olla saman uudestaan.
>> Ja vaikka se ei pidä paikkaansa, se on vielä tehokkaampi ainakin
vain heittää pois elementin me vain katsoi jonka tiedämme olevan väärin.
Niin pieni + ylös / 2 + 1 - >> [opiskelija] Sen pitäisi olla toisinpäin.
[Bowden] Tai Tämän pitäisi olla - 1 ja toinen tulisi olla + 1.
[Opiskelija] Ja olisi kaksinkertainen yhtäläisyysmerkki. >> [Bowden] Joo.
[Opiskelija] Joo.
Okei.
Ja lopuksi, nyt kun meillä on tämä + 1-1 juttu,
on se - se voisi olla - se on aina mahdollista alhainen päätyä arvo on suurempi kuin ylös?
Mielestäni ainoa tapa, joka voi tapahtua - Onko se mahdollista? >> [Opiskelija] En tiedä.
Mutta jos se saa katkaistaan ​​ja sitten saa miinus että 1 ja sitten - >> Joo.
[Opiskelija] Olisi ehkä saada sekaisin.
Mielestäni olisi hyvä vain siksi
se päätyy pienempi niillä olisi oltava yhtäläiset, luulen.
Mutta jos he ovat yhtä, niin emme olisi tehneet samalla silmukka aloittaa
ja me vain olisi palannut arvoa. Joten mielestäni olemme nyt hyvä.
Huomaa, että vaikka tämä ongelma ei ole enää rekursiivinen,
samanlaiset näkemykset sovelleta, jos voimme nähdä miten tämä niin helposti otollisia
on rekursiivinen ratkaisu se, että olemme vain päivittää indeksejä uudestaan ​​ja uudestaan,
Teemme ongelma pienempiä ja pienempiä, emme keskitytään osajoukko jono.
[Opiskelija] Jos alhainen, on 0 ja ylös on 1, ne molemmat olla 0 + 1/2, joka menisi 0,
ja sitten yksi olisi + 1, yksi olisi - 1.
[Opiskelija] Mihin olemme tarkkailun tasa-arvoa?
Kuten jos keskimmäinen on todella neula?
Emme tällä hetkellä tee sitä? Oh!
Jos Se on -
Kyllä. Emme voi vain tehdä testi täällä, koska sanotaanko ensimmäinen Lähi -
[Opiskelija] Se oikeastaan ​​kuin saa heittää pois sidottu.
Joten jos heität pois sidottu, sinun täytyy tarkistaa se ensin tai mitä tahansa.
Ah. Joo. >> [Opiskelija] Joo.
Joten nyt olemme heittäneet pois joka meillä nyt katseli,
mikä tarkoittaa, että meidän on nyt myös
if (heinäsuovasta [(matala + ylös) / 2] == neula), voimme palata totta.
Ja onko Laitoin muuten tai vain, jos se tarkoittaa kirjaimellisesti sama asia
koska tämä olisi palannut totta.
Joten laitan if, mutta sillä ei ole väliä.
>> Joten if tämä, muuten tämä, ja tämä on yhteinen asia, en
jos vaikka se on silloin kaikki on hyvin täällä,
kuten alhainen ei voi koskaan olla suurempi kuin ylöspäin, se ei kannata perusteluja siitä onko se totta.
Joten voit yhtä hyvin sanoa, kun pieni on pienempi tai yhtä suuri
tai kun pieni on alle
joten jos ne ovat koskaan yhtä tai matala sattuu kulkemaan ylös,
voimme murtautua ulos tästä silmukan.
Kysymyksiä, huolenaiheita, kommentteja?
Okei. Tämä näyttää hyvältä.
Nyt haluamme tehdä lajitella.
Jos menemme toinen tarkistus, näemme nämä samat numerot,
mutta nyt ne eivät ole enää lajiteltu järjestyksessä.
Ja haluamme toteuttaa lajitella jollakin algoritmi O n log n.
Joten mikä algoritmi luulet meidän pitäisi toteuttaa täällä? >> [Opiskelija] Merge sort.
[Bowden] Joo. Yhdistä sort on O (n log n), niin että me aiomme tehdä.
Ja ongelma tulee olemaan melko samanlainen,
jos se helposti otollisia rekursiivinen ratkaisu.
Voimme myös keksiä iteratiivinen ratkaisu, jos haluamme,
mutta rekursio on helpompaa täällä ja meidän pitäisi tehdä rekursion.
Kai me käydään läpi merge sort ensin
vaikka on ihana video merge sort jo. [Naurua]
Joten yhdistää lajitella olemassa - Olen tuhlata niin paljon tämän paperin.
Voi, on vain yksi jäljellä.
Joten yhdistää.
Oh, 1, 3, 5.
Okei.
Merge kestää kaksi erillistä taulukot.
Yksilöllisesti nämä kaksi ryhmää ovat molemmat lajitellaan.
Joten tämä array, 1, 3, 5, lajitellaan. Tämä joukko, 0, 2, 4, lajitellaan.
Nyt mitä Yhdistämisen pitäisi tehdä, on yhdistää ne yhdeksi array, joka on itse lajiteltu.
Joten me haluamme erilaisia ​​kooltaan 6, joka tulee olemaan näiden elementtien sisälle
vuonna lajiteltu järjestyksessä.
>> Ja jotta voimme hyödyntää sitä, että nämä kaksi ryhmää on lajiteltu
tehdä tämän lineaarisessa ajassa,
lineaarista aikaa merkityksensä, jos tämä joukko on koko x ja tämä on koko Y,
sitten koko algoritmin tulisi olla O-(x + y). Okei.
Joten ehdotuksia.
[Opiskelija] Voisimmeko aloittaa vasemmalta?
Joten voit laittaa 0 alas ensin ja sitten 1 ja sitten täällä olet 2.
Joten se on tavallaan kuin sinulla välilehti joka liikkuu oikealle. >> [Bowden] Joo.
Kummankin matriiseja, jos me vain keskitymme vasemmanpuoleisin elementti.
Koska molemmat ryhmät lajitellaan, me tiedämme, että nämä 2 elementtiä
ovat pienimpiä elementtejä joko array.
Joten se tarkoittaa, että 1 näistä 2 elementtien täytyy olla pienin osa meidän sulautuneen array.
Se vain on niin, että pienin on yksi oikein tällä kertaa.
Niin otamme 0, aseta se vasemmalla koska 0 on pienempi kuin 1,
niin otetaan 0, aseta se meidän ensimmäinen asentoon, ja sitten me päivittää tätä
nyt keskittyä ensimmäinen osa.
Ja nyt me toistamme.
Joten nyt vertaamme 2 ja 1. 1 on pienempi, niin me lisätään 1.
Me päivittää tämän osoitin osoittamaan tämä kaveri.
Nyt teemme sen uudestaan, niin 2. Tämä päivittää, vertaa näitä 2, 3.
Tämä päivittää, sitten 4 ja 5.
Joten se on merge.
>> Sen pitäisi olla aika selvää, että se on lineaarinen aika koska olemme vain mennä poikki jokaisen elementin kerran.
Ja se on suurin askel täytäntöönpanoon merge sort tekee tätä.
Ja se ei ole niin kova.
Pari asiaa murehtia on sanokaamme olimme yhdistäminen 1, 2, 3, 4, 5, 6.
Tällöin päädymme tilanteessa, jossa tämä tulee olemaan pienempi,
sitten päivittää tätä osoitin, tämä tulee olemaan pienempi, päivittää tätä,
tämä on pienempi, ja nyt sinulla on tunnustettava
kun olet todella loppuu elementtejä verrata.
Koska olemme jo käyttäneet tätä koko jono,
kaikki tämä joukko on nyt vain työnnetään täällä.
Joten jos me koskaan joutunut siihen pisteeseen, jossa yksi paneelit on täysin yhdistetty jo,
Sitten me vain ottaa kaikki osatekijät muiden array ja aseta ne loppuun array.
Joten voimme vain lisätä 4, 5, 6. Okei.
Se on yksi asia varoa.
Toteuttaminen pitäisi olla vaihe 1.
Yhdistä lajitella sitten perustuu, että se on 2 vaihetta, 2 typerä vaiheita.
Mennään vain antaa tämän array.
Joten yhdistää lajitella, vaihe 1 on rekursiivisesti rikkoa taulukon kahtia.
Joten jakaa tämä ryhmä kahtia.
Meillä on nyt 4, 15, 16, 50 ja 8, 23, 42, 108.
Ja nyt me teemme sen uudelleen ja me jakaa nämä kahteen puoliskoon.
Otan vain tehdä sen tällä puolella.
Joten 4, 15 ja 16, 50.
Haluamme tehdä saman täällä.
Ja nyt me jakaa sen kahtia uudelleen.
Ja meillä on 4, 15, 16, 50.
Niin, että on meidän tukikohta tapauksessa.
Kun ryhmät ovat kooltaan 1, sitten pysähtyy halkaisu kahtia.
>> Mitä nyt teemme tämän?
Päädymme tähän myös jakautuvat 8, 23, 42, ja 108.
Joten nyt olemme tässä vaiheessa, nyt lisättävä kaksi merge sort on vain yhdistämällä paria listoille.
Niinpä haluamme yhdistää nämä. Me vain kutsumme sulautua.
Tiedämme merge palaa näitä lajiteltu järjestyksessä.
4, 15.
Nyt haluamme yhdistää nämä, ja joka palauttaa listan kanssa kuin lajiteltu järjestyksessä,
16, 50.
Me yhdistää nuo - En pysty kirjoittamaan - 8, 23 ja 42, 108.
Joten meillä on sulautunut paria kerran.
Nyt me vain yhdistää uudelleen.
Huomaa, että kukin näistä luetteloista lajitellaan itsessään,
ja sitten voimme vain yhdistää nämä luettelot saada luettelon kokoa 4, joka on järjestetty
ja yhdistää nämä kaksi luetteloa saada listan kokoa 4, joka on järjestetty.
Ja lopuksi, voimme yhdistää nämä kaksi luetteloa koko 4 saada yksi listan koko 8, joka on järjestetty.
Joten nähdä, että tämä on yleinen n log n, olemme jo nähneet, että yhdistämisessä on lineaarinen,
joten kun olemme tekemisissä yhdistämällä näitä, niin kuin kokonaiskustannukset merge
Näiden kahden luettelon on vain 2, koska -
Tai no, se on O n, mutta n tässä on vain nämä 2 elementtiä, joten se on 2.
Ja nämä 2 ovat 2 ja nämä 2 ovat 2 ja nämä 2 ovat 2,
joten kaikilla on sulautuu että meidän täytyy tehdä, päädymme tekemään n..
Kuten 2 + 2 + 2 + 2 on 8, joka on n,
joten kustannukset sulautuvan tähän sarjaan on n.
Ja sitten sama asia tässä.
Me yhdistää nämä 2, niin nämä 2 ja erikseen tätä Yhdistäminen kestää neljä operaatiota,
Tämän yhdistämisen kestää neljä operaatiota, mutta jälleen kerran, kaikkien näiden,
päädymme sulautuvan n kaikista asioista, joten tämä vaihe kestää n..
Ja niin jokainen taso kestää n alkio on yhdistetty.
>> Ja kuinka monta tasoa on olemassa?
Kullakin tasolla, meidän array kasvaa koko 2.
Tässä meidän paneelit ovat kooltaan 1, täällä he kokoa 2, täällä he koon 4,
ja lopuksi he kooltaan 8.
Joten koska se kaksinkertaistaa, siellä tulevat olemaan yhteensä log n näiden tasojen.
Joten log n tasoa, kukin taso ottaen n yhteensä toiminnan
saamme n log n algoritmi.
Kysymyksiä?
Ovatko ihmiset jo edistynyt miten toteuttaa tämä?
Onko joku jo tilassa, jossa voin vain vetää heidän koodia?
Voin antaa minuutti.
Tämä tulee olemaan pidempi.
Suosittelen toistu -
Sinun ei tarvitse tehdä rekursio varten Yhdistämisen
koska tehdä rekursio varten yhdistämisen, olet menossa on kuljettava joukko erikokoisia.
Voit, mutta se on ärsyttävää.
Mutta rekursio for sort itsessään on melko helppoa.
Sinä vain kirjaimellisesti soittaa eräänlainen vasemmalla puoli, lajitella oikealla puoli. Okei.
Kellään mitään voin vetää vielä?
Tai muuten Annan minuutti.
Okei.
Kellään jotain voimme työskennellä?
Tai muuten me vain toimi tässä ja laajenna sitten sieltä.
>> Kellään enemmän kuin tämä, että voin vetää?
[Opiskelija] Joo. Voit vetää omani. >> Selvä.
Kyllä!
[Opiskelija] Oli paljon ehtoja. >> Voi ampua. Voitko -
[Opiskelija] Minun täytyy pelastaa se. >> Joo.
Niin teimme tehdä yhdistämisen erikseen.
Voi, mutta se ei ole niin paha.
Okei.
Joten tavallaan itse vain soittaa mergeSortHelp.
Selitä meille, mitä mergeSortHelp tekee.
[Opiskelija] MergeSortHelp melko paljon tekee kaksi päävaihetta,
joka on lajitella kummankin puolen array ja sitten yhdistää molemmat.
[Bowden] Okei, joten anna minulle toinen.
Mielestäni tämä - >> [opiskelija] Minun täytyy -
Joo. Olen puuttuu jotain.
Vuonna merge, ymmärrän, että minun täytyy luoda uuden taulukon
koska en voinut tehdä sitä paikallaan. >> Kyllä. Et voi. Korjaa.
[Opiskelija] Joten voin luoda uuden taulukon.
Unohdin lopussa sulautua uudelleen muuttaa.
Okei. Tarvitsemme uuden taulukon.
Vuonna merge sort, tämä on melkein aina totta.
Osa kustannuksista parempaa algoritmia ajallisesti
on lähes aina tarvitse käyttää hieman enemmän muistia.
Joten tässä, ei väliä kuinka teet yhdistää lajitella,
sinun väistämättä täytyy käyttää ylimääräistä muistia.
Hän loi uuden taulukon.
Ja sitten sanot lopussa meidän tarvitsee vain kopioida uuden array osaksi alkuperäistä array.
[Opiskelija] Luulen niin, kyllä.
En tiedä, jos se toimii suhteen laskeminen viittaamalla tai mitä tahansa -
Joo, se toimii. >> [Opiskelija] Okei.
Oletko kokeilla tämän? >> [Opiskelija] Ei, ei vielä. >> Okei.
Kokeilla sitä, ja sitten minä puhua sitä toista.
[Opiskelija] Minun täytyy olla kaikkien tehtävä prototyyppejä ja kaikkea, mutta, eikö?
Toiminto prototyypit. Ai, tarkoitatko kuin - Kyllä.
Järjestä soittaa mergeSortHelp.
>> Joten jotta sort soittaa mergeSortHelp, mergeSortHelp on joko on määritelty
ennen lajitella tai meidän täytyy vain prototyyppi. Kopioi ja liitä se.
Ja vastaavasti mergeSortHelp kutsuu sulautuvat,
mutta Yhdistämisen ei ole vielä määritelty, joten voimme vain antaa mergeSortHelp tietää
että sitähän yhdistää tulee näyttämään, ja se siitä.
Niin mergeSortHelp.
Meillä on ongelma täällä, jossa meillä ei ole perustapaus.
MergeSortHelp on rekursiivinen, joten mitään rekursiivista funktiota
on menossa on jonkinlainen pohja asian tietää milloin lopettaa rekursiivisesti itseään kutsuva.
Mikä on meidän tukikohta tapaus aiotaan täällä? Joo.
[Opiskelija] Jos koko on 1? >> [Bowden] Kyllä.
Niin kuin näimme oikeassa, pysähdyimme halkaisu ryhmät
kun saimme paneelit koko 1, mikä väistämättä lajitellaan itse.
Joten jos koko on 1, tiedämme taulukko on jo lajiteltu,
joten voimme vain palata.
>> Huomaa, että on mitätön, joten emme palauta mitään erityistä, me vain palata.
Okei. Niin, että meidän perustapaus.
Luulen meidän tukikohta tapauksessa voisi myös olla, jos satumme olla sulautuvan joukko koko 0,
me luultavasti halua lopettaa jossain vaiheessa,
joten voimme sanoa koko on vähemmän kuin 2 tai pienempi tai yhtä suuri kuin 1
niin että tämä toimii mitään array nyt.
Okei.
Niin, että meidän perustapaus.
Nyt haluat kävellä meitä merge?
Mitä nämä tapaukset tarkoittaa?
Täällä, me vain teemme saman ajatuksen, -
[Opiskelija] minun täytyy kulkee koko kaikki mergeSortHelp puhelut.
Lisäsin koko ylimääräisenä ensisijaisena ja se ei ole siellä, kuten koko / 2.
[Bowden] Oh, koko / 2, koko / 2. >> [Opiskelija] Niin, ja myös edellä toimisivat yhtä hyvin.
[Bowden] Täällä? >> [Opiskelija] Vain kokoa. >> [Bowden] Oh. Koko, koko? >> [Opiskelija] Joo.
[Bowden] Okei.
Saanen ajatella toista.
Onko meillä törmätä ongelma?
Olemme aina hoidettaessa vasemmalle 0. >> [Opiskelija] No
Se on väärin myös. Anteeksi. Sen pitäisi olla alku. Joo.
[Bowden] Okei. Pidän siitä paremmin.
Ja loppu. Okei.
Joten nyt haluat kävellä meitä merge? >> [Opiskelija] Okei.
Olen vain kävelemällä tämän uuden taulukon, että olen luonut.
Sen koko on koko osan array, että haluamme voidaan lajitella
ja yrittää löytää tekijä, että minun pitäisi laittaa uuden taulukon askel.
Niin tehdä, että ensin olen tarkistaa, jos vasen puoli array edelleen saada lisää elementtejä,
ja jos ei, niin menet alas, että muu tila, joka vain sanoo
Okei, sen on oltava oikeassa array, ja laitamme, että nykyinen indeksi newArray.
>> Ja sitten muuten olen tarkistaa, jos oikea puoli matriisi on myös valmis,
jolloin juuri laittaa vasemmalle.
Jotka eivät ehkä ole todellisuudessa tarpeen. En ole varma.
Mutta joka tapauksessa, kaksi muuta Tarkista, kumpi on pienempi vasemmalle tai oikealle.
Ja myös kussakin tapauksessa olen mukaa kumpi paikkamerkki I kasvattaa.
[Bowden] Okei.
Se näyttää hyvältä.
Onko kellään kommentteja tai huolenaiheita tai kysymyksiä?
Joten neljästä tapauksesta, että meidän on tuotava asiat oikeisiin vain on - tai se näyttää Five -
mutta meidän on harkittava vasemmalla array on loppunut asioita meidän yhdistää,
onko oikea joukko on loppunut asioita meidän yhdistää -
Olen osoittaen mitään.
Joten onko vasemmalla array on loppunut asioita tai oikealle array on loppunut asioita.
Nämä ovat kaksi tapausta.
Tarvitsemme myös triviaali asia, onko vasemman asia on pienempi kuin oikein.
Sitten haluamme valita vasemmalle asia.
Nämä ovat tapauksia.
Joten tämä oli oikeassa, niin se siitä.
Array vasemmalle. Se on 1, 2, 3. Okei. Niin joo, ne ovat neljä asioita kannattaa tehdä.
Ja me ei mennä yli iteratiivinen ratkaisu.
En suosittele -
Yhdistämisen sort on esimerkki funktio, joka on sekä ei hännän rekursiivinen
se ei ole helppoa tehdä häntää rekursiivinen,
mutta se ei ole kovin helppoa tehdä iteratiivinen.
Tämä on erittäin helppoa.
Tämä täytäntöönpano merge lajitella,
yhdistää, ei väliä mitä teet, olet menossa rakentaa yhdistämisen.
>> Joten yhdistää sort päälle rakennetaan Merge rekursiivisesti vain nämä kolme riviä.
Iteratiivisesti, se on ärsyttävää ja vaikea ajatella.
Mutta huomaa, että se ei ole häntää rekursiivinen koska mergeSortHelp - kun se kutsuu itseään -
se on vielä tehdä asioita tämän jälkeen rekursiivinen puhelu palaa.
Joten tämä pinokehys on edelleen olemassa, vaikka kutsumalla tätä.
Ja sitten kun soitat tätä, pinokehys on edelleen olemassa
sillä senkin jälkeen puhelun, tarvitsemme vielä yhdistää.
Ja se on triviaali tehdä tämä häntää rekursiivinen.
Kysymyksiä?
Selvä.
Niin menee takaisin lajitella - Voi, on kaksi asiaa haluan näyttää. Okei.
Palataan lajitella, teemme tämän nopeasti.
Tai etsi. Lajittele? Lajittele. Joo.
Palataan alkua lajitella.
Haluamme luoda algoritmi, joka lajittelee taulukon jollakin algoritmilla
O n.
Joten miten tämä on mahdollista? Onko kellään minkäänlaista -
Olen vihjannut ennen klo -
Jos aiomme paranevan n log n O n,
olemme parantaneet algoritmin ajallisesti,
mikä tarkoittaa sitä, mitä aiomme pitää tehdä tehdä niin, että?
[Opiskelija] Space. >> Joo. Aiomme käyttää enemmän tilaa.
Eikä edes enemmän tilaa, se on eksponentiaalisesti enemmän tilaa.
Joten mielestäni tällainen algoritmi on pseudo jotain, pseudo polynomin -
pseudo - En muista. Pseudo jotain.
Mutta se johtuu meidän täytyy käyttää niin paljon tilaa
, että tämä on saavutettavissa, mutta ei realistinen.
>> Ja miten saavutamme tämän?
Voimme saavuttaa tämän, jos voimme taata, että tietty alkio
alittaa tietyn koon.
Joten vain sanoa, että koko on 200,
tahansa osa matriisi on alle koko 200.
Ja tämä on todella realistinen.
Voit helposti saada array että tiedät kaiken siinä
tulee olemaan pienempi kuin jokin määrä.
Kuten jos sinulla on joitakin erittäin massiivinen vektori tai jotain
mutta tiedät kaiken tulee olla välillä 0 ja 5,
niin se tulee olemaan huomattavasti nopeampi tehdä tätä.
Ja sitoutunut mihin tahansa elementtien on 5,
joten tämä sidottu, eli kuinka paljon muistia aiot käyttää.
Niin sidottu on 200.
Teoriassa on aina sidottu, koska kokonaisluku voi olla vain jopa 4000000000,
mutta se on epärealistinen jälkeen olisimme käyttäen tilaa
suuruusluokkaa 4000000000. Niin, että on epärealistista.
Mutta tässä me sanomme meidän sidottu on 200.
Temppu tehdä sitä O n on teemme toinen joukko kutsutaan laskee koon sidottu.
Joten oikeastaan, tämä on oikotie - En oikeastaan ​​tiedä, jos clang tämä.
Mutta GCC ainakin - Olen olettaen clang tekee sen liian -
tämä vain alustaa koko ryhmän olevan 0s.
Joten jos en halua tehdä sitä, niin voisin erikseen tehdä (int i = 0;
i <BOUND; i + +) ja laskee [i] = 0;
Joten nyt kaikki on alustettu 0.
Olen toistaa yli minun array,
ja mitä olen tekemässä on Luotan määrä kunkin - Mennään tänne.
Meillä on 4, 15, 16, 50, 8, 23, 42, 108.
Mitä Luotan on esiintymien lkm jokainen näistä seikoista.
Katsotaanpa itse lisätä pari enemmän täällä joitakin toistoja.
Joten arvo täällä on, arvo, joka tulee olemaan array [i].
Joten val voi olla 4 tai 8 tai mitä tahansa.
Ja nyt olen counting kuinka moni tästä arvosta olen nähnyt,
niin väliä [Val] + +;
Kun tämä on tehty, tärkeintä on menossa katsomaan jotain 0001.
Tehdään väliä [Val] - Bound + 1.
>> Nyt se vain selittää, että olemme alkaen 0.
Joten jos 200 tulee olemaan meidän suurin määrä,
Sitten 0-200 on 201 asiaa.
Joten laskee, se tulee näyttämään 00001 koska meillä on yksi 4.
Sitten meillä on 0001, jossa meillä on 1 8. indeksi count.
Meillä on 2 23. indeksi count.
Meillä on 2 42. indeksi count.
Joten voimme käyttää count.
Joten num_of_item = laskee [i].
Ja niin jos num_of_item on 2, se tarkoittaa, että haluamme lisätä 2 numero i
meidän lajiteltu array.
Joten meidän täytyy seurata, kuinka pitkälle olemme osaksi array.
Joten index = 0.
Array - Minä vain kirjoitan sen.
Counts -
array [index + +] = i;
Sitäkö haluan? Luulen, että se mitä haluan.
Kyllä, tämä näyttää hyvältä. Okei.
Joten ei kaikki ymmärrä, mitä tarkoitusta minun laskee array on?
Se laskee tapahtumien määrä kutakin näistä numeroista.
Sitten olen iteroimalla yli ratkaisee array,
ja i: nnen aseman laskee array
on määrä minun tuo pitäisi näkyä minun lajiteltu array.
Siksi laskennat 4 tulee olemaan 1
ja laskee 8 tulee olemaan 1, laskee 23 tulee olemaan 2.
Niin, että miten moni heistä Haluan lisätä minun lajiteltu array.
Sitten vain tehdä se.
Olen lisäämällä num_of_item i on minun lajiteltu array.
>> Kysymyksiä?
Ja niin tämä on jälleen lineaarinen aika, koska olemme juuri iteroimalla yli tämän kerran,
mutta se on myös lineaarinen mitä tämä numero sattuu olemaan,
ja niin se on vahvasti riippuvainen mitä sidotun on.
Sidotulla 200, se ei ole niin paha.
Jos sidottu tulee olemaan 10000, niin se on hieman huonompi,
mutta jos sitoutuneen tulee olemaan 4 miljardia, joka on täysin epärealistinen
ja tämä ryhmä on menossa on oltava koko 4 miljardia euroa, mikä on epärealistista.
Joten se siitä. Kysymyksiä?
[Äänetön opiskelija vastausta] >> Okei.
Tajusin yhden asian, kun olimme menossa läpi.
Mielestäni ongelmana oli Lucasin ja luultavasti joka ikinen olemme nähneet.
Olen täysin unohtanut.
Ainoa asia, jonka halusin kommentoida on, että kun olet tekemisissä asioita, kuten indeksit,
et koskaan todella nähdä tämän, kun olet kirjoittamassa varten silmukka,
mutta teknisesti, kun olet tekemisissä näiden indeksien,
sinun pitäisi oikeastaan ​​aina käsitellä unsigned kokonaislukuja.
Syynä tähän on, kun olet tekemisissä allekirjoitettu kokonaislukuja,
joten jos sinulla on 2 allekirjoittaneet kokonaislukuja ja lisäät ne yhteen
ja he päätyvät liian iso, niin voit päätyä negatiivinen luku.
Niin, että mitä kokonaisluvun ylivuoto on.
>> Jos lisään 2000000000 ja 1000000000, päädyn negatiivinen 1000000000.
Näin kokonaislukuja toimi tietokoneissa.
Joten ongelma käyttäen -
Se on hienoa, paitsi jos pieni sattuu olemaan 2 miljardia jopa sattuu olemaan 1000000000,
tämä tulee olemaan negatiivinen 1000000000 ja sitten me aiomme jakaa, että 2
ja lopulta negatiivinen 500 miljoonaa euroa.
Joten tämä on vain ongelma, jos satut olemaan hakuja array
miljardeja asioita.
Mutta jos pieni + asti tapahtuu ylivuoto, niin se on ongelma.
Heti kun saamme heidät unsigned, sitten 2 miljardia plus 1 miljardi on 3000000000.
3000000000 jaettuna 2 on 1,5 miljardia euroa.
Joten kun he unsigned, kaikki on täydellistä.
Ja niin se on myös ongelma, kun olet kirjoittanut silmukoita,
ja oikeastaan ​​se luultavasti tekee sen automaattisesti.
Se oikeastaan ​​vain huutaa sinulle.
Joten jos tämä määrä on liian suuri vain kokonaisluku, mutta se sopii allekirjoittamaton kokonaisluku,
se huutaa sinulle, joten siksi te koskaan joutunut asiaa.
Voit nähdä, että indeksi ei koskaan tule olemaan negatiivinen,
joten kun olet iteroimalla yli array,
voit melkein aina sanoa unsigned int i, mutta et todellakaan tarvitse.
Asiat ovat menossa töihin melko paljon yhtä hyvin.
Okei. [Kuiskaa] Mitä kello on?
Viimeinen asia, jonka halusin näyttää - ja minä vain tehdä se todella nopeasti.
Tiedätkö miten olemme # define jotta voimme # define MAX kuin 5 tai jotain?
Älkäämme tee MAX. # Define sidottava 200. Niinhän me teimme ennen.
Se määrittelee vakio, joka on juuri menossa kopioida ja liittää
missä satumme kirjoittaa sidottu.
>> Jotta voimme todella tehdä enemmän # määrittelee.
Voimme # define toimintoja.
He eivät oikeasti toimii, mutta me kutsumme heitä toimintoja.
Esimerkiksi olisi jotain MAX (x, y) on määritelty (x <y? Y: x). Okei.
Joten sinun pitäisi tottua ternäärinen operaattorin syntaksi,
mutta on x pienempi kuin y? Return y, muuten palauta x.
Näet siis voit tehdä tämän erillisenä toimintona,
ja toiminta voisi olla bool MAX kestää 2 argumentteja, palauta.
Tämä on yksi yleisimpiä näen tehnyt näin. Me kutsumme heitä makroja.
Tämä on makro.
Tämä on vain syntaksi sitä.
Voit kirjoittaa makron tehdä mitä haluat.
Voit usein nähdä makroja virheenkorjaus printfs ja tavaraa.
Joten tyyppi printf olemassa erityisiä vakiot C kuten alaviiva LINE alaviiva
2 alaviivoja LINE alaviiva
ja siellä on myös mielestäni 2 alaviivoja FUNC. Se voi olla sitä. Jotain sellaista.
Nämä asiat korvataan funktion nimi
tai numero rivin olet.
Usein, kirjoittaa virheenkorjaus printfs että tänne voisin sitten vain kirjoittamaan
Debug ja se tulostaa rivin numero ja toiminto, satun olemaan
että se olisi kohdannut että DEBUG lausuma.
Ja voit myös tulostaa muita asioita.
Joten yksi asia sinun pitäisi varoa on jos satun # define DOUBLE_MAX
kuin jotain 2 * y ja 2 * x.
Joten jostain syystä satut tehdä paljon.
Joten tee se makro.
Tämä on itse asiassa rikki.
Minä kutsuisin sitä tekemällä jotain DOUBLE_MAX (3, 6).
Joten mitä pitäisi palauttaa?
[Opiskelija] 12.
Kyllä, 12 olisi palautettava, ja 12 palautetaan.
3 saa korvataan x, 6 saa korvata y, ja palaamme 2 * 6, joka on 12.
Mitä nyt tästä? Mitä pitäisi palauttaa?
[Opiskelija] 14. >> Ihannetapauksessa 14.
Kyse on siitä, miten hash määrittelee työn, muista se kirjaimellisesti kopioi ja liitä
on aika paljon kaikkea, niin mitä tämä tulee tulkita
on 3 alle 1 + 6, 2 kertaa 1 + 6, 2 kertaa 3.
>> Joten tästä syystä melkein aina kääri kaiken suluissa.
Jokainen muuttuja melkein aina kääri suluissa.
On tapauksia, joissa ei tarvitse, kuin minä tiedän, että minun ei tarvitse tehdä sitä täällä
koska alle on melko paljon aina juuri menossa töihin,
vaikka se ehkä ole edes totta.
Jos siellä on jotain naurettavaa kuten DOUBLE_MAX (1 == 2),
niin se on menossa korvataan 3 alle 1 vastaa vastaa 2,
ja niin sitten se tulee tehdä 3 alle 1, ei se yhtä 2,
joka ei ole sitä, mitä me haluamme.
Joten estääkseen operaattorin edelle ongelmia,
Kääri suluissa.
Okei. Ja siinä se, 5:30.
Jos sinulla on kysyttävää PSET, meille.
Sen pitäisi olla hauskaa, ja hakkeri painos on myös paljon realistisempi
kuin hakkeri painos viime vuoden, joten toivomme, että paljon yrität sitä.
Viime vuoden oli erittäin ylivoimainen.
>> [CS50.TV]