[Powered by Google Translate] Þú hefur sennilega heyrt fólk tala um hratt eða duglegur reiknirit
fyrir framkvæmd tiltekna verkefni þínu,
En hvað nákvæmlega þýðir það fyrir reiknirit til að vera fljótur eða duglegur?
Jæja, það er ekki að tala um mælingu í rauntíma,
eins og sekúndur eða mínútur.
Þetta er vegna þess að tölva vélbúnaður
og hugbúnaður mismunandi harkalegur.
Program minn gæti keyrt hægar en þitt,
vegna þess að ég er að keyra það á eldri tölvu,
eða vegna þess að ég koma að spila online vídeó leikur
á sama tíma, sem er svínslegur allt minni mitt,
eða ég gæti verið að keyra forritið mitt í gegnum mismunandi hugbúnaði
sem hefur samband við vélina öðruvísi á lágu stigi.
Það er eins og að bera saman epli og appelsínur.
Bara vegna þess að hægari tölvan mín tekur lengri
en ykkur að gefa til baka svar
þýðir ekki að þú hefur skilvirkari reiknirit.
>> Svo, þar sem við getum ekki beint bera runtimes af forritum
í sekúndum eða mínútum,
hvernig bera saman við 2 mismunandi reiknirit
óháð vélbúnaði eða hugbúnaði umhverfi?
Til að búa til fleiri samræmda leið til að mæla lausnarleiðar skilvirkni,
tölva vísindamenn og stærðfræðingar hafa hugsað
hugtök til að mæla asymptotic flókið forrit
og tákn sem kallast "Big Ohnotation '
til að lýsa þessu.
Formlega skilgreiningin er að fall f (x)
keyrir á röð g (x)
ef það er nokkur (x) gildi, x ₀ og
sumir stöðug, C, sem
f (x) er minna en eða jafnt og
að fasti sinnum g (x)
fyrir öll x meiri en x ₀.
>> En ekki vera hrædd í burtu með formlega skilgreiningu.
Hvað þýðir þetta í raun í minni fræðilegum skilmála?
Jæja, það er í grundvallaratriðum leið til að greina
hversu hratt afturkreistingur forrit vex aðfellu.
Það er, eins og stærð aðföngum þinn eykst til óendanleika,
segja, þú ert að flokka fjölda stærð 1000 samanborið við fjölda stærð 10.
Hvernig virkar afturkreistingur af forritinu vaxa?
Til dæmis ímynda sér að telja fjölda stafa
í streng einfaldasta leiðin
með því að ganga í gegnum allt band
bréf-við-bréf og bæta 1 við teljarann ​​fyrir hvern staf.
Þetta reiknirit er sagt að keyra í línulegum tíma
með tilliti til fjölda þeirra stafa,
'N' í streng.
Í stuttu máli, keyrir það á O (n).
Hvers vegna er þetta?
Jæja, með því að nota þessa aðferð, tíma þarf
að fara yfir allt band
er í réttu hlutfalli við fjölda þeirra stafa.
Telja fjölda stafa í 20-stafa streng
er að fara að taka tvisvar svo lengi sem það tekur
til að telja stafi í 10-stafa streng,
vegna þess að þú þarft að líta á alla stafi
og hver persóna tekur sama magn af tíma til að líta á.
Eins og þú auka fjölda þeirra stafa,
afturkreistingur eykst línulega með inntak lengd.
>> Nú ímynda sér ef þú ákveður að línulegum tíma,
O (n), var bara ekki nógu hratt fyrir þig?
Kannski þú ert að geyma mikla strengi,
og þú getur ekki efni á auka tíma það myndi taka
að fara yfir allar persónur þeirra telja einn-við-mann.
Svo þú ákveður að prófa eitthvað nýtt.
Hvað ef þú myndir koma þegar geyma fjölda stafa
á band, segja, í breytu sem heitir "Len, '
snemma á í áætluninni,
áður en þú settir jafnvel mjög fyrsta staf í streng þinn?
Þá, allt sem þú vilt þurfa að gera núna til að finna út the band lengd,
er að athuga hvað gildi breytunnar er.
Þú vilt ekki að líta á band sig á öllu,
og aðgang að gildi breytu eins og Len er talið
að aðfellu stöðug skipti aðgerð,
eða O (1).
Hvers vegna er þetta? Jæja, muna hvað asymptotic flókið þýðir.
Hvernig virkar afturkreistingur breyting sem stærð
inntak þitt vex?
>> Segjum að þú varst að reyna að fá fjölda stafa í stærri band.
Jæja, myndi það ekki máli hversu stór þú gera band,
jafnvel milljón stafir að lengd,
allt sem þú vilt þurfa að gera er að finna lengd strengur er með þessari aðferð,
er að lesa út gildi breytu Len,
sem þú gerðir þegar.
Inntak lengd, sem er lengd strengsins sem þú ert að reyna að finna,
hefur ekki áhrif á öll hversu hratt program keyrir.
Þessi hluti program myndi hlaupa jafn hratt á einn staf band
og þúsund-eðli band,
og það er hvers vegna þetta forrit væri vísað til eins og að keyra á stöðugum tíma
varðar inntak stærð.
>> Auðvitað, það er galli.
Þú eyðir auka minni í tölvunni þinni
geyma breytu
og auka tíma sem það tekur
að gera í raun geymsla breytu,
en punkturinn stendur enn,
finna út hversu lengi strengurinn þinn var
ekki treysta á lengd strengsins yfirleitt.
Svo keyrir það á O (1) eða stöðugum tíma.
Þetta vissulega er ekki að meina
að kóðinn keyrir í 1 skrefi,
en það er sama hversu mörg skref það er,
Ef það breytist ekki með stærð á aðföngum,
það er samt aðfellu fasti sem við tákna sem O (1).
>> Eins og þú geta sennilega giska,
það eru margar mismunandi stór O runtimes að mæla reiknirit með.
O (n) ² reiknirit eru aðfellu hægari en O (n) reiknirit.
Það er, eins og fjölda staka (N) vex,
loksins O (n) ² reiknirit mun taka lengri tíma
en O (n) reiknirit til að keyra.
Þetta þýðir ekki O (n) reiknirit alltaf hlaupa hraðar
en O (n) ² reiknirit, jafnvel í sama umhverfi,
á sama vélbúnaði.
Kannski fyrir litlum stærðum inntak,
O (n) ² reiknirit gæti raunverulega vinna hraðar,
En að lokum, eins og inntak stærð eykst
að óendanlegu er O (n) ² Reiknirit á afturkreistingur
mun að lokum myrkvi afturkreistingur á O (n) reiknirit.
Rétt eins og allir stigs stærðfræðilega aðgerð
mun að lokum ná öllum línulegt fall,
sama hversu mikið forskot á línulegt fall byrjar með.
Ef þú ert að vinna með miklu magni af gögnum,
reiknirit sem keyra á O (n) ² tími getur raunverulega endað hægja niður program,
en litlum stærðum inntak,
þú verður að öllum líkindum ekki einu sinni eftir.
>> Annar asymptotic flókið er,
lógaritmískum tíma, O (log n).
Dæmi um reiknirit sem keyrir þetta fljótt
er klassískt tvöfaldur leit reiknirit,
að finna stak í þegar-raðaða lista af þáttum.
>> Ef þú veist ekki hvað tvöfaldur leit hefur,
Ég skal útskýra það fyrir þér mjög fljótt.
Segjum að þú ert að leita að númer 3
í þessum fjölda heiltalna.
Það lítur á miðju þáttur í fylkinu
og spyr, "Er þáttur sem ég vil meira en, jafnt eða minna en þetta?"
Ef það er jafnt, þá frábært. Þú fannst þáttur, og þú ert búinn.
Ef það er meiri, þá þú veist þáttur
þarf að vera í hægra megin í fylkinu,
og þú getur aðeins að líta á það í framtíðinni,
og ef það er minna, þá þú veist það er að vera í vinstri hlið.
Þetta ferli er síðan endurtekið með minni-stærð fylkisins
þar til rétt frumefni er að finna.
>> Þetta öflugur reiknirit sker array stærð í helming með hverri aðgerð.
Svo, til að finna stak í raðaða fjölbreytta stærð 8,
í mesta lagi (log ₂ 8),
eða 3 af þessum aðgerðum,
stöðva miðju frumefni, þá skera í array í tvennt verður krafist,
en fylki af stærð 16 fer (log ₂ 16),
eða 4 aðgerðir.
Það er bara 1 fleiri rekstur fyrir tvöfaldast-stærð fylkisins.
Tvöföldun á stærð fylkisins
eykur afturkreistingur aðeins 1 klumpur af þessum kóða.
Aftur, að haka við miðju þáttur í listanum, þá skipta.
Svo er sagt, að starfa í lógaritmískum tíma,
O (log n).
En bíddu, þú segir,
er þetta ekki háð því hvar á listanum þátturinn sem þú ert að leita að er?
Hvað ef fyrsta þáttur sem þú horfir á verður að vera réttur?
Þá tekur það aðeins 1 aðgerð,
sama hversu stór listinn er.
>> Jæja, það er hvers vegna tölva vísindamenn hafa fleiri orð
fyrir asymptotic flókið sem endurspegla bestu-málið
og versta sýningar um reiknirit.
Fleiri almennilega, efri og neðri mörk
á afturkreistingur.
Í besta tilfelli fyrir leit tvöfaldur, þáttur okkar er
rétt þar í miðju,
og þú færð það í föstu tíma,
sama hversu stór restin af fylki.
Táknið er notað fyrir þetta er Ω.
Svo, þetta reiknirit er sagt að hlaupa í Ω (1).
Í besta falli, finnur það hluti fljótt,
sama hversu stór fylki er,
en í versta tilfelli,
það hefur til að framkvæma (log n) Split eftirlit
í fylki til að finna rétta hluti.
Versta efri mörk eru nefnd með stóru "O" sem þú veist nú þegar.
Svo er það O (log n), en Ω (1).
>> A línuleg leita hins,
þar sem þú gengur í gegnum hvert frumefni í fylkinu
til að finna það sem þú vilt,
er í besta Ω (1).
Again, the fyrstur þáttur sem þú vilt.
Svo það skiptir ekki máli hversu stór fylki er.
Í versta tilfelli, það síðasta þáttur í fylki.
Svo, þú ert að ganga í gegnum allar n þætti í fylki til að finna það,
eins og ef þú varst að leita að 3.
Svo keyrir það á O (n) tíma
því það er í réttu hlutfalli við fjölda staka í fylki.
>> Einn fleiri tákn sem notuð er Θ.
Þetta má nota til að lýsa reiknirit þar sem bestu og verstu tilfellum
eru þau sömu.
Þetta er raunin í band lengd reiknirit við ræddum um áðan.
Það er, ef við geyma það í breytu fyrir
geymum strenginn og opna það seinna í stöðugri tíma.
Sama hvaða tala
við erum að geyma í því breyta, verðum við að líta á það.
Besta tilfelli er, horfum við á það
og finna lengd strengsins.
Svo Ω (1) eða best ef stöðug skipti.
Versta tilfelli er
við lítum á það og finna lengd strengsins.
Svo, O (1) eða stöðugum tíma í versta tilfelli.
Svo er þar sem besta tilfelli og verstu tilvikum sama,
það er hægt að segja að keyra í Θ (1) tíma.
>> Í stuttu máli, höfum við góðar leiðir til að ástæðu um númerum skilvirkni
án þess að vita neitt um alvöru-heiminum þegar þeir taka til að hlaupa,
sem hefur áhrif á fullt af utanaðkomandi þáttum,
meðal mismunar vélbúnaður, hugbúnaður,
eða sérkenni kóðann þinn.
Einnig gerir það okkur að ástæðu vel um hvað mun gerast
þegar stærð inntak eykst.
>> Ef þú ert að keyra í O (n) ² reiknirit,
eða verr, a O (2 ⁿ) reiknirit,
einn af the festa vaxa tegundir,
þú munt í raun að byrja að taka eftir hægagangur
þegar þú byrjar að vinna með stærri magni af gögnum.
>> Það er asymptotic flókið. Takk.