Datastructuren en algoritmen

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

A2 seconden
B8 seconden
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.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

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?
Welke beschrijving van een gelinkte lijst (een lijst waarin elk element een pointer naar het volgende element bevat) is juist in vergelijking met een array?
Op een lege stack worden achtereenvolgens push 1, push 2, pop, push 3, push 4, pop, pop uitgevoerd. In welke volgorde komen de waarden die pop verwijdert eruit?
In een lege wachtrij worden de elementen A, B en C in deze volgorde geplaatst. Daarna wordt er één element uitgehaald, wordt D toegevoegd en weer één uitgehaald, en wordt E toegevoegd en nog één uitgehaald. In welke volgorde worden de elementen uitgehaald?
De expressie „3 4 + 2 * 5 −” in omgekeerde Poolse notatie (postfixnotatie) wordt geëvalueerd door elk getal op een stack te leggen en bij elke operator twee waarden eraf te halen, het resultaat te berekenen en dat weer op de stack te leggen. Wat is het resultaat? De linkeroperand van een operator is de waarde die het eerst op de stack is gelegd.