[Powered by Google Translate] Marahil narinig mo na ang mga tao na makipag-usap tungkol sa isang mabilis o mahusay na algorithm para sa pag-execute ng iyong partikular na gawain, ngunit kung ano eksakto ang ibig sabihin para sa isang algorithm upang maging mabilis o mahusay? Well, ito ay hindi pakikipag-usap tungkol sa isang pagsukat sa real time, tulad ng mga segundo o minuto. Ito ay dahil ang computer hardware at software ay nag-iiba lubhang. Aking programa ay maaaring magpatakbo ng mas mabagal kaysa sa iyo, dahil ako nagpapatakbo ito sa isang mas lumang computer na, o dahil mangyayari kong naglalaro ng isang laro sa online ng video sa parehong oras, na kung saan ay hoging lahat ng memory ang aking, o maaari kong tumatakbo ang aking programa sa pamamagitan ng ibang software na nakikipanayam sa ang machine naiiba sa isang mababang antas. Ito ay tulad ng paghahambing ng mga mansanas at dalandan. Dahil lang sa aking mas mabagal na computer na tumatagal na kaysa sa iyo upang bigyan ng sagot ay hindi nangangahulugan na mayroon kang mas mahusay na algorithm. 

Kaya, dahil hindi direktang namin maaaring ihambing ang mga ang mga runtimes ng mga programa sa mga segundo o minuto, kung paano namin ihambing ang 2 iba't ibang mga algorithm sa kabila ng kanilang hardware o software na kapaligiran? Upang lumikha ng isang mas unipormeng paraan ng pagsukat ng algorithmic kahusayan, computer na siyentipiko at mathematicians na gagawin konsepto para sa pagsukat ng asymptotic kumplikado ng isang programa at ang pagtatanda ng tinatawag na 'Big Ohnotation' para sa naglalarawan ito. Ang pormal na kahulugan ay na ang isang function f (x) tumatakbo sa ang pagkakasunod-sunod ng g (x) kung may umiiral ilang (x) halaga, x ₀ at ilang pare-pareho, C, kung saan f (x) ay mas mababa sa o katumbas ng na pare-pareho beses g (x) para sa lahat ng x mas malaki kaysa sa x ₀. 

Ngunit huwag madala ng pormal na kahulugan. Ano ang tunay na ibig sabihin sa mas panteorya mga tuntunin? Well, ito ay isa lamang paraan ng pag-aaral kung gaano kabilis ang runtime ng programa ay lumalaki asymptotically. Iyon ay, bilang ang laki ng iyong mga input ay nagdaragdag patungo sa infinity, halimbawa, ikaw ay pag-uuri-uri ng isang hanay ng mga laki 1000 kumpara sa isang hanay ng mga laki 10. Kung paano palaguin ang runtime ng iyong programa? Halimbawa, isipin ang pagbibilang sa bilang ng mga character sa isang string ang pinakasimpleng paraan  sa pamamagitan ng paglalakad sa pamamagitan ng ang buong string sulat-by-titik na at pagdadagdag ng 1 sa isang counter para sa bawat karakter. Algorithm na ito ay sinabi upang tumakbo sa linear oras may paggalang sa bilang ng mga character, 'N' sa string. Sa maikli, ito ay tumatakbo sa O (n). Bakit ito? Well, gamit ang diskarteng ito, oras kinakailangan pagbagtas buong string ay proporsyonal sa bilang ng mga character. Nagbibilang ang bilang ng mga character sa isang 20-character na string pagpunta sa dalawang beses hangga't ito ay tumatagal ng upang mabilang ang mga character sa isang 10-karakter na string, dahil mayroon kang upang tumingin sa lahat ang mga character at ang karakter bawat tumatagal sa parehong halaga ng oras upang tumingin sa. Bilang mong taasan ang bilang ng mga character, runtime ay taasan linearly sa input ang haba. 

Ngayon, isipin kung magpasya ka na linear oras, O (n), ay hindi mabilis sapat para sa iyo? Siguro ka sa pag-iimbak ng mga malaking string, at hindi mo kayang bayaran ang labis na oras na tumagal pagbagtas ang lahat ng kanilang mga character pagbibilang ng isa-by-isa. Kaya, nagpasya kang sumubok ng iba't ibang. Ano kung nais mong mangyari sa na-imbak ang bilang ng mga character sa string, sabihin, sa isang variable na tinatawag na 'Len,' sa maagang bahagi sa programa, bago ka kahit na naka-imbak sa unang character sa iyong string? Pagkatapos, ang lahat ng gusto mong gawin ngayon upang mahanap ang string haba, ay tingnan kung ano ang halaga ng variable ay. Hindi mo upang tingnan ang string na mismo sa lahat, at pag-access sa ang halaga ng isang variable tulad Len ay itinuturing oras na operasyon na isang asymptotically na pare-pareho, o O (1). Bakit ito? Well, tandaan kung ano ang ibig sabihin ng asymptotic kumplikado. Paano gumagana ang runtime pagbabago bilang ang laki ng iyong input ay lumalaki? 

