[Powered by Google Translate] Ve pengine habari watu kuzungumza kuhusu algorithm kufunga au ufanisi kwa ajili ya utekelezaji kazi yako maalum, lakini nini hasa nini maana ya algorithm kuwa haraka au ufanisi? Naam, ni si kuzungumza juu ya kipimo katika muda halisi, kama sekunde au dakika. Hii ni kwa sababu vifaa vya kompyuta na programu kutofautiana kwa kasi. Mpango wangu ili kukimbia polepole kuliko yako, kwa sababu mimi nina mbio kwenye kompyuta wakubwa, au kwa sababu mimi kutokea kwa kuwa kucheza mchezo video online wakati huo huo, ambayo ni hogging yangu kumbukumbu zote, au nipate kuwa mbio mpango wangu kupitia programu mbalimbali ambayo mawasiliano na mashine tofauti katika ngazi ya chini. Ni kama kulinganisha apples na machungwa. Kwa sababu tu kompyuta yangu polepole inachukua muda mrefu kuliko yako kutoa nyuma jibu haina maana una algorithm ufanisi zaidi. 

Hivyo, tangu hatuwezi moja kwa moja kulinganisha runtimes ya mipango katika sekunde au dakika, jinsi gani sisi kulinganisha 2 algorithms tofauti bila kujali vifaa zao au mazingira software? Kwa kujenga njia zaidi ya sare ya kupima ufanisi algorithmic, kompyuta wanasayansi na wanahisabati wameazimia dhana kwa ajili ya kupima utata asymptotic wa mpango na nukuu iitwayo 'Big Ohnotation' kwa kuelezea hili. ufafanuzi rasmi ni kwamba kazi f (x) anaendesha juu ya utaratibu wa g (x) kama kuna baadhi ya thamani (x), x ₀ na baadhi ya mara kwa mara, C, ambayo f (x) ni chini ya au sawa na kwamba mara kwa mara mara g (x) kwa ajili ya wote x mkubwa kuliko x ₀. 

Lakini si kuwa na hofu mbali kwa ufafanuzi rasmi. Je, hii kwa kweli maana katika suala chini ya kinadharia? Naam, ni kimsingi njia ya kuchambua jinsi ya kufunga Runtime mpango wa kukua asymptotically. Hiyo ni, kama kawaida ya pembejeo yako huongezeka kuelekea infinity, kusema, wewe ni kuchagua safu ya ukubwa 1000 ikilinganishwa na safu ya kawaida 10. Jinsi gani Runtime ya programu yako kukua? Kwa mfano, fikiria kuhesabu idadi ya wahusika katika string njia rahisi  kutembea kupitia string nzima barua-na-barua na kuongeza 1 kwa counter kwa tabia ya kila. Algorithm Hii inasemekana kukimbia katika wakati linear kwa heshima na idadi ya wahusika, 'N' katika kamba. Kwa kifupi, ni anaendesha katika O (n). Kwa nini hii ni? Naam, kwa kutumia mbinu hii, muda unaotakiwa kwa traverse string nzima ni sawia na idadi ya wahusika. Kuhesabu idadi ya herufi katika string 20-tabia ni kwenda kuchukua mara mbili kama muda mrefu kama inachukua kuhesabu wahusika katika string 10-tabia, kwa sababu una kuangalia wahusika wote na tabia ya kila inachukua kiasi hicho cha muda wa kuangalia katika. Kama wewe kuongeza idadi ya wahusika, Runtime itaongeza linearly na urefu wa pembejeo. 

Sasa, hebu fikiria kama wewe kuamua kuwa wakati linear, O (n), tu si kwa kasi ya kutosha kwa ajili yenu? Labda wewe ni hifadhi ya masharti makubwa, na huwezi kununua muda wa ziada itachukua kwa traverse yote ya wahusika yao ya kuhesabu moja-na-moja. Hivyo, wewe kuamua kujaribu kitu tofauti. Nini kama kingetokea tayari kuhifadhi idadi ya herufi katika kamba, kusema, katika variable iitwayo 'len,' mapema katika mpango, kabla hata kuhifadhiwa tabia sana kwanza katika kamba yako? Kisha, wote wewe d kufanya sasa ili kujua urefu wa kamba, ni kuangalia nini thamani ya kutofautiana ni. Ungependa kuwa kuangalia string yenyewe wakati wote, na kupata thamani ya kutofautiana kama len ni kuchukuliwa asymptotically mara kwa mara wakati wa operesheni, au O (1). Kwa nini hii ni? Naam, kumbukeni yale utata asymptotic maana yake. Jinsi gani mabadiliko Runtime kama kawaida wa pembejeo yako kukua? 

