Ero sivun ”Aikavaativuusluokka” versioiden välillä
Poistettu sisältö Lisätty sisältö
alkuvedos, en-linkki ei vastaa tosin tätä artikkelia |
(ei mitään eroa)
|
Versio 8. helmikuuta 2007 kello 11.06
Aikavaativuusluokka on erityisesti sekä matematiikassa että ohjelmistotieteessä esiintyvä käsite, joka kuvaa funktion tai algoritmien 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 | Aikavaativuusluokka |
---|---|
Useimpien lajitteluongelmien optimaalinen ratkaisu | |
Puolitushaku, etsintä sopivasta puurakenteesta | |
Kauppamatkustajan ongelma, optimaalinen ratkaisu | |
Kauppamatkustajan ongelman optimaalinen ratkaisu brute-force menetelmällä |