Algoritmisk kompleksitet

I Collection framework finnes det mange ulike datastrukturer, og hver av dem har sin egen algoritmiske kompleksitet.

Algoritmisk kompleksitet angis ved bruk av big O-notasjon (f.eks. O(n), O(n^2)), der "O" står for "big O" og indikerer en øvre grense for veksten i kjøretid som en funksjon av størrelsen på input.

Her er hovedtypene av algoritmisk kompleksitet:

• O(1) (konstant tid): tidskompleksiteten avhenger ikke av størrelsen på inputdataene. For eksempel, tilgang til et element i en tabell ved indeks;

• O(log n) (logaritmisk tid): tidskompleksiteten vokser logaritmisk med størrelsen på inputdataene. Eksempel: binærsøk i en sortert tabell;

• O(n) (lineær tid): tidskompleksiteten vokser lineært med størrelsen på inputdataene. Eksempel: iterasjon gjennom alle elementene i en ArrayList;

• O(n^2) (kvadratisk tid): tidskompleksiteten er proporsjonal med kvadratet av størrelsen på inputdataene. Eksempel: boblesortering.

Dette er grunnleggende kategorier, og det finnes mange andre typer algoritmisk kompleksitet, som O(n log n), O(2^n), O(n!) og andre, som kjennetegner mer komplekse algoritmer. Valg av en effektiv algoritme, med hensyn til kompleksitet, er et viktig aspekt ved programvareutvikling.