CPGE-AGADIR MP-PSI-TSI

COMPLEXITE ALGORITHMIQUE

1. INTRODUCTION
Exercice
Ecrire en python une fonction qui prend en argument une chaîne de caractères et détermine si le caractère 'a' est
présent dans la chaîne (on retourne soit True soit False).

● Analysons plusieurs solutions :

Première solution Deuxième solution

def contienta1(chaine): def contienta2(chaine):

k=0 for i in range(len(chaine)):
N=len(chaine) if chaine[i]=='a':
trouve=False return True
while(trouve == False and k < return False
N):
if chaine[k]=='a':
trouve = True
k=k+1
return trouve

Troisième solution Quatrième solution

def contienta3(chaine): def contienta4 (chaine):

n=chaine.count('a') return ('a' in chaine)
return bool(n)

● Quelques questions:

1. que remarquez-vous concernant cet exercice?

2. Le Coûte le plus court ! Est-il meilleur?
3. Comment peut-on désigner le meilleur Coûte parmi ces quatre solutions?

2. DÉFINITION DE LA COMPLEXITÉ 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é?

Complexité 1 /13 M.GUEROIHI

3. TYPES DE COMPLEXITÉ
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 (en espace)
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.

4. 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 → ∞)
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 remarque 3n+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 n0 qui 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:

Complexité 2 /13 M.GUEROIHI

 2
Prouvons que la fonction : T(n)= n +3n est en O(n2)
But: trouver une constante c ∈ ℝ et un seuil n0∈ 𝑁*, à partir du quel 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

5. PROPRIÉTÉS DE LA NOTATION O :

✔ ∀ k ∈ ℝ, on a toujours k ∈ O(1). (P1)

✔ ∀ k ∈ ℝ, on a toujours k.f(x) ∈ O(f(x)) (P2)
Cette propriété implique la réflexivité de la notation grand O : f(x) ∈ O( f(x)).

✔ Si f1(x) ∈ O(g(x)) et f2(x) ∈ O(g(x)), alors (f1 + f2)(x) ∈ O(g(x)) (P3)

✔ Si f1(x) ∈ O(g1(x)) et f2(x) ∈ O(g2(x)), alors (f1 + f2)(x) ∈ O(max (g1(x), g2(x))) (P4)
✔ Si f1(x) ∈ O(g1(x)) et f2(x) ∈ O(g2(x)),, alors (f1 . f2)(x) ∈ O((g1(x). g2(x))) (P5)
✔ Si p > 0, alors log2 x ∈ O(xp) (P6)
✔ Si b >1, alors logb x ∈ O(log2 x) (Tous les logarithmes,∀ la base, croissent au
même rythme, à un facteur près) (P7)
✔ (Transitivité) : Si f(x) ∈ O(g(x)) et g(x) ∈ O(h(x)), alors f(x) ∈ O(h(x)) (P8)

✔ Si f(x) = an.xn + an−1.xn−1 + ⋯ + a1.x + a0 (où les ai sont tous des réels),
Alors f(x) ∈ O(xn) (P9)
Note :
Quand f(x) ∈ O(g(x)) et g(x) ∈ O(f(x)), on dit que f(x) et g(x) sont du même ordre (de la même
classe) et on écrit : f(x) ∈ θ(g(x))

6. 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

O(n) Linéaire
paramètre 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é par 4. 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
O(nk ) Polynômiale
voir des complexités en O(n3) ou O(n4).
quand le paramètre double, letemps d'exécution est élevé à la puissance k avec k
O(kn) Exponentielle
> 1.

O(n!) Factorielle asymptotiquement équivalente à nn

Complexité 3 /13 M.GUEROIHI

