Samenvatting Datastructuren
Jos Perdeck
Inhoudsopgave
Algoritme Analyse ................................................................................................................................................... 3
Tijdcomplexiteit..................................................................................................................................................... 3
Groei: Dominante termen ..................................................................................................................................... 4
Best, worst en avarage case analyse..................................................................................................................... 4
Geheugencomplexiteit ........................................................................................................................................... 5
Handige links ........................................................................................................................................................ 5
Collections ................................................................................................................................................................ 7
Datastructuren ...................................................................................................................................................... 7
List: Array ............................................................................................................................................................. 8
List: LinkedList ..................................................................................................................................................... 8
List: Stack............................................................................................................................................................ 10
Queue .................................................................................................................................................................. 11
Priority Queue .................................................................................................................................................... 11
Reguliere expressies (REGEX) ............................................................................................................................. 12
Basis van reguliere expressies ............................................................................................................................ 12
Voorbeelden: ....................................................................................................................................................... 13
Spitsen van invoer ............................................................................................................................................... 15
Zoeken en vervangen in invoer ........................................................................................................................... 16
Recursie .................................................................................................................................................................. 18
Wat is een recursief algoritme? .......................................................................................................................... 18
(Non-)Efficientie van recursie............................................................................................................................. 18
Sorteer Algoritmen ................................................................................................................................................ 18
BubbleSort........................................................................................................................................................... 19
SelectionSort ....................................................................................................................................................... 19
InsertionSort ....................................................................................................................................................... 19
MergeSort ........................................................................................................................................................... 19
QuickSort ............................................................................................................................................................ 20
Overzicht sorteeralgoritmen ............................................................................................................................... 20
Hashing ................................................................................................................................................................... 20
Collisions & load factor...................................................................................................................................... 21
Gesloten hashing: linear probing ....................................................................................................................... 21
Gesloten hashing: quadratic probing ................................................................................................................. 21
Overflow chaining ............................................................................................................................................... 21
Randomisatie.......................................................................................................................................................... 21
,Inleiding randomisatie ........................................................................................................................................ 21
Linear congruential generator ............................................................................................................................ 22
2
, Algoritme Analyse
Tijdcomplexiteit
• Kijken naar de uitvoeringstijd
• Kijken naar de hoeveelheid ruimte die nodig is
Wat beïnvloedt de looptijd?
• Gebruikte hardware (CPU en randapparatuur)
• Kwaliteit van de code
• Gebruikte programmeertaal
• Vaardigheid van degene die het algoritme implementeert
Inputgrootte = aantal gegevens dat verwerkt moet worden
Hoe groter de dataset hoe meer tijd er nodig is om deze te sorteren
Basisbewerkingen nemen 1 tijdseenheid in beslag
• Waardetoekenningen • Vermenigvuldiging
• Delen etc.
Gezien de inputgrootte de belangrijkste factor is wordt de uitvoeringstijd als T(n) genoteerd
public double Pythagoras(double a, double b)
{
double hypothenusa = Math.sqrt( a * a + b * b); return hypothenusa; }
Voor dit algoritme is er een constante tijd nodig.
Input: positief geheel getal n
Output: waarde van de som van alle derde machten van i=1 tot n
1: s <-- 0
2: for i from 1 to n do
3: s <-- s + i3
4: return s
Regel 1 & 4: beide basisbewerkingen dus ieder 1 tijdseenheid
Regel 3: kost 3 tijdseenheden dus 3n
Regel 2: initialisatie van i kost 1 eenheid, vervolgens test of i kleiner dan n en dan ophogen van i kost
in totaal 2n+1 tijdeenheden
Totaal: T(n)=5n+3
Het is dus een lineaire functie en deze wordt genoteerd als O(n).
3
Jos Perdeck
Inhoudsopgave
Algoritme Analyse ................................................................................................................................................... 3
Tijdcomplexiteit..................................................................................................................................................... 3
Groei: Dominante termen ..................................................................................................................................... 4
Best, worst en avarage case analyse..................................................................................................................... 4
Geheugencomplexiteit ........................................................................................................................................... 5
Handige links ........................................................................................................................................................ 5
Collections ................................................................................................................................................................ 7
Datastructuren ...................................................................................................................................................... 7
List: Array ............................................................................................................................................................. 8
List: LinkedList ..................................................................................................................................................... 8
List: Stack............................................................................................................................................................ 10
Queue .................................................................................................................................................................. 11
Priority Queue .................................................................................................................................................... 11
Reguliere expressies (REGEX) ............................................................................................................................. 12
Basis van reguliere expressies ............................................................................................................................ 12
Voorbeelden: ....................................................................................................................................................... 13
Spitsen van invoer ............................................................................................................................................... 15
Zoeken en vervangen in invoer ........................................................................................................................... 16
Recursie .................................................................................................................................................................. 18
Wat is een recursief algoritme? .......................................................................................................................... 18
(Non-)Efficientie van recursie............................................................................................................................. 18
Sorteer Algoritmen ................................................................................................................................................ 18
BubbleSort........................................................................................................................................................... 19
SelectionSort ....................................................................................................................................................... 19
InsertionSort ....................................................................................................................................................... 19
MergeSort ........................................................................................................................................................... 19
QuickSort ............................................................................................................................................................ 20
Overzicht sorteeralgoritmen ............................................................................................................................... 20
Hashing ................................................................................................................................................................... 20
Collisions & load factor...................................................................................................................................... 21
Gesloten hashing: linear probing ....................................................................................................................... 21
Gesloten hashing: quadratic probing ................................................................................................................. 21
Overflow chaining ............................................................................................................................................... 21
Randomisatie.......................................................................................................................................................... 21
,Inleiding randomisatie ........................................................................................................................................ 21
Linear congruential generator ............................................................................................................................ 22
2
, Algoritme Analyse
Tijdcomplexiteit
• Kijken naar de uitvoeringstijd
• Kijken naar de hoeveelheid ruimte die nodig is
Wat beïnvloedt de looptijd?
• Gebruikte hardware (CPU en randapparatuur)
• Kwaliteit van de code
• Gebruikte programmeertaal
• Vaardigheid van degene die het algoritme implementeert
Inputgrootte = aantal gegevens dat verwerkt moet worden
Hoe groter de dataset hoe meer tijd er nodig is om deze te sorteren
Basisbewerkingen nemen 1 tijdseenheid in beslag
• Waardetoekenningen • Vermenigvuldiging
• Delen etc.
Gezien de inputgrootte de belangrijkste factor is wordt de uitvoeringstijd als T(n) genoteerd
public double Pythagoras(double a, double b)
{
double hypothenusa = Math.sqrt( a * a + b * b); return hypothenusa; }
Voor dit algoritme is er een constante tijd nodig.
Input: positief geheel getal n
Output: waarde van de som van alle derde machten van i=1 tot n
1: s <-- 0
2: for i from 1 to n do
3: s <-- s + i3
4: return s
Regel 1 & 4: beide basisbewerkingen dus ieder 1 tijdseenheid
Regel 3: kost 3 tijdseenheden dus 3n
Regel 2: initialisatie van i kost 1 eenheid, vervolgens test of i kleiner dan n en dan ophogen van i kost
in totaal 2n+1 tijdeenheden
Totaal: T(n)=5n+3
Het is dus een lineaire functie en deze wordt genoteerd als O(n).
3
