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 aikavaatimuksetkasvavat 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)\leq g(n)\leq 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!$