[Powered by Google Translate] Ou te pwobableman tande moun pale sou yon algorithm vit oswa efikas pou egzekite travay an patikilye ou a, men ki sa egzakteman sa vle di pou yon algorithm yo dwe vit oswa efikas? Oke, li pa pale osijè de yon mezi nan tan reyèl, tankou segonn oubyen minit. Sa a se paske kenkayri òdinatè ak lojisyèl varye byen wo. Pwogram m 'lan ka kouri pi dousman pase pou ou, paske mwen m 'kouri l' sou yon òdinatè ki pi gran, oswa paske mwen rive yo dwe jwe yon jwèt videyo sou entènèt an menm tan an, ki se hogging tout memwa m 'yo, oswa mwen ta ka ap kouri pwogram mwen an nan lojisyèl diferan ki kominike avèk machin nan yon fason diferan nan yon nivo ki ba. Se tankou konpare pòm ak zoranj. Jis paske òdinatè pi dousman mwen li pran plis pase ou bay tounen yon repons sa pa vle di ou gen algorithm nan pi efikas. 

Se konsa, depi nou pa ka konpare dirèkteman runtimes yo pou pwogram nan segonn oubyen minit, ki jan nou konpare 2 algoritm diferan kèlkeswa nan kenkayri yo oswa anviwònman lojisyèl? Pou kreye yon fason plis inifòm nan mezire algoritmik efikas, syantis konpitè ak matematisyèn te envante konsèp pou mezire konpleksite a asenptotik nan yon pwogram ak yon notasyon rele 'Big Ohnotation' pou dekri sa a. Definisyon nan fòmèl se ke yon fonksyon f (x) kouri sou lòd la g (x) si gen egziste kèk valè (x), x ₀ ak kèk konstan, C, pou ki f (x) se mwens pase oswa egal a ki konstan fwa g (x) pou tout x pi gran pase x ₀. 

Men, pa dwe pè ale nan definisyon fòmèl la. Ki sa ki sa sa a aktyèlman vle di nan mwens tèm teyorik? Oke, bazikman yon fason pou analize konbyen vit ègzekutabl yon pwogram nan ap grandi asenptotik. Sa se, kòm gwosè a nan entrain ou ogmante nan direksyon pou debordeman, di, w ap Fouye yon etalaj de gwosè 1000 konpare ak yon etalaj de gwosè 10. Ki jan ègzekutabl a nan pwogram ou an grandi? Pou egzanp, imajine konte kantite karaktè nan yon fisèl wout la pi senp  pa mache nan fil la tout antye lèt-pa-lèt ak ajoute 1 nan yon kontwa pou chak karaktè. Sa a se algorithm di kouri nan tan lineyè ki gen rapò ak ki kantite karaktè, 'N' nan fil la. Nan ti bout tan, li kouri nan O (n). Poukisa se sa a? Oke, lè l sèvi avèk apwòch sa a, tan yo mande Traverse fisèl la tout antye se pwopòsyonèl ak kantite karaktè. Konte kantite karaktè nan yon fisèl 20-karaktè a pral pran de fwa osi lontan ke li pran ka konte karaktè yo nan yon fisèl 10-karaktè, paske ou gen fè yon gade nan tout karaktè yo ak chak karaktè pran menm kantite lajan an nan tan fè yon gade nan. Kòm ou ogmante kantite karaktè, ègzekutabl an ap ogmante linear ak longè a D '. 

Koulye a, imajine si ou deside lè sa a lineyè, O (n), jis pa t 'vit ase pou ou? Petèt w ap estoke strings gwo, epi ou pa kapab peye tan siplemantè a li ta pran Traverse tout nan karaktè yo konte yon sèl-pa-youn. Se konsa, ou deside eseye yon bagay diferan. Ki sa ki si ou ta rive deja estoke ki kantite karaktè nan fisèl la, di, nan yon varyab rele 'Len,' byen bonè nan nan pwogram nan, anvan ou menm ki estoke pèsonaj la trè premye nan fil ou a? Lè sa a, tout sa ou ta dwe fè kounye a yo chèche konnen longè a fisèl, se tcheke sa ki valè a nan varyab la se. Ou pa ta gen fè yon gade nan fisèl la li menm nan tout, ak gen aksè nan valè a nan yon varyab tankou Len ki konsidere kòm yon operasyon tan asenptotik konstan, oswa O (1). Poukisa se sa a? Oke, sonje sa konpleksite asenptotik vle di. Kijan chanjman nan ègzekutabl kòm gwosè a entrées nan ou a ap grandi? 

