Aikavaativuusluokka
Wikipedia
Aikavaativuusluokka on erityisesti sekä matematiikassa että ohjelmistotieteessä esiintyvä käsite, joka kuvaa funktion tai algoritmien ajallista käyttäytymistä, usein syötteen koon n funktiona. Erityisesti vakiotermit ja -kertoimet jätetään näistä pois, jolloin luokasta näkee nopeasti, kuinka nopeasti aikavaatimukset kasvavat suhteessa syötteen kokoon.
[muokkaa] Määritelmä
Olkoon funktio f(n) tarkasteltava aikavaativuusluokka. Jos funktio g(n) kuvaa tarkasteltavan funktion aikakäyttäytymistä, niin silloin on olemassa jotkin positiiviset vakiot a, b ja n0 siten, että
aina, kun n > n0.
[muokkaa] Esimerkkejä
| Algoritmi | Aikavaativuusluokka |
|---|---|
| Useimpien lajitteluongelmien optimaalinen ratkaisu | nlog(n) |
| Puolitushaku, etsintä sopivasta puurakenteesta | log(n) |
| Kauppamatkustajan ongelma, optimaalinen ratkaisu | cn |
| Kauppamatkustajan ongelman optimaalinen ratkaisu brute-force menetelmällä | n! |