[Powered by Google Translate] [Kafli 3 - öruggari]
[Rob Bowden - Harvard University]
>> [Þetta er CS50. - CS50.TV]
>> Svo fyrsta spurningin er undarlega orðuð.
GDB leyfir þér "kemba" forrit, en nánar tiltekið, hvað þýðir það að láta þig gera?
Ég svara að einn, og ég veit ekki hvað er nákvæmlega gert ráð fyrir,
þannig að ég ætla að giska á að það er eitthvað á sömu nótum og það leyfir þér skref fyrir skref
ganga í gegnum the program, samskipti við það, breyting breytur, sem gjöri allt þetta -
grundvallaratriðum alveg stjórna framkvæmd áætlunarinnar
og skoða hverjum hluta framkvæmd áætlunarinnar.
Svo þær aðgerðir láta þig kemba það.
Allt í lagi.
Hvers vegna tvöfaldur leita þurfa að fylki er að raða?
Hver vill til að svara því?
[Nemandi] Vegna þess að það virkar ekki ef það er ekki raðað. >> Já. [Hlátur]
Ef það er ekki raðað, þá er það ómögulegt að skipta henni í tvennt
og vita að allt til vinstri er minna og allt til hægri
er meiri en miðju gildi.
Þannig þarf það að vera flokkaður.
Allt í lagi.
Hvers vegna er kúla tegund í O í n veldi?
Er einhver sem vill fyrst að gefa mjög fljótur hár-láréttur flötur yfirlit yfir hvaða kúla tegund er?
[Nemandi] Þú ferð í grundvallaratriðum um hvert frumefni og þú skoðar fyrstu þætti.
Ef þeir eru út af þar sem þú skipta þeim, svo þú stöðva næstu þætti og svo framvegis.
Þegar þú nærð í lok, þá veistu að stærsti þátturinn er sett í lok,
svo þú hunsa að einn þá þú halda áfram að fara í gegnum,
og hvert skipti sem þú þarft að athuga einn minna þáttur þar til þú gera engar breytingar. >> Já.
Það heitir kúla tegund vegna þess að ef þú flettir array á hlið svo það er upp og niður, lóðrétt,
þá stóru gildin munu sökkva til botns og litlu gildi mun kúla upp á toppinn.
Það er hvernig það fékk nafn sitt.
Og já, þú ferð bara í gegnum.
Þú halda að fara í gegnum fylking, skipta stærri gildi
til að fá stærstu gildi til the botn.
>> Hvers vegna er það O n veldi?
Í fyrsta lagi er einhver langar að segja hvers vegna það er O n veldi?
[Nemandi] Þar fyrir hvern tíma það fer n sinnum.
Þú getur aðeins verið viss um að þú hafir tekið Stærsti parturinn alla leið niður,
þá verður þú að endurtaka þetta fyrir eins mörgum þáttum. >> Já.
Svo hafa í huga hvað stór O þýðir og hvað stór þýðir Omega.
Stóri O er eins og efri mörk á hversu hægt það getur í raun keyrt.
Svo með því að segja o Það er í n veldi, það er ekki O n annars það væri hægt að keyra
í línulegum tíma, en það er O n cubed
því það afmarkast af O í n cubed.
Ef það er umlukin O á n veldi, þá er það takmarkast einnig af n cubed.
Svo það er n veldi, og í hreinum versta tilfelli getur það ekki gert betur en n veldi,
sem er hvers vegna það er O n veldi.
Svo að sjá smá stærðfræði á hvernig það kemur út að vera N veldi,
Ef við höfum fimm hluti á listanum okkar, í fyrsta sinn hversu margir samningar gætum við þurfum hugsanlega að
í því skyni að fá þetta? Við skulum reyndar bara -
Hversu margir skiptasamningar við erum að fara að gera í fyrsta hlaupa af tegund kúla gegnum fylki?
[Nemandi] n - 1. >> Já.
>> Ef það eru 5 þættir, við erum að fara að þurfa að gera n - 1.
Síðan á seinni hversu margir skiptasamningar við erum að fara að gera?
[Nemandi] n - 2. >> Já.
Og þriðja er að fara að vera n - 3, og þá til þæginda mun ég skrifa síðustu tvær
eins og þá sem við erum að fara að þurfa að gera 2 skiptasamninga og 1 Víxla.
Ég held að síðasta mega eða mega ekki í raun að gerast.
Er það skipti? Ég veit ekki.
Svo þetta eru alls fjárhæðir skiptasamninga eða amk samanburður sem þú þarft að gera.
Jafnvel ef þú skipta ekki, þú þarft samt að bera gildi.
Þannig að það eru n - 1 samanburður á fyrsta hlaupa í gegnum array.
Ef þú endurskipuleggja þetta, við skulum í raun að gera það sex hlutum svo það stafla upp fallega,
og þá ég skal gera 3, 2, 1.
Svo bara endurskipuleggja þessar upphæðir, við viljum að sjá hversu margir samanburð við tökum
í öllu reiknirit.
Þannig að ef við tökum þessar krakkar hérna,
þá erum við samt bara að leggja saman þó margir samanburð voru.
En ef við summa þetta og við summa þetta og við summa þetta,
það er enn sama vandamál. Við summa bara þessum tiltekna hópa.
>> Svo nú erum við að leggja saman 3 er n. Það er ekki bara 3 er n.
Það er alltaf að fara að vera N / 2 er n.
Svo hér við átt 6.
Ef við hefðum 10 hlutum, svo við gætum gert þetta hópar í 5 mismunandi pör af hlutum
og endar með n + n + n + n + n.
Svo þú ert alltaf að fara að fá N / 2 er n, og svo þetta sem við munum hripa það út til n veldi / 2.
Og svo jafnvel þó að það er þáttur í helming, sem gerist að koma í
vegna þess að með hverri ítrun yfir fylki við saman 1 minna
svo er það hvernig við fá yfir 2, en það er samt n veldi.
Við sama um stöðugum þáttur um helming.
Svo mikið af stór O efni eins og þetta byggir á bara góður að gera þessa tegund af stærðfræði,
gera tölur fjárhæðir og geometrísk röð efni,
en af ​​þeim á þessu námskeiði eru frekar einfalt.
Allt í lagi.
Hvers vegna er insertion sort í Omega í n? Hvað þýðir Omega meina?
[Tveir nemendur tala í einu - óskiljanlegur] >> Já.
Omega er hægt að hugsa um eins og neðri bundinn.
>> Svo sama hversu duglegur insertion sort reiknirit er,
burtséð frá listanum sem er samþykkt í, hefur það alltaf að bera að minnsta kosti n hluti
eða það hefur að iterate yfir n hlutum.
Hvers vegna er það?
[Nemandi] Vegna þess að ef listinn er þegar raðað, þá í gegnum fyrsta endurtekning
þú getur aðeins tryggt að fyrsta þáttur er minnst,
og annað endurtekning þú getur aðeins ábyrgst fyrstu tvær eru
vegna þess að þú veist ekki að restin af listanum er raðað. >> Já.
Ef þú fara í algjörlega raðaða lista, á the mjög minnstur þú ert að fara yfir alla þætti
til að sjá að ekkert þarf að vera flutt í kring.
Svo farið yfir listann og segja ó, þetta er þegar raðað,
það er ómögulegt fyrir þig að vita að það er raðað þar til þú athuga hvert frumefni
til að sjá að þeir eru í raðað röð.
Svo neðri bundinn á Innsetningarröðun er Omega í n.
Hvað er það versta tilfelli í gangi tími Mergesort,
versta tilfelli vera stór O aftur?
Svo í versta falli, hvernig virkar Mergesort hlaupa?
[Nemandi] N log n. >> Já.
The Festa almenn reiknirit flokkun eru n log n. Þú getur ekki gert betur.
>> Það eru sérstök tilfelli, og ef við höfum tíma í dag - en við won't líklega -
við gátum séð sem virkar betur en n log n.
En í almennu máli, getur þú ekki gert betur en n log n.
Og sameina tegund verður að vera sá sem þú ættir að vita að þetta námskeið sem er n log n.
Og svo munum við í raun að framkvæma það í dag.
Og að lokum, í ekki meira en þrjár setningar, hvernig virkar val konar vinna?
Hefur einhver vilja til að svara, og ég ætla að telja setningar þínar
því ef þú ferð yfir 3 -
Hefur einhver man val sort?
Val tegund er yfirleitt mjög auðvelt að muna bara frá nafni.
Þú iterate rúmlega array, finna hvað er stærsta gildi eða minnsta -
hvað röð þú ert að flokka inn
Svo skulum segja að við erum að flokka frá smæstu til stærstu.
Þú iterate yfir fjölda, leita hvað lágmarks þáttur er,
velja hana og síðan bara skipta henni hvað er í fyrsta sæti.
Og þá á öðrum fara yfir fjölda, leita lágmarks frumefni aftur,
velja það, og þá skipta um það með hvað er í annarri stöðu.
Þannig að við erum bara að tína og velja Lágmarksgildi
og setja þá inn í the andlit af the array þar til það er flokkað.
Spurningar um það?
>> Þetta virðist óhjákvæmilega í formi sem þú þarft að fylla út ef þú ert að skila inn pset.
Þeir eru í grundvallaratriðum svör við þeim.
Jæja, svo nú erfðaskrá vandamál.
Ég sendi nú þegar út í tölvupósti - Var einhver ekki fá þessi email? Allt í lagi.
Ég sendi nú þegar út í tölvupósti rými sem við erum að fara að vera með,
og ef þú smellir á nafnið mitt - svo ég held að ég ætla að vera neðst
vegna afturábak r - en ef þú smellir á nafnið mitt sérðu 2 endurskoðun.
Útgáfa 1 er að fara að ég afritað og límt kóðann inn Spaces
að leita hlutur þú ert að fara að framkvæma.
Og Revision 2 verður eins konar hlutur sem við framkvæma eftir það.
Svo er hægt að smella á Revision minn 1 og vinna þaðan.
Og nú viljum við innleiða tvöfaldur leit.
>> Er einhver sem vill bara gefa sauðakóðanum háttsettum skýringu
af því sem við erum að fara að gera fyrir leit? Já.
[Nemandi] Þú tekur bara miðju fylkisins og sjá hvort það sem þú ert að leita að
er minna en eða meira en það.
Og ef það er minna, þú ferð að hluta sem er minna,
og ef það er meira, þú ferð að hluta sem er meira og þú endurtaka það þar til þú færð bara eitt.
[Bowden] Já.
Takið eftir að númer array okkar er þegar raðað,
og svo þýðir það að við getum nýtt sér það og við gátum fyrst að athuga,
allt í lagi, ég er að leita að númer 50.
Svo ég get farið inn á miðju.
Miðjunni er erfitt að skilgreina hvenær það er slétt tala af hlutur,
en við skulum bara segja að við munum alltaf HÃ við miðju.
Svo hér höfum við 8 hlutum, þannig að miðja væri 16 ára.
Ég er að leita að 50, svo 50 meiri en 16 ára.
Svo nú get ég í raun meðhöndla array mitt sem þessum þáttum.
Ég get henda allt frá 16 yfir.
Nú er array minn bara þessir 4 þættir, og ég endurtek.
Svo ég vil að finna miðju aftur, sem er að fara að vera 42.
42 er minna en 50, þannig að ég get henda þessum tveimur þáttum.
Þetta er eftir array mín.
Ég ætla að finna miðju aftur.
Ég giska á 50 var slæmt fordæmi vegna þess að ég var alltaf að henda burt það til vinstri,
en með sömu mál, ef ég er að leita að einhverju
og það er minna en frumefni Ég er nú að leita á,
þá ætla ég að henda öllu til hægri.
Svo nú þurfum við að framkvæma það.
Takið eftir að við þurfum að fara að stærð.
Við getum líka ekki að harða kóða stærð.
Þannig að ef við losna við að # define -
Allt í lagi.
Hvernig get ég fundið fallega út hvað stærð númer array nú er?
>> Hversu mörg frumefni eru í númer array?
[Nemendur] Numbers, sviga,. Lengd?
[Bowden] Það er ekki til í C.
Þarftu. Lengd.
Fylki hefur ekki eiginleika, svo það er engin lengd eign fylki
það verður bara að gefa þér þó lengi það gerist að vera.
[Nemandi] Sjá hversu mikið minni hún hefur og deila með hversu mikið - >> Já.
Og hvernig getum við séð hversu mikið minni hún hefur? >> [Nemandi] sizeof. >> Já, sizeof.
Sizeof er stjórnandi sem er að fara að skila stærð númer fylkisins.
Og það er að fara að vera þó margar heiltölur eru sinnum the stærð af heiltölu
Þar sem er hversu mikið minni það er í raun að taka upp.
Svo ef ég vil ýmislegt í fylking,
þá er ég að fara til að vilja skipta um stærð heiltala.
Allt í lagi. Svo leyfir að mér að fara í stærð hér.
Hvers vegna þarf ég að fara í stærð á öllum?
Hvers vegna get ég ekki bara upp hér int size = sizeof (Haystack) / sizeof (int)?
Hvers vegna virkar þetta ekki?
[Nemandi] Það er ekki alþjóðlegt breytu.
[Bowden] Haystack til og við erum sem liggur í tölum sem Heysátan,
og þetta er góður af a foreshadowing um hvað er að koma. Já.
[Nemandi] Haystack er bara tilvísun í það, þannig að það myndi koma aftur hversu stór sem tilvísun.
Já.
Ég efast í fyrirlestri sem þú hefur séð stafla enn í raun, ekki satt?
Við höfum bara talað um það.
Svo er stafla þar sem allar breytur eru að fara að geyma.
>> Allir minni sem er úthlutað fyrir staðbundnum breytur er að fara í á mánudaginn,
og hver aðgerð fær eigin rúm hennar á mánudaginn, eiga stafla ramma þess er hvað það er kallað.
Svo helstu hefur stafla ramma þess, og inni í því er að fara að vera þetta númer array,
og það er að fara að vera sizeof stærð (númer).
Það er að fara að hafa stærð talna deilt með stærð þáttum,
en alla ævi innan ramma stafla aðal.
Þegar við köllum leit, fær eigin stafla ramma þess,
eigin rúm til þess að geyma allar staðbundnar breytur hennar.
En þessi rök - það er Heysátan ekki afrit af þessu öllu fylki.
Við fara ekki í öllu fylkinu sem afrit í leit.
Það fer bara tilvísun í það fylki.
Svo leita aðgang þessar tölur gegnum þessa tilvísun.
Það er enn að fá aðgang að hlutum sem lifa innan ramma stafla aðal,
en í grundvallaratriðum, þegar við komum að ábendingum, sem ætti að vera fljótlega,
þetta er það sem ábendingum er.
Ábendingar eru bara tilvísanir í hluti, og þú getur notað ábendingum til aðgang hluti
sem eru í ramma stafla annar hlutur.
Svo jafnvel þótt númer er staðbundin að helstu, getum við samt í gegnum þetta músina.
En þar sem það er bara músina og það er bara viðmið,
sizeof (Haystack) skilar bara stærð tilvísun sjálft.
Það þýðir ekki að skila stærð málið það bendir til.
Það þýðir ekki að skila raunverulegri stærð af tölum.
Og svo er þetta ekki að fara að vinna eins og við viljum það til.
>> Spurningar um það?
Ábendingum verður farið í í marktækt Gory smáatriðum í vikur til að koma.
Og þetta er ástæðan fyrir a einhver fjöldi af hlutur sem þú sérð, the leita hlutum eða raða hlutum,
þeir eru nánast allir að fara að þurfa að taka raunverulegan stærð fylkisins,
því að í C, höfum við ekki hugmynd um hvað stærð fylkisins er.
Þú þarft að höndunum gefa það inn
Og þú getur ekki handvirkt að fara í öllu fylkinu vegna þess að þú ert bara farið í tilvísun
og það er ekki hægt að fá stærð frá viðmiðunarverði.
Allt í lagi.
Svo nú viljum við að framkvæma það sem var lýst áður.
Þú getur unnið á það í eina mínútu,
og þú þarft ekki að hafa áhyggjur óður í getting allt fullkomlega 100% vinna.
Bara skrifa upp hálfa sauðakóðanum því hvernig þú heldur að það ætti að virka.
Allt í lagi.
Engin þörf á að vera alveg búin með það enn.
En er einhver líða vel með það sem þeir hafa svo langt,
eins og eitthvað sem við getum unnið með saman?
Er einhver sem vill sjálfboðaliða? Eða mun ég af handahófi velja.
Það þarf ekki að vera rétt því hvaða mál en eitthvað Við getum breytt í starfshóp ástand.
[Nemandi] Jú. >> Lagi.
Svo er hægt að vista útgáfu með því að smella á litlu Vista táknið.
Þú ert Ramya, ekki satt? >> [Nemandi] Já. >> [Bowden] lagi.
Svo nú get ég skoðað endurskoðun og allir geta draga upp endurskoðun.
Og hér höfum við - Allt í lagi.
Svo Ramya fór með endurkvæma lausn, sem er ákveðið gild lausn.
Það eru tvær leiðir sem þú getur gert þetta vandamál.
Þú getur annað hvort gera það iteratively eða undirmöppum.
Flest vandamál sem þú lendir það er hægt að gera endurkvæmt getur líka verið gert iteratively.
Svo hér höfum við gert það í undirmöppum.
>> Hefur einhver vilja til að skilgreina hvað það þýðir að gera fall endurkvæma?
[Nemandi] Þegar þú ert með virka kalla sig
og þá kalla sig þangað til það kemur út með rétt og satt. >> Já.
A endurkvæma virka er bara fall sem kallar sig.
Það eru þrjú stór atriði sem endurkvæma virka verður að hafa.
Í fyrsta lagi er augljóslega, kallar það sig.
Annað er undirstaða raunin.
Svo á einhverjum tímapunkti fallið þarf að hætta að kalla sig,
og það er það sem grunn tilfelli er fyrir.
Svo hér við vitum að við ættum að hætta ætti við að gefast upp í leit okkar
þegar byrja jafnt enda - og við munum fara yfir hvað þetta þýðir.
En að lokum, the síðastur hlutur sem er mikilvægt fyrir endurkvæma virka:
aðgerðir verða einhvern veginn nálgast grunn tilfelli.
Eins ef þú ert í raun ekki að uppfæra neitt þegar þú annað endurkvæma hringja,
Ef þú ert bókstaflega bara að hringja í virkni aftur með sömu rökum
og engin global breytur hafa breyst eða eitthvað,
þú munt aldrei ná stöð að ræða, í því tilviki sem er slæmt.
Það mun vera óendanlega endurkvæmni og stafla flæða.
En hér sjáum við að uppfæra er að gerast þar sem við erum að byrja að uppfæra + End / 2,
Við erum að uppfæra á hætta rifrildi hér, við erum að uppfæra byrjun rök hér.
Svo í öllum endurkvæma símtöl við erum að uppfæra eitthvað. Allt í lagi.
Viltu ganga okkur í gegnum lausn þína? >> Jú.
Ég er að nota SearchHelp þannig að í hvert skipti sem ég geri þetta virka símtalinu
Ég hef upphaf þar sem ég er að leita að í fylkinu og í lok
um þar sem ég er að leita að fylki.
>> Við hvert skref sem það er að segja það er miðju þáttur sem er að byrja að + enda / 2,
er miðaður við það sem við erum að leita að?
Og ef það er, þá fundum við það, og ég held að fær liðið upp magn endurkvæmni.
Og ef það er ekki satt, þá erum við að athuga hvort að miðju gildi fylkisins er of stór,
í því tilviki við líta á vinstri hluta fylkisins með því að fara frá upphafi til miðju vísitölunni.
Og annað sem við gerum á hætta helminginn.
[Bowden] lagi.
Það hljómar vel.
Jæja, svo nokkra hluti, og í raun er þetta mjög háttsettum hlutur
að þú munt aldrei þurfa að vita fyrir þetta námskeið, en það er satt.
Endurkvæmar aðgerðir, heyrir þú alltaf að þær séu slæmur samningur
því ef þú kallar endurkvæmt þig of oft, þá færðu stafla flæða
síðan, eins og ég sagði áður, hvert hlutverk fær eigin stafla ramma þess.
Þannig fær hvert símtal um endurkvæma virka eigin stafla ramma þess.
Svo ef þú gerir 1000 endurkvæma símtöl, þá færðu 1.000 stakkur ramma,
og fljótt þú leiða til að hafa of marga stafla ramma og svoleiðis bara brot.
Svo er það hvers vegna endurkvæma virka almennt illa.
En það er a ágætur hluti af endurkvæma virka kallað hali-endurkvæma virka,
og þetta gerist að vera dæmi um einn þar ef þýðandinn tilkynningar þetta
og það ætti, held ég - í Clang ef þú gefa það á-O2 merkja
þá mun það taka þetta er hali endurkvæma og gera hlutina vel.
>> Það mun endurnýta sömu stafla ramma aftur og aftur fyrir hvern endurkvæma hringja.
Og svo þar sem þú ert að nota sömu stafla ramma, þú þarft ekki að hafa áhyggjur
alltaf stafla barmafullur, og á sama tíma, eins og þú sagðir áður,
þar þegar þú kemur aftur satt, þá hefur það að fara aftur upp öllum þessum stafla ramma
og 10 kalla til SearchHelp að fara aftur í 9, þarf að fara aftur til 8..
Svo þarf ekki að gerast þegar aðgerðir eru hali endurkvæma.
Og svo er það sem gerir þessa aðgerð hali endurkvæma Athugið að í hverju símtali til searchHelp
endurkvæma hringja að það er að gera er það sem það er að koma aftur.
Svo í fyrstu kalla til SearchHelp, annaðhvort við strax aftur rangar,
strax aftur satt, eða við tökum endurkvæma hringja til SearchHelp
þar sem við erum að koma aftur er það sem kalla er að fara aftur.
Og við gátum ekki gert þetta ef við gerðum eitthvað eins og int x = SearchHelp, skila X * 2,
bara nokkrar af handahófi breyting.
>> Svo nú þetta endurkvæma hringja, þetta int x = SearchHelp endurkvæma hringja,
er ekki lengur hali endurkvæma vegna þess að það raunverulega hjartarskinn þurfa að snúa
til baka í fyrri stafla ramma svo að fyrri hringja í aðgerð
geta þá gert eitthvað með skilagildi.
Svo er þetta ekki hali endurkvæma, en það sem við höfðum áður er fallega hali endurkvæma. Já.
[Nemandi] Ætti ekki annað stöð mál að athuga fyrst
vegna þess að það gæti verið aðstæður þar sem þegar þú standist það rök
þú byrjar = enda, en þeir eru nál gildi.
Spurningin var ekki hægt að hlaupa í málið þar enda er nálin gildi
eða byrja = enda, viðeigandi, start = enda
og þú hefur í raun ekki athugað þessa tilteknu gildi enn,
þá byrja + End / 2 er bara að fara að vera á sama gildi.
En við höfum nú þegar aftur rangar og við aldrei athugað gildi.
Svo að minnsta kosti, í fyrsta símtali, ef stærð er 0, þá viljum við skila falskur.
En ef stærð er 1, þá er að byrja er ekki að fara að jafna enda,
og við munum að minnsta kosti athuga eitt frumefni.
En ég held að þú ert rétt í því að við getum endað í máli þar byrja + End / 2,
byrja endar að vera það sama og upphafi + End / 2,
en við aldrei athugað að frumefni.
>> Þannig að ef við athugum fyrst er miðja þáttur gildi sem við erum að leita að,
þá getum við strax aftur satt.
Annars ef þeir eru jafnir, þá er ekkert lið í að halda áfram
þar sem við erum bara að fara að uppfæra í máli þar sem við erum á einum staka fylki.
Ef að einn þáttur er ekki það sem við erum að leita að,
þá er allt vitlaust. Já.
[Nemandi] Málið er að þar sem stærð er í raun stærri en fjöldi staka í fylkinu,
Það er nú þegar móti - >> Svo mun stærð -
[Nemandi] Segja ef array var stærð 0, þá SearchHelp mun reyndar athuga Heysátan af 0
á fyrsta símtali.
Array er stærð 0, þannig að 0 er - >> Já.
Það er annar hlutur sem - það gæti verið gott. Við skulum hugsa.
Svo ef array hafði 10 þætti og miðja sem við erum að fara að athuga vísitölu 5,
þannig að við erum að athuga 5, og við skulum segja að gildið er minna.
Þannig að við erum að henda allt frá 5 áfram.
Svo byrjar + endir / 2 er að fara að vera nýr enda okkar,
svo já, það er alltaf að fara að vera út í lok fylkisins.
Ef það er málið ef það væri jafnvel eða stakur, þá myndum við stöðva, segja, 4,
en við erum enn að henda í burtu -
Svo já, enda er alltaf að fara að vera út raunverulegan enda fylkisins.
Svo þætti sem við erum með áherslu á, enda er alltaf að fara að vera einn eftir það.
Og svo ef byrja er alltaf jafn enda erum við í fylki af stærð 0.
>> The annar hlutur sem ég var að hugsa er að við erum að uppfæra byrja að byrja + enda / 2,
þannig að þetta er raunin að ég er í vandræðum með, hvar byrja + End / 2
er þáttur sem við erum að skoða.
Við skulum segja að við höfðum þetta 10-þátturinn array. Whatever.
Svo byrjar + endir / 2 er að fara að vera eitthvað eins og þessi,
og ef það er ekki verðmæti, segjum við að uppfæra.
Gildið er meiri, þannig að við viljum líta á þetta hluta fylkisins.
Svo hvernig við erum að uppfæra byrja, við erum að uppfæra byrja að nú sé þetta þáttur.
En þetta getur samt vinna, eða að minnsta kosti er hægt að byrja + endir / 2 + 1.
[Nemandi] Þú þarft ekki að byrja + End [inaudible] >> Já.
Við höfum þegar athugað þennan þátt og veit að það er ekki sá sem við erum að leita að.
Þannig að við þurfum ekki að uppfæra byrja að vera svona þáttur.
Við getum bara sleppt því og uppfæra byrja að vera svona þáttur.
Og er það alltaf gott dæmi, við skulum segja, að þetta væri endir,
svo þá byrja væri þetta, byrja + End / 2 væri þetta,
byrja + End - Já, ég held að það getur endað í óendanlega endurkvæmni.
Við skulum segja að það er bara fylki af stærð 2 eða fylki af stærð 1. Ég held að þetta muni virka.
Svo nú, byrja að frumefni og enda er 1 utan það.
Svo er þáttur sem við erum að fara að athuga þetta,
og svo þegar við uppfærum byrja, við erum að uppfæra byrja að vera 0 + 1/2,
sem er að fara að enda okkur aftur með því að vera að byrja á þessu atriði.
>> Þannig að við erum að athuga sömu frumefni aftur og aftur.
Svo er þetta málið þar sem hvert endurkvæma hringja þarf reyndar að uppfæra eitthvað.
Þannig að við þurfum að byrja + End / 2 + 1, eða annað það er málið
þar sem við erum í raun ekki að uppfæra byrjun.
Allir sjá að?
Allt í lagi.
Hefur einhver hefur einhverjar spurningar um þessa lausn eða einhver fleiri athugasemdir?
Allt í lagi. Hefur einhver hafa endurtekningu lausn sem við getum öll líta á?
Gerði við gerum allt það undirmöppum?
Eða líka að ég held ef þú opnað hennar, þá þú might hafa yfirkeyrt fyrri einn.
Er það spara sjálfkrafa? Ég er ekki jákvæð.
Hefur einhver hafa endurtekningu?
Við getum gengið í gegnum það saman ef ekki.
Hugmyndin er að fara til vera the sami.
Endurtekningu lausn.
Við erum að fara til að vilja grundvallaratriðum sömu hugmynd
þar sem við viljum halda utan um nýju enda fylkisins og nýja byrjun í fylkinu
og gera það aftur og aftur.
Og ef það sem við erum að halda utan um eins og í upphafi og enda alltaf skerast,
þá erum við ekki að finna hana og við getum aftur rangar.
Svo hvernig á ég að gera það? Einhver hafa ábendingar eða kóða fyrir mig að draga upp?
[Nemandi] Do a while lykkju. >> Já.
Þú ert að fara til að vilja gera lykkju.
>> Vissir þú hefur númerið ég gæti draga upp, eða hvað varstu að fara að stinga upp á?
[Nemandi] Ég held það. >> Allt í lagi. Þetta gerir það auðveldara. Hvað var nafn þitt?
[Nemandi] Lucas.
Revision 1. Allt í lagi.
Low er það sem við kallað byrja áður.
Up er ekki alveg það sem við kallað enda áður.
Reyndar, enda er nú innan fylkisins. Það er þáttur sem við ætti að íhuga.
Svo lágt er 0, allt er the stærð af the array - 1,
og nú erum við lykkja, og við erum að skoða -
Ég giska á að þú getur gengið í gegnum það.
Hver var að hugsa með þessu? Ganga okkur í gegnum kóðann þinn.
[Nemandi] Jú. Horfðu á Haystack gildi í miðju og bera saman það til nál.
Svo ef það er meira en nál, þá þú vilt - ó, í raun, það ætti að vera aftur á bak.
Þú ert að fara til að vilja henda rétt hluta, og svo já, það ætti að vera leið.
[Bowden] Þannig að þetta ætti að vera minna? Er það sem þú sagðir? >> [Nemandi] Já.
[Bowden] lagi. Minna.
Svo ef það sem við erum að horfa á er minni en það sem við viljum,
þá já, viljum við henda vinstri hálfleik
sem þýðir að við erum að uppfæra allt sem við erum að íhuga
með því að færa lágmark til hægri fylkisins.
Þetta lítur vel út.
Ég held að það hafi sama mál sem við sögðum á undan,
þar ef lítið er 0 og upp er 1, þá er lágmark + upp / 2 er að fara að setja upp til að vera það sama aftur.
>> Og jafnvel ef það er ekki málið, það er enn skilvirkari minnsta kosti
bara henda þáttur við litum bara á sem við vitum er rangt.
Svo lág + upp / 2 + 1 - >> [nemandi] Það ætti að vera önnur leið.
[Bowden] Eða það ætti að vera - 1 og hitt ætti að vera + 1.
[Nemandi] Og það ætti að vera tvöfaldur jafn skilti. >> [Bowden] Já.
[Nemandi] Já.
Allt í lagi.
Og að lokum, nú þegar við höfum þetta + 1 - 1 hlutur,
er það - það gæti ekki verið - það er alltaf hægt að lágt til endir upp með a gildi sem er stærra en allt?
Ég held að eina leiðin sem getur gerst - Er það mögulegt? >> [Nemandi] Ég veit ekki.
En ef það gerist stytt og þá fær mínus að 1 og þá - >> Já.
[Nemandi] Það myndi hugsanlega fá boðberi upp.
Ég held að það ætti að vera góður bara af því
fyrir það að enda minni að þeir myndu þurfa að vera jafnir, held ég.
En ef þeir eru jafnir, þá myndum við ekki hafa gert meðan lykkja til að byrja með
og við bara hefði aftur gildi. Þannig að ég held að við séum gott núna.
Takið eftir að jafnvel þótt þetta vandamál er ekki lengur endurkvæma,
sams konar hugmyndir um hvar við getum séð hvernig þetta svo auðveldlega lánar sig
í endurkvæma lausn af því að við erum bara að uppfæra vísitölur aftur og aftur,
við erum að gera vandamál minni og minni, við erum með áherslu á hlutmengi fylkisins.
[Nemandi] Ef lágt er 0 og upp er 1, myndu þeir báðir vera 0 + 1/2, sem myndi fara til 0,
og þá mætti ​​vera + 1, vildi einn vera - 1.
[Nemandi] Hvar erum við að skoða jafnrétti?
Eins ef miðju einn er í raun nál?
Við erum ekki eins og að gera það? Oh!
Ef it's -
Já. Við getum ekki bara að gera prófið hérna því Segjum að fyrsta miðju -
[Nemandi] Það er í raun ekki eins og henda bundið.
Svo ef þú henda bundið, þú þarft að athuga það fyrst eða hvað.
Ah. Já. >> [Nemandi] Já.
Svo nú höfum við hent einn við litum nú á,
sem þýðir að við þurfum nú að hafa einnig
if (Haystack [(lítil + allt) / 2] == nál), þá getum við aftur satt.
Og hvort ég setti annað eða bara ef það þýðir bókstaflega það sama
vegna þess að þetta hefði skilað satt.
Svo ég ætla að setja annað hvort, en það skiptir ekki máli.
>> Svo annað ef þetta, annars þetta og þetta er algengt sem ég geri
þar sem jafnvel ef það er raunin þar sem allt er gott hér,
eins lágt getur aldrei verið meiri en allt, það er ekki þess virði að rök um það hvort það er satt.
Svo þú getur svo að segja á meðan lítið er minna en eða jafnt og
eða á meðan lágt er minni en
svo gerist ef þeir eru alltaf jafn eða lágt til að fara upp,
þá getum við brjótast út úr þessari lykkju.
Spurningum, áhyggjur, athugasemdir?
Allt í lagi. Þetta lítur vel út.
Nú viljum við að gera svoleiðis.
Ef við förum í seinni endurskoðun minn, sjáum við þessar sömu tölur,
en nú eru þeir ekki lengur í raðað röð.
Og við viljum að innleiða konar nota hvaða reiknirit í O í n log n.
Svo sem reiknirit finnst þér að við ættum að innleiða hér? >> [Nemandi] Mergesort.
[Bowden] Já. Mergesort er O (n log n), svo það er það sem við erum að fara að gera.
Og vandamálið er að fara að vera mjög svipuð,
þar sem það lánar auðveldlega sig við endurkvæma lausn.
Við getum einnig að koma upp með endurtekningu lausn ef við viljum,
en endurkvæmni verður auðveldara hér og við ættum að gera endurkvæmni.
Ég held að við munum ganga í gegnum Mergesort fyrst,
þó það er yndisleg vídeó á Mergesort þegar. [Hlátur]
Svo Mergesort það eru - ég er að eyða svo mikið af þessum pappír.
Ó, það er aðeins einn eftir.
Svo sameinast.
Ó, 1, 3, 5.
Allt í lagi.
Merge tekur tvö aðskilin fylki.
Sig þessi tvö fylki eru bæði flokkað.
Þannig að þetta fylki, 1, 3, 5, raðað. Þessi fylki, 0, 2, 4, flokkað.
Nú er það sameinast ætti að gera sameina þær í eina fylkingu sem er sjálf raðað.
Þannig að við viljum á fjölbreytta stærð 6 sem er að fara að hafa þessi atriði inni í því
í raðað röð.
>> Og svo við getum nýta þá staðreynd að þessi tvö fylki eru flokkuð
að gera þetta í línulegum tíma,
línuleg sinn sem þýðir að ef þetta fylki er stærð x og þetta er stærð y,
þá alls reiknirit að vera O (x + y). Allt í lagi.
Svo tillögur.
[Nemandi] Gat við byrjum frá vinstri?
Svo þú munt setja 0 niður fyrst og síðan 1 og þá hér þú ert á 2.
Svo það er góður af eins og þú hafa a flipi sem er að flytja til hægri. >> [Bowden] Já.
Fyrir bæði þessi fylki ef við einbeitum okkur bara á lengst frumefni.
Vegna bæði fylki eru flokkuð, vitum við að þessir 2 þættir
eru minnstu einingar í hvoru fylki.
Svo þýðir að 1 af þessum 2 þáttum verður að vera minnsti þáttur í sameinaða fylking okkar.
Það bara gerist þannig að minnsti er einn á hægri og er.
Svo við tökum 0, setja það á vinstri því 0 er minna en 1,
þannig að 0, setja það inn í efstu stöðu okkar, og þá erum við að uppfæra þetta
að nú áherslu á fyrstu frumefni.
Og nú erum við að endurtaka.
Svo nú erum við að bera saman 2 og 1. 1 er minni, þannig að við munum setja inn 1.
Við uppfæra músina til að benda á þennan gaur.
Nú erum við að gera það aftur, svo 2. Þetta mun uppfæra og bera saman þessar 2, 3.
Þetta uppfærslur, síðan 4 og 5.
Svo er að sameinast.
>> Það ætti að vera nokkuð augljóst að það er línuleg tími þar sem við förum bara yfir hvert frumefni einu.
Og það er stærsta skrefið til að innleiða Mergesort er að gera þetta.
Og það er ekki það erfitt.
Tveimur atriði til að hafa áhyggjur óður í er við skulum segja að við vorum að sameina 1, 2, 3, 4, 5, 6.
Í þessu tilfelli erum við að enda í atburðarás þar sem þetta er að fara að vera minni,
þá erum við að uppfæra músina, þetta er að fara að vera minni, uppfæra þetta,
þetta er minni, og nú þú ert að viðurkenna
þegar þú hefur keyrt í raun út af þáttum til að bera saman við.
Þar sem við höfum nú þegar að nota þetta allt array,
allt í þessu fylki er nú bara sett inn hér.
Þannig að ef við hlaupa alltaf í stað þar sem eitt fylki okkar er alveg sameinast nú þegar,
þá erum við að taka bara alla þætti hins array og setja þá í lok fylkisins.
Þannig að við getum bara setja 4, 5, 6. Allt í lagi.
Það er eitt að horfa út fyrir.
Framkvæmd sem ætti að vera skref 1.
Sameina raða þá byggt á því, er það 2 skref, 2 kjánalegt skref.
Við skulum gefa bara þetta fylki.
Svo Mergesort, skref 1 er að endurkvæmt brjóta fylki í helminga.
Svo skipta þessu fylki í helminga.
Við höfum nú 4, 15, 16, 50 og 8, 23, 42, 108.
Og nú erum við að gera það aftur og við hættu þessir í helminga.
Ég ætla bara að gera það á þessari hlið.
Svo 4, 15 og 16, 50.
Við viljum gera það sama hérna.
Og nú erum við skipt því í helminga aftur.
Og við höfum 4, 15, 16, 50.
Svo er þessi stöð mál okkar.
Þegar fylki eru stærð 1, þá erum við að hætta við að skipta í helminga.
>> Nú hvað gerum við við þetta?
Við á endanum mun þetta einnig brjóta niður í 8, 23, 42, og 108.
Svo nú er að við erum á þessum tímapunkti, nú stíga tveir Mergesort er bara að sameina pör á listum.
Þannig að við viljum að sameina þá. Við köllum bara steypa.
Við vitum sameinast aftur þetta í raðað röð.
4, 15.
Nú viljum við að sameina þetta, og það mun skila lista með þeim í raðað röð,
16, 50.
Við sameina þá - ég get ekki skrifað - 8, 23 og 42, 108.
Þannig að við höfum sameinað par einu sinni.
Nú erum við að sameinast bara aftur.
Takið eftir því hver af þessum listum er raðað í sjálfu sér,
og þá getum við bara sameinast þessum listum til að fá lista af stærð 4, sem er raðað
og sameina þessa tvo lista til að fá lista af stærð 4 það er flokkað.
Og að lokum, getum við sameinast þessir tveir listar stærð 4 til fá einn lista yfir stærð 8 sem er raðað.
Svo til að sjá að þetta er almennt N log n, sáum við þegar það sameinast er línuleg,
svo þegar við erum að fást við sameiningu, svo eins og heildarkostnað af sameiningu
fyrir þessar tvær lista er bara 2 af því -
Eða vel, það er O n, en N hér er bara þessir 2 þættir, svo það er 2.
Og þessir 2 verða 2 og þessir 2 verða 2 og þessir 2 verða 2,
svo yfir öll sameinast um að við þurfum að gera, enda við upp að gera n.
Eins og 2 + 2 + 2 + 2 er 8, sem er n,
þannig að kostnaður við sameiningu í þessu mengi er n.
Og þá það sama hér.
Við munum sameina þá 2, þá eru þessir 2, og sérstaklega þetta sameinast mun taka fjórar aðgerðir,
þetta sameinast mun taka fjórar aðgerðir, en enn og aftur, milli allra þeirra,
við á endanum sameina N samtals hlutir, og svo tekur þetta skref n.
Og svo tekur hvert stig n þætti verið sameinuð.
>> Og hve mörg borð eru?
Á hverju stigi, array okkar vex með stærð 2.
Hér fylki okkar eru stærð 1, hér að þeir eru í stærð 2, hér að þeir eru í stærð 4,
og að lokum, þá eru þeir í stærð 8.
Svo þar sem það er tvöföldun, eru að fara að vera alls log n af þessum liðum.
Svo með log n stig, hvert stig að taka N samtals starfsemi,
fáum við n log n reiknirit.
Spurningar?
Hefur fólk gert þegar framfarir á hvernig á að framkvæma þetta?
Er einhver sem þegar í ríki þar sem ég get bara draga upp kóðann þeirra?
Ég get gefið eina mínútu.
Þetta er að fara að vera lengur.
Ég mæli aftur fram -
Þú þarft ekki að gera endurkvæmni fyrir sameiningu
því að gera endurkvæmni fyrir sameiningu, ætlar þú að fara til verða að standast fullt af mismunandi stærðum.
Þú getur, en það er pirrandi.
En endurkvæmni fyrir tegund sjálft er laglegur þægilegur.
Þú bara bókstaflega kalla svoleiðis á vinstri helmingi, flokka á hægri hluta. Allt í lagi.
Einhver hefur eitthvað sem ég get draga upp enn?
Eða annað sem ég ætla að gefa eina mínútu.
Allt í lagi.
Einhver með eitthvað sem við getum að vinna með?
Eða annað sem við verðum bara að vinna við þetta og þá þenja út þaðan.
>> Einhver hafa meira en þetta sem ég get draga upp?
[Nemandi] Já. Þú getur draga upp minn. >> Allt í lagi.
Já!
[Nemandi] Það voru fullt skilyrði. >> Ó, skjóta. Getur þú -
[Nemandi] Ég verð að vista hana. >> Já.
Þannig að við gerðum ekki sameiningu sérstaklega.
Ó, en það er ekki svo slæmt.
Allt í lagi.
Svo er tegund sig bara að hringja mergeSortHelp.
Útskýrðu fyrir okkur hvað mergeSortHelp gerir.
[Nemandi] MergeSortHelp ansi er mikill tvo liði,
sem er að raða hverjum helming fylkisins og síðan að sameina bæði.
[Bowden] Jæja, svo gefa mér annað.
Ég held að þetta - >> [nemandi] ég þarf að -
Já. Ég vantar eitthvað.
Í sameiningu, við gerum ég að ég þarf að búa til nýtt array
vegna þess að ég gat ekki gert það í stað. >> Já. Þú getur ekki. Rétt.
[Nemandi] Svo ég að búa til nýtt array.
Ég gleymdi í lok sameinast við aftur breyta.
Allt í lagi. Við þurfum nýtt fylki.
Í Mergesort, þetta er næstum alltaf satt.
Hluti af kostnaði við betri reiknirit tíma-vitur
er nánast alltaf þurfa að nota aðeins meira minni.
Svo hér, sama hvernig þú sameina konar,
þú myndi óhjákvæmilega þurfa að nota nokkrar auka minni.
Hann eða hún skapaði nýja fylki.
Og þá segir þú í lok við þurfum bara að afrita nýtt array í upprunalegu fylkisins.
[Nemandi] Ég held það, já.
Ég veit ekki hvort það virkar í skilmálar af að telja með tilvísun eða hvað -
Já, það mun virka. >> [Nemandi] lagi.
Vissir þú reynir að keyra þetta? >> [Nemandi] Nei, ekki enn. >> Lagi.
Prófaðu að keyra það, og svo skal ég tala um það fyrir a second.
[Nemandi] Ég þarf að hafa alla virka frumútgáfur og allt, þó, ekki satt?
The virka frumútgáfur. Ó, að þú eins - Já.
Raða kallar mergeSortHelp.
>> Svo í röð til að raða að hringja mergeSortHelp verður mergeSortHelp annaðhvort hafa verið skilgreind
fyrir tegund eða þurfum við bara frumgerð. Bara afrita og líma það.
Og sömuleiðis, mergeSortHelp kallar sameinast
en sameinast hefur ekki verið skilgreint enn, svo að við getum bara látið mergeSortHelp vita
að það er það sem sameinast er að fara að líta út eins og það er það.
Svo mergeSortHelp.
Við höfum málefni hér þar sem við höfum ekki grunn tilfelli.
MergeSortHelp er endurkvæma, svo allir endurkvæma virka
er að fara að þurfa einhvers konar tilfelli stöð til að vita hvenær á að hætta endurkvæmt kalla sig.
Hvað er undirstaða okkar tilviki að fara að vera hér? Já.
[Nemandi] Ef stærð er 1? >> [Bowden] Já.
Svo eins og við sáum þarna, hætt við skerandi fylki
þegar við fengum inn fylki af stærð 1, sem óhjákvæmilega eru flokkuð sig.
Svo ef stærð er 1, vitum við fylki er þegar raðað,
þannig að við getum bara aftur.
>> Takið eftir það er tóm, svo að við ekki aftur neitt sérstaklega, aftur við bara.
Allt í lagi. Svo það er undirstaða okkar tilviki.
Ég held að byggja mál okkar gæti líka verið ef við gerast að sameina óákveðinn greinir í ensku fylking af stærð 0,
við viljum líklega að hætta á einhverjum tímapunkti,
þannig að við getum bara sagt stærð minna en 2 eða minna en eða jafnt og 1
þannig að þetta mun virka fyrir hvaða fylking nú.
Allt í lagi.
Svo það er undirstaða okkar tilviki.
Nú þú vilt að ganga okkur í gegnum sameiningu?
Hvað öll þessi tilfelli þýða?
Up hér, við erum bara að gera sömu hugmynd, að -
[Nemandi] Ég þarf að brottför stærð með öllum mergeSortHelp símtöl.
Ég bætti stærð sem viðbótar aðal og það er ekki þar, eins og stærð / 2.
[Bowden] Ó, stærð / 2, stærð / 2. >> [Nemandi] Já, og einnig í ofangreindum virka eins og heilbrigður.
[Bowden] Hér? >> [Nemandi] Bara stærð. >> [Bowden] Ó. Stærð, stærð? >> [Nemandi] Já.
[Bowden] lagi.
Leyfðu mér að hugsa um annað.
Eigum við að keyra inn í málið?
Við erum alltaf að meðhöndla vinstri sem 0. >> [Nemandi] Nei
Það er rangt líka. Því miður. Það ætti að vera upphafið. Já.
[Bowden] lagi. Mér finnst það betra.
Og enda. Allt í lagi.
Svo nú þú vilt að ganga okkur í gegnum sameiningu? >> [Nemandi] lagi.
Ég er bara að ganga í gegnum þetta nýja fylkingu sem ég hef búið til.
Stærð hennar er á stærð við hluta fylkisins sem við viljum að vera flokkaður
og reyna að finna hluti sem ég ætti að setja í nýju array skref.
Svo til að gera það, fyrst ég er að athuga hvort að vinstri helmingur í fylkinu heldur áfram að hafa neitt fleiri þætti,
og ef það virkar ekki, þá fara niður til að annað ástand, sem bara segir
allt í lagi, það verður að vera í rétta fylking, og við munum setja það í núverandi vísitölu newArray.
>> Og svo annað, ég er að athuga hvort hægra megin í fylkinu er einnig lokið,
þar sem ef ég setti bara í vinstri.
Það gæti í raun ekki verið nauðsynlegt. Ég er ekki viss.
En engu að síður, eru hinir tveir stöðva hvaða tvær minni í vinstri eða hægri.
Og einnig í hverju tilfelli, ég incrementing hvort tákn ég hækka.
[Bowden] lagi.
Það lítur vel út.
Hefur einhver hafa athugasemdir eða áhyggjur eða spurningar?
Svo fjórum tilvikum sem við höfum til að koma hlutum í bara að vera - eða það lítur út eins og fimm -
en við verðum að íhuga hvort vinstri array hefur keyrt út af hlutum sem við þurfum að sameinast,
hvort rétt array hefur keyrt út af hlutum sem við þurfum að sameinast -
Ég er að benda á neitt.
Svo hvort vinstri array hefur keyrt út af hlutum eða rétt array hefur keyrt út af hlutum.
Þeir eru tvö tilvik.
Við þurfum einnig léttvæg ræða hvort vinstri sem er minna en the réttur hlutur.
Þá viljum við að velja vinstri hlutur.
Þeir eru dæmi.
Svo þetta var rétt, svo það er það.
Array vinstri. Það er 1, 2, 3. Allt í lagi. Svo já, eru þeir fjórir hlutir sem við gætum vilja til að gera.
Og við munum ekki fara yfir endurtekningu lausn.
Ég myndi ekki mæla með -
Mergesort er dæmi um fall sem er bæði ekki hali endurkvæma,
það er ekki auðvelt að gera það hali endurkvæma,
en einnig er það ekki mjög auðvelt að gera það endurtekningu.
Þetta er mjög auðvelt.
Þessi framkvæmd Mergesort,
sameinast, það er sama hvað þú gerir, þú ert að fara að byggja sameinast.
>> Svo Mergesort byggt ofan á sameiningu endurkvæmt er bara þessar þrjár línur.
Iteratively er það meira pirrandi og erfiðara að hugsa um.
En eftir að það er ekki hali endurkvæma síðan mergeSortHelp - þegar það kallar sig -
það þarf samt að gera það eftir þetta endurkvæma skilar hringja.
Þannig að þetta stafla ramma verður að halda áfram að vera til jafnvel eftir að kalla þetta.
Og svo þegar þú kallar þetta, stafla ramma verður að halda áfram að vera til
því jafnvel eftir að hringja, þurfum við enn að sameinast.
Og það er nontrivial að þetta hali endurkvæma.
Spurningar?
Allt í lagi.
Svo að fara til baka til að flokka - ó, það er tvennt sem ég vil sýna. Allt í lagi.
Fara aftur til að flokka, við munum gera það fljótt.
Eða leita. Raða? Tagi. Já.
Fara aftur til upphaf tagi.
Við viljum búa til reiknirit sem flokkar fylki með hvaða reiknirit
í O á n.
Svo hvernig er þetta hægt? Hefur einhver hefur einhverjar tegund af -
Ég gefið í skyn áður á -
Ef við erum að fara að bæta úr n log n O á n,
Við höfum bætt reiknirit okkar tími-vitur,
sem þýðir hvað við erum að fara að þurfa að gera til að bæta upp fyrir það?
[Nemandi] Space. >> Já. Við ætlum að vera með meira pláss.
Og ekki einu sinni bara meira pláss, það veldishraða meira pláss.
Þannig að ég held að þessi tegund af reiknirit er falsaður eitthvað gervi polynom -
gervi - Ég man það ekki. Gervi eitthvað.
En það er vegna þess að við þurfum að nota svo mikið pláss
að þetta sé náð en ekki raunhæf.
>> Og hvernig ná við þetta?
Við getum ná þessu ef við tryggjum að allir einkum þáttur í fylkinu
er undir ákveðinni stærð.
Svo við skulum bara segja að stærð er 200,
hvaða þáttur í fylki er undir stærð 200.
Og þetta er í raun mjög raunhæf.
Þú getur mjög auðveldlega hafa fylki sem þú veist allt í það
er að fara að vera minna en sumir tala.
Eins ef þið hafið einhverjar algerlega gegnheill vektor eða eitthvað
en þú veist allt er að fara að vera á milli 0 og 5,
þá er það að fara að vera verulega hraðar til að gera þetta.
Og bundið um einhver þeirra atriða er 5,
þannig að þetta bundið, það er hversu mikið minni þú ert að fara að nota.
Svo er bundið 200.
Fræðilega er alltaf bundið þar heiltala getur aðeins verið allt að 4 milljarða króna,
en það er óraunhæft síðan við myndum vera með rúm
á röð 4 milljörðum króna. Svo er það óraunhæft.
En hér munum við segja bundið okkar er 200.
The bragð til að gera það í O á n við að gera annað fylki kallast telja stærð bundinn.
Svo í raun, þetta er flýtileið fyrir - ég reyndar veit ekki hvort Clang gerir þetta.
En í GCC minnsta kosti - Ég er miðað Clang gerir það líka -
þetta mun bara frumstilla alla array að vera 0s.
Svo ef ég vil ekki að gera það, þá gæti ég sérstaklega gert fyrir (int i = 0;
i <bundið, i + +) og telja [i] = 0;
Svo nú er allt frumstilla í 0.
Ég iterate yfir fylking minn,
og hvað ég er að gera er að ég er að telja fjölda hvers - Við skulum fara niður hér.
Við höfum 4, 15, 16, 50, 8, 23, 42, 108.
Það sem ég er að telja er fjöldi atvika af hverjum þessara þátta.
Skulum raunverulega bæta nokkrum fleiri hér með nokkrum endurtekningar.
Þannig að verðmæti við höfum hér, gildi sem er að fara að vera array [i].
Svo Val gæti verið 4 eða 8 eða hvað sem er.
Og núna er ég að telja hversu margir af þeim gildi sem ég hef séð,
svo telja [Val] + +;
Eftir það er gert, gildir er að fara að líta eitthvað eins og 0001.
Gerum telja [Val] - bundinn + 1.
>> Nú er það bara að gera grein fyrir því að við erum að byrja frá 0.
Svo ef 200 er að fara að vera stærsta númerið okkar,
þá er 0-200 201 hlutir.
Svo telja, mun það líta út eins og 00.001 því við höfum eitt 4.
Síðan munum við hafa 0001 þar sem við munum hafa 1 í 8. vísitölu telja.
Við munum hafa 2 í 23 vísitölu telja.
Við munum hafa 2 í 42 vísitölu telja.
Svo getum við notað telja.
Svo num_of_item = máli [i].
Og svo ef num_of_item er 2, sem þýðir að við viljum að setja 2 í fjölda i
í raðað array okkar.
Þannig að við þurfum að halda utan um hversu langt við erum í array.
Svo vísitölu = 0.
Array - Ég verð bara að skrifa það.
Talning -
array [Vísitala + +] = i;
Er það það sem ég vil? Ég held að það er það sem ég vil.
Já, þetta lítur vel út. Allt í lagi.
Svo er allir skilja hvað varðar telja fylki minn er?
Það er að telja fjölda atvika af öllum þessum tölum.
Og ég er iterating á að telja fjölda,
og ith stöðu á telja fylki
er fjöldi i er sem ætti að birtast í raðað array mínu.
Þess vegna telja 4 er að fara að vera 1
og telja 8 er að fara að vera 1, telja 23 er að fara að vera 2.
Svo er það hversu margir af þeim sem ég vil setja inn raðað array minn.
Og ég bara það.
Ég er að setja num_of_item ég er í raðað array minn.
>> Spurningar?
Og svo aftur, þetta er línuleg tími þar sem við erum bara að iterating yfir þetta einu sinni,
en það er líka línuleg í hvað þessi tala verður að vera,
og svo fer það að miklu leyti á því sem bundið er.
Með bundið af 200, sem er ekki svo slæmt.
Ef bundið er að fara að vera 10.000, þá er það aðeins verra,
en ef bundið er að fara að vera 4 milljarðar það er alveg óraunhæft
og þetta fylki er að fara til verða að vera af stærð 4 milljarða, sem er óraunhæft.
Svo er það það. Spurningar?
[Inaudible nemandi svar] >> lagi.
Ég áttaði mig á eitt annað hlutur þegar við vorum að fara í gegnum.
Ég held að vandamálið var í er Lucas og sennilega hvert einasta sem við höfum séð.
Ég gleymdi alveg.
Það eina sem ég vildi gera athugasemd við er að þegar þú ert að takast á við hluti eins og vísitalna,
þú aldrei raunverulega séð þetta þegar þú ert að skrifa a for lykkju,
en tæknilega, þegar þú ert að takast á við þessar vísitölur
þú ættir nánast alltaf að takast á við óundirritaður heiltölur.
Ástæðan fyrir þessu er þegar þú ert að takast á við undirrituð heiltölur
þannig að ef þú ert með 2 undirritað heiltölur og þú bætir við þeim saman
og þeir á endanum of stór, þá endar með neikvæða tölu.
Svo það er það sem heiltala flæða er.
>> Ef ég bæta 2 milljörðum og 1 milljarður, enda ég upp með neikvæðum 1 milljarð.
Það er hvernig heiltölur vinna á tölvur.
Þannig að vandamálið með því að nota -
Það er allt í lagi nema lítið gerist að 2 milljarðar og allt verður að vera 1 milljarður,
þá er þetta að fara að vera neikvæð 1 milljarð og þá erum við að fara að deila því með 2
og endað með neikvæðum 500 milljónir.
Svo er þetta bara vandamál ef þú skyldir vera að leita í gegnum fylki
milljarða hluta.
En ef lítið + allt gerist að flæða, þá er það vandamál.
Um leið og við tökum þá óundirritaður, þá er 2 milljörðum plús 1 milljarð 3 milljarðar.
3 milljarðar deilt með 2 er 1,5 milljarðar króna.
Svo um leið og þeir eru án undirritunar, allt er fullkomið.
Og svo er það líka málið þegar þú ert að skrifa þína fyrir lykkjur,
og í raun er það sennilega það sjálfkrafa.
Það verður í raun bara að æpa á þig.
Þannig að ef þessi tala er of stór til að vera í bara heiltala en það myndi passa að óundirritaður heiltölu,
það mun æpa á þig, svo það er hvers vegna þú aldrei hlaupa inn í málið.
Þú getur séð að vísitala er aldrei að fara að vera neikvæð,
og svo þegar þú ert iterating yfir fjölda,
þú getur nánast alltaf sagt óundirritaður int i, en þú í raun ekki til.
Hlutirnir eru að fara að vinna ansi mikið eins og heilbrigður.
Allt í lagi. [Hvíslar] Hvað er klukkan?
Það síðasta sem ég vildi sýna - og ég verð bara að gera það mjög fljótur.
Þú veist hvernig við höfum skilgreint # svo við getum # define MAX sem 5 eða eitthvað?
Við skulum ekki Max. # Define bundinn eins og 200. Það er það sem við gerðum áður.
Það skilgreinir stöðug, sem er bara að fara að afrita og líma
hvar sem við gerast að skrifa bundinn.
>> Þannig að við getum í raun gert meira með # skilgreinir.
Við getum # skilgreina aðgerðir.
Þeir eru í raun ekki virka, en við munum kalla þá virka.
Dæmi væri eitthvað eins og Max (x, y) er skilgreind sem (x <Y y:? X). Allt í lagi.
Svo þú ættir að venjast ternary rekstraraðila setningafræði,
en er x minna en y? Return y, annars aftur x.
Svo þú sérð að þú getur gert þetta sér aðgerð,
og virka gæti verið eins bool MAX tekur 2 rök, skila þessu.
Þetta er einn af the sameiginlegur sjálfur sé ég gert svona. Við köllum þá Fjölvi.
Þetta er þjóðhagsleg.
Þetta er bara setningafræði fyrir það.
Þú getur skrifað Fjölvi til að gera hvað sem þú vilt.
Þú sérð oft Fjölvi fyrir kembiforrit printfs og efni.
Svo gerð printf eru sérstakar fastar í C ​​eins og undirstrik LINE undirstrika,
2 undirstrikar LINE undirstrika,
og það er líka að ég held 2 undirstrikar störf. Það gæti verið það. Eitthvað eins og þessi.
Þessir hlutir verða skipt út með nafni virka
eða númer línu sem þú ert á.
Oft, skrifa kembiforrit printfs sem hérna ég gæti þá bara skrifa
Kemba og það mun prenta línu númer og aðgerð sem ég gerst að vera í
að fundur þessi Debug yfirlýsingu.
Og þú getur líka prentað út annað.
Svo er einn hlutur sem þú ættir að horfa út fyrir ef ég gerst að # define DOUBLE_MAX
sem eitthvað eins og 2 * y og 2 * x.
Svo fyrir ástæðu hvað, gerast þú að gera það mikið.
Svo gera það þjóðhagsleg.
Þetta er í raun brotinn.
Ég myndi kalla það með því að gera eitthvað eins og DOUBLE_MAX (3, 6).
Svo hvað ætti að vera aftur?
[Nemandi] 12.
Já, ætti 12 að vera aftur, og 12 er skilað.
3 er skipt út fyrir X, fær 6 í stað fyrir y, og við aftur 2 * 6, sem er 12.
Nú hvað um það? Hvað ætti að vera aftur?
[Nemandi] 14. >> Helst 14.
Málið er að hvernig kjötkássa skilgreinir vinna, muna að það er bókstaflega afrita og líma
á nánast allt, svo það þetta er að fara að túlka sem
er 3 minna en 1 plús 6, 2 sinnum 1 plús 6, 2 sinnum 3.
>> Svo þess vegna er sett næstum alltaf allt í sviga.
Hvaða breyta er sett nánast alltaf í sviga.
Það eru tilvik þar sem þú þarft ekki að, eins og ég veit að ég þarf ekki að gera það hér
því minna en nánast alltaf bara að fara að vinna,
þó að það gæti ekki einu sinni að vera satt.
Ef það er eitthvað fáránlegt eins DOUBLE_MAX (1 == 2),
þá er að fara að fá stað með 3 minna en 1 er jafnt 2,
og svo þá það er að fara að gera 3 minna en 1, er að jafn 2,
sem er ekki það sem við viljum.
Svo í því skyni að koma í veg fyrir rekstraraðila forgang vandamál,
alltaf sett í sviga.
Allt í lagi. Og það er það, 5:30.
Ef þú hefur einhverjar spurningar um pset, láttu okkur vita.
Það ætti að vera gaman, og tölvusnápur útgáfa einnig er miklu raunsærri
en spjallþráð útgáfa af síðasta ári, þannig að við vonum að mikið af þú ert að reyna það.
Á síðasta ári var mjög yfirþyrmandi.
>> [CS50.TV]