Lycée Mohamed 5 – CASA Pr.

Salsabila BENGHAZOUANI

Chapitre 1 : Complexité Algorithmique

Problème

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 1 soit 0).

Solutions proposées

1
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Quelques questions
Que remarquez-vous concernant cet exercice ?
Le code le plus court ! est-il meilleur ?
Comment peut-on designer le meilleur code parmi ces 9 solutions ?

Quelques réflexions
La solution la plus intuitive pour choisir la meilleure solution consiste à mesurer le temps
d’exécution exacte pour chaque algorithme
Pour ce faire, python offre le module time qui permet de calculer le temps d’exécution.

2
 Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Question
Mais, est ce que cette technique est toujours valide ?

Réponse :
Malheureusement, cette technique n’est pas toujours valide, car on se sait pas le
comportement de l’algorithme proposé quand n devient grand

⇒Contre exemple :Tri d’une liste

Tri d’une liste
On dispose de deux programmes fondés chacun sur deux algorithmes exacts pour trier
une liste : Le tri par insertion, Le tri fusion.
Les deux programmes sont écrits en langage python Avec chacun des deux programmes,
nous trions par ordre croissant une liste aléatoire de N éléments.
⇒Environnement de simulation
Processeur Intel Core i5-4210U CPU 1,70GHz x 4
Mémoire vive 8Go
OS : Linux Ubuntu 14.04 LTS 64bits
⇒Résultats de l’expérience

Définition
Généralement, pour le même problème P, on peut trouver plusieurs algorithmes
(Alg1, Alg2, .., Algn ).
La complexité : mesure de la quantité de ressources nécessaires à la résolution
du problème P.
Mesure : estimation d’opérations de base en fonction de la taille des données.
Objectif de la complexité :
Evaluer le coût d’exécution de chaque algorithme afin de
choisir le meilleur.
Maitriser les techniques d’évaluation d’un algorithme

Types de complexité
Ressources utilisées ⇒ 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. 3
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

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.

Déterminer la complexité d’un algorithme, c’est évaluer les ressources nécessaires à son
exécution (essentiellement la quantité de mémoire requise) et le temps de calcul à prévoir.
Ces deux notions dépendent de nombreux paramètres matériels qui sortent du domaine de
l’algorithmique : nous ne pouvons attribuer une valeur absolue ni à la quantité de mémoire
requise ni au temps d’exécution d’un algorithme donné. En revanche, il est souvent possible
d’évaluer l’ordre de grandeur de ces deux quantités de manière à identifier l’algorithme le plus
efficace au sein d’un ensemble d’algorithmes résolvant le même problème.
Prenons un exemple concret : la détermination du nombre de diviseurs d’un entier naturel n.
Une première solution consiste à essayer si chacun des entiers compris entre 1 et n est un
diviseur de n. Ceci conduit à définir la fonction diviseurs1 de la figure 1.

Comment comparer ces deux versions ? Si on se focalise sur les deux boucles conditionnelles
de ces algorithmes on constate que dans les deux cas on effectue deux additions, une division
euclidienne et un test. Chacune de ces opérations est effectuée n fois dans le premier cas, √𝑛
fois dans le second. Nous ne connaissons pas le temps τ1 nécessaire à la réalisation de ces
différents calculs, mais on peut légitimement penser que le temps total d’execution de

4
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

