[Powered by Google Translate] [Oddiel 3 - Ďalšie Komfortné]
[Rob Bowden - Harvard University]
>> [To je CS50. - CS50.TV]
>> Takže prvá otázka je podivne znie.
GDB umožňuje "ladiť" program, ale konkrétne, čo to nechať urobiť?
Budem odpovedať, že jeden, a ja neviem, čo to presne očakáva,
takže hádam, že je to niečo v duchu to umožňuje krok za krokom
prejsť programu, pracovať s ním, zmena premenných, robiť všetky tieto veci -
v podstate kompletne ovládať realizáciu programu
a skontrolujte, či na danej časti realizácie programu.
Takže tieto funkcie vám umožní ladiť veci.
Dobre.
Prečo binárne hľadanie vyžaduje, aby poľa byť zoradené?
Kto chce odpovedať, že?
[Študent] Vzhľadom k tomu, že nefunguje, pokiaľ to nie je zoradená. Jo >>. [Smiech]
Ak to nie je zoradená, potom je to možné rozdeliť na dve polovice
a viem, že všetko na ľavej strane je menší a všetko vpravo
je väčšia, ako je stredná hodnota.
Tak to musí byť zoradené.
Dobre.
Prečo je bublina triediť O n na druhú?
Má niekto najprv chcieť dať veľmi rýchlo na vysokej úrovni prehľad o tom, čo bublina druh je?
[Študent] Tie v podstate prejsť každý prvok a dáte zistiť niekoľko prvých prvkov.
Ak sú z miesta, kde ste ich swap, potom skontrolovať niekoľko ďalších prvkov, a tak ďalej.
Keď sa dostanete na koniec, potom viete, že najväčší prvok je umiestnený na konci,
takže budete ignorovať, že jeden potom pokračovať ďalej cez,
a zakaždým, keď budete musieť skontrolovať jeden menej prvok, kým nevykonáte žiadne zmeny. Jo >>.
Je to tzv bubble sort, pretože ak otočíte poľa na jeho strane, takže je to hore a dole, vertikálne,
potom veľké hodnoty budú klesať ku dnu a malé hodnoty budú bublina až na vrchol.
To je, ako to dostalo jeho meno.
A jo, stačí prejsť.
Stále ide cez pole, vymieňať väčšiu hodnotu
získať najväčšie hodnoty na dno.
>> Prečo je to O n na druhú?
Po prvé, niekto chce povedať, prečo je to O n na druhú?
[Študent] Pretože pre každý beh ide n krát.
Môžete byť istí, že ste si vzal Najsilnejším prvkom celú cestu dole,
potom sa budete musieť zopakovať, že tak veľa prvkov. Jo >>.
Takže majte na pamäti to, čo veľké O znamená a aké veľké Omega znamená.
Veľký O je ako hornú hranicu o tom, ako pomaly to môže skutočne spustiť.
Takže tým, že hovorí, že je to O n štvorčekový, to nie je O n inak by byť schopný spustiť
v lineárnom čase, ale je to O z n kocky
pretože to je ohraničené O n kocky.
Ak je to ohraničené O n štvorcový, potom je to ohraničené aj n kocky.
Takže je n na druhú, a v absolútnom najhoršom prípade nemožno lepšie ako n štvorcový,
čo je dôvod, prečo je O z n na druhú.
Takže vidieť mierny matematiku na to, ako vyjde von, aby sa n na druhú,
ak budeme mať päť vecí v našom zozname, prvýkrát, koľko swapy by sme mohli potenciálne potrebné, aby
aby sa to? Poďme vlastne len -
Koľko swapy budeme musieť urobiť v prvom behu bublín radiť cez pole?
[Študent] n - 1. Jo >>.
>> Ak sú 5 prvkov, budeme musieť vykonať n - 1.
Potom na druhom koľko swapy budeme musieť urobiť?
[Študent] n - 2. Jo >>.
A tretí bude n - 3, a potom pre pohodlie budem písať posledné dva
ako potom budeme potrebovať, aby sa 2 swapy a 1 swap.
Myslím, že posledný človek môže alebo nemusí v skutočnosti sa muselo stať.
Je to výmena? Neviem.
Takže sa jedná o celkové množstvo swapov alebo aspoň porovnaní budete musieť urobiť.
Aj keď nechcete vymeniť, budete ešte potrebovať na porovnanie hodnôt.
Tak sú n - 1 porovnanie v prvom prejdení poľa.
Ak usporiadanie týchto vecí, poďme vlastne robiť to šesť vecí, takže to vyrovnať pekne,
a potom budem robiť 3, 2, 1.
Takže len preskupiť tieto sumy, chceme vidieť, koľko porovnaní robíme
v celom algoritmu.
Takže ak vám prinášame tie chlapov tu,
potom sme stále len súčet však veľa porovnaní existovali.
Ale ak sčítame tieto a sčítame tieto a sčítame tieto,
je to stále rovnaký problém. Práve sme zhrnúť tieto konkrétne skupiny.
>> Takže teraz sa budeme sčítavať 3 n Nie je to len 3 n
Je to vždy bude n / 2 n
Takže tu máme náhodou 6.
Ak sme mali 10 vecí, potom by sme mohli urobiť túto združenia pre 5 rôznych párov vecí
a skončiť s n + n + n + n + n
Takže ste vždy dostane n / 2 n je, a tak to budeme zapisovať to k n na druhú / 2.
A tak aj keď je to faktor polovice, ktorý sa stane ďalej
vzhľadom k tomu, že po každej iterácii cez pole porovnáme 1 menej
tak to je, ako sa dostaneme cez 2, ale to je ešte n na druhú.
My sa nestaráme o konštantný faktor o polovicu.
Takže veľa veľké veci O takhle spolieha len na druhu robiť tento druh matematiky,
robiť aritmetické súčty a geometrické rady ďalšie veci,
ale väčšina z nich v tomto kurze sú celkom jasné.
Dobre.
Prečo je vloženie triediť Omega n? Čo omega znamená?
[Dva študenti hovoria naraz - nezrozumiteľné] >> Jo.
Omega si môžete myslieť, ako dolná hranica.
>> Takže bez ohľadu na to, ako efektívne váš vloženie sort je algoritmus,
bez ohľadu na zozname, ktorý je odovzdaný do, vždy musí porovnať aspoň n veci
alebo to má pre iteráciu n vecí.
Prečo je to?
[Študent] Pretože ak je zoznam už je zoradený, potom cez prvú iteráciu
môžete iba zaručiť, že úplne prvý element je najmenej,
a druhá iterácia možné iba zaručiť prvé dva sú
pretože neviete, že zvyšok zoznamu zoradené. Jo >>.
Ak predáte v úplne zoradený zoznam, prinajmenšom budete musieť ísť cez všetky prvky
vidieť, že nemusí nič pohyboval.
Takže prechádzajúcej cez zoznam a povedal oh, je to už sú zoradené,
to je nemožné, aby ste vedeli, že to sú zoradené kým zistiť každý prvok
vidieť, že sú v zoradené poradí.
Tak dolná hranica vloženie radiť je Omega n
Čo je najhoršie doba chodu druhu korešpondencie,
Najhorší prípad je veľké O znova?
Takže v najhoršom prípade, ako sa zlúčenie sort beží?
[Študent] N log n Jo >>.
Najrýchlejší všeobecné triedenie algoritmy sú n log n Môžete to urobiť lepšie.
>> Existujú špeciálne prípady, a ak budeme mať čas dnes - ale asi won't -
sme mohli vidieť ten, ktorý robí lepšie ako n log n
Ale vo všeobecnom prípade, nemôžete urobiť lepšie, než n log n
A zlúčiť druh sa stane, že ten, čo by ste mali vedieť o tomto kurze, ktorý je n log n
A tak budeme skutočne vykonávania uvedenej dnes.
A konečne, v nie viac ako tri vety, ako sa výber radenie prácu?
Má niekto bude chcieť odpovedať, a ja počítať svoje vety
pretože ak pôjdete cez 3 -
Pamätá si niekto, výber druhu?
Výber radenie je obvykle docela ľahké si pamätať len z názvu.
Stačí určiť iteráciou cez pole, nájsť, čo najväčšia hodnota alebo najmenší -
bez ohľadu na poradie, ktoré ste triedenie palcov
Takže povedzme, že sme triedenie od najmenšej k najväčšej.
Môžete určiť iteráciou cez pole, hľadá čokoľvek minimálny prvok,
vyberte ju, a potom už len vymeniť to, čo je na prvom mieste.
A potom na druhom priechodu cez pole, pozrite sa na minimálny prvok znovu,
vyberte ju a potom si vymieňať s tým, čo je na druhej pozícii.
Takže sme len zber a výber minimálne hodnoty
a vložením do prednej časti poľa, kým sa triedi.
Otázky týkajúce sa, že?
>> Tie nevyhnutne objaví vo formulároch musíte vyplniť, keď ste podanie PSet.
Tí sú v podstate odpovede na tie.
Dobre, takže teraz kódovanie problémy.
Už som rozoslal cez e-mail - Bolo niekto nedostal tento e-mail? Dobre.
Už som rozoslal cez e-mail na miesto, ktoré sme bude používať,
a ak kliknete na moje meno - takže myslím, že budem na dne
z dôvodu spätnej r - ale ak kliknete na moje meno uvidíte 2 revízie.
Revízia 1 sa bude už som skopírovať a vložiť kód do priestorov
pre hľadanie vec, ktorú budete musieť vykonávať.
A Revízia 2 bude druh vecí, ktoré vykonávame po tom.
Takže môžete kliknúť na mojej revízie 1 a pracovať odtiaľ.
A teraz chceme zaviesť binárne vyhľadávanie.
>> Má niekto chcel len dať pseudokódu na vysokej úrovni vysvetlenie
z toho, čo budeme musieť urobiť pre vyhľadávanie? Jo.
[Študent] Stačí vziať stred poľa a uvidíme, či to, čo ste hľadali
je menšia než alebo viac.
A ak je to menej, idete do polovice, ktorá je menej,
a ak je to viac, môžete ísť do polovice, ktorá je viac a vy to zopakovať, kým stačí si jednu vec.
[Bowden] Jo.
Všimnite si, že naše čísla poľa už je zoradený,
a tak to znamená, že môžeme využiť, že sme mohli najprv skontrolujte,
jo, ja som hľadal číslo 50.
Takže môžem ísť do stredu.
Stredná je ťažké definovať, kedy je to ešte rad vecí,
ale povedzme, že budeme vždy skrátiť na stredu.
Takže tu máme 8 vecí, takže prostrednej bude 16.
Hľadám 50, takže 50 je väčší ako 16 rokov.
Takže teraz môžem v podstate liečiť svoje pole ako týchto prvkov.
Môžem vyhodiť všetko od 16 cez.
Teraz je moja pole je práve táto 4 prvky, a opakujem.
Takže chcem nájsť stred znovu, čo bude 42.
42 je menší ako 50, takže môžem hodiť ďaleko tieto dva prvky.
To je môj zostávajúce pole.
Idem nájsť stred znova.
Myslím, že 50 bol zlý príklad, pretože som bol vždy zahodil veci na ľavej strane,
ale v rovnakej miere, keď som hľadal niečo
a je to menej, než prvok som v súčasnej dobe pri pohľade na,
potom budem vyhadzovať všetko vpravo.
Takže teraz musíme zaviesť, že.
Všimnite si, že musíme prejsť vo veľkosti.
Môžeme tiež nie je nutné hard-kódu veľkosti.
Takže ak sa zbavíme toho # define -
Dobre.
Ako môžem krásne zistiť, čo je veľkosť čísel pole je v súčasnej dobe?
>> Koľko prvkov je v číslach poli?
[Štud] Čísla, držiaky,. Dĺžka?
[Bowden] To neexistuje v C.
Potrebujete. Dĺžka.
Pole nemajú vlastnosti, takže nie je dĺžka vlastnosť polí
že bude len aby vám ako dlho to stane sa.
[Študent] Pozri koľko pamäte má, a rozdeliť podľa toho, ako moc - >> Jo.
Takže, ako môžeme vidieť, koľko pamäte má? >> [Študent] sizeof. Jo >>, sizeof.
Sizeof je operátor, ktorý to bude vrátiť veľkosť čísla poľa.
A to bude ale veľa celé čísla tam sú časy, veľkosť celé číslo
pretože to je to, koľko pamäte je to vlastne nástupu do.
Takže keď chcem na rad vecí v poli,
potom budem chcieť rozdeliť podľa veľkosti na celé číslo.
Dobre. Takže mi umožňuje odovzdať vo veľkosti tu.
Prečo musím odovzdať do veľkosti vôbec?
Prečo nemôžem jednoducho robiť tu int size = sizeof (sena) / sizeof (int)?
Prečo to nefunguje?
[Študent] Nie je to globálne premenná.
[Bowden] Haystack existuje a my sme okolo v číslach ako kope sena,
a toto je predzvesť toho, čo príde. Jo.
[Študent] Haystack je len odkaz na to, tak to by sa vrátil, aký veľký tento odkaz je.
Jo.
Pochybujem, v prednáške, keď ste videli hromadu skutočnosti ešte, že jo?
Práve sme hovorili o tom.
Takže stack je miesto, kde všetky vaše premenné sa bude uložený.
>> Každá pamäť, ktorá je pridelená pre lokálne premenné sa deje v zásobníku,
a každá funkcia má svoj vlastný priestor na zásobníku, vlastný zásobník rám je to, čo sa volá.
Takže hlavná má svoj stack frame a vnútri nej bude existovať tento čísla poľa,
a to bude o veľkosti sizeof (čísla).
Bude to mať veľkosť čísel rozdelených podľa veľkosti prvkov,
ale že všetky životy v zásobníku rámci hlavné je.
Keď zavoláme hľadanie, hľadanie má svoj vlastný zásobník rám,
vlastný priestor pre ukladanie všetkých svojich lokálnych premenných.
Ale tieto argumenty - takže sena nie je kópiou celého tohto poľa.
Nechceme odovzdať v celé pole ako kópia do vyhľadávania.
Je to len odovzdá odkaz na tejto matice.
Takže hľadanie možné prístup k týmto číslam prostredníctvom tohto odkazu.
Je to stále prístup k veci, ktoré žijú vo vnútri zásobníka rámu hlavných je,
ale v podstate, keď sa dostaneme do ukazovateľov, ktoré by malo byť čoskoro,
to je to, čo ukazovátka.
Ukazovatele sú len odkazy na veci, a môžete použiť odkazy na prístup k veci
ktoré sú v zásobníku iných vecí "rámov.
Takže aj keď čísla je miestne hlavné, stále ešte môžeme pristupovať prostredníctvom tohto ukazovateľa.
Ale pretože je to len ukazovateľ a je to len odkaz,
sizeof (Haystack) vráti iba veľkosť odkazu samotného.
To nevráti veľkosť vec je to ukazuje.
To nevráti skutočnú veľkosť čísel.
A tak to nebude fungovať, ako chceme, aby to.
>> Otázky týkajúce sa, že?
Ukazovatele budú preč do významne viac krvavý podrobnejšie v týždňoch prísť.
A to je dôvod, prečo mnoho vecí, ktoré vidíte, väčšina vyhľadávacích vecí alebo triediť veci,
oni takmer všetci budeme musieť vziať skutočnej veľkosti poľa,
pretože v C, nemáme poňatia, čo veľkosť poľa je.
Musíte ručne preniesť dovnútra
A nemožno ručne odovzdať v celom poli, pretože si len prechádzať v odkaze
a nemôže dostať do veľkosti v odkaze.
Dobre.
Takže teraz chceme realizovať to, čo bolo vysvetlené skôr.
Môžete pracovať na ňom za minútu,
a nemusíte sa báť všetko perfektne 100% funkčné.
Stačí napísať do polovičnej pseudokódu pre to, ako si myslíte, že by to malo fungovať.
Dobre.
Nie je potrebné byť úplne hotový s to ešte.
Ale niekto cíti dobre s tým, čo majú tak ďaleko,
ako niečo, čo môžeme pracovať spoločne?
Má niekto chcel dobrovoľne? Alebo som sa náhodne vyberať.
Nemusí to byť priamo v každom ohľade, ale niečo, čo môžeme meniť do funkčného stavu.
[Študent] Jasne. Dobre >>.
Takže môžete ušetriť na revíziu kliknutím na malú ikonu Uložiť.
Ste Ramy, že jo? >> [Študent] Jo. >> [Bowden] Dobre.
Takže teraz môžem zobraziť revíziu a každý môže vytiahnuť revíziu.
A máme tu - Dobre.
Takže rámy šiel s rekurzívne riešenie, ktoré je rozhodne platné riešenie.
Existujú dva spôsoby, ako môžete urobiť tento problém.
Môžete to urobiť iteračné alebo rekurzívne.
Väčšina problémy mi, že môže byť vykonané rekurzívne môže byť tiež vykonané opakované.
Tak tu sme urobili to rekurzívne.
>> Má niekto chcete definovať, čo to znamená, aby sa funkcia rekurzívne?
[Študent] Ak máte funkciu volať seba
a potom volať seba, kým to vyjde s pravdou a pravda. Jo >>.
Rekurzívne funkcie je len funkcia, ktorá volá sama seba.
K dispozícii sú tri veľké veci, ktoré rekurzívne funkcie musia mať.
Prvá z nich je samozrejme, že volá sama seba.
Druhým je base-case.
Takže v určitom okamihu funkcie musí prestať volať sám,
a to je to, čo referenčný prípad je pre.
Tak tu vieme, že by sme mali prestať, mali by sme sa v našom hľadaní
ak je štart rovná koniec - a pôjdeme nad tým, čo to znamená.
Ale nakoniec, posledná vec, ktorá je dôležitá pre rekurzívne funkcie:
funkcie musí nejako priblížiť základnú vec.
Rovnako ako keď ste v skutočnosti aktualizácia nič, keď urobíte druhý rekurzívne volanie,
ak ste doslova volá funkciu znova s ​​rovnakými argumentmi
a žiadne globálne premenné zmenili alebo tak niečo,
budete nikdy nedosiahne základnú vec, v tomto prípade to je zlé.
Bude to nekonečná rekurzia a pretečenie zásobníka.
Ale tu vidíme, že aktualizácia sa deje, pretože sme aktualizáciu kto + koniec / 2,
sme aktualizáciu koniec argumentu tu, sme aktualizáciu počiatočné tvrdenie tu.
Takže vo všetkých rekurzívne volanie sme aktualizáciu niečo. Dobre.
Chcete chodiť nám prostredníctvom riešenia? Iste >>.
Ja používam SearchHelp tak, že zakaždým, keď som túto funkciu volania
Mám štart, kde som hľadal v poli a koniec
, Kde som pohľade na pole.
>> Na každom kroku, kde je to hovorí, že je to stredný element, ktorý je začiatok + koniec / 2,
je, že rovná tomu, čo sme hľadali?
A ak je, potom sme ho našli, a ja myslím, že je odovzdaný do úrovne rekurzie.
A ak to nie je pravda, potom sme skontrolovať, či stredná hodnota poľa je príliš veľká,
v takom prípade sa pozeráme na ľavej polovici poľa tým, že ide od začiatku do strednej indexu.
A inak robíme Koniec polovice.
[Bowden] Dobre.
To znie dobre.
Dobre, takže pár vecí, a skutočne, je to veľmi vysokej úrovni, čo
že budete nikdy vedieť tohto kurzu, ale je to pravda.
Rekurzívne funkcie, vždy budete počuť, že sú zlé riešenie
pretože keď rekurzívne hovoríš príliš veľakrát, získate pretečeniu zásobníka
pretože, ako som už povedal skôr, každá funkcia má svoj vlastný zásobník rám.
Takže každý hovor z rekurzívne funkcie má svoj vlastný zásobník rám.
Takže ak urobíte 1.000 rekurzívne volanie, získate 1.000 zásobník snímok,
a rýchlo sa viesť k nutnosti príliš veľa stack rámy a veci sa rozbijú.
Takže to je dôvod, prečo rekurzívne funkcie sú všeobecne zlé.
Ale tam je pekný podmnožina rekurzívny funkciou tzv tail-rekurzívne funkcie,
a to sa stane, že je príkladom jednej, kde v prípade, že kompilátor vníma tento
a to by malo, myslím, že - v Clang odovzdáte ho the-flag O2
potom si všimnete je to chvost rekurzívne a robiť veci dobre.
>> To bude používať rovnaké fronty rám znovu a znovu pre každú rekurzívne volanie.
A tak, pretože ste pomocou rovnakého zásobníka rám, nemusíte sa obávať
kedy zásobník pretekaniu, a na rovnakú dobu, ako tie povedané vyššie,
kde akonáhle sa vrátite pravda, potom to musí vrátiť do všetkých týchto zásobníka rámov
a 10. výzva na SearchHelp musí vrátiť do 9., sa musí vrátiť do 8..
Takže nie je potrebné sa stane, keď funkcia chvost rekurzívne.
A tak to, čo robí táto funkcia chvost rekurzívne je upozornenie, že pre dané výzvy na searchHelp
rekurzívne volanie, že to robiť, je to, čo sa vracia.
Takže v prvej volanie SearchHelp, sme buď okamžite vráti false,
okamžite vrátiť true, alebo budeme robiť rekurzívne volanie SearchHelp
kde to, čo sa vraciame, je to, čo, že hovor sa vracia.
A my sme nemohli robiť to, ak sme urobili niečo ako int x = SearchHelp, return x * 2,
len nejaký náhodný zmena.
>> Takže teraz to rekurzívne volanie, toto int x = SearchHelp rekurzívne volanie,
je už chvost rekurzívny, pretože to vlastne nemá musieť vrátiť
späť na predchádzajúcu zásobníka ráme tak, že predchádzajúce volanie funkcie
potom môže niečo urobiť s návratovú hodnotu.
Takže to nie je chvost rekurzívne, ale to, čo sme mali predtým, je pekne chvost rekurzívny. Jo.
[Študent] Ak nie je druhá základňa prípad skontrolovať prvý
pretože by mohlo nastať situácia, kedy pri odovzdať argument
ste start = koniec, ale oni sú ihly hodnotu.
Otázka nemôže narazíme na prípad, kedy je koniec ihly hodnota
alebo štart = koniec, primerane, štart = koniec
a vy ste v skutočnosti kontrolovať, že konkrétne hodnoty ešte,
potom začať + koniec / 2 je len tak mať rovnakú hodnotu.
Ale my už sa vrátil false, a nikdy sme vlastne čítal hodnotu.
Takže prinajmenšom v prvom hovore, ak je veľkosť 0, potom chceme vrátiť false.
Ale ak veľkosť je 1, potom začiatok nebude rovnaké konca,
a budeme aspoň skontrolovať jeden prvok.
Ale myslím, že máte pravdu v tom, že môžeme skončiť v prípade, kedy začať + koniec / 2,
Začiatok nakoniec je rovnaký ako začiatok + koniec / 2,
ale nikdy sme vlastne čítal tento prvok.
>> Takže keď sme najprv skontrolovať, je stredná prvok hodnotu, ktorú hľadáte,
potom môžeme okamžite vrátiť true.
Else, ak sú rovnaké, potom je tu nemá zmysel pokračovať
pretože sme len tak aktualizáciu na prípad, kedy sme na jednej prvku poľa.
Ak tento jediný prvok nie je ten, ktorého hľadáme,
potom je všetko v poriadku. Jo.
[Študent] vec je, že od tej doby veľkosť je v skutočnosti väčší ako počet prvkov v poli,
tam je už offset - >> Tak bude veľkosť -
[Študent] povedať, či pole je veľkosť 0, potom SearchHelp skutočne kontrolovať Haystack 0.
na prvú výzvu.
Pole má veľkosť 0, takže 0 je - >> Jo.
Je tu ďalšia vec, ktorá - to by mohlo byť dobré. Poďme premýšľať.
Takže ak pole mal 10 článkov a prostredný budeme kontrolovať, je index 5,
takže sme kontrolu 5, a povedzme, že hodnota je menšia.
Takže sme hádzať všetko preč od 5 dopredu.
Takže začať + end / 2 bude náš nový koniec,
tak jo, to vždy zostať aj po skončení tohto poľa.
Ak je to prípad, kedy to bolo párne alebo nepárne, potom by sme zistili, či, povedzme, 4,
ale my sme stále vyhadzujete -
Tak jo, koniec je vždy bude za skutočného konca poľa.
Takže prvkov sme so zameraním na, koniec je vždy bude jeden po tom.
A ak sa niekedy začiatok rovnaký koniec, my sme v poli veľkosti 0.
>> Ďalšia vec, ktorú som myslel je, že sme aktualizáciu štart sa začať + koniec / 2,
tak to je pravda, že mám problémy s, kde začať + koniec / 2
je element sme kontrolu.
Povedzme, že sme mali 10-prvok poľa. Čokoľvek.
Takže začať + end / 2 bude niečo ako je tento,
a ak to nie je hodnota, že chceme aktualizovať.
Hodnota je väčšia, takže chceme sa pozrieť na tejto polovice poľa.
Tak ako sme aktualizáciu začiatok, sme aktualizáciu štart teraz tento prvok.
Ale to sa môže stále fungovať, alebo prinajmenšom, môžete tak urobiť začiatok + koniec / 2 + 1.
[Študent] Nemusíte byť začať + koniec [nepočuteľné] >> Jo.
Sme už skúmali tento prvok a viem, že to nie je ten, ktorého hľadáme.
Takže nepotrebujeme aktualizovať štart je tento prvok.
Môžeme len preskočiť a aktualizovať začať byť tento prvok.
A je tam niekedy prípad, povedzme, že to bolo koniec,
takže potom kto by to, kto + koniec / 2 by to,
kto + koniec - Jo, myslím, že to môže skončiť v nekonečnej rekurzie.
Povedzme, že je to len pole o veľkosti 2 alebo pole o veľkosti 1. Myslím, že to bude fungovať.
Takže v súčasnej dobe, štart je tento prvok a koniec je 1 mimo neho.
Takže prvok, ktorý budeme kontrolovať, je to jedno,
a potom, keď sme aktualizáciu začiatok, sme aktualizáciu štart byť 0 + 1/2,
ktorý sa bude do konca nás späť s počiatočnou že tento prvok.
>> Takže sme kontrolu rovnaký prvok znovu a znovu.
Tak toto je prípad, kedy každá rekurzívne volanie, musí byť skutočne aktualizovať niečo.
Takže musíme urobiť začiatok + koniec / 2 + 1, inak je tu prípad
kde sme v skutočnosti aktualizácia začiatok.
Všetci vidia, že?
Dobre.
Má niekto nejaké otázky týkajúce sa tohto roztoku alebo akékoľvek ďalšie komentáre?
Dobre. Má niekto iteratívny riešenie, ktoré môžeme všetci pozrieť na?
Sme to všetci rekurzívne?
Alebo tiež myslím, že ak ste si otvorili jej, potom by ste mali mať prepísať svoj predchádzajúci.
Má to automaticky ukladať? Nie som pozitívne.
Má niekto sa opakujúce?
Môžeme prejsť nej spoločne, ak nie.
Myšlienka bude rovnaké.
Iteračné riešenie.
Budeme chcieť, aby v podstate robiť rovnakú myšlienku
tam, kde chceme sledovať nové konci poľa a nový začiatok poľa
a to, že znova a znova.
A či to, čo sme sledovaní ako na začiatku a na konci vždy pretínajú,
potom sme nenašli, a môžeme sa vrátiť false.
Tak ako to mám urobiť, že? Každý, kto má návrhy alebo kód pre mňa vytiahnuť?
[Študent] Do slučky while. Jo >>.
Budeš chcieť urobiť slučku.
>> Mali ste kód, ktorý som mohol vytiahnuť, alebo čo si chcel navrhnúť?
[Študent] Myslím, že áno. >> Dobre. To robí veci jednoduchšie. Aké bolo vaše meno?
[Študent] Lucas.
Revízia 1. Dobre.
Najnižšia je to, čo sme nazvali začať skôr.
Up nie je to, čo sme nazvali koniec pred.
V skutočnosti, koniec je teraz v matici. Je to prvok, by sme mali zvážiť.
Takže nízka je 0 až je veľkosť poľa - 1,
a teraz sme slučky, a my sa kontrola -
Myslím, že môžete chodiť cez neho.
Aký bol váš myslenie cez to? Prechádzka nás prostredníctvom kódu.
[Študent] Jasne. Pozrite sa na Haystack hodnotu v strede a porovnať ho s ihlou.
Takže ak je to väčšie než vaše ihly, potom budete chcieť - oh, vlastne, že by mala byť spätne.
Budeš chcieť vyhodiť pravú polovicu, a tak jo, to by malo byť tak.
[Bowden] Tak by to malo byť menej? Je to to, čo si povedal? >> [Študent] Jo.
[Bowden] Dobre. Menej.
Takže ak to, čo sa pozeráme na menšie, než to, čo chceme,
tak jo, chceme vyhodiť ľavú polovicu,
čo znamená, že sa aktualizácia všetko Uvažujeme
Pohybom nízko na pravej strane poľa.
To vyzerá dobre.
Myslím, že to má rovnaký problém, ktorý sme si povedali na predchádzajúcu,
, Kde v prípade nízkej je 0, a až je 1, potom nízky + až / 2 bude nastavený tak, aby sa to isté znova.
>> A aj keď to nie je tento prípad, je ešte účinnejšia, prinajmenšom
len vyhodiť prvok sme práve pozrel na ktorom vieme, že je v poriadku.
Tak nízka + hore / 2 + 1 - >> [Študent] To by malo byť naopak.
[Bowden] Alebo by to malo byť - 1 a druhý by mal byť + 1.
[Študent] A by mal byť dvojaký znamienko rovnosti. >> [Bowden] Jo.
[Študent] Jo.
Dobre.
A konečne, teraz, keď máme túto + 1-1 vec,
je to - to nemusí byť - je to vôbec možné, nízka skončiť s hodnotou vyššou ako hore?
Myslím, že jediný spôsob, ako sa môže stať - je to možné? >> [Študent] Neviem.
Ale ak to bude skrátený a potom dostane mínus 1 a potom - >> Jo.
[Študent] To by možno si spackal.
Myslím, že by to malo byť dobré len preto, že
pre to, aby skončil nižšie, budú musieť byť so rovnať, myslím.
Ale ak sú rovnaké, potom by sme urobili while začať s
a my sme sa vrátili hodnotu. Takže myslím, že sme v pohode teraz.
Všimnite si, že aj keď je tento problém už rekurzívne,
rovnaký druh myšlienok platí, kde môžeme vidieť, ako to tak ľahko prepožičiava
k rekurzívne riešenie tým, že sme len aktualizuje indexy znova a znova,
robíme problém menšie a menšie, my sa sústredíme na podmnožinu poľa.
[Študent] Pri nízkej je 0, a až je 1, by sa obaja 0 + 1/2, čo by na 0,
a potom jeden by + 1, jeden by byť - 1.
[Študent] Kde sme kontrolu rovnosti?
Ako v prípade, že prostredný je vlastne ihla?
Nie sme v súčasnej dobe robí, že? Oh!
Pokiaľ to -
Áno. Nemôžeme len tak urobiť test sem, pretože povedzme, že prvé stredu -
[Študent] Je to vlastne ako nevyhadzujte viazané.
Takže ak máte vyhodiť viazaný, budete musieť skontrolovať prvej alebo čokoľvek.
Ah. Jo. >> [Študent] Jo.
Takže teraz sme zahodil ten sme v súčasnej dobe sa pozrel na,
čo znamená, že teraz musíme tiež mať
if (Haystack [(low + up) / 2] == ihly), potom môžeme vrátiť true.
A či som dal inam, alebo len v prípade, to znamená doslova to isté
pretože by sa vrátili pravda.
Tak som si dal else if, ale to nevadí.
>> Takže ešte ak to, inak to, a to je bežná vec robím
, Kde aj keď je to v prípade, keď je všetko dobré tu,
ako nízka, môže byť nikdy vyššia ako hore, to nestojí za úvaha o tom, či je to pravda.
Takže sa môže tiež hovoriť pri nízkej je menší ako alebo rovný
alebo pri nízkej je menšia ako
takže v prípade, že sú stále rovnaké, alebo nízka stane ujsť,
potom môžeme vymaniť z tejto slučky.
Otázky, obavy, názory?
Dobre. To vyzerá dobre.
Teraz chceme urobiť akúsi.
Ak pôjdeme do mojej druhej revízii, vidíme tie isté čísla,
ale teraz sú už v zoradené poradí.
A my chceme zaviesť akúsi pomocou akýkoľvek algoritmus v O n log n
Takže, ktoré algoritmus si myslíte, že by sme mali zaviesť tu? >> [Študent] Merge sort.
[Bowden] Jo. Zlúčiť sort je O (n log n), takže to je to, čo budeme robiť.
A problém bude dosť podobne,
kde sa ľahko požičiava seba k rekurzívne riešenie.
Môžeme tiež prísť s iteratívny riešenie, ak chceme,
ale rekurzia bude jednoduchšie tu a mali by sme robiť rekurziu.
Myslím, že budeme prechádzať radiť zlúčenie prvý,
hoci tam je krásne video o radiť zlúčenie už. [Smiech]
Takže zlúčiť druh existuje - Som plytvanie toľko tejto práce.
Oh, je tu len jeden vľavo.
Tak zlúčenie.
Ó, 1, 3, 5.
Dobre.
Merge má dva samostatné pole.
Individuálne tieto dve polia sú obaja zoradené.
Takže toto pole, 1, 3, 5, zoradené. Toto pole, 0, 2, 4, zoradené.
Čo teraz zlúčenie mali urobiť, je spojiť ich do jedného poľa, ktorá je sama zoradené.
Takže chceme pole o veľkosti 6, ktorá sa bude mať tieto prvky vnútri neho
v zoradenie poradí.
>> A tak môžeme využiť k tomu, že tieto dva polia sú zoradené
k tomu v lineárnom čase,
lineárny čas význam v prípade, že je veľkosť poľa x, a to je veľkosť y,
potom celkový algoritmus by mal byť O (x + y). Dobre.
Tak návrhy.
[Študent] Mohli by sme začať zľava?
Takže budete dal 0 dolu a potom 1 a potom tu ste na 2.
Takže je to niečo ako, že máte kartu, ktorá sa pohybuje doprava. >> [Bowden] Jo.
Pre obidva z týchto polí, ak sa sústrediť len na krajnom prvku.
Vzhľadom k tomu, ako polia sú zoradené, vieme, že tieto 2 prvky
sú najmenšie prvky oboch poli.
To znamená, že 1 z týchto 2 prvkov musí byť najmenší prvok v našej zlúčené polia.
To len tak sa stane, že najmenší je jedno na pravej tejto doby.
Tak sme sa 0, vložte ho na ľavej strane, pretože 0 je menšia ako 1,
takže si 0, vložte ju do našej prvej pozície, a potom sme ich aktualizuje
aby teraz sústrediť na prvý prvok.
A teraz sme sa opakovať.
Takže teraz sme tieto 2 a 1. 1 je menšie, takže vložíme 1.
My aktualizovať tento ukazovateľ aby ukazoval na toho chlapa.
Teraz sme to znovu, tak 2. To bude aktualizovať, porovnanie týchto 2, 3.
Táto aktualizácia, potom 4 a 5.
Tak to je zlúčenie.
>> Malo by byť absolútne jasné, že je lineárny čas, pretože sme jednoducho ísť cez každý prvok raz.
A to je najväčší krok k realizácii zlúčenia radenie to robí.
A to nie je tak ťažké.
A pár vecí robiť starosti, je povedzme sme zlúčenie 1, 2, 3, 4, 5, 6.
V tomto prípade sme skončili v scenári, kde tento človek bude menší,
potom aktualizovať tento ukazovateľ, toto bude menšie, je aktualizuje,
toto je menšie, a teraz budete musieť uznať
keď ste skutočne spustiť z prvkov, ktoré majú v porovnaní s
Pretože sme už používali tento celého poľa,
všetko v tomto poli je teraz práve vložené do tu.
Takže ak sa niekedy dostanete do bodu, kedy je jeden z našich polí úplne zlúčené už,
potom len vziať všetky prvky druhej poľa a vložiť do konca poľa.
Takže môžeme len vložiť 4, 5, 6. Dobre.
To je jedna vec, dávať si pozor na.
Vykonávacie ktorý by mal byť krok 1.
Zlúčiť radiť potom na základe toho, že je to 2 kroky, 2 hlúpe kroky.
Poďme dať toto pole.
Takže zlúčiť druh, krok 1 je rekurzívne rozdeliť pole na polovice.
Takže rozdeliť toto pole na polovice.
V súčasnej dobe máme 4, 15, 16, 50 a 8, 23, 42, 108.
A teraz sme to znova a rozdelili sme ich do polovice.
Ja si len to na tejto strane.
Takže 4, 15 a 16, 50.
Radi by sme robiť rovnakú vec znovu tu.
A teraz sme sa rozdelili do polovice znovu.
A máme 4, 15, 16, 50.
Tak to je náš základný scenár.
Akonáhle polia sú veľkosti 1, potom prestať s rozdelením do polovice.
>> Čo teraz budeme robiť s tým?
Sme skončiť to bude tiež rozdeliť do 8, 23, 42, a 108.
Takže teraz, že sme v tomto bode, teraz kroku dve radiť zlúčenie je len zlúčenie dvojice zoznamov.
Takže chceme zlúčiť tieto. Práve sme zavolať zlúčenie.
Vieme, že zlúčenie sa vrátiť tieto v zoradené poradí.
4, 15.
Teraz chceme zlúčiť tieto, a že vráti zoznam s tými v zoradenie poradí,
16, 50..
Spojíme ty - Nemôžem písať - 8, 23 a 42, 108.
Takže máme zlúčené dvojica raz.
Teraz už len zlúčiť znovu.
Všimnite si, že každý z týchto zoznamov je zoradená v sebe,
a potom môžeme len zlúčiť tieto zoznamy získať zoznam veľkosti 4, ktorý je zoradená
a spojiť tieto dva zoznamy získať zoznam veľkosti 4, ktorá je zoradená.
A konečne, môžeme zlúčiť tieto dva zoznamy veľkosti 4, aby si jeden zoznam veľkosti 8, ktorá je zoradená.
Takže vidieť, že je to celkovo n log n, už sme videli, že zlúčenie je lineárne,
takže keď máme čo do činenia s zlúčením táto, takže rovnako ako celkové náklady na zlúčenie
týchto dvoch zoznamov je len 2, pretože -
Alebo dobre, je to O n, ale n je tu len tieto 2 prvky, takže je to 2.
A tieto 2 bude 2 a tieto 2 bude 2 a tieto 2 bude 2,
takže cez všetky splýva, ktoré musíme urobiť, sme sa nakoniec robiť n
Ako 2 + 2 + 2 + 2 je 8, čo je n,
takže náklady na zlúčenie v tejto sade je n
A potom to isté tu.
Budeme zlúčenie týchto 2, potom tieto 2, a osobne to zlúčenie bude trvať štyri operácie,
to zlúčenie bude trvať štyri operácie, ale opäť, medzi všetkými z nich,
sme sa nakoniec zlučovanie n celkom veci, a tak tento krok trvá n
A tak každá úroveň má n prvkov je zlúčené.
>> A koľko úrovní je tam?
Na každej úrovni, naše pole rastie podľa veľkosti 2.
Tu naše polia sú veľkosti 1, tu sú veľkosti 2, tu sú veľkosti 4,
a napokon, sú veľkosti 8.
Takže, pretože to je zdvojenie, tam sa bude celkom log n z týchto úrovní.
Takže s log n úrovní, každá jednotlivá úroveň pričom n celkom operácie,
dostaneme log n n algoritmus.
Otázky?
Ľudia už dosiahla pokrok v tom, ako to urobiť čo?
Je niekto už v stave, kedy som si len vytiahnuť svoj kód?
Môžem dať chvíľku.
Tento bude dlhší.
Vrelo odporúčam opakovať -
Nemusíte robiť rekurziu pre zlúčenie
pretože robiť rekurziu pre zlúčenie, budete musieť prejsť veľa rôznych veľkostí.
Môžete, ale je to otravné.
Ale rekurzia pre radiť sám o sebe je celkom jednoduché.
Stačí zavolať doslova akousi na ľavej polovici, sort na pravej polovici. Dobre.
Každý, kto má niečo, čo som si vytiahnuť hore?
Inak ja dám minútku.
Dobre.
Každý, kto má niečo, čo môžeme pracovať s?
Inak budeme len s týmto pracujete a potom rozbaľte odtiaľ.
>> Každý, kto má viac než to, že som si vytiahnuť?
[Študent] Jo. Môžete vytiahnuť moje. >> Dobre.
Áno!
[Študent] Bola tam kopa podmienok. >> Oh, strieľať. Môžeš -
[Študent] Musím zachrániť ju. Jo >>.
Tak sme urobili to zlúčenie oddelene.
Oh, ale to nie je tak zlé.
Dobre.
Takže druh je sám o sebe len volanie mergeSortHelp.
Vysvetlite nám, čo mergeSortHelp robí.
[Študent] MergeSortHelp celkom veľa robí dva hlavné kroky,
ktorý je vyriešiť každú polovicu poľa a potom zlúčiť oba.
[Bowden] Dobre, tak mi za sekundu.
Myslím, že to - >> [Študent] musím -
Jo. Som niečo chýba.
V zlúčenie, som si uvedomil, že musím vytvoriť nové pole
pretože som nemohol urobiť to na mieste. Áno >>. Nemôžete. Opraviť.
[Študent] Tak som vytvoriť nové pole.
Zabudol na konci sa ponorí znovu zmeniť.
Dobre. Potrebujeme nové pole.
V radiť zlučovacie, je to takmer vždy pravda.
Časť nákladov na lepšiu algoritmu časovo
je takmer vždy museli použiť trochu viac pamäte.
Tak tu, bez ohľadu na to, ako to robíš zlúčiť druh,
budete nevyhnutne potrebovať nejaké extra pamäť.
On alebo ona vytvorila nové pole.
A potom povieš na konci sme stačí skopírovať nové pole do pôvodného poľa.
[Študent] Myslím, že áno, jo.
Neviem, či to funguje, pokiaľ ide o počítanie odkazu alebo čokoľvek iné -
Jo, bude to fungovať. >> [Študent] Dobre.
Bolo pre vás skúste to? >> [Študent] Nie, ešte nie. Dobre >>.
Skúste ju spustiť, a potom budem hovoriť o tom na chvíľu.
[Študent] Musím mať všetky funkčné prototypy a všetko, že jo?
Funkčné prototypy. Oh, myslíš ako - Áno.
Zoradiť volá mergeSortHelp.
>> Tak, aby pre radenie volať mergeSortHelp, musí mergeSortHelp buď boli definované
pred radiť alebo si len potrebujete prototyp. Stačí len skopírovať a vložiť, že.
A podobne, mergeSortHelp volá zlúčenie,
ale merge nie je doteraz definované, takže sa môžeme len nechať mergeSortHelp vedieť
že to, čo zlúčenie bude vyzerať, a tým to hasne.
Tak mergeSortHelp.
Máme problém, tu, kde nemáme základnú vec.
MergeSortHelp je rekurzívny, takže každý rekurzívne funkcie
bude potrebovať nejaký základné veci vedieť, kedy prestať rekurzívne volať sám.
Čo je náš základný scenár bude tu? Jo.
[Študent] Ak je veľkosť 1? >> [Bowden] Áno.
Tak ako sme videli tu, zastavili sme sa rozdelenie poľa
Akonáhle sme sa dostali do polí veľkosti 1, čo nevyhnutne sú zoradené sami.
Takže ak veľkosť zodpovedá 1, vieme, že pole už je zoradený,
takže môžeme len vrátiť.
>> Všimnite si, že je neplatné, a tak sme sa nevracia nič konkrétneho, len sme sa vrátiť.
Dobre. Tak to je náš základný scenár.
Myslím, že náš základný scenár by tiež mohla byť, keby sme sa náhodou zlúčenie poľa veľkosti 0,
sme asi chcú zastaviť na nejakom mieste,
takže stačí povedať veľkosti menšej ako 2 alebo nižšia ako alebo rovná 1
tak, že to bude fungovať za každé pole sa.
Dobre.
Tak to je náš základný scenár.
Teraz už chcete chodiť nás cez zlúčenie?
Čo všetky tieto prípady znamenajú?
Až tu, my sme len robí rovnakú myšlienku, -
[Študent] musím byť okolo veľkosti so všetkými hovory mergeSortHelp.
Pridal som veľkosť ako ďalšie primárne a nie je to tam, ako je veľkosť / 2.
[Bowden] Oh, veľkosť / 2, veľkosť / 2. >> [Študent] Jo, a tiež vo vyššie uvedenom funkciu.
[Bowden] Tu? >> [Študent] Len veľkosť. >> [Bowden] Oh. Veľkosť, veľkosť? >> [Študent] Jo.
[Bowden] Dobre.
Nechajte ma premýšľať o sekundu.
Páči narazíme na problém?
Sme vždy zaobchádzať ľavici ako 0. >> [Študent] č
To je zle taky. Prepáčte. Malo by to byť začiatok. Jo.
[Bowden] Dobre. Páči sa mi, že lepšie.
A koniec. Dobre.
Takže teraz chceš prejsť nám prostredníctvom zlúčenie? >> [Študent] Dobre.
Len som prechádzal tohto nového poľa, ktoré som vytvoril.
Jeho veľkosť je veľkosť časti poľa, ktoré chceme triediť
a snaží sa nájsť prvok, ktorý by som mal dať v novom poľa kroku.
Tak k tomu, že v prvej som kontrole, či ľavá polovica poľa pokračuje mať žiadne ďalšie prvky,
a ak tomu tak nie je, potom ísť dole k tomuto inému stavu, ktorý práve hovorí, že
v poriadku, musí byť v pravom poli, a dáme, že v súčasnej indexu newArray.
>> A potom inak, ja som kontrolu, či pravá strana pole je tiež skončil,
v takom prípade som dal v ľavej.
To by mohlo byť skutočne nutné. Nie som si istý.
Ale rovnako, ďalšie dva kontrola, ktorú z tých dvoch sa menšie doľava alebo doprava.
A tiež v každom prípade, ja navýšením podľa toho, čo zástupný Aj zvyšovať.
[Bowden] Dobre.
To vyzerá dobre.
Má niekto nejaké pripomienky alebo obavy alebo otázky?
Takže štyri prípady, ktoré musíme priviesť veci do jednoduchého bytia - alebo to vyzerá ako päť -
ale musíme zvážiť, či doľava pole je vyčerpať čo musíme zlúčiť,
či právo pole je vyčerpať čo musíme zlúčiť -
Som ukázal na nič.
Takže nech ľavej pole došla veci alebo právo poľa došiel vecí.
To sú dva prípady.
Potrebujeme tiež triviálne prípad, či ľavica, čo je menšie ako správnu vec.
Potom chceme zvoliť ľavej vec.
To sú prípady.
Tak toto mal pravdu, tak je to.
Array vľavo. Je to 1, 2, 3. Dobre. Tak jo, to sú štyri veci, ktoré sme mohli chcieť robiť.
A nebudeme ísť cez iteračné riešenie.
Neodporúčal by som -
Zlúčenie druh je príklad funkcie, ktorá je ako to chvost rekurzívne,
to nie je ľahké, aby sa to tail rekurzívne,
ale tiež to nie je ľahké, aby sa to iteratívny.
To je veľmi jednoduché.
Táto implementácia druhu korešpondencie,
zlúčenie, bez ohľadu na to, čo robíte, budete stavať zlúčenie.
>> Takže zlúčiť druh postavený na vrchole zlúčenie rekurzívne je práve táto tri riadky.
Iteratívne, je to viac nepríjemné a ťažké premýšľať o
Ale všimnite si, že to nie je chvost rekurzívny, pretože mergeSortHelp - keď to sama hovorí -
stále musí robiť veci po tomto rekurzívne volanie vráti.
Takže to stack frame musí naďalej existovať aj po volaní tejto.
A potom, keď budete volať, musí stack frame naďalej existovať
pretože aj po tomto hovoru, stále potrebujeme zlúčiť.
A to je triviálne, aby sa tento chvost rekurzívne.
Otázky?
Dobrá.
Takže návrat k radenia - oh, sú dve veci, ktoré chcem ukázať. Dobre.
Vráťme sa späť k druhu, urobíme to rýchlo.
Alebo hľadajte. Radiť? Zoradiť. Jo.
Vráťme sa späť do začiatkov druhu.
Chceme vytvoriť algoritmus, ktorý triedi pole pomocou ľubovoľného algoritmu
v O n
Tak, ako je to možné? Má niekto nejaký druh -
Som naznačil skôr u -
Ak sa chystáme zlepšenie z n log n na O n,
sme zlepšili naše algoritmus časovo,
čo znamená, že to, čo budeme musieť urobiť, aby sa na to?
[Študent] Space. Jo >>. Budeme používať viac priestoru.
A to aj len viac priestoru, je to exponenciálne viac priestoru.
Takže si myslím, tento typ algoritmu je pseudo niečo, pseudo polynómov -
pseudo - Nemôžem si spomenúť. Pseudo niečo.
Ale je to preto, že musíme použiť toľko priestoru
že to možno dosiahnuť, ale nie je reálne.
>> A ako môžeme dosiahnuť?
Toho môžeme dosiahnuť, ak sa zaručí, že určitá element v poli
pod určitú veľkosť.
Takže povedzme, že veľkosť je 200,
akýkoľvek prvok v poli je nižšia ako veľkosť 200.
A to je skutočne veľmi realistický.
Môžete veľmi ľahko mať pole, ktoré viete, že všetko, čo v ňom
bude menší ako nejaké číslo.
Ako keď mám nejaký úplne masívne vektor, alebo tak niečo
ale viete, všetko bude medzi 0 a 5,
potom to bude výrazne rýchlejší urobiť.
A viazané na niektorý z prvkov je 5,
tak tento odhad, že je to, ako moc pamäte budete používať.
Takže viazaný je 200.
Teoreticky je vždy viazaný od celé číslo môže byť až 4000000000,
ale to je nereálne, pretože potom by sme používať miesto
na poradie 4000000000. Tak to je nereálne.
Ale tu budeme hovoriť naše viazaný je 200.
Trik, ako to robí v O n je urobíme ďalšie pole s názvom počty veľkosti VIAZANIA.
Takže vlastne, to je skratka pre - Ja vlastne neviem, či zvonenie to robí.
Ale v GCC na prinajmenšom - Som za predpokladu, že zvonenie to robí taky -
to bude len inicializácii celého poľa, aby sa 0s.
Takže ak nechcem robiť, potom by som mohol samostatne urobiť for (int i = 0;
i <Bound; i + +) a počíta [i] = 0;
Takže teraz je všetko inicializovaná na 0.
Aj iterácii svoje pole,
a to, čo robím, je počítam počet každého - Poďme sem.
Máme 4, 15, 16, 50, 8, 23, 42, 108.
Čo Počítam je počet výskytov každého z týchto prvkov.
Poďme skutočne pridať pár ďalších tu s niektorými opakovania.
Takže hodnota, ktorú máme, je hodnota, ktorá bude pole [i].
Takže val by mohol byť 4 alebo 8 alebo čokoľvek iného.
A teraz som počítať, koľko z tejto hodnoty som videl,
takže sa počíta [val] + +;
Po to urobiť, počíta sa bude vyzerať ako 0001.
Poďme urobiť počíta [val] - RIADIŤ + 1.
>> Teraz to je len zodpovedať za to, že sme počnúc 0.
Takže ak 200 bude naše najväčšie číslo,
potom 0-200 je 201 vecí.
Takže sa počíta, bude to vyzerať, ako 00001, pretože máme jeden 4.
Potom budeme mať 0001, kde budeme mať 1 v 8. indexu počtu.
Budeme mať 2 v 23. indexu počtu.
Budeme mať 2 v indexe 42. počte.
Takže môžeme použiť počet.
Takže num_of_item = počíta [i].
A ak num_of_item je 2, to znamená, že chceme vložiť 2 z počtu i
do nášho triedenom poli.
Takže musíme sledovať, ako ďaleko sme sa do poľa.
Takže index = 0.
Array - budem len písať.
Počty -
array [index + +] = i;
Je to to, čo chcem? Myslím, že je to to, čo chcem.
Áno, to vyzerá dobre. Dobre.
Takže si všetci pochopili, čo je cieľom mojej počíta pole je?
To počíta počet výskytov každého z týchto čísel.
Potom som iterácie, ktorá sa počíta polia,
a tá pozícia v poli sa počíta
je počet aj to, že by sa mal objaviť v mojom triedenom poli.
To je dôvod, prečo sa počty 4 bude 1
a počty 8 bude 1, počty 23 bude 2.
Tak to je, koľko z nich chcem vložiť do môjho triedenom poli.
Potom som to.
Som vloženie num_of_item aj to do môjho triedenom poli.
>> Otázky?
A tak opäť, je to lineárny čas, pretože sme sa práve iterácia cez to raz,
ale je to tiež lineárna v tom, čo toto číslo sa stane byť,
a tak to silne závisí na tom, čo je viazaný.
S viazaný na 200, to nie je tak zlé.
Ak váš viazaný bude 10.000, potom je to trochu horšie,
ale ak vaša spojený sa bude 4000000000, to je absolútne nereálne
a toto pole bude musieť byť veľkosti 4 miliardy korún, čo je nereálne.
Tak to je to. Otázky?
[Nepočuteľné Študent odpoveď] >> Dobre.
Uvedomil som si, jednu vec, keď sme išli cez.
Myslím, že problém bol v Lucasovi a pravdepodobne jeden každý sme videli.
Úplne som zabudla.
Jediné, čo som chcel vyjadriť, je, že keď máte čo do činenia s vecami, ako je indexov,
nikdy naozaj vidieť, keď píšete pre sláčiky,
ale technicky, keď máte čo do činenia s týmito indexy,
mali by ste skoro vždy riešiť s celých čísel bez znamienka.
Dôvodom pre to je, keď máte čo do činenia s podpísanými celé čísla,
takže ak máte 2 podpísané celé čísla a pridajte ich spolu
a oni skončí príliš veľké, potom vy skončíte s záporné číslo.
Takže to je to, čo integer overflow je.
>> Ak môžem pridať 2000000000 a 1000000000, som skončiť s negatívnym 1000000000.
To je, ako celé čísla pracovať na počítačoch.
Takže problém s použitím -
To je v poriadku s výnimkou prípadov nízka stane byť 2 miliardy až sa stane na 1 mld Sk,
potom bude negatívne 1 miliarda a potom budeme deliť, že 2
a skončiť s negatívnym 500000000.
Tak toto je len problém, ak sa stalo, že sa hľadá cez pole
miliárd vecí.
Ale ak low + až sa stane pretečeniu, potom je to problém.
Akonáhle sme, aby boli nesignováno, potom 2 miliárd eur 1000000000 je 3 mld Sk.
3000000000 deleno 2 je 1,5 mld Sk.
Takže akonáhle to unsigned, všetko je perfektné.
A tak to aj problém, keď ste písanie pre slučky,
a vlastne, to asi robí to automaticky.
To bude vlastne len kričať na vás.
Takže ak toto číslo je príliš veľký, aby sa počas jedinej celé číslo, ale to by sa zmestili do celé číslo bez znamienka,
bude kričať na teba, tak to je dôvod, prečo ste nikdy naraziť na problém.
Môžete vidieť, že index je nikdy nebude negatívne,
a tak, keď ste iterácia cez pole,
môžete takmer vždy povedať, unsigned int i, ale nemáte naozaj musieť.
Veci idú do práce skoro rovnako dobre.
Dobre. [Šepká] Aký je čas?
Posledná vec, ktorú som chcel ukázať - a ja to jednoducho urobiť to naozaj rýchlo.
Vieš, ako sme # define, takže môžeme # define MAX ako 5 alebo tak niečo?
Poďme to urobiť MAX. # Define viazaný ako 200. To je to, čo sme robili pred.
To definuje konštantu, ktorá je len tak skopírovať a vložiť
všade tam, kde sa stalo písať VIAZANIA.
>> Takže môžeme skutočne urobiť viac s # definuje.
Môžeme # define funkcie.
Sú to naozaj funguje, ale budeme im hovoriť funkcie.
Príkladom by mohol byť niečo ako MAX (x, y) je definovaná ako (x <y y:? X). Dobre.
Takže by ste mali zvyknúť na syntax ternárnu operátor,
ale je x menšie ako y? Návrat y, inak vráti x.
Takže môžete vidieť, môžete túto samostatnú funkciu,
a funkcia môže byť ako bool MAX trvá 2 argumenty, vrátiť.
To je jeden z najčastejších z nich vidím urobil takhle. Hovoríme im makrá.
To je makro.
To je len syntaxe pre neho.
Môžete napísať makro robiť, čo chcete.
Tie často vidieť makrá pre ladenie printfs a tak.
Takže typu printf, existujú špeciálne konštanty v C ako podčiarknutie LINE podčiarkovník,
2 podčiarkuje LINE podčiarkovník,
a tam je tiež myslím, že 2 podčiarkovníky FUNC. To by mohlo byť ono. Niečo také.
Tieto veci budú nahradené s názvom funkcie
alebo číslo linky, ktoré ste na.
Často, môžete napísať ladenie printfs, že tu dole som mohol potom len napísať
DEBUG a vytlačí sa číslo riadku a funkcie, ktoré som náhodou byť v
že došlo, že DEBUG vyhlásenie.
A môžete tiež vytlačiť iné veci.
Takže jedna vec, ktorú by mal dávať pozor, je, či som náhodou # define DOUBLE_MAX
niečo ako 2 * y a 2 * x.
Takže z akéhokoľvek dôvodu, ste náhodou k tomu, že veľa.
Tak, aby to makro.
To je skutočne zlomené.
Nazval by som to tým, že robí niečo ako DOUBLE_MAX (3, 6).
Takže to, čo by mala byť vrátená?
[Študent] 12.
Áno, mala 12 byť vrátené, a 12 je vrátená.
3 bude nahradené za x, dostane 6 nahrádza pre y, a vraciame sa 2 * 6, ktorá je 12.
Teraz čo toto? Čo by sa malo vrátiť?
[Študent] 14. V ideálnom prípade >>, 14.
Problém je, že ako hash definuje prácu, pamätajte, že je to doslovný kopírovanie a vkladanie
zo dňa skoro všetko, takže to, čo to bude vykladať ako
je 3 menej ako 1 plus 6, 2 krát 1 plus 6, 2 krát 3.
>> Takže z tohto dôvodu takmer vždy zabaliť všetko v zátvorkách.
Akákoľvek premenná takmer vždy zabaliť v zátvorkách.
Existujú prípady, keď nemáte k, ako ja viem, že nemám potrebu k tomu, že tu
pretože menej, než je do značnej miery vždy len chodiť do práce,
aj keď to nemusí byť dokonca pravda.
Ak je niečo smiešne ako DOUBLE_MAX (1 == 2),
potom, že sa to byť nahradený s 3 menej ako 1 rovná rovná 2,
a tak potom to bude robiť 3 menej ako 1, to, že rovné 2,
čo je to, čo chceme.
Tak, aby sa zabránilo operátor prednosť problémy,
vždy zabaľte v zátvorkách.
Dobre. A to je to, 5:30.
Ak máte akékoľvek otázky týkajúce sa PSet, dajte nám vedieť.
To by mala byť zábava, a hacker vydanie je tiež oveľa realistickejšie
ako hackerské vydanie v minulom roku, tak dúfame, že veľa z vás to skúsiť.
V minulom roku to bol veľmi zdrvujúce.
>> [CS50.TV]