Algoritmisk kompleksitet

I Collection framework findes der mange forskellige datastrukturer, og hver af dem har sin egen algoritmiske kompleksitet.

Algoritmisk kompleksitet angives ved hjælp af big O-notation (f.eks. O(n), O(n^2)), hvor "O" står for "big O" og angiver en øvre grænse for væksten af kørselstiden som en funktion af inputstørrelsen.

Her er de vigtigste typer af algoritmisk kompleksitet:

• O(1) (konstant tid): tidskompleksiteten afhænger ikke af størrelsen på inputdataene. For eksempel adgang til et element i et array via indeks;

• O(log n) (logaritmisk tid): tidskompleksiteten vokser logaritmisk med størrelsen på inputdataene. Eksempel: binær søgning i et sorteret array;

• O(n) (lineær tid): tidskompleksiteten vokser lineært med størrelsen på inputdataene. Eksempel: gennemløb af alle elementer i en ArrayList;

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

Dette er grundlæggende kategorier, og der findes mange andre typer af algoritmisk kompleksitet, såsom O(n log n), O(2^n), O(n!) og andre, som karakteriserer mere komplekse algoritmer. Valg af en effektiv algoritme under hensyntagen til dens kompleksitet er et centralt aspekt af softwareudvikling.