Aikavaativuusluokka

Aikavaativuusluokka on tietojenkäsittelytieteen käsite, joka kuvaa funktion tai algoritmin ajallista käyttäytymistä, usein syötteen koon 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

Olkoon funktio   tarkasteltava aikavaativuusluokka. Jos funktio   kuvaa tarkasteltavan funktion aikakäyttäytymistä, niin silloin on olemassa jotkin positiiviset vakiot  ,   ja   siten, että

 

aina, kun  .

EsimerkkejäMuokkaa

Algoritmi Aikavaativuusluokka
Useimpien lajitteluongelmien optimaalinen ratkaisu  
Puolitushaku, etsintä sopivasta puurakenteesta  
Kauppamatkustajan ongelma, optimaalinen ratkaisu  
Kauppamatkustajan ongelman optimaalinen ratkaisu brute-force menetelmällä