diviseurs1 n’est pas éloigné de τ1 n + τ2 , le temps τ2 étant le temps requis par les autres
opérations. De même, le temps requis par la fonction diviseurs2 est de l’ordre de
Les temps τ’2 et τ2 sont négligeable pour de grandes valeurs de n ; de plus les
valeurs de τ1 et τ1’ importent peu ; elle dépendent de conditions matérielles qui nous échappent.
Nous n’allons retenir que le taux de croissance de chacune de ces deux fonctions : proportionnel
à n pour la première (on dira plus loin qu’il s’agit d’un algorithme de coût linéaire),
proportionnel à √𝑛 pour la seconde. Autrement dit :
– multiplier n par 100 multiplie le temps d’exécution de diviseurs1 par 100
– multiplier n par 100 multiplie le temps d’exécution de diviseurs2 par 10.
Ainsi, connaissant le temps d’exécution pour une valeur donnée de n il est possible d’évaluer
l’ordre de grandeur du temps d’exécution pour de plus grandes valeurs.
Pour calculer la complexité, il convient de définir ce qu’on appelle la taille de l’entrée. Cette
notion dépend du problème étudié : pour de nombreux problèmes, il peut s’agir du nombre
d’éléments constituant les paramètres de l’algorithme (par exemple le nombre d’éléments du
tableau dans le cas d’un algorithme de tri) ; dans le cas d’algorithmes de nature arithmétique
(le calcul de nk par exemple) il peut s’agir d’un entier passé en paramètre, voire du nombre de
bits nécessaire à la représentation de ce dernier. Enfin, il peut être approprié de décrire la
taille de l’entrée à l’aide de deux entiers (le nombre de sommets et le nombre d’arêtes dans le
cas d’un algorithme portant sur les graphes).
Une fois la taille n de l’entrée définie, il reste à évaluer en fonction de celle-ci le nombre f (n)
d’opérations élémentaires requises par l’algorithme. Mais même s’il est parfois possible d’en
déterminer le nombre exact, on se contentera le plus souvent d’en donner l’ordre de grandeur
à l’aide des notations de Landau.

Notation asymptotique
On introduit le concept de la notation asymptotique, qui permet d’estimer le temps
d’exécution d’un algorithme

Notation asymptotique - ”Big” O

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 ) telle que T (n) <= c ∗ f (n)
∀n >= n0

”Big” O : Exemples
Exemple 1 :
si T (n) = 3n + 6 alors T (n) = O (n)
Démonstration :

5
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

En effet, pour n >= 2, on a 3n + 6 <= 9n ; la quantité 3n + 6 est donc bornée, `à

partir d’un certain rang, par le produit de n et d’une constante.
3 ∗ 2 + 6 <= 9 ∗ 2
3 ∗ 3 + 6 <= 9 ∗ 3
3 ∗ 4 + 6 <= 9 ∗ 4
3 ∗ 5 + 6 <= 9 ∗ 5
Remarque
En général, il est difficile de trouver le seuil afin de borner la complexité O. Pour cela,
on applique des règles afin de simplifier l’expression du temps d’exécution
Règles de calcul
On calcule le temps d’exécution comme avant, mais on effectue des simplifications
suivantes :
* On oublie les constantes multiplicatives ;
* On annule les constantes additives ;
* On ne retient que les termes dominants ;
Exemple :
Soit un algorithme effectuant T (n) = 4n3 − 5n2 + 2n + 3 opérations ;
→ On remplace les constantes multiplicatives par 1 : 1n3 − 1n2 + 1n + 3 → On annule
les constantes additives : n3 − n2 + n + 0
→ On garde le terme de plus haut degré : n3 + 0 ⇒ Donc :T (n) = O (n3 ).

Classes de complexité les plus usuelles

6
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Ordres de grandeur de différents types de complexité

Ordre de grandeur et temps d’exécution
La détermination de la complexité algorithmique ne permet pas d’en déduire le temps
d’exécution mais seulement de comparer entre eux deux algorithmes résolvant le même
problème. Cependant, il importe de prendre conscience des différences d’échelle considérables
qui existent entre les ordres de grandeurs usuels que l’on rencontre. En s’appuyant sur une base
de 109 opérations par seconde, le tableau de la figure 2 est à cet égard significatif. Il indique en
fonction de la taille n de l’entrée (102, 103 , . . .) et du nombre d’opérations requis par un
algorithme (log n, n, . . . ) le temps d’exécution de ce dernier.

Comment mesurer la complexité d’un algorithme

Le temps d’exécution d’un algorithme est la somme des temps d’exécution de ses
instructions.

Ti dépend du coût de l’instruction i et dépend également de la performance de

l’ordinateur (Microprocesseur, RAM,..)

7
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Le coût des instructions élémentaires

On appelle opération de base, ou opération élémentaire, toute :
1 Affectation ;
2 Test de comparaison :==, <, <=, >=, ! = ;
3 Opération de lecture (input) et écriture (print) ;
4 Opération arithmétique :+, −, ∗, /, % ;
5 Opération d’incrémentation :a=a+1,(pas 1) a=a+n (pas n) ;
6 Opération de décrémentation :a=a-1,(pas 1) a=a-n (pas n) ;
Le coût d’une opération élémentaire est égale `a 1 (ou une constante cte ).
Exemple 1 : Que vaut le coût de l’algorithme A

