[Powered by Google Translate] [3. jagu - mugavam]
[Rob Bowden - Harvardi Ülikool]
>> [See on CS50. - CS50.TV]
>> Nii et esimene küsimus on kummaliselt sõnastatud.
GDB saate "siluda" programm, kuid täpsemalt, mida see teile teha?
Ma vastan, et üks, ja ma ei tea, mis täpselt oodatakse,
nii et ma olen aim see on midagi eeskujul ta laseb teid samm-sammult
kõndida läbi programmi, suhelda ta, muutus muutujaid, teha kõiki neid asju -
põhimõtteliselt täielikult kontrolli täitmise programmi
ja kontrollida mis tahes osa programmi täitmiseks.
Nii et need funktsioonid võimaldavad teil siluda asju.
Okei.
Miks binaarne otsing nõuda, et massiiv sorteeritud?
Kes tahab sellele vastata?
[Üliõpilane] Sest see ei toimi, kui see ei järjestatud. >> Jah. [Naer]
Kui see ei ole sorteeritud, siis on võimatu jagada see pooleks
ja tean, et kõik vasakule on vähem ja kõike paremal
on üle keskmise väärtuse.
Seega tuleb välja sorteerida.
Okei.
Miks on mull sorteerida O n ruudus?
Kas keegi kõigepealt tahan anda väga kiire kõrgetasemeline ülevaade sellest, mis mull sorteerida on?
[Üliõpilane] Sa põhimõtteliselt läbida iga element ja teil vaadata esimese paari elemente.
Kui nad välja, kus sa vahetada neid, siis vaadake järgmise paari elemente ja nii edasi.
Kui jõuad lõpuks, siis sa tead, et suurim element on paigutatud lõpus,
nii et sa ignoreerida, et üks siis hoida läheb läbi,
ja iga kord, sa pead kontrollima üks vähem element, kuni te ei muudeta. >> Jah.
Seda nimetatakse mull sorteerida, sest kui sa flip massiivi küljel nii et see on üles ja alla, vertikaalne,
siis suur väärtused vajuvad põhja ja väikesed väärtused mulksuma üles.
See, kuidas ta sai oma nime.
Ja jaa, sa lihtsalt läbi minema.
Hoiad läbimas massiivi, vahetades suuremat väärtust
saada suurim väärtused alt.
>> Miks on O n ruudus?
Esiteks, keegi ei taha öelda, miks see O n ruudus?
[Üliõpilane] Sest iga katse läheb n korda.
Võite kindel olla vaid siis, kui olete võtnud suurima osa kogu tee alla,
siis sa pead kordama, et nii palju elemente. >> Jah.
Nii et pidage meeles, mida Big O tähendab ja mida suur Omega vahenditega.
Big O on nagu ülemise kuidas aeglane see saab reaalselt sõita.
Nii öeldes see O n ruudus, see ei ole O n muidu oleks võimelised sõitma
üksteise aega, kuid see on O n kuubis
sest see on piiratud O n kuubis.
Kui see on piiratud O n ruudus, siis see on piiratud ka n kuubis.
Nii et see on n ruudus, ja absoluutne halvimal juhul ei saa teha paremini kui n ruudus,
mis on põhjus, miks see O n ruudus.
Nii et näha kerget matemaatikat, kuidas asi välja tuleb n ruudus,
kui meil on viis asju meie nimekirjas, esimest korda, kuidas paljud vahetustehingud võiks meil olla vaja teha
et saada seda? Olgem tegelikult lihtsalt -
Mitu vahetuslepingud me kavatseme peavad tegema, esimene sõit mull sorteerida läbi massiivi?
[Üliõpilane] n - 1. >> Jah.
>> Kui seal on 5 elementi, me ei kavatse vaja teha n - 1.
Siis teine, kui palju vahetuslepingud me kavatseme tegema?
[Üliõpilane] n - 2. >> Jah.
Ja kolmas saab olema n - 3 ja seejärel lükitud ma kirjutan kahe viimase
kui siis lähed vaja teha 2 vahetuslepingud ja 1 swap.
Ma arvan, et viimane ei pruugi tegelikult vaja juhtuda.
Kas see swap? Ma ei tea.
Nii et need on kogusummad vahetuslepingud või vähemalt võrdlusi sa pead tegema.
Isegi kui te ei vaheta, ikka on vaja võrrelda väärtusi.
Nii on n - 1 võrdlust esietendus läbi massiivi.
Kui teil ümber need asjad, olgem tegelikult teha seda kuus asjad nii asjad Kestab ilusti,
ja siis ma teen 3, 2, 1.
Nii lihtsalt ümber tõstes need summad, me tahame näha, kuidas paljud võrdlused teeme
kogu algoritm.
Nii et kui me toome need kutid siin all,
siis me veel lihtsalt liidetakse siiski palju võrdlusi oli.
Aga kui me kokku neid ja me Kokkuvõttes need ja me Kokkuvõttes need,
see on ikka sama probleem. Me lihtsalt kokku nende konkreetsete rühmade.
>> Nii et nüüd me liidetakse 3 n 's. See ei ole lihtsalt 3 n 's.
See on alati saab olema n / 2 n 's.
Nii et siin me juhtumisi on 6.
Kui meil oleks 10 asja, siis võiks seda teha rühmituse 5 erinevat paari asja
ja lõpuks n + n + n + n + n.
Nii olete alati hakka n / 2 n on, ja nii see me kübeke see välja n ruudus / 2.
Ja nii kuigi see on tegur poole, mis juhtub tulema
sest asjaolu, et läbi iga iteratsiooni üle massiivi me võrdleme 1 vähem
nii see on, kuidas me saame üle 2, aga see on ikkagi n ruudus.
Me ei hooli pidev tegur poole.
Nii palju suuri O selliseid asju toetub just selline seda selline matemaatika,
tehes aritmeetika summad ja geomeetrilise jadana kraami,
kuid enamik neist selles muidugi on üsna lihtne.
Okei.
Miks on sisestamise omamoodi Omega n? Mis omega tähendab?
[Kaks üliõpilast rääkides korraga - arusaamatu] >> Jah.
Omega sa ei mõtle nagu alampiir.
>> Nii et ükskõik kui tõhus teie sisestamise omamoodi algoritm on,
olenemata nimekirja, mis on vastu võetud, see on alati võrrelda vähemalt n asjad
või peab ta itereerime n asju.
Miks nii?
[Üliõpilane] Sest kui nimekiri on juba sorteeritud, siis läbi esimese iteratsiooni
saab ainult tagada, et kõige esimene element on vähim,
ja teise iteratsiooni saab ainult tagada kaks esimest on
sest sa ei tea, et ülejäänud nimekirja sorteeritakse. >> Jah.
Kui te kaotate täiesti järjestatud nimekirja, vähemalt sa pead minema üle kõik elemendid
näha, et midagi tuleb liigutada.
Nii jooksevad üle nimekirja ja ütleb Oh, see on juba sorteeritud,
see on võimatu, et sa teaksid seda inimest järjestatud kuni teil kontrollida iga element
näha, et nad on järjestatud järjekorras.
Nii alampiiri sisestamise sorteerida on Omega n.
Mis halvimal juhul sõiduaega ühendamise sortida,
Halvimal juhul on suur O uuesti?
Nii et halvimal juhul kuidas ühendamise omamoodi joosta?
[Üliõpilane] N log n. >> Jah.
Kiireim üldine sortimine algoritmid on n log n. Sa ei saa teha paremini.
>> On erijuhtudel, ja kui meil on aega täna - kuid me ilmselt won't -
me ei näe sellist, mis ei parem kui n log n.
Aga üldiselt juhul, ei saa te teha paremini kui n log n.
Ja ühendada omamoodi juhtub olema üks sa peaksid teadma seda muidugi, et on n log n.
Ja nii me tegelikult rakendatakse, et täna.
Ja lõpuks, mitte rohkem kui kolm lauset, kuidas valik omamoodi töö?
Kas keegi taha vastata, ja Ma loen oma lauseid
sest kui te lähete üle 3 -
Kas keegi mäletab valik omamoodi?
Selection sort on tavaliselt üsna lihtne meeles pidada lihtsalt nimest.
Sa lihtsalt kinnitada, üle massiivi, leida mida iganes suurim väärtus on või väikseim -
mida iganes et sa sorteerimine sisse
Ütleme, et me sorteerimine alates väiksemast suurim.
Sa itereerime massiiv, otsin tahes minimaalne element on,
valige see ja siis lihtsalt vahetada see kõik, mis on esimene koht.
Ja siis teine ​​kiht üle massiivi, otsida minimaalne element uuesti
valige see ja siis vahetada see, mida on teisel positsioonil.
Nii et me lihtsalt korjamise ja valides miinimumväärtustest
ja lisades need ees massiivi, kuni see on lahendatud.
Küsimused, mis?
>> Need paratamatult esinevad vormid pead täitma, kui sisestad pset.
Need on põhiliselt vastused nendele.
Okei, nii et nüüd kodeerimine probleeme.
Ma juba välja saadetud e-posti kaudu - Kas keegi ei saa seda e-maili? Okei.
Ma juba välja saadetud e-posti kaudu ruumi, et me ei kavatse olla kasutades,
ja kui sa vajutad mu nime - nii et ma arvan, et ma lähen allosas
sest tagurpidi r - aga kui klõpsate minu nimi näete 2 revisions.
1. läbivaatamine läheb mul juba kopeeritud ja kleebitud kood Spaces
otsingu asi, mida sa lähed on rakendada.
Ja Revision 2 on omamoodi asi, mida me rakendada pärast seda.
Nii et võite klõpsata minu muudatuse 1. ja tööd sealt.
Ja nüüd me tahame ellu binaarne otsing.
>> Kas keegi taha lihtsalt anda pseudokoodi kõrgetasemeline selgitus
mida me lähed on teha otsingut? Jah.
[Üliõpilane] Sa võta keset massiivi ja vaata, kas see, mida te otsite
on väiksem kui või rohkem.
Ja kui see on väiksem, kui minna pool on vähem,
ja kui see on rohkem, kui minna pool on rohkem ja sa korrata, et kuni sa saad ühe asja.
[Bowden] Jah.
Pange tähele, et meie numbrid massiiv on juba sorteeritud,
ja nii see tähendab, et me võime ära ja me võiks kõigepealt kontrollida,
okei, ma otsin number 50.
Nii et ma ei saa minna keset.
Lähis on raske määratleda, kui see on isegi mitmeid asju,
aga ütleme lihtsalt me ​​alati välja lülitada laeva keskel.
Nii et siin on meil 8 asju, nii keskel oleks 16.
Otsin 50, nii 50 on suurem kui 16.
Nii et nüüd ma ei põhimõtteliselt ravida minu massiivi kui neid elemente.
Ma ei visata kõik 16 üle.
Nüüd on mu massiiv on lihtsalt need 4 elementi, ja ma kordan.
Nii siis ma tahan leida uuesti keskel, mis saab olema 42.
42 on alla 50, nii et ma ei viska need kaks elementi.
See on minu ülejäänud massiiv.
Ma lähen leida kuldset uuesti.
Ma arvan, et 50 oli halb näide, sest olin alati visata ära asju vasakule,
kuid sama meetme, kui ma otsin midagi
ja see on väiksem kui element Ma olen praegu vaadates,
siis ma lähen ära visata kõik paremale.
Nii et nüüd me peame rakendama seda.
Pange tähele, et meil on vaja läbida suurusega.
Me võime ka ei pea raskesti koodi suurusest.
Nii et kui me vabaneme sellest # define -
Okei.
Kuidas ma saan kenasti aru saada, mis suurust numbrid array praegu on?
>> Mitu elemendid on numbrid massiivi?
[Üliõpilane] Numbrid, sulgudes. Pikkus?
[Bowden] See ei eksisteeri C.
Vajad. Pikkus.
Massiivid ei ole omadusi, mistõttu ei ole pikkus vara massiivid
mis just teile kui kaua see juhtub olema.
[Üliõpilane] Vaadake kui palju mälu on ja jagage kui palju - >> Jah.
Niisiis, kuidas me saame näha, kui palju mälu tal on? >> [Üliõpilane] sizeof. >> Jah, sizeof.
Sizeof on operaator, et läheb tagasi suurusest numbrid massiivi.
Ja see saab olema siiski palju täisarvud on korda suurem täisarv
kuna see, kui palju mälu see on tegelikult asumist.
Nii et kui ma tahan palju asju on massiiv,
siis ma lähen taha jagage suurus täisarv.
Okei. Nii et laseb mul läbida suurus siin.
Miks ma pean läbima suurus üldse?
Miks ma ei saa lihtsalt teha siin int size = sizeof (heinakuhjas) / sizeof (int)?
Miks see ei tööta?
[Üliõpilane] See ei ole globaalne muutuja.
[Bowden] heinakuhi olemas ja me läbivad numbrid nagu heinakuhi,
ja see on selline foreshadowing Mis tulema. Jah.
[Üliõpilane] heinakuhi on vaid viide sellele, et ta oleks tagasi, kui suur see viide.
Jah.
Ma kahtlen, loeng, et olete näinud korstnat veel tegelikult, eks?
Me oleme lihtsalt rääkinud ta.
Nii et korstnat on koht, kus kõik oma muutujad ei kavatse hoida.
>> Iga mälu, mis on eraldatud kohalike muutujate läheb pakis,
ja iga funktsiooni saab oma ruumi korstnat oma freimi on, kuidas seda nimetatakse.
Nii et peamine on selle freimi, ja sees see saab eksisteerida see numbrite massiiv,
ja see saab olema nende suurusest sizeof (numbrid).
See saab olema suurus numbrid jagatud suurus elemendid,
aga et kõik elu jooksul peamine on freimi.
Kui me kutsume otsing, otsing sai oma freimi,
oma ruumi, et salvestada kõik oma lokaalsed muutujad.
Aga need argumendid - nii heinakuhjas ei ole koopia sellest kogu massiiv.
Me ei liigu kogu massiivi koopia arvesse otsing.
See lihtsalt läheb viidates, et massiivi.
Nii et otsi pääseb need numbrid läbi see viide.
See on ikka tutvumise asjad, mis elada sees peamine on freimi,
aga põhimõtteliselt, kui saame vihjeid, mida tuleks kiiresti,
see on see, mida osuti on.
Näiturid on vaid viiteid asju, ja mida saab kasutada viiteid juurdepääsu asjad
mis on muud asjad "korstnat raame.
Nii et kuigi numbrid on kohaliku Otse me siiski võimalik seda läbi selle osuti.
Aga kuna see on lihtsalt kursor ja see on lihtsalt viide,
sizeof (heinakuhjas) lihtsalt tagastab suuruse viide ise.
See ei tagasta suuruse asi see osutab.
See ei tagasta tegeliku suuruse numbrid.
Ja nii see ei lähe tööle, kui me tahame seda.
>> Küsimused, mis?
Näiturid on läinud oluliselt rohkem Verine üksikasjalikult lähinädalatel.
Ja see on põhjus, miks paljud asjad, mis sa näed, kõige otsing asju või järjesta asju,
Nad on peaaegu kõik läheb vaja võtta tegelikku suurust massiivi
sest C, me ei tea, mis suurus massiiv on.
Sa pead käsitsi andke seda sisse
Ja sa ei saa käsitsi läbida kogu antennide massiivi, sest sa oled lihtsalt möödaminnes viide
ja see ei saa suurus viide.
Okei.
Nii et nüüd me tahame rakendada, mida seletati varem.
Võite töötada seda hetke,
ja sa ei pea muretsema kõik täiesti 100% töökorras.
Lihtsalt kirjutada üles poole pseudokoodi, kuidas sa arvad, et see peaks toimima.
Okei.
Pole vaja olla täiesti teha seda veel.
Aga kas keegi on mugav, mida nad on seni
nagu midagi saame teha koos?
Kas keegi soovite vabatahtlikuna? Või ma juhuslikult kätte.
See ei pea olema õigus mis tahes meede, kuid midagi saame muuta ühte toimivat riiki.
[Üliõpilane] Muidugi. >> Okei.
Nii saab säästa läbivaatamise klikkides vähe Save ikoonil.
Sa oled Ramya, eks? >> [Üliõpilane] Jah. >> [Bowden] Okei.
Nii et nüüd on mul võimalik näha oma läbivaatamine ning igaüks võib tõmba läbi vaadata.
Ja siin on meil - Okei.
Nii Ramya läks rekursiivne lahendus, mis on kindlasti kehtiv lahendus.
On kaks võimalust, mida saate teha selle probleemiga.
Võite teha seda korduvalt või rekursiivselt.
Enamik probleeme sul tekib, mida saab teha rekursiivselt saab teha ka korduvalt.
Nii et siin me oleme teinud seda rekursiivselt.
>> Kas keegi soovite määratleda, mida tähendab teha funktsiooni rekursiivne?
[Üliõpilane] Kui teil on funktsioon kõne ise
ja siis helistada ise, kuni see väljub õige ja tõsi. >> Jah.
Rekursiivne funktsioon on lihtsalt funktsioon, mis nimetab ennast.
On kolm suurt asja, et rekursiivne funktsioon peab olema.
Esimene on ilmselt see nõuab ise.
Teine on tugipunkt.
Nii et mingil hetkel funktsioon vajab lõpetada helistab ise,
ja see on, mida tugipunkti on.
Nii et siin me teame, et peaksime lõpetama, me peaksime loobuma oma otsing
kui start võrdub lõppu - ja läheme üle, mida see tähendab.
Aga lõpuks, viimane asi, mis on oluline rekursiivne funktsioone:
funktsioonid tuleb kuidagi läheneda tugipunkti.
Nagu kui sa ei ole tegelikult ajakohastamine midagi, kui teete teise rekursiivne kõne
kui sa sõna otseses mõttes lihtsalt kutsutakse funktsioon uuesti samad argumendid
ja ei globaalsed muutujad on muutunud või midagi,
sa ei saavuta kunagi tugipunkti, mille puhul see on halb.
See on lõpmatu rekursiooni ja korstnat ülevoolu.
Aga siin me näeme, et uuendus toimub alates oleme ajakohastamine hakata + lõpp / 2,
uuendame me lõpuks argumenti siin uuendame me alguses argument siin.
Nii et kõik rekursiivne kõned me oleme parasjagu midagi. Okei.
Kas soovite kõndida meid läbi sinu lahendus? >> Muidugi.
Ma kasutan SearchHelp nii et iga kord kui ma seda funktsiooni kõne
Mul on alguses, kus ma otsin on massiiv ja lõpuks
kus ma otsin massiivi.
>> Igal sammul, kus ta ütleb, et see on keset element, mis on algus + lõpp / 2,
on võrdne sellega, mida me otsime?
Ja kui on, siis me leidsime selle, ja ma arvan, et saab edasi kuni tase rekursioon.
Ja kui see pole tõsi, siis me kontrollida, kas seda keset väärtuse massiivi on liiga suur,
sel juhul me vaatame vasakul pool massiivi minnes algusest keskel indeks.
Ja muidu me lõpuks poole võrra.
[Bowden] Okei.
See kõlab hästi.
Okei, nii et paar asja, ja tegelikult on see väga kõrgel tasemel asi
et sa ei pea kunagi teada selle käigus, kuid see on tõsi.
Rekursiivne funktsioone, mida sa kuuled, et nad on halb asi
sest kui sa rekursiivselt nimetad ennast liiga palju kordi, saad korstnat ülevoolu
sest nagu ma enne ütlesin, iga funktsiooni saab oma freimi.
Nii et iga kõne rekursiivne funktsioon sai oma freimi.
Nii et kui teete 1000 rekursiivne kõned, saad 1000 korstnat raamid
ja kiiresti sa kaasa liiga palju korstna raamid ja asjad lihtsalt murda.
Nii et miks rekursiivne funktsioon on üldiselt halb.
Aga seal on tore alagrupis rekursiivne funktsioone nimetatakse saba-rekursiivne funktsioone,
ja see juhtub olema näide, kus kui kompilaator märkab seda
ja see peaks, ma arvan - on rõkkama, kui te kaotate ta-O2 lipp
siis märkad, et see on saba rekursiivne ja teha asju hea.
>> See uuesti sama freimi ikka ja jälle iga rekursiivne kõne.
Ja nii kuna sa kasutad sama freimi, sa ei pea muretsema
kunagi korstnat täis, ja samal ajal, nagu sa ütlesid enne,
kus kui sa tagasi true, siis peab tagastama kuni kõik need virna raamid
ja 10. üleskutse SearchHelp on naasta 9., peab tagastama kuni 8..
Nii et ei ole vaja juhtuda, kui funktsioonid on saba rekursiivne.
Ja nii teebki seda funktsiooni saba rekursiivne on teada, et iga konkreetse kõne searchHelp
rekursiivne kõne, et see teeb ja mida siis tagasi.
Nii et esimene kõne SearchHelp, me kas kohe tagasi false,
kohe tagasi true, või teeme rekursiivne kõne SearchHelp
kus mida me tagasi just, et kõne on tagasi.
Ja me ei saanud seda teha, kui me tegime midagi int x = SearchHelp, tagasi x * 2,
lihtsalt mõne juhusliku muutuse.
>> Nii et nüüd see rekursiivne kõne, see int x = SearchHelp rekursiivne kõne
ei ole enam saba rekursiivne, sest tegelikult ei pea tagastama
tagasi eelmise freimi nii, et eelmine kõne funktsioon
saab siis teha midagi tagastatav väärtus.
Nii et see ei ole saba rekursiivne, kuid mis meil oli enne on kenasti saba rekursiivne. Jah.
[Üliõpilane] ei tohiks teise tugipunkti kontrollitakse 1.
sest seal võib olla olukord, kus, kui te kaotate see argument
olete start = lõpus, kuid nad on nõel väärtus.
Küsimus ei ole meil tekib siis, kui lõpp on nõel väärtus
või start = lõpus, asjakohaselt, start = lõpus
ja sa ei ole tegelikult kontrollida, et erilist väärtust veel,
siis alusta + lõpp / 2 on lihtsalt saab olema sama väärtusega.
Aga me oleme juba tagasi vale ja me tegelikult ei kontrollinud väärtus.
Nii et vähemalt esimeses kõne, kui suurus on 0, siis tahame tagasi false.
Aga kui suurus on 1, siis alguses ei kavatse võrdne lõppu,
ja me vähemalt kontrollida üks element.
Aga ma arvan, teil on õigus, et saame lõpuks juhul, kui hakata + lõpp / 2,
algus jõuab on sama algus + lõpp / 2,
kuid me tegelikult kunagi kontrollinud, et element.
>> Nii et kui me esimest korda vaadata on keset element väärtus me otsime,
siis saame kohe tagasi true.
Else kui nad võrdsed, siis pole mingit mõtet jätkata
kuna me lihtsalt läheb uuendada juhul, kui me oleme ühe elemendi massiivist.
Kui see ühe osa ei ole see, mida me otsime,
siis on kõik vale. Jah.
[Üliõpilane] Asi on selles, et kuna mõõtmed on tegelikult suurem kui elementide arv massiivis,
on juba nihe - >> Nii on suurus -
[Üliõpilane] Ütle kui massiivi oli suurus 0, siis SearchHelp tegelikult kontrollida heinakuhjas 0
aasta esimese kõne.
Massiiv on suurusega 0, seega 0 on - >> Jah.
Seal on teine ​​asi - see võib olla hea. Mõtleme.
Nii et kui massiivi oli 10 elementi ja keskmine me ei kavatse vaadata on punktid 5,
nii me uurime 5, ja oletame, et väärtus on väiksem.
Nii et me viskamine kõik ära 5 aastast.
Nii algab + lõpp / 2 saab olema meie uus eesmärgil
Nii et jah, see on alati jään kauem massiivi.
Kui see on juhul, kui see oli paaris-või paaritu, siis me oleks vaadata, ütleme, 4,
aga me peame veel minema visata -
Nii et jah, lõpuks on alati saab olema lisaks tegelikule lõpuks massiiv.
Nii elemente oleme keskendudes, lõpp on alati saab olema üks pärast seda.
Ja nii kui alguses ei kunagi võrdne lõpuks oleme massiivi suurus 0.
>> Teine asi, ma mõtlesin, et me oleme parasjagu algust tuleb hakata + lõpp / 2,
nii see on nii, et mul on probleeme, kus hakata + lõpp / 2
on element me uurime.
Oletame, et meil oli see 10-element massiivi. Mida iganes.
Nii algab + lõpp / 2 saab olema midagi nagu see üks,
ja kui see ei ole väärtus, ütleme me tahame uuendada.
Väärtus on suurem, nii et me tahame vaadata seda pool massiivi.
Niisiis, kuidas me ajakohastamise algus uuendame me algusest nüüd selle elemendi.
Aga see võib veel palju tööd, või vähemalt, mida saate teha algus + lõpp / 2 + 1.
[Üliõpilane] Sa ei pea olema algus + lõpp [kuuldamatu] >> Jah.
Oleme juba kontrollinud seda elementi ja tean, et see pole see, mida me otsime.
Nii et me ei pea uuendama hakatakse selle elemendi.
Saame vaid jätke see vahele ja ajakohastada hakkavad olema selle elemendi.
Ja on seal kunagi juhul, oletame, et see oli lõpp,
nii siis alustada oleks see, alusta + lõpp / 2 oleks see,
algus + lõpp - Jah, ma arvan, et see võib sattuda lõpmatu rekursiooni.
Oletame, et see on lihtsalt massiivi suurus 2 või massiivi suurus 1. Ma arvan, et see töötab.
Nii et praegu, alguses on see, et element ja lõpuks on 1 väljaspool.
Nii element, mis me kavatseme vaadata on see,
ja siis kui me värskendame algus uuendame me hakatakse 0 + 1/2,
mis läheb lõpuks meid tagasi alguses on see element.
>> Nii et me kontrollida sama elemendi ikka ja jälle.
Nii et see on nii, kui iga rekursiivne kõne peab tegelikult uuendada midagi.
Nii et me peame tegema algus + lõpp / 2 + 1, muidu seal on juhtum
kuhu me tegelikult ei ajakohastamise algus.
Igaüks näed seda?
Okei.
Kas kellelgi on küsimusi selle lahendus või enam kommenteerida?
Okei. Kas keegi on iteratiivne lahendus, et me kõik saame vaadata?
Kas me kõik teeme seda rekursiivselt?
Või ka ma arvan, kui sa avada päralt, siis võib-olla kaalu oma eelmist.
See automaatselt salvestada? Ma ei ole kindel.
Kas keegi on iteratiivne?
Me võime minna läbi see, kui ei saa.
Idee saab olema sama.
Iteratiivsed lahendus.
Me läheme taha põhimõtteliselt teha sama mõte
kuhu me tahame jälgida uute lõpus massiivi ja uue algust massiivi
ja seda ikka ja jälle.
Ja kui see, mida me jälgida, kui algus ja lõpp kunagi ristuvad,
siis me ei leidnud seda ja me saame tagasi false.
Niisiis, kuidas ma seda teen? Igaüks on ettepanekuid või kood, et ma tõmba?
[Üliõpilane] Kas samas silmus. >> Jah.
Sa ei kavatse teha tahad silmus.
>> Kas teil on kood Ma ei tõmba, või mida sa lähed soovitate?
[Üliõpilane] Ma arvan küll. >> Olgu. See teeb asjad lihtsamaks. Mis su nimi oligi?
[Üliõpilane] Lucas.
1. läbivaatamine. Okei.
Madal on see, mida me kutsusime alustada enne.
Kuni ei ole päris see, mida me kutsusime end enne.
Tegelikult lõpp on nüüd jooksul massiivi. See on element peaksime kaaluma.
Nii madal on 0, kuni on suurus array - 1
ja nüüd oleme silmuspõletamise, ja me kontroll -
Ma arvan, et saab kõndida läbi.
Milline oli teie mõtlemise kaudu? Kõnni meid läbi oma kood.
[Üliõpilane] Muidugi. Vaata heinakuhjas väärtus keskel ja võrrelda seda nõela.
Nii et kui see on suurem kui nõela, siis tahad, et - oh, tegelikult, et peaks olema tagurpidi.
Sa lähed tahan visata paremal pool, ja nii jah, et tuleks tee.
[Bowden] Nii et see peaks olema väiksem? Kas see, mida sa ütlesid? >> [Üliõpilane] Jah.
[Bowden] Okei. Vähem.
Nii et kui see, mida me vaatame on väiksem kui see, mida me tahame,
siis jah, me tahame visata vasakule poole
mis tähendab, et me oleme parasjagu kõike me arvestades
liigutades madal paremal massiivi.
See näeb hea välja.
Ma arvan, et see on sama teema, et me ütles eelmine,
kus, kui madal on 0 ja üles on 1, siis madala + üles / 2 kavatse luua üks ja sama asi jälle.
>> Ja isegi kui see nii ei ole, see on veelgi tõhusam, vähemalt
lihtsalt visata element me just vaatasin, mis me teame, on vale.
Nii madal + üles / 2 + 1 - >> [üliõpilane] See peaks olema teistpidi.
[Bowden] Või peaks see olema - 1 ja teine ​​peaks olema + 1.
[Üliõpilane] Ja seal peaks olema topelt võrdusmärk. >> [Bowden] Jah.
[Üliõpilane] Jah.
Okei.
Ja lõpuks, nüüd, et meil on see + 1 - 1 asi,
on see - see ei pruugi olla - kas see on kunagi võimalik madal, et lõpuks suurem väärtus on?
Ma arvan, et ainus viis, mis võib juhtuda - Kas on võimalik? >> [Üliõpilane] Ma ei tea.
Aga kui ta saab kärbitud ja siis läheb miinus, et 1 ja siis - >> Jah.
[Üliõpilane] Oleks võimalik saada messed up.
Ma arvan, et see peaks olema hea ainult sellepärast
see, et lõpuks madalam neil oleks võrdne, ma arvan.
Aga kui nad on võrdsed, siis me poleks seda teinud samas silmus alustada
ja me lihtsalt oleks tagastatud väärtus. Nii et ma arvan, et me oleme head nüüd.
Pange tähele, et kuigi see probleem ei ole enam rekursiivne,
sama laadi ideid kohaldata, kui näeme, kuidas seda nii lihtsalt sobiv
et rekursiivne lahendus see, et me lihtsalt ajakohastamine indeksite ikka ja jälle,
teeme probleemi väiksemaks ja väiksemaks, me keskendudes alagrupis massiivi.
[Üliõpilane] Kui madal on 0 ja üles on 1, nad oleksid mõlemad 0 + 1/2, mis läheks 0,
ja siis üks oleks + 1, üks oleks - 1.
[Üliõpilane] Kuhu me kontrollida võrdõiguslikkuse?
Nagu siis, kui keskmisel on tegelikult nõela?
Me ei ole praegu seda teeb? Oh!
Kui see on -
Jah. Me ei saa lihtsalt teha katse siia alla, sest oletame, et esimene Lähis -
[Üliõpilane] See on tegelikult nagu ei visata seotud.
Nii et kui sa visata seotud, sa pead kontrollima seda esimesena või mis iganes.
Ah. Jah. >> [Üliõpilane] Jah.
Nii et nüüd oleme visata üks me praegu vaatasin,
mis tähendab, me peame nüüd ka
if (heinakuhjas [(madal + up) / 2] == nõel), siis saame tagasi true.
Ja kas ma panen mujale või lihtsalt kui, siis tähendab see sõna-sõnalt sama asi
kuna see oleks tagastatud tõsi.
Ma panen muidu kui, kuid see ei ole oluline.
>> Nii teine ​​kui see, siis see, ja see on ühine asi, mida ma teha
kus isegi kui see on nii, kui kõik on hea siin,
nagu madal saa kunagi olla suurem kui üleval, see ei ole väärt arutluskäik selle kohta, kas see on tõsi.
Nii et võite ka öelda, et kui madal on väiksem või võrdne
või kui madal on alla
nii et kui nad on kunagi võrdne või madal juhtub mööda üles,
siis saame murda läbi selle aasa.
Küsimused, mured, kommentaare?
Okei. See näeb hea välja.
Nüüd me tahame teha omamoodi.
Kui läheme minu teine ​​läbivaatamine, me näeme neid samu numbreid,
aga nüüd nad enam ei järjestatud järjekorras.
Ja me tahame ellu omamoodi kasutades algoritmi O n log n.
Nii et mis algoritmi sa arvad, et peaksime rakendama siin? >> [Üliõpilane] Merge omamoodi.
[Bowden] Jah. Merge sorteerida on O (n log n), nii see on, mida me teeme.
Ja probleem saab olema üsna sarnane,
kus see lihtsalt väärib rekursiivne lahendus.
Me võime ka tulla iteratiivne lahendus, kui me tahame,
kuid rekursioon on lihtsam siin ja me peaksime tegema rekursioon.
Ma arvan, et me kõnnime läbi ühendamise omamoodi esimene,
kuigi on armas video on märk omamoodi juba. [Naer]
Nii et ühendada omamoodi on - ma raiskan nii palju seda paberit.
Oh, seal on ainult üks vasakule.
Nii ühendada.
Oh, 1, 3, 5.
Okei.
Merge võtab kaks eraldi massiivid.
Eraldi nende kahe massiivid on nii järjestatud.
Nii et see massiiv, 1, 3, 5, järjestatud. See massiiv, 0, 2, 4, järjestatud.
Nüüd mida ühendamise peaks tegema, on ühendada need ühtsesse massiivi ise sorteerida.
Nii et me tahame massiivi suurus 6, mis läheb on need elemendid sees on
aastal sorteeritud järjekorras.
>> Ja nii saame ära kasutada asjaolu, et need kaks massiivid on järjestatud
teha seda lineaarset aega
lineaarse aja tähenduses, kui see massiiv on suurus x ja see on suurus y,
Seejärel kogu algoritm peaks olema O (x + y). Okei.
Nii ettepanekuid.
[Üliõpilane] Kas hakkame vasakult?
Nii saad panna 0 alla ja siis 1 ja siis siin sa oled 2.
Nii et see on selline nagu teil on kaart, mis liigub paremale. >> [Bowden] Jah.
Sest mõlemad massiivid kui me keskenduda ainult kõige vasakpoolsem element.
Kuna mõlemad massiivid on järjestatud, me teame, et need 2 elementi
on väikseim elemendid kas massiiv.
Nii et see tähendab, et 1 neist 2 elementi peab olema väikseim element meie ühinenud massiivi.
See lihtsalt nii juhtub, et väikseim on üks paremal seekord.
Nii et me võtame 0, sisesta see vasakul sest 0 on väiksem kui 1,
nii et võta 0, sisestage see meie esimesel kohal ja siis me uuendada seda
et nüüd keskenduda esimese osaga.
Ja nüüd me kordame.
Nii et nüüd me võrdleme 2 ja 1. 1 on väiksem, nii me lisada 1.
Me värskenduse see pointer juhtida selle kutiga.
Nüüd teeme uuesti, nii et 2. See uuendab, võrrelda neid 2, 3.
See uudiseid, siis 4 ja 5.
Nii et on ühendamisega.
>> See peaks olema üsna selge, et see on lineaarne aega, sest me lihtsalt minna üle iga element ühe korra.
Ja see on suurim samm rakendamisel ühendamise omamoodi teeb seda.
Ja see ei ole nii raske.
Paar asja muretsema, oletame, et me ühinevad 1, 2, 3, 4, 5, 6.
Sel juhul me sattuda olukorda, kus see saab olema väiksem,
siis me uuendada see pointer, see saab olema väiksem, ajakohastab seda,
see on väiksem, ja nüüd sa pead tunnistama
kui olete tegelikult otsa elemente võrrelda.
Kuna me oleme juba kasutanud seda kogu antennide massiivi,
kõik see massiiv on nüüd lihtsalt lisada siia.
Nii et kui me kunagi joosta, kus üks meie massiivid on täielikult segunenud juba,
siis me lihtsalt võtame kõik elemendid teiste massiivi ja lisada need lõpuks massiiv.
Nii saame lihtsalt sisestada 4, 5, 6. Okei.
See on üks asi, et olge.
Rakendamine, mis peaks olema 1. etapp.
Merge sortida siis põhineb sellel, et see on 2 sammu, 2 rumal samme.
Ütleme lihtsalt annan selle massiivi.
Nii et ühendada sorteerida, 1.etapp on rekursiivselt murda massiivi pooleks.
Nii et jagada seda massiivi pooleks.
Meil on nüüd 4, 15, 16, 50 ja 8, 23, 42, 108.
Ja nüüd teeme uuesti ja me jagada need pooleks.
Ma lihtsalt teen seda siinpool.
Nii et 4, 15 ja 16, 50.
Me teeks sama asi siin.
Ja nüüd me jagame pooleks uuesti.
Ja meil on 4, 15, 16, 50.
Nii et see on meie tugipunkt.
Kui massiivid on suurus 1, siis me lõpetame koos jagamine pooleks.
>> Nüüd, mida me teeme seda?
Me lõpuks see ka lagunenud 8, 23, 42 ja 108.
Nüüd, et me oleme selles punktis, nüüd samm kaks Tarkvaraprojekteerimise on lihtsalt ühinevad paari nimekirju.
Nii et me tahame ühendada need. Me lihtsalt helistada ühendada.
Me teame ühendamise naaseb need sorteeritakse järjekorras.
4, 15.
Nüüd tahame koondada need, ja et tagasi nimekirja omadega sorteeritud järjekorras
16, 50..
Me ühendada need - ma ei saa kirjutada - 8, 23 ja 42, 108.
Nii et meil on tekkinud paari korraga.
Nüüd me lihtsalt ühendada uuesti.
Pange tähele, et kõik need nimekirjad on sorteeritud iseenesest
ja siis saame lihtsalt ühendada need nimekirjad saada nimekirja suurus 4, mis on järjestatud
ja ühendada need kaks nimekirja, et saada nimekirja suurus 4, mis on järjestatud.
Ja lõpuks, me võime ühendada need kaks nimekirja suurus 4, et saada üks nimekiri suurus 8, mis on järjestatud.
Nii et näete, et see on üldine n log n, me juba nägime, et ühendamine on lineaarne,
nii et kui me tegeleme nende ühendamine, nii nagu üldkuludest ühendamise
Nende kahe nimekirja on vaid 2, sest -
Või noh, see on O n, kuid n siin on lihtsalt need 2 elementi, nii et see on 2.
Ja need 2 on 2 ja need 2 on 2 ja need 2 on 2,
nii üle kõik sulab, et me peame tegema, me lõpuks teeme n.
Nagu 2 + 2 + 2 + 2 on 8, mis on n
nii et kulud ühinevad selle komplekti on n.
Ja siis sama asi siin.
Me ühendada need 2, siis need 2, ja eraldi kõnealust ühendamist võtab neli operatsiooni,
kõnealust ühendamist võtab neli operatsiooni, kuid taas, vahel kõik need,
me lõpuks ühinevad n kokku asju, ja nii see toiming n.
Ja nii igal tasandil võtab n elementi liitmisega.
>> Ja kui palju tasanditel on olemas?
Igal tasandil meie massiivi kasvab suurus 2.
Siin meie massiivid on suurus 1, siin nad on suurus 2, siin nad on suurus 4,
ja lõpuks, nad on suurus 8.
Nii et kuna ta on kahekordne, seal saab olema kokku log n nendest tasanditest.
Nii log n taset, iga tase, võttes n kogu tegevus,
saame n log n algoritm.
Küsimused?
Kas inimesed on juba saavutanud edu kohta, kuidas rakendada seda?
Kas keegi juba riigis, kus ma saan lihtsalt tõmba oma koodi?
Võin anda minut.
See üks läheb kauem.
Ma väga soovitada kordu -
Sa ei pea tegema rekursiooni jaoks ühendamise
sest teha rekursiooni jaoks ühinevad, sa lähed on läbida hunnik erinevaid suurusi.
Sa saad, aga see on tüütu.
Aga rekursiooni jaoks omamoodi ise on üsna lihtne.
Sa lihtsalt sõna otseses mõttes helistada omamoodi vasakul pool, sorteerida paremal pool. Okei.
Igaüks on midagi ma ei tõmba veel?
Või muidu ma annan minut.
Okei.
Igaüks on midagi, mida me saame töötada koos?
Või muidu me lihtsalt töötada selle ja seejärel laiendage sealt.
>> Igaüks on rohkem kui see, et ma ei tõmba?
[Üliõpilane] Jah. Võite tõmba minu. >> Olgu.
Jah!
[Üliõpilane] Oli palju tingimusi. >> Oh, tulistada. Kas sa -
[Üliõpilane] Ma pean salvestage see. >> Jah.
Nii et me tegime seda ühendamise eraldi.
Oh, aga see ei ole nii halb.
Okei.
Nii et omamoodi on ise lihtsalt helistades mergeSortHelp.
Selgitage meile, mida mergeSortHelp teeb.
[Üliõpilane] MergeSortHelp päris palju maksab kaks peamist etappi,
mis on sorteerida iga poole massiiv ja seejärel ühendada mõlemad.
[Bowden] Okei, nii et andke mulle teine.
Ma arvan, et see - >> [üliõpilane] mul on vaja -
Jah. Ma olen midagi puudu.
Aastal ühinevad, ma mõistan, et mul on vaja luua uus massiiv
sest ma ei suutnud seda teha paigas. >> Jah. Sa ei saa. Õige.
[Üliõpilane] Nii saan luua uue massiivi.
Ma unustasin lõpus ühendada uuesti muuta.
Okei. Me vajame uut massiivi.
Aastal ühendamise omamoodi, see on peaaegu alati tõsi.
Osa kuludest parem algoritm ajaliselt
on peaaegu alati vaja kasutada natuke rohkem mälu.
Nii et siin, ükskõik kuidas sa seda ühendada sorteerida,
sa paratamatult vaja kasutada mõned ekstra mälu.
Ta lõi uue massiivi.
Ja siis lõpus öelda, me lihtsalt vaja kopeerida uue massiivi algsesse massiivi.
[Üliõpilane] Ma arvan küll, jah.
Ma ei tea, kas see töötab nii lugedes viitega või mis iganes -
Jah, see töötab. >> [Üliõpilane] Okei.
Kas sa proovisid töötab see? >> [Üliõpilane] Ei, veel mitte. >> Okei.
Proovige käivitada see ja siis räägin seda teist.
[Üliõpilane] mul on vaja, et kõik funktsiooni prototüüpe ja kõik, eks?
Funktsiooni prototüüpe. Oh, sa mõtled nagu - Jah.
Sorteeri helistatakse mergeSortHelp.
>> Nii et omamoodi helistada mergeSortHelp, mergeSortHelp peavad kas on määratletud
enne sorteeri või me lihtsalt vaja prototüüp. Lihtsalt kopeeri ja kleebi see.
Ja samamoodi, mergeSortHelp helistatakse ühinevad,
kuid ühendamise ei ole veel kindlaks määratud, et saaksime lihtsalt lasta mergeSortHelp tea
et see, mida ühendada saab välja nägema, ja nii ongi.
Nii mergeSortHelp.
Meil on küsimus siin, kus meil ei ole tugipunkti.
MergeSortHelp on rekursiivne, nii et kõik rekursiivne funktsioon
läheb vaja mingi tugipunkti teada, millal lõpetada rekursiivselt kutsutakse ise.
Mis on meie tugipunkt saab olema siin? Jah.
[Üliõpilane] Kui suurus on 1? >> [Bowden] Jah.
Nii nagu me nägime seal, me lõpetasime jagamine massiivid
kui me sattus massiive suurus 1, mis paratamatult on järjestatud ise.
Nii et kui suurus võrdub 1, me teame massiiv on juba sorteeritud,
nii et me saame lihtsalt tagasi.
>> Pange tähele, et on tühine, nii et me ei tule midagi erilist, me lihtsalt tagasi.
Okei. Nii et meie tugipunkt.
Ma arvan, et meie baasi Võib ka juhtuda, kui me juhtumisi ühinevad massiivi suurus 0,
me ilmselt tahad lõpetada mingil hetkel,
nii et me võiks lihtsalt öelda suurus väiksem kui 2 või väiksem või võrdne 1
nii et see töötab iga massiivi nüüd.
Okei.
Nii et meie tugipunkt.
Nüüd sa tahad kõndida meid ühendada?
Mida kõik need juhtumid tähendab?
Siin üleval, me teeme lihtsalt sama mõte, -
[Üliõpilane] Ma pean mööda sõitma suurus kõik mergeSortHelp kõned.
Lisasin suurus täiendava esmane ja see ei ole seal, nagu suurus / 2.
[Bowden] Oh, suurus / 2, suurus / 2. >> [Üliõpilane] Jah, ja ka eespool funktsioon samuti.
[Bowden] Siin? >> [Üliõpilane] Lihtsalt suurus. >> [Bowden] Oh. Suurus, suurus? >> [Üliõpilane] Jah.
[Bowden] Okei.
Las ma mõtlen teist.
Kas me joosta küsimus?
Me oleme alati ravivad vasakule kui 0. >> [Üliõpilane] nr
See on vale ka. Vabandust. See peaks olema algus. Jah.
[Bowden] Okei. Mulle meeldib, et parem.
Ja lõpuks. Okei.
Nii et nüüd sa tahad kõndida meid ühendada? >> [Üliõpilane] Okei.
Ma lihtsalt jalgsi läbi uue massiivi Olen loonud.
Selle suurus on suurus osa massiiv, et me tahame välja sorteerida
ja püüab leida element, mis ma peaks tegema uue massiivi samm.
Nii et mida teha, et esiteks Ma kontrollin, kas vasakul pool massiiv on jätkuvalt enam elemente,
ja kui seda ei juhtu, siis minna, et teine ​​tingimus, mis lihtsalt ütleb
okei, see peab olema õiges massiiv, ja me paneme, et praeguses indeks newArray.
>> Ja siis muidu, ma kontrollin, kas paremal pool massiiv on samuti lõpetatud,
sel juhul ma lihtsalt panna vasakule.
See ei pruugi tegelikult olla vajalik. Ma pole kindel.
Aga ikkagi, aga teised kaks kontroll kumb on väiksema vasakule või paremale.
Ja ka iga kord, ma incrementing kumb kohatäide ma juurdekasvu.
[Bowden] Okei.
See näeb hea välja.
Kas kellelgi on kommentaare või muresid või küsimusi?
Nii et neli juhtumit, et me peame tooma asjad lihtsalt on - või tundub 5 -
kuid me peame kaaluma, kas vasakul massiiv on otsa asjad peame ühinema,
kas õigus massiiv on otsa asjad peame ühendada -
Ma osutavad midagi.
Nii et kas vasakul massiiv on otsa asjad või paremale massiiv on otsa asjad.
Need on kaks juhtumit.
Samuti peame triviaalne puhul kas vasakule asi on väiksem kui õige asi.
Siis tahame valida vasakul asi.
Need on juhtumid.
Nii et see oli õige, et see on.
Array jäänud. See on 1, 2, 3. Okei. Nii et jah, need on neli asju, mida me võiksite teha.
Ja me ei lähe üle iteratiivne lahendus.
Ma ei soovitaks -
Merge omamoodi on näide funktsioon, mis on nii mitte saba rekursiivne,
see ei ole kerge teha seda saba rekursiivne,
kuid ka see ei ole väga lihtne teha seda iteratiivne.
See on väga lihtne.
See rakendamist ühendamise sortida,
ühendada, ükskõik mida sa teed, sa lähed ehitada ühendamisega.
>> Nii et ühendada omamoodi ehitatud peal ühendamise rekursiivselt on vaid need kolm rida.
Iteratiivselt, see on rohkem tüütu ja raske mõelda.
Aga teate, et see ei ole saba rekursiivne alates mergeSortHelp - kui ta nimetab ennast -
see vajab veel teha asju pärast seda rekursiivne kõne tulu.
Nii et see freimi peab püsima isegi pärast nõuab see.
Ja siis kui te nimetate seda, freimi peab püsima
sest isegi pärast seda kõnet, peame siiski ühendada.
Ja see on mittetriviaalsed teha seda saba rekursiivne.
Küsimused?
Hea küll.
Nii läheb tagasi sortida - oh, seal on kaks asja, ma tahan näidata. Okei.
Tulles tagasi sorteerida, me teeme seda kiiresti.
Või leidke. Sorteeri? Sordi. Jah.
Tulles tagasi alguse omamoodi.
Me tahame luua algoritm, mis sorteerib massiivi kasutades algoritmi
O n.
Niisiis, kuidas on see võimalik? Kas kellelgi on mingit -
Ma vihjanud enne kell -
Kui me parasjagu paranema n log n-O n,
oleme parem meie algoritm aeg-tark,
mis tähendab, mida me kavatseme vaja teha, et korvata seda?
[Üliõpilane] Space. >> Jah. Me ei kavatse kasutama rohkem ruumi.
Ja isegi mitte lihtsalt rohkem ruumi, see on hüppeliselt rohkem ruumi.
Nii et ma arvan seda tüüpi algoritm on pseudo midagi, pseudo polünoom -
pseudo - ma ei mäleta. Pseudo midagi.
Aga sellepärast, et me peame kasutama nii palju ruumi
et see on saavutatav, kuid mitte realistlik.
>> Ja kuidas me seda saavutada?
Me suudame seda saavutada, kui me garanteerida ühegi element massiivi
on alla teatud suurust.
Nii et ütleme lihtsalt, et suurus on 200,
tahes osa massiiv on allpool suurus 200.
Ja see on tegelikult väga realistlik.
Te saate väga lihtsalt on massiiv, et sa tead kõike seda
saab olema väiksem kui mõned number.
Nagu kui teil on mõned täiesti massiivne vektor või midagi
kuid sa tead kõike saab olema vahemikus 0 kuni 5,
siis see saab olema tunduvalt kiiremini seda teha.
Ja seotud mis tahes elemente on 5,
nii see seotud, et kui palju mälu sa kavatsed kasutada.
Nii köidetud on 200.
Teoreetiliselt on alati seotud kuna täisarv võib olla ainult kuni 4 miljardit,
aga see on ebareaalne, sest siis me tahaks olla kasutades ruumi
tellimisel 4 miljardit eurot. Nii et on ebareaalne.
Aga siin me ütleme meie köidetud on 200.
Trikk teeb seda O n teeme teise massiivi nimega loeb suurus seotud.
Nii et tegelikult on see otsetee - ma tegelikult ei tea, kas rõkkama teeb seda.
Aga GCC vähemalt - Ma eeldades rõkkama see liiga -
see lihtsalt initsialiseerida kogu massiiv olla 0..
Nii et kui ma ei taha seda teha, siis ma võiks eraldi teha jaoks (int i = 0;
i <siduv; i + +) ja loeb [i] = 0;
Nii et nüüd on kõik käivitub kuni 0.
Ma itereerime minu massiiv,
ja mida ma teen on ma loendades iga - lähme alla siit.
Meil on 4, 15, 16, 50, 8, 23, 42, 108.
Mida ma loendan on sündmuste arv kõikidel osadel.
Olgem tegelikult lisada veel paar siin mõned kordub.
Nii et raha on meil siin, väärtus, mis saab olema massiiv [i].
Nii Val võiks olla 4 või 8 või mis iganes.
Ja nüüd ma loen, kui palju selle väärtus Olen näinud,
nii loeb [Val] + +;
Kui see on tehtud, loeb läheb otsima midagi 0001.
Teeme loeb [Val] - JÄRGIMA + 1.
>> Nüüd ongi lihtsalt arvestada asjaolu, et me alates 0.
Nii et kui 200 saab olema meie suurim arv,
siis 0-200 on 201 asja.
Nii loeb, see näeb välja nagu 00001, sest meil on üks 4.
Siis me peame 0001, kus me peame 1 8. indeks loota.
Me peame 2 23. indeksi arvu.
Me peame 2 42. indeksi arvu.
Nii saame kasutada loota.
Nii num_of_item = loeb [i].
Ja nii kui num_of_item on 2, mis tähendab, et me tahame lisada 2 numbrit i
meie järjestatud massiivist.
Seega on meil vaja jälgida, kui kaugele oleme arvesse massiivi.
Nii index = 0.
Array - ma lihtsalt kirjutan selle.
Loeb -
massiiv [index + +] = i;
Kas see, mida ma tahan? Ma arvan, et see, mida ma tahan.
Jah, see näeb hea välja. Okei.
Nii ei igaüks aru, mida eesmärgil minu loeb massiiv on?
On loendades esinemistest kõik need numbrid.
Siis ma itereerimise üle, mis loeb massiivi
ja-nda positsiooni loeb massiivi
on mitmeid i on, et peaks ilmuma minu sorteeritud massiiv.
Sellepärast loeb 4 saab olema 1
ja loeb 8 saab olema 1, loeb 23. saab olema 2.
Nii see on, kuidas paljud neist Tahan lisada oma sorteeritud massiiv.
Siis ma lihtsalt teha.
Olen sisestamist num_of_item i on minu sorteeritud massiiv.
>> Küsimused?
Ja nii jälle, see on lineaarne aega, sest me lihtsalt itereerimise üle seekord,
aga see on ka lineaarne mida see number juhtub olema,
ja nii see suuresti sõltub sellest, mida teie seotud on.
Mis köidetud 200, see pole nii hull.
Kui oma köidetud saab olema 10000, siis see on natuke hullem,
aga kui oma köidetud saab olema 4 miljardit, mis on täiesti ebareaalne
ja see massiiv läheb pea olema suurus 4 miljardit eurot, mis on ebareaalne.
Nii et see on. Küsimused?
[Kuuldamatu õpilase vastus] >> Okei.
Ma sain aru, üks teine ​​asi, kui me läksime mööda.
Ma arvan, et probleem oli Lucase ja ilmselt iga üks oleme näinud.
Ma täitsa unustasin.
Ainuke asi, ma tahtsin kommenteerida, et kui olete tegelevad asju nagu indeksite,
sa kunagi näha seda, kui olete kirjalikult jaoks silmus,
kuid tehniliselt, kui olete tegelevad need indeksid,
siis peaks päris palju alati käsitleda allkirjastamata täisarvud.
Selle põhjuseks on see, kui olete tegelevad allkirjastatud täisarvud,
nii et kui sul on 2 logis täisarvud ja sa lisage need koos
ja nad lõpuks liiga suur, siis sa lõpuks koos negatiivse numbriga.
Nii see on, mida Integer overflow on.
>> Kui ma lisan 2 miljardit ja 1 miljard ma lõpuks negatiivne 1 miljard eurot.
Nii täisarvud tööd arvutitega.
Nii et probleem kasutades -
See on hea, välja arvatud juhul, kui madal juhtub olema 2 miljardit ja kuni juhtub olema 1 miljard
siis see saab olema negatiivne 1000000000 ja siis me hakkame jagama, et 2
ja lõpuks negatiivne 500 miljonit eurot.
Nii et see on ainult küsimus, kui teil juhtub olema otsivad läbi massiivi
miljardeid asju.
Aga kui madal + kuni juhtub ülevoolu, siis see on probleem.
Niipea kui me need allkirjastamata, siis 2 miljardit pluss 1 miljard 3000000000.
3000000000 jagatud 2 on 1,5 miljardit eurot.
Nii et niipea kui nad on allkirjastamata, kõik on täiuslik.
Ja nii see on ka küsimus, kui olete kirjalikult oma jaoks silmuseid,
ja tegelikult, siis ilmselt teeb seda automaatselt.
See tegelikult lihtsalt karjuda sulle.
Nii et kui see arv on liiga suur, et olla lihtsalt täisarv, kuid see sobiks allkirjastamata täisarv,
see ütleb teile, nii et miks sa kunagi tekib küsimus.
Te näete, et indeks on kunagi saab olema negatiivne,
ja nii kui sa itereerimise üle massiiv,
saate peaaegu alati öelda allkirjastamata int i, kuid sa tõesti ei pea.
Asjad lähevad tööle päris palju sama hästi.
Okei. [Sosistab] Mis kell on?
Viimane asi, mida ma tahtsin näidata - ja ma just seda teha väga kiiresti.
Sa tead, kuidas oleme # define et saaksime # define MAX kui 5 või midagi?
Ärme teeme MAX. # Define tema kui 200-le. See, mida me tegime enne.
See määratleb konstant, mis on lihtsalt läheb kopeerida ja kleepida
kus iganes me juhtumisi kirjutan seotud.
>> Nii saame tegelikult teha rohkem # määratleb.
Saame # define funktsioone.
Nad pole tõesti toimib, kuid me kutsume neid funktsioone.
Näiteks oleks midagi MAX (x, y) on defineeritud kui (x <y? Y: x). Okei.
Nii et sa peaksid harjuma kolmekomponentsete operaator süntaks,
kuid on x vähem kui y? Tagasi y, teine ​​tagasi x.
Nii et näete, saate teha seda eraldi funktsioon,
ja funktsioon võiks olla nagu bool MAX kestab 2 argumente, tagastab.
See on üks enim levinud näen teinud niimoodi. Me nimetame neid makrosid.
See on makro.
See on lihtsalt süntaks ta.
Võite kirjutada makro teha mida iganes sa tahad.
Sa sageli näha makrosid silumiseks printfs ja värki.
Nii tüüpi printf on olemas spetsiaalsed konstandid C nagu rõhutavad LINE rõhutada,
2 rõhutatakse LINE rõhutada,
ja seal on ka minu arvates 2 rõhutatakse FUNC. See võib olla see. Midagi sellist.
Need asjad tuleb asendada funktsiooni nimi
või mitu liini, mis sa oled.
Sageli kirjutad silumine printfs et siin all ma võiksin siis lihtsalt kirjutada
Debug ja see print line number ja funktsioon, et ma juhtun olema
et tal tekkisid selle DEBUG avalduse.
Ja saate printida ka muid asju.
Nii et üks asi, mida sa peaksid olge on, kui ma juhtun # define DOUBLE_MAX
kui midagi 2 * y ja 2 * x.
Nii et mingil põhjusel juhtub, et teha palju.
Nii et see makro.
See on tegelikult katki.
Ma nimetaksin seda tehes midagi DOUBLE_MAX (3, 6).
Mida tuleks tagasi?
[Üliõpilane] 12.
Jah, 12 tuleb tagasi, ja 12 tagastatud.
3 saab asendada x, 6 saab asendada y, ja me läheme tagasi 2 * 6, mis on 12.
Nüüd mis sellest? Mida tuleks tagasi?
[Üliõpilane] 14. >> Ideaalis, 14.
Küsimus on, et kuidas hash määratleb töö, pidage meeles see on sõnasõnaline kopeeri ja kleebi
ja päris palju kõike, mis siis, et see saab tõlgendada
on 3 alla 1 pluss 6, 2 korda 1 pluss 6, 2 korda 3.
>> Nii et sel põhjusel sa peaaegu alati wrap kõike sulgudes.
Iga muutuja sa peaaegu alati wrap sulgudes.
On juhtumeid, kus sa ei pea, nagu ma tean, et ma ei pea seda tegema siin
sest vähem kui on päris palju alati lihtsalt läheb tööle,
kuigi see ei pruugi isegi olla tõsi.
Kui midagi on naeruväärne nagu DOUBLE_MAX (1 == 2)
siis see on hakka asendatakse 3 vähem kui 1 võrdub võrdub 2,
ja nii siis see läheb teha 3 alla 1, siis kas see võrdub 2,
mis pole see, mida me tahame.
Nii et vältida operaatori tähtsam probleeme,
alati wrap sulgudes.
Okei. Ja ongi kõik, 5:30.
Kui teil on küsimusi pset, andke meile teada.
See peaks olema lõbus, ja häkker väljaanne ka on palju realistlikum
kui häkker väljaanne eelmise aasta, seega loodame, et palju teil seda proovida.
Eelmisel aastal oli väga suur.
>> [CS50.TV]