Lycée Moulay ABDELLAH MP & 2TSI
Centre de CPGE –Safi - Informatique
Année2015/2016
LA COMPLEXITE
1. DEFINITION DE LA COMPLEXITE D'UN ALGORITHME
La complexité d'un problème mathématique P est une mesure de la quantité de ressources nécessaires à la
résolution du problème P.
Cette mesure est basée sur une estimation du nombre d'opérations de base effectuées par l'algorithme en
fonction de la taille des données en entrée de l'algorithme.
Généralement, pour le même problème P, on peut trouver plusieurs algorithmes (Alg1; Alg2;...;Algn).
L'objectif de la complexité est d'évaluer le coût d'exécution de chaque algorithme afin de choisir le meilleur.
Problème:
Comment évaluer le coût d'exécution d'un algorithme donné?
2. TYPES DE COMPLEXITE
En fonction des ressources utilisées pour évaluer la complexité d'un algorithme, on sera amené à distinguer deux
types de complexité: complexité temporelle et complexité spatiale.
Complexité temporelle (en temps)
La complexité temporelle d'un algorithme est le nombre d'opérations élémentaires (affectations, comparaisons,
opérations arithmétiques) effectuées par un algorithme.
Complexité spatiale (enespace)
La complexité en mémoire donne le nombre d'emplacements mémoires occupés lors de l'exécution d'un
programme.
Remarque : Dans ce cours, nous nous intéressons uniquement à la complexité temporelle.
3. LA NOTATION O :(Complexité asymptotique)
Définition
Soit T(n) une fonction qui désigne le temps de calcul d'un algorithme A.
On dit que T(n) est en grand O de f(n): T(n)= O(f (n)) si et seulement si:
n0∈ ℕ*, c ∈ ℝ, n >= n0 :T(n) <= c *f (n).
La notation O(f (n)) est aussi appelée Notation de Landau : (Complexité asymptotique) (i.e.quand n → ∞)
1
Lycée Moulay ABDELLAH MP & 2TSI
Centre de CPGE –Safi - Informatique
Année2015/2016
Exemples
Exemple1:
Prouvons que la fonction T(n)=3n +6 est en O(n) (on écrit aussi 3n +6∈O(n))
But: trouver une constante c ∈ℝet un seuil n0∈ ℕ*, à partir du quel T(n) <c.n
On remarque3n+6<9n si n>2
3*2+6 <9*2
3*3+6 <9*3
3*4+6 <9*4 On déduit donc que c=9 fonctionne à partir d’un seuil n0=2
3*5+6 <9*5
.
.
.
Remarque:
On ne demande pas d'optimisation (le plus petit c ou n0qui fonctionne), juste de donner des valeurs qui
fonctionnent;
c =10 et n0 =5 est donc aussi acceptable;
3*5+6 <10*2
3*6+6 <10*3
3*7+6 <10*4
Exemple2:
Prouvons que la fonction : T(n)= n2 +3n est en O(n2)
But: trouver une constante c ∈ℝet un seuil n0∈ ℕ*, à partir duquel T(n) <c.n
Cherchons d'abord la constante c ; c =1 ne peut pas marcher, essayons donc c =2;
On doit alors trouver un seuil n0∈ ℕ*, à partir du quel :n2 +3n <=2n2
On remarque n2 +3n <=2n2 si n>3
On déduit donc que c=2 fonctionne à partir d’un seuil n0=3
4. CLASSES DE COMPLEXITE LES PLUS USUELLES
On voit souvent apparaître les complexités suivantes:
Complexité Nom courant Description
O(1) Constante Le temps d'exécution ne dépend pas des données traitées, ce qui est assez rare!
O(log(n)) Logarithmique augmentation très faible du temps d'exécution quand le paramètre croit.
augmentation linéaire du temps d'exécution quand le paramètre croit(si le paramètre
O(n) Linéaire
double, le temps double).
O(nlog(n)) Quasi-linéaire augmentation un peu supérieure à O(n)
quand le paramètre double, le temps d'exécution est multiplié par4. Exemple:
O(n2) Quadratique
algorithmes avec deux boucles imbriquées.
ici, nk est le terme de plus haut degré d'un polynôme en n ; il n'est pas rare de voir des
O(nk ) Polynômiale
complexités en O(n3) ou O(n4).
O(kn) Exponentielle quand le paramètre double, letemps d'exécution est élevé à la puissance k avec k > 1.
O(n!) Factorielle asymptotiquement équivalente à nn
2
Lycée Moulay ABDELLAH MP & 2TSI
Centre de CPGE –Safi - Informatique
Année2015/2016
5. COMMENT MESURER LA COMPLEXITE D'UN ALGORITHME
a. Le coût des instructions élémentaires
Opération élémentaire.
On appelle opération de base, ou opération élémentaire, toute:
Affectation;
Test de comparaison: ==;<;<=;>=;!=
Opération de lecture(input)et d’écriture (print);
Opération arithmétique:+;- ; *;/ ; %
Lecoûtd'uneopération élémentaireest égal à 1.
Exemple1: Que vaut le coût de l'algorithme A
somme = n +1 #instr1
somme = somme * n #instr2
somme = somme/2 #instr3
Coût(A) =Coût(inst1)+Coût(instr2)+Coût(instr3)
= 2 +2+2
=6
b. Le coût des instructions composées
On appelle opération composée, toute instruction contenant:
L'exécution d'une instruction conditionnelle :
Si (test) alors
Q1
Sinon
Q2
Finsi
Le nombre d'opérations est: Coût(P) = Coût (test)+ max (Coût(Q1),Coût(Q2))
L'exécution d'une boucle : est égal à la multiplication de nombre de répétitions par la somme du coût
de chaque instruction xi du corps de la boucle;
Coût (bouclefor)= ∑ 𝐂𝐨û𝐭(𝐱𝐢)
Coût(boucle while)= ∑(𝐂𝐨û𝐭(𝐜𝐨𝐦𝐩𝐚𝐫𝐚𝐢𝐬𝐨𝐧) + 𝐂𝐨û𝐭(𝐱𝐢))
L'appel d'une fonction : Lorsqu'une fonction ou une procédure est appelée, le coût de cette fonction ou
procédure est le nombre total d'opérations élémentaires engendrées par l'appel de cette fonction.
Exemple2: Que vaut le coût de l'algorithme B
if i%2==0:
n=i//2
else:
i=i+1
n=i//2
Coût (B)=Coût(i%2==0)+max(Coût(n = i//2),Coût(i = i +1 , n = i//2))
= 2 + max(2,4) = 6
Exemple3: Que vaut le coût de l'algorithme C
i=1
while i <= n :
somme=somme+i
i=i+1
3
Lycée Moulay ABDELLAH MP & 2TSI
Centre de CPGE –Safi - Informatique
Année2015/2016
Coût(C)=𝟏 + ∑(𝐂𝐨û𝐭(𝐢 <= 𝒏) + 𝑪𝒐û𝒕(𝒔𝒐𝒎𝒎𝒆 = 𝒔𝒐𝒎𝒎𝒆 + 𝒊) + 𝑪𝒐û𝒕(𝒊 = 𝒊 + 𝟏))
=1+n+2n+2n =1+5n
c. La notation O :motivation
Les calculs à effectuer pour évaluer le temps d'exécution d'un algorithme peuvent parfois être longs et
pénibles;
De plus, ledegré de précision qu'ils requièrent est souvent inutile;
Onauradoncrecours à une approximation decetempsdecalcul,représenté parla notation O(.);
d. Règles de calcul : simplifications
On calcule le temps d'exécution comme avant, mais on effectue les simplifications suivantes:
o On oublie les constantes multiplicatives (elles valent 1);
o On annule les constantes additives;
o On ne retient que les termes dominants;
Exemple (simplifications)
Soit un algorithme effectuant T(n) = 4n3 - 5n2 +2n +3 opérations;
o On remplace les constantes multiplicatives par 1 : 1n3 - 1n2 + 1n +3
o On annule les constantes additives : n3 - n2 + n +0
o On garde le terme de plus haut degré : n3 + 0
Et on a donc : T(n)= O(n3).
