Asymptoottinen suoritusaika
Wikipedia
Tämän artikkelin määritelmä puuttuu tai on huonosti laadittu. | |
Lisää tietoa saattaa olla keskustelusivulla. |
Puhtaan matematiikan ja mekaanisen laskennan välillä on useita eroja, joista yksi on monien matematiikan funktioiden asymptoottinen luonne. Mikäli näitä funktioita pyritään ratkaisemaan alkeisoperaatioiden avulla, laskenta-aika venyy. Piin desimaalien laskenta on tästä yksi esimerkki. Käytännössä usein riittää kuvata yhtälö yksinkertaisemmassa muodossa, koska käsiteltävien desimaalien määrä monissa järjestelmissä (esim. talous-) on rajoitettu. Alla on matemaattinen kuvaus riittävällä tarkkuudella ratkeavasta funktiosta.
Funktioiden kasvunopeudesta käytetään useita eri merkintätapoja. Käsittelen tässä niistä yleisimmät, eli
- Theta-notaatio(Θ) - aidosti alhaalta ja ylhäältä rajoitettu.
- Ordo-notaatio(Ο) - aidosti ylhäältä rajoitettu.
Lisäksi vielä vähemmän käytetty merkintätapa:
- ω-notaatio – aidosti alhaalta rajoitettu, joka tarkoittaa lyhyesti Suoritukseen kuluu vähintään näin monta alkeisoperaatiota, mutta se voi kuluttaa enemmänkin
[muokkaa] Ordo-notaatio
Matemaattinen merkitys:
Ο(g(n)) = {f(n) | 0 <= f(n) <= c2g(n) kaikilla n >= n0}
missä c2 on jokin positiivinen reaaliluku ja n0 on jokin luonnollinen luku.
Merkitään, että f(n) = Ο(g(n)).
Ordo-merkintä kuvastaa pahinta mahdollista tapausta. Se rajoittaa ylhäältä päin aidosti algoritmin suoritusaikaa. Esimerkiksi, pikalajittelu toimii nopeimmin jos alkiot ovat syötteessä mahdollisimman sekaisin. Lisäyslajittelu toimii nopeimmin jos alkiot ovat jo järjestyksessä, ja hitaimmin jos käänteisessä järjestyksessä. Ordo-notaatiolla jätetään syötteen aiheuttama suoritusajan vaihtelu huomiotta, ja keskitytään vain pahimpaan mahdolliseen tapaukseen, jolloin lajittelu kestää eniten aikaa.
Ordo-notaatiolla siis ilmoitetaan:
Suoritukseen kuluu maksimissaan näin monta alkeisoperaatiota syötteestä riippumatta, mutta se voi valmistua vähemmälläkin
[muokkaa] Theta-notaatio
Matemaattinen merkitys:
Θ(g(n)) = {f(n) | 0 <= c1*g(n) <= f(n) <= c2g(n) kaikilla n >= n0}
missä c1,c2 on jokin positiivinen reaaliluku ja n0 on jokin luonnollinen luku.
f(n) on jokin Θ(g(n)):ään sisältyvä funktio, toisin sanoen: on olemassa sellaiset vakiot c1,c2 että f(n) on jossain välillä c1*g(n)..c2*g(n), silloin kun n kasvaa riittävän suureksi.
Θ(g(n)) on siis itse asiassa funktioiden joukko.
Theta-merkintä kertoo sekä hitaimman että nopeimman suoritusajan. Toisin sanoen, algoritmin toimiessa Θ(n2) -ajassa, se Ordo-notaation perusteellakin toimii Ο(n2) -ajassa. Mutta, jos algoritmi toimii Ο(n2) ajassa, siitä ei välittömästi seuraa, että algoritmi toimisi Θ(n2) -ajassa, sillä Θ(f(n)) sisältää Ο(f(n)):n mutta Ο(f(n)) ei sisällä Θ(f(n)):aa.
Theta-notaatiolla siis ilmoitetaan:
Tarvittavien alkeisoperaatioiden määrä on aina tällä välillä syötteestä riippumatta
[muokkaa] Esimerkki
Osoitetaan että 12n8 != Θ(n7).
Väite:
12n8 != Θ(n7)
Vastaväite:
12n8 = Θ(n7)
Tällöin pitää löytyä sellaiset c2 ja n0 että:
12n8 <= c2n7 kaikilla n >= n0
Mutta tällöinhän:
12n2<= c2 kaikilla n >= n0
Josta nähdään, että alkuperäinen väite on tosi 12n8 != Θ(n7).
Samalla periaatteella voidaan todistaa, että 12n7 = Θ(n8) on tosi.