[Powered by Google Translate] You ħadthom probabbilment jinstemgħu nies jitkellmu dwar l-algoritmu mgħaġġel u effiċjenti għall-eżekuzzjoni kompitu partikolari tiegħek, imma dak eżattament jfisser għal algoritmu li tkun rapida u effiċjenti? Ukoll, huwa ma jitkellem dwar kejl fil-ħin reali, bħal f'sekondi jew minuti. Dan huwa minħabba ħardwer tal-kompjuter u softwer jvarjaw b'mod drastiku. Programm My jista 'jmur aktar kajman minn tiegħek, għaliex jien running fuq kompjuter anzjani, jew minħabba I jiġri li tkun playing video game online fl-istess ħin, li huwa hogging l-memorja tiegħi, jew I jista 'tkun qed taħdem programm tiegħi permezz ta' software differenti li tikkomunika mas-magna differenti f'livell baxx. Huwa simili tqabbel it-tuffieħ u larinġ. Sempliċiment għax il-kompjuter bil-mod tiegħi jieħu aktar minn tiegħek biex tagħti lura tweġiba ma jfissirx li inti għandek l-algoritmu aktar effiċjenti. 

Allura, peress li ma nistgħux direttament jqabblu l-runtimes tal-programmi f'sekondi jew minuti, kif nistgħu iqabblu 2 algoritmi differenti irrispettivament mill-hardware tagħhom jew l-ambjent tas-softwer? Biex jinħoloq mod aktar uniformi ta 'kejl effiċjenza algorithmic, xjenzjati tal-kompjuter u matematiċi fasslu kunċetti għall-kejl tal-kumplessità asintotiku ta 'programm u notazzjoni imsejjaħ "Ohnotation Big" għad-deskrizzjoni dan. Id-definizzjoni formali hija li f funzjoni (x) timxi fuq l-ordni ta 'g (x) jekk jeżisti xi valur (x), x ₀ u xi kostanti, C, li għaliha f (x) huwa inqas minn jew ugwali għal li g ħinijiet kostanti (x) għal kulħadd x akbar minn x ₀. 

Imma ma jkun jibża bogħod mid-definizzjoni formali. Xi jfisser dan fil-fatt tfisser fil inqas f'termini teoretiċi? Ukoll, huwa bażikament mod ta 'analiżi kif fast runtime ta 'programm tikber asimptotikalment. Dan huwa, bħala l-daqs ta 'inputs tiegħek żidiet lejn infinità, jiġifieri, int issortjar firxa ta 'daqs 1000 meta mqabbla mal-firxa ta' daqs 10. Kif il-runtime tal-programm tiegħek jikbru? Per eżempju, immaġina għadd tan-numru ta 'karattri fil string-aktar sempliċi mod  bil-mixi permezz tal-sekwenza sħiħa ittra-by-ittra u żżid 1 sa kontro għal kull karattru. Dan algoritmu huwa qal li jimxu fil-ħin lineari fir-rigward tan-numru ta 'karattri, "N" fil-sekwenza. Fil-qosor, hija tmur fil O (n). Għaliex dan? Ukoll, bl-użu dan l-approċċ, il-ħin meħtieġ travers-sekwenza sħiħa huwa proporzjonali għan-numru ta 'karattri. Għadd tan-numru ta 'karattri fi string 20-karattri huwa ser jieħu darbtejn sakemm li tieħu li jgħoddu l-karattri fil string 10-karattru, għaliex inti għandek tfittex fil-karattri u kull karattru tieħu l-istess ammont ta 'żmien li nħarsu lejn. Kif inti żżid l-għadd ta 'karattri, l-runtime se jiżdied b'mod lineari mat-tul input. 

Issa, jimmaġina jekk inti tiddeċiedi dak iż-żmien lineari, O (n), biss ma kienx mgħaġġel biżżejjed għalik? Forsi int ħażna kordi enormi, u inti ma tistax taffordja l-ħin żejjed li se tieħu travers kollha ta 'karattri tagħhom jgħoddu wieħed mill-wieħed. Għalhekk, inti tiddeċiedi li tipprova xi ħaġa differenti. X'jiġri jekk inti jiġri li diġà jaħżen in-numru ta 'karattri fil-sekwenza, jiġifieri, fil-varjabbli imsejjaħ "len," kmieni fil-programm, qabel ma inti anki maħżuna l-karattru ħafna ewwel string tiegħek? Imbagħad, kull youd għandek tagħmel issa biex issir taf l-tul string, huwa jiċċekkjaw liema l-valur tal-varjabbli hi. Inti ma nħarsu lejn l-sekwenza nnifisha fil-livelli kollha, u aċċess għall-valur ta 'varjabbli bħal len hija kkunsidrata operazzjoni asimptotikalment Kostanti tal-ħin, jew O (1). Għaliex dan? Ukoll, ftakar dak kumplessità asintotiku mezzi. Kif il-bidla runtime id-daqs inputs tal tiegħek tikber? 

