LA COMPLEXITE DES ALGORITHMES

Il faut déterminer l'algorithme qui fait le travail au moindre coût :

coût = temps d'éxécution + taille mémoire

Complexité Complexité

temporelle spatiale

Complexité pratique : mesure précise des temps de calcul et des tailles mémoires pour un modèle de machine bien défini.

Complexité théorique : donne des ordres de grandeur des coûts indépendamment de toute machine.

ALGO A1;

VAR ent i,n;

Début

lire(n);

i:=n-1;

TTque n mod i<>0 Faire i:=i-1;

Fait

ecrire(i);

Fin.

ALGO A2;

VAR ent i,n;

Début

lire(n);

i:=2;

TTque i<RAC(n) et n mod i<>0 Faire i:=i+1;

Fait

Si n mod i=0 Alors ecrire(n/i);

Sinon ecrire(1);

Fsi

Fin.

I1

TTque condition Faire I2

Fait

I3

T1,T2,T3 T1 = temps branchement inconditionnel

T2 = temps branchement conditionnel

T=T1+m(Tc+T2+T1)+T3 t=P+mQ

Maximum d'exécution de la boucle ? n est premier

Algo1 n-2 => a+nb Complexité

Algo2 ENT(RAC(N))-1 a'+Vnb' temporelle

maximale

n=1010 1 boucle 10-3s

1: 1010 x 10-3 = 10-7s

2: V1010 x 10-3 = 100s

La taille est le paramètre n caractérisant la grandeur des données.

Le temps d'éxécution c est une fonction de la taille.

On dit qu'un algorithme est de complexité théorique (direction asymptotique).

O(f(n)) si le rapport C(n)/f(n) est borné qd x ®

c'est-à-dire il existe la constante C(n) k f(n)

Si la complexité de l'algorithme est indépendant de la taille, on dira qu'elle est de l'ordre de O(1).

La complexité maximale Cmax correspond au temps d'éxécution avec des données entraînant l'éxécution la plus longue.

La complexité maximale Cmin correspond au temps d'éxécution avec des données entraînant l'éxécution la plus courte.

Algo1 Cmax=Cmin=(n-1)+(n-2)+...+1=(n-1)/2

Cmax=Cmin=O(n2)

Tri a bulle amélioré Cmax=O(n2), Cmin=n-1=O(n)

Recherche séquentielle Cmax=O(n) Cmin=O(1)

Recherche dichotomique Cmax=Cmin=O(Log2n)

Tri par sélection Cmax=Cmin=O(n2)