2. Analyse van algoritmen

Question 1

Wat is een algoritme?

Answer 1

Een algoritme is een reeks van instructies om vanaf een beginpunt een bepaald doel te bereiken.

Question 2

Wat is een programma?

Answer 2

Een programma is een algoritme of een geheel van algoritmes die uitgeschreven zijn in een bepaalde programmeertaal.

Question 3

Wat is een datastructuur?

Answer 3

Een datastructuur is een manier waarop data bijgehouden wordt.

Question 4

Wat bepaalt de datastructuur?

Answer 4

De datastructuur bepaalt de wijze waarop en hoe efficiënt gegevens kunnen worden opgeslagen, gewijzigd of geraadpleegd.

Question 5

Wat is een goed algoritme?

Answer 5

Een goed algoritme is een efficiënt algoritme, en heeft dus een korte UITVOERINGSTIJD en gebruikt weinig GEHEUGEN.

Question 6

Wat zijn de beperkingen van de uitvoeringstijd experimenteel (System.currentTimeMillis()) te meten?

Answer 6

• Het aantal testen is beperkt. Er zullen bepaalde groottes van invoer niet getest worden, die misschien wel van belang zijn.
• Testen kunnen alleen vergeleken worden met elkaar als ze op identiek hetzelfde platform uitgevoerd worden (hardware en software).
• Om de algoritmen uit te voeren, moeten ze geïmplementeerd worden en moeten er goede testen gezocht worden. Dit vergt veel tijd.

Question 7

Wat zijn primitieve opdrachten?

Answer 7

Dit zijn basisinstructies waarvan de uitvoeringstijd constant is.

Question 8

Som enkele primitieve opdrachten op.

Answer 8

• Een toekenning van een waarde aan een variabele
• Een methodeoproep
• Een return
• Wiskundige en logische bewerkingen (vb optelling, vergelijking)
• Een element raadplegen in een array aan de hand van z’n index

Question 9

Waarom bepalen we het worst-case scenario van een algoritme?

Answer 9

We kiezen voor het slechtste scenario omdat dit zo zijn voordelen heeft:
􏰀- Het geeft een bovengrens aan en in bepaalde domeinen is die bovengrens van cruciaal belang (vb luchtvaart, geneeskunde).
􏰀- Het slechtste scenario komt in bepaalde algoritmen het meest voor.
􏰀- Het gemiddelde is dikwijls even erg als het slechtste geval.

Question 10

Hoe meten we de uitvoeringstijd van een algorithm op een algemene manier?

Answer 10

Door de primitive opdrachten op te tellen.

Question 11

Waarom zijn we enkel geïnteresseerd in de graad van de groei van de uitvoeringstijd?

Answer 11

Dit geeft een beter overzicht van de relatie van het algoritme met n.
De grootte van invoer is namelijk een zeer belangrijke factor in de uitvoeringstijd van een algoritme.

Question 12

Som de zeven meest voorkomende functies op.

Answer 12

• constante functie
• logaritmische functie
• lineaire functie
• kwadratische functie
• n log n functie
• kubische functie
• exponentiële functie

Question 13

Constante functie?

Answer 13

f(n) = c

Wanneer een algoritme een uitvoeringstijd heeft waarin f(n) = c, betekent dit dat het algoritme altijd even lang zal duren, ongeacht de invoer.

n = 1 => f(n) = c
n = 2 => f(n) = c
n = 4 => f(n) = c
...
n = 100 => f(n) = c

> 0(1)

Question 14

Logaritmische functie?

Answer 14

f(n) = log n

Een algoritme heeft als uitvoeringstijd een logaritmische functie wanneer het algoritme het probleem steeds weer in twee deelt, zoals binair zoeken.

n = 1 => f(n) = 0
n = 2 => f(n) = 1
n = 4 => f(n) = 2
...
n = 32 => f(n) = 5

> 0(log n)

Question 15

Lineaire functie?

Answer 15

f(n) = n

Een algoritme heeft een uitvoeringstijd die lineair is, wanneer we iedere keer een eenvoudige basisopdracht moeten uitvoeren voor elke element uit de invoer. Bijvoorbeeld, de vergelijking van een getal x met elk element uit een array met grootte n, zal n vergelijkingen vereisen.

De waarde dat de functie f(n) teruggeeft is recht evenredig met de waarde van n.

n = 1 => f(n) = 1
n = 2 => f(n) = 2
n = 3 => f(n) = 3
...
n = 100 => f(n) = 100

> 0(n)

Question 16

Kwadratische functie?

Answer 16

f(n) = n^2

Een uitvoeringstijd van kwadratische orde komt voor bij algoritmen met geneste lussen.
Als de binnenste lus n keren loopt voor elke doorgang door de buitenste lus, en de buitenste lus loopt ook n keer, dan hebben we een uitvoeringstijd van n * n = n^2.

De waarde dat de functie f(n) teruggeeft is het product van n met zichzelf (of n^2).

n = 1 => f(n) = 1 = 1 * 1
n = 2 => f(n) = 4 = 2 * 2
n = 3 => f(n) = 9 = 3 * 3
...
n = 10 => f(n) = 100

> 0(n^2)

Question 17

n log n functie?

Answer 17

f(n) = n log n

Deze functie groeit sneller dan de lineaire functie, maar is minder stijl dan de kwadratische functie.

Wanneer we de uitvoeringstijd van een algoritme van een kwadratische functie kunnen terugbrengen naar een functie van orde n log n, hebben we een aanzienlijk sneller algoritme.

n = 1 => f(n) = 0 = 0
n = 2 => f(n) = 2*1 = 2
n = 4 => f(n) = 4*2 = 8
...
n = 8 => f(n) = 8*3 = 24

> O(n log n)

Question 18

Kubische functie?

Answer 18

f(n) = n^3

De waarde dat de functie f(n) teruggeeft is drie keer het product van n met zichzelf (of n3).

n = 1 => f(n) = 1
n = 2 => f(n) = 8
n = 3 => f(n) = 27
n = 4 => f(n) = 64
...
n = 10 => f(n) = 1000 = 10 * 10 * 10

> O(n^3)

Question 19

Exponentiële functie?

Answer 19

f(n) = b^n

In de binaire wereld van de computerwetenschappen, is b meestal 2. We spreken dan van f(n) = 2^n.

De waarde dat de functie f(n) teruggeeft is n keer het product van 2 met zichzelf (of 2^n).

n = 1 => f(n) = 2
n = 2 => f(n) = 4
n = 3 => f(n) = 8 = 2 * 2 * 2
...
n = 10 => f(n) = 1024

> O(2^n)

Question 20

Wat is de somformule van Gauss?

Answer 20

1+2+3+4+...+n = n*(n+1)/2
1 + 2 + 3 + 4 + 5 = 15
5 x (5 + 1) / 2 = 15

Question 21

Waarmee moeten we rekening houden bij het meten van de efficiëntie van een algoritme?

Answer 21

Met de grootte van de invoer.

Daarom zullen we de uitvoeringstijd en gebruikte geheugen altijd uitdrukken in functie van de grootte van de invoer.

Question 22

Tot wat zullen we de analyse van een algoritme altijd herleiden?

Answer 22

Tot een functie van n, f(n), waar n de grootte van de invoer voorstelt.