12 september 2012 Complexiteit. Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen

12 september 2012

Complexiteit

Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie

Complexiteit van Algoritmen Ferd van Odenhoven Fontys Hogeschool voor Techniek en Logistiek Venlo Software Engineering

12 september 2012

ODE/FHTBM

Complexiteit van Algoritmen


12 september 2012

1/41

Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen

Analyse van algoritmen (doelen) Efficientie-analyse voor fundamentele algoritmen Reden waarom we (wiskundige) analyse van algoritmen doen Vergelijken van verschillende algoritmen voor dezelfde taak Voorspellen van hun efficientie onafhankelijk van de omgeving Bepalen van de waarde van de parameters van een algoritme

Wiskundige formules zijn bekend die gebruikt kunnen worden om de looptijd van in een praktische situatie te kunnen voorspellen. We onderscheiden twee strategieën voor de efficientiebeschouwing

empirische analyse complexiteitsklassen

ODE/FHTBM



12 september 2012

2/41


Eigenschappen van Algoritmen - Algoritme-analyse Hoe bekijken we de eigenschappen van algoritmen? Controleer operaties op data Controleer input data

Hoe bepalen we de efficientie van algoritmen? We gebruiken de volgende methoden voor bestaande implementaties Implementatie en empirische analyse

Analyse van algoritmen vóór de implementatie Groei van functies om de complexiteitsklassen te beschrijven Groot-Oh Notatie and O-Notatie

Garanties, voorspellingen en beperkingen

ODE/FHTBM


12 september 2012

3/41

1

12 september 2012

Complexiteit



Implementaie en empirische analyse Algoritmen voor berekeningen worden ontworpen als we operaties op datastrukturen bekijken, of (data-)strukturen kiezen, waarvan we weten dat bepaalde operaties snel uitgevoerd kunnen worden Om een correcte implementatie te vinden, bijv. in Java, moeten we bovenstaande zaken afwisselend beschouwen en tegen elkaar afwegen. Het kan vaak voorkomen dat men start met een bestaande implementatie (uit de Java bibliotheek) We kunnen leren van een bestaande implementatie.

ODE/FHTBM



12 september 2012

4/41


Empirische analyse We beginnen met een bestaande implementatie. Wat kan door empirische analyse worden gevonden? Wat levert ons een beschouwing van de werkelijke looptijd op? Neem aan dat twee algoritmen gegeven zijn om hetzelfde probleem op te lossen. We ’runnen’ ze allebei om te zien welke de meeste tijd nodig heeft! Het ene algoritme is 10 keer sneller dan het andere en dat is snel opgemerkt als we de looptijden: 3 en 30 seconden respectievelijk, gemeten hebben; Klopt zo’n test voor alle mogelijke invoer van beide algoritmen? Voorbeeld: Sommatie van een eindige getallenrij

ODE/FHTBM



12 september 2012

5/41


Empirische analyse : Voorbeeld Som van een eindige reeks (niet in het boek) public int Ga ussian SumSim ple ( int n ) { int sum =0; for ( int i = n ; n > 0; i - -) { sum = sum + i ; } return sum ; } Voor N = 30 worden bij doorlopen van de lus 30 optellingen uitgevoerd. Voor N = 300 worden bij doorlopen van de lus 300 optellingen uitgevoerd, oftewel 10 maal zoveel. Net zoveel als de groei van N.

ODE/FHTBM


12 september 2012

6/41

2

12 september 2012

Complexiteit



Empirische analyse : Voorbeeld (2) Sommatie van een eindige getallenrij (niet in het boek) tweede implementatie public int GaussianSum ( int n ) { int sum = 0.5* n *( n +1); return sum ; } Voor een vast aantal bijv. N = 30: N = 30 ⇒ sum = 0.5 ∗ 30 ∗ (30 + 1) = 1860 Een opteliing en twee vermenigvuldigingen zijn nodig. Als N = 300 ⇒ sum = 0.5 ∗ 300 ∗ (300 + 1) = 45150 Een opteliing en twee vermenigvuldigingen zijn nodig. Aantal benodigde operaties is onafhankelijk van de waarde van N. ODE/FHTBM



12 september 2012

7/41


