Aikavaativuusluokka

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ä

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ä

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