CPGE-AL QALAM-AGADIR MP-PSI

COMPLEXITE ALGORITHMIQUE

 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 < N): return False
if chaine[k]=='a':
trouve = True
k=k+1
return trouve

Troisième solution Quatrième solution

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

n=[Link]('a') return ('a' in chaine)
return bool(n)

 Quelques questions:

1. Le code le plus court ! Est-il meilleur?

2. Comment peut-on désigner le meilleur code parmi ces quatre solutions?

 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é?

Complexité algorithmique -1/8 - M. GUEROIHI

 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.
a- 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.
Dans ce type de complexité on trouve:
 Complexité en meilleur cas : c'est la valeur minimale des opérations effectuées par l'algorithme
 Complexité en pire des cas : c'est la valeur maximale des opérations effectuées par l'algorithme
 Complexité en moyenne : c'est la valeur moyenne des opérations effectuées par l'algorithme
b- 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 en pire des cas.
 COMMENT MESURER LA COMPLEXITE D'UN ALGORITHME
a. 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:
 Compter le nombre d'opérations jugées significatives : noté C(n) ou T(n). où n est le nombre de données
 Simplification du cout pour déduire la complexité en O (notation asymptotique/Landau (Grand O)). On
ne s'intéresse qu'au cas où n est très grand.
b. Le coût des instructions
 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 : + ; - ; * ; / ; %
 Accès à un élément d’une liste, tuple ou chaine
Le coût d'une opération élémentaire est égal à 1.
Exemple1:
somme = n +1 #instr1 Coût = Coût(inst1)+Coût(instr2)+Coût(instr3)
somme = somme * n #instr2 = 2 +2 + 2
somme = somme/2 #instr3 =6
 Opération composée
On appelle opération composée, tout traitement contenant : une instruction conditionnelle, une boucle
ou l'appel d'une fonction:
 L'exécution d'une instruction conditionnelle :
if test :
Q1 Coût = Coût (test) + max (Coût(Q1) , Coût(Q2))
else:
Q2
Exemple2:
if i%2==0:
n=i//2 Coût = Coût(i%2==0)+max(Coût(n = i//2),Coût(i = i +1 , n = i//2))
else: Coût = 2 + max(2,4)
i=i+1 Coût = 6
n=i//2

Complexité algorithmique -2/8 - M. GUEROIHI

  L'exécution d'une boucle :
o Boucle while

while condition: Coût= ∑(𝐂𝐨û𝐭(𝐜𝐨𝐧𝐝𝐢𝐭𝐢𝐨𝐧) + 𝐂𝐨û𝐭(𝒙𝒊 ))

𝒙𝒊 #bloc d'instructions

Exemple 3 :
i=1
s=0 Le corps de la boucle sera exécuté 𝑛 𝑓𝑜𝑖𝑠 (i varie de 1 à n) et la condition (i<=n) va
while i <= n : être exécutée une fois de plus (quand i=n+1)
s = s+i Coût = 𝟐 + ∑𝒏+𝟏 𝒏
𝒊=𝟏 𝑪𝒐𝒖𝒕(𝒊 ≤ 𝒏) + ∑𝒊=𝟏(𝑪𝒐𝒖𝒕(𝒔 = 𝒔 + 𝒊) + 𝑪𝒐𝒖𝒕(𝒊 = 𝒊 + 𝟏))
i = i+1
= 2 + (n+1) + n(2+2)
= 5n+3
o Boucle for

for i in range(n):
Coût= ∑(𝐂𝐨û𝐭(𝒙𝒊 ))
𝒙𝒊 #bloc d'instructions

Exemple 4 :
s=0
Coût= 𝑪𝒐𝒖𝒕(𝒔 = 𝟎) + 𝑪𝒐𝒖𝒕(𝒏 + 𝟏)+ ∑𝒏𝒊=𝟏(𝑪𝒐𝒖𝒕(𝒔 = 𝒔 + 𝒊))
for i in range(1,n+1):
s = s+i Coût= 1 + 1 + 2n = 2n+2

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

c. La notation O :
 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(.), notation
asymptotique/Landau (Grand O)).
Rappel : notation O
𝑠𝑜𝑖𝑒𝑛𝑡 𝒇 𝑒𝑡 𝒈 𝑑𝑒𝑢𝑥 𝑓𝑜𝑛𝑐𝑡𝑖𝑜𝑛𝑠 𝑑𝑒 ℕ ⟼ ℝ+

