Datastructuren: Samenvatting deel 2
Recursie en Master theorem
Recursieve methode: een methode die zichzelf aanroept
→ Handig voor het opsplitsen van een probleem, waarvan je niet weet hoe je die moet oplossen, in
kleinere problemen die je wel kan oplossen
Voorbeeld: Optellen
Je hebt een array van integers, waarvan je de som wil berekenen, maar je weet niet hoe je dit moet
aanpakken. Je weet echter wel dat de totaalsom gelijk is aan de som van de linker en rechter helft van de
array. Je gaat het probleem dus met recursie aanpakken:
static int Som(int[] A, int p, int q)
{
//Base-cases
if(q <= p) //Segment van lengte nul...
return 0; //... heeft als return waarde ook nul
if(q == p+1) //Segment met lente een...
return A[p]; //... heeft als return waarde dat element
//Recursie
int r = (p + q)/2;
int L = Som(A, p, r);
int R = Som(A, r, q);
return R+L;
}
Hier splitsen we de array steeds op in twee gelijke delen met grenzen p en q. Dan checken we eerst de
base-cases; is het een segment van lengte 0 of 1? Is dit niet het geval, dan gaan we verder de recursie in,
totdat we wel bij de base-case komen. Wanneer je helemaal onderaan bij de base-case bent, ga je stap
voor stap weer omhoog en tel je elke stap L op bij R. Zo krijg je uiteindelijk de som van de array.
Base-case: het kleinst mogelijke ‘probleem’ dat niet verder opgesplitst kan worden
We hebben hier twee base-cases, want met alleen de eerste base-case zouden we in een oneindige
recursie terecht komen. Want een segment van 1 element kan altijd opgesplitst worden in een segment
van 0 en 1. Het segment van 0 geeft correct 0 terug, maar het segment van 1 gaat oneindig vaak terug de
recursie in, wat een overflow veroorzaakt (wat natuurlijk resulteert in een crash). Door de tweede base-
case toe te voegen, zijn we er zeker van dat alleen segmenten van lengte 2 of meer de recursie in gaan.
Je wil de som over de gehele array, dus deze methode roep je aan met als ondergrens nul en als
bovengrens de lengte van je array: Som(0, n)
De toren van Hanoi
Van een recursief algoritme kan je de kosten niet rechtstreeks uitrekenen, want je hebt te maken met
stappen waarvan je de kosten nog niet kent. Het uitrekenen gaat altijd met een tussenstap; de recurrente
betrekking.
Recurrente betrekking: definieert de waarde van een functie in termen van de waarden voor kleinere
parameters
→ De oplossing van de recurrente betrekking geeft de waarde rechtstreeks
Datastructuren: Samenvatting deel 2 1
, Neem als voorbeeld het oplossen van de toren van Hanoi, dit kan gedaan worden met behulp van
recursie, en de pseudocode ziet er als volgt uit:
Hanoi(A, B, n)
{ if(n==1)
Zet(A, B);
else
{
Hanoi(A, C, n-1);
Zet(A, B);
Hanoi(B, C, n-1);
}
}
De recurrente betrekking die hierbij hoort is:
Z(n) = {
1 als n = 1
Z(n − 1) + 1 + Z(n − 1) als n > 1
Je ziet dat dit een functie is die zichzelf bevat, dit is dus lastig op te lossen. Soms kan je de oplossing
vinden door ‘raden-en-checken’; je maakt een tabel met n en Z(n) en kijkt of je een verband kan vinden.
Je stelt een hypothese op en gaat die bewijzen met inductie. Dit kan omdat we het hier over het aantal
stappen n hebben die nodig zijn om het probleem op te lossen. Wanneer we het over de tijd van een
bepaald algoritme hebben is het lastiger.
MergeSort
Het idee van MergeSort is als volgt; je hebt een array die je wil
sorteren, je splitst met behulp van recursie de array in in de kleinst
mogelijke elementen (in het geval hiernaast losse getallen), daarna ga
je stap voor stap weer die elementen bij elkaar plakken, waarbij je bij
elke plak actie checkt op de juiste volgorde van de elementen.
Het idee van MergeSort is hiernaast weergeven voor een array met
vier getallen. Het ‘ritsen’ van n keys kost lineaire tijd, omdat je
constante tijd per item gebruikt.
Datastructuren: Samenvatting deel 2 2
, De implementatie van MergeSort in C# ziet er als volgt uit:
static void MergeSort(int[] A, int p, int q)
{
if (q - p <= 1)
return;
int m = (p + q) / 2;
//Recursie
MergeSort(A, p, m);
MergeSort(A, m, q);
//Mergen van de sub-arrays
int i = p; int j = m; int k = 0;
int[] B = new int[q - p];
while (i < m || j < q)
{
if (j >= q || (i < m && A[i] <= A[j]))
{
B[k] = A[i]; i++;
}
else
{
B[k] = A[j]; j++;
}
k++;
}
for (k = 0; k < q - p; k++)
{
A[p + k] = B[k];
}
}
De recurrente betrekking die bij MergeSort hoort is als volgt:
M(n) = {
0 als n ≤ 1
2 ⋅ M(n/2) + Θ(n) als n > 1
Deze functie kan je alleen asymptotisch oplossen, niet exact. Dit vinden we niet erg, want wanneer we het
over tijd hebben, redeneren we toch al in ordegroottes, niet met exacte waardes.
Asymptotisch oplossen
Wanneer we globaal kijken naar een probleem, mogen we een paar dingen verwaarlozen:
De randvoorwaarde is onbelangrijk (hoe veel kost de base-case?)
Afronden bij delen is onbelangrijk → We splitsen altijd in tweeën, maar het maakt dus niet uit als
links iets groter of kleiner is dan rechts
De exacte waarde van extra termen (dwangtermen) is onbelangrijk
Wat wel belangrijk is, is hoe vaak je de recursie in gaat
Datastructuren: Samenvatting deel 2 3
, Substitutie methode
De substitutie methode is vergelijkbaar met de ‘raden-en-bewijzen’ methode die eerder besproken is. Je
gokt dat een recurrente betrekking een bepaalde ordegrootte als oplossing heeft, en gaat dat dan aan de
hand van inductie bewijzen. Hierbij zijn drie dingen waar je op miet letten:
Het bewijzen mag zonder basis-stap, want de randconditie is niet van belang
In je inductie stap mag je niet met O of Θ uitrekenen, je moet constanten expliciteren
In je inductie stap vind je een restrictie op de constante c (uit de definitie van O)
De substitutie bewijzen moet je kunnen volgen, maar je hoeft ze niet zelf te kunnen opstellen.
Master Theorem
De algemene vorm van een recurrente betrekking waarbij je a keer de recursie in gaat met steeds een
fractie 1/b van de originele input is:
T (n) = a ⋅ T (n/b) + f(n) (1)
Hierbij is f(n) de dwangterm. We willen voor deze vergelijking de algemene oplossing vinden. Hiervoor
willen we de volgende grootheid uitrekenen, en vergelijken met de dwangterm:
b
log(a)
n (2)
Wanneer we deze term met de dwangterm vergelijken, zijn er drie mogelijke uitkomsten:
b
log(a) b
log(a)
1. n > f(n) → T(n) is van ordegrootte Θ(n )
b b
log(a) log(a)
2. n = f(n) → T(n) is van ordegrootte Θ(n ⋅ lg(n))
b
log(a)
3. n < f(n) → T(n) is van ordegrootte Θ(f(n))
Wanneer f(n) een exponentiële term is, zal deze altijd domineren, want exponentieel wint van alles. Let op:
in geval 1 en 3 gaat het om polynomiaal groter of kleiner zijn, als de twee termen een fractie lg(n) van
elkaar verschillen ga je uit van punt twee, waarbij je nu de dwangterm vermenigvuldigd met lg(n).
Voorbeeld van oplossen met de Master Theorem
Neem de volgende recurrente betrekking:
V (n) = 4V (n/2) + O(n)
Hierbij wordt a gegeven door 2 en b door 4. Hiermee rekenen we met vergelijking 2 uit dat de macht van n
wordt gegeven door 2. De eerste term is dus kwadratisch en domineert dus over de dwangterm die lineair
is. V(n) is dus van ordegrootte O(n2 ).
Datastructuren: Samenvatting deel 2 4
Recursie en Master theorem
Recursieve methode: een methode die zichzelf aanroept
→ Handig voor het opsplitsen van een probleem, waarvan je niet weet hoe je die moet oplossen, in
kleinere problemen die je wel kan oplossen
Voorbeeld: Optellen
Je hebt een array van integers, waarvan je de som wil berekenen, maar je weet niet hoe je dit moet
aanpakken. Je weet echter wel dat de totaalsom gelijk is aan de som van de linker en rechter helft van de
array. Je gaat het probleem dus met recursie aanpakken:
static int Som(int[] A, int p, int q)
{
//Base-cases
if(q <= p) //Segment van lengte nul...
return 0; //... heeft als return waarde ook nul
if(q == p+1) //Segment met lente een...
return A[p]; //... heeft als return waarde dat element
//Recursie
int r = (p + q)/2;
int L = Som(A, p, r);
int R = Som(A, r, q);
return R+L;
}
Hier splitsen we de array steeds op in twee gelijke delen met grenzen p en q. Dan checken we eerst de
base-cases; is het een segment van lengte 0 of 1? Is dit niet het geval, dan gaan we verder de recursie in,
totdat we wel bij de base-case komen. Wanneer je helemaal onderaan bij de base-case bent, ga je stap
voor stap weer omhoog en tel je elke stap L op bij R. Zo krijg je uiteindelijk de som van de array.
Base-case: het kleinst mogelijke ‘probleem’ dat niet verder opgesplitst kan worden
We hebben hier twee base-cases, want met alleen de eerste base-case zouden we in een oneindige
recursie terecht komen. Want een segment van 1 element kan altijd opgesplitst worden in een segment
van 0 en 1. Het segment van 0 geeft correct 0 terug, maar het segment van 1 gaat oneindig vaak terug de
recursie in, wat een overflow veroorzaakt (wat natuurlijk resulteert in een crash). Door de tweede base-
case toe te voegen, zijn we er zeker van dat alleen segmenten van lengte 2 of meer de recursie in gaan.
Je wil de som over de gehele array, dus deze methode roep je aan met als ondergrens nul en als
bovengrens de lengte van je array: Som(0, n)
De toren van Hanoi
Van een recursief algoritme kan je de kosten niet rechtstreeks uitrekenen, want je hebt te maken met
stappen waarvan je de kosten nog niet kent. Het uitrekenen gaat altijd met een tussenstap; de recurrente
betrekking.
Recurrente betrekking: definieert de waarde van een functie in termen van de waarden voor kleinere
parameters
→ De oplossing van de recurrente betrekking geeft de waarde rechtstreeks
Datastructuren: Samenvatting deel 2 1
, Neem als voorbeeld het oplossen van de toren van Hanoi, dit kan gedaan worden met behulp van
recursie, en de pseudocode ziet er als volgt uit:
Hanoi(A, B, n)
{ if(n==1)
Zet(A, B);
else
{
Hanoi(A, C, n-1);
Zet(A, B);
Hanoi(B, C, n-1);
}
}
De recurrente betrekking die hierbij hoort is:
Z(n) = {
1 als n = 1
Z(n − 1) + 1 + Z(n − 1) als n > 1
Je ziet dat dit een functie is die zichzelf bevat, dit is dus lastig op te lossen. Soms kan je de oplossing
vinden door ‘raden-en-checken’; je maakt een tabel met n en Z(n) en kijkt of je een verband kan vinden.
Je stelt een hypothese op en gaat die bewijzen met inductie. Dit kan omdat we het hier over het aantal
stappen n hebben die nodig zijn om het probleem op te lossen. Wanneer we het over de tijd van een
bepaald algoritme hebben is het lastiger.
MergeSort
Het idee van MergeSort is als volgt; je hebt een array die je wil
sorteren, je splitst met behulp van recursie de array in in de kleinst
mogelijke elementen (in het geval hiernaast losse getallen), daarna ga
je stap voor stap weer die elementen bij elkaar plakken, waarbij je bij
elke plak actie checkt op de juiste volgorde van de elementen.
Het idee van MergeSort is hiernaast weergeven voor een array met
vier getallen. Het ‘ritsen’ van n keys kost lineaire tijd, omdat je
constante tijd per item gebruikt.
Datastructuren: Samenvatting deel 2 2
, De implementatie van MergeSort in C# ziet er als volgt uit:
static void MergeSort(int[] A, int p, int q)
{
if (q - p <= 1)
return;
int m = (p + q) / 2;
//Recursie
MergeSort(A, p, m);
MergeSort(A, m, q);
//Mergen van de sub-arrays
int i = p; int j = m; int k = 0;
int[] B = new int[q - p];
while (i < m || j < q)
{
if (j >= q || (i < m && A[i] <= A[j]))
{
B[k] = A[i]; i++;
}
else
{
B[k] = A[j]; j++;
}
k++;
}
for (k = 0; k < q - p; k++)
{
A[p + k] = B[k];
}
}
De recurrente betrekking die bij MergeSort hoort is als volgt:
M(n) = {
0 als n ≤ 1
2 ⋅ M(n/2) + Θ(n) als n > 1
Deze functie kan je alleen asymptotisch oplossen, niet exact. Dit vinden we niet erg, want wanneer we het
over tijd hebben, redeneren we toch al in ordegroottes, niet met exacte waardes.
Asymptotisch oplossen
Wanneer we globaal kijken naar een probleem, mogen we een paar dingen verwaarlozen:
De randvoorwaarde is onbelangrijk (hoe veel kost de base-case?)
Afronden bij delen is onbelangrijk → We splitsen altijd in tweeën, maar het maakt dus niet uit als
links iets groter of kleiner is dan rechts
De exacte waarde van extra termen (dwangtermen) is onbelangrijk
Wat wel belangrijk is, is hoe vaak je de recursie in gaat
Datastructuren: Samenvatting deel 2 3
, Substitutie methode
De substitutie methode is vergelijkbaar met de ‘raden-en-bewijzen’ methode die eerder besproken is. Je
gokt dat een recurrente betrekking een bepaalde ordegrootte als oplossing heeft, en gaat dat dan aan de
hand van inductie bewijzen. Hierbij zijn drie dingen waar je op miet letten:
Het bewijzen mag zonder basis-stap, want de randconditie is niet van belang
In je inductie stap mag je niet met O of Θ uitrekenen, je moet constanten expliciteren
In je inductie stap vind je een restrictie op de constante c (uit de definitie van O)
De substitutie bewijzen moet je kunnen volgen, maar je hoeft ze niet zelf te kunnen opstellen.
Master Theorem
De algemene vorm van een recurrente betrekking waarbij je a keer de recursie in gaat met steeds een
fractie 1/b van de originele input is:
T (n) = a ⋅ T (n/b) + f(n) (1)
Hierbij is f(n) de dwangterm. We willen voor deze vergelijking de algemene oplossing vinden. Hiervoor
willen we de volgende grootheid uitrekenen, en vergelijken met de dwangterm:
b
log(a)
n (2)
Wanneer we deze term met de dwangterm vergelijken, zijn er drie mogelijke uitkomsten:
b
log(a) b
log(a)
1. n > f(n) → T(n) is van ordegrootte Θ(n )
b b
log(a) log(a)
2. n = f(n) → T(n) is van ordegrootte Θ(n ⋅ lg(n))
b
log(a)
3. n < f(n) → T(n) is van ordegrootte Θ(f(n))
Wanneer f(n) een exponentiële term is, zal deze altijd domineren, want exponentieel wint van alles. Let op:
in geval 1 en 3 gaat het om polynomiaal groter of kleiner zijn, als de twee termen een fractie lg(n) van
elkaar verschillen ga je uit van punt twee, waarbij je nu de dwangterm vermenigvuldigd met lg(n).
Voorbeeld van oplossen met de Master Theorem
Neem de volgende recurrente betrekking:
V (n) = 4V (n/2) + O(n)
Hierbij wordt a gegeven door 2 en b door 4. Hiermee rekenen we met vergelijking 2 uit dat de macht van n
wordt gegeven door 2. De eerste term is dus kwadratisch en domineert dus over de dwangterm die lineair
is. V(n) is dus van ordegrootte O(n2 ).
Datastructuren: Samenvatting deel 2 4