Samenvatting sommatie voorbeeld Sommatie van een eindige getallenrij In de eerste implementatie is er een relatie tussen de kosten en de grootte van de invoer, d.w.z. de kosten groeien rechtevenredig met N. De kosten groeien lineair. In de tweede implemetatie is de berekeningsmethode onafhankelijk van de grootte van de invoer N. We zeggen dat de kosten constant zijn. Blijkbaar kan de looptijd afhangen van de input. Het is niet altijd mogelijk deze afhankelijkheid uit te sluiten, maar het wel een poging waard. Bedenk wat er kan gebeuren als N vast is.

ODE/FHTBM



12 september 2012

8/41


Empirische analyse Empirisch onderzoek kost veel tijd. Merk op dat we voor zo’n onderzoek de algoritmen eerst moeten implementeren, pas dan is een vergelijking mogelijk. Het kan voorkomen dat we heeeeel lang moeten wachten voordat we resultaten verkrijgen.

Bestuderen van input data Drie verschillende keuzes Actuele data Random data Perverse data

ODE/FHTBM


12 september 2012

9/41

3

12 september 2012

Complexiteit



Empirische analyse Actuele data laat ons de looptijd meten van een bepaald programma (in zijn softwaresysteem). Random data verzekert ons ervan dat we met onze experimenten ook echt de algoritmen testen en niet de input data. Perverse data verzekert ons ervan dat ons programma elke input die het aangeboden krijgt aan kan.

ODE/FHTBM



12 september 2012

10/41


Kritiek op de empirische analyse Diverse factoren liggen buiten de invloedsfeer van de programmeur, zoals: Programmeeromgevingen, zoals voor Java of .NET Java-programma’s worden vertaald in bytecode, en bytecode wordt ge¨ınterpreteerd of vertaald naar ’runtime code’ op een virtual machine (VM). De compiler en VM implementaties be¨ınvloeden allemaal de instructies die feitelijk op de computer worden uitgevoerd. Compiler options geven enige mogelijkheid om het proces te be¨ınvloeden.

Input data Veel programma’s zijn extreem gevoelig voor input data, en de prestatie kan behoorlijk fluctueren afhankelijk van de input.

Programma’s (of implementaties) zijn niet goed te begrijpen. ODE/FHTBM



12 september 2012

11/41


Empirische analyse (gevolgen) We kunnen geen experimenten doen met een programma dat nog niet geschreven is en dat uitgevoerd wordt met grote hoeveelheid input data, maar we kunnen wel de eigenschappen analyseren en de potentiële effectiviteit schatten. We kunnen parameters in onze implementatie toevoegen en deze in de analyse gebruiken. Doel: door begrip van de fundamentele eigenschappen van onze programma’s en het gebruik van de programma bronnen, kunnen we deze beoordelen, zelfs voor computers die nog niet gemaakt zijn, en met algoritmen vergelijken die nog niet ontworpen zijn.

ODE/FHTBM


12 september 2012

12/41

4

12 september 2012

Complexiteit


Groei van Functies De functies

Analyse van Algoritmen Hoe analyseren we algoritmen? Tijdens de analyse van een algoritme moeten we de operaties identificeren. Het aantal operaties kan groot zijn, in principe zal de prestatie van een algoritme enkel afhangen van weinig grootheden, die eenvoudig te identificeren zijn; bijv. door toepassing van een ’profiling mechanisme’ (tellen van aantallen instructies).

ODE/FHTBM



12 september 2012

13/41


Analyse van Algoritmen ’Worst-case’ analyse kan gedaan worden middels bepalen van de time complexity (bovengrens afhankelijk van de gekozen invoerparameter N) of space complexity (bovengrens afhankelijk van geheugengebruik). NB: resultaten van ‘time complexity’ kunnen omgezet worden naar die van ‘space complexity’ en de resultaten van ‘space complexity’ kunnen omgezet worden naar die van ‘time complexity’.

Deze complexiteit resultaten kunnen aangegeven worden door groei van functies m.b.v. ‘Big-Oh’ notatie.

ODE/FHTBM



12 september 2012

14/41


Eigenschappen van algoritmen Correctheid Invarianten van lussen Invarianten van methoden

Bepalen van efficiënte algoritmen Ruimte complexiteit Tijd complexiteit Kostenberekeningen Best case, worst case, average case

ODE/FHTBM


12 september 2012

15/41

5

12 september 2012

Complexiteit



Groei van functies Enn wiskundige functie wordt gebruikt om de complexiteit van een algoritme aan te geven. Veel algoritmen hebben een hoofdparameter N die de meeste invloed heeft op de looptijd. De parameter N kan onder meer zijn: de graad van een polynoom, de afmeting van een bestand dat gesorteerd of doorzocht moet worden, het aantal karakters in een tekststring een of andere maat voor de ameting van het probleem onder beschouwing.

