[Powered by Google Translate] Sa oled ilmselt kuulnud inimesed räägivad kiiresti või tõhus algoritm teostamiseks oma konkreetne ülesanne, Aga mida täpselt tähendab see algoritm peab olema kiire või tõhus? Noh, see ei räägi mõõtmine reaalajas nagu sekundites või minutites. Seda seetõttu, et arvuti riistvara ja tarkvara väga oluliselt erineda. Minu programm võib käivitada aeglasem kui sinu oma, sest ma olen töötab see vanem arvuti, või sellepärast, et ma juhtumisi mängib online videomäng samal ajal, mis on hogging kõik mu mälu, või ma võib olla töötab minu programm läbi erinevate tarkvara mis suhtleb masin erinevalt madalal tasemel. See on nagu võrrelda õunu ja apelsine. Lihtsalt, sest minu aeglasem arvuti võtab kauem kui sinu oma tagasi anda vastus ei tähenda, teil on tõhusam algoritm. 

Niisiis, kuna me ei saa otseselt võrrelda runtimes programmide sekundites või minutites, Kuidas me võrrelda 2 erinevat algoritmid sõltumata nende riistvara või tarkvara keskkonnas? Et luua ühtne viis mõõta algoritmilise tõhususe, arvuti teadlased ja matemaatikud on välja töötatud mõisted mõõtmiseks asümptootilisest keerukus programmi ja märge "suure Ohnotation" kirjeldamiseks seda. Formaalne definitsioon on, et funktsioon f (x) töötab järjekorras g (x) kui on olemas mõned (x) väärtus, x ₀ ja mingite konstantide, c, mille f (x) on väiksem või võrdne et pidev korda g (x) iga x suurem kui x ₀. 

Aga ei karda kaugusel ametlik definitsioon. Mida see tegelikult tähendab vähem teoreetiline mõttes? Noh, see on põhimõtteliselt nii, et analüüsida kui kiiresti programmi Runtime kasvab asümptootiliselt. See tähendab, et kui suurust oma sisendid suurendab suunas lõpmatus, Ütle, et sa sorteerimine massiivi suurus 1000 võrreldes massiivi suurus 10. Kuidas Runtime oma programmi kasvama? Oletagem näiteks, loendades tähemärki aastal string lihtsaim viis  jalgsi läbi terve rea täht-täht ja lisades 1 kuni loendur iga märk. See algoritm on öelnud, et sõidetud lineaarne aeg seoses märkide arvu, "N" string. Ühesõnaga, see jookseb O (n). Miks see nii on? Noh, kes seda meetodit kasutavad, vajalik aeg läbida kogu string on võrdeline arvu märke. Counting märkide arvu 20-märgijada see aega võtab kaks korda nii kaua kui vaja lugema märkide 10-märgijada, sest sa pead vaatama kõik märgid ja iga märk võtab sama palju aega vaadata. Nagu te suurendada arvu märke, Runtime kasvab lineaarselt sisend pikkus. 

Nüüd kujutage ette, kui sa otsustad, et lineaarne aeg, O (n), lihtsalt ei olnud piisavalt kiire Teie jaoks? Võib-olla olete ladustamiseks tohutu stringid, ja sa ei saa endale rohkem aega, mis kulub läbida kõik oma omadustelt lugedes ühe poolt-üks. Niisiis, sa otsustad proovida midagi muud. Mis siis, kui juhtuks juba salvestada mitu sümbolit aastal string, ütleme, muutuja nimega "len" varakult programmi enne kui isegi salvestatud kõige esimene märk teie string? Siis kõik soovid on teha nüüd välja selgitada stringi pikkus, on vaadata, mida muutuja väärtus on. Sa ei pea vaatama string ise üldse, ja pääseda väärtus muutuja nagu len peetakse asümptootiliselt pidevalt aega operatsiooni või O (1). Miks see nii on? Noh, mäletad, mida asümptootilisest keerukus tähendab. Kuidas Runtime muutunud suurus oma sisendid kasvab? 

Ütle, et sa üritad saada tähemärkide arv suurem stringi. Noh, see pole oluline, kui suur teete stringi, isegi miljoni tähemärki pikk, kõik soovid on teha, et leida jada pikkusest selline lähenemine, on lugeda läbi muutuja len, mis sa juba teinud. Sisend pikkus, see, stringi pikkusena te üritate leida, ei mõjuta üldse, kui kiiresti teie programm töötab. See osa teie programmi läheks sama kiiresti edasi ühe märgijada ja tuhande märgijada, ja sellepärast see programm oleks edaspidi töötab pidevalt aega suhtes sisend suurus. 

Muidugi, seal on puudus. Sa veedad pildi mälu arvutis ladustamiseks muutuja ja lisaaeg kulub teil teha tegelikku salvestusmahtu muutuja, kuid küsimus on endiselt jõus, teada saada, kui kaua teie string oli ei sõltu stringi pikkusena üldse. Niisiis, see jookseb O (1) või pidevalt aega. See kindlasti ei tähenda et sinu kood töötab 1 aste, Aga ükskõik kui palju samme on, kui see ei muutu suurusest sisendid, see on ikka asümptootiliselt konstant, mis me esindame kui O (1). 