7. COMPARAISON DE TEMPS D'EXECUTION
● Prenons un ordinateur, dont la vitesse du microprocesseur est 1GHz (c.à.d. il exécute un milliard d'opérations
par seconde), et imaginons des algorithmes qui effectuent un traitement donné dans un temps T(N).
● Nous donnons ci-dessous un tableau des ordres de grandeur des temps d'exécution que l'on peut espérer
pour N éléments suivant la complexité de l'algorithme.

8. 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 : + ; - ; * ; / ; %
Le coût d'une opération élémentaire est é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
✔ Opération composée
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)= ∑(𝐶𝑜û𝑡(𝑐𝑜𝑚𝑝𝑎𝑟𝑎𝑖𝑠𝑜𝑛) + 𝐶𝑜û𝑡(𝑥𝑖))

Complexité 4 /13 M.GUEROIHI

 ● 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

Coût(C) =1 + ∑(𝐶𝑜û𝑡(𝑖 <= 𝑛) + 𝐶𝑜û𝑡(𝑠𝑜𝑚𝑚𝑒 = 𝑠𝑜𝑚𝑚𝑒 + 𝑖) + 𝐶𝑜û𝑡(𝑖 = 𝑖 + 1))

= 1+n+2n+2n
= 1+5n

c. Principe pour calculer la complexité d'un algorithme

La mesure de complexité d'un algorithme consiste à évaluer le temps d'exécution de cet algorithme.
Dans l'évaluation de ce temps d'exécution (coût), on sera amené à suivre les étapes suivantes:
● Déterminer les opérations élémentaires (OE) à prendre en considération : coût T(OE).
● Calculer le nombre d'instructions effectuées par les opérations composées(OC) : coût T(OC).
● Préciser les instructions à négliger.
● Le coût de l'algorithme T(Alg) est la somme des deux coûts T(OE) et T(OC) : T(Alg)= T(OE) + T(OC)

d. 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, le degré de précision qu'ils requièrent est souvent inutile;
● On aura donc recours à une approximation de ce temps de calcul, représenté par la notation O(.);

e. 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;

3
o On remplace les constantes multiplicatives par 1 : 1n - 1n2 + 1n +3
o On annule les constantes additives : n3 - n2 + n + 0
o On garde le terme de plus haut degré : n3 + 0
3
Et on a donc : T(n) = O(n ).

Complexité 5 /13 M.GUEROIHI

Complexité 6 /13 M.GUEROIHI
 ● Justification des simplifications
● Les processeurs actuels effectuent plusieurs milliards d'opérations à la seconde;

1. qu'une affectation requière 2 ou 4 unités de temps ne change donc pas grand-chose ; d'où le
remplacement des constantes par des 1 pour les multiplications.

2. un nombre constant d'instructions est donc aussi négligeable par rapport à la croissance de la taille des
données ; d'où l'annulation des constantes additives.

3. pour de grandes valeurs de n, le terme de plus haut degré l'emportera ; d'où l'annulation des termes
inférieurs
● On préfère donc avoir une idée du temps d'exécution de l'algorithme plutôt qu'une expression plus précise
mais inutilement compliquée;

f. Exemples de calcul de complexité

Exemple 1 Exemple 2

● La fonction suivante permet de retourner le La fonction suivante permet de retourner la somme des
quotient et le reste de la division d’un nombre éléments d’une liste:
entier a par b.
def Somme(L):
def division (a ,b): s=0
q=a//b for i in rang(len(L)) :
r=a%b s=s+L[i]
return(q,r) return s
● Exemple Exemple
>>> x , y = 10 , 3 >>> L =[1, 2, 8, 4]
>>> division(x , y) >>>Somme(L)
3 , 1 15
● Le nombre d'opérationsest:5 ● Le paramètre de complexité est la taille de laliste
● Temps de calcul est constant d'entrée L.
● Complexité: O(1) ● en fixant i on exécute 2 opérations: (addition et
affectation)
● Nombre de fois d'exécution de ces 2 opérations
est: len(T)
● Len ombre total d'opérations est : 4 * len(L) + 3
● Complexité: O(len(L))= O(n)

