Datastructuren
Binary Search 1
Sorting 1
Analyse 4
Sommaties 5
Recursie 6
Asymptotisch oplossen 6
Master Theorem 7
Binomiaalcoëfficiënt 8
Kansrekening 9
Verwachting 10
Abstracte Datastructuren 13
Stack 13
Queue 13
(Min)Heap 14
HashTabellen 15
Zoekbomen 16
Hash lengte 18
Fibonacci 19
Log en Sin 19
Notes 21
,Binary Search
Array organisatie
- Ongesorteerde array
- Toevoegen van elementen kan in constante tijd
- Zoeken van elementen kan in lineaire tijd, O(n)
- Gesorteerde array
- Toevoegen van elementen tijdrovend
- Zoeken kan heel snel met behulp van binary search in O(log(n))
Invariant Predikaat over je variabelen en data, waarvoor je zorgt dat die true is vóór en na
elke slag van de loop
Variant Predikaat dat er op een gegeven moment voor zorgt dat de loop terminated wordt
Sorting
Insertion Sort
- Begint vooraan in input en elk element wordt op de juiste positie gezet door alles
beneden de positie (links ervan) van het betreffende element naar rechts op te schuiven
zolang het groter dan of gelijk aan de waarde van het element is
- Invariant: A[0 .. i] is gesorteerd (en bestaat uit dezelfde keys als input)
- Binary search helpt om het aantal vergelijkingen te reduceren, maar het aantal
elementen dat je moet opschuiven blijft gelijk
- 2 keer zoveel keys betekent 4 keer zoveel tijd, want je moet niet alleen 2 keer meer
keys invoegen, maar het duurt ook 2 keer zo lang, dus O(n2)
- Insertion Sort kan worden gebruikt bij weinig elementen of bij presorted keys, als de lijst
al ongeveer op de goede volgorde staat, bijvoorbeeld door random waarschijnlijkheid
- Kan in O(n) tijd als de rang van A[i] tussen i - x en i + x (als x < n) zonder iets aan te
passen, elk element hoeft hoogstens x plekken opgeschoven te worden
Selection Sort
- Begin vooraan in output en zet op plek A[i] de kleinste waarde uit A[i .. n]
- Invariant: A[0 .. i] is gesorteerd (en bestaat uit de i kleinste keys)
- Profiteert niet van gunstige input volgorde, altijd O(n2)
- Slechts O(n) data verplaatsingen, wat wel gunstig kan zijn
- Kan in O(n) tijd als de rang van A[i] tussen i - x en i + x ligt (als x < n) door alleen maar
te zoeken in de eerste x elementen van het ongesorteerde deel
QuickSort
- Pak een random key als pivot en vergelijk de rest met de pivot om twee groepen te
vormen (Partition/Split) die nu apart van elkaar gesorteerd kunnen worden, omdat het
eerste blok altijd <= pivot en tweede blok >= pivot
- Kan ongunstig uitpakken met random key, dus bijvoorbeeld 3 random keys en daarvan
de middelste gebruiken
- Kan als pivot ook eerste, achterste of middelste element pakken, maar succes
hiervan is afhankelijk van de input volgorde
- Parameters: array om te sorteren en gebied daarbinnen om te sorteren
1
, - Eerste plek en lengte: QS(A, 4, 4)
- Eerste plek en laatste: QS(A, 4, 7)
- Eerste en eerste niet-meetellende: QS(A, 4, 8) (aantal elementen is 8 - 4)
- Invariant voor Split methode:
- p <= i < r : A[i] <= pivot
- i = r : A[i] = pivot
- s < i < q : A[i] > pivot
- Omvang van onbekende stuk is (s - r), dus variant
- Snelheid
- Bij weinig keys is insertion sort sneller, dus in de QS methode kun je daar een
check voor toevoegen
- Hoe vaak doet een bepaalde key mee met een split?
- Een Split i is snel als de omvang van het block ¾ van het vorige blok is
en anders langzaam
- X doet hoogstens mee in 4/3log n snelle splits
- Elke split heft kans >= ½ om snel te zijn (vier kwartielen)
- Per key verwachten we 4/3log n / ½ = 4,8 lg n nodig
- In totaal dus n・4,8・lg n = O(n・lg n)
Bernoulli: het verwachte aantal pogingen tot het Se succes bij slaagkans p is S / p
- 10 lampen nodig, 50% kans om uit de bak een goede lamp te pakken, dan is de
verwachting .5 = 20 pogingen tot je 10 goede lampen hebt
In situ/In-place Een algoritme is in situ als het de array sorteert zonder extra tijdelijk
geheugenruimte nodig te hebben om de data op te slaan
- Zoals Selection, Insertion, BubbleSort, ShellSort, QuickSort en HeapSort
- Maar niet Counting Sort, BucketSort en MergeSort
Counting sort
- Aanname: keys komen uit (kleine) verzameling van M elementen
- Extra geheugen nodig om counters bij te houden
- Totale tijd: O(n) voor het tellen, O(M) voor de cumulatief en O(n) voor het omstapelen,
dus O(n + M), want je weet niet welke van n of M de grootste is
- Stabiele sorteermethode, maar extra array nodig
Radix sort
- Aanname: elke key bestaat uit een vast aantal stukjes, waarop een lexicografische
ordening bestaat
- Sorteert in fases, waarbij elke fase op één van de stukjes (dag/maand/eeuw/jaar)
sorteert, beginnend bij het minst-significante stukje (dag)
- In combinatie met Counting Sort
Bucket sort
- Aanname: keys zijn uniform verdeeld over een bekend interval
2
Binary Search 1
Sorting 1
Analyse 4
Sommaties 5
Recursie 6
Asymptotisch oplossen 6
Master Theorem 7
Binomiaalcoëfficiënt 8
Kansrekening 9
Verwachting 10
Abstracte Datastructuren 13
Stack 13
Queue 13
(Min)Heap 14
HashTabellen 15
Zoekbomen 16
Hash lengte 18
Fibonacci 19
Log en Sin 19
Notes 21
,Binary Search
Array organisatie
- Ongesorteerde array
- Toevoegen van elementen kan in constante tijd
- Zoeken van elementen kan in lineaire tijd, O(n)
- Gesorteerde array
- Toevoegen van elementen tijdrovend
- Zoeken kan heel snel met behulp van binary search in O(log(n))
Invariant Predikaat over je variabelen en data, waarvoor je zorgt dat die true is vóór en na
elke slag van de loop
Variant Predikaat dat er op een gegeven moment voor zorgt dat de loop terminated wordt
Sorting
Insertion Sort
- Begint vooraan in input en elk element wordt op de juiste positie gezet door alles
beneden de positie (links ervan) van het betreffende element naar rechts op te schuiven
zolang het groter dan of gelijk aan de waarde van het element is
- Invariant: A[0 .. i] is gesorteerd (en bestaat uit dezelfde keys als input)
- Binary search helpt om het aantal vergelijkingen te reduceren, maar het aantal
elementen dat je moet opschuiven blijft gelijk
- 2 keer zoveel keys betekent 4 keer zoveel tijd, want je moet niet alleen 2 keer meer
keys invoegen, maar het duurt ook 2 keer zo lang, dus O(n2)
- Insertion Sort kan worden gebruikt bij weinig elementen of bij presorted keys, als de lijst
al ongeveer op de goede volgorde staat, bijvoorbeeld door random waarschijnlijkheid
- Kan in O(n) tijd als de rang van A[i] tussen i - x en i + x (als x < n) zonder iets aan te
passen, elk element hoeft hoogstens x plekken opgeschoven te worden
Selection Sort
- Begin vooraan in output en zet op plek A[i] de kleinste waarde uit A[i .. n]
- Invariant: A[0 .. i] is gesorteerd (en bestaat uit de i kleinste keys)
- Profiteert niet van gunstige input volgorde, altijd O(n2)
- Slechts O(n) data verplaatsingen, wat wel gunstig kan zijn
- Kan in O(n) tijd als de rang van A[i] tussen i - x en i + x ligt (als x < n) door alleen maar
te zoeken in de eerste x elementen van het ongesorteerde deel
QuickSort
- Pak een random key als pivot en vergelijk de rest met de pivot om twee groepen te
vormen (Partition/Split) die nu apart van elkaar gesorteerd kunnen worden, omdat het
eerste blok altijd <= pivot en tweede blok >= pivot
- Kan ongunstig uitpakken met random key, dus bijvoorbeeld 3 random keys en daarvan
de middelste gebruiken
- Kan als pivot ook eerste, achterste of middelste element pakken, maar succes
hiervan is afhankelijk van de input volgorde
- Parameters: array om te sorteren en gebied daarbinnen om te sorteren
1
, - Eerste plek en lengte: QS(A, 4, 4)
- Eerste plek en laatste: QS(A, 4, 7)
- Eerste en eerste niet-meetellende: QS(A, 4, 8) (aantal elementen is 8 - 4)
- Invariant voor Split methode:
- p <= i < r : A[i] <= pivot
- i = r : A[i] = pivot
- s < i < q : A[i] > pivot
- Omvang van onbekende stuk is (s - r), dus variant
- Snelheid
- Bij weinig keys is insertion sort sneller, dus in de QS methode kun je daar een
check voor toevoegen
- Hoe vaak doet een bepaalde key mee met een split?
- Een Split i is snel als de omvang van het block ¾ van het vorige blok is
en anders langzaam
- X doet hoogstens mee in 4/3log n snelle splits
- Elke split heft kans >= ½ om snel te zijn (vier kwartielen)
- Per key verwachten we 4/3log n / ½ = 4,8 lg n nodig
- In totaal dus n・4,8・lg n = O(n・lg n)
Bernoulli: het verwachte aantal pogingen tot het Se succes bij slaagkans p is S / p
- 10 lampen nodig, 50% kans om uit de bak een goede lamp te pakken, dan is de
verwachting .5 = 20 pogingen tot je 10 goede lampen hebt
In situ/In-place Een algoritme is in situ als het de array sorteert zonder extra tijdelijk
geheugenruimte nodig te hebben om de data op te slaan
- Zoals Selection, Insertion, BubbleSort, ShellSort, QuickSort en HeapSort
- Maar niet Counting Sort, BucketSort en MergeSort
Counting sort
- Aanname: keys komen uit (kleine) verzameling van M elementen
- Extra geheugen nodig om counters bij te houden
- Totale tijd: O(n) voor het tellen, O(M) voor de cumulatief en O(n) voor het omstapelen,
dus O(n + M), want je weet niet welke van n of M de grootste is
- Stabiele sorteermethode, maar extra array nodig
Radix sort
- Aanname: elke key bestaat uit een vast aantal stukjes, waarop een lexicografische
ordening bestaat
- Sorteert in fases, waarbij elke fase op één van de stukjes (dag/maand/eeuw/jaar)
sorteert, beginnend bij het minst-significante stukje (dag)
- In combinatie met Counting Sort
Bucket sort
- Aanname: keys zijn uniform verdeeld over een bekend interval
2