Vaak is N direct evenredig aan de afmeting van de dataverzameling die bewerkt wordt. ´ en parameter N is in het algemeen genoeg, een tweede E´ parameter kan in N worden uitgedrukt. ODE/FHTBM



12 september 2012

16/41


Groei van functies Ons doel is om de de vraag naar resources (tijd of ruimte) in termen van N uit te drukken, met gebruik van wiskundige formules die nauwkeuriger zijn naarmate de parameters groter worden, (gericht op problemen m.b.t. implementatie en massa’s input data) De algoritmen bezitten typische tijd complexiteit evenredig aan de functies op de volgende slide. Merk op dat we hiermee een klassificatie voor alle algoritmen kunnen maken.

ODE/FHTBM



12 september 2012

17/41


// return number of distinct triples (i , j , k ) // such that a [ i ] + a [ j ] + a [ k ] = 0 public static int count ( int [] a ) { int N = a . length ; int cnt = 0; for ( int i = 0; i < N ; i ++) { for ( int j = i +1; j < N ; j ++) { for ( int k = j +1; k < N ; k ++) { if ( a [ i ] + a [ j ] + a [ k ] == 0) { cnt ++; } } } } return cnt ; }

ODE/FHTBM


// N = N ^1 // ( N ^2)/2 // { N ^3}/6

12 september 2012

18/41

6

12 september 2012

Complexiteit



De functies

Figuur: De functies : 1, log (x), x, x · log (x), x 2 , x 3 , .. ODE/FHTBM



12 september 2012

19/41


Groei van functies : 1 Kostante looptijd De meeste programma-instructies worden een of hoogstens enkele malen uitgevoerd. Als alle instructies in een programma deze eigenschap hebben, zeggen we dat de looptijd van het programma constant is. Bijv.: een verdubbeling van de invoerlengte heeft nauwelijks invloed op de looptijd.

ODE/FHTBM



12 september 2012

20/41


Groei van functies : logN Logaritmische looptijd Als de looptijd van een programma logaritmisch is, groeit het net iets langzamer dan N. Deze looptijd komt gewoonlijk voor in programma’s die een groot probleem oplossen door omzetting in een aantal kleinere problemen, die de probleemomvang in elke stap met een bepaalde factor verkleinen. Bijv.: een verdubbeling van de invoerlengte voegt een constante hoeveelheid tijd toe aan de looptijd. Voor ons doel kunnen we aannemen dat de looptijd kleiner is dan een grote constante. Het grondtal van de logaritme be¨ınvloedt de constante een beetje.

ODE/FHTBM


12 september 2012

21/41

7

12 september 2012

Complexiteit



Groei van functies : N Lineaire looptijd De looptijd van een programma is linear, als er een kleine hoeveelheid bewerkingen op elk input element wordt uitgevoerd. Deze situatie is optimaal voor een algoritme dat N invoerwaarden moet bewerken (of N uitvoerwaarden produceren).

ODE/FHTBM



12 september 2012

22/41


Groei van functies : NlogN NlogN looptijd Een Nlog (N) looptijd komt voor bij algoritmen die een probleem oplossen door het op te delen in kleinere deelproblemen, die onafhankelijk van elkaar opgelost worden, en waarvan de resultaten dan gecombineerd worden. Als N verdubbelt, groeit de looptijd meer (maar niet veel meer) dan een verdubbeling.

ODE/FHTBM



12 september 2012

23/41


Groei van functies : N 2 en N 3 N 2 Als de looptijd van een algoritme kwadratisch is, dan is dat algoritme alleen van praktische waarde voor relatief kleine problemen. Kwadratische looptijden komen typisch voor in algoritmen welke alle data-items in parenverwerkt worden (bijvoorbeeld in een dubbel-geneste lus). N 3 Een algoritme dat data-item-triplets bewerkt (bijvoorbeeld in een drievoudig-geneste lus) heeft een kubieke looptijd. Als N verdubbelt, zal de looptijd met een factor acht toenemen!

ODE/FHTBM


12 september 2012

24/41

8

12 september 2012

Complexiteit


Groei van functies :


2N

