Naar inhoud
BetaAI Begrippen

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

Asymptotische complexiteit

Engels: Asymptotic computational complexity · Ook wel: asymptotic computational complexity, asymptotic complexity, asymptotische computationele complexiteit

In het kort

Asymptotische computationele complexiteit is een schatting van de rekentijd of het geheugen van een algoritme bij steeds grotere invoer. Anders dan een meting op één computer laat dit vooral zien hoe rekentijd en geheugen groeien, vaak als bovengrens in de grote-O-notatie, een korte schrijfwijze voor die groei. Daarmee vergelijken ontwikkelaars algoritmen op die groei, bijvoorbeeld een lineaire tegenover een kwadratische toename, los van de snelheid van één computer.

Waarom is dit belangrijk?

Onderzoekers kunnen trage rekenmethoden laten vallen nog voordat ze die bouwen, door eerst het gedrag bij veel gegevens te bekijken. In de wetenschap maakt dat duidelijk welke planningsvraagstukken bij een omvangrijke taak te lang duren voor een bruikbare uitkomst. Leerlingen en werknemers kiezen zo een methode die bij een zwaardere opdracht bruikbaar blijft, al telt bij een korte opdracht een eenvoudige bouw vaak meer.

Zo werkt het in de praktijk

In de softwarepraktijk gebruiken informatici asymptotische computationele complexiteit, omdat een tijdmeting niet alle invoeren dekt. Zo schatten zij de rekentijd van binair zoeken in een gesorteerde lijst. In de wiskunde groeien de snelste bekende methoden voor ontbinding in priemfactoren sneller dan elke veelterm en trager dan een exponentiële functie.

Het onderzoeksveld heet analyse van algoritmen. Donald Knuth voerde die term in. De computationele complexiteitstheorie schat hierin hoeveel rekenkracht methoden voor een vraagstuk vragen.

In de beroepspraktijk leggen informatici de schatting vast in een kostenmodel. Het uniforme kostenmodel geeft elke machinebewerking dezelfde kost. Het logaritmische kostenmodel laat de kost meelopen met het aantal bits en past bij grote getallen in de cryptografie.

Bron: en.wikipedia.org

Gecontroleerd op 23 oktober 2026