Complexité des algorithmes

Algorithmique 1 2023-2024

Stéphane Grandcolas

Aix-Marseille Université

Contact : [Link]@[Link]

S. Grandcolas, 2024
Algorithmique 1

Objectifs du cours :
▶ introduire les structures de données et les techniques de
conception de base de l’algorithmique,
▶ étudier les outils d’analyse et de preuve de correction des
algorithmes.

Modalités de contrôle :
session 1 : NF = 0, 8 × ET + 0, 2 × CC
session 2 : NF = ET

Contrôle continu : quatre TP évalués.

S. Grandcolas, 2024
Algorithmique 1

Programme :
▶ algorithmes : complexité, tris,
▶ structures de données : arbres, tas, dictionnaires,
▶ méthodes : backtracking, programmation dynamique,
▶ graphes : plus courts chemins, arbres couvrants.

Livre de référence : Introduction à l’algorithmique, Thomas H. Cormen, Charles E.

Leiserson, Ronald L. Rivest, Clifford Stein.

S. Grandcolas, 2024
Algorithmes et structures de données

P : un problème

M : une méthode pour résoudre le problème P

Algorithme : description de la méthode M dans un

langage algorithmique
du nom du mathématicien perse Al Khuwarizmi (780 - 850)

S. Grandcolas, 2024
Algorithmes et structures de données

P : un problème

M : une méthode pour résoudre le problème P

Algorithme : description de la méthode M dans un

langage algorithmique
du nom du mathématicien perse Al Khuwarizmi (780 - 850)

Structure de données : manière d’organiser et de stocker

les données (supposée rendre efficace certaines opérations)

S. Grandcolas, 2024
Structures algorithmiques

Structures de contrôle
▶ séquence
▶ embranchement (ou sélection)
▶ boucle (ou itération)

Structures de données : supports

▶ constantes, variables
▶ tableaux
▶ structures récursives (listes, arbres, graphes)

S. Grandcolas, 2024
Complexité des algorithmes

On veut
▶ Evaluer l’efficacité de la méthode M
▶ Comparer M avec une autre méthode M′

indépendamment de l’environnement (machine, système,

compilateur, . . .)

S. Grandcolas, 2024
Complexité des algorithmes

Evaluation du nombre d’opérations élémentaires en fonction

▶ de la taille des données (par ex. le nombre d’éléments à trier)
▶ de la nature des données (provoquant par exemple une sortie
de boucle prématurée)

Notations :
▶ n : la taille des données,
▶ T (n) : le nombre d’opérations élémentaires

Configurations caractéristiques :
▶ le meilleur des cas,
▶ le pire des cas,
▶ la configuration en moyenne.
S. Grandcolas, 2024
Evaluation de T (n) (séquence)

Somme des coûts.


Traitement1 T1 (n) 
T (n) = T1 (n) + T2 (n)
Traitement2 T2 (n)


S. Grandcolas, 2024
Evaluation de T (n) (embranchement)

Max des coûts.


si < condition > alors Tc (n) 

Traitement1 T1 (n)

sinon 

Traitement2 T2 (n)


Tc (n) + max(T1 (n), T2 (n))

S. Grandcolas, 2024
Evaluation de T (n) (boucle)

Somme des coûts des passages successifs


tant que < condition > faire Ci (n) 
Traitement Ti (n)
fin faire


k
X
(Ci (n) + Ti (n)) + Ck+1 (n)
i=1

Ti (n) : coût de la i ième itération

souvent défini par une équation récursive

S. Grandcolas, 2024
Evaluation de T (n) (fonctions récursives : exemple)
fonction FUNCTIONRECURSIVE (n)
1 si (n > 1) alors
2 FUNCTIONRECURSIVE(n/2), coût T (n/2)
3 FUNCTIONRECURSIVE(n/2), coût T (n/2)
4 Traitement(n), coût C (n)

Equation récursive

T (n) = 1 + 2 × T (n/2) + C (n)

si C (n) = 1 alors T (n) = K × n

si C (n) = n alors T (n) = K × n × log n
...

S. Grandcolas, 2024
Notation de Landau O(f (n))
c × f (n )

T (n) = O(f (n))

n0 n

Caractérise le comportement asymptotique (i.e. qd n → ∞).

