[Powered by Google Translate] [3. szakasz - További Kényelmes]
[Rob Bowden - Harvard University]
>> [Ez CS50. - CS50.TV]
>> Tehát az első kérdés furcsán hangzik.
GDB lehetővé teszi, hogy "debug" egy program, de konkrétan mit jelent ez engedi csinálni?
Fogok válaszolni, hogy az egyik, és nem tudom, hogy mi pontosan az várható volt,
úgyhogy azt hiszem, hogy valami mentén ez lehetővé teszi, lépésről lépésre
séta a program, kölcsönhatásba vele, váltással változók, tegyenek meg mindent ezek a dolgok -
Alapvetően teljesen ellenőrzése a program végrehajtásának
és vizsgáljuk meg egy adott részét a program végrehajtása.
Tehát ezek a jellemzők teszik hibakeresés dolgokat.
Oké.
Miért bináris keresés előírják, hogy a tömb kell válogatni?
Ki akar válaszolni?
[Hallgató] Mert ez nem működik, ha nincs rendezve. >> Igen. [Nevetés]
Ha ez nem válogatták szét, akkor lehetetlen osztott ketté
és tudom, hogy mindent a bal kevésbé, és mindent a megfelelő
nagyobb, mint a középső érték.
Tehát meg kell rendezni.
Oké.
Miért van buborék egyfajta O n négyzetes?
Valaki 1. akar adni egy nagyon gyors, magas szintű áttekintést, hogy mi buborék rendezés?
[Hallgató] Ön alapvetően végig minden elem, és ellenőrizze az első néhány elemet.
Ha ők ki hol cserélni őket, akkor ellenőrizze a következő néhány elemet, és így tovább.
Amikor eléred a végén, akkor tudja, hogy a legnagyobb elem kerül a végén,
így figyelmen kívül hagyja, hogy az egyik, akkor tovább megy keresztül,
és minden egyes alkalommal meg kell ellenőrizni eggyel kevesebb elemet mindaddig, amíg nem történik változás. >> Igen.
Úgy hívják bubble sort, mert ha megfordítja a tömb az oldalán, így ez felfelé és lefelé, függőleges,
majd a nagy értékek aljára és a kis értékek buborék fel a csúcsra.
Így kapta a nevét.
És igen, csak megy keresztül.
Folyton megy keresztül a tömb, csere a nagyobb érték
hogy a legnagyobb értékeket az alján.
>> Miért van az O n négyzetes?
Először is, nem akárki azt akarom mondani, miért O n négyzetes?
[Hallgató] Mert minden futam megy n-szer.
Csak akkor lehetünk benne, hogy már megtette a legnagyobb elem egészen,
akkor meg kell ismételni, hogy minél több elemet. >> Igen.
Tehát ne feledje, milyen nagy O jelent, és milyen nagy Omega jelent.
A nagy O olyan, mint a felső korlát milyen lassan tud ténylegesen futni.
Tehát azzal, hogy a O n négyzetes, nem O n különben nem lenne képes futtatni
lineáris időben, de O n-CubeD
mert határolja O n-kocka.
Ha ez által határolt O n négyzetes, akkor ez által is határolt n kocka.
Így, ha n szögletes, és az abszolút legrosszabb esetben meg jobban, mint n négyzetnagyságrendű,
ezért ez O n négyzeten.
Tehát, ha csekély matematikai, hogyan jön ki, hogy n négyzetes,
ha van öt dolog, ami a mi listán, az első alkalom, hogy hány swap lehetne esetleg kell tenni
annak érdekében, hogy ezt? Nézzük valójában csak -
Hány swap fogunk van, hogy az első távon a buborék sort a tömb?
[Hallgató] n - 1. >> Igen.
>> Ha van 5 elem, mi lesz szükség, hogy n - 1.
Aztán a másik, hogy hány swap fogunk van, hogy?
[Hallgató] n - 2. >> Igen.
És a harmadik lesz n - 3, majd az egyszerűség kedvéért fogom írni az elmúlt két
ahogy akkor lesz szükségünk, hogy a 2 és 1 swap swap.
Azt hiszem, az utolsó lehet, hogy valójában nem kell, hogy megtörténjen.
Ez a csere? Nem tudom.
Tehát ezek teljes összege swap vagy legalább összehasonlításokat meg kell tenni.
Még ha nem csere, akkor is kell összehasonlítani az értékeket.
Tehát vannak n - 1 összehasonlítás az első távon a tömb.
Ha rendezni ezeket a dolgokat, hadd valójában, hogy azt hat a dolgok így a dolgok verem szépen,
majd én megteszem 3, 2, 1.
Szóval csak átrendezése ezen összegek, szeretnénk látni, hogy hány összehasonlítást teszünk
az egész algoritmus.
Tehát ha ezek a srácok, hogy itt lenn,
akkor még mindig csak összefoglalva azonban sok összehasonlítás volt.
De ha összeadjuk ezeket, és összeadjuk ezeket és összeadjuk ezeket,
ez még mindig ugyanaz a probléma. Csak Összefoglalva e bizonyos csoportok.
>> Szóval most mi összeadásával 3 n években. Ez nem csak a 3 n.
Ez mindig lesz n / 2 n években.
Tehát itt történik, hogy 6.
Ha lenne 10 dolog, akkor is ezt a csoportosítást 5 különböző pár dolog
és a végén az n + n + n + n + n.
Szóval mindig lesz, hogy n / 2 n-k, és így ez a mi jot ki, hogy n négyzetes / 2.
És annak ellenére, hogy ez a tényező a fele, ami történik, hogy jöjjön
mert az a tény, hogy az átmenő minden iterációs felett a tömb, amit összehasonlításba 1 kevésbé
annak érdekében, hogy ez hogyan kap a több mint 2, de ez még mindig n faragva.
Nem érdekel az állandó tényező fél.
Szóval egy csomó nagy O dolgok, mint ez támaszkodik csak egyfajta ezt a fajta matematika,
Ennek összegek számtani és mértani sorozat stuff,
de a legtöbbjük a tanfolyam elég egyértelmű.
Oké.
Miért van beszúrási sort az Omega n? Mit jelent omega jelent?
[Két diák beszél egyszerre - érthetetlen] >> Igen.
Omega lehet gondolni, mint az alsó korlát.
>> Tehát nem számít, mennyire hatékony a beszúrási sort algoritmus,
függetlenül attól, hogy a lista, ami telt el, azt mindig meg összehasonlítandó legalább n dolgokat
vagy nem iterációkhoz n dolgokat.
Miért van ez?
[Hallgató] Mert ha a lista már rendezve, akkor az első iterációs
csak akkor tudjuk garantálni, hogy az első elem a sorban,
és a második iteráció csak akkor lehet garantálni az első kettő
azért, mert nem tudja, hogy a többi lista rendezésre. >> Igen.
Ha át egy teljesen rendezett lista legalább van, hogy menjen át az összes elemet
látni, hogy semmit sem kell mozgatni.
Így halad át a listát, és azt mondja jaj, ezt már rendezve,
lehetetlen, hogy tudja, ez rendezve amíg be nem minden elem
látni, hogy vannak rendezve sorrendben.
Tehát az alsó korlát elhelyezésének rendezés Omega n.
Mi a legrosszabb futási ideje merge sort,
legrosszabb esetben pedig nagy O megint?
Így a legrosszabb forgatókönyv esetén hogyan merge sort futni?
[Hallgató] N log n. >> Igen.
A leggyorsabb általános rendezési algoritmusok n log n. Nem lehet jobban csinálni.
>> Vannak speciális esetek, és ha van ideje ma - de mi talán won't -
láttuk az egyik, hogy nem jobb, mint az n log n.
De általános esetben, akkor nem jobb, mint n log n.
És merge sort történik, hogy az, amit tudnia kell, erre a tanfolyamra, ami n log n.
És így fogunk ténylegesen végrehajtó ma.
És végül, az nem több, mint három mondatban, hogyan működik kiválasztási rendezési munkát?
Vajon valaki akar válaszolni, és én számold össze a mondatok
mert ha megy át 3 -
Tudja valaki emlékszik kiválasztás sort?
Selection sort általában elég könnyű emlékezni, csak a nevét.
Csak iterációkhoz a tömb, megtalálja, amit a legnagyobb érték vagy a legkisebb -
bármilyen sorrendben, amit válogatás be
Tehát mondjuk mi válogatás a legkisebbtől a legnagyobb.
Te iterációkhoz a tömb, keresve függetlenül minimum elem,
válassza ki, és aztán csak csere azt bármi is van az első helyen.
És aztán a második lépésben az array, keresse meg a minimális elem újra,
jelölje ki, majd cserélni azt, hogy mi van a második pozíciót.
Tehát csak a szedés és kiválasztja a minimális értékek
, és helyezze azokat az első a tömb, amíg van rendezve.
Kérdések az?
>> Ezek elkerülhetetlenül megjelennek a formában van, hogy töltse ki, amikor benyújtásakor Pset.
Ezek alapvetően a választ e.
Oké, szóval most már kódolás problémákat.
Már küldött e-mailben - Nem valaki nem kap, hogy az e-mailt? Oké.
Már küldött e-mailben a teret, hogy mi fogunk használni,
és ha rákattint a nevem - úgyhogy azt hiszem, leszek az alján
mert a visszafelé r - de ha rákattint a nevemet látni fogod, 2 javítások.
Felülvizsgálat 1 lesz már a vágólapra másolni a kódot Spaces
a keresési dolgot fogsz végre kell hajtania.
És Revision 2 lesz az a fajta dolog, hogy mi végre után.
Szóval, akkor kattintson a Revision 1-es és az innen való munka.
És most szeretnénk végrehajtani a bináris keresés.
>> Akar valaki csak adni pszeudokód magas szintű magyarázat
hogy mit fogunk tenni, hogy a keresés? Igen.
[Hallgató] Csak vegye a közepén, a tömb, és nézd meg, hogy mit keres
kevesebb, mint a, vagy annál több.
És ha ez kevesebb, akkor menj a felét, ami kevesebb,
és ha ez több, akkor menj a felére több, és megismétlem, hogy amíg csak kap egy dolog.
[Bowden] Igen.
Figyeljük meg, hogy a mi számok tömb már rendezett,
és így ez azt jelenti, hogy mi is kihasználni ezt, és tudtunk először ellenőrizze,
oké, én keresem a számot 50.
Így tudok menni a középső.
Közel nehéz meghatározni, ha ez még számos dolgot,
de mondjuk mi mindig csonkolja a közepén.
Tehát itt van 8 dolog, így a középső lenne 16.
Ezt keresem: 50, így 50-16-nál nagyobb.
Szóval most alapvetően kezelni a tömb mivel ezek az elemek.
Tudok dobni mindent, 16-tól vége.
Most a tömb csak a 4 elem, és ismételje meg.
Így aztán szeretné megtalálni a középső újra, ami lesz 42.
42 kevesebb, mint 50, így tudok dobni ezt a két elemet.
Ez az én maradék tömb.
Meg fogom találni a középső újra.
Azt hiszem, 50 volt egy rossz példa, mert én mindig eldobni a dolgokat a baloldalt,
de ugyanaz az intézkedés, ha én keresek valamit
és ez kevesebb, mint az elem Én jelenleg vizsgálja,
akkor fogom eldobni mindent jobbra.
Tehát most kell végrehajtani, hogy a.
Figyeljük meg, hogy át kell adni a méret.
Azt is nem kell a kemény-kód méret.
Tehát, ha megszabadulni a # define -
Oké.
Hogyan lehet szépen kitalálni, hogy mi a méret a számok tömb jelenleg?
>> Hány eleme van a számok tömb?
[Hallgató] Számok, konzolok,. Hossz?
[Bowden] Ez nem létezik C.
Szüksége. Hossza.
Tömbök nincs tulajdonságai így nincs length tulajdonság tömbök
hogy majd csak Önnek azonban sokáig ez történik lennie.
[Hallgató] Lásd mennyi memória van, és osszuk el, hogy mennyi - >> Igen.
Szóval, hogyan lehet látni, hogy mennyi memória van? >> [Hallgató] sizeof. >> Ja, sizeof.
Sizeof az üzemeltető, hogy fogja vissza a méret a számok tömb.
És ez lesz azonban sok egész szám van akkora értéke
mivel ez mennyi memóriát ez ténylegesen munkába.
Tehát, ha azt akarom, hogy néhány dolog a tömbben,
akkor megyek ketté akarja osztani a méret egy egész szám.
Oké. Annak érdekében, hogy lehetővé teszi számomra át méretben itt.
Miért kell átadni a méret egyáltalán?
Miért nem tudok csak tedd fel ide int size = sizeof (szénakazalban) / sizeof (int)?
Miért ez nem működik?
[Hallgató] Ez nem egy globális változót.
[Bowden] Haystack létezik, és mi halad számok szénaboglya,
és ez egyfajta előrevetítette, hogy mi jön. Igen.
[Hallgató] Haystack csak az arra való utalás, így visszatér, hogy milyen nagy ez az utalás.
Igen.
Kétlem, előadás, hogy már látták a stack igazából még, ugye?
Már most beszélt róla.
Tehát a verem, ahol az összes változót fognak tárolni.
>> Bármely memória van kiutalt lokális változók megy a stack,
és minden funkciót kap saját helyet a stack, saját verem keret mi a neve.
Tehát fő megvan a maga stack frame, és a benne lévő fog létezni e számok tömb,
és ez lesz a mérete sizeof (szám).
Ez megy, hogy a számok mérete osztva méretű elemek,
de ez az összes életét tartozó fontosabb a stack frame.
Mikor hívjuk keresés keressen kap saját stack frame,
saját hely tárolni az összes helyi változók.
De ezek az érvek - így szénakazalban nem másolatot a teljes tömb.
Mi nem adja át az egész tömb egy példányt a keresést.
Csak halad hivatkozást, hogy a tömb.
Így search érhetik ezeket a számokat ezen keresztül referencia.
Ez még mindig a dolgokat, hogy él benne a fő a stack frame,
de alapvetően, ha eljutunk mutató, amely minden bizonnyal hamarosan,
ez az, amit pointerek vannak.
Mutatók csak hivatkozásokat a dolgokat, és tudod használni mutatókat elérni dolgokat
, amelyek más dolgok "stack kereteket.
Így, bár a számok helyi fő, akkor is elérheti keresztül ez a mutató.
De mivel ez csak egy mutató, és ez csak egy referencia,
sizeof (szénakazalban) éppen visszatérjen a méret a referencia is.
Nem tér vissza a mérete a dolog, ez mutat.
Nem tér vissza a tényleges mérete a számok.
És így ez nem fog működni, ahogy jónak látja.
>> Kérdések az?
Mutatók fognak tűnni a jelentősen több véres részletesebben az elkövetkezendő hetek során.
És ez az, amiért egy csomó dolog, amit látsz, a legtöbb keresési dolgokat, vagy rendezni a dolgokat,
ők szinte minden lesz szüksége, hogy a tényleges mérete a tömb,
mert a C, fogalmunk sincs, hogy mi a mérete a tömb.
Manuálisan kell átadni be!
És nem lehet manuálisan át az egész tömb, mert te csak halad a referencia
és nem kap a méretét a referencia.
Oké.
Tehát most azt akarjuk, hogy végre mi is magyarázta előtt.
Lehet dolgozni rajta egy kicsit,
és akkor nem kell aggódnia, mindent tökéletesen 100%-os dolgozik.
Csak írd fel a fele pszeudokód, hogy hogyan gondolja, hogy működnie kell.
Oké.
Nem kell teljesen kész ezzel még.
De nem mindenki érzi, kényelmes, amit eddig,
mintha tudunk dolgozni együtt?
Akar valaki önkéntes? Vagy véletlenszerűen felvenni.
Nem kell, hogy jobbra minden olyan intézkedés, hanem valami, amit lehet módosítani egy működő állapotba.
[Hallgató] Persze. >> Oké.
Szóval lehet menteni a felülvizsgálat kattintva a kis Mentés ikonra.
Igazad Ramya, ugye? >> [Hallgató] Igen. >> [Bowden] Oké.
Szóval most megtekintheti felülvizsgálata és mindenki húzza fel a felülvizsgálatot.
És itt van - Oké.
Így Ramya elment a rekurzív megoldás, ami mindenképpen érvényes megoldás.
Kétféle módon lehet ezt a problémát.
Akkor sem csinálni iteratív vagy rekurzív.
A legtöbb probléma a találkozás, hogy lehet tenni rekurzívan is elvégezhető iterációval.
Tehát itt megcsináltuk rekurzívan.
>> Vajon valaki akarja meghatározni, hogy mit jelent, hogy egy függvény rekurzív?
[Hallgató] Ha van egy függvényhívás maga
majd hívja magát, amíg ki nem jön a valódi és igaz. >> Igen.
A rekurzív függvény csak olyan funkció, amely saját magát hívja meg.
Van három nagy dolog, hogy egy rekurzív függvény kell.
Az első természetesen, ez nevezi magát.
A második az alapeset.
Tehát egy bizonyos ponton a funkciót le kell állítania a nevezte magát,
és ez az, amit az alap ügyben a.
Tehát itt tudjuk, hogy le kell állítani, meg kell adja fel a keresést
amikor a kezdő értéke end - és akkor megy át, hogy ez mit jelent.
De végül, az utolsó dolog, ami fontos a rekurzív funkciók:
a funkciókat kell valahogy megközelíteni az alapeset.
Mint ha nem is naprakésszé semmit, ha csinál a második rekurzív hívás
ha szó szerint csak a funkció meghívása újra ugyanazokat az érveket
és nem globális változók megváltoztak, vagy ilyesmi,
soha nem éri el az alap esetben, ebben az esetben, hogy ez rossz.
Ez lesz egy végtelen rekurzió és verem túlcsordulás.
De itt azt látjuk, hogy a frissítés történik, mivel mi frissítése kezdeni + end / 2,
vagyunk frissítése vége érv itt vagyunk frissítése kezdetét érvet itt.
Tehát minden rekurzív hívás vagyunk frissítése valamit. Oké.
Szeretné járni hozzánk a megoldás? >> Persze.
Én vagyok a SearchHelp úgy, hogy minden alkalommal, amikor ezt a funkciót felhívás
Nekem van a kezdete, ahol én keresem a tömbben és a végén
hol keresem a tömbben.
>> Minden lépésnél, ahol mondja, hogy ez a középső elem, amely a kezdő + end / 2,
, hogy azonos azzal, amit keresünk?
És ha igen, akkor talált rá, és azt hiszem, hogy lesz telt ki a szint rekurzió.
És ha ez nem igaz, akkor ellenőrizze, hogy a középső érték a tömb túl nagy,
ebben az esetben nézzük a bal felén a tömböt fog kezdetétől a középső index.
És egyébként mi a vége fele.
[Bowden] Oké.
Ez jól hangzik.
Oké, egy pár dolgot, és valóban, ez egy nagyon magas szintű dolog
hogy soha nem kell tudni, hogy a kurzus, de ez igaz.
Rekurzív függvények, mindig hallani, hogy ők egy rossz üzlet
mert ha rekurzívan nevezed magad túl sokszor, akkor kap verem túlcsordulás
mert, mint már mondtam, minden funkciót kap a saját stack frame.
Tehát minden egyes hívás a rekurzív függvény kap saját stack frame.
Tehát, ha csinál 1.000 rekurzív hívásokat, akkor kap 1.000 stack keretek,
és gyorsan vezetsz, hogy miután túl sok stack keretek és a dolgok csak megtörni.
Szóval ezért rekurzív függvények általában rossz.
De van egy szép részhalmaza rekurzív függvények úgynevezett tail-rekurzív függvények,
és ez történetesen egy példát, ahol, ha a fordító észreveszi ezt
és azt kell, azt hiszem - a csengés, ha átadja neki a-O2 flag
akkor veszi észre ezt farok rekurzív, és a dolgok jó.
>> Ez újra ugyanazt a stack frame újra és újra minden rekurzív hívást.
És mivel te ugyanazt a verem keret, akkor nem kell aggódnia
valaha verem túláradó, és ezzel egy időben, ahogy már korábban említettük,
ha egyszer visszatér igaz, akkor vissza kell térnie az összes ilyen stack frame
és a 10. hívás SearchHelp vissza kell térnie a 9., van, hogy visszatérjen a 8..
Annak érdekében, hogy nem kell történni, ha a funkciók farok rekurzív.
És mi teszi ezt a funkciót, farok rekurzív is vegyük észre, hogy az adott hívás searchHelp
a rekurzív hívás, hogy ez így van, mi ez visszatér.
Tehát az első hívás SearchHelp, akkor vagy azonnal vissza hamis,
azonnal vissza igaz, vagy mi, hogy egy rekurzív hívás SearchHelp
ahol mi vagyunk vissza, ami a hívás visszatér.
És nem tudtuk ezt, ha csináltunk valami hasonlót int x = SearchHelp, return x * 2,
Csak néhány véletlenszerű változás.
>> Tehát most ez a rekurzív hívás ez int x = SearchHelp rekurzív hívás
már nem farok rekurzív, mivel azt valóban kell vissza
vissza az előző stack keretet annak érdekében, hogy, hogy a korábbi felhívását, hogy a funkció
ezután csinálni valamit a visszatérési érték.
Tehát ez nem farok rekurzív, de mi volt azelőtt szépen farok rekurzív. Igen.
[Hallgató] Ha nem a második alapeset kell ellenőrizni 1.
mert lehet olyan helyzet, amikor, amikor átadni azt az érvet,
Ön start = end, de ők a tűt értéket.
A kérdést nem tudjuk befut az esetben, ha vége a tű érték
, vagy indítson = végén, megfelelő, start = end
és még nem is ellenőrizték, hogy különös értéket még,
majd indítsa + end / 2 csak lesz ugyanaz az értéke.
De mi már vissza hamis, és mi soha nem ellenőrizték az értéket.
Így legalábbis, az első hívást, ha a méret 0, akkor szeretnénk visszatérni hamis.
De ha mérete 1, akkor indítás nem fog azonos célból
és mi legalább megtekintéséhez egy eleme.
De azt hiszem, igazad van, hogy mi is a végén egy olyan ügyben, ahol az induló + end / 2,
indítás végül is ugyanaz, mint a kezdő + end / 2,
de mi soha nem ellenőrizte, hogy elemet.
>> Tehát ha először ellenőrzi a középső elem értéke keresünk,
akkor azonnal vissza igaz.
Különben ha ők egyenlő, akkor nincs értelme tovább
hiszen mi csak fog frissíteni az esetben, ha mi egyetlen elemű tömb.
Ha egyetlen elem nem az, amit keresünk,
akkor minden rossz. Igen.
[Hallgató] A lényeg az, hogy mivel a mérete valóban nagyobb, mint a tömb elemeinek,
már van egy eltolás - >> Így lesz méret -
[Hallgató] Mondja, ha a tömb mérete 0 volt, akkor a SearchHelp ténylegesen ellenőrzi szénaboglya a 0
az első hívást.
A tömb mérete 0, tehát a 0 jelentése - >> Igen.
Van egy másik dolog, hogy - ez lehet jó. Gondoljuk.
Tehát, ha a tömb volt 10 elemek és a középső fogjuk ellenőrizni a index 5,
úgyhogy ellenőrzése 5, és tegyük fel, hogy az érték kisebb.
Szóval dobott mindent idegenben 5-től kezdve.
Így kezdődik + end / 2 lesz az új végén,
Szóval igen, ez mindig fog maradni vége után a tömb.
Ha ez a helyzet, ha ez páros vagy páratlan, akkor mi lenne ellenőrizni, mondjuk, 4,
de még mindig eldobni -
Szóval igen, vége mindig lesz túl tényleges végén a tömb.
Tehát az elemeket mi összpontosítva, végén mindig lesz az egyik után.
És ha az elején nem mindig egyenlő a célból vagyunk tömb mérete 0.
>> A másik dolog, gondoltam is vagyunk frissítése kezdetét kell kezdeni + end / 2,
így ez az eset áll fenn, hogy Gondjaim be, ahol az induló + end / 2
az elem vagyunk ellenőrzés.
Tegyük fel, hogy mi volt ez a 10-elem tömb. Mindegy.
Így kezdődik + end / 2 lesz valami, mint ez,
és ha ez nem az érték, mondjuk szeretnénk frissíteni.
Az érték nagyobb, ezért szeretnénk, hogy nézd meg ezt a felét a tömbben.
Szóval hogyan vagyunk frissítése kezdetét, mi frissítése kezdetétől most ezt az elemet.
De ez még mindig működik, vagy legalábbis, meg tudod csinálni kezdő + end / 2 + 1.
[Hallgató] Nem kell kezdeni + végét [hallhatatlan] >> Igen.
Már ellenőrizte ezt az elemet, és tudom, hogy ez nem az, amit keresünk.
Tehát nem kell frissíteni kezdetét, hogy ezt az elemet.
Mi is csak hagyja ki és frissítse kezd, hogy ezt az elemet.
És van még egy eset, mondjuk, hogy ez volt a célból
így majd indítsa lenne ez, indítsa + end / 2 lesz ez,
indul + end - Igen, azt hiszem, hogy végül a végtelen rekurziót.
Tegyük fel, hogy ez csak egy tömb mérete 2 vagy tömb mérete 1. Azt hiszem, ez működni fog.
Tehát jelenleg az, hogy a kezdő elem és vége 1 túl.
Tehát az elem, hogy mi megyünk, hogy ellenőrizze ezt,
majd amikor frissíti kezdete, mi frissítése kezdete legyen 0 + 1/2,
amely a fog végződni minket vissza kezdetét, hogy ezt az elemet.
>> Szóval ellenőrzésére azonos elem újra és újra.
Szóval ez a helyzet, ha minden rekurzív hívás ténylegesen frissíteni valamit.
Így kell tennünk kezdő + end / 2 + 1, vagy pedig van egy eset
ha nem vagyunk valójában frissítés start.
Mindenki látja, hogy?
Oké.
Van valakinek kérdése ez a megoldás, vagy bármilyen további megjegyzés?
Oké. Tudja valaki, hogy egy iteratív megoldás, hogy mindannyian nézni?
Vajon mindannyian csinálni rekurzívan?
Vagy is, azt hiszem, ha nyitott az övé, akkor lehet, hogy felülírja az előző.
Vajon automatikusan elmenti? Nem vagyok pozitív.
Tudja valaki, hogy iteratív?
Mi lehet járni rajta együtt, ha nem.
Az ötlet lesz ugyanaz.
Iteratív megoldás.
Fogunk szeretnénk alapvetően nem ugyanaz a gondolat
ahol szeretnénk nyomon követni az új végén a tömb és az új kezdete a tömb
és nem, hogy újra és újra.
És ha mi vagyunk nyomon követni, mint a kezdet és a vég mindig metszik egymást,
akkor nem találtunk, és vissza tudjuk hamis.
Szóval, hogyan tudom ezt? Bárki, aki javaslatokat vagy kód a számomra, hogy húzza fel?
[Hallgató] Van egy darabig hurok. >> Igen.
Fogsz szeretne csinálni egy hurok.
>> Hasznosnak tekintette kódot tudtam felhúzni, vagy mit fog javasolni?
[Hallgató] Azt hiszem, igen. >> Rendben. Ez megkönnyíti a dolgokat. Mi volt a neve?
[Hallgató] Lucas.
Felülvizsgálat 1. Oké.
Olcsó az, amit az úgynevezett kezdeni előtt.
Fel nem egészen, amit az úgynevezett vége előtt.
Igazából, vége már a tömbben. Ez egy elemet is figyelembe kell vennie.
Így alacsony 0, fel a méret a tömb - 1,
és most looping, és ellenőrzik -
Azt hiszem, lehet sétálni rajta.
Mi volt a gondolkodás ezen keresztül? Sétáljon velünk a kódot.
[Hallgató] Persze. Nézd meg a szénakazalban értéket a középső és hasonlítsa össze a tűt.
Szóval, ha ez magasabb, mint a tű, akkor azt szeretnénk, hogy - ó, tényleg, hogy kell visszafelé.
Fogsz szeretné eldobni a jobb felét, és így igen, hogy kell az utat.
[Bowden] Szóval ez alacsonyabbnak kell lennie? Ez az, amit mondott? >> [Hallgató] Igen.
[Bowden] Oké. Kevesebbet.
Tehát, ha mi éppen a kisebb, mint amit akarunk,
akkor igen, azt akarjuk, hogy dobja el a bal fele,
ami azt jelenti, frissít mindent vagyunk tekintve
mozgatásával alacsony jobbra a tömb.
Ez jól néz ki.
Azt hiszem, ez ugyanaz a kérdés, hogy azt mondtuk, az előző,
ahol ha alacsony értéke 0 és legfeljebb 1, akkor az alacsony + fel / 2 fog létrehozni, hogy ugyanaz a dolog újra.
>> És akkor is, ha nem ez a helyzet, akkor még hatékonyabb legalább
hogy csak dobja az elemet már csak néztem amiről tudjuk, hogy rossz.
Tehát alacsony + fel / 2 + 1 - >> [hallgató] Ez legyen a másik irányba.
[Bowden] Vagy ezt kellene - 1 és a másik legyen + 1.
[Hallgató] És legyen egy dupla egyenlőségjel. >> [Bowden] Igen.
[Hallgató] Igen.
Oké.
És végül, most, hogy van ez a + 1 - 1 dolog,
ez - talán nem is - ez mindig lehetséges alacsony ahhoz, hogy a végén egy-nél nagyobb értéket fel?
Azt hiszem, az egyetlen módja, hogy megtörténhet - Lehetséges ez? >> [Hallgató] Nem tudom.
De ha ez lesz csonkítva, majd kap mínusz, hogy az 1, majd a - >> Igen.
[Hallgató] Ez valószínűleg kap elrontotta.
Azt hiszem, jó lesz csak azért, mert
mert a végén alacsonyabb kellett volna egyenlő, azt hiszem.
De ha egyenlő, akkor nem tett volna a while ciklus kezdeni
és mi csak volna vissza az értéket. Tehát úgy gondolom, jók vagyunk most.
Figyeljük meg, hogy annak ellenére, hogy ez a probléma már nem rekurzív,
ugyanolyan ötleteket kell alkalmazni, ha azt látjuk, hogy ez ilyen könnyen kínálkozik
a rekurzív megoldás az, hogy mi csak frissítésével indexek újra és újra,
tesszük a problémát, egyre kisebb és kisebb, mi összpontosítva egy részhalmaza a tömb.
[Hallgató] Ha alacsony jelentése 0 és fel jelentése 1, akkor mindketten 0 + 1/2, ami menne 0-ra,
és akkor sem lenne + 1, az egyik a - 1.
[Hallgató] Hol vagyunk ellenőrzési egyenlőség?
Mint ha a középső valójában tű?
Mi jelenleg nem csinálja ezt? Oh!
Ha ez -
Igen. Nem csak ezt a vizsgálatot le ide, mert mondjuk az első közép -
[Hallgató] Ez tulajdonképpen tetszik nem dobja el a kötött.
Tehát, ha dobja a kötött, akkor ellenőrizze, hogy az első vagy bármi.
Ah. Igen. >> [Hallgató] Igen.
Tehát most már dobni az egyik jelenleg nézett,
ami azt jelenti, hogy most kell is
if (szénakazalban [(low +-ig) / 2] == tű), akkor mi is vissza igaz.
És akár tettem mást, vagy csak, ha ez azt jelenti, szó szerint ugyanaz a dolog
mert ez volna vissza igaz.
Így fogok tenni, ha mást, de ez nem számít.
>> Tehát még ha ez, más ez, és ez egy közös dolog, amit csinálni
ahol még ha ez a helyzet, ha minden jó itt,
mint az alacsony soha nem lehet nagyobb, mint felfelé, nem érdemes érvelést arról, hogy ez igaz.
Szóval, akkor is azt mondják, míg az alacsony kisebb vagy egyenlő, mint
vagy az olyan, kis kisebb, mint
így ha valaha is azonos vagy alacsony lesz, hogy lemondjunk róluk,
akkor lehet kitörni a hurok.
Kérdések, aggályok, észrevétel?
Oké. Ez jól néz ki.
Most szeretnénk csinálni sort.
Ha elmegyünk a második felülvizsgálat, azt látjuk, ezek ugyanazt a számot,
de most már nem rendezetten.
És azt akarjuk, hogy végre sort tetszőleges algoritmus O n log n.
Tehát melyik algoritmus mit kéne végre itt? >> [Hallgató] Merge sort.
[Bowden] Igen. Merge rendezés O (n log n), úgy, hogy az, amit mi fogunk csinálni.
És a probléma lesz nagyon hasonló,
ahol könnyen alkalmas arra, hogy egy rekurzív megoldást.
Mi is felér egy iteratív megoldás, ha azt akarjuk,
de a rekurzió könnyebb lesz itt, és meg kell tennünk a rekurziót.
Azt hiszem, majd séta a merge sort az első,
bár van egy szép videót merge sort már. [Nevetés]
Tehát merge sort vannak - Én pazarlás ennyi e papír.
Ó, már csak egy maradt.
Szóval egyesítése.
Oh, 1, 3, 5.
Oké.
Merge vesz két külön tömböket.
Egyénileg a két tömb egyaránt rendezve.
Szóval ez a tömb, 1, 3, 5, rendezve. Ez a tömb, 0, 2, 4, rendezve.
Most mit kell tennie, egyesítés egyesíteni őket egy tömb, amely maga rendezve.
Tehát szeretnénk egy sor mérete 6, ami megy, hogy ezek az elemek belsejében
rendezetten.
>> És így tudjuk kihasználni azt a tényt, hogy ez a két tömb rendezése
hogy ezt a lineáris időben,
lineáris idő értelme, ha ez a tömb mérete x és ez a méret y,
akkor a teljes algoritmus legyen O (x + y). Oké.
Szóval javaslatokat.
[Hallgató] tudnánk kezdeni a bal?
Szóval, akkor tegye a 0 le először, majd az 1-es és akkor itt te vagy a 2.
Szóval ez olyan, mint hogy van egy fül, ami mozog jobbra. >> [Bowden] Igen.
A mindkét tömbök ha csak összpontosítani a bal szélső elem.
Mivel mindkét tömbök vannak rendezve, tudjuk, hogy ezek 2 elem
a legkisebb elem egyik tömbben.
Ez azt jelenti, hogy 1 e 2 elem kell, hogy legyen a legkisebb eleme a egyesített tömbben.
Ez csak azért történik, hogy a legkisebb az egyik a jobb ebben az időben.
Úgyhogy veszünk 0, tegye rá a baloldali mivel 0 kisebb, mint 1,
hogy vegye 0, helyezze be az első helyre, majd mi frissíti ezt
hogy most összpontosítani az első elemet.
És most megismételjük.
Tehát most összehasonlítjuk 2 és 1. 1 kisebb, úgyhogy be 1.
Frissítjük ezt a mutatót, hogy pont ez a fickó.
Most csináld újra, így a 2. Ez frissíteni fogja, hasonlítsa össze ezeket a 2, 3.
Ezt frissítéseket, majd a 4 és 5.
Ez tehát merge.
>> Meg kell elég nyilvánvaló, hogy a lineáris idő óta megyünk át minden elem egyszer.
És ez a legnagyobb lépés a végrehajtási összevonási rendezés ezt.
És ez nem olyan nehéz.
Egy pár dolog aggódni a mondjuk voltunk egyesülő 1, 2, 3, 4, 5, 6.
Ebben az esetben a végén a forgatókönyv, ahol ez lesz kisebb,
akkor frissíti a mutató, ez lesz kisebb, frissíti a,
ez már kisebb, és most fel kell ismernie
ha már tényleg elfogyott elemek összehasonlítani.
Mivel már használnak az egész tömb,
mindent a tömb már csak beilleszteni ide.
Szóval, ha valaha is befut a ponton, ahol az egyik tömbök teljesen összeolvadt már,
akkor csak hogy minden elemét a többi tömb, és helyezze őket a végén a tömb.
Így tudjuk csak helyezze 4, 5, 6. Oké.
Ez az egyik dolog, hogy néz ki.
Végrehajtási, hogy kell az 1. lépést.
Merge rendezni, akkor ennek alapján, ez 2 lépésben, 2 buta lépéseket.
Nézzük csak hogy ezt a tömböt.
Szóval merge sort, az 1. lépés az, hogy rekurzív törni a tömb a félidőt.
Szóval szét ezt a tömböt a félidőt.
Most már 4, 15, 16, 50 és 8, 23, 42, 108.
És most újra meg újra, és szét ezeket a félidőt.
Én csak csinálni ezen az oldalon.
Így 4, 15 és 16, 50.
Azt nem ugyanaz a dolog itt.
És most osztott be félbe ismét.
És van 4, 15, 16, 50.
Annak érdekében, hogy a mi alapeset.
Ha a tömbök mérete 1, akkor hagyja abba a hasítási a félidőt.
>> Most mit csináljunk ezzel?
A végén ez is lebontják a 8, 23, 42, és 108.
Tehát most, hogy vagyunk ezen a ponton, most lépjen kettő merge sort éppen egyesülő párok a listákra.
Tehát szeretnénk egyesíteni ezeket. Csak hívjon összeolvad.
Tudjuk, hogy merge visszatér ezeket rendezett sorrendben.
4, 15.
Most szeretnénk egyesíteni ezeket, és hogy vissza fog térni a listát azokkal, rendezetten,
16, 50.
Mi egyesíteni azokat - nem tudok írni - 8, 23 és 42, 108.
Tehát létrejött pár egyszer.
Most már csak egyesíteni újra.
Figyeljük meg, hogy minden egyes ilyen listák rendezve önmagában,
és akkor is csak egyesíteni ezeket a listákat, hogy kap egy listát a 4-es méretű, amely rendezve
és egyesíti a két listát kap egy listát a 4-es méretű, ami rendezve.
És végül, tudjuk egyesíteni e két listáját 4-es méretű, hogy kap egy listát, hogy a 8-as méret van rendezve.
Tehát látható, hogy ez az általános n log n, már láttuk, hogy merge lineáris,
így amikor dolgunk egyesülő e, így például a teljes költsége merge
e két lista csak 2, mert -
Vagy jól, ez O n, de n itt csak ezeket a 2 elem, így 2.
És ezek a 2 lesz 2 és e 2 lesz 2, és ezek 2 lesz 2,
így minden a összevonta, hogy meg kell csinálni, amit a végén csinál n.
Mint a 2 + 2 + 2 + 2 8 közül az N,
így a költsége egyesülő erre a halmazra n.
És ugyanaz a dolog itt.
Majd eleget a 2, majd ezeket a 2, és egyénileg ezen engedmény lesz 4 műveletek,
ezen engedmény lesz 4 műveleteket, de még egyszer, az összes ilyen,
a végén egyesülő n át a dolgokat, és így ezt a lépést tart n.
És így minden szinten előnyben n elem egyesítették.
>> És hány szint van?
Minden egyes szinten a tömb növekszik 2-es méret.
Íme a tömbök mérete 1, itt ők a 2-es méret, itt ők a 4-es méretű,
és végül, ők a 8-as méret.
Tehát mivel duplájára, ott lesznek összesen log n ezeket a szinteket.
Tehát log n szint, minden egyes szinten figyelembe n összesen műveletek,
kapunk egy n log n algoritmus.
Kérdései vannak?
Az emberek már haladást ért el, hogyan hajtsák végre ezt?
Van valaki már egy olyan államban, ahol tudok csak húzza fel a kódot?
Tudok adni egy percet.
Ez lesz hosszabb.
Én nagyon ajánlom kiújulnak -
Nem kell tennie rekurziót a merge
mert tenni rekurziót az egyesítés fogsz át kell adni egy csomó különböző méretű.
Tudod, de ez bosszantó.
De rekurzió a sort maga nagyon egyszerű.
Te csak a szó szoros értelmében szükséges sort a bal fele, sort a jobb felét. Oké.
Bárki bármit tudok húzni még fel?
Vagy Adok egy percet.
Oké.
Bárki, aki valamit tudunk dolgozni?
Vagy akkor csak dolgozni ezzel majd bontsa ki onnan.
>> Bárki, aki több, mint ez, hogy én is húzza fel?
[Hallgató] Igen. Akkor húzza fel az enyémet. >> Rendben.
Igen!
[Hallgató] Volt egy csomó feltételeket. >> Ó, a francba. Can you -
[Hallgató] Meg kell menteni. >> Igen.
Így tettük ezt az egyesítés külön-külön.
Ó, de ez nem olyan rossz.
Oké.
Szóval sort maga csak hívás mergeSortHelp.
Magyarázd el, mi mergeSortHelp csinál.
[Hallgató] MergeSortHelp nagyjából működik a két fő lépésben,
amely rendezni mindkét felét a tömb, majd egyesíteni mind a ketten.
[Bowden] Oké, adj egy percet.
Azt hiszem, ez - >> [hallgató] Meg kell -
Igen. Én valami hiányzik.
Az egyesítés, rájöttem, hogy szükségem van egy új tömböt
mert nem tudtam csinálni a helyén. >> Igen. Nem lehet. Helyes.
[Hallgató] Szóval hozzon létre egy új tömböt.
Elfelejtettem végén egyesítés újbóli-változás.
Oké. Szükségünk van egy új tömböt.
A merge sort, ez szinte mindig igaz.
Része a költségek egy jobb algoritmust idő-bölcs
szinte mindig szüksége, hogy egy kicsit több memóriát igényel.
Tehát itt nem számít, hogyan csinálod egyesítése sort,
akkor elkerülhetetlenül kell használni egy kis extra memóriát.
Ő létrehozott egy új tömböt.
És akkor azt mondja a végén már csak be kell másolni az új tömb az eredeti tömb.
[Hallgató] Azt hiszem, igen.
Én nem tudom, hogy működik szempontjából számolás történő hivatkozással, vagy bármi -
Igen, ez működni fog. >> [Hallgató] Oké.
Próbáltad futó ezt? >> [Hallgató] Nem, még nem. >> Oké.
Próbálja futtatni, és aztán majd beszélünk róla egy kicsit.
[Hallgató] Azt kell, hogy az összes funkció prototípusok és mindent, igaz?
A függvény prototípusok. Úgy érted, mint a - Igen.
Sort hívja mergeSortHelp.
>> Így ahhoz, hogy a sort, hogy hívja mergeSortHelp, mergeSortHelp kell vagy már meghatározták
mielőtt sort, vagy már csak be kell a prototípus. Csak másolja be azt.
És hasonlóképpen, mergeSortHelp hív összeolvad,
de merge még nem határozták még meg, így tudjuk csak hadd mergeSortHelp tudom
hogy az, amit egyesíteni fog kinézni, és ennyi.
Szóval mergeSortHelp.
Van olyan kérdés van, ahol nincs az alapeset.
MergeSortHelp rekurzív, így minden rekurzív függvény
lesz szüksége valamilyen alapeset tudni, hogy mikor kell abbahagyni rekurzívan hívja magát.
Mi a alapeset lesz itt? Igen.
[Hallgató] Ha a méret 1? >> [Bowden] Igen.
Szóval, mint láttuk ott, álltunk hasító tömbök
ha egyszer bekerült tömbök mérete 1, ami elkerülhetetlenül vannak rendezve magukat.
Tehát, ha mérete értéke 1, tudjuk, hogy a tömb már rendezett,
így tudjuk csak vissza.
>> Figyeljük meg, hogy az érvénytelen, így nem adott vissza semmit, csak vissza.
Oké. Szóval ez a mi alapeset.
Azt hiszem, a mi az alapeset is lehetne, ha történetesen egyesülő tömb mérete 0,
akkor valószínűleg szeretne állni egy bizonyos ponton,
így tudjuk csak mondjuk méret kisebb, mint 2 vagy kisebb, mint vagy egyenlő 1
annak érdekében, hogy ez működni fog bármilyen tömb most.
Oké.
Szóval ez a mi alapeset.
Most akarsz járni hozzánk merge?
Mit jelentenek ezek az esetekben jelent?
Akár itt, csak most ugyanezt teszi ötlet, a -
[Hallgató] I kell áthaladó méret minden mergeSortHelp hívást.
Én hozzá méretű kiegészítő elsődleges, és nem ott, mint például a méret / 2.
[Bowden] Oh, méret / 2, méret / 2. >> [Hallgató] Ja, és szintén a fenti funkció is.
[Bowden] Itt? >> [Hallgató] Csak méretét. >> [Bowden] Oh. Méret, méret? >> [Hallgató] Igen.
[Bowden] Oké.
Hadd gondolkozzam egy kicsit.
Vajon befut egy kérdés?
Mindig kezeljük a bal oldali 0-ként. >> [Hallgató] Nem
Ez rossz is. Bocsánat. Meg kell kezdeni. Igen.
[Bowden] Oké. Szeretem, hogy a jobb.
És a végén. Oké.
Tehát most nem akarsz járni hozzánk merge? >> [Hallgató] Oké.
Én csak séta az új tömb, hogy én már létre.
Mérete a méret a részét a tömb, hogy szeretnénk kell válogatni
és megpróbálja megtalálni az elemet, amit meg kell oldania az új tömb lépést.
Így kell csinálni, hogy először én ellenőrzése, amikor a bal fele a tömb továbbra is többé elemet,
és ha nem, akkor menj le, hogy más feltétel, amely szerint csak a
rendben kell, hogy legyen a megfelelő tömb, és mi fel, hogy a jelenlegi index newArray.
>> És aztán különben én ellenőrzése, ha a jobb oldalon a tömb is befejeződött,
ebben az esetben én csak fel a bal oldalon.
Ez talán nem is lesz szükség. Nem vagyok benne biztos.
De egyébként is, a másik két ellenőrzést, hogy a két kisebb, a bal vagy a jobb.
És azt is minden esetben, én növelésének amelyik placeholder I növelni.
[Bowden] Oké.
Jól néz ki.
Van valakinek megjegyzése vagy problémája vagy kérdése?
Így a négy eset, hogy meg kell hozni a dolgokat csak, hogy - vagy úgy néz ki, 5 -
de meg kell vizsgálni, hogy a bal oldali tömb kifogy a dolog, amit meg kell egyesíteni,
arról, hogy a megfelelő tömb kifogy a dolog, amit meg kell egyesíteni -
Én mutatott semmit.
Szóval, hogy a bal oldali tömb elfogyott a dolgok, vagy a megfelelő tömb kifogyott a dolgokat.
E két esetben.
Azt is meg kell triviális eset, hogy a bal oldali dolog, kevesebb, mint a helyes dolog.
Aztán akarjuk választani a bal dolog.
Azok az esetek.
Szóval ez volt a helyes, hogy ez az.
Array maradt. Ez 1, 2, 3. Oké. Szóval igen, ezek a négy dolog, amit érdemes csinálni.
És mi nem megy át egy iteratív megoldást.
Én nem ajánlom -
Merge rendezés egy példa egy függvény, amely egyszerre nem farok rekurzív,
ez nem könnyű, hogy ez farok rekurzív,
de ez nem könnyű, hogy ez iteratív.
Ez nagyon egyszerű.
Ez a végrehajtása merge sort,
egyesítése, nem számít, mit teszel, fogsz építeni merge.
>> Szóval merge sort épülő egyesítés rekurzívan mindössze három sorokat.
Iteratív, ez több bosszantó és nehezebb gondolkodni.
De észre, hogy ez nem farok rekurzív kezdete mergeSortHelp - ha nevezi magát -
meg kell még csinálni a dolgokat után rekurzív hívás visszatér.
Tehát ez a stack frame továbbra is fennállnak után is hívja ezt.
És akkor, amikor hívja ezt, a verem keretet kell továbbra is fennállnak
mert még azután is, hogy a hívást, még mindig meg kell egyesíteni.
És ez triviális, hogy ez a farok rekurzív.
Kérdései vannak?
Rendben van.
Szóval, megy vissza a rendezéshez - ó, ott két dolgot szeretnék mutatni. Oké.
Visszatérve a sort, akkor ezt gyorsan.
Vagy keressen. Sort? Sort. Igen.
Visszatérve a kezdetekhez a sort.
Szeretnénk létrehozni egy olyan algoritmus, amely rendezi a tömb bármely algoritmus
O n.
Hogy lehetséges ez? Van valakinek bármilyen -
Én utalt mielőtt azt -
Ha mindjárt javul n log n O n,
már javult a algoritmus idő-bölcs,
ami azt jelenti, hogy mit fogunk csinálni kell pótolni ezt?
[Hallgató] Space. >> Igen. Fogunk használni több helyet.
És nem is csak több helyet, hanem exponenciálisan nagyobb teret.
Úgy gondolom, ez a fajta algoritmus pszeudo valami pszeudo polinom -
pszeudo - Nem emlékszem. Pszeudo valamit.
De ez azért van, mert meg kell használni, így sok helyet
, hogy ez megvalósítható, de nem reális.
>> És hogyan érhetjük el ezt?
Mi lehet ennek elérésére, ha garantáljuk, hogy egy adott elem a tömbben
ér el egy meghatározott méret.
Akkor mondjuk, hogy a mérete 200,
bármely elem egy tömb alatt van méret 200.
És ez valóban nagyon reális.
Akkor nagyon könnyen van egy tömb, hogy tudod, mindent, ami benne
lesz kisebb, mint néhány szám.
Mint ha van néhány teljesen masszív vektort vagy valami
de tudod, minden rendben van, hogy 0 és 5 között,
akkor lesz jelentősen gyorsabb erre.
És a kötődött bármelyik az elemek 5,
így ez a korlát, azaz mennyi memóriát fogsz használni.
Tehát a korlát 200-at.
Elméletileg van mindig egy kötött mert értéke csak legfeljebb 4 milliárd
de ez reális cél, mivel akkor lenne a tér
a sorrendben a 4 milliárdot. Szóval ez irreális.
De itt mi mondjuk a korlát 200.
A trükk az, hogy csinálja az O n teszünk egy sor úgynevezett rendbeli méretű kötve.
Tehát tulajdonképpen ez egy parancsikont - Igazából nem tudom, ha csenget teszi ezt.
De GCC legalább - Én feltételezve csenget csinálja is -
ez csak inicializálja az egész tömb legyen 0s.
Szóval, ha én nem akarom, hogy akkor én is külön-külön do for (int i = 0;
i <BOUND; i + +) és számít [i] = 0;
Tehát most mindent inicializálva 0-ra.
Én iterációkhoz a tömb,
és mit csinálok én számlálás a számát az egyes - Menjünk le ide.
Jelenleg 4, 15, 16, 50, 8, 23, 42, 108.
Amit én számolva ez az előfordulások számát az egyes elemei.
Nézzünk ténylegesen hozzá még egy pár itt néhány ismétlődik.
Tehát ez az érték van itt, az értékét a lesz array [i].
Így val lehet 4 vagy 8, vagy bármi.
És most számít, hogy hány az értéket láttam,
így számít [val] + +;
Miután ez megtörtént, számít fog kinézni 0001.
Csináljuk számít [val] - KÖTELEZŐ + 1.
>> Most, hogy csak azért, hogy figyelembe azt a tényt, hogy mi kezdődően 0.
Tehát ha 200 lesz a legnagyobb számú,
majd 0-200 jelentése 201 dolgok.
Tehát számít, úgy fogsz kinézni, mint 00001, mert van egy 4.
Akkor mi lesz, ha 0001 lesz egy 1-8-án index száma.
Lesz egy 2-23-index száma.
Mi lesz a 2 a 42. index száma.
Így tudjuk használni száma.
Szóval num_of_item = számít [i].
És így ha num_of_item 2, ez azt jelenti, hogy szeretné szúrni 2-i száma
a mi rendezett tömbben.
Tehát meg kell nyomon követni, hogy milyen messze vagyunk a tömb.
Tehát index = 0.
Array - Én csak írni.
Counts -
array [index + +] = i;
Ez az, amit akarok? Azt hiszem, ez az, amit akarok.
Igen, ez jól néz ki. Oké.
Tehát nem mindenki érti, mi a célja az én számít tömb?
Ez számít az előfordulások számát minden egyes ilyen számok.
Akkor vagyok iterációjával felett számít tömb,
és az i-edik pozícióját a szám tömb
a szám az i ez jelenjen meg a rendezett tömbben.
Ezért számít a 4 lesz 1
és számít a 8 lesz 1, számuk 23 lesz 2.
Szóval így sokan szeretnék illeszteni a rendezett tömbben.
Aztán csak csinálni.
Én behelyezése num_of_item i-az én rendezett tömbben.
>> Kérdései vannak?
És újra, ez a lineáris idő óta mi csak iterációjával át ezt egyszer,
de ez is lineáris, mi ez a szám történetesen,
és így nagymértékben attól függ, hogy mi a korlát.
A kötött, 200, ez nem is olyan rossz.
Ha a kötött lesz 10.000, akkor ez egy kicsit rosszabb,
de ha a rögzített lesz 4 milliárd ez teljesen irreális
és ez a tömb lesz, hogy legyen a méret 4 milliárd, ami irreális.
Szóval ennyi. Kérdései vannak?
[Hallhatatlan diák válasza] >> Oké.
Rájöttem, egy másik dolog, ha megyünk keresztül.
Azt hiszem, a probléma az volt, a Lucas és valószínűleg minden egyes ember láttunk.
Teljesen elfelejtettem.
Az egyetlen dolog, amit szerettem volna, hogy mondjon véleményt, hogy ha van dolgunk, dolgok, mint indexek,
Ön soha nem látni ezt, ha írsz egy for ciklus,
de technikailag, ha van dolgunk, ezek a mutatók,
akkor nagyjából mindig foglalkozik előjel nélküli egészek.
Ennek oka az, amikor dolgunk aláírt egészek,
így ha van 2 aláírt egészek, és felveszi őket
és a végén túl nagy, akkor a végén egy negatív szám.
Szóval ez az, amit egész túlcsordulás.
>> Ha hozzá 2 milliárd 1 milliárd I végén negatív 1 milliárd euró.
Így egész munka számítógépeken.
Tehát a probléma a -
Ez rendben van, kivéve, ha az alacsony történik, hogy 2 milliárd legfeljebb történetesen 1 milliárd
akkor ez lesz a negatív 1 milliárd és akkor fogjuk osztani, hogy a 2-
és a végén a negatív 500 millió EUR.
Tehát ez csak egy kérdés, ha történetesen kereső segítségével egy tömb
milliárd a dolgokat.
De ha kis +-ig történik túlcsordulás, akkor ez a probléma.
Amint teszik aláíratlan, majd 2000000000 plusz 1 milliárd 3 milliárdot.
3000000000 osztva 2 pedig 1,5 milliárd euró.
Szóval, amint ők aláíratlan, minden tökéletes.
És ez is egy olyan kérdés, amikor írsz be a hurkok,
és valóban, ez valószínűleg nem teszi meg automatikusan.
Ez valójában csak kiabálni veled.
Tehát, ha ez a szám túl nagy lenni csak egy integer, de ez illik egy előjel nélküli egész,
fog kiabálni, úgyhogy ez az, amiért soha nem befut a kérdést.
Láthatjuk, hogy az index soha nem lesz negatív,
és így, amikor iterációjával át egy tömb,
akkor szinte mindig azt mondják, unsigned int i, de nem igazán kell.
Dolgok mennek dolgozni nagyjából ugyanúgy.
Oké. [Suttog] Mi van most?
Az utolsó dolog, amit meg akartam mutatni - és én csak csinálni nagyon gyors.
Tudod, hogy mi # define így tudjuk # define MAX mint 5, vagy valami?
Ne tegye MAX. # Define KÖTELEZŐ, mint 200-at. Ez az, amit mi korábban.
Ez határozza meg a konstans, ami csak megy a vágólapra másolni
bárhol is történik, hogy írjon rá nézve kötelező.
>> Tehát valójában többre # definiálja.
Mi lehet a # define funkciókat.
Ők nem igazán funkcióját, de fogjuk hívni őket funkciókat.
Egy példa lenne, valami hasonlót MAX (x, y) meghatározása (x <y? Y: x). Oké.
Szóval meg kell szokni hármas operátor szintaxisa,
de x kisebb mint y? Vissza y, különben vissza x.
Így látni lehet, hogy ez egy külön funkció,
és a funkció lehet, mint bool MAX úgy 2 érvek vissza ezt.
Ez az egyik a leggyakoribbak látom kész így. Hívjuk őket makrókat.
Ez egy makrót.
Ez csak a szintaxis is.
Írhat makrót csinálsz, amit akarsz.
Ön gyakran látni makrók hibakeresési printfs, meg ilyesmi.
Tehát egyfajta printf, vannak speciális állandók C mint aláhúzás LINE aláhúzás,
2 aláhúzás LINE aláhúzás,
és ott is azt hiszem 2 aláhúzás FUNC. Lehet, hogy azt. Valami ilyesmi.
Azok a dolgok váltják fel a nevét, a funkció
vagy a számot a sor, hogy te vagy az.
Gyakran írsz hibakeresés printfs, hogy ide tudok majd csak írni
DEBUG, és kiírja a sor számát és a funkció, hogy én történetesen
hogy felmerült, hogy DEBUG nyilatkozatot.
És te is nyomtathatja más dolog.
Tehát az egyik dolog, amit meg kell nézni ki, ha én történetesen # define DOUBLE_MAX
valami, mint a 2 * 2 * y és x.
Tehát bármilyen okból, véletlenül csinálni, hogy egy csomó.
Tehát, hogy ez egy makrót.
Ez ténylegesen sérült.
Hívnám azt csinál valami ilyesmi DOUBLE_MAX (3, 6).
Szóval mit kell visszaküldeni?
[Hallgató] 12.
Igen, 12 vissza kell küldeni, és 12 van vissza.
3 kap helyébe az x, 6 lesz helyettesíteni y, és mi vissza 2 * 6, amely a 12.
Most mi van ezzel? Mit kell vissza?
[Hallgató] 14. >> Ideális esetben 14.
A kérdés az, hogy mennyire hash meghatározza a munka, ne feledje, ez egy szó szerinti másolás és beillesztés
Az elég sok mindent, akkor mi ez lesz kell értelmezni,
3 kisebb, mint 1 és 6, 2-szer 1 és 6, 2-szer 3.
>> Szóval ezért szinte mindig mindent betakar zárójelben.
Minden változó, szinte mindig csomagolja zárójelben.
Vannak olyan esetek, amikor nem kell, mint tudom, hogy nem kell csinálni, hogy itt
mert kevesebb, mint nagyjából mindig csak működni fog,
annak ellenére, hogy talán nem is igaz.
Ha van valami nevetséges, mint DOUBLE_MAX (1 == 2),
akkor ez fog kap helyett 3 kevesebb, mint 1 egyenlő értéke 2,
és így akkor fog csinálni 3 kevesebb, mint 1, nem, hogy az egyenlő 2,
ami nem az, amit akarunk.
Így annak érdekében, hogy megakadályozza operátor precedencia problémákat,
Mindig csomagolja zárójelben.
Oké. És ez az, 5:30.
Ha bármilyen kérdése van a Pset, tudassa velünk.
Meg lehet szórakoztató, és a hacker kiadás is sokkal reálisabb
mint a hacker kiadása a tavalyi, ezért reméljük, hogy sok nem próbálja meg.
A tavalyi nagyon nyomasztó.
>> [CS50.TV]