Nederlands
Menu

Wat is Tijdcomplexiteit (O-notatie)?

Beschrijving van hoe de rekeninspanning (tijdcomplexiteit) of het geheugen (ruimtecomplexiteit) dat een algoritme nodig heeft, groeit met het aantal gegevens n. Ze wordt geschreven in O-notatie, zoals O(n), O(n log n) of O(n²), waarbij constante factoren en termen van lagere orde wegvallen.

Japanse benaming: 計算量

“Tijdcomplexiteit (O-notatie)” komt voor in 8 oefenvragen uit 2 onderwerpen, bijv. Datastructuren en algoritmen, Prestatiemeting en profiling.

Vakgebied: Datastructuren en algoritmen

O-notatie lezen

O(f(n)) betekent dat de inspanning voor voldoende grote n binnen een constant veelvoud van f(n) blijft. Een algoritme dat 3n² + 5n + 2 vergelijkingen doet, wordt geschreven als O(n²), omdat de term n² overheerst naarmate n groeit. Veelvoorkomende klassen zijn, van klein naar groot, O(1) (constant), O(log n) (binair zoeken), O(n) (lineair zoeken), O(n log n) (mergesort, heapsort), O(n²) (bubblesort, selection sort) en O(2ⁿ) (naïef uitputtend zoeken). Voor n = 1000 is log₂ n ongeveer 10, n log₂ n ongeveer 10.000 en n² is 1 miljoen, dus bij grote hoeveelheden gegevens is het verschil in complexiteit doorslaggevend.

Beste, gemiddelde en slechtste geval

Hetzelfde algoritme kan afhankelijk van de invoer verschillend veel werk doen. Insertion sort doet op gesorteerde gegevens n−1 vergelijkingen, O(n), maar op omgekeerd gesorteerde gegevens n(n−1)/2, O(n²). Quicksort is gemiddeld O(n log n), maar in het slechtste geval O(n²), afhankelijk van de keuze van de pivot en de gegevens. Systemen die een bovengrens voor de responstijd nodig hebben, letten op het slechtste geval, terwijl schattingen van de totale verwerkingshoeveelheid van het gemiddelde geval uitgaan. Als een af en toe dure stap over veel bewerkingen uitmiddelt tot een constante, zoals bij toevoegen aan een dynamische array, worden de kosten beschreven als geamortiseerd O(1).

De werkelijke snelheid hangt niet alleen van de complexiteit af

Omdat de O-notatie constante factoren negeert, kunnen twee algoritmen van O(n) in werkelijke snelheid sterk verschillen. Op moderne computers is het hoofdgeheugen bijna 100 keer trager dan de L1-cache, dus een array in volgorde lezen is vele malen sneller dan een gelinkte lijst doorlopen. Voor kleine n kan een eenvoudig algoritme met een slechtere complexiteit ook sneller zijn; daarom gebruiken praktische sorteerimplementaties insertion sort voor korte stukken. Controleer bij het verbeteren van prestaties eerst of er geen algoritme met een onnodig hoge complexiteit wordt gebruikt, en meet en verfijn daarna details zoals het patroon van geheugentoegangen.

Nu oefenen: vragen over Tijdcomplexiteit (O-notatie)

Wat is de tijdcomplexiteit van een bewerking die in een array van n elementen elk paar van twee verschillende elementen precies één keer vergelijkt (een dubbele lus die element i vergelijkt met alle elementen erna en i telkens één stap verder zet)?

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
Antwoord en toelichting tonen

Antwoord: C. O(n²)

Het aantal vergeleken paren is (n−1) + (n−2) + … + 1 = n(n−1)/2: 45 voor n = 10 en 499.500 voor n = 1000. De O-notatie kijkt alleen naar hoe het aantal groeit als n groot wordt, dus de factor 1/2 en de termen van lagere orde vallen weg en het resultaat is O(n²). Als n verdubbelt, wordt het aantal ongeveer vier keer zo groot. O(n) is de complexiteit van een bewerking die elk element één keer bekijkt, en O(n log n) die van algoritmen zoals mergesort, die de gegevens herhaaldelijk in tweeën delen.

