Aikakompleksiteetti

Aikakompleksiteetti kuvaa, kuinka nopeasti algoritmin suorituskyky kasvaa, kun syötteen koko n kasvaa. Tyypillisesti tarkastelu tehdään suurimman tilan rajaamiseksi käyttämällä Big O -notaatio, joka kuvaa kasvunopeutta ilman pienimpiä vakioita.

Yleisimmät merkinnät ovat O(1) vakioaika, O(n) lineaarinen, O(log n) logaritminen sekä O(n log n), O(n^2) ja muut kasvuvaihtoehdot. Lisäksi erikseen ilmoitetaan paras-case, keskinkertainen-case (average-case) ja huonoin-case (worst-case). Esimerkkejä: binaarihaku on O(log n), lineaarinen haku on O(n), ja lajittelu voi olla O(n log n) tai O(n^2) riippuen käytetystä algoritmista.

Analysointi tapahtuu yleensä muodostamalla operaatioiden määrä funktiona n. Tämä voidaan ratkaista rekursioyhtälöiden tai muiden menetelmien avulla. Aikakompleksiteetin lisäksi on usein hyödyllistä tarkastella tilakompleksiteettiä eli muistinkäyttöä.

Aikakompleksiteetti auttaa vertailemaan algoritmien tehokkuutta ja skaalautuvuutta sekä antamaan viitteitä siitä, miten tiedon rakenne ja syötteen ominaisuudet vaikuttavat suoritusaikaan. On kuitenkin tärkeää huomata, että todellinen aika riippuu myös tekijöistä kuten välimuistin käytöstä, toteutuksesta ja laitteistosta, joten Big O on vain yksi mittari.