Tgħid li inti kienu qegħdin jippruvaw jiksbu l-għadd ta 'karattri fi string akbar. Ukoll, ma jimpurtax kemm hu kbir inti tagħmel l-sekwenza, anki miljuni karattri fit-tul, kull youd tagħmel biex isibu tul il-sekwenza ma 'dan l-approċċ, huwa li jaqra l-valur tal-len varjabbli, li inti diġà saru. It-tul input, jiġifieri, it-tul tas-sekwenza qed jippruvaw isibu, ma jaffettwax livelli kollha kif fast program tiegħek runs. Din il-parti tal-programm tiegħek imur ugwalment mgħaġġel fuq string one-karattru u string elf karattru, u hu għalhekk li dan il-programm ikun magħruf bħala running fil-ħin kostanti fir-rigward tad-daqs input. 

Naturalment, hemm żvantaġġ. Inti tqatta ispazju memorja extra fuq il-kompjuter tiegħek ħażna tal-varjabbli u l-ħin żejjed li tieħu inti li jagħmlu l-ħażna attwali tal-varjabbli, imma l-punt għadu stands, jiskopru kemm string tiegħek kienet ma jiddependix mit-tul tas-sekwenza fil-livelli kollha. Għalhekk, hija tmur fil O (1) jew il-ħin kostanti. Dan ċertament ma jfissirx li jkollhom dan il-kodiċi tiegħek runs fl-1 pass, iżda l-ebda kwistjoni kif ħafna passi li huwa, jekk dan ma jbiddilx id-daqs ta 'l-inputs, huwa għadu asimptotikalment kostanti li aħna jirrappreżentaw bħala O (1). 

Kif tista 'probabbilment raden, hemm diversi runtimes kbar ħafna O biex jitkejlu algoritmi ma. O (n) ² algoritmi huma asimptotikalment aktar kajman milli O (n) algoritmi. Dan huwa, bħala n-numru ta 'elementi (n) tikber, eventwalment O (n) ² algoritmi se tieħu aktar żmien minn O (n) algoritmi jiddekorri. Dan ma jfissirx O (n) algoritmi dejjem jimxu aktar mgħaġġel minn O (n) ² algoritmi, anke fl-istess ambjent, fuq l-istess ħardwer. Forsi għal daqsijiet input żgħar,  lO (n) ² algoriżmu jista 'attwalment taħdem aktar malajr, iżda, eventwalment, id-daqs input żidiet lejn infinità, il-O (n) runtime ² algoritmu ta eventwalment se eklissi l runtime tal-O (n) algoritmu. Eżatt bħal kull operazzjoni matematika kwadratiċi  eventwalment se jispiċċaw biex jaqbżu kwalunkwe funzjoni lineari, ebda kwistjoni kemm ta 'ras tibda l-funzjoni lineari jibda off ma. Jekk int taħdem ma 'ammonti kbar ta' data, algoritmi li jimxu fil O (n) ² żmien jista 'verament jispiċċaw lajma program tiegħek, iżda għal daqsijiet input żgħar, inti probabilment mhux se anki Avviż. 

Ieħor kumplessità asintotiku hija, ħin logaritmika, O (log n). Eżempju ta 'algoriżmu li timxi dan malajr huwa l-algoritmu klassika tfittxija binarja, għal konstatazzjoni ta 'element fil-lista diġà magħżula ta' elementi. 

Jekk ma tkunx taf liema tfittxija binarja ma, I ser jispjegaw dan għalik verament malajr. Ejja ngħidu li inti qed tfittex l-numru 3 f'dan firxa ta 'numri interi. Hija tħares lejn l-element nofs tal-firxa u jitlob, "Huwa l-element Irrid akbar minn, ugwali għal, jew inqas minn dan?" Jekk huwa ugwali, imbagħad kbira. Sibtha l-element, u qed isir. Jekk huwa akbar, allura inti taf l-element għandu jkun fil-lemin tal-firxa, u inti tista 'biss tħares lejn li fil-futur, u jekk huwa iżgħar, allura inti taf għandu jkun fil-linja xellugija. Dan il-proċess huwa imbagħad ripetut mal-firxa iżgħar daqs sakemm l-element korrett jinstab. 

