Aikavaativuusluokka

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

a f ( n ) ≤ g ( n ) ≤ b f ( n ) {\displaystyle af(n)\leq g(n)\leq bf(n)}

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

Esimerkkejä

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