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)