Asymptoottinen suoritusaika

Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan.

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.^lähde? 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ää.^[1] Lisäksi suorituksen kustannus on laskenut sekä muistilatenssin suhteellinen vaikutus suoritusaikaan on kasvanut.^[1] Välimuistihutien vaikutus on nykyään merkittävä tekijä algoritmien suunnittelussa.^[1]

1. ↑ ^{a b c} Mehta, Dinesh P. & Sahni, Sartaj: Handbook of Data Structures And Applications, s. 1-1, 1-6. Chapman & Hall/CRC, 2005. ISBN 1-58488-435-5 (englanniksi)