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
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
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¨en voor de efficientiebeschouwing
empirische analyse complexiteitsklassen
ODE/FHTBM
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
2/41
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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´o´or de implementatie Groei van functies om de complexiteitsklassen te beschrijven Groot-Oh Notatie and O-Notatie
Garanties, voorspellingen en beperkingen
ODE/FHTBM
Complexiteit van Algoritmen
12 september 2012
3/41
1
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
4/41
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
5/41
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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
Complexiteit van Algoritmen
12 september 2012
6/41
2
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
7/41
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
8/41
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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
Complexiteit van Algoritmen
12 september 2012
9/41
3
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
10/41
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
11/41
Analyse van algoritmen (doelen) Empirische analyse : Voorbeeld Gevolgen
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¨ele 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
Complexiteit van Algoritmen
12 september 2012
12/41
4
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
13/41
Groei van Functies De functies
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
14/41
Groei van Functies De functies
Eigenschappen van algoritmen Correctheid Invarianten van lussen Invarianten van methoden
Bepalen van effici¨ente algoritmen Ruimte complexiteit Tijd complexiteit Kostenberekeningen Best case, worst case, average case
ODE/FHTBM
Complexiteit van Algoritmen
12 september 2012
15/41
5
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groei van Functies De functies
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
16/41
Groei van Functies De functies
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
17/41
Groei van Functies De functies
// 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
Complexiteit van Algoritmen
// N = N ^1 // ( N ^2)/2 // { N ^3}/6
12 september 2012
18/41
6
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groei van Functies De functies
De functies
Figuur: De functies : 1, log (x), x, x · log (x), x 2 , x 3 , .. ODE/FHTBM
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
19/41
Groei van Functies De functies
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
20/41
Groei van Functies De functies
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
Complexiteit van Algoritmen
12 september 2012
21/41
7
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groei van Functies De functies
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
22/41
Groei van Functies De functies
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
23/41
Groei van Functies De functies
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
Complexiteit van Algoritmen
12 september 2012
24/41
8
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groei van functies :
Groei van Functies De functies
2N
Weinig algoritmen met een exponenti¨ele 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
Complexiteit van Algoritmen
12 september 2012
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
25/41
Groei van Functies De functies
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
N 3/2 32 1000 31623 105 31.6106
N2 100 10000 105 106 1010
12 september 2012
26/41
Groei van Functies De functies
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
Complexiteit van Algoritmen
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
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groei van Functies De functies
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. . .
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
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¨entie van algoritmes te beschrijven In de meeste gevallen bepaalt de implementatie van de (wiskundige) operaties op een datastructuur de effici¨entie van algoritmen. Van de andere kant be¨ınvloedt de onderliggende datastructuur de effici¨entie 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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
29/41
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
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
Complexiteit van Algoritmen
12 september 2012
30/41
10
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
Groei van functies: gedrag voor grote N f (N)
f (N) = N 2
f (N) = Nlog (N)
N ODE/FHTBM
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
31/41
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
32/41
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
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
Complexiteit van Algoritmen
12 september 2012
33/41
11
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - 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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
34/41
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
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)
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
35/41
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
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
Complexiteit van Algoritmen
12 september 2012
36/41
12
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - 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¨ele 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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
37/41
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
Samenvatting - Complexiteit We hebben twee methoden bestudeerd voor de analyse van algoritmen Empirische analyse Complexiteitsklassen
ODE/FHTBM
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
38/41
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
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
Complexiteit van Algoritmen
12 september 2012
39/41
13
12 september 2012
Complexiteit
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - 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
Complexiteit van Algoritmen
Implementaties en Empirische Analyse Analyse van Algoritmen Groot Oh-Notatie
12 september 2012
40/41
Groot O-notatie van f(N) Voorbeelden - Hoe de O-notatie te gebruiken Samenvatting - Complexiteit
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
Complexiteit van Algoritmen
12 september 2012
41/41
14