→Technique 1 : Coût(A)=6
→Technique 2 : Coût(A)=c 1 + c 2 + c 3
Donc la complexité est O(1)
Le coût des instructions composées
On appelle opération composée, toute instruction contenant :
1 L’exécution d’une instruction conditionnelle : Si P est une instruction
conditionnelle du type Si b alors Q 1 sinon Q 2 finsi, le nombre
d’opérations est :
Cout (P ) <= Cout (test ) + max (Cout (Q 1), Cout (Q 2))
2 L’exécution d’une boucle : le temps d’une boucle est égal `a la multiplication
de nombre de répétition par la somme du coût de chaque instruction xi du corps de la
boucle ;
Cout (boucle for ) = ∑ Cout (xi )
Cout (boucle while ) = ∑ (Cout (comparaison) + Cout (xi ))
3 L’appel d’une fonction : lorsqu’une fonction est appelée, le coût de cette fonction
est le nombre total d’opérations élémentaires engendrées par l’appel de cette fonction.

8
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Exemple 2 : Que vaut le coût de l’algorithme B

→ Technique 1 : Coût(B )=2+ max(2,4)=6

→ Technique 2 : Coût(B )=c1+ max(c2,c3+c4)=c1+c3+c4
Donc la complexité est O(1)
Exemple 3 : Que vaut le coût de l’algorithme C

→ Technique 1 : Coût(C )=2xn+1xn=3n

→ Technique 2 : Coût(B )=c1xn+ c2xn=(c1+c2)xn
Donc la complexité est O(n)
Exemple 4 : Que vaut le coût de l’algorithme D

→ Technique 1 : Coût(D )=5n+1 et → Technique 2 : Coût(D )=c1+(c2+c3+c4)n

Donc la complexité est O(n)

9
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Des exemples de calculs de complexité

Exemple 1 : la fonction division
La fonction suivante permet de retourner le quotient et le reste de la division entière
d’un nombre entier a par b

def division(a,b) :
q=a//b
r=a%b
return (q,r)

Le nombre d’opérations C (n) est : 5

Complexité : O (1)
Exemple 2 : la fonction somme d’une liste
La fonction suivante retourne la somme des éléments d’une liste :

def somme(L) :
s=0
for i in range (len(L)) :
s=s+L[i]
return s

Le paramètre de complexité est la taille de la liste d’entrée L.

On a le coût C (n) = 4 ∗ len(L) + 2 donc complexité : O(len(L))= O(n)
Ex. 3 : remplir une matrice

def RemplirMat(M,n,p) :
for i in range(n) :
for j in range(p) :
print(“T[”,i,“][“,j,”]=“,end=”)
T[i][j]=int(input())
10
 Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

On suppose que p=n

C (n) = 2n + 2np + np + 2np = 5np + 2n = 5n2 + n ⇒ O (n2 )
Donc la complexité est quadratique.
Exemple. 4 : produit matriciel

def ProduitMatriciel(A,B) :
n,p,m= len(A)) , len(B[0])) , len(B))
prod = [[0]*len(A) for i in range(len(A))]
for i in range(n) :
for j in range(p) :
s=0
for k in range(m) :
s= s + A[i][k] * B[k][i]
prod[i].append(s)
return prod

Analyse: le corps de la boucle sur k est en O(1) car ne contient qu’un nombre constant d’opérations
élémentaires. Comme cette boucle est itérée m fois, sa complexité est alors en O(m). La boucle sur
j est itérée p fois. Sa complexité est en p.O(m) = O(mp). La boucle sur i est répétée n fois. Par
conséquent, la complexité de tout l’algorithme est en O(nmp).
Remarque : cas particulier, si A et B sont des matrices carrées donc m=n=p et T(n)=O(n3)
complexité polynomiale cubique
Différentes nuances de complexité temporelle
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 cela, on distingue 3 types de complexité :
• Complexité au pire des cas.
• Complexité dans le meilleur des cas.
• Complexité en moyenne des cas.

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 )}
11
d ∈Dn
avec Dn l'ensemble des données de taille n
• C(d) est le cout d'exécution de l'algorithme sur la donnée d de taille n.
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Recherche d'un élément dans un tableau

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
Tmin (n) = min{C (d )} d ∈Dn
Complexité en moyenne des cas : c’est une évaluation du temps d’exécution moyen
portant sur toutes les entrées possible d’une même taille supposées équiprobables.
Tmoy (n) = {Pr (d ).C (d ), d ∈ Dn }

Exemple. 5 : minimum d’un tableau

T min(n) : la liste L est triée par ordre croissant

T min(n)=c1+n*c2+n*c3+c5, donc la complexité dans le meilleure des cas : O (n)
T max(n) : la liste L est triée par ordre décroissant
T max(n)=c1+n*c2+n*c3+n*c4+c5, donc la complexité dans le pire des cas : O (n)
Exemple. 6 : recherche séquentielle

12
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Complexité dans le pire des cas : O (n)

Dans le pire des cas : quand l'élément recherché x est le dernier (dans la case n-1) ou est
absent.
Complexité dans le meilleure des cas : O (1)
Dans le meilleur des cas : quand l'élément recherché x se trouve en 1ére position.
Exemple. 7 : recherche dichotomie

T MIN(n) : X existe au milieu de la liste

T min(n)=c1+c2+c3+c4+c5+c6
Complexité dans le meilleure des cas est O (1)
T MAX(n) : quand l'élément recherché x est le dernier (dans la case n-1) ou est absent.
Sachant qu'à chaque itération de la boucle on divise le tableau en 2, cela revient donc à se
demander combien de fois faut-il diviser le tableau en 2 pour obtenir, à la fin, un tableau
comportant un seul entier ? Autrement dit, combien de fois faut-il diviser n par 2 pour obtenir
1?
Itération intervalle de recherche

0 n

1 n/2

2 n/4

3 n/8
.......................................

k n/ 2k

13
 Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

On exécute la boucle while k fois tant que n/2k ≠ 1 plus une opération pour
exécuter la condition d’arrêt
𝑛
=1→n=2k → log2(n)=log2(2k)→k=log2(n),
2𝑘

T MAX(n)=c1+c2+(k+1)*c3+k*c4+k*c5+2*k*c7+c8+4 Donc Complexité dans le pire

des cas est O (log2 (n))
on dispose de la relation : C(n) = C(n/ 2) + Θ(1). Ce type de relation est souvent étudié dans le
cas particulier des puissances de 2 en posant up = C(2p ) car alors on dispose de la relation
up = up−1 + Θ(1) qui conduit à up = Θ(p), soit C(n) = Θ(log n) lorsque n = 2p
Dans tous les cas, la complexité est donc un O(log n).

Complexité d’une fonction récursive

Exemple.1 Suite de Fibonacci

def FiboRe(n) :
if (n==0 or n==1) :
return 1
else :
return FiboRe(n-1)+FiboRe(n-2)

Analyse de la complexité de la suite de Fibonacci -version1

14
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Analyse de la complexité de la suite de Fibonacci -version2

Soit T(n) le nombre d’additions effectuées par cet algorithme. T(n) vérifie les équations
suivantes :

En posant S(n) =T(N)+1 on obtient :

Donc une équation de récurrence sans second membre : S(n) − S(n −1) − S(n − 2) = 0
Son polynôme caractéristique est : x2-x-1=0
Cette équation possède dans ce cas deux solutions réelles distinctes

S S

Théorème général
Soient a ≥ 1 et b > 1 deux constantes, soit f (n) une fonction et soit T(n) définie pour les
entiers non négatifs par la récurrence
T(n)=aT(n/b)+f (n)

où l’on interprète n/b comme signifiant ⌊n/b⌋. T(n) peut alors être bornée asymptotiquement
de la façon suivante.

15
Lycée Mohamed 5 – CASA Pr.Salsabila BENGHAZOUANI

Exemple

Complexité spatiale
De la même façon qu’on définit la complexité temporelle d’un algorithme pour évaluer ses
performances en temps de calcul, on peut définir sa complexité spatiale pour évaluer sa
consommation en espace mémoire. Le principe est le même sauf qu’ici on cherche à évaluer
l’ordre de grandeur du volume en mémoire utilisé : il ne s’agit pas d’évaluer précisément
combien d’octets sont consommés par un algorithme mais de préciser son taux de croissance
en fonction de la taille n de l’entrée. Cependant, on notera que la complexité spatiale est bien
moins que la complexité temporelle un frein à l’utilisation d’un algorithme : on dispose
aujourd’hui le plus souvent d’une quantité pléthorique de mémoire vive, ce qui rend moins
important la détermination de la complexité spatiale.

16