Sema ungekuwa kujaribu kupata idadi ya herufi katika kamba kubwa. Naam, ingekuwa si jambo jinsi kubwa ya kufanya kamba, hata milioni wahusika muda mrefu, wote wewe d kufanya kupata urefu wa kamba pamoja na mfumo huu, ni kusoma nje thamani ya len variable, ambayo tayari alifanya. urefu wa pembejeo, kwamba ni, urefu wa kamba wewe ni kujaribu kupata, haiathiri wakati wote jinsi ya kufunga programu yako anaendesha. Hii sehemu ya mpango wako ingekuwa kukimbia sawa haraka juu ya kamba moja-tabia na kamba elfu-tabia, na kwamba ni kwa nini mpango huu itakuwa inajulikana kama mbio katika muda wa mara kwa mara kwa heshima na ukubwa wa pembejeo. 

Bila shaka, kuna drawback. Kutumia ziada kumbukumbu nafasi kwenye kompyuta yako hifadhi ya kutofautiana na muda wa ziada inachukua wewe kufanya hifadhi ya halisi ya kutofautiana, lakini uhakika bado anasimama, kutafuta namna ya muda mrefu string yako ilikuwa Haitegemei urefu wa kamba wakati wote. Hivyo, ni anaendesha katika O (1) au wakati mara kwa mara. Bila ya shaka hii haina maana kwamba code yako anaendesha katika hatua 1, lakini hakuna jambo jinsi hatua nyingi ni, ikiwa haina mabadiliko na ukubwa wa pembejeo, bado asymptotically mara kwa mara ambayo sisi kuwakilisha kama O (1). 

Kama unaweza pengine guess, kuna tofauti kubwa O runtimes kupima algorithms na. O (n) ² algorithms ni asymptotically polepole zaidi kuliko O algorithms (n). Hiyo ni, kama idadi ya vipengele (n) kukua, hatimaye O (n) ² algorithms itachukua muda zaidi kuliko O (n) algorithms kukimbia. Hii haina maana O (n) algorithms daima kukimbia kwa kasi kuliko O (n) ² algorithms, hata katika mazingira sawa, juu ya vifaa hivyo. Labda kwa wadogo pembejeo ukubwa,  O (n) ² algorithm ili kweli kazi kwa kasi, lakini hatimaye, kama kawaida huongeza pembejeo kuelekea infinity, O (n) ² algorithm ya Runtime hatimaye kupatwa Runtime ya algorithm O (n). Tu kama kazi yoyote ya hisabati quadratic  hatimaye iwafikie kazi yoyote linear, haijalishi ni kiasi gani ya kichwa kuanza kazi linear kuanza mbali na. Kama wewe ni kufanya kazi kwa kiasi kikubwa cha data, algorithms kwamba kukimbia katika O (n) ² wakati kweli unaweza kuishia kupunguza chini ya mpango wako, lakini kwa ajili ya wadogo pembejeo ukubwa, pengine hata taarifa. 

Mwingine ni utata asymptotic, logarithmic muda, O (logi n). mfano wa algorithm kwamba anaendesha hii haraka ni classic binary tafuta algorithm, kwa ajili ya kutafuta kipengele katika orodha tayari-sorted ya vipengele. 

Kama hawajui nini binary tafuta gani, Mimi itabidi kueleza ni kwa wewe kweli haraka. Hebu sema wewe ni kuangalia kwa namba 3 katika hii safu ya integers. Inaangalia kipengele katikati ya safu na anauliza, "Je, kipengele nataka zaidi kuliko, sawa na, au chini zaidi kuliko haya?" Kama ni sawa, basi kubwa. Wewe kupatikana kipengele, na wewe ni kosa. Kama ni kubwa, basi, unajua kipengele ina kuwa katika upande wa kulia wa safu, na unaweza tu kuangalia kwamba katika siku zijazo, na kama ni ndogo, basi, unajua ina kuwa katika upande wa kushoto. Utaratibu huu ni kisha alirudia na safu ndogo ya kawaida mpaka kipengele sahihi ni kupatikana. 

