IAD1 samenvatting
Inhoudsopgave
Week 1....................................................................................................................................................2
1.2 Big O.............................................................................................................................................2
1.4 Big O code logaritmisch................................................................................................................3
1.5 big O code recursief......................................................................................................................3
1.6 Sorteren........................................................................................................................................4
1.7 Selection sort................................................................................................................................5
Week 2....................................................................................................................................................6
2.1 Quicksort......................................................................................................................................6
2.2 Quicksort voorbeeld.....................................................................................................................7
2.3 Heapsort.......................................................................................................................................7
2.4 Heapsort voorbeeld......................................................................................................................8
Week 3....................................................................................................................................................9
3.1 Hash Table....................................................................................................................................9
3.2 Hashfunctie.................................................................................................................................11
Week 4..................................................................................................................................................12
4.1 Boom & binaire zoekboom.........................................................................................................12
4.2 AVL boom....................................................................................................................................13
4.3 AVL Rotaties................................................................................................................................14
4.4 AVL voorbeeld.............................................................................................................................14
Week 5..................................................................................................................................................15
5.1 Graaf...........................................................................................................................................15
5.2 Graaf programmeren..................................................................................................................16
5.3 Zoeken in een graaf.....................................................................................................................17
5.4 DFS voorbeeld.............................................................................................................................18
5.5 BFS voorbeeld.............................................................................................................................18
5.6 Dijkstra........................................................................................................................................19
5.7 Dijkstra voorbeeld.......................................................................................................................19
Week 6..................................................................................................................................................20
6.1 compressie-algoritmen...............................................................................................................20
6.2 compressie Huffman...................................................................................................................21
6.3 Compressie LZW (Lempel-Ziv-Welch)..........................................................................................23
,Week 1
1.2 Big O
Big-O notatie: Een manier om over de performance van een algoritme te praten.
Het gaat dan over de worst-case complexiteit (in ruimte of tijd)
De complexiteit bepaald je door te kijken hoeveel stapjes de code doet.
Je neemt voor de Big-O notatie de grootste n
Figuur 1: Doorlooptijd voor algoritme, n = 100
, 1.4 Big O code logaritmisch
Kwadratisch = O(N^2) -> 2 for-loops
Kubisch = O(N^3) -> 3 for-loops
Logaritmisch -> deel elke keer je stappen/elementen door 2
Bijv. binair zoeken
1.5 big O code recursief
Lineair -> 1 for-loop
Recursive: je functie roept zichzelf opnieuw aan
Exponentieel -> (2^n) – duurt veel langer dan lineair
Inhoudsopgave
Week 1....................................................................................................................................................2
1.2 Big O.............................................................................................................................................2
1.4 Big O code logaritmisch................................................................................................................3
1.5 big O code recursief......................................................................................................................3
1.6 Sorteren........................................................................................................................................4
1.7 Selection sort................................................................................................................................5
Week 2....................................................................................................................................................6
2.1 Quicksort......................................................................................................................................6
2.2 Quicksort voorbeeld.....................................................................................................................7
2.3 Heapsort.......................................................................................................................................7
2.4 Heapsort voorbeeld......................................................................................................................8
Week 3....................................................................................................................................................9
3.1 Hash Table....................................................................................................................................9
3.2 Hashfunctie.................................................................................................................................11
Week 4..................................................................................................................................................12
4.1 Boom & binaire zoekboom.........................................................................................................12
4.2 AVL boom....................................................................................................................................13
4.3 AVL Rotaties................................................................................................................................14
4.4 AVL voorbeeld.............................................................................................................................14
Week 5..................................................................................................................................................15
5.1 Graaf...........................................................................................................................................15
5.2 Graaf programmeren..................................................................................................................16
5.3 Zoeken in een graaf.....................................................................................................................17
5.4 DFS voorbeeld.............................................................................................................................18
5.5 BFS voorbeeld.............................................................................................................................18
5.6 Dijkstra........................................................................................................................................19
5.7 Dijkstra voorbeeld.......................................................................................................................19
Week 6..................................................................................................................................................20
6.1 compressie-algoritmen...............................................................................................................20
6.2 compressie Huffman...................................................................................................................21
6.3 Compressie LZW (Lempel-Ziv-Welch)..........................................................................................23
,Week 1
1.2 Big O
Big-O notatie: Een manier om over de performance van een algoritme te praten.
Het gaat dan over de worst-case complexiteit (in ruimte of tijd)
De complexiteit bepaald je door te kijken hoeveel stapjes de code doet.
Je neemt voor de Big-O notatie de grootste n
Figuur 1: Doorlooptijd voor algoritme, n = 100
, 1.4 Big O code logaritmisch
Kwadratisch = O(N^2) -> 2 for-loops
Kubisch = O(N^3) -> 3 for-loops
Logaritmisch -> deel elke keer je stappen/elementen door 2
Bijv. binair zoeken
1.5 big O code recursief
Lineair -> 1 for-loop
Recursive: je functie roept zichzelf opnieuw aan
Exponentieel -> (2^n) – duurt veel langer dan lineair
