[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.