Asymptoottinen suoritusaika

Asymptoottinen suoritusaika kuvaa algoritmin suoritusajan rajoja suhteessa algoritmin käsittelemän tietojoukon kokoon. Tietojoukon koon kasvaessa algoritmin suoritusaika lähestyy, mutta ei koskaan lähestymissuunnasta riippuen ylitä tai alita, asymptoottista rajaa. Ajan yksikkönä käytetään yhtä algoritmin suorittamaa askelta. Esimerkiksi hyvin sekoitettu korttipakka, jossa on N korttia voidaan järjestää arvojärjestykseen käymällä pakka läpi korkeintaan N kertaa ja jos havaitaan vierekkäiset kortit väärässä järjestyksessä, vaihdetaan näiden paikkaa (kuplalajittelu). Tällöin korttipakan järjestämisen asymptoottinen ylärajan sanotaan olevan O(n²). Jos korttipakka on jo järjestyksessä, se havaitaan käymällä kaikki kortit läpi, mistä saadaan asymptoottiseksi alarajaksi Θ(n).

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ä (esimerkiksi talous-) on rajoitettu. Alla on matemaattinen kuvaus riittävällä tarkkuudella ratkeavasta funktiosta.

Aikavaatimuksen (kompleksisuus) lisäksi algoritmilla voi olla tilavaatimus eli paljonko resursseja (muistia) suoritus voi käyttää. Lisäksi suorituksen kustannus on laskenut sekä muistilatenssin suhteellinen vaikutus suoritusaikaan on kasvanut. Välimuistihutien vaikutus on nykyään merkittävä tekijä algoritmien suunnittelussa.

Taustaa

J. Hartmanis ja R. E. Stearns julkaisivat vuonna 1965 artikkelin On The Computational Complexity of Algorithms, jossa laskennallista (komputaatio) kompleksisuutta verrattiin miten nopeasti kuvitteellinen Turingin kone pystyy käsittelemään käskynauhaa. Abstraktia mallia käytettiin, koska kaikki digitaaliset tietokoneet ovat ideaalisessa muodossa Turingin koneen kaltaisia.

Merkintätavat

Funktioiden kasvunopeudesta käytetään useita eri merkintätapoja. Tässä niistä yleisimmät, eli

• Bachmann–Landau -notaatio tai iso-O -notaatio – aidosti ylhäältä rajoitettu.
• Theta-notaatio tai iso theta (Θ) – aidosti alhaalta ja ylhäältä rajoitettu.
• Iso-omega -notaatio (Ω)

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

Iso-O -notaatio

Yleisesti iso-O -notaationa tunnettu merkintätapa on tunnettu myös Bachmann–Landau -notaationa. Myös termiä Ordo-notaatio käytetään.^lähde?

Matemaattinen merkitys:

Ο(g(n)) = {f(n) | 0 ≤ f(n) ≤ c₂g(n) kaikilla n ≥ n₀}

..missä c₂ on jokin positiivinen reaaliluku ja n₀ 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

Theta-notaatio

Matemaattinen merkitys:

Θ(g(n)) = {f(n) | 0 ≤ c₁*g(n) ≤ f(n) ≤ c₂g(n) kaikilla n ≥ n₀}

.. missä c₁,c₂ on jokin positiivinen reaaliluku ja n₀ on jokin luonnollinen luku.

f(n) on jokin Θ(g(n)):ään sisältyvä funktio, toisin sanoen: on olemassa sellaiset vakiot c₁,c₂ että f(n) on jossain välillä c₁*g(n)..c₂*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 Θ(n²) -ajassa, se Ordo-notaation perusteellakin toimii Ο(n²) -ajassa. Mutta, jos algoritmi toimii Ο(n²) ajassa, siitä ei välittömästi seuraa, että algoritmi toimisi Θ(n²) -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

Esimerkki

Osoitetaan, että 12n⁸ ≠ Ο(n⁷).

Väite:

12n⁸ ≠ Ο(n⁷)

Tehdään vastaoletus:

12n⁸ = Ο(n⁷)

Tällöin on löydyttävä sellaiset c₂ ja n₀ että:

12n⁸ ≤ c₂n⁷ kaikilla n ≥ n₀

Mutta tällöinhän:

12n ≤ c₂ kaikilla n ≥ n₀

Josta seuraa ristiriita.

Vastaoletuksesta seuraa ristiriita, joten alkuperäinen väite on tosi, eli 12n⁸ ≠ Ο(n⁷).

Samalla periaatteella voidaan todistaa, että 12n⁷ = Ο(n⁸) on tosi.

Kirjallisuutta

• Sanjeev Arora & Boaz Barak: Computational Complexity: A Modern Approach, Draft (PDF) (englanniksi)