Di ou te ap eseye jwenn nimewo a nan karaktè nan yon fisèl pi gran. Oke, li pa ta gen pwoblèm ki jan gwo ou fè fisèl la, menm yon milyon dola karaktè long, tout sa ou ta gen pou fè pou jwenn longè fil la ak apwòch sa a, a se fè lekti soti valè a nan Len a varyab, ki ou deja fè fè yo. D 'longè a, se sa ki, longè a nan fisèl la w ap eseye jwenn, pa afekte nan tout kouman vit pwogram ou an ap kouri. Pati sa a nan pwogram ou an ta kouri egalman vit sou yon fisèl yon sèl-karaktè ak yon fisèl mil-karaktè, ak sa a, se poukisa ta pwogram sa a dwe refere yo kòm kouri nan tan konstan ki gen rapò ak gwosè a D '. 

Natirèlman, gen yon dezavantaj. Ou depanse plis espas memwa sou òdinatè ou estoke varyab la ak tan siplemantè a li pran ou fè depo aktyèl la nan varyab la, men pwen an toujou rete, jwenn deyò konbyen tan fisèl ou te pa depann de longè nan fisèl la nan tout. Se konsa, li kouri nan O (1) oswa tan konstan. Sa a sètènman pa gen vle di ki kòd ou a kouri nan 1 etap, men pa gen pwoblèm ki jan anpil etap li ye, si li pa chanje avèk gwosè a nan entrain yo, li la toujou asenptotik konstan ki nou reprezante kòm O (1). 

Kòm ou ka pwobableman devine, genyen anpil moun ki diferan gwo runtimes O ki mezire algoritm avèk yo. O (n) ² algoritm yo se asenptotik pi dousman pase O algoritm (n). Sa se, kòm nimewo a nan eleman (n) ap grandi, evantyèlman O (n) ² algoritm ap pran plis tan pase O (n) algoritm nan kouri. Sa pa vle di O (n) algoritm toujou kouri pi vit pase O (n) algoritm ², menm nan anviwònman an menm, nan kenkayri a menm. Petèt pou gwosè D 'piti,  O an (n) ² algorithm ta ka aktyèlman ap travay pi vit, men, evantyèlman, menm jan gwosè a D 'ogmante nan direksyon pou debordeman, O (n) ègzekutabl la ² algorithm nan pral evantyèlman eklips ègzekutabl a nan algorithm nan O (n). Jis tankou nenpòt ki fonksyon kwadratik matematik  pral evantyèlman rapouswiv nenpòt fonksyon lineyè, pa gen pwoblèm konbyen nan yon tèt kòmanse fonksyon an lineyè kòmanse koupe ak. Si w ap travay ak gwo kantite done, algoritm ki kouri nan O (n) ² tan ka vrèman fini ralanti desann pwogram ou an, men pou gwosè D 'piti, pwobableman ou pa pral menm remake. 

Yon lòt konpleksite asenptotik se, logaritmik tan, O (boutèy demi lit n). Yon egzanp yon algorithm ki kouri sa a byen vit se binè algorithm la klasik rechèch, pou jwenn yon eleman nan yon lis deja-Ranje nan eleman. 

Si ou pa konnen ki sa ki rechèch binè fè, Mwen pral eksplike li pou ou reyèlman byen vit. Se pou nou di w ap chèche pou yon nimewo pou la 3 nan sa a seri nonm antye relatif. Li sanble nan eleman nan mitan nan etalaj la epi mande, "se eleman ki mwen vle pi gran pase, egal a, oswa mwens pase sa a?" Si li la egal, Lè sa a, gwo. Ou te jwenn eleman a, epi w ap fè. Si li nan pi gwo a, Lè sa a, ou konnen eleman nan gen yo dwe nan bò dwat la etalaj la, epi ou ka sèlman gade nan ki nan tan kap vini an, epi si li nan pi piti, Lè sa a, ou konnen li te gen nan bò gòch la. Pwosesis sa a Lè sa a, repete ak etalaj ki pi piti a-gwosè jiskaske yo eleman ki kòrèk la jwenn. 

