ITC - MPSI 2023-2024
R APPELS SUR LA COMPLEXITÉ
L’analyse de la complexité d’un algorithme est l’étude de la consommation en ressource (en géné-
ral en temps de calcul ou en espace mémoire utilisé) de l’algorithme.
Définition 0.0.1. La complexité en temps d’un algorithme est la mesure du temps de calcul exprimée
comme fonction de la taille de l’entrée de l’algorithme. On parle de temps de calcul, mais de façon
équivalente, on compte usuellement le nombre d’opérations effectuées par l’algorithme.
• On calcule généralement la complexité dans le pire cas, mais on peut également calculer la
complexité en moyenne ; dans tous les cas, on essaye de donner une borne supérieure de la
complexité ;
• On s’intéresse au comportement asymptotique en fonction de la taille de l’entrée ;
• Toutes les opérations ne sont pas équivalentes. Par exemple, une multiplication est plus coû-
teuse qu’une addition, ou qu’une affectation de valeur à une variable ;
• Il existe encore d’autres façons d’évaluer la complexité d’un algorithme : par exemple, la com-
plexité amortie, le calcul par agrégation ou encore la méthode du potentiel. Nous y reviendrons
(ou pas), ces notions étant plutôt hors-programme.
Définition 0.0.2. Soit f : N → N. On dit que f est de l’ordre de g : N → N, et on note f (n) = O(g (n)) si
∃k > 0, ∃n 0 ∈ N, ∀n ≥ n 0 , | f (n)| ≤ k × |g (n)|.
Cela signifie que la fonction g borne la fonction f à partir d’un certain rang. La notation O(g (n))
est appelée grand O de Landau.
Exemple 0.0.3. Prenons l’exemple du tri par insertion :
# T une liste ou un tableau de nombres .
for i in range (1 , n ) :
temp = T [ i ]
j = i-1
while j > 0 and T [ j ] > temp
T[j+1]=T[i]
i-=1
T [ j + 1 ] = temp
On itère n − 1 fois la boucle for. A chaque itération i de la boucle for, on parcourt, dans le pire cas, les i
premiers éléments. La complexité dans le pire cas est donc de l’ordre de n−1 2
P
i =1 (i − 1) = O(n )
Remarque : le pire cas est atteint quand la liste donnée en entrée est triée dans l’ordre décroissant
1
Exemple 0.0.4. Calculons la complexité de la recherche dichotomique d’un élément dans une liste
(triée).
def recherche_dicho (x , liste ) :
# entree : a un entier , l une liste d ’ entiers tries dans l ’ ordre croissant
# sortie : un booleen indiquant si a est dans l ou non
n = len ( liste )
if n = = 0 :
return False
elif n = = 1 :
return x = = liste [ 0 ]
else :
mediane = liste [ n // 2 ]
if x = = mediane : # si par chance on a i m m d i a t e m e n t t r o u v l ’ lment
, on renvoie true
return True
elif x > mediane : # si x est plus grand que la m d i a n e , alors on doit
le chercher dans la deuxieme
m o i t i de la liste
return recherche_dicho (x , liste [ n // 2 : ] )
else : # sinon , on le cherche dans la p r e m i r e m o i t i
return recherche_dicho (x , liste [ : n // 2 ] )
Soit T (n) le temps de calcul pour une liste de taille n. Alors T (n) = c + T ( n2 ) où c est une constante
correspondant aux différentes comparaisons effectuées. On considère ici que le slicing d’une liste se
fait en temps constant (ce qui dépend de l’implémentation de la liste, mais cela est vrai en Python en
complexité amortie au moins).
Soit k ∈ N tel que 2k−1 ≤ n ≤ 2k . Alors T (n) < T (2k ), et le calcul de T (2k ) se fait aisément par récurrence.
Pk
On montre alors que T (2k ) = T (1) + i =1 c = O(k) = O(log2 (n)) = O(log(n))
Nom Complexité en temps Exemple d’algorithme
Constant O(1) Affecter une variable
Logarithmique O(log(n)) Recherche dichotomique
Linéaire O(n) Recherche séquentielle
Linéarithmioque O(n log(n)) tri par fusion
Quadratique O(n 2 ) Tri par insertion
Cubique O(n 3 ) Multiplication (naïve) de matrices
Polynômial O(n k ) Test de primalité AKS
Exponentiel 2O(n) Problème du voyageur de commerce
Remarque 0.0.5. (extrêmement hors programme) Temps pseudo-polynômial : un algorithme naïf de
p
test de primalité d’un entier n nécessite n − 1 divisions, de sorte que l’algorithme est linéaire en la
valeur de n. Cependant, on calcule en fait la complexité en fonction de la taille de l’entrée et non sa
valeur. Ainsi, on doit ici la calculer en fonction de la taille de la représentation en machine de l’entier
n. Cet algorithme est dit-pseudo polynômial.