T (n) = O(f (n)) si ∃c ∃n0 tels que ∀n > n0 , T (n) ≤ c × f (n)

S. Grandcolas, 2024
Notation Θ(f (n))
c1 × f (n)

T (n )

c2 × f (n)

n0 n

T (n) = Θ(f (n)) si ∃c1 , c2 , n0 tels que

∀n > n0 , c1 × f (n) ≤ T (n) ≤ c2 × f (n)

S. Grandcolas, 2024
Exemples

T (n) = n3 + 2 n2 + 4 n + 2 = O(n3 )
(si n ≥ 1 alors T (n) ≤ 9 × n3 )

S. Grandcolas, 2024
Exemples

T (n) = n3 + 2 n2 + 4 n + 2 = O(n3 )
(si n ≥ 1 alors T (n) ≤ 9 × n3 )

T (n) = n log n + 12 n + 2 = O(n log n)

S. Grandcolas, 2024
Exemples

T (n) = n3 + 2 n2 + 4 n + 2 = O(n3 )
(si n ≥ 1 alors T (n) ≤ 9 × n3 )

T (n) = n log n + 12 n + 2 = O(n log n)

2n
T (n) = 2 n10 + n7 + 12 n4 + = O(2n )
100

S. Grandcolas, 2024
Les classes de complexité les plus courantes

O(1) temps constant

O(log n) logarithmique
O(n) linéaire
O(n × log n) tris par comparaisons optimaux
O(n2 ) quadratique, polynomial
O(n3 ) cubique, polynomial
O(2n ) exponentiel (problèmes très difficiles)

S. Grandcolas, 2024
Exemple : permutation dans un tableau
fonction PERMUTATION (S[1, . . . , n], i, j)
1 tmp := S[i], coût c1
2 S[i] := S[j], coût c2
3 S[j] := tmp, coût c3
4 renvoyer S coût c4

Coût total

T (n) = c1 + c2 + c3 + c4 = O(1)

S. Grandcolas, 2024
Exemple : recherche séquentielle dans un tableau
fonction RECHERCHE_SEQUENTIELLE(x, S[1, . . . , n])
1 i := 1, (c1 )
2 tant que ((i < n) et (S[i] ̸= x)) faire (c2 )
3 i := i + 1, (c3 )
4 renvoyer (S[i] = x) (c4 )

Pire des cas : n fois la boucle

T (n) = c1 + c2 + n−1
P
i=1 (c3 + c2 ) + c4 = O(n)

S. Grandcolas, 2024
Exemple : tri à bulle
fonction TRI_A_BULLES (S[1, . . . , n])
1 pour i := n à 2 faire
2 pour j := 1 à i − 1 faire
3 si (S[j] > S[j + 1]) alors coût Cc
4 PERMUTER(S, j, j + 1), coût Cp

Pire des cas : la condition est toujours vraie

Pn−1
T (n) = (Cc + Cp ) × i=1 i = (Cc + Cp ) × n×(n−1)
2
= O(n2 )

S. Grandcolas, 2024
Equations récursives

Boucles itératives, fonctions récursives, approches de type

diviser pour régner

Cas général

T (n) = a × T (n/b) + f (n)

Différents outils :
▶ méthode par substitution (vérification, preuve),
▶ méthode par sommation (développement itératif),
▶ théorème général.

S. Grandcolas, 2024
Méthode par substitution

Principe : on vérifie une proposition

T (n) = a × T (n/b) + f (n) et T (1) = c

Proposition
T (n) = O(g (n))

A démontrer en fixant les constantes

S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

fonction RECHERCHE_DICHOTOMIQUE (x, S = (v1 , . . . , vn ))

1 g := 0, d := n + 1,
2 tant que (g < d − 1) faire
3 si (x > v(g +d)/2 ) alors
4 g := (g + d)/2,
5 sinon
6 d := (g + d)/2,
7 renvoyer d,

Renvoie la position de x s’il apparaît dans S,

renvoie la position à laquelle il faudrait l’insérer sinon

S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

fonction RECHERCHE_DICHOTOMIQUE (x, S = (v1 , . . . , vn ))