Nagu näete ilmselt arvan, seal on palju eri suur O runtimes mõõta algoritme. O (n) ² algoritmid on asümptootiliselt aeglasem kui O (n) algoritme. See tähendab, et kui mitu elementi (n) kasvab, lõpuks O (n) ² algoritme võtab rohkem aega kui O (n) algoritme joosta. See ei tähenda, O (n) algoritme alati kulgema kiiremini kui O (n) ² algoritme, isegi samas keskkonnas, sama riistvara. Võib-olla väikeste sisend suurused,  O (n) ² algoritm võib tegelikult töötavad kiiremini, kuid lõpuks, nagu sisend suurus kasvab suunas lõpmatusse, O (n) ² algoritmi käitusaja lõpuks Eclipse Runtime O (n) algoritmi. Nagu iga ruutkeskmised matemaatiline funktsioon  lõpuks mööduda mis tahes lineaarfunktsioonina ükskõik kui palju edumaa lineaarfunktsioon hakkab liikuma. Kui töötate koos suurte andmemahtude, algoritmide O (n) ² aega saab tõesti lõpuks aeglustub oma programmi, kuid väikese panuse suurused, siis ilmselt ei märka. 

Teine asümptootilisest keerukus on logaritmiline aeg, O (log n). Näide algoritm, mis töötab selle kiiresti on klassikaline binaarne otsing algoritm, leidmiseks element juba sorteeritud elementide loetelu. 

Kui te ei tea, mida Kahendotsingupuu teeb, Ma seletan seda teile tõesti kiiresti. Oletame, et te otsite number 3 Selles valikus täisarvud. Vaadeldakse keskel element massiivi ja küsib: "Kas element Ma tahan sellest suurem võrdne või vähem kui see?" Kui see on võrdne, siis suur. Sa leidsid element, ja sa oled teinud. Kui see on suurem, siis sa tead element peab olema paremal pool massiiv, ja saab ainult vaadata, et tulevikus, ja kui see on väiksem, siis sa tead, see peab olema vasakul poolel. Seda protsessi korratakse väiksema suurusega massiiv kuni õige element on leitud. 

See võimas algoritm lõikab massiivi suurus pooleks iga operatsiooni. Niisiis, leida element sorditud massiivi suurus 8, kõige rohkem (log ₂ 8) või 3 nimetatud toimingute, kontroll keskel element, seejärel lõikamise massiivi poole on vaja, arvestades massiivi suurus 16 võtab (log ₂ 16) või .4. See on vaid 1 operatsiooni kahekordistunud suurus massiiv. Kahekordistades massiivi suurendab Runtime vaid 1 patakas see kood. Jällegi, kontroll keskel element loendis, siis jagamine. Niisiis, see ütles, et tegutseda logaritmiline ajal O (log n). Aga oota, sa ütled, ei see sõltub sellest, millises nimekirjas element otsite on? Mis siis, kui esimene element te vaatate juhtub olema õige? Siis, see võtab vaid 1 toiming, kuitahes suur nimekiri on. 

Noh, et miks arvuti teadlased on rohkem mõttes jaoks asümptootilisest keerukust, mis kajastaks parimal juhul ja halvima etendused algoritm. Rohkem korralikult, ülemise ja alumise piire edasi tööaega. Parimal juhul jaoks Kahendotsingupuu, meie element on seal keskel, ja sa saad selle konstantse ajaga, kuitahes suur ülejäänud massiiv on. Sümbol, mida kasutatakse see on Ω. Niisiis, see algoritm on öelnud, et sõidetud Ω (1). Parimal juhul leiab element kiiresti, ükskõik kui suur massiiv on, kuid halvimal juhul see peab läbima (log n) jagatud kontroll on massiiv leida õige element. Halvima ülemised piirid on nimetatud suurte "O", et sa juba tead. Nii, see on O (log n), kuid Ω (1). 

Lineaarne otsing seevastu kus te kõndida läbi iga element massiivi leida üks soovite, on parimal Ω (1). Jällegi, esimene element, mida soovite. Niisiis, see ei ole oluline, kui suur massiiv on. Halvimal juhul on see viimase elemendi massiivist. Nii, teil on kõndida läbi kõik n elementi massiivi seda leida, nagu kui sa olid otsivad 3. Niisiis, see jookseb O (n) ajaga sest see on võrdeline elementide arvu massiivis. 

Veel üks sümbol, mida kasutatakse on Θ. Seda saab kasutada, et kirjeldada algoritme, kus on parimad ja halvimal juhul on samad. See on nii jada pikkusega algoritme me rääkisime varem. See tähendab, et kui me seda säilitada muutuja enne me salvestada string ja seda hiljem pidevalt aega. Ükskõik, mis number me salvestamine et muutuja, me peame vaatama seda. Parimal juhul on, vaatame seda ja leida stringi pikkusena. Nii Ω (1) või parimal juhul konstantset aega. Halvim on see, me vaatame seda ja leida stringi pikkusena. Nii, O (1) või pidev aja halvim. Niisiis, kuna parimal juhul ja halvimal juhul on sama, võib seda öelda töötamine Θ (1) aeg. 

Kokkuvõttes on meil häid võimalusi põhjus umbes koodid tõhususe tundmata midagi reaalse aja nad joosta, mis mõjutab palju välistest teguritest, sealhulgas erinevate riist-ja tarkvara, või spetsiifikat oma kood. Samuti võimaldab see meil Mõelge hästi järele, mis juhtub kui suurus sisendite suureneb. 

Kui näed O (n) ² algoritm, või veel hullem, O (2 ⁿ) algoritm, üks kiiremini kasvavaid liike, sa tõesti hakata märkama aeglustumine kui alustate tööd suuremate andmemahtude. 

See on asümptootilisest keerukus. Aitäh.