[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.