𝒇(𝒏) = 𝑶(𝒈(𝒏)) 𝐿𝑜𝑟𝑠𝑞𝑢𝑒 ∶ ∃ 𝑘 > 0 , ∃ 𝑛0 > 0 𝑡𝑒𝑙 𝑞𝑢𝑒 ∀ 𝑛 > 𝑛0 𝑓(𝑛) ≤ 𝑘 × 𝑔(𝑛)

Autrement dit : 𝒇(𝒏) 𝒆𝒔𝒕 𝒆𝒏 𝑶(𝒈(𝒏)) s'il existe un seuil à partir duquel la fonction 𝒇(. ) est toujours dominée
par la fonction 𝒈(. ), à une constante k multiplicative fixée près.
Exemples:
 3 2
Soit un algorithme effectuant C(n) = 4n - 5n +2n +3 opérations. On a alors C(n)=O(n
3
)
(Il suffit de garder le terme de plus grand ordre et supprimer son coefficient)

 C(n)=100n2 + 10n = O(n2)

 C(n) = [Link](n) + 12.n + 888 = O([Link](n))
 C(n)=1000n−n+12n+(2n/100)=O(2n)
 Remarque
Si nous avons 𝒇𝟏(𝒏) = 𝑶(𝒈𝟏(𝒏)) 𝒆𝒕 𝒇𝟐(𝒏) = 𝑶(𝒈𝟐(𝒏)) , 𝒂𝒍𝒐𝒓𝒔 ∶
 𝒇𝟏(𝒏) + 𝒇𝟐(𝒏) = 𝑶(𝒈𝟏(𝒏) + 𝒈𝟐(𝒏))
 𝒇𝟏(𝒏). 𝒇𝟐(𝒏) = 𝑶(𝒈𝟏(𝒏). 𝑶(𝒈𝟐(𝒏)))

Complexité algorithmique -3/8 - M. GUEROIHI

 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, le temps d'exécution est élevé à la puissance k avec
O(kn) Exponentielle
k > 1.

O(n!) Factorielle asymptotiquement équivalente à nn

 EXEMPLES DE CALCUL DE COMPLEXITE

Exemple 1 Exemple 2
 La fonction suivante permet de retourner la somme
 La fonction suivante permet de retourner le
des éléments d’une liste:
quotient et le reste de la division d’un nombre
def Somme(L):
entier a par b. s=0
def division (a ,b): for i in range(len(L)) :
q=a//b s=s+L[i]
r=a%b return s
return(q,r) Exemple
 Exemple >>> L =[1, 2, 8, 4]

>>> x , y = 10 , 3 >>>Somme(L)

>>> division(x , y) 15

3 , 1  Le paramètre de complexité est la taille n de la

 Le nombre d'opérations est: 4 liste d'entrée L. on pose n=len(L)

 L'instruction return est négligée  Avant la boucle for on a une affectation

 Temps de calcul est constant quelque soient a et b  en fixant i on exécute 3 opérations: (addition,

 Complexité: 𝓞(𝟏) affectation et lecture de L[i])

 Nombre de fois d'exécution de ces 3 opérations
est: n=len(T)
 Le nombre total d'opérations est :
𝒏−𝟏

𝑪(𝒏) = 𝟏 + 𝟏 + ∑ 𝟑 = 𝟑𝒏 + 𝟐
𝒊=𝟎

 Complexité: 𝓞(𝒏)

Complexité algorithmique -4/8 - M. GUEROIHI

 Exemple 3 : Somme éléments d'une matrice

 La fonction suivante permet de retourner la somme des éléments d’une matrice carré M de dimensions n
lignes et n colonnes:
def Somme(M):
n=len(M)
s=0
for i in range(n) :
for j in range(n) :
s=s+M[i][j]
return s
Exemple
>>> M=[[1,2,3],[1,0,1],[6,4,5]]
>>> Somme(M)
23
 Le paramètre de complexité est n=len(M)
 Avant la boucle for on a 2 affectations et la fonction len(M)
 Le Coût pour calculer une valeur de s est 4 :(addition, affectation et double lecture de M[i][j])
 Le nombre total d'opérations est :
𝒏−𝟏 𝒏−𝟏

𝑪(𝒏) = 𝟑 + ∑ ∑ 𝟒 = 𝟑 + 𝟒𝒏𝟐
𝒊=𝟎 𝒋=𝟎

 Complexité: 𝓞(𝒏𝟐 )

Exemple 4 : 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 : 7 (produit, addition , affectation et lecture de A[i][k]et B[k][j])
 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 :
𝒏−𝟏 𝒏−𝟏 𝒏−𝟏

𝐓(𝐧) = 𝟐 + 𝟑 + 𝟑 + 𝐧 + 𝟏 + ∑ ∑ (𝟑 + ∑ 𝟕)
𝒊=𝟎 𝒋=𝟎 𝒌=𝟎