1 g := 0, d := n + 1,
2 tant que (g < d − 1) faire
3 si (x > v(g +d)/2 ) alors ici 0 < (g + d)/2 < n + 1
4 g := (g + d)/2,
5 sinon
6 d := (g + d)/2,
7 renvoyer d,

Invariant : g ≤ d − 1, et ∀i, si i ≤ g alors vi < x, si i ≥ d alors vi ≥ x,

S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

fonction RECHERCHE_DICHOTOMIQUE (x, S = (v1 , . . . , vn ))

1 g := 0, d := n + 1,
2 tant que (g < d − 1) faire
3 si (x > v(g +d)/2 ) alors
4 g := (g + d)/2,
5 sinon
6 d := (g + d)/2,
7 renvoyer d,

Invariant : g ≤ d − 1, et ∀i, si i ≤ g alors vi < x, si i ≥ d alors vi ≥ x,

Après la boucle : g = d − 1, et ∀i, i ≤ g ⇒ vi < x et i ≥ d ⇒ vi ≥ x,

S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

fonction RECHERCHE_DICHOTOMIQUE (x, S = (v1 , . . . , vn ))

1 g := 0, d := n + 1,
2 tant que (g < d − 1) faire
3 si (x > v(g +d)/2 ) alors
4 g := (g + d)/2,
5 sinon
6 d := (g + d)/2,
7 renvoyer d,

Invariant : g ≤ d − 1, et ∀i, si i ≤ g alors vi < x, si i ≥ d alors vi ≥ x,

Après la boucle : g = d − 1, et ∀i, i ≤ g ⇒ vi < x et i ≥ d ⇒ vi ≥ x,
Conclusion : puisque S est ordonnée, et que toutes les valeurs plus
petites que x apparaissent avant l’indice d, la première valeur dans S qui
soit supérieure ou égale à x est à l’indice d ou x > vn .
S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

Nombre d’itérations

T (1) = 1
T (n) = 1 + T (n/2) si n > 1

▶ T (1) = 1 car s’il y a un seul élément on fera une itération

▶ T (⌈n/2⌉) = T (n/2)
(pour simplifier on considère que n est de la forme 2k )

S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

T (n) = 1 + T (n/2) et T (1) = 1

Proposition T (n) = O(log2 n)

S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

T (n) = 1 + T (n/2) et T (1) = 1

Proposition T (n) = O(log2 n)

alors ∃k1 , k2 tels que T (n) = k1 × log2 n + k2

S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

T (n) = 1 + T (n/2) et T (1) = 1

Proposition T (n) = O(log2 n)

alors ∃k1 , k2 tels que T (n) = k1 × log2 n + k2

donc T (n/2) = k1 × log2 n − k1 + k2 car log2 (n/2) = log2 n − 1
donc T (n) = 1 + T (n/2) = 1 + k1 × log2 n − k1 + k2
donc 1 − k1 + k2 = k2 et donc k1 = 1,
enfin, puisque T (1) = 1, on a k2 = 1

S. Grandcolas, 2024
Méthode par substitution [recherche dichotomique]

T (n) = 1 + T (n/2) et T (1) = 1

Proposition T (n) = O(log2 n)

alors ∃k1 , k2 tels que T (n) = k1 × log2 n + k2

donc T (n/2) = k1 × log2 n − k1 + k2 car log2 (n/2) = log2 n − 1
donc T (n) = 1 + T (n/2) = 1 + k1 × log2 n − k1 + k2
donc 1 − k1 + k2 = k2 et donc k1 = 1,
enfin, puisque T (1) = 1, on a k2 = 1

Conclusion T (n) = log2 n + 1 = O(log2 n)

(en fait Θ(log2 n))

S. Grandcolas, 2024
Méthode par développement itératif (sommation)

Quelques formules utiles :

Pn−1 n×(n−1)
▶ i=1 i= 2
= Θ(n2 ) = O(n2 )

x n+1 −1
Pn
▶ i=0 xi = x−1

en particulier quand x vaut 2

Pn
i=0 2i = 2n+1 − 1

S. Grandcolas, 2024
Tri par fusion

▶ diviser pour régner

▶ décomposition
▶ fusion
fonction TRI_PAR_FUSION (S)

1 si (longueur (S) > 1) alors