Weinig algoritmen met een exponentiële looptijd zijn van praktisch nut, zelfs als deze algoritmen het resultaat zijn van een ’brute-force’ aanpak. Als N verdubbelt, zal de looptijd kwadrateren! 2(2∗N) = (2N )2

ODE/FHTBM


12 september 2012


25/41


Waarden van voorkomende functies lgN 3 7 10 13 17

√

N 3 10 32 100 316

ODE/FHTBM

N 10 100 1000 104 105

NlgN 33 664 9966 132877 1.66106

N(lgN)2 110 4414 99317 176533 27.6106



N 3/2 32 1000 31623 105 31.6106

N2 100 10000 105 106 1010

12 september 2012

26/41


Groei van functies : Speciale functies Funktion

Beschrijving

Voorbeeld

bxc dxe lgN FN HN N! lg (N!)

Bodemfunktie Plafondfunktie Binaire Logaritme Fibonacci Getallen Harmonische Getallen (som) Fakulteit-funktie

b3.14c = 3 d3.14e = 4 lg (1024) = 10 F10 = 55

ODE/FHTBM


10! = 3628800 lg (10!) ≈ 520

Benadering voor grote waarden x x 1.44ln(N) √ φN / 5 ln(N) + γ (N/e)N Nlg (N) − 1.44N

12 september 2012

27/41

9

12 september 2012

Complexiteit



Groei van functies : Speciale constanten Constant e γ φ ln(2) lg(e)

ODE/FHTBM

= = = = =

Value 2.71828. . . 0.57721. . . √ (1 + 5)/2 = 1.61803 . . . 0.69347. . . 1/ln(2) = 1.44269. . .



12 september 2012

28/41

Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit

Groot Oh-Notatie Wat motivatie van te voren Groot O-Notatie gebruiken we om de efficiëntie van algoritmes te beschrijven In de meeste gevallen bepaalt de implementatie van de (wiskundige) operaties op een datastructuur de efficiëntie van algoritmen. Van de andere kant be¨ınvloedt de onderliggende datastructuur de efficiëntie ook. Dit betekent dat als we beslissen om de datastructuur te veranderen de algoritmen ’sneller’ kunnen worden. Wat betekent hier ’snel’ of ’langzaam’ ?

ODE/FHTBM



12 september 2012

29/41


Groot O-notatie van f(N) De fout te beperken die we maken als we ’kleine termen’ verwaarlozen in formules De fout te beperken die we maken als we programma-delen weglaten die maar een kleine bijdrage leveren aan het totale programma Bieden van de mogelijkheid om algoritmen in te delen volgens een bovengrens aan de totale looptijd ’snel’ en ’langzaam’ is bepaald en wordt weergegeven door de O-notation: O(f (N)) - “groot O van f (N)” De O-notatie geeft een ’is evenredig aan’ relatie weer. Zoals gezegd: het onderzoek naar de invoerdata is een asymptotische benadering van de ’worst case’ situatie.

ODE/FHTBM


12 september 2012

30/41

10

12 september 2012

Complexiteit



Groei van functies: gedrag voor grote N f (N)

f (N) = N 2

f (N) = Nlog (N)

N ODE/FHTBM



12 september 2012

31/41


Groot O-Notatie: O(f (N)) ”Groot O van f (N)” O(f (N)) - “Groot O van f (N)” Ruwweg: De verzameling functies die als N toeneemt, niet sneller groeit dan een constante maal f (N), waarin N (de maat of lengte van) de input (data) is. Precies: De verzameling functies g (N) : N → R, als voor elke g (N), er constanten bestaan: c0 ∈ R+ en N0 ∈ N zodanig dat g (N) ≤ c0 f (N) voor alle N > N0 Valkuil: We prefereren een algoritme met N 2 nanoseconden ten opzichte van een met log (N) eeuwen, maar we kunnen deze keuze niet bepalen op grond van de O-notatie.

ODE/FHTBM



12 september 2012

32/41


Voorbeelden - Hoe de O-notatie te gebruiken In wezen kunnen we uitdrukkingen O-notatie uitwerken alsof de O er helemaal niet is, dan verwijderen we alles behalve de grootste term. Bijvoorbeeld, als we de uitdrukking uitwerken: (O(N) + O(1))(O(N) + O(logN) + O(1)) krijgen we zes termen: O(N 2 ) + O(NlogN) + O(N) + O(N) + O(logN) + O(1)

ODE/FHTBM


12 september 2012

33/41

11

12 september 2012