Dan algoritmu qawwija qatgħat-daqs l-array fil nofs ma 'kull operazzjoni. Allura, biex isibu element fil-firxa magħżula ta 'daqs 8, l-aktar (log ₂ 8), jew 3 ta 'dawn l-operazzjonijiet, verifika tal-element tan-nofs, imbagħad qtugħ il-firxa fil nofs se jkunu meħtieġa, billi firxa ta 'daqs 16 jieħu (log ₂ 16), jew 4 operazzjonijiet. Dak biss 1 tħaddim aktar għal firxa irduppjat-daqs. Irduppjar-daqs tal-array iżid il-runtime billi biss 1 blokki ta 'dan il-kodiċi. Għal darb'oħra, l-iċċekkjar l-element nofs tal-lista, imbagħad qsim. Għalhekk, huwa qal li joperaw fil-ħin logaritmika, O (log n). Imma stenna, inti tgħidli, ma dan jiddependi fuq fejn fil-lista l-element li qed tfittex huwa? X'jiġri jekk l-ewwel element inti tħares lejn jiġri li jkun il-wieħed dritt? Imbagħad, hija tieħu biss 1-operazzjoni, ebda kwistjoni kemm hu kbir il-lista hija. 

Ukoll, hu għalhekk li x-xjenzjati tal-kompjuter għandhom termini aktar għall-kumplessità asintotika li jirriflettu l-aħjar każ u l-agħar każ prestazzjonijiet ta 'algoritmu. Aktar suppost, il-limiti ta 'fuq u t'isfel fuq il-runtime. Fil-każ aħjar għal tfittxija binarja, l-element tagħna huwa hemm dritt fin-nofs, u ġġibu fil-ħin kostanti, ebda kwistjoni kemm hu kbir il-bqija ta 'l-array huwa. Is-simbolu użat għal dan hija Ω. Għalhekk, dan algoritmu huwa qal li jimxu fil Ω (1). Fil-każ aħjar, isib l-element malajr, ebda kwistjoni kemm hu kbir il-firxa hija, iżda fl-agħar każ, għandu jwettaq (log n) il-kontrolli maqsuma tal-firxa biex isibu l-element dritt. Limiti agħar każ ta 'fuq huma msemmija bl-big "O" li inti diġà taf. Għalhekk, huwa O (log n), iżda Ω (1). 

A tfittxija lineari, b'kuntrast, fejn inti timxi permezz ta 'kull element tal-firxa biex isibu l-waħda tixtieq, huwa fl-aħjar Ω (1). Għal darb'oħra, l-ewwel element li trid. Għalhekk, ma jimpurtax kemm hu kbir il-firxa hija. Fl-agħar każ, huwa l-aħħar element fil-firxa. Allura, inti għandek timxi permezz elementi kollha n fil-firxa li jsibuha, bħal jekk inti kienu qed ifittxu għal 3. Għalhekk, hija tmur fil O (n) iż-żmien għaliex dan huwa proporzjonali għan-numru ta 'elementi fil-firxa. 

Wieħed simbolu aktar użata hija Θ. Dan jista 'jintuża biex jiddeskrivi algoritmi fejn l-każijiet aħjar u l-agħar huma l-istess. Dan huwa l-każ fil-algoritmi string-tul tkellimna dwar preċedenti. Dan huwa, jekk aħna jaħżnu varjabbli qabel aħna jaħżnu l-sekwenza u l-aċċess aktar tard fil-ħin kostanti. Ma jimpurtax f'liema numru aħna qed ħażna f'dik varjabbli, aħna ser ikollhom biex tħares lejn din. Il-każ l-aħjar huwa, inħarsu lejn din u ssib it-tul tas-sekwenza. Allura Ω (1) jew aħjar każ ħin kostanti. L-agħar każ hija, irridu nħarsu lejn din u ssib it-tul tas-sekwenza. Allura, O (1) jew il-ħin kostanti fil-agħar każ. Għalhekk, peress li l-każ l-aħjar u l-agħar każijiet huma l-istess, dan jista 'jingħad li jimxu fil Θ (1) iż-żmien. 

Fil-qosor, għandna modi tajba biex raġuni dwar l-effiċjenza kodiċijiet mingħajr ma jkunu jafu xejn dwar il-ħin tad-dinja reali li jieħdu biex jaħdmu, li huwa affettwat minn ħafna fatturi esterni, inkluż hardware differenti, software, jew l-ispeċifiċitajiet tal-kodiċi tiegħek. Ukoll, tippermetti magħna biex raġuni sew dwar dak li se jiġri meta d-daqs taż-żidiet inputs. 

Jekk int taħdem fl-O (n) ² algoritmu, jew agħar, O (2 ⁿ) algoritmu, wieħed mit-tipi li qed jikbru malajr, inti ser verament tibda l-avviż l-istaġnar meta tibda taħdem ma ammonti akbar ta 'data. 

Dak kumplessità asintotiku. Grazzi.