Exemple 3 : remplir un tableau Exemple 4 : remplir une matrice

def RemplirTab (T): def RemplirMat(M):

n=len(M)
for i in range(len(T)):
p=len(M[0])
print("T[",i, "]=",end=' ')
for i in range(n):
T[i]=int(input()) for j in range(p):
● Le paramètre de complexité est la taille du print("T[",i,"][",j,"]=")
tableau d'entrée T. T[i][j]=int(input())
● en fixant i on exécute 4 opérations: (print, input,
● Coût pour saisir une valeur est : 4
int et affectation)
● Le nombre d'itérations de la boucle sur j pour i
● Nombre de fois d'exécution de ces 4 opérations
fixé égal à : p
est: len(T)
● Le nombre total pour lire toutes les valeurs pour
● Le nombre total d'opérations est : 4 * len(T)
i fixé égal à 4p
● Complexité: O(len(T))= O(n)
● Le nombre total d'opérations est : 2 +4p.n
● Complexité : O(n.p)

Complexité 7 /13 M.GUEROIHI

 Exemple 5 : Produit matriciel

def prodMatrice(A,B):
n=len(A) #nombre de lignes de A
m=len(A[0]) #nombre de colonne de A
p=len(B[0]) #nombre de colonnes de B
C=[p*[0] for i in range(n)]
for i in range(0,n):
for j in range (0,p):
s=0;
for k in range (0,m):
s = s + A[i][k]*B[k][j]
C[i][j]=s
return C
● On suppose que A et B sont deux matrices carrées d'ordre n = m = p
● Coût pour calculer une valeur de s est : 3 (produit, addition et affectation)
● Le nombre d'itérations de la boucle sur k pour j fixé égal à m = n
● Le nombre d'itérations de la boucle sur j pour i fixé égal à p = n
● Le nombre total d'opérations est : T(n)=4+ n + n(n(2+n(3))
● Complexité: O(n3)

Exemple6 : Tri par sélection