Complexiteit



Voorbeelden - Hoe de O-notatie te gebruiken We verwijderen alle lagere O-termen, en houden de benadering: O(N 2 ) + O(NlogN). O(N 2 ) is benadert de uitdrukking goed voor grote N. We noemen een uitdrukking met een O-term een asymptotische uitdrukking.

ODE/FHTBM



12 september 2012

34/41


Voorbeelden - Hoe de O-notatie te gebruiken g (N) = 3N 3 + 10N + 1000logN ∈ O(N 3 ) houdt ook in dat: g (N) = 3N 3 + 10N + 1000logN ∈ O(N 4 )

ODE/FHTBM

( 5N, N ≤ 10120 g (n) = N 2 , N > 10120

∈ O(N 2 )

( N 2 , N ≤ 10120 g (n) = 5N, N > 10120

∈ O(N)



12 september 2012

35/41


Zeef van Eratosthenes class Primes { public static void main ( String [] args ) { int N = integer . parseInt ( args [0]); boolean [] a = new boolean [ N ]; for ( int i = 2; i < N ; i ++) a [ i ] = true ; for ( int i = 2; i < N ; i ++) if ( a [ i ] != false ) for ( int j = i , i * j < N ; j ++) a [ i * j ] = false ; for ( int i = 2; i < N ; i ++ ) if ( i > N - 100 ) if ( a [ i ]) System . out . println ( " " + i ); System . out . println (); } } ODE/FHTBM


12 september 2012

36/41

12

12 september 2012

Complexiteit



Zeef van Eratosthenes - Complexiteit De implementatie heeft vier lussen, waarvan er drie de items van het array sequentieel doorlopen, van begin tot eind. Sequentiële processing is essentieel. We zouden de eerste lus kunnen veranderen, bijv.: for(i = N-1; i > 1; i--) a[i] = true; Deze verandering heeft geen enkel effect! Analyseer de looptijd, die is evenredig aan: N + N/2 + N/3 + N/5 + N/7 + N/11 + ... hetgeen kleiner is dan: N + N/2 + N/3 + N/4 + ... De eerste N termen van deze reeks: N·(1 + 1/2 + 1/3 + 1/4 + ... + 1/N) = N · HN = O(N · logN) HN : harmonic numbers sum ODE/FHTBM



12 september 2012

37/41


Samenvatting - Complexiteit We hebben twee methoden bestudeerd voor de analyse van algoritmen Empirische analyse Complexiteitsklassen

ODE/FHTBM



12 september 2012

38/41


Samenvatting - Empirische analyse Er moet een implementatie aanwezig zijn. We hebben (veel) data nodig. De meting van de looptijd kan worden beinvloed door het softwareysteem. Stapsgewijze, mogelijk zeer kostbare verbeteringen door kennis van randvoorwaarden van een speciale toepassing. Zulke randvoorwaarden kunnen in speciale gevallen leiden tot snelle oplossingen.

ODE/FHTBM


12 september 2012

39/41

13

12 september 2012

Complexiteit



Samenvatting - Complexiteit. In de ontwerpfase van een algoritme Focus op invoerdata indien nodig beperkt tot een mogelijke invoerparameter en de ’langzame’ programmadelen

Afschatting van de wezenlijke invoerparameter door looptijdcomplexiteit of geheugencomplexiteit

Vind een komplexiteitsklasse, waartoe het algoritme behoort. De complexiteit van een algoritme wordt gegeven door de kleinste bovengrens bij ’worst-case’ invoerdata. De kleinste bovengrens wordt uitgedrukt door de groei van een wiskundige functie.

ODE/FHTBM



12 september 2012

40/41


Samenvatting - Complexiteit. Elk geimplementeerd programma heeft een looptijd. De complexiteitsanalyse levert met de kleinste bovengrens de snelste looptijd in ’worst-case’ (of benodigde geheugenruimte) van elk algoritme met betrekking tot wiskundige operaties. We verkrijgen kennis met de complexiteitsanalyse over de beste oplossing, die tegelijkertijd een absolute grens vormt. De programmalooptijd van een implementatie hoeft niet overeen te komen met de looptijd, die door de complexiteitsklasse wordt beschreven. We willen in deze kursus de algoritmen leren voor de meest toegepaste operaties welke de beste algoritmen zijn.

ODE/FHTBM


12 september 2012

41/41

14

12 september 2012 Complexiteit. Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen

Recommend Documents