[Powered by Google Translate] [Oddelek 3 - Več Udobna]
[Rob Bowden - Harvard University]
>> [To je CS50. - CS50.TV]
>> Zato je prvo vprašanje nenavadno oblikovan.
GDB vam omogoča, da "debug" program, ampak, natančneje, kaj to kaj si naredil?
Jaz bom odgovoril, da je eden, in ne vem, kaj točno pričakuje,
tako da sem ugibati, da je nekaj po vzoru ji omogoča, da korak za korakom
sprehod skozi program, delajo z njim, spreminjanje spremenljivke, vse te stvari -
v bistvu popolnoma nadzoruje izvajanje programa
in preglejte dane del izvajanja programa.
Torej te funkcije vam debug stvari.
Ok.
Zakaj dvojiška iskalna zahteva, da se razvrstijo niz?
Kdo želi odgovoriti na to?
[Študent] Ker to ne deluje, če ni urejeno. >> Ja. [Smeh]
Če ni urejen, potem je nemogoče, da ga razdelili na pol
in vem, da je vse, kar je na levi strani je manjša in vse na desni
večji od srednje vrednosti.
Zato je treba sortirati.
Ok.
Zakaj je mehurček nekako v O n kvadrat?
Ali kdo najprej želeli, da bi lahko zelo hitro na visoki ravni pregled, kaj mehurček vrste je?
[Študent] Vanj gredo skozi vsak element in preverite prvih nekaj elementov.
Če si od tam, kjer jih zamenjali, potem preverite naslednjih nekaj elementov, in tako naprej.
Ko pridete do konca, potem veste, da je največji element postavi na koncu,
tako da prezreti, da je eden potem naprej skozi,
in vsakič, ko boste morali preveriti 1 manj element, dokler ne bo nobenih sprememb. >> Ja.
To se imenuje bubble sort, ker če ste flip matriko na svoji strani, tako da je gor in dol, vertikalno,
potem bodo velike vrednosti potopil na dno in majhne vrednosti, bo balon na vrh.
To je, kako je dobil svoje ime.
In ja, greš skozi.
Kar naprej gre skozi niz, swapping večjo vrednost
, da bi dobili največje vrednosti do dna.
>> Zakaj je O n kvadrat?
Prvič, ali ima kdo rad povedal, zakaj je to O n kvadrat?
[Študent] Ker za vsako vožnjo gre n-krat.
Lahko samo se prepričajte, da ste vzeli Največji element vso pot navzdol,
potem boste morali ponoviti, da je za čim več elementov. >> Ja.
Torej, ne pozabite, kaj velik O pomeni in kaj pomeni velike Omega.
Veliki O je kot zgornja meja, kako počasi lahko dejansko deluje.
Torej z besedami, svoj 'O, o n kvadrat, ni O n ali pa bi bilo lahko vozijo
v linearnem času, vendar pa je O n kubikov
ker je omejen z O n kubikov.
Če je to, ki ga omejuje O n kvadrat, potem je omejena tudi n kubikov.
Tako je n kvadrat, v najslabšem primeru pa absolutno ne more storiti bolje, kot n kvadrat,
kar je razlog, zakaj je za n O kvadrat.
Torej, da vidim nekoliko matematiko, kako se pride ven, da je n kvadrat,
Če imamo pet stvari v našem seznamu, prvič, koliko zamenjav bi lahko potencialno potrebujete, da bi
da bi to dobila? Kaj je dejansko le -
Koliko zamenjave se bomo morali v prvi zavoj vrste mehurček skozi niz?
[Študent] n - 1. >> Ja.
>> Če so 5 elementov, bomo morali narediti n - 1.
Nato na drugem pa, koliko zamenjav bomo morali narediti?
[Študent] n - 2. >> Ja.
In tretja bo n - 3, nato pa zaradi lažjega bom pisal v zadnjih dveh
kot potem bomo morali narediti 2 zamenjavami in 1 zamenjave.
Mislim, da je zadnja lahko ali pa ne, dejansko moralo zgoditi.
Ali je zamenjava? Ne vem.
Tako so skupni zneski za zamenjave ali vsaj primerjave, ki jih morate narediti.
Tudi če ne boste zamenjali, še vedno je treba primerjati vrednosti.
Torej, obstaja n - 1 primerjave v prvi vožnji skozi niz.
Če želite preurediti te stvari, kaj je dejansko naredimo 6 stvari, tako da bi se zlagajo lepo,
in potem bom naredil 3, 2, 1.
Torej samo prerazporejanje teh zneskov, želimo, da bi videli, koliko naredimo primerjavo
v celotnem algoritmu.
Torej, če bi te ljudi tukaj,
Nato smo še vedno le seštevek pa veliko primerjav ni bilo.
Ampak, če povzamem to in povzamemo te in te povzamemo,
je še vedno isti problem. Pravkar smo povzeli te posebne skupine.
>> Torej, zdaj smo seštevek 3 n letih. To ni samo 3 n letih.
Vedno bo n / 2 n letih.
Torej, tukaj se zgodi, da imajo 6.
Če bi imeli 10 stvari, potem lahko to storimo skupine za 5 različnih parov stvari
in na koncu z n + n + n + n + n.
Torej, ste vedno tekoč, da bi dobili n / 2 n-ih, zato bo to smo ga zapišete ven n kvadrat / 2.
In tako, čeprav je to faktor polovico, ki se zgodi, da pridejo v
zaradi dejstva, da se z vsako ponovitvijo čez niz primerjamo 1 manj
tako, da je, kako smo dobili več kot 2, vendar je še vedno n kvadrat.
Ne skrbi konstantni faktor za polovico.
Torej, veliko velik stvari O, kot je ta odvisna le vrste početje to vrsto matematike,
tem aritmetične vsote in geometrične serije stvari,
vendar je večina od njih v tem času so zelo enostavna.
Ok.
Zakaj je vključitev neke Omega n? Kaj omega pomeni?
[2 študentje govorijo naenkrat - nerazumljivi] >> Ja.
Omega si lahko zamislite kot spodnja meja.
>> Torej, ne glede na to, kako učinkovito je vaše vstavljanje sortiranje algoritem,
glede na seznam, ki je bila izrečena v, ima vedno primerjati vsaj n stvari
ali pa se mora ponoviti čez n stvari.
Zakaj je tako?
[Študent] Ker če je seznam že urejen, nato pa skozi prvo ponovitev
lahko zagotavljajo le, da je prvi element je najmanj,
in drugo ponovitev lahko jamčijo le za prva dva sta
ker ne veste, da je razvrščena ostali na seznamu. >> Ja.
Če se boste peljali v popolnoma izločen seznam, vsaj moraš iti čez vse elemente
vidim, da ni treba ničesar okoli premakniti.
Torej gre čez seznam in rekel: oh, to je že urejen,
da je nemogoče, da veš, to je razvrščenih dokler se ne preveri vsak element
videti, da so v urejenih redu.
Tako je spodnja meja za razvrščanje vstavljanja je omega n.
Kaj se v najslabšem primeru teče čas vrste spajanja,
v najslabšem primeru pa veliki O.?
Torej, v najslabšem primeru pa, kako zlivanjem deluje?
[Študent] N log n. >> Ja.
Najhitrejši splošna sortiranje algoritmi n log n. Ne moreš narediti bolje.
>> Obstajajo posebni primeri, in če bomo imeli čas danes - ampak verjetno won't -
smo lahko videli tisti, ki počne bolje kot n log n.
Toda v splošnem primeru, da ne morete narediti bolje kot n log n.
In nekako združiti zgodi, da se tisti, ki ga je treba vedeti, da je to seveda n log n.
In tako bomo dejansko izvajanje, ki še danes.
In končno, v največ treh stavkih, kako deluje izbirni vrstni?
Ali kdo želi odgovoriti, pa bom prešteti svoje kazni
ker če greš čez 3 -
Ali kdo spomnite izbiro vrste?
Izbor vrste je običajno precej težko zapomniti samo z imenom.
Pravkar ste Ponovil čez polje, je bil ne glede na največjo vrednost ali najmanjšo -
karkoli da ste noter razvrščanje
Torej, recimo, da smo razvrščanje od najmanjšega do največjega.
Vi izbirate čez polje, ki išče kar je minimalni element,
ga izberete, nato pa samo zamenjal vse, kar je na prvem mestu.
In nato na drugi prelaz čez polje, poiščite MIP znova
ga izberete, nato pa ga zamenjajte s tistim, kar je na drugem mestu.
Tako smo šele izbiranje najmanjše vrednosti
in jih vstavite v sprednji del niza, dokler se razvrstijo to.
Vprašanja o tem?
>> To neizogibno pojavlja v oblikah, ki jih morate izpolniti, ko ste oddajo pset.
Tisti, ki so v bistvu odgovore na njih.
Ok, zdaj kodiranja težav.
Sem že poslal po e-pošti - Ali je kdo ni dobil to e-pošto? Ok.
Sem že poslala po elektronski pošti prostor, da bomo uporabljali,
in če kliknete na moje ime - tako da mislim, da bom na dnu
ker je zavoljo r - vendar, če kliknete na moje ime, boš videl 2 popravke.
Revizija 1 se bo sem že kopirali in prilepili kodo v prostore
Za iskalni stvar, ki jo boš moral izvajati.
In Revizija 2 je neke vrste stvar, ki jo izvajajo po tem.
Torej, lahko kliknete na mojem revizije 1 in delo od tam.
In zdaj želimo izvajati binarno iskanje.
>> Ali kdo želi samo dati psevdokod visoki ravni pojasnilo
na kaj bomo morali storiti za iskanje? Ja.
[Študent] Ti samo sredi polja, in videli, če kaj iščete
je manjša kot ali več kot to.
In če je to manj, greš do polovice, ki je manj,
in če je več, pojdi na polovico, ki je več in to ponovite, dokler ne boste le dobili eno stvar.
[Bowden] Ja.
Obvestilo, da je naša številke matrika že urejen,
in tako to pomeni, da bomo lahko to izkoristimo in smo lahko najprej preverite,
ok, iščem številko 50.
Lahko grem v sredini.
Bližnji je težko določiti, kdaj je še veliko stvari,
ampak recimo, da bomo vedno obrezovanje na sredini.
Torej, tukaj imamo 8 stvari, tako da bi bila srednja 16.
Iščem 50, tako da je 50 več kot 16.
Sedaj lahko sem v bistvu, da mojo zbirko v teh elementih.
Lahko mečejo vse od 16 več.
Zdaj mi je matrika samo te 4 elemente, in ponavljam.
Torej želim, da bi našli sredi znova, kar se bo 42.
42 je manj kot 50, tako da sem lahko vrgel proč teh dveh elementov.
To je moja preostala polja.
Grem poiskati sredino znova.
Mislim, da je bilo 50 slab zgled, ker sem bil vedno metali stran stvari v levo,
vendar v istem ukrepu, če sem iskal nekaj
in to je manj kot elementa sem trenutno iščejo,
potem bom vrgel stran vse na desni.
Torej, zdaj moramo izvajati to.
Obvestilo, da moramo opraviti v velikosti.
Prav tako ni mogoče morali trdo oznako velikosti.
Torej, če se znebimo da # define -
Ok.
Kako lepo razbrati, kaj je velikost matrike številk je trenutno?
>> Koliko elementi v matriki števil?
[Študentske] Številke, držala,. Dolžina?
[Bowden] To ne obstaja v C.
Rabite. Dolžina.
Polja nimajo lastnosti, tako da ni dolžina last nizi
da bo samo dam pa dolgo se zgodi, da bo.
[Študent] Glej koliko pomnilnika ima in razdeliti za koliko - >> Ja.
Torej, kako smo lahko videli, koliko pomnilnika ima? >> [Študent] sizeof. >> Ja, sizeof.
Sizeof je subjekt, ki se dogaja, da se vrnete na velikost matrike številk.
In to bo pa veliko cela obstajajo krat večje celo število
saj to je, koliko pomnilnika je dejansko prejemajo.
Torej, če želim, da veliko stvari v matriki,
potem bom želel deliti z velikostjo celo število.
Ok. Tako, da mi omogoča prehod v velikosti tukaj.
Zakaj moram prenesti v velikosti sploh?
Zakaj ne morem storiti tukaj int velikost = sizeof (senu) / sizeof (int)?
Zakaj se to ne dela?
[Študent] To ni globalna spremenljivka.
[Bowden] Haystack obstaja in da smo mimo v številu, senu,
in to je nekako foreshadowing, kaj je, da pridejo. Ja.
[Študent] Haystack je le sklicevanje na to, da bi se vrnil, kako velika je ta sklicevanja.
Ja.
Dvomim v predavanju, ki ste jih videli sveženj še res, kajne?
Pravkar smo govorili o tem.
Torej bo sveženj, kjer so vse vaše spremenljivk se bodo shranjeni.
>> Vsak spomin, ki je namenjen za lokalne spremenljivke se dogaja v plasteh,
vsaka funkcija dobi svoj prostor na sklad, sklad lastnih okvir je, kako se imenuje.
Tako ima žetonov glavni okvir, znotraj njega se dogaja, da obstaja ta niz številk,
in to se dogaja, da so velikosti (dolžina tipa številke).
To se dogaja, da imajo velikosti številk, ločenih glede na velikost elementov,
ampak, da so vsi živi znotraj okvirja dimnik je glavni.
Ko pravimo iskanje, iskanje dobi svojo žetonov okvir,
svoj prostor za shranjevanje vseh njenih lokalnih spremenljivk.
Toda te trditve - tako senu ni kopija tega celotnega niza.
Mi ne gre v celotnem matrike kot kopija v iskanju.
Prav tako gre za sklicevanje na ta niz.
Tako lahko dostop do teh številk iskanje prek te odločbe.
Še vedno dostop do stvari, ki živijo znotraj okvirja dimnika je glavni,
ampak v bistvu, ko smo dobili namig, ki bi morala biti kmalu
To je tisto, kar kazalci.
Kazalci za sklicevanje na stvari, in jih lahko uporabite namig za dostop do stvari
da so druge stvari, "dimnika okvirjev.
Torej, čeprav je število na lokalni, glavno, lahko še vedno dostopate prek tega kazalca.
Ampak saj to je samo kazalec, in to je samo predlog,
sizeof (senu), prav tako vrne velikost glede same.
To ne vrne velikost stvar, ki jo kaže.
To ne vrne dejansko velikost številk.
In tako se to ne bo delovalo, kot smo želeli.
>> Vprašanja o tem?
Kazalci bodo šli v občutno bolj krvave podrobnosti v tednih, ki prihajajo.
In to je razlog, zakaj veliko stvari, ki jih vidite, večina stvari iskanja ali razvrščanje stvari,
oni so skoraj vse bo potrebno, da bi dejansko velikost matrike,
ker je v C, nimamo pojma, kaj je velikost matrike je.
Moraš ročno prenesti noter
In ne morete ročno prenesti v celotnem polju, ker ste pravkar poteka v referenčnem
in ga ni mogoče dobiti velikosti od referenčne.
Ok.
Torej, zdaj smo želeli izvesti, kar je bilo razloženo prej.
Delate lahko na njem za minuto,
in vam ni treba skrbeti, da bi vse popolnoma 100% deluje.
Samo napisati polovico psevdokod, kako misliš, da bi moral delovati.
Ok.
Ni potrebe, da se v celoti narejena s tem.
Ampak ne, kdo se počutijo udobno s tem, kar imajo sedaj,
kot nekaj, kar lahko delamo skupaj?
Ali kdo želel prostovoljno? Ali bom naključno izbral.
Ni nujno, da je prav z vsakim ukrepom, temveč nekaj, kar lahko spremenijo v delujoče stanje.
[Študent] Seveda. >> Redu.
Torej si lahko shranite revizijo s klikom na malo ikono Save.
Si Ramya, kajne? >> [Študent] Ja. >> [Bowden] Ok.
Torej, zdaj lahko ogledate revizijo in vsakdo lahko potegnite do revizije.
In tukaj imamo - V redu.
Torej Ramya šel z rekurzivno rešitev, ki je zagotovo dobra rešitev.
Obstajata dva načina, ki jih lahko storite to težavo.
Lahko to iterativno ali rekurzivno.
Največ težav boste naleteli, da je mogoče narediti rekurzivno mogoče doseči tudi iterativno.
Torej, tukaj smo storili rekurzivno.
>> Ali nekdo želi opredeliti, kaj pomeni, da se funkcija rekurzivna?
[Študent] Če imate funkcijo se klic
in potem se klic, dokler ne pride ven z res in resnično. >> Ja.
Rekurzivna funkcija je samo funkcija, ki se imenuje.
Obstajajo tri velike stvari, ki jih imajo rekurzivna funkcija.
Prvo je seveda, da se pokliče.
Drugi je osnova drži.
Torej, na neki točki funkcija mora prenehati klical samega sebe,
in to je tisto, kar je za osnovna.
Torej, tukaj smo vedeli, da moramo ustaviti, moramo odreči pri iskanju
Začetek konca, ko je enaka - in bomo šli nad tem, kaj to pomeni.
Ampak na koncu, zadnja stvar, ki je pomembna za rekurzivne funkcije:
naloge morajo nekako obrniti na osnovno zadevo.
Všeč mi je, če ste dejansko ni ničesar posodobitev, ko bo drugi rekurzivni klic,
če ste dobesedno le klicem funkcije spet z istimi argumenti
in ni bilo nobenih globalne spremenljivke spremenijo ali karkoli,
ne boste nikoli dosegli osnovni primer, v katerem velja, da je slabo.
To bo neskončna rekurzija in kup overflow.
Ampak tukaj vidimo, da je sprememba se dogaja, saj smo začeli posodabljanje + konec / 2,
bomo posodobiti konec argument tukaj, bomo posodobiti začetni argument tukaj.
Torej, v vseh rekurzivnih klicev smo nekaj posodobitev. Ok.
Ali želite, da se nam sprehod skozi vaše rešitve? >> Seveda.
Jaz sem z uporabo SearchHelp tako, da vsakič, ko sem ti to funkcijo klica
Imam začetek, kjer sem iskal v polju in na koncu
o tem, kje iščem matriko.
>> Na vsakem koraku, kjer je rekel, da je srednji element, ki je začetek + konec / 2,
je to enako, kaj iščemo?
In če je, potem smo ga našli, in mislim, da dobi opravil do ravni rekurzije.
In če to ni res, potem smo preveriti, ali je ta srednja vrednost matrike prevelik,
v tem primeru gledamo na levi polovici niza, tako da greste od začetka na srednji indeks.
In sicer bomo za konec polovico.
[Bowden] Ok.
Sliši se dobro.
Ok, nekaj stvari, in dejansko je to zelo visoki ravni, kar
da vam nikoli ne bo treba vedeti za to seveda, ampak je res.
Rekurzivne funkcije, si vedno slišal, da si slab posel
ker če rekurzivno se imaš preveč časa, vam Stack overflow
saj, kot sem že rekel, vsak dobi svojo funkcijo dimnika okvirja.
Torej, vsak poziv za rekurzivna funkcija dobi svojo dimnika okvirja.
Torej, če bi rekurzivnih klicev 1000, dobiš 1000 dimnih okvirje,
in hitro lahko povzroči, da imajo preveč okvirji odvodnikom in stvari le prekinil.
Torej, to je, zakaj rekurzivne funkcije so na splošno slabo.
Vendar pa je lepo podmnožica rekurzivne funkcije imenuje repa rekurzivne funkcije,
in to se zgodi, da bo primer tista, v kateri, če je prevajalnik zazna to
in bi ga, mislim, da - v Jek, če se boste peljali to the-O2 zastave
potem bo to opazil, je to rep rekurzivni in da stvari dobro.
>> To bo ponovno isti okvir snop in znova za vsako rekurzivni klic.
In zato, ker si z isto žetonov okvir, vam ni treba skrbeti
kdaj nakladanje prepolno, in ob istem času, kot si že rekel,
kjer je nekoč vrnili ste res, potem mora vrniti do vseh teh odvodnikom okvirjev
in 10. poziv SearchHelp mora vrniti v 9., je, da se vrnete na 8..
Tako, da ni potrebno, da se zgodi, ko so funkcije rep rekurzivno.
In kaj je ta funkcija rep rekurzije je obvestilo, da je za vsakega razpisa do searchHelp
rekurzivni klic, da je kar je tisto, kar se je vrnil.
Tako je v prvem razpisu za SearchHelp, smo takoj vrne false,
takoj vrne res, ali pa naredimo rekurzivni klic SearchHelp
če kaj nam vrača tisto, kar je ta poziv se vrača.
In ne moremo narediti, če smo storili kaj takega int x = SearchHelp, povratno x * 2,
Samo nekaj naključno spremembe.
>> Torej, zdaj je to rekurzivni klic, ta int x = SearchHelp rekurzivni klic,
ni več rep rekurzivna, ker dejansko ne morali vrniti
nazaj na prejšnjo okvir dimnik, tako da ta predhodni klic funkcije
lahko naredite nekaj s povratno vrednost.
Torej to ni rep rekurzivna, ampak tisto, kar smo imeli, preden je lepo rep rekurzivno. Ja.
[Študent], ne bi bilo treba preverjati 2. osnovna 1.
ker bi lahko prišlo do položaja, kjer ko dajati argument
ste začetek = koncu, vendar so se igla vrednost.
Vprašanje je bilo, ne moremo teči v primeru, ko je konec igle vrednost
ali začetek = koncu, primerno, začetek = konec
in si dejansko ne preverja, da posebno vrednost še ni,
začnite + konec / 2 je le, da bo za enako vrednost.
Vendar smo že vrnili napačen in smo dejansko nikoli ni preverila vrednost.
Torej, vsaj v prvem razpisu, če znaša 0, potem želimo vrne false.
Ampak, če je velikost 1, nato pa začetek ne bo enak namen,
in bomo vsaj preveriti en element.
Ampak mislim, da je prav, da se lahko znajdemo v primeru, ko začnete + konec / 2,
Začetek konča pa enako kot začetek konca + / 2,
vendar nikoli dejansko preveriti ta element.
>> Torej, če smo najprej preveriti, je srednja vrednost del, ki ga iščemo,
potem lahko takoj vrne res.
Sicer če si ti enako, potem ni smisla še naprej
saj smo le, da bo posodobitev na primer, ko smo na enega elementa matrike.
Če je posamezen element ni tisti, ki ga iščemo,
potem je vse narobe. Ja.
[Študent] Stvar je v tem, da je od velikosti je večje, kot je število elementov v matriki,
je že pobot - >> Tako bo velikost -
[Študent] Recimo, če je matrika velikosti 0, potem bo dejansko SearchHelp preverite senu od 0
na prvi poziv.
Matrika ima velikost 0, tako da je 0 - >> Ja.
Še ena stvar, ki - to bi bilo dobro. Pomislimo.
Torej, če je niz 10 elementov in srednjo bomo preveriti, je indeks 5,
tako da smo preverjanje 5, in recimo, da je vrednost manj.
Torej smo metali vse, od 5 naprej.
Torej začetek + konec / 2 se bo naša nova konec,
Tako ja, to je vedno tekoč, da ostanejo tudi po koncu array.
Če je tako, če je bilo celo ali sodo, potem bi morali preveriti, recimo, 4,
vendar smo še vedno meče stran -
Torej, ja, konec je vedno tekoč, da bo po dejanskem koncu niza.
Torej elementov, smo se osredotočajo na, konec je vedno tekoč, da je tisti, po tem.
In tako, če ne še enak začetek konca, smo v paleto velikosti 0.
>> Druga stvar, ki sem mislil je, da smo se posodabljanje začetek za začetek + konec / 2,
tako da je to res, da imam težave z, kjer je to začetek konca + / 2
je element smo preveriti.
Recimo, da smo imeli to 10-element array. Karkoli.
Torej začetek + konec / 2 se bo nekaj takega kot je ta,
in če to ni vrednost, torej želimo posodobiti.
Vrednost je večja, zato smo želeli videti na tej polovici niza.
Torej, kako bomo posodobiti začetek, bomo posodobiti začetek zdaj ta element.
Vendar pa lahko to še vedno dela, ali pa vsaj, lahko to storite začetek + konec / 2 + 1.
[Študent], vam ni treba začeti + konec [neslišno] >> Ja.
Smo že preverili ta element, in vem, da to ni tisto, ki ga iščemo.
Tako nam ni treba posodobiti začetek za ta element.
Mi lahko samo preskočite in začnete posodobiti, da je ta element.
In ni vedno tako, recimo, da je bil to namen,
zato začnite bi bilo to, da začnete + konec / 2, bi bilo to,
začetek + konec - Ja, mislim, da lahko končajo v neskončno rekurzije.
Recimo, da je samo niz velikosti 2 ali množica velikosti 1. Mislim, da bo to delovalo.
Torej sedaj, začetek je ta element in konec je 1 zunaj njega.
Tako je element, ki ga bomo preveriti, je ta,
in potem, ko smo posodobili začetek, bomo posodobiti začetek za 0 + 1/2,
ki nas bo na koncu spet z začetka pa je ta element.
>> Torej smo preverjanje isti element znova in znova.
Torej, to je v primeru, ko mora vsak rekurzivni klic dejansko posodobiti nekaj.
Torej moramo narediti konec, začetek + / 2 + 1, sicer pa je tako
če ne bomo dejansko posodabljanje začetek.
Vsi videl?
Ok.
Ima kdo kakšno vprašanje v zvezi s tem rešitve ali katere koli dodatnih komentarjev?
Ok. Ali kdo se ponavlja rešitev, da bomo lahko vsi gledate?
Ali smo vsi narediti rekurzivno?
Ali pa tudi mislim, da če njeno pa je začela, potem ste morda prevlada prejšnjega.
Ali samodejno shrani? Nisem pozitiven.
Ali kdo so ponavlja?
Mi lahko hodi skozi njo skupaj, če ne.
Ideja se bo enako.
Iterativni rešitev.
Bomo želeli, da v bistvu storijo isto idejo
če želimo slediti novim konca niza in nov začetek polja,
in to, da znova in znova.
In če kaj smo sledenja kot na začetku in na koncu vedno križajo,
potem nismo našli in smo lahko vrne false.
Torej, kako naj to naredim? Vsakdo ima predloge ali kodo za mene, da pull up?
[Študent] Ali while zanko. >> Ja.
Boste želeli narediti zanko.
>> Ali imate kodo, da bi lahko potegnite navzgor, ali pa kaj si hotel predlagati?
[Študent] jaz tako mislim. >> Redu. To naredi stvari lažje. Kako ti je ime?
[Študent] Lucas.
Revizija 1. Ok.
Nizka je tisto, kar imenujemo začeti prej.
Do ni ravno tisto, kar imenujemo konec prej.
Pravzaprav, konec je zdaj v array. To je element, bi morali razmisliti.
Tako nizka je 0, kar je velikost matrike - 1,
in zdaj smo zanka, in smo preverjanje -
Mislim, da lahko hodiš po njej.
Kakšna je bila vaša razmišljanja skozi to? Nas Sprehod skozi svojo kodo.
[Študent] Seveda. Pogled na senu vrednosti na sredini in ga primerjajte z iglo.
Torej, če je višja od vaše igle, potem hočeš - oh, pravzaprav, da bi morala biti nazaj.
Če boste želeli, da mečejo desno polovico, in tako ja, da bi moralo biti tako.
[Bowden] Torej bi bilo to manj? Je to tisto, kar si rekel? >> [Študent] Ja.
[Bowden] Ok. Manj.
Torej, če kaj iščemo v manjši od tistega, kar smo želeli,
potem ja, želimo, da mečejo v levi polovici,
kar pomeni, da smo vse, kar smo posodabljanje razmišlja
s premikanjem nizko na desni strani polja.
To izgleda dobro.
Mislim, da ima isti problem, da smo rekli na prejšnjega,
kjer je nizka, če je 0 in se je 1, potem nizko + gor / 2 se bo ustanovila za isto stvar znova.
>> In tudi če to ni tako, je to še vedno bolj učinkovito vsaj
da samo mečejo element sva pogledala kar vemo, je narobe.
Tako nizko do + / 2 + 1 - >> [Študent] To bi moralo biti drugače.
[Bowden] Ali bi to morala biti - 1, drugo pa mora biti + 1.
[Študent] In tam bi morala biti dvojna enačaj. >> [Bowden] Ja.
[Študent] Ja.
Ok.
In končno, zdaj ko imamo to + 1 - 1 stvar,
je - ne bi bilo - ali je to možno za nizko končati z večjo vrednostjo kot je?
Mislim, da je edini način, da se lahko zgodi - je to mogoče? >> [Študent], ne vem.
Ampak, če postane okrnjena in potem dobi minus, da je 1 in potem - >> Ja.
[Študent] To bi lahko dobil zamočil.
Mislim, da bi bilo dobro, samo zato, ker
za to, da končajo nižje bi morala biti enaka, se mi zdi.
Ampak, če so enaki, potem ne bi naredil while zanko, da začnete z
in bi samo še vrnil vrednost. Zato mislim, da smo dobro zdaj.
Vedite, da čeprav je ta problem ni več rekurzivni,
iste ideje, uporabljajo, kjer bomo lahko videli, kako je to tako preprosto bi lahko bilo
na rekurziven rešitve s tem, da smo pravkar posodablja indekse znova in znova,
delamo problem manjši in manjši, smo se osredotočajo na podmnožico matrike.
[Študent] Če je nizka, je 0 in se je 1, bi bila oba 0 + 1/2, ki bi šel na 0,
in potem bi bilo + 1, bi lahko - 1.
[Študent] Če smo preverjanje enakost?
Všeč mi je, če sredinska dejansko igla?
Ne bomo zdaj s tem? Oh!
Če it's -
Da. Ne moremo narediti test tukaj zato, ker recimo prvi sredini -
[Študent] To je res všeč, ne zavrzite navezani.
Torej, če si vrgel proč omejeni, ga morate najprej preveriti, ali karkoli.
Ah. Ja. >> [Študent] Ja.
Torej, zdaj smo zavrgli 1 trenutno pogledal,
kar pomeni, da moramo zdaj tudi
if (senu [(+ do nizka) / 2] == iglo), potem se lahko vrnemo res.
In če dodam še, ali samo, če to pomeni dobesedno isto stvar
ker bi to res vrnil.
Tako da bom dal drugega, če pa to ni pomembno.
>> Tako pa, če je to, pa to, in to je skupna stvar, ki mi
če tudi če je v primeru, ko je vse dobro tukaj,
kot nizko nikoli ne more biti večja od gor, to ni vredno razmišljanje o tem, ali je to res.
Torej lahko tudi rekli, medtem ko je nizka ali manj enaka
ali pa nizka, manj kot
tako da, če so vse enako ali nizka zgodi, da bi šli gor,
potem lahko iztrgajo iz te zanke.
Vprašanja, vprašanja, komentarji?
Ok. To izgleda dobro.
Zdaj želimo narediti vrste.
Če gremo v mojo drugo revizijo, vidimo te iste številke,
zdaj pa niso več v urejenih redu.
In želimo izvajati neke z uporabo katerega koli algoritma v O n log n.
Torej, kateri algoritem misliš, da bi morali tu izvajati? >> [Študent] zlivanjem.
[Bowden] Ja. Zlivanjem je O (n log n), tako da je tisto, kar smo naredili.
In problem, se bo precej podoben,
kjer lahko dovzetni za rekurziven rešitev.
Prav tako lahko prišli do iterativno rešitev, če želimo,
vendar bo rekurzija lažje tu in da bi morali storiti rekurzijo.
Mislim, da se bomo sprehodili po datumu spajanja prvič,
čeprav je lep video na vrste spajanja že. [Smeh]
Torej zlivanjem obstajajo - jaz sem zapravljati toliko tega prispevka.
Tam je ostal samo še eden.
Torej združiti.
Oh, 1, 3, 5.
Ok.
Merge traja dve ločeni nize.
Posamično se ta dva nizi tako urejeno.
Torej ta matrika, 1, 3, 5, razvrščeni. Ta matrika, 0, 2, 4, razvrščeni.
Zdaj, kaj je treba storiti, je spajanje jih združiti v en sam niz, ki je sama razvrščena.
Zato želimo matriko velikosti 6, ki se dogaja, da so ti elementi znotraj nje
v urejenih vrstnem redu.
>> In tako bomo lahko izkoristili dejstvo, da so razporejene ta dva nizi
to storiti v linearnem času,
Linearni časovno smisel, če je ta matrika velikosti x in to je velikost y,
potem mora biti skupni algoritem O (x + y). Ok.
Torej predlogi.
[Študent] Lahko začnemo na levi?
Torej boš dal dol 0 in šele nato 1, nato pa sem si na 2.
Torej, to je nekako kot da imate kartico, ki se premika v desno. >> [Bowden] Ja.
Za oba nizi, če bomo samo osredotočiti na skrajni levi element.
Ker so razporejene tako nizi, vemo, da ti elementi 2
so najmanjši elementi v obeh matrike.
To pomeni, da mora 1 od teh 2 elementov je najmanjši element v našem novega niza.
Samo tako se zgodi, da je najmanjša, je pa na desno tem času.
Tako smo lahko 0, ga vstavite na levo, ker je 0 manj kot 1,
tako da 0, ga vstavite v našem prvem mestu, nato pa smo posodobili to
do zdaj osredotočiti na prvem elementu.
In zdaj smo ponovili.
Zdaj smo primerjali 2 in 1. 1 je manjši, tako da bomo vstavite 1.
Mi posodobiti to kazalec, da kaže na tega tipa.
Zdaj pa še enkrat, tako da 2. To bo posodobil, primerjati te 2, 3.
To posodobitve, nato 4 in 5.
Tako, da je spajanje.
>> Treba je precej očitno, da je linearna časa, odkar sva šla čez vsak element enkrat.
In to je največji korak k izvajanju zlivanjem to počne.
In to ni tako težko.
Nekaj ​​stvari za skrbeti je, recimo, smo združujejo 1, 2, 3, 4, 5, 6.
V tem primeru se znajdemo v scenariju, kjer je to ena se dogaja, da so manjše,
potem bomo posodobiti to kazalec, ta se bo manjši, posodablja,
ta je manjši, zdaj pa moraš priznati
ko ste dejansko zmanjka elementov primerjati s.
Ker smo se že uporablja ta celoten niz,
vse, kar je v tem polju je zdaj samo vstavite tukaj.
Torej, če bomo kdaj naleteli na mestu, kjer je eden od naših polj popolnoma združila že,
potem vzemite vse elemente drugega niza in jih vstavite v zaključku niza.
Tako smo lahko samo vstavite 4, 5, 6. Ok.
To je ena stvar, da pazi.
Izvajanje da bi morala biti stopnja 1.
Zlivanjem nato na podlagi tega, da je 2 koraka, 2 pisanih koraki.
Reciva da ta niz.
Torej zlivanjem, stopnja 1 je prekinil niz rekurzivno na polovici.
Torej to vrsto razdeliti na polovici.
Zdaj imamo 4, 15, 16, 50 in 8, 23, 42, 108.
In zdaj smo še enkrat, in to bomo razdelili na pol.
Pravkar sem ga bom na tej strani.
Torej, 4, 15 in 16, 50.
Mi bi naredil isto stvar tukaj.
In zdaj smo ga razdelili na polovici znova.
In imamo 4, 15, 16, 50.
Tako, da je naša osnovna.
Ko nizi so velikosti 1, potem prenehajte z delitvijo na polovici.
>> Kaj pa naj naredimo s tem?
Smo na koncu bo to tudi razčleniti v 8, 23, 42 in 108.
Torej, zdaj, ko smo že pri tem, zdaj korak dve vrste spajanja je samo združitev para seznamov.
Zato želimo, da združite. Mi samo pokličite dokumentov.
Vemo, da se bo vrnil spajanje teh v urejenih redu.
4, 15.
Zdaj želimo, da združite in da se bo vrnil seznam s tistimi, ki v urejenih vrstnem redu,
16, 50.
Mi združiti tiste - ne morem napisati - 8, 23 in 42, 108.
Tako smo združili parov naenkrat.
Zdaj sva spet združita.
Obvestilo, da je razvrščena vsako od teh seznamov v sebi,
in potem bomo lahko samo združitev teh seznamov, da bi dobili seznam velikosti 4, ki je razvrščena
in združitev teh dveh seznamov, da bi dobili seznam velikosti 4, ki je razporejen.
In končno, lahko združitev teh dveh seznamov velikosti 4, da bi dobili en seznam velikosti 8, ki je razporejen.
Tako je videti, da je to skupna n log n, smo že videli, da je spajanje linearna,
tako da, ko imamo opravka z združitvijo teh, tako kot celotni stroški spajanje
za ta dva seznama je samo 2, ker -
Ali pa, da je O n, n pa tukaj je samo ta 2 elementa, tako da je 2.
In to je 2 in 2 teh 2 bo 2 in teh 2 bo 2,
Tako se je na vseh spajanja, ki jih moramo narediti, bomo na koncu delaš n.
Kot 2 + 2 + 2 + 2 je 8, kar je za n,
Tako je n stroški združitve v tem setu.
In potem isto tukaj.
Bomo združiti te 2, potem se ti 2 in posamično to merge traja štiri operacije,
to merge bo štiri operacije, vendar še enkrat, med vsemi temi,
smo na koncu združitev n skupne stvari, zato je ta korak se n.
In tako se vsaka stopnja ima n elementov, ki se združijo.
>> In koliko vrednosti so tam?
Na vsaki ravni, naša polja raste z velikostjo 2.
Tu so naši nizi so velikosti 1, tu oni velikosti 2, tu oni velikosti 4,
in končno, oni so velikosti 8.
Zato, ker je podvojila, pa se bodo skupaj log n teh ravneh.
Torej, z log n ravni, pri čemer vsaka posamezna stopnja n skupne operacije,
smo dobili dnevnik N algoritem.
Vprašanja?
So ljudje, ki že napredovala o tem, kako izvajati to?
Je kdo že v stanju, ko sem lahko samo dvigni svojo kodo?
Lahko vam dam malo.
Ta se bo več.
Toplo priporočam ponovil -
Ni vam treba storiti rekurzijo za spajanje
ker narediti rekurzijo za spajanje, boste morali opraviti kup različnih velikosti.
Lahko, vendar je nadležno.
Ampak rekurzija za razvrščanje sama je precej enostavno.
Pravkar ste dobesedno poklical vrste na levi polovici, nekako na desni polovici. Ok.
Vsakdo ima vse, kar sem lahko pull up yet?
Ali pa bom dal malo.
Ok.
Vsakdo ima nekaj, kar lahko skupaj z?
Ali pa bomo samo delo s tem in nato še od tam.
>> Vsakdo ima več kot to, da sem lahko pull up?
[Študent] Ja. Lahko potegnite navzgor rudnik. >> Redu.
Da!
[Študent] je bilo veliko pogojev. >> Oh, sranje. Ali lahko -
[Študent], da moram to rešiti. >> Ja.
Tako smo naredili spajanja ločeno.
Oh, pa saj ni tako slabo.
Ok.
Tako nekako je tudi sama prav kliče mergeSortHelp.
Razloži nam, kaj počne mergeSortHelp.
[Študent] MergeSortHelp precej pa dva glavna koraka,
ki je razvrstiti vsak polovico niz in nato združiti oba.
[Bowden] Ok, daj mi sekundo.
Mislim, da je to - >> [Študent], moram -
Ja. Sem kaj spregledal.
V spajanja, se zavedam, da moram ustvariti nov niz
ker nisem mogel storiti v mestu. >> Da. Ne moreš. Popravite.
[Študent] Tako sem ustvaril novo vrsto.
Pozabil sem na koncu združita ponovno spremeniti.
Ok. Potrebujemo nov niz.
V vrste spajanja, to je skoraj vedno res.
Del stroškov boljšega algoritma čas pametno
se skoraj vedno morali uporabiti nekoliko več pomnilnika.
Torej, tukaj, ne glede na to, kako boste to storili z zlivanjem,
da bi nujno morali uporabiti nekaj dodatnega pomnilnika.
On ali ona ustvarila nov niz.
In potem rečeš na koncu smo morali kopirati nov niz v prvotni matriki.
[Študent] Mislim, da ja.
Ne vem, če deluje na področju štetja s sklicem ali karkoli -
Ja, bo delovalo. >> [Študent] Ok.
Ste poskusili vožnjo to? >> [Študent] No, ne še. >> Redu.
Poskusite jo izvaja, in potem bom govoril o tem, za sekundo.
[Študent], da moram imeti vse funkcije prototipov in vse, kajne?
Funkcija prototipi. Oh, misliš kot - Ja.
Razvrsti kliče mergeSortHelp.
>> Torej, da bi nekako lahko pokličete mergeSortHelp mora mergeSortHelp bodisi so bili opredeljeni
Pred vrste ali moramo samo prototip. Preprosto kopirajte in prilepite to.
In podobno, mergeSortHelp kliče dokumentov,
vendar je spajanje še ni določena, tako da bomo vedeli šele pustiti mergeSortHelp
, da je tisto, kar se združita bo izgledal, in to je to.
Torej mergeSortHelp.
Imamo težavo tukaj, kjer nimamo osnovno zadevo.
MergeSortHelp je rekurzivna, zato je vsaka rekurzivna funkcija
se bo treba neke vrste primerjavi z osnovnim vedeti, kdaj prenehati rekurzivno klical samega sebe.
Kaj je naša osnovna bo treba tukaj? Ja.
[Študent] Če znaša 1? >> [Bowden] Da.
Tako kot smo videli tam, sva se ustavila delitev nizi
ko smo dobili v matrikah velikosti 1, ki so neizogibno sami izločeni.
Torej, če velikost je enaka 1, vemo matrika je že urejen,
tako da bomo lahko samo vrnitev.
>> Obvestilo, da je ničen, zato ne vrne nič posebnega, samo vrniti.
Ok. Torej, to je naša osnovna.
Mislim, da naša osnovna lahko tudi, če se zgodi, da bo združitev paleto velikosti 0
bomo verjetno želeli ustaviti na neki točki,
tako da bomo lahko samo rečem velikosti manj kot 2 ali manj ali enako kot 1
tako, da bo to delo za vsak niz zdaj.
Ok.
Torej, to je naša osnovna.
Zdaj pa bi rad, da nas sprehod skozi spajanje?
Kaj pomenijo vse te primere?
Do tu smo šele počne isto idejo, -
[Študent], da moram mimo velikosti z vsemi klici mergeSortHelp.
Dodal sem velikosti kot dodatno primarnim in to ni tam, kot velikost / 2.
[Bowden] Oh, velikost / 2, velikost / 2. >> [Študent] Ja, pa tudi v zgornji funkciji, kot tudi.
[Bowden] Tukaj? >> [Študent] Samo velikost. >> [Bowden] Oh. Velikost velikost? >> [Študent] Ja.
[Bowden] Ok.
Naj pomislim za sekundo.
Ali smo naleteli na težavo?
Vedno smo zdravljenje levo kot 0. >> [Študent] No
To je narobe preveč. Žal mi je. To bi morala biti začetek. Ja.
[Bowden] Ok. Všeč mi je, da je bolje.
In konec. Ok.
Torej, zdaj bi radi, da nam sprehod skozi spajanje? >> [Študent] Ok.
Jaz sem samo sprehod skozi ta novi niz, ki sem jih ustvaril.
Njena velikost je obseg dela polja, ki jih želimo rešiti
in poskuša najti element, ki naj ga v novem koraku polja.
Torej za to, prvič sem preverjanje, če leva polovica matrike še vedno vse več elementov,
in če se ne, potem greš v ta drug pogoj, ki je ravno pravi
ok, mora biti na pravem array, in bomo napisali, da je v sedanji indeks newArray.
>> In potem drugače, bom preverjanje, če je na desni strani polja, tudi končal,
V tem primeru sem dal v levo.
To ne bi dejansko potrebno. Nisem prepričan.
Ampak vseeno, drugi dve preverjanje, kateri od obeh so manjši v levo ali desno.
In prav v vsakem primeru, sem povečevanje kar sem ogrado prirastek.
[Bowden] Ok.
To izgleda dobro.
Ali ima kdo pripombe ali pomisleke ali vprašanja?
Torej tistih štirih primerih, ki jih imamo, da bi stvari v le da - ali je videti kot 5 -
vendar pa moramo preučiti, ali je levo polje zmanjkalo stvari, ki jih moramo združiti,
ali je pravica niz zmanjkalo stvari, ki jih moramo združiti -
Jaz sem gledala nič.
Torej, ali je levo polje zmanjkalo stvari ali pravice matrika je zmanjkalo stvari.
Tisti, ki so v dveh primerih.
Potrebujemo tudi trivialna primer, ali je leva, kar je manj kot prava stvar.
Potem smo želeli izbrati levi stvar.
To so primeri.
Torej, to je prav, da to je to.
Array levo. To je 1, 2, 3. Ok. Torej, ja, to so štiri stvari, ki jih lahko naredite.
In mi ne bo šel čez iterativno rešitev.
Jaz ne bi priporočal -
Zlivanjem je primer funkcije, ki je tako ne repa rekurzivna,
to ni enostavno, da bi bilo rekurzivni rep,
vendar tudi to ni zelo enostavno, da bi se ponavlja.
To je zelo enostavno.
Ta izvedba vrste spajanja,
združiti, ne glede na to, kaj počnete, boste graditi spajanje.
>> Tako nekako združiti zgrajen na vrhu spajanja rekurzivno je samo te tri vrstice.
Iterativno, je bolj siten in težje misliti.
Toda opazil, da to ni rep rekurzivna, ker mergeSortHelp - ko sebe imenuje -
mora še delati stvari po tem rekurzivni klic vrne.
Zato mora ta sklad okvir še naprej obstaja tudi po tem kliče.
In potem, ko pokličeš to mora sklad okvir še naprej obstaja
ker je tudi po tem razpisu, bomo še vedno morali združiti.
In to ni enostavna, da bi to rep rekurzivno.
Vprašanja?
V redu.
Torej grem nazaj, da razvrstite - oh, tam je dve stvari, ki jih želim pokazati. Ok.
Če se vrnemo k uredi, bomo to hitro.
Ali iskanje. Razvrsti? Sortiraj. Ja.
Če se vrnemo na začetke vrste.
Želimo ustvariti algoritem, ki razvršča matrike z uporabo katerega koli algoritma
V O n.
Torej, kako je to mogoče? Ima kdo kakršno koli -
Sem namignil prej -
Če smo na tem, da izboljša od n log n do O n
smo izboljšali naš algoritem čas pametno,
kar pomeni, kaj bomo morali storiti, da bi za to?
[Študent] Space. >> Ja. Bomo uporabljali več prostora.
In niti ni tako več prostora, je eksponentno več prostora.
Zato mislim, da je ta vrsta algoritma je psevdo nekaj, psevdo polynom -
psevdo - Ne spomnim se. Lažni nekaj.
Ampak to je zato, ker smo morali uporabiti toliko prostora
da je to mogoče doseči, vendar ni realno.
>> In kako to doseči?
To dosežemo, če bomo zagotovili, da vsak element v matriki
pod določeno velikost.
Torej, kaj je pravkar rekel, da velikost je 200,
vsak element v matriki je pod velikost 200.
In to je pravzaprav zelo realno.
Lahko zelo enostavno imeti niz, ki ga poznate vse kar je v njem
se bo manj kot nekaj več.
Všeč mi je, če imate nekaj povsem ogromen vektor ali kaj podobnega
ampak veš vse, kar se dogaja, da je med 0 in 5,
potem se bo bistveno hitreje, da to storijo.
In vezana na katerikoli od elementov je 5,
tako da je ta vezan, da je, koliko pomnilnika boste uporabili.
Torej, vezan je 200.
V teoriji je vedno vezan, saj lahko celo le do 4 milijarde,
ampak to je nerealno, ker potem bi se z uporabo prostora
o vrstnem redu v višini 4 milijarde EUR. Torej, to je nerealno.
Ampak tukaj bomo rekli naši vezana je 200.
Trik, da to počne v O n je naredimo še eno vrsto, imenovano grofje velikosti zavezuje.
Torej, dejansko je to bližnjica za - Pravzaprav ne vem, če ima to Jek.
Toda v Zalivu, da je vsaj - Jaz sem ob predpostavki, da to počne tudi Jek -
To bo samo inicializacijo celotno paleto za 0s.
Torej, če ne želite storiti, potem bi jaz naredil posebej for (int i = 0;
i <vezan; i + +) in štetje [i] = 0;
Torej, zdaj je vse inicializira na 0.
Ponovil sem nad mojo array,
in kaj počnem jaz, je štetje števila vsak - Greva tukaj.
Imamo 4, 15, 16, 50, 8, 23, 42, 108.
Kaj sem štetja je število ponovitev vsakega od teh elementov.
Naj dejansko dodali nekaj več tukaj z nekaj ponovitev.
Torej vrednost imamo tukaj, je vrednost, ki se bo matrika [i].
Tako bi lahko val 4 ali 8 ali karkoli.
In zdaj sem štetje, koliko od te vrednosti, kar sem videl,
tako šteje [val] + +;
Ko je to storjeno, pričakuje se bo izgledal nekako 0001.
Naredimo šteje [val] - VEZANA + 1.
>> No, to je samo, da se upoštevalo dejstvo, da smo z začetkom od 0.
Torej, če 200 se bo naša največja številka,
Nato 0-200 je 201 stvari.
Torej točk, bo to videti kot 00.001, ker imamo eno 4.
Potem bomo imeli 0001, kjer bomo imeli 1 v 8. indeks štetjem.
Imeli bomo 2 v 23. indeksa štetjem.
Imeli bomo 2 v indeksu 42. štetjem.
Tako bomo lahko uporabite count.
Torej num_of_item = število [i].
In tako, če num_of_item je 2, kar pomeni, da želimo vstaviti 2 od števila i
v našem razvrščene matrike.
Zato moramo slediti, kako daleč smo v matriki.
Torej, indeks = 0.
Array - bom napisal.
Grofje -
array [index + +] = i;
Je to tisto, kar hočem? Mislim, da je tisto, kar hočem.
Ja, to je v redu. Ok.
Torej, to vsi razumejo, kaj je namen mojega niza grofje je?
To je štetje število ponovitev za vsako od teh številk.
Potem sem ponavljanjem, ki šteje več kot matriko,
in i-položaj v matriki grofje
je število i, da bi bilo videti v mojem razvrščene array.
Zato se število 4 se bo 1
in grofje 8 se bo 1, 23 točk pa se bo 2.
Torej, to je, koliko jih želim vstaviti v mojo razvrščene matrike.
Potem pa sem naredil.
Jaz sem vstavljanje num_of_item i je v moji razvrščene matrike.
>> Vprašanja?
In tako spet, to je linearen čas, saj smo tik pred ponavljanjem tokrat,
ampak to je tudi linearna, kaj to število zgodi, da se,
in tako je močno odvisna od tega, kaj vam je vezan.
Z vezan na 200, to ni tako slabo.
Če je vaš veže se bo 10.000, potem je to malo slabše,
če pa veže se bo 4 milijarde EUR, to je povsem nerealno
in to polje bo morala biti velikost 4 milijarde EUR, kar je nerealno.
Torej, to je to. Vprašanja?
[Neslišno študentski odziv] >> Ok.
Spoznal sem še eno stvar, ko smo šli skozi.
Mislim, da je problem v Lucas je in verjetno vsak posameznik, ki smo jih videli.
Čisto sem pozabil.
Edina stvar, ki sem želel komentirati, je, da ko imate opravka s stvarmi, kot so indeksi,
nikoli zares videti, ko pišeš za zanke,
ampak tehnično, kadar imate opravka s temi indeksi,
morate precej vedno ukvarjajo z nepodpisane celih števil.
Razlog za to je, ko imate opravka s podpisanimi števil,
tako da če imate 2 podpisane števil in jih dodate skupaj
in se na koncu preveč, potem si na koncu z negativnim predznakom.
Torej, to je tisto, kar je celo preliv.
>> Če dodam 2000000000 in 1000000000, sem končal z negativnim 1 milijardo EUR.
Tako je cela delo na računalnikih.
Torej, problem pri uporabi -
To je v redu, razen če se zgodi, da je nizka 2 milijardi in se zgodi, da bo 1 milijardo EUR,
potem bo to negativno 1 milijarde EUR in potem bomo to delite z 2
in na koncu z negativnim 500 milijonov EUR.
Torej, to je samo vprašanje, če se zgodi, da bo iskanje po matriki
milijard stvari.
Ampak, če nizka do + zgodi overflow, potem je to problem.
Takoj, ko smo jih podpisana, potem 2 milijard evrov 1000000000 znaša 3 milijarde EUR.
3000000000 deljeno z 2 je 1,5 milijarde evrov.
Torej, takoj, oni nepodpisana, je vse popolno.
In tako je tudi problem, ko pišete for zanke,
in dejansko je verjetno stori samodejno.
To bo pravzaprav le kričati na vas.
Torej, če je ta številka prevelika, da bi lahko v samo celo število, vendar bi ustrezal unsigned integer,
bo kriči na vas, tako da je, zakaj ne boste nikoli zares teče v vprašanju.
Vidite lahko, da je indeks nikoli ne bo negativna
in tako, ko ste ponavljanjem v matriko,
lahko skoraj vedno pravim unsigned int i, vendar ne boste res treba.
Stvari gredo na delo precej preprosto, kot dobro.
Ok. [Šepeta] Koliko je ura?
Zadnja stvar, ki sem želel pokazati - in bom naredil res hitro.
Saj veste, kako smo # define, da bomo lahko # define MAX kot 5 ali kaj podobnega?
Ne smemo storiti MAX. # Define zavezana kot 200 ljudi. To je tisto, kar smo že naredili.
Ta določa, da je konstanto, ki je pravkar dogaja, da se kopirali in prilepili
kadar se zgodi, da napišete svoje obveze.
>> Tako bomo lahko dejansko narediti več z # opredeljuje.
Mi lahko # define funkcije.
Oni niso zares deluje, vendar bomo jim pravimo funkcije.
Primer bi lahko nekaj podobnega MAX (x, y) je opredeljena kot (x <y y?: X). Ok.
Torej bi se navadiš na trikomponentnih operaterja sintakso,
vendar je x manjši od y? Vrni y, drugače vrne x.
Tako lahko vidite, lahko to posebno funkcijo,
in bi se kot funkcija int MAX traja 2 argumente, vrnil.
To je ena izmed najpogostejših vidim storili takole. Pravimo jim makrov.
To je makro.
To je samo sintaksa za to.
Lahko napišete makro, ki naredi vse, kar si želite.
Si pogosto videti makrov za razhroščevanje printfs in podobno.
Torej, tip printf obstajajo posebni konstante v C, kot poudarjajo LINE poudarjajo,
2 poudarja LINE poudarjajo,
in tam je tudi mislim, da 2 poudarja FUNC. To bi lahko bilo. Nekaj ​​takega.
Te stvari bo nadomeščen z imenom funkcije
ali številko proge, ki ste na.
Pogosto pa pišete Razhroščevalna printfs, da tukaj sem lahko potem samo napisati
Odpravljati napake in se bo izpisal število vrstic in funkcijo, ki mi zgodi, da se v
da bi naletela na to debug izjavo.
In si lahko natisnete tudi druge stvari.
Torej, ena stvar, ki jo je treba paziti jasno zakaj je, če sem se zgodi, da # define DOUBLE_MAX
kot nekaj podobnega 2 * y in 2 * x.
Torej, ne glede na razlog za, se zgodi, da to, da je veliko.
Zato bi bilo makro.
To je dejansko prekinjena.
Jaz bi ga poklical s tem, kaj takega DOUBLE_MAX (3, 6).
Torej, kaj bi bilo treba vrniti?
[Študent] 12.
Da bi bilo treba vrniti 12 in 12 se vrne.
3 gets nadomestiti x, dobi 6 nadomesti za y in se vrnemo 2 * 6, ki je 12.
Kaj je zdaj to? Kaj bi bilo treba vrniti?
[Študent] 14. >> Idealno 14.
Vprašanje je, kako hash opredeljuje delo, se spomnite, da je dobesedno kopiranje in lepljenje
od zal veliko vse, kaj bo to treba razlagati tako,
je 3 manj kot 1 plus 6, 2-krat 1 plus 6, 2-krat 3.
>> Torej iz tega razloga skoraj vedno zaviti vse, kar je v oklepajih.
Vsaka spremenljivka skoraj vedno zaviti v oklepajih.
Obstajajo primeri, kjer ne bi bilo treba, kot vem, da mi ni treba storiti, da tukaj
ker je manj kot je precej vedno le na delovno mesto,
čeprav to morda sploh ne bi bilo res.
Če je kaj smešno, kot DOUBLE_MAX (1 == 2),
potem se dogaja, da se zamenja s 3 manj kot 1 enaka enaka 2,
in tako potem bo naredil 3 manj kot 1, ne da enaka 2,
ki ni tisto, kar si želimo.
Torej, da bi preprečili operaterja izpiąemo težave,
vedno zaviti v oklepajih.
Ok. In to je to, 5:30.
Če imate kakršna koli vprašanja v zvezi z pset, nam to sporočite.
To bi bilo zabavno, in heker izdaja tudi veliko bolj realistična
od hacker izdaji lani, zato upamo, da veliko od vas poskusiti.
Lansko leto je bilo zelo veliko.
>> [CS50.TV]