def TriSelection(T):
n=len(T)
for i in range(n-1):
Posmin=i
for j in range(i+1,n):
ifT[j] < T[Posmin]:
Posmin=j
#Permutation
T[i] , T[Posmin] = T[Posmin] , T[i]
● Coût des échanges:
o Le tri par sélection sur n nombres fait n-1 échanges, ce qui fait : 3(n- 1) affectations
● Coûtdesrecherchesde minimum:
o On recherche le minimum parmi n éléments : au plus 3(n -1) opérations. (c'est le nombre
d'itérations de la boucle sur j pour i fixé égal à n- 1)
o On recherche le minimum parmi n-1 éléments : au plus 3(n-2) opérations. (c'est le nombre
d'itérations de la boucle sur j pour i fixé égal à n-2)
o On recherche en suite le minimum parmi n-2 éléments: 3(n-3)tests.
o ...
● Le nombre total de tests est : 3(1+2+3+ … +(n- 2)+(n -1))=3( (n- 1)n)/2
● Le nombre total d'opérations est : 3(n- 1) + 3((n- 1)n)/2
● Donc, la complexité est quadratique : O(n2)

Complexité 8 /13 M.GUEROIHI

 Exemple 7 : recherches séquentielle
def Recherche_Seq(T,x):
i=0
n=len(T)
for i in range(n):
if T[i]==x :
return True
return False
● Le nombre d'opérations avant for est : 3
● La boucle for contient 2 opérations: (test et return True)
● Le nombre de fois d'exécution de ces 2 instructions dans le pire de cas est n
● Le nombre d'opérations après la boucle for est : 1(return False)
● Le nombre d'opérations total est : 3+2n+1
● Complexité : O(n)

Exemple 8 : Recherche dichotomique

def RechDichotomique(T,x):
g,d=0,len(T)-1
while g<=d:
m=(g+d)//2
ifT[m]==x: return True
if T[m]<x:
g=m+1
else:
d=m-1
return False
● Soit k le nombre de passages dans la boucle while.
● on divise le nombre d'éléments restants par 2 jusqu'à ce qu'il n'en reste qu'un (k divisions)
((((n/2)/2)/2)/…./2)=1
● Donc n/2k =1 et ainsi k=log2n
● Complexité: O(log2(n))

Complexité 9 /13 M.GUEROIHI

 Exemple9 : Recherche d'un mot dans une chaîne de caractères
Le principe est le même que pour la recherche d'un caractère dans une chaîne mais ici il est nécessaire d'ajouter une
boucle "while" pour tester tous les caractères du mot.
def searchWord (mot, texte):
n = len(texte)
m = len(mot)
if m > m : return False
for i in range(1+ n-m):
j=0
while j < len(mot)and mot[j ]== texte[i+j]:
j=j+1
if j == len(mot): return i
return None
● Le programme va chercher le mot à toutes les places possibles et va tester tous les caractères du mot
● Le nombre d'opérations total est de l'ordre de m(1+ n - m) où m est la longueur du mot et n la longueur du
texte
● En particulier le maximum est atteint pour m = n/2 et on obtient (n2+2n)/4
● Donc la complexité de l'algorithme est O(n2)

Exemple.10 : les tours de Hanoï

def hanoi ( n , A='A' , B='B', C='C'):

if n > 0:
hanoi(n-1, A, C, B)
print("Déplacer le disque %d de la tige %s vers la tige %s."% (n, A, C))
hanoi(n-1, B, A, C)

● L'évaluation de la complexité de cet algorithme est assez simple. Nous allons chercher à savoir combien de
déplacements de disques sont nécessaires pour arriver à nos fins. Très simplement, la fonction calculant ceci
peut être définie de la manière suivante (on peut se baser sur la fonction ci-dessus) :
● T(0) = 0; T(1) = 1; T(n) = 2*T(n-1)+1. On peut démontrer par récurrence que ceci est égal à T(n) = 2n-1 :
● On a T(n+1) = 2*T(n)+1. En supposant que T(n) = 2n-1, on a T(n+1) = 2*(2n-1)+1. On développe ensuite en
T(n+1) = 2*2n -2+1 ce qui nous donne au final T(n+1) = 2n+1-1. On a ainsi démontré que si c'est vrai pour n,
alors c'est vrai pour (n+1). Comme on a T(1) = 2*0+1 = 21-1 = 1, c'est vrai pour tous les n supérieurs à 1. La
complexité exacte de l'algorithme présenté ci-dessus est donc en 2n-1 pour n disques à déplacer de la tour
● On trouve T(n)=2n - 1
● Donc lacomplexité est éxponentielle O(2n)

Complexité 10 /13 M.GUEROIHI

9. DIFFÉRENTES NUANCES DE COMPLEXITÉ
● Il est fréquent que la complexité en temps soit améliorée au prix d'une augmentation de la complexité en
espace, et vice-versa.
● La complexité dépend notamment:
o De la puissance de la machine sur la quelle l'algorithme est exécuté,
o Du langage et interpréteur (ou compilateur) utilisé pour coder l'algorithme,
o Pour des données de même taille, un algorithme n'effectue pas nécessairement le même nombre
d'opérations élémentaires.
● Pour ce la, on distingue 3 types de complexités:
1- Complexité au pire des cas.
2- Complexité dans le meilleur des cas.
3- Complexité en moyenne des cas.
9-1 : Complexité au pire des cas
La complexité au pire est le plus grand nombre d'opérations qu'aura à exécuter l'algorithme sur un jeu de
données de taille fixée à n.
Tmax(n)= max{C(d)}
d∈Dn
- Avec Dn l'ensemble des données de taille n
- C(d) est le coût d'exécution de l'algorithme sur la donnée d de taille n.
Exemple : Recherche d'un élément dans un tableau
def find(T,x): On note n la longueur du tableau T(n=len(T)).
for e in T:
Dans le pire des cas : quand l'élément recherche x est le dernier (dans
if e==x:
la case n-1) ou est absent.
return True
return False Donc la complexité dans le pire est Cmax (n)= n

9-2 : Complexité dans le meilleur des cas

La complexité au meilleur est le plus petit nombre d'opérations qu'aura à exécuter l'algorithme sur un jeu de
données de taille fixée. C'est une borne inferieure de la complexité de l'algorithme sur un jeu de données de
taille n.
Tmin(n)= min{C(d)}
d∈Dn
Exemple: Recherche d'un élément dans un tableau
On considère le même exemple précédent.
Dans le meilleur des cas : quand l'élément recherche x se trouve en 1ere position.
Donc la complexité dans le meilleur des cas est Cmin(n)=1
9-3 : Complexité en moyenne des cas
La complexité en moyenne est la moyenne des complexités de l'algorithme sur des jeux de donnes de taille n. Cette
complexité en moyenne reflète le comportement "général" de l'algorithme si les cas extrêmes sont rares ou si la
complexité varie peu en fonction des données.

Tmoy (n)={ ∑ 𝑃𝑟(𝑑). 𝐶(𝑑), 𝑑 ϵ 𝐷𝑛 }

Où Pr(d) est la probabilité d'avoir la donnée d en entrée de l'algorithme.

Exemple : Recherche d'un élément dans un tableau
En moyenne, dans l'hypothèse ou la probabilité de trouver x dans le tableau est q et si x est présent, il peut se
trouver dans n'importe quelle case avec la même probabilité, à savoir 1/n
Alors la probabilité que x se trouve dans la ième case est : q * 1/n , d'où:
Cmoy (n)= q *(1/n + 2/n + 3/n + …+ n/n) + (1-q)*n = q(n+1)/2 + n(1-q)

Complexité 11 /13 M.GUEROIHI

Si q=1, la complexité en moyenne des cas sera Cmoy (n)= (n+1)/2

Complexité 12 /13 M.GUEROIHI

10. COMPLEXITÉ ET RÉCURSIVITÉ
Il existe diverses techniques pour la résolution des équations de récurrence.
● méthode des fonctions génératrices et décomposition des fractions rationnelles
● Transformée en Z
● …

Résolution des récurrences.

❖ C(n) = C(n-1) + b
● solution : C(n) = c(0) + b*n = O(n)
● exemples : factorielle, recherche séquentielle récursive dans un tableau

❖ C(n) = a*C(n-1) + b, a ≠ 1
● solution : C(n) = an*(C(0) – b/(1-a)) + b/(1-a) = O(an)
● exemples : répétition a fois d'un traitement sur le résultat de l'appel récursif

❖ C(n) = C(n-1) + a*n + b

● solution : C(n) = c(0) + a*n*(n+1)/2 + n*b = O(n2).
● exemples : traitement en coût linéaire avant l'appel récursif, tri à bulle

❖ C(n) = C(n/2) + b
● solution : C(n) = C(1) + b*log2(n) = O(log(n))
● exemples : élimination de la moitié des éléments en temps constant avant l'appel récursif, recherche
dichotomique récursive

❖ C(n) = a*C(n/2) + b, a ≠ 1
● solution : C(n) = nlog2(a) *(c(1) – b/(1-a)) + b/(1-a) = O(nlog2(a))
● exemples : répétition a fois d'un traitement sur le résultat de l'appel récursif dichotomique

❖ C(n) = C(n/2) + n
● solution : C(n) = O(n)
● exemples : traitement linéaire avant l'appel récursif dichotomique

❖ C(n) = 2*C(n/2) + a*n + b

● solution : C(n) = O(n*log(n))
● exemples : traitement linéaire avant double appel récursif dichotomique, tri fusion

Complexité 13 /13 M.GUEROIHI