Analyse des AlgorithmesInformatique de gestion

Introduction : Efficacité des algorithmes (1)

Comment choisir parmi les différentes approches pour résoudre un problème?

Exemple: Liste chaînée ou tableau?

Deux objectifs à atteindre: Concevoir un algorithme facile à

comprendre, coder et déboguer. Concevoir un algorithme qui utilise de façon

efficace les ressources de l’ordinateur.

Introduction : Efficacité des algorithmes (2)

Objectif (1): concerne le génie logiciel

Objectif (2): concerne les algorithmes et structures de données.

4

Introduction : Efficacité des algorithmes (e)

Evaluation de performances d’un algorithmeEst-ce que le programme utilise efficacement

la mémoire ?Est-ce que son temps d’exécution est

acceptable?

Complexité des

algorithmes Estimations de temps et d’espace Indépendants de la machine

5

Introduction : Définitions

Définition : La complexité en espace mémoire d’un

algorithme est la quantité de mémoire nécessaire à son exécution complète

Définition : La complexité en temps d’un algorithme est

la quantité de temps nécessaire à son exécution complète Comment peut-on mesurer la complexité en

temps?

Introduction : Comment mesurer la complexité en temps?

Deux approches : Comparaison empirique: (exécuter le programme) Analyse assymptotique d’algorithmes

Facteurs affectant le temps d’exécution: machine, language, programmeur, compilateur, algorithme et structure de données.

En général, le temps d’exécution dépend de la longueur de l’entrée.

Ce temps est une fonction T(n) où n est la longueur de l’entrée.

Analyse d’un algorithmeExemple d’un algorithme:

Algorithme(T[1..N]) 1. dmin <- 0

2. pour i <- 1 à N

3. pour j <- 1 à N

4. si i ≠ j et |T[i] – T[j]| > dmin

5. dmin <- |T[i] – T[j]|

6. retourner dmin

Que fait cet algorithme?Combien de fois chaque ligne est exécutée?

Analyse d’un algorithme

Coût Nombre exact d’exécutions

F( T[ 1.. N ] )

pour i 1 à N c1

min T[i] c2

indexMin i c3

pour j i+1 à N c4

si T[j] < min c5

min T[j] c6

indexMin j c7

T[indexMin] T[i] c8

T[i] min c9

2

( 1)(( ) 1)

2

N

i

N NN i

