[Powered by Google Translate] Olet varmaan kuullut puhuttavan nopea tai tehokas algoritmi toteuttamisesta oman tietyn tehtävän, mutta mitä se tarkoittaa algoritmin olla nopea tai tehokas? No, se ei puhu mittauksen reaaliajassa, kuten sekuntia tai minuuttia. Tämä johtuu siitä, tietokonelaitteiston ja ohjelmiston vaihdella suuresti. Oma ohjelma voisi ajaa hitaammin kuin sinun, koska olen käynnissä sitä vanhempi tietokone, tai koska satun pelata online-videopeli samaan aikaan, joka on kahmimalla kaikki minun muistiin, tai voisin olla käynnissä oman ohjelman kautta eri ohjelmistojen joka on yhteydessä koneen eri alhaisella tasolla. Se on kuin vertaisi omenoita ja appelsiineja. Vain koska minun hitaampi tietokone kestää kuin sinun antaa takaisin vastausta ei tarkoita sinulla on tehokkaampi algoritmi. 

Joten, koska emme voi suoraan verrata runtimes ohjelmien sekunnin tai minuutin, Miten voimme vertailla 2 eri algoritmeja riippumatta niiden laitteita tai ohjelmistoja ympäristölle? Voit luoda tasaisemman tapa mitata algoritmisen tehokkuutta, tietotekniikan tutkijoita ja matemaatikot ovat kehittäneet käsitteet mittaamiseksi asymptoottinen monimutkaisuus ohjelman ja merkintä nimeltään "Big Ohnotation" kuvaamiseen tässä. Muodollinen määritelmä on, että funktio f (x) toimii suuruusluokkaa g (x) jos on olemassa joitakin (x) arvo, x ₀ ja Joissakin vakio, C, jonka f (x) on pienempi tai yhtä suuri kuin että vakio kertaa g (x) kaikilla x on suurempi kuin x ₀. 

Mutta älä pelkää pois virallisen määritelmän. Mitä tämä oikeastaan ​​tarkoittaa vähemmän teoreettisesti? No, se on pohjimmiltaan tapa analysoida kuinka nopeasti ohjelman runtime kasvaa asymptoottisesti. Toisin sanoen, kuten kokoa panosten kasvaa kohti ääretöntä, sanoa, olet lajittelu joukko koko 1000 verrattuna joukko koko 10. Miten runtime oman ohjelman kasvaa? Oletetaan esimerkiksi, laskee merkkien määrä in string yksinkertaisin tapa  kävelemällä läpi koko merkkijono kirjain-by-kirjain ja lisäämällä 1 laskuri kunkin merkin. Tämä algoritmi on sanonut ajaa lineaarisessa ajassa suhteen merkkien määrä, 'N' merkkijono. Lyhyesti sanottuna, se toimii O (n). Miksi on näin? No, käyttäen tätä lähestymistapaa, aika, joka tarvitaan kulkemaan koko merkkijono on verrannollinen merkkien määrä. Counting merkkien määrä 20-merkkijonon vie kaksi kertaa niin kauan kuin se kestää laskea merkkiä 10-merkkinen merkkijono, koska sinulla on katsoa kaikki merkit ja kukin merkki vie saman verran aikaa tarkastella. Kun lisäät merkkien määrä, runtime kasvaa lineaarisesti tulo pituus. 

Nyt, kuvittele jos päätät, että lineaarisen ajan, O (n), ei vain ollut tarpeeksi nopea sinulle? Ehkä olet tallentamiseen valtava jouset, ja sinulla ei ole varaa ylimääräistä aikaa kestäisi kulkemaan kaikkien niiden merkkien laskemisen yhden by-one. Joten, päätät kokeilla jotain erilaista. Mitä jos tapahtuisi jo tallentaa monta merkkiä in string, eli vuonna muuttuja nimeltä "len" varhaisessa vaiheessa ohjelmaan ennen kuin edes tallentaa aivan ensimmäinen merkki merkkijono? Sitten kaikki sinun täytyy tehdä nyt selvittää merkkijonon pituus, on tarkistaa, mitä muuttujan arvo on. Sinulla ei tarvitse katsoa merkkijonon itse ollenkaan, ja päästä arvo muuttujan kuten LEN pidetään asymptoottisesti vakio toiminnassa, tai O (1). Miksi on näin? No, muistaa, mitä asymptoottinen monimutkaisuus tarkoittaa. Miten runtime muutoksen koko teidän tulot kasvaa? 

