Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Time complexity

Engels: Time complexity · Ook wel: tijdscomplexiteit, runtime complexity, time-complexity

In het kort

Tijdscomplexiteit is een maat die aangeeft hoeveel rekentijd een algoritme nodig heeft om een taak af te ronden. Die schatting telt alle eenvoudige stappen, omdat elke stap een vaste tijd kost en de looptijd hooguit een constante factor van dat aantal verschilt. Ontwikkelaars kunnen zo inschatten hoeveel de rekentijd toeneemt wanneer een algoritme voor dezelfde taak meer stappen moet uitvoeren.

Waarom is dit belangrijk?

Weten hoe snel een berekening groeit, maakt het mogelijk een aanpak te kiezen die bij meer gegevens op tijd klaar is. In de zorg gaat het dan om patiënten aan bedden koppelen, en in het onderwijs om lesroosters zonder overlappende vakken. Medewerkers en studenten hebben een planning nodig die op tijd af is, maar een zware methode kan bij veel gegevens zo traag worden dat de uitkomst te laat komt.

Zo werkt het in de praktijk

Zoekalgoritmen voor tekst, zoals Boyer-Moore en Ukkonen, werken met lineaire tijdscomplexiteit. Binair zoeken in een gesorteerde lijst blijft logaritmisch, en lineair zoeken kan elk element aflopen. In cryptografie houden ontwerpers de tijdscomplexiteit soms constant, tegen aanvallen via tijdmeting.

Onderzoek zoekt lineaire of bijna lineaire tijd als het programma alle invoer leest. Klasse P bevat ja-nee-vragen waarvan de tijd als een macht van de invoer groeit. Vergelijkend sorteren heeft in het slechtste geval minstens n log n vergelijkingen.

Donald Knuth gaf de werkwijze de naam analyse van algoritmen. Big-O-notatie geeft daarin een bovengrens voor de groei van het aantal stappen. Het uniforme kostenmodel rekent met vaste kost per stap en het logaritmische laat de kost meegroeien met het aantal bits.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026