2 décomposer S −→ (S1 , S2 ),
3 S1 := TRI_PAR_FUSION(S1 ),
4 S2 := TRI_PAR_FUSION(S2 ),
5 S := FUSIONNER(S1 , S2 ),
6 renvoyer S

S. Grandcolas, 2024
Tri par fusion

▶ diviser pour régner 69412537

décompositions
▶ décomposition
6423 9157
▶ fusion
62 43 95 17

6 2 4 3 9 5 1 7

26 34 59 17

fusions 1579
2346

12345679

S. Grandcolas, 2024
Tri par fusion
fonction TRI_PAR_FUSION (S)

1 si (longueur (S) > 1) alors

2 décomposer S −→ (S1 , S2 ), (n)
3 S1 := TRI_PAR_FUSION(S1 ), (T (⌈n/2⌉))
4 S2 := TRI_PAR_FUSION(S2 ), (T (⌊n/2⌋))
5 S := FUSIONNER(S1 , S2 ), (n)
6 renvoyer S

T (n) = 1 + n + T (⌈n/2⌉) + T (⌊n/2⌋) + n et T (1) = 1

S. Grandcolas, 2024
Tri par fusion
fonction TRI_PAR_FUSION (S)

1 si (longueur (S) > 1) alors

2 décomposer S −→ (S1 , S2 ), (n)
3 S1 := TRI_PAR_FUSION(S1 ), (T (⌈n/2⌉))
4 S2 := TRI_PAR_FUSION(S2 ), (T (⌊n/2⌋))
5 S := FUSIONNER(S1 , S2 ), (n)
6 renvoyer S

T (n) = 2n + 1 + 2 × T (n/2)

on suppose que n est de la forme 2k

S. Grandcolas, 2024
Méthode par sommation [développement itératif]

T (n) = 2n + 1 + 2 × T (n/2)

S. Grandcolas, 2024
Méthode par sommation [développement itératif]

T (n) = 2n + 1 + 2 × T (n/2)
donc T (n/2) = n + 1 + 2 × T (n/4)

S. Grandcolas, 2024
Méthode par sommation [développement itératif]

T (n) = 2n + 1 + 2 × T (n/2)
donc T (n/2) = n + 1 + 2 × T (n/4)
= (2n + 1) + (2n + 2) + 4 × T (n/4)

S. Grandcolas, 2024
Méthode par sommation [développement itératif]

T (n) = 2n + 1 + 2 × T (n/2)
donc T (n/2) = n + 1 + 2 × T (n/4)
= (2n + 1) + (2n + 2) + 4 × T (n/4)
or T (n/4) = n/2 + 1 + 2 × T (n/8)

S. Grandcolas, 2024
Méthode par sommation [développement itératif]

T (n) = 2n + 1 + 2 × T (n/2)
donc T (n/2) = n + 1 + 2 × T (n/4)
= (2n + 1) + (2n + 2) + 4 × T (n/4)
or T (n/4) = n/2 + 1 + 2 × T (n/8)
= (2n + 1) + (2n + 2) + (2n + 4) + 8 × T (n/8)
...

S. Grandcolas, 2024
Méthode par sommation [développement itératif]

T (n) = 2n + 1 + 2 × T (n/2)
donc T (n/2) = n + 1 + 2 × T (n/4)
= (2n + 1) + (2n + 2) + 4 × T (n/4)
or T (n/4) = n/2 + 1 + 2 × T (n/8)
= (2n + 1) + (2n + 2) + (2n + 4) + 8 × T (n/8)
...
Plog n−1
T (n) = i=0 (2n + 2i ) + 2log n × T (1)

S. Grandcolas, 2024
Méthode par sommation [développement itératif]

T (n) = 2n + 1 + 2 × T (n/2)
donc T (n/2) = n + 1 + 2 × T (n/4)
= (2n + 1) + (2n + 2) + 4 × T (n/4)
or T (n/4) = n/2 + 1 + 2 × T (n/8)
= (2n + 1) + (2n + 2) + (2n + 4) + 8 × T (n/8)
...
Plog n−1
T (n) = i=0 (2n + 2i ) + 2log n × T (1)
P n−1 i
= 2n log n + logi=0 2 +n

S. Grandcolas, 2024
Méthode par sommation [développement itératif]

