1 de 27
Algorithmique
Notion de complexité
Florent Hivert
Mél : [Link]@[Link]
Adresse universelle : [Link]
Outils mathématiques 2 de 27
Outils mathématiques : analyse élémentaire
(Uk )k∈N suite de terme général Uk , k ∈ N
(Uk )k∈K famille d’index K ⊂ N ; suite extraite de (Uk )k∈N
q
X
Uk somme des termes Uk où k vérifie p ≤ k ≤ q (entiers) ;
k=p lorsque p > q, la somme est vide et vaut 0
Yq
Uk produit des termes Uk où k vérifie p ≤ k ≤ q (entiers) ;
k=p lorsque p > q, le produit est vide et vaut 1
Outils mathématiques 3 de 27
Identité sur les sommes et produits
q
X q−1
X q
X
Uk = Uk + Uq = Up + Uk
k=p k=p k=p+1
Plus généralement, si P(n) est un prédicat :
q
X q
X q
X
Uk = Uk + Uk
k=p k=p k=p
P(k) est vrai P(k) est faux
Un exemple très courant :
n
X n
X n
X
Uk = Uk + Uk
k=1 k=1 k=1
k est pair k est impair
Idem pour les produits.
Outils mathématiques 4 de 27
Outils mathématiques : arithmétique
opérateurs usuels :
+ − ×/ < ≤ mod
bxc partie entière inférieure (ou plancher) du réel x : le
plus grand entier ≤ x
dxe partie entière supérieure (ou plafond) du réel x : le
plus petit entier ≥ x
n! la factorielle de n :
n
Y
n! := i = 1 × 2 × 3 × ··· × n
i=1
Outils mathématiques 5 de 27
Parties entières et égalités
Pour tout réel x, pour tout entier n :
bxc = n ⇐⇒ n ≤ x < n + 1 ;
dxe = n ⇐⇒ n − 1 < x ≤ n ;
bx + nc = bxc + n ;
dx + ne = dxe + n.
Pour tout entier n :
n = bn/2c + dn/2e.
Outils mathématiques 6 de 27
Parties entières et inégalités
Pour tout réel x, pour tout entier n :
bxc < n ⇐⇒ x < n ;
dxe ≤ n ⇐⇒ x ≤ n ;
n < dxe ⇐⇒ n < x ;
n ≤ bxc ⇐⇒ n ≤ x.
Pour tous réels x et y :
bxc + by c ≤ bx + y c ≤ bxc + by c + 1 ;
dxe + dy e − 1 ≤ dx + y e ≤ dxe + dy e.
Outils mathématiques 7 de 27
Fonctions usuelles
ln fonction logarithme népérien (ou naturel), de base e
loga fonction logarithme de base a : loga (x) = ln x/ ln a
log fonction logarithme sans base précise, à une constante
multiplicative près
log2 fonction logarithme binaire, de base 2 :
log2 (x) = ln x/ln2
Outils mathématiques 8 de 27
Complexités
Définitions (complexités temporelle et spatiale)
complexité temporelle : (ou en temps) : temps de calcul ;
complexité spatiale : (ou en espace) : l’espace mémoire
requis par le calcul.
Définitions (complexités pratique et théorique)
La complexité pratique est une mesure précise des
complexités temporelles et spatiales pour un modèle de
machine donné.
La complexité (théorique) est un ordre de grandeur de ces
couts, exprimé de manière la plus indépendante possible des
conditions pratiques d’exécution.
Outils mathématiques 9 de 27
Un exemple
Problème (plus grand diviseur)
Décrire une méthode de calcul du plus grand diviseur autre que
lui-même d’un entier n ≥ 2.
Notons pgd(n) le plus grand diviseur en question.
On a :
1 ≤ pgd(n) ≤ n − 1 ;
pgd(n) = 1 ⇐⇒ n est premier.
Outils mathématiques 9 de 27
Un exemple
Problème (plus grand diviseur)
Décrire une méthode de calcul du plus grand diviseur autre que
lui-même d’un entier n ≥ 2.
Notons pgd(n) le plus grand diviseur en question.
On a :
1 ≤ pgd(n) ≤ n − 1 ;
pgd(n) = 1 ⇐⇒ n est premier.
Outils mathématiques 10 de 27
Algorithme (1)
Puisqu’il s’agit de trouver le plus grand diviseur, on peut procéder
en décroissant sur les diviseurs possibles :
1 k n−1
à voir vus
←
Algorithme
calcul du plus grand diviseur (solution 1)
Entrée : un entier n
Sortie : pgd(n)
k ←n−1
tant que n mod k 6= 0 : k ← k − 1
retourner k
Outils mathématiques 10 de 27
Algorithme (1)
Puisqu’il s’agit de trouver le plus grand diviseur, on peut procéder
en décroissant sur les diviseurs possibles :
1 k n−1
à voir vus
←
Algorithme
calcul du plus grand diviseur (solution 1)
Entrée : un entier n
Sortie : pgd(n)
k ←n−1
tant que n mod k 6= 0 : k ← k − 1
retourner k
Outils mathématiques 10 de 27
Algorithme (1)
Puisqu’il s’agit de trouver le plus grand diviseur, on peut procéder
en décroissant sur les diviseurs possibles :
1 k n−1
à voir vus
←
Algorithme
calcul du plus grand diviseur (solution 1)
Entrée : un entier n
Sortie : pgd(n)
k ←n−1
tant que n mod k 6= 0 : k ← k − 1
retourner k
Outils mathématiques 11 de 27
Algorithme (2)
Remarque : le résultat cherché est n ÷ p, où p est le plus petit
diviseur supérieur ou égal à 2 de n.
Notons ppd(n) le plus petit diviseur en question.
2 k n
vus à voir
→
Algorithme (calcul du plus grand diviseur (solution 2))
Entrée : un entier n
Sortie : pgd(n)
k ←2
tant que n mod k 6= 0 : k ← k + 1
retourner n/k
Outils mathématiques 11 de 27
Algorithme (2)
Remarque : le résultat cherché est n ÷ p, où p est le plus petit
diviseur supérieur ou égal à 2 de n.
Notons ppd(n) le plus petit diviseur en question.
2 k n
vus à voir
→
Algorithme (calcul du plus grand diviseur (solution 2))
Entrée : un entier n
Sortie : pgd(n)
k ←2
tant que n mod k 6= 0 : k ← k + 1
retourner n/k
Outils mathématiques 12 de 27
Algorithme (3)
On peut maintenant tenir compte de ce que :
n non premier =⇒ 2 ≤ ppd(n) ≤ pgd(n) ≤ n − 1.
D’où il vient que :
n non premier =⇒ (ppd(n))2 ≤ n.
Proposition
√
Si n ne possède pas de diviseur compris entre 2 et b nc, c’est qu’il
est premier ;
Cece permet d’améliorer le temps de calcul pour les nombres
premiers : il est donc inutile de chercher en croissant entre
√
b nc + 1 et n.
Outils mathématiques 13 de 27
Algorithme (3)
En procédant en croissant sur les diviseurs possibles :
√
2 k b nc n
vus à voir à ne pas voir
→
Algorithme (calcul du plus grand diviseur (solution 3))
Entrée : un entier n
Sortie : pgd(n)
k ←2
tant que n mod k 6= 0 et k ≤ n/k : k ← k + 1
si k > n/k retourner 1 sinon retourner n/k
Outils mathématiques 13 de 27
Algorithme (3)
En procédant en croissant sur les diviseurs possibles :
√
2 k b nc n
vus à voir à ne pas voir
→
Algorithme (calcul du plus grand diviseur (solution 3))
Entrée : un entier n
Sortie : pgd(n)
k ←2
tant que n mod k 6= 0 et k ≤ n/k : k ← k + 1
si k > n/k retourner 1 sinon retourner n/k
Outils mathématiques 14 de 27
Analyse des trois algorithmes
Calcul des complexités temporelles pratiques des solutions (1), (2) et (3) :
Leurs formulations sont du type :
A1
tant que C : A2
A3
Pour un algorithme donné, soient t1 , tC , t2 et t3 les temps d’exécution
respectifs des actions A1 , C , A2 et A3 .
Hypothèse : la boucle représentée en machine par un branchement
conditionnel et un branchement inconditionnel ; temps d’exécution
respectifs : tBC et tBI .
Le temps d’exécution est donc :
t1 + (tBC + tC + t2 + tBI )B(n) + tC + tBC + t3 ,
où B(n) est le nombre de boucles exécutées.
Outils mathématiques 14 de 27
Analyse des trois algorithmes
Calcul des complexités temporelles pratiques des solutions (1), (2) et (3) :
Leurs formulations sont du type :
A1
tant que C : A2
A3
Pour un algorithme donné, soient t1 , tC , t2 et t3 les temps d’exécution
respectifs des actions A1 , C , A2 et A3 .
Hypothèse : la boucle représentée en machine par un branchement
conditionnel et un branchement inconditionnel ; temps d’exécution
respectifs : tBC et tBI .
Le temps d’exécution est donc :
t1 + (tBC + tC + t2 + tBI )B(n) + tC + tBC + t3 ,
où B(n) est le nombre de boucles exécutées.
Outils mathématiques 14 de 27
Analyse des trois algorithmes
Calcul des complexités temporelles pratiques des solutions (1), (2) et (3) :
Leurs formulations sont du type :
A1
tant que C : A2
A3
Pour un algorithme donné, soient t1 , tC , t2 et t3 les temps d’exécution
respectifs des actions A1 , C , A2 et A3 .
Hypothèse : la boucle représentée en machine par un branchement
conditionnel et un branchement inconditionnel ; temps d’exécution
respectifs : tBC et tBI .
Le temps d’exécution est donc :
t1 + (tBC + tC + t2 + tBI )B(n) + tC + tBC + t3 ,
où B(n) est le nombre de boucles exécutées.
Outils mathématiques 14 de 27
Analyse des trois algorithmes
Calcul des complexités temporelles pratiques des solutions (1), (2) et (3) :
Leurs formulations sont du type :
A1
tant que C : A2
A3
Pour un algorithme donné, soient t1 , tC , t2 et t3 les temps d’exécution
respectifs des actions A1 , C , A2 et A3 .
Hypothèse : la boucle représentée en machine par un branchement
conditionnel et un branchement inconditionnel ; temps d’exécution
respectifs : tBC et tBI .
Le temps d’exécution est donc :
t1 + (tBC + tC + t2 + tBI )B(n) + tC + tBC + t3 ,
où B(n) est le nombre de boucles exécutées.
Outils mathématiques 15 de 27
Analyse des trois algorithmes
Retenir
Sur une machine où les opérations sur les entiers s’effectuent en
temps constant, le temps d’exécution est donc de la forme :
a B(n) + b
où a et b sont des constantes.
Borne maximale :
Pour les solution (1) et (2) B(n) ≤ n√
−2
Pour la solution (3) B(n) ≤ b nc − 1
Complexité temporelle maximale :
Pour les solution (1) et (2) a0 n√
+ b0
Pour la solution (3) a0 b nc + b 0
Outils mathématiques 15 de 27
Analyse des trois algorithmes
Retenir
Sur une machine où les opérations sur les entiers s’effectuent en
temps constant, le temps d’exécution est donc de la forme :
a B(n) + b
où a et b sont des constantes.
Borne maximale :
Pour les solution (1) et (2) B(n) ≤ n√
−2
Pour la solution (3) B(n) ≤ b nc − 1
Complexité temporelle maximale :
Pour les solution (1) et (2) a0 n√
+ b0
Pour la solution (3) a0 b nc + b 0
Outils mathématiques 16 de 27
En pratique
Voici les temps d’exécution mesurés pour quelques nombres à la
fois premiers et proches de puissances de 10 :
n solution 1 solution 2 solution 3
101 0,000 000 6s 0,000 000 7s 0,000 000 3s
100003 0,000 427 s 0,000 425 s 0,000 003 s
10000019 0,045 s 0,044 s 0,000 031 s
1000000007 4.47 s 4.56 s 0,000 308 s
Outils mathématiques 17 de 27
Opération élémentaire
On cherche à définir une notion de compléxité robuste :
indépendante de l’ordinateur, du compilateur, du langage de
programmation, etc.. Exprimée en fonction de la Taille de la
donnée à traiter.
Retenir (opération élémentaire)
Opération qui prend un temps constant (ou presque).
Outils mathématiques 17 de 27
Opération élémentaire
On cherche à définir une notion de compléxité robuste :
indépendante de l’ordinateur, du compilateur, du langage de
programmation, etc.. Exprimée en fonction de la Taille de la
donnée à traiter.
Retenir (opération élémentaire)
Opération qui prend un temps constant (ou presque).
Outils mathématiques 18 de 27
Complexité d’un algorithme
Cout de A sur x : l’exécution de l’algorithme A sur la donné x
requiert CA (x) opérations élémentaires.
Définitions (Cas le pire, cas moyen)
n désigne la taille de la donnée à traité.
Dans le pire des cas : CA (n) := max CA (x)
x |x|=n
Moy
X
En moyenne : CA (n) := pn (x)CA (x)
x |x|=n
pn : distribution de probabilité sur les données de taille n.
Outils mathématiques 19 de 27
Notations asymptotiques
Les constantes n’importent pas !
Définition (notations asymptotiques)
Soit g : N 7→ R+ une fonction positive.
O(g ) est l’ensemble des fonctions positives f pour lesquelles il
existe une constante positive α et un rang n0 tels que :
f (n) ≤ αg (n), pour tout n ≥ n0 .
Ω(g ) est l’ensemble des fonctions positives f pour lesquelles il
existe une constante positive α et un rang n0 tels que :
f (n) ≥ αg (n), pour tout n ≥ n0 .
Θ(g ) = O(g ) ∩ Ω(g ).
Outils mathématiques 20 de 27
Par commodité, les expressions « image » des fonctions sont
souvent utilisées dans les notations plutôt que leurs symboles. On
écrit ainsi « f (n) ∈ X (g (n)) » plutôt que « f ∈ X (g ) », où X
signifie O, Ω ou Θ.
Par commodité toujours, on écrit souvent « est » plutôt que « ∈ »
et on dit souvent « est » plutôt que « appartient ».
Exemple
notations asymptotiques (1/2)
n ∈ O(n) n ∈ Ω(n) n ∈ Θ(n)
7 + 1/n ∈ O(1) 7 + 1/n ∈ Ω(1) 7 + 1/n ∈ Θ(1)
log2 n ∈ O(log n) log2 n ∈ Ω(log n) log2 n ∈ Θ(log n)
n + ln n ∈ O(n) n + ln n ∈ Ω(n) n + ln n ∈ Θ(n)
n2 + 3n ∈ O(n3 ) n2 + 3n ∈/ Ω(n3 ) n2 + 3n ∈/ Θ(n3 )
Outils mathématiques 20 de 27
Par commodité, les expressions « image » des fonctions sont
souvent utilisées dans les notations plutôt que leurs symboles. On
écrit ainsi « f (n) ∈ X (g (n)) » plutôt que « f ∈ X (g ) », où X
signifie O, Ω ou Θ.
Par commodité toujours, on écrit souvent « est » plutôt que « ∈ »
et on dit souvent « est » plutôt que « appartient ».
Exemple
notations asymptotiques (1/2)
n ∈ O(n) n ∈ Ω(n) n ∈ Θ(n)
7 + 1/n ∈ O(1) 7 + 1/n ∈ Ω(1) 7 + 1/n ∈ Θ(1)
log2 n ∈ O(log n) log2 n ∈ Ω(log n) log2 n ∈ Θ(log n)
n + ln n ∈ O(n) n + ln n ∈ Ω(n) n + ln n ∈ Θ(n)
n2 + 3n ∈ O(n3 ) n2 + 3n ∈/ Ω(n3 ) n2 + 3n ∈/ Θ(n3 )
Outils mathématiques 21 de 27
On cherche toujours à exprimer toute notation asymptotique à
l’aide de fonctions de référence : constante, somme, produit,
puissance, logarithme, minimum, maximum...
Définitions (désignations des complexités courantes)
notation désignation notation désignation
Θ(1) constante Θ(n2 ) quadratique
√ n)
Θ(log logarithmique Θ(n3 ) cubique
Θ( n) racinaire Θ(nk ), k ∈ N, k ≥ 2 polynomiale
Θ(n) linéaire Θ(an ), a > 1 exponentielle
Θ(n log n) quasi-linéaire Θ(n!) factorielle
Exemple
Suite aux résultats précédents, on peut énoncer que le problème du
calcul du plus grand diviseur peut se résoudre en temps au plus
racinaire avec un espace constant.
Outils mathématiques 21 de 27
On cherche toujours à exprimer toute notation asymptotique à
l’aide de fonctions de référence : constante, somme, produit,
puissance, logarithme, minimum, maximum...
Définitions (désignations des complexités courantes)
notation désignation notation désignation
Θ(1) constante Θ(n2 ) quadratique
√ n)
Θ(log logarithmique Θ(n3 ) cubique
Θ( n) racinaire Θ(nk ), k ∈ N, k ≥ 2 polynomiale
Θ(n) linéaire Θ(an ), a > 1 exponentielle
Θ(n log n) quasi-linéaire Θ(n!) factorielle
Exemple
Suite aux résultats précédents, on peut énoncer que le problème du
calcul du plus grand diviseur peut se résoudre en temps au plus
racinaire avec un espace constant.
Outils mathématiques 21 de 27
On cherche toujours à exprimer toute notation asymptotique à
l’aide de fonctions de référence : constante, somme, produit,
puissance, logarithme, minimum, maximum...
Définitions (désignations des complexités courantes)
notation désignation notation désignation
Θ(1) constante Θ(n2 ) quadratique
√ n)
Θ(log logarithmique Θ(n3 ) cubique
Θ( n) racinaire Θ(nk ), k ∈ N, k ≥ 2 polynomiale
Θ(n) linéaire Θ(an ), a > 1 exponentielle
Θ(n log n) quasi-linéaire Θ(n!) factorielle
Exemple
Suite aux résultats précédents, on peut énoncer que le problème du
calcul du plus grand diviseur peut se résoudre en temps au plus
racinaire avec un espace constant.
Outils mathématiques 22 de 27
Aucun progrès technologique (modèle de machine standard) ne
permet à un algorithme de changer de classe de complexité.
Exemple (tyranie de la complexité)
Effets de la multiplication de la puissance d’une machine par 10,
100 et 1000 sur la taille maximale N des problèmes que peuvent
traiter des algorithmes de complexité donnée :
Outils mathématiques 22 de 27
Aucun progrès technologique (modèle de machine standard) ne
permet à un algorithme de changer de classe de complexité.
Exemple (tyranie de la complexité)
Effets de la multiplication de la puissance d’une machine par 10,
100 et 1000 sur la taille maximale N des problèmes que peuvent
traiter des algorithmes de complexité donnée :
complexité ×10 ×100 ×1000
Θ(log n) N 10 N 100 N 1000
√
Θ( n) 102 N 104 N 106 N
Θ(n) 10 N 100 N 1000 N
Θ(n log n) < 10 N < 100 N < 1000 N
Θ(n2 ) ' 3N 10 N ' 32 N
Θ(n3 ) ' 2N ' 5N 10 N
Θ(2n ) 'N +3 'N +7 ' N + 10
Outils mathématiques 23 de 27
Propriétés des notations asymptotiques
Proposition
Soient f , g , h, l des fonctions positives et a, b ∈ R+ .
X désigne n’importe lequel des opérateur O, Ω ou Θ
Si f ∈ X (g ) et g ∈ X (h) alors f ∈ X (h) ;
Si f , g ∈ X (h) alors af + bg ∈ X (h) ;
Si f ∈ X (h) et g ∈ X (l ) alors fg ∈ X (hl ) ;
Si f ∈ Ω(h) alors pour tout g on a af + bg ∈ Ω(h) ;
Outils mathématiques 24 de 27
Cas des polynômes
Proposition
Un polynôme est de l’ordre de son degré. Plus précisément si
d
X
P= ci x i
i=0
avec cd 6= 0 (c’est-à-dire que d est le degré de P) alors
P ∈ Θ(x d )
Par exemple, 5x 3 + 3x 2 + 100x + 12 ∈ Θ(x 3 ) .
Outils mathématiques 25 de 27
Récapitulatif
Complexité Vitesse Temps Formulation Exemple
Factorielle très lent proportionnel N! Résolution par recherche exhaus-
à NN tive du problème du voyageur de
commerce.
Exponentielle lent proportionnel KN Résolution par recherche exhaus-
à une tive du Rubik’s Cube.
constante
à la puissance
N
Polynomiale moyen proportionnel NK Tris par comparaison, comme le tri
à N à une à bulle (N 2 ).
puissance
donnée
Quasi-linéaire assez rapide intermédiaire N log(N) Tris quasi-linéaires, comme le
entre linéaire Quicksort.
et polynomial
Linéaire rapide proportionnel N Itération sur un tableau.
àN
Logarithmique très rapide proportionnel log(N) Recherche dans un arbre binaire.
au logarithme
de N
Constante le plus rapide indépendant 1 recherche par index dans un ta-
de la donnée bleau.
Outils mathématiques 26 de 27
Calcul de complexité dans les structures de contrôle
Instructions élémentaires (affectations, comparaisons) sont en
temps constant, soit en Θ(1).
Tests : si a ∈ O(A), b ∈ O(B) et c ∈ O(C ) alors
(if a then b else c) ∈ O(A + max(B, C ))
Tests : si a ∈ Ω(A), b ∈ Ω(B) et c ∈ Ω(C ) alors
(if a then b else c) ∈ Ω(A + min(B, C ))
Outils mathématiques 27 de 27
Cas des boucles imbriquées
Boucles si ai ∈ O(Ai ) (idem Ω, Θ) alors
n
!
X
(for i from 1 to n do ai ) ∈ O (Ai )
i=1
Lorsque Ai est constant égal à A, on a
(for i from 1 to n do ai ) ∈ nO(A)
Retenir (Boucles imbriqués)
Cas particulier important : si Ai ∈ O(i k ) (idem Ω, Θ) alors
(for i from 1 to n do ai ) ∈ O(nk+1 )