COMMUNITY

Samenvatting · Informatica · vwo 5 Complexiteit van algoritmen: orde van grootte en efficiëntie

StudyZone

InformaticaVak

WAT ZIT ERIN

1Twee algoritmen kunnen hetzelfde probleem oplossen en toch enorm verschillen in snelheid. Bij een lijst van tien elementen merk je dat niet, bij een miljard wel. Na deze samenvatting bepaal je de orde van grootte van een algoritme en beoordeel je of het ook voor grote invoer…

Bewaar deze samenvatting

Twee algoritmen kunnen hetzelfde probleem oplossen en toch enorm verschillen in snelheid. Bij een lijst van tien elementen merk je dat niet, bij een miljard wel. Na deze samenvatting bepaal je de orde van grootte van een algoritme en beoordeel je of het ook voor grote invoer bruikbaar blijft.

Waarom complexiteit?

Je meet de snelheid van een algoritme niet in seconden, want die hangen af van de computer en de programmeertaal. In plaats daarvan tel je hoe het aantal basisstappen (vergelijkingen, optellingen, toewijzingen) groeit met de grootte van de invoer $n$ . Je kijkt naar het slechtste geval (worst case), omdat dat een garantie geeft.

Orde van grootte

Je geeft de groei aan met de grote-O-notatie: alleen de snelst groeiende term telt, constante factoren laat je weg. Een algoritme met $3 n^{2} + 5 n + 7$ stappen is $O (n^{2})$ .

orde	naam	voorbeeld
$O (1)$	constant	het eerste element van een lijst lezen
$O (lo g n)$	logaritmisch	binair zoeken
$O (n)$	lineair	lineair zoeken, alle elementen optellen
$O (n lo g n)$	lineair-logaritmisch	snelle sorteeralgoritmen (mergesort)
$O (n^{2})$	kwadratisch	bubble sort, selection sort
$O (2^{n})$	exponentieel	alle deelverzamelingen proberen
$O (n!)$	faculteit	alle volgordes proberen

Het aantal stappen bepalen

Kijk naar de lussen:

Een enkele lus die $n$ keer draait: $O (n)$ .
Twee geneste lussen die allebei $n$ keer draaien: $n \cdot n = n^{2}$ , dus $O (n^{2})$ .
Een lus die $n$ telkens halveert (n = n // 2 tot n = 1): $lo g_{2} n$ rondes, dus $O (lo g n)$ .
Twee lussen na elkaar: de stappen tellen op en alleen de grootste telt, dus $O (n) + O (n) = O (n)$ .

Voorbeeld

een inwendige lus die bij ronde

i

maar

i

keer draait, geeft in totaal

1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}

stappen. Ook dat is

O (n^{2})

, want de grootste term is

\frac{1}{2} n^{2}

Wat betekent een orde in de praktijk?

Wat gebeurt er met de rekentijd als $n$ twee keer zo groot wordt?

$O (n)$ : twee keer zo lang.
$O (n^{2})$ : vier keer zo lang.
$O (lo g n)$ : maar één stap erbij.
$O (2^{n})$ : één extra element verdubbelt al de tijd.

Voorbeeld

binair zoeken in een gesorteerde lijst van 1 000 000 elementen kost maximaal ongeveer

lo g_{2} (1000000) \approx 20

vergelijkingen, want

2^{20} = 1048576

. Lineair zoeken kost er in het slechtste geval een miljoen.

Efficiënt en onhandelbaar

Algoritmen met een orde $n^{k}$ (een macht van $n$ ) heten polynomiaal en zijn in de praktijk meestal bruikbaar. Algoritmen met een exponentiële of faculteitsorde groeien zo snel dat ze al bij matige $n$ onhaalbaar zijn.

Voorbeeld: het handelsreizigersprobleem. Een reiziger moet $n$ steden bezoeken en de kortste route zoeken. Alle routes proberen (brute force) kost een aantal stappen dat groeit als $n!$ : bij 10 steden zijn dat al 3,6 miljoen volgordes en bij 20 steden meer dan $2 \cdot 1 0^{18}$ . Voor zulke problemen is geen snel algoritme bekend dat altijd de beste oplossing vindt. In de praktijk gebruikt men heuristieken: slimme methoden die snel een goede, maar niet altijd de beste oplossing geven.

Ruimtecomplexiteit

Naast tijd telt ook geheugen. Een algoritme dat een kopie van de invoer maakt, heeft $O (n)$ extra geheugen nodig; een algoritme dat alleen een paar variabelen gebruikt, $O (1)$ . Tijd en geheugen ruilen vaak: een tabel met tussenresultaten maakt een algoritme sneller maar kost geheugen.

Let op

Alleen de snelst groeiende term telt. $n^{2} + 1000 n$ is $O (n^{2})$ .
Constanten tellen niet mee in O, maar wel in de praktijk bij kleine $n$ .
Slechtste, beste en gemiddelde geval kunnen verschillen. Lineair zoeken kan in het beste geval al bij het eerste element klaar zijn.
** $O$ zegt hoe snel de tijd groeit,** niet hoe lang het precies duurt.

In het kort

Je telt basisstappen als functie van de invoergrootte $n$ , meestal in het slechtste geval.
Grote-O: alleen de snelst groeiende term telt, constanten vallen weg.
Een enkele lus is $O (n)$ , twee geneste lussen $O (n^{2})$ , een halverende lus $O (lo g n)$ .
Bij $O (n^{2})$ betekent een dubbele invoer ongeveer vier keer zoveel tijd.
Exponentiële en faculteitsgroei zijn onhandelbaar; dan gebruikt men heuristieken.

Staat hier iets dat niet klopt of niet hoort? .