12

)3(

2

N

i

NNiN

12

)3(

2

N

i

NNiN

12

)3(

2

N

i

NNiN

1N

N

N

N

N

22 5 6 7 4 5 6 71 2 3 8 9 2 3 5 6 7( )

2 2

c c c c c c c cT N N c c c c c N c c c c c

Le tri par sélectionL’algorithme

5 7 82631.

57 82 633.

57 82 632.

5 7 82 634.

5 7 82 636.

5 7 82 635.

5 7 82 637.

Analyse d’une fonction

Analyse détaillée d’un algorithme:Avantage :Très préciseDésavantage : Long à calculer

Solution: Analyser asymptotiquement le comportement de l’algorithme lorsque le(s) paramètre(s) de l’algorithme tendent vers l’infini:Avantage: Facile à calculerDésavantage: Moins précis

Notation ODétermine une borne supérieure Définition formelle : f(n) = O(g(n)) s’il existe deux constantes

positives n0 et c tel que f(n) <= cg(n) pour tout n>n0

f(n) = O(g(n))

n

tem

ps

cg(n)

f(n)

n0

Notation-O (Calcul analytique)Étant donné deux fonctions f(n) et g(n), f(n) = O(g(n))

ssi: b >= 0, n, f(n) / g(n) <= b

Þ limn®¥ f(n) / g(n) Î Â+ È 0

Exemple:f(n) = 3n2+6n+4 et g(n) = n2+3 limn®¥ f(n) / g(n) = 3

\ 3n2+6n+4 est O(n2+3)

On dit « f(g) est d’ordre de g(n) »

Notation-O (Analyse d’un algorithme)Cherche une fonction simple qui décrit le comportement de

l’algorithme dans le pire cas. Exemples : O(n), O(n2), O(lg n)

L’analyse est simplifiée selon les règles suivantes: Les constantes sont éliminées Seul le monôme avec le degré le plus élevé est conservé

Exemple: f(n) = 3n2+5n+4 est en O(n2)

0 10 20 30 40 50 600

500

1000

1500

2000

2500

3000

3500

4000

n (taille des données)

f(n) vs n2

f(n)

n2

f(n)

TRI PAR INSERTION

TRI PAR INSERTION

Tri par insertion

5 7 82631.

5 7 82632.

5 7 82633.

5 7 82634.

5 7 82 635.

5 7 82 636.

Notation-O (Analyse d’un algorithme)

1N

Nombre exact d’exécutions(Pire cas)

Analyse asymptotique

InsertionSort( T[ 1.. N ] )

pour j 2 à N

key T[j]

i j -1

tant que i > 0 et T[i]>key

T[i+1] T[i]

i i-1

T[i+1] key

12

)1(

2

N

j

NNj

N

j

NNj

2 2

)1(1

N

j

NNj

2 2

)1(

N

1N

1N

T(N) = O(3N2+4N) = O(N2)

O(N)

O(N)

O(N)

O(N2)

O(N2)

O(N2)

O(N)

Notation-WDétermine une borne inférieureDéfinition formelle : f(n) = W(g(n)) s’il existe deux constantes

positives n0 et c tel que cg(n) <= f(n) pour tout n>n0

f(n) = W (g(n))

n

tem

ps

cg(n)

f(n)

n0

Notation- (W Calcul analytique)Étant donné deux fonctions f(n) et g(n), f(n) = W(g(n))

ssi: b > 0, n, f(n) / g(n) >= b

limn®¥ f(n) / g(n) Î Â+ È ¥

Exemple:f(n) = 3n2+6n+4 et g(n) = n+3 limn®¥ f(n) / g(n) = ¥

\ 3n2+6n+4 est W(n+3) 3n2+6n+4 est W(n)

On dit « f(g) est en oméga g(n) »

Notation-W (Analyse d’un algorithme)

Nombre exact d’exécutions (Meilleur cas)

Analyse asymptotique

InsertionSort( T[ 1.. N ] )

pour j <- 2 à N

key <- T[j]

i <- j-1

tant que i > 0 et T[i]>key

T[i+1] <- T[i]

i <- i-1

T[i+1] <- key

112

N

j

N

N

1N

1N

T(N) = W(5N+2) = W(N)

W(N)

W(N)

W(N)

W(N)

W(1)

W(1)

W(N)1N

0

0

Notation-QRelation d’équivalenceDéfinition formelle : f(n) = Q(g(n)) s’il existe trois constantes

positives n0,c1 et c2 tel que c1g(n) <= f(n) <= c2g(n) pour tout n>n0

f(n) = Q(g(n))

n

tem

ps

c1g(n)

f(n)

n0n0

c2g(n)

Notation- Q (Calcul analytique)Étant donné deux fonctions f(n) et g(n), f(n) = Q(g(n)) ssi:

a,b > 0, n, a <= f(n) / g(n) <= b

limn®¥ f(n) / g(n) +Î Â

Exemple:f(n) = 3n2+6n+4 et g(n) = n2+3

limn®¥ f(n) / g(n) = 3

\ 3n2+6n+4 est Q(n2+3) 3n2+6n+4 est Q(n2)

Autre propriété:f(n) = Q(g(n)) ssi f(n) = O(g(n)) et f(n) = W(g(n))

Notation- (Q Analyse d’un algorithme)

N

1N

1N

N

i

NNiN

2 2

)1(1)(

Analyse du pire cas Analyse meilleur cas

SelectionSort( T[ 1.. N ] )

pour i <- 1 à N-1

min <- T[i]

indexMin <- i

pour j <- i+1 à N

si T[j] < min

min <- T[j]

indexMin <- j

T[indexMin] <- T[i]

T[i] <- min

N

i

NNiN

2 2

)1(1)(

12

)3(

2

N

i

NNiN

12

)3(

2

N

i

NNiN

12

)3(

2

N

i

NNiN

N

1N

1N

1N

1N

1N

1N

12

)3(

2

N

i

NNiN

O(N)

O(N)

O(N)

O(N2)

O(N2)

O(N2)

O(N2)

O(N)

O(N)

W(N)

W(N)

W(N)

W(N2)

W(N2)

W(1)

W(1)

W(N)

W(N)

T(N) = O(N2) et T(N) = (W N2)Þ TN QN2

0

0

Notation- (Q Analyse d’un algorithme)

Analyse W Analyse O

InsertionSort( T[ 1.. N ] )

pour j <- 2 à N

key <- T[j]

i <- j-1

tant que i > 0 et T[i]>key

T[i+1] <- T[i]

i <- i-1

T[i+1] <- key

O(N)

O(N)

O(N)

O(N2)

O(N2)

O(N2)

O(N)

W(N)

(W N)

W(N)

W(N)

W(1)

W(1)

W(N)

Analyse algorithmiqueMeilleur cas Pire cas

Tri à bulle W(N2) O(N2)

Tri par sélection W(N2) O(N2)

Tri par insertion W(N) O(N2)

Trois algorithmes de tri

Dans le pire cas et avec le même nombre de données à trier, est-ce que le temps d’exécution sera identique?

Analyse de la mémoire de travail

Analyse W Analyse O

CreateAndFillMatrix(N,M )

C[1..N,1..M] : matrice

pour i <-1 to N

pour j<-1 to M

ci,j <- max(C[i,j-1],C[i-1,J]+ )l

C[i,j] <-ci,j

retourner C[1..N,1..M]

O(N*M)

O(1)

O(1)

O(1)

W(N*M)

(1W )

W(1)

W(1)

Mémoire de travail : Q(N*M)

Même principe que pour le temps d’exécution mais on considère la dimension des variables et tableaux.

Déterminer expérimentalement la relation asymptotique entre deux fonctions

2 fonctions inconnues f(n) et g(n).Fonctions positives non décroissantes.Arguments positifs.

On a un échantillon des valeurs de f(n) et de g(n) pour plusieurs points n = {n1, n2.....}. On peut avoir plusieurs valeurs de f(n) et g(n)

pour le même n.Tracer un graphe f(n) vs g(n).

Déterminer expérimentalement la relation asymptotique entre fonctions ensemblistes

Diagramme X-Y.Abscisses g(n), ordonnées f(n).

f(n)

g(n)

Simplifier les séries Sommes ou produits avec un nombre variable de termes.

Série Formule Résultat Exemple -équivalente

constante k=1..N a aN 3+3+...+3(10 fois) N

somme de logs k=1..N log(k) log(N!) log(2)+log(3)+..log(100) N log(N)

arithmétique k=1..N k N(N+1)/2 1+2+...+10 N2

somme de carrés k=1..N k2 N(N+1)(2N+1)/6 1+22+32+..102 N3

somme de puissances

k=1..N ka (a entier)   1+23+33+..103 (a=3) Na+1

de polynomes de degré a

k=1..N Pa(k)   k=1..N k(k+1)..(k+a) Na+1

géométrique binaire

k=0..N 2k 2N+1-1 1+2+4+..+128 2N

géométrique entière

k=0..N ak (a entier) (aN+1-1)/(a-1) 1+3+9+..+81 (a=3) aN

factorielle k=1..N k N!2N (N/e)N 1*2*..*100 NN+0.5

Analyse des algorithmesTypes de temps de calcul rencontré.

O(1). Constant ou borné parfait. O(log*(n)). Logarithme itératif excellent

log*(n)= i t.q. log(log..(n)) (i fois) <= 1. O(log(n)). Logarithmique excellent O(log(n)a). Polylog excellent O(n), O(n1/a). Sub-linéaire très bon O(n). Linéaire très bon O(n log(n) ) bon. O(na) polynomial

acceptable O(an) exponentiel inacceptable O(n!) factoriel beurk.

Fonctions de plusieurs argumentsLe calcul asymptotique s'applique aux fonctions de

plusieurs arguments, f(n1,...nk).Arguments entiers ou réels.Tous les arguments peuvent tendre vers +¥.

On prend les mêmes définitions, avec une modification.lim n1 -> +¥ lim n2 -> +¥ ... lim nk -> +¥

au lieu de lim n -> +¥

Exemple.f (n, m, r) = (m+1) * n2 * (r+log(r))f(n, m, r) est en (m *n2 * r)

Contre exemple.f (n, m, r) = m* n2 * (r+log(n))On ne peut pas dire que f(n, m, r) est en (m *n2 * r)

Conclusion1. Calculer le temps d’exécution.

• Précisement• Asymptotiquement (, , O)

2. Même méthode appliquée pour déterminer la mémoire de travail.