Hii algorithm nguvu kupunguzwa ukubwa safu katika nusu na operesheni ya kila. Hivyo, ili kupata kipengele katika safu ya ukubwa sorted 8, saa zaidi (kuingia ₂ 8), au 3 ya shughuli hizo, kuangalia kipengele katikati, kukata kisha safu katika nusu watatakiwa, ambapo safu ya ukubwa 16 inachukua (kuingia ₂ 16), au 4 shughuli. Hiyo tu 1 zaidi operesheni kwa safu mbili-size. Maradufu ukubwa wa safu huongeza Runtime na tu 1 chunk ya kanuni hii. Tena, kuangalia kipengele katikati ya orodha, basi splitting. Hivyo, ni alisema kufanya kazi katika muda logarithmic, O (logi n). Lakini kusubiri, unaweza kusema, haina hii wanategemea ambapo katika orodha ya kipengele wewe ni kuangalia kwa ni? Nini kama kipengele kwanza ukiangalia kinachotokea kwa kuwa moja ya haki? Kisha, tu inachukua 1 operesheni, hakuna jambo gani kubwa orodha ni. 

Naam, hiyo ndiyo sababu ya kompyuta wanasayansi suala zaidi kwa utata asymptotic ambayo kutafakari bora kesi na mbaya zaidi kesi maonyesho ya algorithm. Zaidi vizuri, mipaka ya juu na chini juu ya Runtime. Katika kesi bora kwa ajili ya kutafuta binary, kipengele yetu ni haki pale katikati, na wewe kupata katika muda mara kwa mara, hakuna jambo gani kubwa ya mapumziko ya safu ni. ishara kutumika kwa ajili ya hii ni Ω. Hivyo, algorithm hii ni alisema kukimbia katika Ω (1). Katika kesi bora, huikuta kipengele haraka, hakuna jambo gani kubwa safu ni, lakini katika hali mbaya, ina kufanya (logi n) hundi kupasuliwa wa safu wa kupata haki ya kipengele. Mipaka Mbaya-herufi ni inajulikana na kubwa "O" kwamba tayari kujua. Hivyo, ni O (logi n), lakini Ω (1). 

tafuta linear, kwa kulinganisha, ambayo wewe kutembea kwa njia ya kila kipengele cha safu kupata moja unataka, ni saa Ω bora (1). Tena, kipengele kwanza unataka. Hivyo, haijalishi jinsi kubwa ni safu. Katika kesi mbaya, ni kipengele mwisho katika safu. Hivyo, wewe kuwa na kutembea kwa njia ya mambo yote n katika safu ya kupata hiyo, kama kama walikuwa wanatafuta 3. Hivyo, ni anaendesha katika O muda (n) sababu ni sawia na idadi ya vipengele katika safu. 

Moja zaidi ishara kutumika ni Θ. Hii inaweza kutumika kuelezea algorithms ambapo kesi mzuri na mbaya zaidi ni sawa. Hii ni kesi katika algorithms string-urefu kuongelea mapema. Hiyo ni, kama sisi kuhifadhi katika variable kabla sisi kuhifadhi kamba na kupata hiyo baadaye katika wakati mara kwa mara. Hakuna jambo gani idadi sisi ni hifadhi katika variable kwamba, tutaweza kuwa na kuangalia saa yake. kesi bora ni, sisi kuangalia ni na kupata urefu wa kamba. Hivyo Ω (1) au bora-kesi ya mara kwa mara wakati. kesi mbaya zaidi ni, sisi kuangalia ni kupata na urefu wa kamba. Hivyo, O (1) au wakati mara kwa mara katika hali mbaya. Hivyo, tangu kesi bora na hali mbaya ni sawa, hii inaweza kuwa alisema kukimbia katika Θ wakati (1). 

Kwa muhtasari, tuna njia nzuri ya sababu kuhusu ufanisi codes bila kujua chochote kuhusu wakati halisi ya dunia wao kuchukua kukimbia, ambayo ni walioathirika na kura ya mambo ya nje, ikiwa ni pamoja na vifaa mbalimbali ya programu,, au specifics ya maadili yako. Pia, ni inaruhusu sisi kufikiri vyema kuhusu nini kitatokea wakati ukubwa wa ongezeko pembejeo. 

Kama wewe ni mbio katika algorithm O (n) ², au mbaya zaidi, O (2 ⁿ) algorithm, moja ya aina ya kukua haraka sana, utasikia kweli kuanza kwa taarifa kushuka wakati wa kuanza kufanya kazi na kiasi kubwa ya data. 

Hiyo asymptotic utata. Shukrani.