Algoritminen kompleksisuus

Collection framework -kirjastossa on useita erilaisia tietorakenteita, joilla jokaisella on oma algoritminen kompleksisuutensa.

Algoritminen kompleksisuus ilmaistaan big O -notaatiolla (esim. O(n), O(n^2)), jossa "O" tarkoittaa "big O" ja osoittaa ylärajan suoritusaikojen kasvulle syötteen koon funktiona.

Tässä ovat tärkeimmät algoritmisen kompleksisuuden tyypit:

• O(1) (vakioaika): aikavaativuus ei riipu syötteen koosta. Esimerkki: alkion hakeminen taulukosta indeksin perusteella;

• O(log n) (logaritminen aika): aikavaativuus kasvaa logaritmisesti syötteen koon mukana. Esimerkki: binäärihaku lajitellusta taulukosta;

• O(n) (lineaarinen aika): aikavaativuus kasvaa lineaarisesti syötteen koon mukana. Esimerkki: kaikkien alkioiden läpikäynti ArrayList-rakenteessa;

• O(n^2) (neliöllinen aika): aikavaativuus on verrannollinen syötteen koon neliöön. Esimerkki: kuplalajittelu.

Nämä ovat peruskategorioita, ja on olemassa monia muita algoritmisen kompleksisuuden tyyppejä, kuten O(n log n), O(2^n), O(n!) ja muita, jotka kuvaavat monimutkaisempia algoritmeja. Tehokkaan algoritmin valinta kompleksisuuden perusteella on olennainen osa ohjelmistokehitystä.