Aikavaativuusluokka

Kohteesta Wikipedia
Loikkaa: valikkoon, hakuun

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 | muokkaa wikitekstiä]

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 | muokkaa wikitekstiä]

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