Sano yritit saada merkkien määrä isompi merkkijono. No, se ei väliä kuinka suuri teet merkkijono, jopa miljoona merkkiä pitkä, kaikki sinun täytyy tehdä löytää merkkijonon pituus tätä lähestymistapaa, on lukea muuttujan arvo len- jotka olet jo tehnyt. Tulo pituus, joka on, että merkkijonon pituus yrität löytää, ei vaikuta lainkaan kuinka nopeasti ohjelma toimii. Tämä osa ohjelmaa kulkisi yhtä nopeaa yhden merkkijonon ja tuhannen merkkijonon, ja siksi tämä ohjelma kutsutaan käynnissä jatkuvasti ajan suhteessa sisääntulon koko. 

Tietenkin siellä haittana. Vietät lisää muistia tietokoneeseen tallennetaan muuttujan ja ylimääräistä aikaa se vie tehdä todellinen varastoinnin muuttujan mutta kohta on edelleen voimassa, selvittää kuinka kauan merkkijono oli ei riipu merkkijonon pituus lainkaan. Niin, se kulkee O (1) tai vakio ajan. Tämä ei tietenkään tarvitse tarkoittaa että koodi toimii 1 askeleen, mutta ei väliä kuinka monta askelta on, jos se ei muutu koko panosten se on silti asymptoottisesti vakio jota edustan O (1). 

Kuten arvata saattaa, on olemassa monia erilaisia ​​Big O runtimes mitata algoritmit. O (n) ² algoritmit ovat asymptoottisesti hitaampia kuin O (n) algoritmeja. Toisin sanoen, kuten elementtien määrä (n) kasvaa, lopulta O (n) ² algoritmeja vie enemmän aikaa kuin O (n) algoritmit suorittaa. Tämä ei tarkoita O (n) algoritmit aina ajaa nopeammin kuin O (n) ² algoritmeja, jopa samassa ympäristössä, samalla laitteisto. Ehkä pieni panos koot,  O (n) ² algoritmi saattaisi toimia nopeammin, mutta, lopulta, kun tulo koko kasvaa kohti ääretöntä, O (n) ² algoritmin runtime lopulta varjoonsa kulkuaikaerojen O (n)-algoritmia. Aivan kuten mikä tahansa asteen matemaattinen funktio  lopulta ohittaa minkä tahansa lineaarinen funktio, ei väliä kuinka paljon etumatkaa lineaarinen funktio alkaa pois. Jos olet työskennellyt suuria tietomääriä, algoritmeja, jotka toimivat O (n) ² aikaa voi todella päätyä hidastamatta ohjelmaa, mutta pienellä panoksella kokoja, luultavasti ei edes huomaa. 

Toinen asymptoottinen monimutkaisuus on, logaritminen aikaa, O (log n). Esimerkki algoritmi, joka suorittaa tämän nopeasti on klassinen binäärihakupuu algoritmi, löytää osa jo lajiteltu luettelo elementtejä. 

Jos et tiedä mitä binäärihakupuu tekee, Selitän sen teille todella nopeasti. Sanotaan etsit numero 3 Tässä joukko kokonaislukuja. Siinä tarkastellaan keskellä alkiota ja kysyy, "Onko elementin haluan suurempi, yhtä suuri tai pienempi kuin tämä?" Jos se on sama, niin hyvä. Löysit elementti, ja olet valmis. Jos se on suurempi, niin tiedät elementti on oltava oikeassa reunassa array, ja voit vain katsoa, ​​että tulevaisuudessa, ja jos se on pienempi, niin tiedät sen on oltava vasemmalla puolella. Tämä prosessi toistetaan sitten kanssa pienemmän koon array kunnes oikea elementti on löytynyt. 