Sabihin nating ikaw ay sinusubukan upang makuha ang bilang ng mga character sa isang mas malaking string. Well, hindi ito ay mahalaga kung gaano kalaki ang string, kahit isang milyong mga character ang haba, lahat na nais mong gawin upang mahanap ang haba ng string na ang diskarteng ito, upang basahin ang halaga ng variable Len, kung saan ikaw ay ginawa. Ang haba ng input, iyon ay, ang haba ng string na sinusubukan mong mahanap, ay hindi nakakaapekto sa lahat kung gaano kabilis ang iyong programa ay tumatakbo. Ito bahagi ng iyong programa ay tatakbo pantay mabilis sa isa-character na string at thousand-character na string, at iyon ang dahilan kung bakit ang programa ito ay tinutukoy bilang tumatakbo sa pare-pareho ang oras may paggalang sa laki ng input. 

Siyempre, ang isang sagabal. Gumastos ka ng dagdag na espasyo ng memorya sa iyong computer pag-imbak ng variable at ang labis na oras na tumagal upang gawin ang mga aktwal na imbakan ng variable, ngunit ang punto pa rin nakatayo, paghahanap ng kung gaano katagal ang iyong string ay ay hindi depende sa haba ng string sa lahat. Kaya, ito ay tumatakbo sa O (1) o pare-pareho ang oras. Ito ay tiyak na walang ibig sabihin na ang iyong code ay tumatakbo sa 1 hakbang, ngunit hindi mahalaga kung gaano karaming mga hakbang na ito ay, kung hindi ito baguhin ang laki ng input, pa rin asymptotically pare-pareho na kumakatawan namin bilang O (1). 

Bilang maaari mong marahil hulaan, maraming iba't ibang malaking O runtimes sukatin ang mga algorithm na may. O (n) ² algorithm asymptotically mas mabagal kaysa sa O (n) na mga algorithm. Iyon ay, bilang ang bilang ng mga elemento (n) ay lumalaki, kalaunan O (n) ² algorithm ay mas maraming oras sa O (n) na mga algorithm upang tumakbo. Hindi ito nangangahulugan O (n) na mga algorithm palaging patakbuhin ang mas mabilis sa O (n) ² algorithm, kahit na sa parehong kapaligiran, sa parehong hardware. Siguro para sa maliit na mga laki ng input,  ang O (n) ² algorithm ay maaaring aktwal na magtrabaho nang mas mabilis, ngunit, kalaunan, bilang ang laki ng input ay nagdaragdag patungo sa infinity, ang runtime O (n) ² algorithm ng ay malaon Eclipse ang runtime ng algorithm O (n). Tulad ng anumang parisukat mathematical function na  kalaunan maabutan anumang linear function na, hindi mahalaga kung magkano ng isang ulo simulan ang linear function na ay nagsisimula off na may. Kung ikaw ay gumagawa na may malaking halaga ng data, algorithm na tumakbo sa O (n) ² oras talagang magtapos alalay ng iyong programa, ngunit para sa maliit na mga laki ng input, malamang na hindi ka kahit mapansin. 

Isa pang asymptotic kumplikado ay, logarithmic oras, O (log n). Isang halimbawa ng isang algorithm na tumatakbo ito mabilis ay ang classic na algorithm ng paghahanap ng binary, para sa paghahanap ng isang elemento sa isang na-pinagsunod-sunod na listahan ng mga elemento. 

Kung hindi mo alam kung ano ang binary paghahanap, Ipapaliwanag ko ito para sa iyo talagang mabilis. Sabihin nating na iyong hinahanap para sa numero 3 sa hanay ng mga integer. Tinitingnan ang gitnang elemento ng array at nagtatanong, "Ang elemento Gusto kong mas malaki kaysa sa, katumbas ng, o mas mababa dito?" Kung ito ay katumbas, pagkatapos mahusay. Na iyong natagpuan ang sangkap, at tapos ka na. Kung ito ay mas malaki, at pagkatapos ay alam mo ang elemento ay sa kanang bahagi ng array, at maaari ka lamang tumingin sa na sa hinaharap, at kung ito ay mas maliit, pagkatapos ay alam mo ito sa kaliwang bahagi. Ang proseso na ito ay paulit-ulit na may mas maliit na-laki array hanggang sa tamang elemento ay natagpuan. 

