Ero sivun ”Asymptoottinen suoritusaika” versioiden välillä
| [arvioimaton versio] | [katsottu versio] |
Poistettu sisältö Lisätty sisältö
p täsmennys |
|||
Rivi 1:
'''Asymptoottinen suoritusaika''' kuvaa [[algoritmi]]n 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|6. maaliskuuta 2012|Mitähänä tämä virke edes tarkoittaa}} 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<sup>2</sup>)''. Jos korttipakka on jo järjestyksessä, se havaitaan käymällä kaikki kortit läpi, mistä saadaan asymptoottiseksi alarajaksi ''Θ''(n).
Puhtaan [[matematiikka|matematiikan]] ja mekaanisen laskennan välillä on useita eroja, joista yksi on monien matematiikan [[funktio]]iden [[asymptootti]]nen luonne. Mikäli näitä funktioita pyritään ratkaisemaan [[alkeisoperaatio]]iden avulla, laskenta-aika venyy. [[Pii (vakio)|Piin]] desimaalien laskenta on tästä yksi esimerkki. Käytännössä usein riittää kuvata yhtälö yksinkertaisemmassa muodossa, koska käsiteltävien [[desimaali]]en määrä monissa järjestelmissä (esimerkiksi talous-) on rajoitettu. Alla on matemaattinen kuvaus riittävällä tarkkuudella ratkeavasta funktiosta.
| |||