Aikavaativuusluokka

Aikavaativuusluokka on tietojenkäsittelytieteen käsite, joka kuvaa funktion tai algoritmin ajallista käyttäytymistä, usein syötteen koon ${\displaystyle 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 ${\displaystyle f(n)}$ tarkasteltava aikavaativuusluokka. Jos funktio ${\displaystyle g(n)}$ kuvaa tarkasteltavan funktion aikakäyttäytymistä, niin silloin on olemassa jotkin positiiviset vakiot ${\displaystyle a}$, ${\displaystyle b}$ ja ${\displaystyle n_{0}}$ siten, että

${\displaystyle af(n)\leq g(n)\leq bf(n)}$

aina, kun ${\displaystyle n>n_{0}}$.

Esimerkkejä

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