Complexité algorithmique -5/8 - M. GUEROIHI

 𝒏−𝟏 𝒏−𝟏

𝐓(𝐧) = 𝟗 + 𝐧 + ∑ ∑(𝟑 + 𝟕. 𝒏)
𝒊=𝟎 𝒋=𝟎

𝒏−𝟏

𝐓(𝐧) = 𝟗 + 𝐧 + ∑(𝟑 + 𝟕. 𝒏). 𝒏

𝒊=𝟎

𝐓(𝐧) = 𝟗 + 𝐧 + ((𝟑 + 𝟕. 𝒏). 𝒏). 𝒏

𝑻(𝒏) = 𝟕𝒏𝟑 + 𝟑𝒏𝟐 +n+9
 Complexité: 𝓞(𝒏𝟑 )

Exemple 5 : recherches séquentielle

def Recherche_Seq(T,x):
n=len(T)
for i in range(n):
if T[i]==x :
return True
return False
 Le paramètre de complexité est n=len(M)
 Le nombre d'opérations avant for est : 2
 La boucle for contient une lecure de T[i] et un test (2 opérations)
 Le nombre de fois d'exécution de ce test dans le pire de cas est n
 Dans le pire des cas L’instruction return True ne sera jamais exécutée.
 Le nombre d'opérations total est :

𝒏−𝟏

𝐓(𝐧) = 𝟐 + ∑ 𝟐 = 𝟐𝒏 + 𝟐
𝒊=𝟎

 Complexité : 𝓞(𝒏)

Complexité algorithmique -6/8 - M. GUEROIHI

 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):
if T[j] < T[Posmin]:
Posmin=j
#Permutation
T[i] , T[Posmin] = T[Posmin] , T[i]

● Le paramètre de complexité est 𝒏 = 𝒍𝒆𝒏(𝑻)

● Calculons le nombre d'opérations 𝑻(𝒏):

𝒏−𝟐 𝒏−𝟏 𝒏−𝟐

𝑻(𝒏) = 𝟐 + 𝟏 + ∑ (𝟖 + ∑ 𝟒) = 𝟑 + ∑(𝟖 + 𝟒(𝒏 − 𝒊 − 𝟏))

𝒊=𝟎 𝒋=𝒊+𝟏 𝒊=𝟎
𝒏−𝟐

𝑻(𝒏) = 𝟑 + ∑(𝟒𝒏 + 𝟒 − 𝟒𝒊)

𝒊=𝟎
𝒏−𝟐 𝒏−𝟐

𝑻(𝒏) = 𝟑 + ∑(𝟒𝒏 + 𝟒) − 𝟒. ∑ 𝒊
𝒊=𝟎 𝒊=𝟎
(𝒏 − 𝟐)(𝒏 − 𝟏)
𝑻(𝒏) = 𝟑 + (𝟒𝒏 + 𝟒)(𝒏 − 𝟏) − 𝟒. = 𝟑 + (𝟒𝒏 + 𝟒)(𝒏 − 𝟏) − 𝟐(𝒏 − 𝟐)(𝒏 − 𝟏)
𝟐
𝑻(𝒏) = 𝟑 + (𝒏 − 𝟏)(𝟒𝒏 + 𝟒 − 𝟐𝒏 + 𝟒)
𝑻(𝒏) = 𝟐𝒏𝟐 + 𝟔𝒏 − 𝟓
Donc, la complexité est: 𝓞(𝒏𝟐 )

Complexité algorithmique -7/8 - M. GUEROIHI

 Exemple 7 : Recherche dichotomique

def RechDichotomique(T,x):
g,d=0,len(T)-1
while g<=d:
m=(g+d)//2
if T[m]==x: return True
if T[m]<x:
g=m+1
else:
d=m-1
return False

Soit 𝐧 la taille de la liste T.

A chaque itération de la boucle while, l’intervalle de recherche est divisé par 2.

n
Après k itérations, la taille de l’intervalle restant est :
2k

La boucle continue tant que cet intervalle contient au moins un élément, donc :

n
≥ 1 ⇒ n ≥ 2k ⇒ k ≤ log 2 (n)
2k

Le nombre maximal d’itérations dans la boucle est donc :

k max = ⌊log 2(n)⌋ + 1

À chaque itération, on effectue un nombre constant d’opérations (calcul du milieu, comparaisons, mise à jour
des indices).

Donc la complexité temporelle totale est proportionnelle à 𝐥𝐨𝐠 𝟐 (𝐧) soit :

𝓞(𝒍𝒐𝒈 𝒏)

Complexité algorithmique -8/8 - M. GUEROIHI