Aikavaativuusluokka

Wikipedia
Loikkaa: valikkoon, hakuun

Aikavaativuusluokka on tietojenkäsittelytieteen käsite, joka kuvaa funktion tai algoritmin 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.

Määritelmä[muokkaa | muokkaa wikitekstiä]

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 n_0 siten, että

af(n) \le g(n) \le bf(n)

aina, kun n > n_0.

Esimerkkejä[muokkaa | muokkaa wikitekstiä]

Algoritmi Aikavaativuusluokka
Useimpien lajitteluongelmien optimaalinen ratkaisu n log(n)
Puolitushaku, etsintä sopivasta puurakenteesta log(n)
Kauppamatkustajan ongelma, optimaalinen ratkaisu c^n
Kauppamatkustajan ongelman optimaalinen ratkaisu brute-force menetelmällä n!