W1 - Analyse van algoritmes

Question 1

O.b.v. wat analyseer je een algoritme?

Answer 1

Het aantal stappen dat het algoritme uitvoert.
T(n) = aantal operaties
Big O = Orde van groei voor het aantal operaties naarmate n toeneemt.

Question 2

Wat is het belangrijkste verschil tussen T(n) en Big O?

Answer 2

Big O gaat om de Orde van Groei o.b.v. de grootste term.
T(n) gaat om het aantal operaties / stappen, waarmee je de specifieke tijdcomplexiteit uitdrukt.

Question 3

Belangrijke sorteeralgoritmes (week 1):

Answer 3

1. Bubble sort
2. Insertion sort
3. Selection sort

Question 4

Hoe werkt Bubble sort?

Answer 4

Grootste getal ‘bubbelt’ naar ‘boven’.
Vergelijkt telkens 2 elementen en wisselt ze als het linkergetal groter is dan het rechtergetal.
Veel wissels, veel vergelijkingen.

Question 5

Hoe werkt Selection sort?

Answer 5

Selection sort zoekt telkens het kleinste getal.
Wisselt het eerste getal met het kleinste getal en gaat dan verder naar de volgende index.
Minder wissels dan Bubble sort (max. 1 per iteratie), veel vergelijkingen.

Question 6

Hoe werkt Insertion sort?

Answer 6

Je vormt links een groeiende deelrij van gesorteerde elementen.
Breid telkens uit met 1 element naar rechts en vergelijk deze met de elementen in de deelrij.
Insert het op de juiste plek als het kleiner blijkt te zijn.