T (n) = 2n + 1 + 2 × T (n/2)
donc T (n/2) = n + 1 + 2 × T (n/4)
= (2n + 1) + (2n + 2) + 4 × T (n/4)
or T (n/4) = n/2 + 1 + 2 × T (n/8)
= (2n + 1) + (2n + 2) + (2n + 4) + 8 × T (n/8)
...
Plog n−1
T (n) = i=0 (2n + 2i ) + 2log n × T (1)
P n−1 i
= 2n log n + logi=0 2 +n
Plog n−1
or i=0 2i = 2log n − 1 = n − 1

= 2n log n + 2n − 1 = Θ(n log n)

S. Grandcolas, 2024
Tri par fusion
n 2×n

n/2 n/2 2×n

hauteur ⌈log n⌉
n/4 n/4 n/4 n/4 2×n

n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8

1 1 1 ....

décomposition ou fusion d’une suite de longueur n/k : coût O(n/k)

T (n) = 2 × n × ⌈log2 n⌉

S. Grandcolas, 2024
Master theorem [Equations récursives]

T (n) = a × T (n/b) + f (n)

avec a ≥ 1, b > 1 et f (n) est positive asymptotiquement.
a−ϵ
▶ si ∃ϵ > 0, f (n) = O(nlogb ) alors T (n) = Θ(nlogb a ),
▶ si f (n) = Θ(nlogb a ) alors T (n) = Θ(nlogb a
× log n),
▶ si ∃ϵ > 0, f (n) = Ω(nlogb a+ϵ ) et
si ∃c < 1, ∃n0 , ∀n > n0 , a × f (n/b) ≤ c × f (n) alors
T (n) = Θ(f (n))

S. Grandcolas, 2024
Master theorem [Equations récursives]

T (n) = a × T (n/b) + f (n)

avec a ≥ 1, b > 1 et f (n) est positive asymptotiquement.
a−ϵ
▶ si ∃ϵ > 0, f (n) = O(nlogb ) alors T (n) = Θ(nlogb a ),
▶ si f (n) = Θ(nlogb a ) alors T (n) = Θ(nlogb a
× log n),
▶ si ∃ϵ > 0, f (n) = Ω(nlogb a+ϵ ) et
si ∃c < 1, ∃n0 , ∀n > n0 , a × f (n/b) ≤ c × f (n) alors
T (n) = Θ(f (n))

Tri par fusion (T (n) = 2 × T (n/2) + 2n + 1) cas 2 :

a = b = 2 et f (n) = 2n + 1 = Θ(n)
et donc T (n) = Θ(n log n)

S. Grandcolas, 2024
Méthode par substitution [tri par fusion]

T (n) = 2n + 1 + 2 × T (n/2) et T (1) = 1

Hypothèse : T (n) = O(n log n) = a × n log n + b × n + c

et donc T (n/2) = a × n/2 log n + (b − a) × n/2 + c
T (n) = 2n + 1 + 2T (n/2) = 2n + 1 + a × n log n + (b − a) × n + 2c
= a × n log n + (b − a + 2) × n + 2c + 1

(1) b = b − a + 2 et donc a = 2
(2) c = 2c + 1 et donc c = −1
(3) T (1) = b + c = 1 et donc b = 2

et finalement T (n) = 2n log n + 2n − 1 = O(n log n)

S. Grandcolas, 2024
Temps de calcul [simulation]

Combien de temps pour traiter un problème ?

Taille log2 n n n log2 n n2 2n

10 0.003 ms 0.01 ms 0.03 ms 0.1 ms 1 ms
14
100 0.006 ms 0.1 ms 0.6 ms 10 ms 10 siècles
1000 0.01 ms 1 ms 10 ms 1s
104 0.013 ms 10 ms 0.1 s 100 s
105 0.016 ms 100 ms 1.6 s 3 heures
106 0.02 ms 1s 20 s 10 jours

pour une machine qui effectue 106 traitements par seconde

S. Grandcolas, 2024
Temps de calcul [simulation]

Quel problème peut-on traiter en une seconde ?

nTs 2n n2 n log2 n n log2 n

106 20 1000 63000 106
10300000
107 23 3162 600000 107 103000000
109 30 31000 4.107 109
1012 40 106 3.1010

nTs = nombre d’instructions effectuées chaque seconde

S. Grandcolas, 2024