46

Datastructuren Analyse van algoritmen

José Lagerberg FNWI, UvA

Jos´ e Lagerberg (FNWI, UvA)

Datastructuren

1 / 46

Datastructuren en Algoritmen

Datastructuren, 6 ECTS eerstejaars Bachelor INF Datastructuren, 6 ECTS tweedejaars Bachelor KI 1

Organisatie

2

Practicum

3

Inhoud college

4

Analyse van algoritmen

5

ArrayList


Datastructuren

2 / 46

Organisatie

college

- theorie van datastructuren

college

- C voor Informatica

practicum

Java voor KI

practicum

C voor Informatica

Afsluiting 1

Tentamen in 8ste week (moet voldoende zijn, dus 5.6 of hoger)

2

Practicum (moet voldoende zijn, dus 5.6 of hoger)


Datastructuren

3 / 46

Inhoud datastructuren

1 2

Analyse van Algoritmen Basis Datastructuren I I I I

3

Stacks en Queues Lijsten Hash tabellen Priority queues en heaps

Zoekbomen I I I I

Binaire zoekbomen B-bomen AVL bomen, rood-zwart bomen Splay bomen


Datastructuren

4 / 46

Leerdoelen

Leerdoelen studenten kunnen operaties op datastructuren en algoritmen classificeren met behulp van de Big-Oh notatie


Datastructuren

5 / 46

Inhoud vandaag

1

Analyse van algoritmen I

2

Big-Oh notatie I

3

Gebruik Big-Oh notatie om algoritme en operaties op datastructuren te karakteriseren

Sorteeralgoritmen I

4

bestuderen van efficiency van algoritme als input grootte verandert, gebaseerd op aantal stappen, computertijd en geheugengebruik

Bepaal Big-Oh van aantal sorteeralgoritmen

ArrayList is datastructuur toegankelijk met index I

Wat is probleem van ArrayList?


Datastructuren

6 / 46

Datastructuur

Datastructuur = Systematische manier om gegevens op te slaan, te wijzigen, en terug te kunnen vinden. Voorbeelden: stapel, wachtrij, lijst, boom


Datastructuren

7 / 46

Algoritme

Algoritme = eindige rij instructies om een doel te bereiken


Datastructuren

8 / 46

Worst case, best case, average case

Voor probleem van grootte n: Worst case: langste looptijd voor alle mogelijke invoer ter grootte n - bepaal de maximum looptijd van algoritme Best case: kortste looptijd voor alle mogelijke invoer ter grootte n - bepaal de minimum looptijd van algoritme Average case: gemiddelde looptijd voor alle mogelijke invoer ter grootte n - bepaal de gemiddelde looptijd van algoritme


Datastructuren

9 / 46

Voorbeeld van 3 cases

Gegeven ongesorteerde rij van n getallen tussen 1 en 100. Probleem: zoek getal 10 Worst case: doorloop hele rij en vindt getal 10 op laatste plek, of helemaal niet Best case: vindt getal 10 op eerste plek van rij Average case: doorloop helft van rij tot getal 10 gevonden


Datastructuren

10 / 46

Running time (looptijd) als functie van grootte input

Een algoritme vergt inspanning: tijd, ruimte, (=tijds- of ruimtecomplexiteit) De inspanning neemt toe met de omvang van de input Average-case complexiteit is vaak moeilijk te bepalen We richten ons op de worst case complexiteit


Datastructuren

11 / 46

Experimentele Analyse door implementatie/benchmarking Benchmarking: Implementeer je algoritme, test je implementatie uit op input van verschillende grootte en samenstelling, meet de looptijd in seconden en geheugengebruik in bytes teken een grafiek met andere compiler en andere computer heel ander resultaat mogelijk Nadelen Vereist implementatie, slechts steekproeven, resultaat is hardware- en software-afhankelijk.


Datastructuren

12 / 46

Wiskundige (Asymptotische) Analyse