Tämä tehokas algoritmi leikkaa jonon pituus on puoli jokaisen operaation. Joten, löytää osa lajitellaan joukko koko 8, enintään (log ₂ 8), tai 3 näistä toimista, tarkkailun keskimmäinen elementti, sitten leikkaamalla array puoli tarvitaan, taas joukko koko 16 vie (log ₂ 16), tai 4 toimintaa. Se on vain 1 enemmän toiminnassa kaksinkertaistui-size array. Koko kaksinkertaistui array lisää runtime vain 1 kimpale tämän koodin. Jälleen tarkistaa keskimmäinen elementti luettelosta ja halkaisu. Niin, se sanoi toimimaan logaritminen aika, O (log n). Mutta hetkinen, te sanotte, ei tämä riipu siitä, missä luettelossa elementti etsit on? Mitä jos ensimmäinen elementti sinä katsot sattuu olemaan oikea? Sitten se kestää vain 1 käytössä, ei väliä kuinka iso lista on. 

No, siksi tietojenkäsittelyasiantuntijat enemmän ehdot varten asymptoottinen monimutkaisuus jotka heijastavat parhaiten tapaus ja pahimman tapauksen suorituskyky algoritmin. Oikeammin, ylä-ja alarajojen on runtime. Parhaassa tapauksessa binäärihakupuu, meidän elementti on tuolla keskellä, ja saat sen jatkuvasti ajan siitä, kuinka iso loput joukko on. Symboli käyttää tähän on Ω. Joten, tämä algoritmi on mainittu toimimaan Ω (1). Parhaassa tapauksessa se löytää elementti nopeasti, ei väliä kuinka suuri joukko on, mutta pahimmassa tapauksessa, se on suorittaa (log n) kohdalta tarkastuksia on array löytää oikea elementti. Pahin ylärajat viitataan isolla "O", että tiedät jo. Niin, se on O (log n), mutta Ω (1). 

Lineaarista hakua, sitä vastoin, jossa kävelee jokaisen alkiota löytää haluamasi, on paras Ω (1). Jälleen ensimmäinen elementti haluat. Niin, se ei ole väliä kuinka suuri joukko on. Pahimmassa tapauksessa se viimeinen alkio. Joten, sinun täytyy käydä läpi kaikki n elementtejä array löytää se, kuten jos etsit 3. Niin, se kulkee O (n) aika koska se on verrannollinen elementtien lukumäärä jono. 

Yksi symboli on käytetty Θ. Tätä voidaan käyttää kuvaamaan algoritmeja, joissa paras ja pahimmassa tapauksessa ovat samat. Tämä tapaus on merkkijonon pituus algoritmit puhuimme aiemmin. Eli jos me säilytä se muuttuja ennen me tallentaa merkkijonon ja käyttää sitä myöhemmin jatkuvasti ajan. Ei ole väliä mitä numero olemme tallentaminen muuttujan, meidän täytyy katsoa sitä. Parhaassa tapauksessa on, katsomme sitä ja löytää langan pituutta. Joten Ω (1) tai parhaassa tapauksessa vakio ajan. Pahimmassa tapauksessa on, katsomme sitä ja löytää merkkijonon pituus. Niin, O (1) tai vakio aikaa pahimmassa tapauksessa. Joten, koska parhaassa tapauksessa ja pahimmassa tapauksessa ovat samat, Tämän voidaan sanoa ajaa Θ (1) aika. 

Yhteenvetona, meillä on hyviä tapoja syystä noin koodeja tehokkuutta tietämättä mitään reaalimaailman aikaa he ottavat juosta, johon vaikuttaa paljon ulkopuoliset tekijät, mukaan lukien erilaiset laitteet, ohjelmistot, tai yksityiskohtien koodisi. Lisäksi sen avulla voimme järkeillä hyvin siitä, mitä tapahtuu kun koko panosten kasvaessa. 

Jos käytät O (n) ² algoritmi, tai pahempaa, O (2 ⁿ) algoritmi, yksi nopeimmin kasvavista tyypit, sinun todella alkaa huomata hidastumiseen Kun aloitat työskentelyn suurempia tietomääriä. 

Se asymptoottinen monimutkaisuutta. Kiitos.