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ä
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ä
Algoritmi AikavaativuusluokkaUseimpien lajitteluongelmien optimaalinen ratkaisuPuolitushaku, etsintä sopivasta puurakenteestaKauppamatkustajan ongelma, optimaalinen ratkaisuKauppamatkustajan ongelman optimaalinen ratkaisu brute-force menetelmällä
Luokka:Tietojenkäsittelyteoria Luokka:Seulonnan keskeiset artikkelit