Hoe kunnen we looptijd T (n) van algoritme bepalen uit definitie van algoritme? bepalen van aantal statements in algoritme looptijd T (n) bepalen als functie van invoergrootte n analyse geldt voor willekeurige input, looptijd is onafhankelijk van hardware en software. Asymptotische analyse 1

Groei van T (n) bekijken als n → ∞

2

Bepalen van worst case complexiteit van algoritme


Datastructuren

13 / 46

Asymptotische complexiteit

Stel dat een algoritme 8n + 5 stappen nodig heeft voor input van grootte n Wat is de betekenis van de 8 en de +5? Als n groot wordt, heeft de +5 geen betekenis meer De 8 is niet nauwkeurig als verschillende operaties verschillende hoeveelheid tijd kosten Fundamenteel is dat de tijd lineair is in n Asymptotische complexiteit: als n groot wordt, vergeet dan alle termen van lagere orde, en beschouw alleen term met hoogste orde


Datastructuren

14 / 46

Complexiteit van algoritme, aantal stappen tellen? Analyse van algoritme voor berekenen van integer exponent s t a t i c i n t exp ( i n t a , i n t n ) { i n t ans = 1 ; w h i l e ( n > 0 ) { // w h i l e l o o p n k e e r u i t g e v o e r d a n s ∗= a ; n −= 1 ; } return ans ; }

Hoeveel stappen T (n) gebruikt door methode? aantal stappen T (n) = 2 + 3 ∗ n n 100 200 400

T(n) 302 602 1202

Als n verdubbelt, dan verdubbelt looptijd Jos´ e Lagerberg (FNWI, UvA)

Datastructuren

15 / 46

c la s s Voorbeeld1 { p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { i n t [ ] a = {1 , 4 , 7 , 10 , 3 , 4 , 2 , 9}; int index = search (a , 2); System . o u t . p r i n t l n ( ” i n d e x i s ” + i n d e x ) ; } /∗ z o e k n a a r e e n waarde i n e e n a r r a y ∗/ static int search ( int [ ] x , int target ) { f o r ( i n t i = 0 ; i < x . l e n g t h ; i ++) { i f ( x [ i ] == t a r g e t ) return i ; } r e t u r n −1; } }

worst case Als target niet aanwezig loop x.length = n keer uitgevoerd average case Als target wel aanwezig loop gemiddeld n/2 keer uitgevoerd best case Meteen eerste keer raak Jos´ e Lagerberg (FNWI, UvA)

Datastructuren

16 / 46

c la s s Voorbeeld2 { p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { i n t [ ] a = {1 , 4 , 7 , 10 , 3 , 4 , 2 , 9}; i n t [ ] b = {3 , 9 , 8 , 2 , 5 , 6}; System . o u t . p r i n t l n ( areTheSame ( a , b ) ) ; } /∗ b e p a a l o f twee a r r a y s e e n z e l f d e e l e m e n t b e v a t t e n ∗/ s t a t i c b o o l e a n areTheSame ( i n t [ ] x , i n t [ ] y ) { f o r ( i n t i = 0 ; i < x . l e n g t h ; i ++) { i f ( s e a r c h ( y , x [ i ] ) != −1) // e l e m e n t g e v o n d e n return true ; } return f a l s e ; } }

Loop in areTheSame x.length = n keer uitgevoerd Loop binnen search y.length = m keer uitgevoerd Totale executie-tijd evenredig met n * m


Datastructuren

17 / 46

c la s s Voorbeeld3 { p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s ) { i n t [ ] a = {1 , 4 , 7 , 10 , 3 , 4 , 2 , 9}; System . o u t . p r i n t l n ( a r e U n i q u e ( a ) ) ; } /∗ b e p a a l o f a r r a y u n i e k e e l e m e n t e n b e v a t ∗/ s t a t i c boolean areUnique ( i n t [ ] x ) { f o r ( i n t i = 0 ; i < x . l e n g t h ; i ++) { f o r ( i n t j = 0 ; j < x . l e n g t h ; j ++) { i f ( i != j && x [ i ] == x [ j ] ) // n i e t u n i e k return f a l s e ; } } return true ; } }

worst case is als elementen uniek zijn i-for loop x.length = n keer, j-for loop x.length = n keer If-statement n2 keer uitgevoerd Jos´ e Lagerberg (FNWI, UvA)

Datastructuren

18 / 46

c la s s Voorbeeld4 { /∗ b e p a a l o f a r r a y u n i e k e e l e m e n t e n b e v a t t e n ∗/ s t a t i c boolean areUnique ( i n t [ ] x ) { f o r ( i n t i = 0 ; i < x . l e n g t h ; i ++) { f o r ( i n t j = i + 1 ; j < x . l e n g t h ; j ++) { i f ( x [ i ] == x [ j ] ) return f a l s e ; } } return true ; } }

worst case is als elementen uniek zijn eerste keer j-for loop x.length - 1 = n - 1 keer tweede keer j-for loop x.length - 2 = n - 2 keer laatste keer j-for loop 1 keer aantal keren if-statement n × (n − 1) (n − 1) + (n − 2) + . . . + 2 + 1 = = 0.5n2 − 0.5n 2 Jos´ e Lagerberg (FNWI, UvA)

Datastructuren

19 / 46

Gebruik van Big-Oh (Asymptotische notatie) Wat is relatie tussen grootte van input en looptijd van algoritme? 1

als looptijd verdubbelt bij verdubbeling van n, dan algoritme van orde n (lineair)

2

als looptijd verviervoudigt bij verdubbeling van n, dan algoritme van orde n2 (kwadratisch)

1

eerste algoritme van orde O(n)

2

tweede algoritme van orde O(n2 )

Deze Big-Oh notatie gebruikt om algoritmen te classificeren: hoe reageren algoritmen op verandering van grootte van input? Bepaling van Big-Oh van algoritme: bekijk loops en of ze genest zijn bekijk hoe vaak een loop wordt doorlopen


Datastructuren

20 / 46

Executietijd T (n) f o r ( i n t i = 0 ; i < n ; i ++) { f o r ( i n t j = 0 ; j < n ; j ++) { statement } } f o r ( i n t i = 0 ; i < n ; i ++) { statement 1 statement 2 statement 3 } statement 4 statement 5

Neem aan statement gebruikt één tijdseenheid en for-loops kosten niets Executietijd T (n) als functie van n is T (n) = n2 + 3n + 2 T (n) = O(n2 ) Jos´ e Lagerberg (FNWI, UvA)

Datastructuren

21 / 46

Definitie van Big-Oh

Definitie Zij f , g : N → R. We zeggen “f (n) is O(g (n))” als er c ∈ R en n0 ∈ N bestaan met c > 0 en n0 ≥ 1 zo dat f (n) ≤ c × g (n) voor n ≥ n0


Datastructuren

22 / 46

Big-Oh Definitie Zij f , g : N → R. We zeggen “f (n) is O(g (n))” als er c ∈ R en n0 ∈ N bestaan met c > 0 en n0 ≥ 1 zo dat f (n) ≤ c × g (n) voor n ≥ n0

Voorbeeld 2n + 10 is O(n) 2n + 10 ≤ cn (c − 2)n ≥ 10 n ≥ 10/(c − 2) Neem c = 3 en n0 = 10 2n + 10 ≤ 3 × n Jos´ e Lagerberg (FNWI, UvA)

voor n ≥ 10 Datastructuren

23 / 46

Big-Oh Voorbeeld

Voorbeeld n2 is NIET O(n) n2 ≤ cn n≤c Onmogelijk. . . c is constante


Datastructuren

24 / 46

Meer Big-Oh Voorbeelden

Voorbeeld (7n − 2) 7n − 2 is O(n). We hebben c > 0 en n0 ≥ 1 nodig met 7n − 2 ≤ cn

voor n ≥ n0 .

Neem c = 7, n0 = 1. 7n − 2 ≤ 7n


voor n ≥ 1

Datastructuren

25 / 46

Big-Oh voorbeeld

Voorbeeld (3n3 + 20n2 + 5) 3n3 + 20n2 + 5 is O(n3 ). We hebben c > 0 en n0 ≥ 1 nodig met 3n3 + 20n2 + 5 ≤ cn3

voor n ≥ n0 .

Neem c = 4 en n0 = 21. 3n3 + 20n2 + 5 ≤ 4n3


voor n ≥ 21.

Datastructuren

26 / 46

Big-Oh voorbeeld Voorbeeld (3 log n + 5) 3 log n + 5 is O(log n). We hebben c > 0 en n0 ≥ 1 nodig met 3 log n + 5 ≤ c log n

voor n ≥ n0 .

Je kunt nemen c = 4 en dan is n0 = 32. (log 25 = 5 ≤ log n) Of je kunt nemen c = 5 en dan is n0 = 7. (log 25/2 = 5/2 ≤ log n). 3 log n + 5 ≤ 4 log n

voor n ≥ 32.

3 log n + 5 ≤ 5 log n

voor n ≥ 7.


Datastructuren

27 / 46

Big-Oh begrenst de groei van boven De uitspraak “f (n) is O(g (n))” betekent dat het groeitempo van f (n) niet groter is dan dat van g (n).

Big-Oh Regels ak nk + ak−1 nk−1 + · · · a1 n + a0 is O(nk ): laat constanten en kleine orde-termen weg! Zeg “2n is O(n)” i.p.v. “2n is O(n2 )” (minimale) “3n + 5 is O(n)” i.p.v. “3n + 5 is O(3n)”.


Datastructuren

28 / 46

Meest voorkomende groeitempo’s O(1) O(log(n)) O(n) O(n log(n)) O(n2 ) O(n3 ) O(2n )

constant logaritmisch lineair log-lineair kwadratisch derdemachts exponentieel

O O(1) O(log(n)) O(n) O(n log(n)) O(n2 ) O(n3 ) O(2n )

bepalen of getal even of oneven binair zoeken in gesorteerd array zoeken van item in ongesorteerd array FFT, heap sort, merge sort bubble-, insertion-, selection sort traveling salesman problem

T(50) 1 5.64 50 282 2500 12500 1.126 × 1015

T(100) 1 6.64 100 664 10000 100000 1.27 × 1030

T(100)/T(50) 1 1.18 2 2.35 4 8 1.126 × 1093

Table: uit Datastructures van Koffman en Wolfgang Jos´ e Lagerberg (FNWI, UvA)

Datastructuren

29 / 46


Datastructuren

30 / 46

Opgaven Opgave 1 Hoe vaak worden de statements in de binnenste loop uitgevoerd? Wat is de orde van dit programmaonderdeel? for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ... } }

Oplossing aantal keren is n ∗ n = n2 orde O(n2 )


Datastructuren

31 / 46

Opgaven Opgave 2 Hoe vaak worden de statements in de binnenste loop uitgevoerd? Wat is de orde van dit programmaonderdeel? for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { ... } }

Oplossing aantal keren is ((n − 1) + (n − 2) + · · · + (1)) = orde O(n2 )


Datastructuren

n(n−1) 2

= 0.5n2 − 0.5n

32 / 46

Opgaven Opgave 3 Hoe vaak worden de statements in de loop uitgevoerd? Wat is de orde van dit programmaonderdeel? for (int i = 1; i < n; i *= 2) { ... }

Oplossing Loop wordt uitgevoerd voor de volgende waarden van i: 1, 2, 4, 8, 16, 32, . . . , 2k−1 met 2k ≥ n 2k−1 ≤ n ≤ 2k → k − 1 ≤ log n ≤ k orde O(log n)


Datastructuren

33 / 46

Opmerking Big-Oh notatie drukt een relatie tussen functies uit Het zegt niet wat de functies zijn! Functie links hoeft niet de worst-case running time te zijn

Voorbeeld Binair zoeken in gesorteerd array van grootte n We zullen later zien dat: worst-case running time is O(log n) best-case running time is O(1) gemiddelde running time is O(log n/2) = O(log n) geheugengebruik is O(n)


Datastructuren

34 / 46

De buren van Big-Oh

ondergrens f (n) is Ω(g (n)) ⇔ ∃c > 0, ∃n0 ≥ 1, ∀n ≥ n0 : f (n) ≥ c × g (n) bovengrens ´ en ondergrens f (n) is Θ(g (n)) ⇔ ∃c’, c” > 0, ∃n0 ≥ 1, ∀n ≥ n0 : c’ × g (n) ≤ f (n) ≤ c” × g (n) dwz. f (n) is O(g (n)) en Ω(g (n))


Datastructuren

35 / 46

Sorteeralgoritmen

Fundamenteel probleem van informatica: sorteren lijst Bubble-Sort O(n2 ) Selection-Sort O(n2 ) Insertion-Sort O(n2 ) Merge-Sort O(n log n) Quick-Sort O(n log n)


Datastructuren

36 / 46

Vergelijking O(n2 ) sorteeralgoritmen


Datastructuren

37 / 46

Vergelijking O(n log n) sorteeralgoritmen


Datastructuren

38 / 46

ArrayList is datastructuur met index Toegang elementen in willekeurige volgorde met index lengte array is vast toevoeging add(int index, E e) op bepaalde plek schuift andere elementen op (van orde O(n)) weghalen remove(int index) op bepaalde plek schuift andere elementen terug (van orde O(n)) als ArrayList vol, moet nieuw groter array gealloceerd worden en oude data hierin gecopieerd worden de add(E e) operatie voegt element toe aan einde lijst (van orde O(1))

wat kost deze add(E e) operatie gemiddeld? (volgende week)

I n d o c u m e n t a t i e van A r r a y L i s t The add o p e r a t i o n r u n s i n a m o r t i z e d c o n s t a n t time , t h a t i s , a d d i n g n e l e m e n t s r e q u i r e s O( n ) t i m e .


Datastructuren

39 / 46

Toevoegen aan en weghalen uit ArrayList A r r a y L i s t <S t r i n g > l i s t = new A r r a y L i s t <S t r i n g > ( ) ; l i s t . add ( ” J a n s e n ” ) ; l i s t . add ( ” P i e t e r s e n ” ) ; l i s t . add ( ” D i r k s e n ” ) ; l i s t . add ( ” A r e n d s ” ) ; System . o u t . p r i n t l n ( l i s t ) ; l i s t . add ( 2 , ” W i l l e m s ” ) ; System . o u t . p r i n t l n ( l i s t ) ; l i s t . add ( ” B u r g e r ” ) ; System . o u t . p r i n t l n ( l i s t ) ; l i s t . remove ( 0 ) ; System . o u t . p r i n t l n ( l i s t ) ;

[ Jansen , P i e t e r s e n , [ Jansen , P i e t e r s e n , [ Jansen , P i e t e r s e n , [ P i e t e r s e n , Willems


Dirksen , Willems , Willems , , Dirksen

Arends ] Dirksen , Arends ] D i r k s e n , Arends , B u r g e r ] , Arends , B u r g e r ]

Datastructuren

40 / 46

Reallocatie van List

abstract

SimpleList / /

/ / / SimpleListDoubling r e s i z e ()


<−−−−−−−−−−>

IList \ add ( ) \ size () \ clear () \ abstract r e s i z e () \ SimpleListFixed r e s i z e ()

Datastructuren

41 / 46

Reallocatie van List public interface I L i s t { p u b l i c v o i d add ( O b j e c t x ) ; public int size (); public void c l e a r ( ) ; } p u b l i c a b s t r a c t c l a s s S i m p l e L i s t implements I L i s t { p r i v a t e s t a t i c f i n a l i n t INIT SIZE = 10; O b j e c t [ ] myCon ; int mySize ; public SimpleList (){ myCon = new O b j e c t [ I N I T S I Z E ] ; mySize = 0 ; } ... }


Datastructuren

42 / 46

Voorbeeld van eigen SimpleList methoden p u b l i c v o i d add ( O b j e c t x ) { i f ( s i z e ( ) == myCon . l e n g t h ) resize (); myCon [ mySize ] = x ; mySize++; } abstract void r e s i z e ( ) ; public int size () { r e t u r n mySize ; } public void c l e a r () { myCon = new O b j e c t [ 1 0 ] ; mySize = 0 ; }


Datastructuren

43 / 46

Fixed of Doubling p u b l i c c l a s s S i m p l e L i s t F i x e d extends S i m p l e L i s t { void r e s i z e (){ O b j e c t [ ] temp = new O b j e c t [ s i z e ( ) + 1 0 0 0 ] ; System . a r r a y c o p y ( myCon , 0 , temp , 0 , s i z e ( ) ) ; myCon = temp ; } } p u b l i c c l a s s S i m p l e L i s t D o u b l i n g extends S i m p l e L i s t { void r e s i z e (){ O b j e c t [ ] temp = new O b j e c t [ s i z e ( ) ∗ 2 ] ; System . a r r a y c o p y ( myCon , 0 , temp , 0 , s i z e ( ) ) ; myCon = temp ; } }


Datastructuren

44 / 46

Fixed of Doubling A r r a y L i s t l i s t s = new A r r a y L i s t ( ) ; l i s t s . add ( new S i m p l e L i s t D o u b l i n g ( ) ) ; l i s t s . add ( new S i m p l e L i s t F i x e d ( ) ) ; for ( I L i s t l i s t : l i s t s ) { System . o u t . p r i n t l n ( l i s t . g e t C l a s s ( ) . getSimpleName ( ) ) ; testList ( l i s t ); } s t a t i c void t e s t L i s t ( I L i s t l i s t ) { f o r ( i n t i = 1 0 0 0 ; i < 2 5 0 0 0 0 ; i ∗= 2 ) { l o n g s t a r t = System . c u r r e n t T i m e M i l l i s ( ) ; f o r ( i n t j = 0 ; j < i ; j ++) l i s t . add ( j ) ; l o n g s t o p = System . c u r r e n t T i m e M i l l i s ( ) ; show ( ” Time t o add ” + i + ” e l e m e n t s ” + ( stop − s t a r t ) + ” m i l l i s e c o n d s . ” ) ; l i s t . clear (); } }


Datastructuren

45 / 46

java -Xint ListTester

% j a v a −X i n t L i s t T e s t e r SimpleListDoubling Time t o add 1000 e l e m e n t s 1 m i l l i s e c o n d s . Time t o add 2000 e l e m e n t s 1 m i l l i s e c o n d s . Time t o add 4000 e l e m e n t s 1 m i l l i s e c o n d s . Time t o add 8000 e l e m e n t s 3 m i l l i s e c o n d s . Time t o add 16000 e l e m e n t s 5 m i l l i s e c o n d s . Time t o add 32000 e l e m e n t s 10 m i l l i s e c o n d s . Time t o add 64000 e l e m e n t s 21 m i l l i s e c o n d s . Time t o add 128000 e l e m e n t s 44 m i l l i s e c o n d s . SimpleListFixed Time t o add 1000 e l e m e n t s 0 m i l l i s e c o n d s . Time t o add 2000 e l e m e n t s 0 m i l l i s e c o n d s . Time t o add 4000 e l e m e n t s 2 m i l l i s e c o n d s . Time t o add 8000 e l e m e n t s 2 m i l l i s e c o n d s . Time t o add 16000 e l e m e n t s 5 m i l l i s e c o n d s . Time t o add 32000 e l e m e n t s 16 m i l l i s e c o n d s . Time t o add 64000 e l e m e n t s 36 m i l l i s e c o n d s . Time t o add 128000 e l e m e n t s 117 m i l l i s e c o n d s .


Datastructuren

46 / 46

46

Recommend Documents