Sa a algorithm pwisan koupe gwosè a etalaj nan mwatye ak chak operasyon. Se konsa, jwenn yon eleman nan yon etalaj Ranje nan gwosè 8, nan pifò (ouvri sesyon ₂ 8), oswa 3 nan operasyon sa yo, tcheke eleman nan mitan, lè sa a koupe etalaj la nan mwatye yo pral mande, Lè nou konsidere ke yon etalaj de gwosè 16 pran (ouvri sesyon ₂ 16), oswa 4 operasyon yo. Sa a se sèlman 1 operasyon plis pou yon etalaj double-gwosè. Double pwensip gwosè a nan etalaj la ogmante ègzekutabl a pa sèlman 1 ti moso nan sa a kòd. Yon fwa ankò, tcheke eleman nan mitan nan lis la, Lè sa a, divize. Se konsa, li di l opere nan tan logaritmik, O (boutèy demi lit n). Men, tann, ou di, pa sa a depann sou kote nan lis la eleman nan w ap chèche pou se? E si eleman nan premye ou gade nan k ap pase yo dwe youn nan dwa? Lè sa a,, li sèlman pran 1 operasyon, pa gen pwoblèm ki jan gwo lis la se. 

Oke, sa a, se poukisa syantis òdinatè gen plis tèm pou asenptotik konpleksite ki reflete pi byen ki ka a ak pi move-ka pèfòmans nan yon algorithm. Plis byen, anwo ak pi ba limit yo sou ègzekutabl la. Nan ka a pi bon pou rechèch binè, eleman nou an, se dwa gen nan mitan an, epi ou jwenn li nan tan konstan, pa gen pwoblèm ki jan gwo rès la nan etalaj la se. Senbòl yo itilize pou sa a se Ω. Se konsa, sa a algorithm te di se kouri nan Ω (1). Nan ka ki pi bon, li jwenn eleman ki byen vit, pa gen pwoblèm ki jan gwo etalaj la se, men nan ka ki pi mal la, li gen fè (boutèy demi lit n) chèk separe nan etalaj la jwenn eleman ki dwat. Pi move-ka anwo avèk limit yo refere yo bay ak gwo "O la" ke ou deja konnen. Se konsa, li O (boutèy demi lit n), men Ω (1). 

Yon rechèch lineyè, pa kontra, nan kote ou mache nan chak eleman nan etalaj la jwenn youn nan ou vle, se nan pi bon Ω (1). Yon fwa ankò, eleman nan premye ou vle. Se konsa, li pa gen pwoblèm ki jan gwo etalaj la se. Nan ka ki pi mal la, li nan eleman an dènye nan etalaj la. Se konsa, ou gen mache nan tout eleman n nan etalaj la jwenn li, renmen si w te gen ap chèche pou yon 3. Se konsa, li kouri nan tan O (n) paske li nan pwopòsyonèl ak kantite eleman nan etalaj la. 

Youn nan senbòl plis itilize se Θ. Sa a ka sèvi ak dekri algoritm kote pi byen ak pi move ka yo se menm bagay la. Sa a se ka a nan algoritm yo fisèl-longè nou te pale de pi bonè. Sa se, si nou mete yo nan yon varyab anvan nou sere fisèl la ak jwenn aksè nan li pita nan konstan tan. Pa gen pwoblèm sa nimewo nou ap estoke nan varyab sa a, nou pral oblije gade nan li. Ka a se pi bon, nou gade nan li ak jwenn longè fil la. Se konsa, Ω (1) oswa pi bon-ka tan konstan. Ka ki pi mal la se, nou gade nan li epi li jwenn longè fil la. Se konsa, O (1) oswa konstan tan nan pi move ka. Se konsa, depi ka a pi byen ak pi move ka yo se menm bagay la, sa a kapab di nan kouri nan tan Θ (1). 

An rezime, nou gen bon fason di rezon sou efikasite kòd san yo pa konnen anyen sou tan an nan lavi reyèl yo pran kouri, ki se afekte pa anpil nan faktè deyò a, ki gen ladan diferan kenkayri, lojisyèl, oswa kòman sa ap kòd ou a. Epitou, li pèmèt nou fè lojik byen sou sa ki pral rive lè gwosè a nan ogmantasyon yo entrain. 

Si w ap kouri nan O (n) algorithm ², oswa pi mal, yon O (2 ⁿ) algorithm, yonn nan plus ki kalite k ap grandi, ou pral reyèlman kòmanse avi ralentissement la lè ou kòmanse ap travay ak pi gwo kantite done. 

Sa a konpleksite asenptotik. Mèsi.