Structures de données Christian Carrez Cnam Algorithmes et complexité 1
Notion d'algorithme et de
complexité
algorithme
Structures de données Christian Carrez Cnam Algorithmes et complexité 2
ensemble de règles opératoires dont l'application permet de
résoudre un problème en un nombre fini d'opérations
choix des règles opératoires
étude préliminaire de l'algorithme
♦ préciser les actions sans les détails des opérations
♦ vérifier la correction de l'algorithme
♦ étudier son efficacité en temps et en espace mémoire
complexité de l'algorithme
implantation de l'algorithme, i.e. mise en œuvre
voyageur de commerce
Structures de données Christian Carrez Cnam Algorithmes et complexité 3
Lille
417
227
220 443 Nancy
Rouen
308
136
Paris
parcours (V1,...,Vn) = Σ d(Vi-1,Vi)
calculer le parcours de toutes les permutations prendre et
choisir
additions: n * n!
♦ 5 villes => 600 additions
♦ 20 villes => 5 10 19 additions, soit 1,5 millions d'années
note: résolution par des heuristiques
opération fondamentale
Structures de données Christian Carrez Cnam Algorithmes et complexité 4
peut être complexe, mais de durée indépendante des
données
si plusieurs opérations fondamentales, décompte séparé, et
coefficient
opération de détail prises en compte par absorption
comparaison entre algorithmes si mêmes opérations
exemples:
♦ addition des distances dans voyageur de commerce
♦ comparaison de valeurs dans une recherche ou un tri
♦ déplacements de valeurs dans un tri
♦ accès à la mémoire secondaire
calcul de la complexité
Structures de données Christian Carrez Cnam Algorithmes et complexité 5
évaluer le nombre d'exécutions de l'opération
fondamentale
var T: tableau [1..N] de T_Elem; {rangé par valeurs croissantes}
k : entier;
début k := 1; tant que k <= N et alors T[k] < x faire k := k+1; fait;
retourner k;
fin
invariant: pour tout j < k, t[j] < x
sortie de boucle: k = N+1 ou (k≤N et T[k]≥x)
complexité: au mieux 1, au pire N, en moyenne N/2
{1, ou 2, ou 3,..., N} si k≤N et N si k=N+1
définitions
Structures de données Christian Carrez Cnam Algorithmes et complexité 6
Soit Dn l'ensemble des données de taille n
et coûtA (d) le coût de l'algorithme sur la donnée d
complexité au mieux MinA(n)=min{coûtA(d) | d ∈Dn }
complexité au pire MaxA(n)=max{coûtA(d) | d ∈Dn }
complexité en moyenne MoyA(n)=Σ{p(d)*coûtA(d) | d ∈Dn}
où p(d) est la probabilité d'avoir le donnée d
MinA(n) ≤ MoyA(n) ≤ MaxA(n)
comparaisons d'algorithmes
Structures de données Christian Carrez Cnam Algorithmes et complexité 7
var T: tableau [1..N] de T_Elem;
i, j, k: entier;
invariant:
début ♦ m < i => T [m] < x
i := 1; j := N; ♦ j ≠ N => x ≤ T[j]
tant que i < j faire ♦ N ≠ 0 => i ≤ j
k := (i+j) / 2;
si T[k] < x alors i := k+1; arrêt:
sinon j := k; finsi; ♦ nouveau(j-i) = ancien(j-i) / 2
fait;
si i = N et alors T[i] < x alors
complexité:
i := N+1; ♦ log2N
finsi;
retourner i;
fin;
meilleur que précédent sauf si début
ordre de grandeur
Structures de données Christian Carrez Cnam Algorithmes et complexité 8
l'important est l'ordre de grandeur, et l'évolution en
fonction de la taille
définition: f est dominée par g, f = O(g) s'il existe n0 et c
tels que pour tout n > n0, on ait f(n) ≤ c g(n)
définition: f et g sont du même ordre de grandeur, f = Θ(g)
s'il existe n0 , c1 et c2 tels que
pour tout n > n0, on ait c1 g(n) ≤ f(n) ≤ c2 g(n)
c g(n) c2 g(n)
f(n)
f(n) c1 g(n)
n n
temps d'exécution suivant la taille
Structures de données Christian Carrez Cnam Algorithmes et complexité 9
1 log2n n n log2n n2 n3 2n
102 1µs 7µs 0.1 ms 0.7 ms 10 ms 1s 4107Ga
103 1µs 10µs 1 ms 10 ms 1s 17 mn ∞
104 1µs 13µs 10 ms 130 ms 1.7 mn 12 j ∞
105 1µs 17µs 0.1 s 1.7 s 2.8 h 32 a ∞
106 1µs 20µs 1s 20 s 12 j 32 Ka ∞
taille suivant temps d'exécution
Structures de données Christian Carrez Cnam Algorithmes et complexité 10
1 log2n n n log2n n2 n3 2n
1s ∞ ∞ 1 M. 63 K. 1 K. 100 20
1 mn ∞ ∞ 60 M. 3 M. 7 K. 400 26
1h ∞ ∞ 4 G. 130 M. 60 K. 1.5 K. 32
1j ∞ ∞ 90 G. 3 G. 300 K. 4.4 K. 36
complexité en place mémoire
Structures de données Christian Carrez Cnam Algorithmes et complexité 11
évaluer la quantité de mémoire nécessaire en fonction de la
taille des données
conservation des diminution de
résultats intermédiaires complexité en temps
mémoire doit être suffisante
compromis espace-temps
conclusion
Structures de données Christian Carrez Cnam Algorithmes et complexité 12
algorithme: correct et temps d'exécution raisonnable
complexité relative à une ou des opérations fondamentales
♦ dépend de la taille des données et de leur configuration
– complexité < n2 => taille quelconque
– entre n2 et n3 => taille moyenne
– > n3 => petite taille
performance des machines ne change pas l'efficacité
compromis espace-temps