Ang malakas na algorithm ay mapuputol ang laki ng array sa kalahati sa bawat operasyon. Kaya, upang mahanap ang isang elemento sa isang pinagsunod-sunod na hanay ng mga laki 8, hindi hihigit sa (log ₂ 8), o 3 sa mga pagpapatakbo, sa pagsusuri sa gitna elemento, na-cut ang array sa kalahati ay kailangan, kung saan ang isang hanay ng mga laki 16 tumatagal (log ₂ 16), o 4 pagpapatakbo. Na lamang 1 pang operasyon para sa Dinoble-laki array. Pagdodoble ang laki ng array pinatataas ang runtime pamamagitan lamang ng 1 tipak ng ang code na ito. Muli, check sa gitna elemento ng listahan, pagkatapos ay paghahati ng. Kaya, ito ay sinabi na nagpapatakbo sa logarithmic oras, O (log n). Ngunit maghintay, sabihin mo, ay hindi ito depende sa kung saan sa listahan ang sangkap na hinahanap mo ay? Paano kung ang unang elemento na tumingin ka sa mangyayari ang tamang? Pagkatapos, ito lamang ay tumatagal ng 1 pagpapatakbo, hindi mahalaga kung gaano kalaki ang listahan. 

Well, na kung bakit ang computer na siyentipiko ay may higit pang mga term para sa asymptotic kumplikado na sumasalamin sa pinakamahusay na-case at pinakamalala-case performance ng isang algorithm. Mas maayos, itaas at mas mababang mga hangganan sa runtime. Sa pinakamahusay na kaso para sa paghahanap ng binary, ang aming elemento ay doon sa gitna, at makakakuha ka ng ito sa pare-pareho ang oras, kahit gaano kalaki ang ibang bahagi ng array ay. Ang simbolo na ginamit para sa Ω. Kaya, ito algorithm ay sinabi upang tumakbo sa Ω (1). Sa ang pinakamahusay na kaso, nakakahanap ng mga elemento mabilis, hindi mahalaga kung gaano kalaki ang array, ngunit sa ang pinakamasama kaso, upang isagawa (log n) tseke split ng array upang mahanap ang karapatan na elemento. Pinakamahina-case itaas na hangganan ay tinutukoy na may malaking "O" na alam mo na. Kaya, O (log n), ngunit Ω (1). 

Isang linear paghahanap, sa pamamagitan ng kaibahan, kung saan ituturo sa iyo sa pamamagitan ng bawat elemento ng array upang mahanap ang isa na nais mong, sa pinakamahusay Ω (1). Muli, ang unang elemento gusto mo. Kaya, hindi mahalaga kung gaano kalaki ang array. Sa pinakamasama kaso, ang huling elemento sa array. Kaya, mayroon kang maglakad sa lahat n mga elemento sa array upang hanapin ito, bang kung ikaw ay naghahanap para sa isang 3. Kaya, tumatakbo sa O (n) oras dahil ito ay proporsyonal sa bilang ng mga elemento sa array. 

Isa pang simbolo na ginamit ay Θ. Na ito ay maaaring gamitin upang ilarawan ang mga algorithm kung saan ang pinakamahusay at pinakamasama kaso ay pareho. Ito ay ang kaso sa string-length na algorithm usapan natin ang tungkol mas maaga. Iyon ay, kung namin iimbak ito sa isang variable bago imbak ng namin ang string at ma-access ang mga ito sa ibang pagkakataon sa pare-pareho ang oras. Kahit na ano bilang namin ang pag-iimbak sa na variable, makikita namin upang tingnan ito. Ang pinakamahusay na kaso ay, tinitingnan namin dito at hanapin ang haba ng string. Kaya Ω (1) o pinakamahusay na kaso na pare-pareho ang oras. Ang pinakamasama kaso ay, tinitingnan namin ito at hanapin ang haba ng string. Kaya, O (1) o pare-pareho ang oras sa pinakamalala kaso. Kaya, dahil ang pinakamahusay na kaso at pinakamalala kaso ay pareho, ito ay maaaring sinabi upang tumakbo sa Θ (1) oras. 

Sa buod, mayroon kaming magandang paraan sa dahilan tungkol sa mga code ng kahusayan nang hindi alam ng anumang tungkol sa real-world na oras na tumagal sila upang tumakbo, na apektado ng maraming labas kadahilanan, kabilang ang magkakaibang hardware, software, o ang mga pagtutukoy ng iyong code. Gayundin, ito ay nagbibigay-daan sa amin upang dahilan na rin tungkol sa kung ano ang mangyayari kapag ang laki ng pagtaas ng input. 

Kung nagpapatakbo ka sa O (n) ² algorithm, o mas masahol pa, isang O (2 ⁿ) algorithm, isa sa pinakamabilis na lumalagong uri, mo ba talagang simulan upang mapansin ang paghina kapag nagsimula ka nagtatrabaho na may mas malaking halaga ng data. 

Na asymptotic kumplikado. Salamat.