Een programma met tijdcomplexiteit O(n²) doet er 0,5 seconde over bij 1000 gegevens. Hoeveel seconden duurt het ongeveer bij 4000 gegevens?

  1. A2 seconden
  2. B8 seconden
  3. C32 seconden
Antwoord en toelichting tonen

Antwoord: B. 8 seconden

Bij O(n²) is de rekentijd evenredig met het kwadraat van het aantal gegevens. Viermaal zoveel gegevens kost dus 4² = 16 keer zoveel tijd: 0,5 s × 16 = 8 s. 2 seconden zou de uitkomst zijn bij O(n), dat evenredig is met het aantal gegevens, en 32 seconden bij O(n³), dat met de derde macht groeit (4³ = 64 keer). In de praktijk kan het nog trager worden, bijvoorbeeld zodra de gegevens niet meer in de cache passen.

Veelgestelde vragen

Wat is het grondtal van de logaritme in O(log n)?

Een ander grondtal verandert de waarde alleen met een constante factor (log₂ n = log₁₀ n ÷ log₁₀ 2), dus in de O-notatie wordt het grondtal meestal weggelaten. Bij algoritmen die de gegevens elke stap halveren, zoals binair zoeken, ligt het werkelijke aantal dicht bij log₂ n.

Wat is het verschil tussen tijdcomplexiteit en ruimtecomplexiteit?

Tijdcomplexiteit beschrijft hoe de rekeninspanning (uitvoeringstijd) groeit, en ruimtecomplexiteit hoe het benodigde geheugen groeit. Beide worden samen vergeleken: mergesort is O(n log n) in tijd met O(n) werkruimte, terwijl heapsort O(n log n) in tijd is met O(1) ruimte.

“Tijdcomplexiteit (O-notatie)” in de toelichting

Vragen met “Tijdcomplexiteit (O-notatie)” (8)

  1. Wat is de tijdcomplexiteit van een bewerking die in een array van n elementen elk paar van twee verschillende elementen precies één keer vergelijkt (een dubbele lus die element i vergelijkt met alle elementen erna en i telkens één stap verder zet)?
  2. Een programma met tijdcomplexiteit O(n²) doet er 0,5 seconde over bij 1000 gegevens. Hoeveel seconden duurt het ongeveer bij 4000 gegevens?
  3. Welk sorteeralgoritme heeft ook in het slechtste geval tijdcomplexiteit O(n log n) en sorteert met nauwelijks extra geheugen, zoals een werkarray?
  4. In welk typisch geval heeft quicksort tijdcomplexiteit O(n²)?
  5. Lineair zoeken vergelijkt de elementen van een array met 100 verschillende waarden één voor één vanaf het begin om een gezochte waarde te vinden. De gezochte waarde staat altijd in de array en heeft op elke positie dezelfde kans. Wat is het gemiddelde aantal vergelijkingen?
  6. Met binair zoeken wordt een waarde gezocht in 1000 verschillende waarden die oplopend gesorteerd zijn. Eén vergelijking laat zien of de waarden gelijk zijn of dat de ene kleiner of groter is. Wat is het maximale aantal vergelijkingen, voor zowel een geslaagde als een mislukte zoekactie?
  7. Wat is de meest passende reden dat open adressering met lineair proberen bij een hashtabel met veel elementen en een bezettingsgraad van ongeveer 0,5 vaak sneller is dan chaining (elementen koppelen met gelinkte lijsten)?
  8. Bij een programma dat grote hoeveelheden gegevens verwerkt: welke verbetering levert waarschijnlijk de grootste versnelling op?

Verwante termen

Array Binair zoeken (binary search) Binaire heap (binary heap) Mediaan Hashtabel (hash table) Gelinkte lijst (linked list) Cacheregel (cache line) Prefetching Pointer Algoritme van Dijkstra

Naar de woordenlijst