Ero sivun ”Asymptoottinen suoritusaika” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p Botti lisäsi: he:סימון אסימפטוטי |
|||
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 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 (N=korttien lukumäärä) 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ä (
Funktioiden kasvunopeudesta käytetään useita eri merkintätapoja. Tässä niistä yleisimmät, eli
Rivi 18:
Merkitään, että f(n) = ''Ο''(g(n)).
Ordo-merkintä kuvastaa pahinta mahdollista tapausta. Se rajoittaa ylhäältä päin aidosti algoritmin suoritusaikaa. Esimerkiksi
Ordo-notaatiolla siis ilmoitetaan:<BR>
|