Algoritmische Complexiteit

Binnen het Collection framework bestaan er verschillende datastructuren, elk met hun eigen algoritmische complexiteit.

Algoritmische complexiteit wordt aangeduid met behulp van de big O-notatie (bijvoorbeeld O(n), O(n^2)), waarbij "O" staat voor "big O" en een bovengrens aangeeft voor de groei van de uitvoeringstijd als functie van de invoergrootte.

Hieronder staan de belangrijkste typen algoritmische complexiteit:

• O(1) (constante tijd): tijdcomplexiteit hangt niet af van de grootte van de invoergegevens. Bijvoorbeeld, het benaderen van een element in een array via de index;

• O(log n) (logaritmische tijd): tijdcomplexiteit groeit logaritmisch met de grootte van de invoergegevens. Voorbeeld: binaire zoekopdracht in een gesorteerde array;

• O(n) (lineaire tijd): tijdcomplexiteit groeit lineair met de grootte van de invoergegevens. Voorbeeld: itereren door alle elementen in een ArrayList;

• O(n^2) (kwadratische tijd): tijdcomplexiteit is evenredig met het kwadraat van de grootte van de invoergegevens. Voorbeeld: bubblesort.

Dit zijn basiscategorieën, en er bestaan veel andere typen algoritmische complexiteit, zoals O(n log n), O(2^n), O(n!) en andere, die complexere algoritmen karakteriseren. Het kiezen van een efficiënt algoritme, rekening houdend met de complexiteit, is een essentieel aspect van softwareontwikkeling.