Cours : Algorithmique &

complexité

Enseignante : Fatma Hermès

Niveau : 1ière année CS
Semestre : 2
Année universitaire : 2021-2022
Chapitre 5 : Complexité
algorithmique
 Introduction
 Efficacité d’un algorithme
 Types de complexité
◦ Complexité en temps
◦ Complexité en espace
 Complexité en temps :
◦ Evaluation
◦ Approximations
◦ Types
◦ Bornes approchées
◦ Algorithmes récursifs
◦ Classes de complexité

2
Introduction :
Algorithme et algorithmique
 Un algorithme est une méthode permettant de
résoudre un problème donné en un temps fini.
➔Un algorithme est une suite ordonnée
d'opérations ou d'instructions décrites pour la
résolution d'un problème donné.
 Algorithmique désigne le processus de recherche
d’algorithme.
◦ Il n’existe pas d’algorithme pour créer des
algorithmes.
◦ Il existe quelques principes généraux que l’on peut
suivre.

3
 Introduction :
Caractéristiques d’un bon algorithme
 Correct : Résout correctement le problème pour lequel il a été
conçu ==> donne un résultat correct.
 Complet : Considère tous les cas possibles == > donne un
résultat dans chaque cas.
 Efficace : exécute sa tâche avec efficacité c’est à dire avec un coût
minimal. Le coût pour un ordinateur se mesure en termes de
temps de calcul et d’espace mémoire nécessaire.
 NB : on attend d’un algorithme qu’il résolve de manière efficace le
problème à résoudre, quelles que soit le volume des données à
traiter.
La théorie de la complexité s’intéresse à
l’efficacité d’un algorithme

4
 Complexité algorithmique :
Efficacité d’un algorithme
 L’efficacité d’un algorithme peut être évaluée par :
◦ Sa rapidité : en terme de temps d’exécution
◦ Sa consommation de ressources : espace de stockage,
mémoire utilisé
 NB : La rapidité d’un algorithme ne se mesure pas en
heures minutes et secondes sinon on doit implémenter
tous les algorithmes possibles avant de choisir un.
 En plus ces mesures ne seraient pas pertinentes puisque
le même algorithme serait plus rapide sur une machine
plus puissante.

5
Complexité algorithmique : Types
 L'efficacité d'un algorithme peut être évalué en temps et/ou en
espace :
◦ Complexité en temps : évaluation du temps d'exécution de
l'algorithme
◦ Complexité en espace : évaluation de l'espace mémoire
occupé par l'exécution de l'algorithme ➔ éviter les problèmes de
(mémoire insuffisante) : l’allocation dynamique de mémoire peut
réduire ce type de problème (Exemple : dans le cas d’utilisation de
matrice).
 NB : Même si on s’intéresse quasi-exclusivement à la complexité en
temps des algorithmes. Il est parfois intéressant de s’intéresser à
d’autres ressources, comme la complexité en espace (taille de
l’espace mémoire utilisé), la largeur de bande passante requise, etc.
6
Complexité en temps
 Pour un même problème supposons que nous avons deux
méthodes
 On veut Evaluer l’efficacité de la méthode M
 Comparer M avec une autre méthode M′ indépendamment
de l’environnement (machine, système, compilateur, . . .)
 Evaluation du nombre d’opérations élémentaires en fonction
de la taille des données, de la nature des données.
 Notations :
◦ n : taille des données en entrée,
◦ T ( n ) : nombre d’opérations élémentaires

7
 Complexité en temps
Exemple 1 : échange de deux valeurs
entières
Méthode 1 : //Echanger x et y Méthode 2 : //Echanger x et y
x, y, z : entier; //Déclarations entier x, y; //Déclarations
x  5; y  20; //Initialisations x  5; y  20; //Initialisations
z  x; x  y-x;
x  y; y  y-x;
y  z; x  y+x;

 La première méthode utilise une variable supplémentaire (z) et réalise 3

affectations
 La deuxième méthode n'utilise que les deux variables dont on veut
échanger les valeurs, mais réalise 3 opérations arithmétiques (2
soustraction et 1 addition)
8
 Complexité en temps
Exemple 2 : Calcul de la factorielle
Fonction factorielle1(n : entier) : entier
Variables : i, resultat : entier;
Début
resultat  1;
Pour (i allant de 2 à n (pas =1)) faire
resultat  resultat*i;
Finpour
retourne resultat;
Fin
 Le paramètre de la complexité est ce qui va faire varier le temps
d'exécution de l'algorithme.
 Le paramètre de complexité dans l’exemple 2 est la valeur de n
 T(n) = (n-1) multiplications + (n-1) affectation + 1 initialisation
= 2n-1 Opérations élémentaires
9
Complexité en temps
Exemple 3 : multiplier tous les éléments d'un
tableau d'entiers par un entier donné
Procédure : multiplie(tab :Tableau [1..n] d’entiers, x :
entier)
Variable i : entier
Début
Pour i allant de 1 à n faire
tab[i]  tab[i] * x
Fin pour
Fin
 Le paramètre de complexité est n la longueur du tableau tab.
 T(n) = n multiplication
= n opération élémentaires
10
Complexité en temps : Types
 Lorsque, pour une valeur donnée du paramètre de
complexité, le temps d'exécution varie selon la taille des données
en entrée, on peut distinguer :
◦ La complexité au pire : temps d'exécution maximum, dans le
cas le plus défavorable.
◦ La complexité au mieux : temps d'exécution minimum, dans
le cas le plus favorable (en pratique, cette complexité n'est pas
très utile).
◦ La complexité moyenne : temps d'exécution dans un cas
médian, ou moyenne des temps d'exécution. Le plus souvent, on
utilise la complexité au pire, car on veut borner le temps
d'exécution.
 C'est l'analyse pessimiste ou au pire des cas qui est généralement
adoptée.

11
Complexité en temps : Types
Exemple
 Recherche d’un élément dans une liste de n éléments.
◦ La complexité au meilleur est que l’élément cherché soit le
premier élément testé dans la liste
T(n)=1 (comparaison).
◦ La complexité au pire est que l’élément cherché soit le
dernier élément testé dans la liste ou inexistant
T(n)=n.
◦ La complexité moyenne est NB : La complexité
T(n) = (1+2+3+…+n-1+n)/n en nombre de
T(n)= ((n(n+1))/2)/n = (n+1)/2 == comparaisons
> T(n) =(n+1)/2 .

Note : L'analyse au pire des cas donne une limite supérieure de la

performance et elle garantit qu'un algorithme ne fera jamais moins bien
que ce qu'on a établi.
12
Complexité en temps :
Approximations
 Calculer la complexité de façon exacte n'est pas raisonnable vu la
quantité d'instructions de la plupart des programmes et n'est pas
utile pour pouvoir comparer deux algorithmes.
◦ Première approximation :
on ne considère souvent que la complexité au pire
(le cas le plus défavorable)
◦ Deuxième approximation :
on ne calcule que la forme générale de la complexité
◦ Troisième approximation :
on ne regarde que le comportement asymptotique de la
complexité : lorsque le paramètre de la complexité est
très grand (la taille des données en entrée est très
grande).

13
Complexité en temps :
Règles de calcul
 Structures de contrôle
Structures
 Séquence
algorithmiques :
 Embranchement (ou sélection)
 Boucle (ou itération)

 Structures de données
 Constantes
 Variables
 Tableaux
 Structures récursives (listes, arbres)

14
Complexité en temps :
Règles de calcul
 Chaque instruction basique consomme une unité de
temps (affectation d’une variable, comparaison,
opération arithmétique : multiplication,…,)
 Chaque itération d’une boucle rajoute le nombre
d’unités de temps consommées dans le corps de cette
boucle.
 Chaque appel de fonction rajoute le nombre
d’unités de temps consommées dans cette fonction.
 Pour avoir le nombre effectués d’opérations par
l’algorithme et avoir le total d’unités de temps on
additionne le tout.

15
 Complexité en temps :
Règles de calcul
Structures de contrôle

1) Séquences : Somme des coûts

Traitement1 : T1(n)
Traitement2 : T2(n) T(n) = T1(n) + T2(n)

2) Embranchement (ou sélection) : Max des coûts

si < condition > alors
Traitement1 : T1(n)
sinon max(T1(n),T2(n))
Traitement2 : T2(n)
Finsi

16
 Complexité en temps :
Règles de calcul
Structures de contrôle
3) Boucle
Somme des coûts des passages successifs
Tant que < condition > faire
T(n)=Σi=1..Nb Ti(n)
Traitement i : Ti (n)
Fin faire
Nb : nombre d’itérations

Ti (n) : coût de la ième itération

17
Notion de grand O :
Borne supérieure asymptotique
 On dit que la fonction g est une borne supérieure asymptotique de
la fonction f ( ou bien f est un grand O de g) s’il existe une
constante positive c telle que pour n assez grand (∃n0>0 tel
que ∀n>n0 ) on a :
f(n)≤c*g(n)
 On note alors
f(n)=O(g(n)) (ou f(n)O(g(n)) ).
 Cela signifie qu'à partir d'un certain rang n0 la fonction f est
majorée par une c*g(n) (constante c (positive) fois la
fonction g) .
 Il s'agit donc d'une situation de domination de la fonction f par
la fonction g .

18
 Interprétation graphique de la notion de grand O : A partir du rang
n0, la courbe de f est au dessous de celle de c*g .
 Exemples de relations grand O :
◦ Si T(n)=4 alors T(n)=O(1) : (par exemple c=5 et n0=0 ).
◦ Si T(n)=3n+2 alors T(n)=O(n). (par exemple c=4et n0=2) .
◦ Si T(n)=3n+2 alors T(n)=O(n2)) ((par exemple c=1et n0=5) )
◦ Si T(n)=2n2+3 alors T(n)=O(n2)) . (par exemple c=3 et n0=3) .
19
Notion de grand Oméga :
Borne inférieure asymptotique
 On dit qu’une fonction g est une borne inférieure
asymptotique d’une fonction g (ou f est un grand Oméga
de g) s’il existe une constante positive c (∃c > 0) telles que
pour n assez grand (∃n0>0 tel que ∀n>n0) on a :
c*g(n) ≤ f(n)
 On dit aussi que f est un grand Oméga de g et on note
f(n)=Ω(g(n)) (ou f(n)Ω(g(n)) )
 A partir d'un certain rang n0 la fonction f est minorée
par une constante ( c*g(n)) c fois la fonction g
(c*g(n)).
 Il s'agit donc d'une situation de domination de la
fonction g par la fonction f .

20
 Interprétation graphique de la notion de grand Oméga : A partir du
rang n0 , la courbe de f est au dessus de celle de c fois g .
 Exemples de relations grand Oméga
◦ Si T(n)=4 alors T(n)=Ω(1) . (par exemple c=1 et n0=0 ).
◦ Si T(n)=3n+2 alors T(n)=Ω(n) . (par exemple c=1et n0=0)
◦ Si T(n)=2n2+3 alors T(n)=Ω(n2) . (par exemple c=1 et n0=1)
◦ Si T(n)=2n2+3 alors T(n)=Ω(n) . (par exemple c=1 et n0=1)
21
 Notion de grand Théta « Θ »:
Borne approchée asymptotique
 On dit qu’une fonction g est une borne approchée asymptotique
d’une fonction f s’il existe deux constante strictement positives c1 et c2
(∃c1>0, ∃c2>0) telles que pour n assez grand (∃n0>0) on a :
∀n>n0, 0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n)
 On dit aussi que f un grand Théta de g et on note :
f(n)=Θ(g(n)) (ou f(n)Θ(g(n))) .
 Cette situation combine les deux précédentes, à partir d'un certain rang
n0 la fonction f est encadrée par des multiples de la fonction g . Cela
signifie que les fonctions f et g sont du même ordre de grandeur
à un facteur constant près pour n assez grand.
 Remarque :
f(n)=Θ(g(n)) ⇔ (f(n)=O(g(n)) et f(n)=Ω(g(n)))

22
 Interprétation graphique de la notion de grand Théta
 Remarque :
f(n)=Θ(g(n)) ⇔ (f(n)=O(g(n)) et f(n)=Ω(g(n)))
 Exemples de relations grand Théta
◦ Si T(n)=4 alors T(n)=Θ(1) . (4 =O(1) et 4 =Ω(1))
◦ Si T(n)=3n+2 alors T(n)=Θ(n) . (3n+2 =O(n) et 3n+2 =Ω(n))
◦ Si T(n)=2n2+3 alors T(n)=Θ(n2) . (2n2+3 =O(n) et 2n2+3 =Ω(n))
23
Notion d'équivalence
 Equivalence : On dit qu’une fonction f est équivalente à
une fonction g si et seulement si
Limn→∞ f(n)/g(n)=1
 On note alors f(n)∼g(n) .
 Exemple : F(n)=n2+2n+4 et g(n) = n2+3
 Il faut bien comprendre que cette notion est plus forte que
celle de grand Théta, car non seulement les fonctions sont
du même ordre de grandeur mais leur quotient tend vers 1.

24
Notion de dominance
 On dit qu’une fonction f domine une fonction
g si on a
Limn→∞ f(n)/g(n)= +
 On dit qu’une fonction f est dominé par une
fonction g si on a
Limn→∞ f(n)/g(n)=0

25
Complexité en temps :
Algorithme récursif
● Il est souvent possible de retrouver une relation de récurrence
qui décrit le temps d'exécution d’un algorithme récursif en
fonction des temps d'exécution des appels récursifs résolvant les
sous-problèmes associés de tailles inférieures.
● le temps d’exécution d’un algorithme récursif est souvent facile à
déterminer à l’aide des récurrences.

Une récurrence est une équation qui décrit une fonction

à partir de sa valeur sur des entrées plus petites.

● Chaque appel récursif prendrait un temps constant plus le temps

pour les appels récursifs qu’il effectue.

● Les récurrences peuvent prendre différentes formes.

26
Exemple de récurrence : fonction Factorielle
 On considère l’opération de multiplication comme opération
élémentaire. À chaque appel récursif, l’algorithme effectue une
multiplication.
 Soit T(n) désignant l’estimation du temps d’exécution, l’équation
de récurrence associée est donnée par:

Fonction Factorielle(N:Entier): entier

Début
T(n) = 0 si n = 0 si (N = 0)alors
T(n-1) + 1 si n ≥ 1 retourner(1)
sinon
Calculer le factoriel de n-1
retourner(N * Factorielle(N-1))
fin si
Fin
Une multiplication
27
Exemple de récurrence : fonction
Factorielle
 T(n) = T(n-1) +1
=T(n-2)+1 +1 = T(n-2)+2
=T(n-3)+1 +1+1 =T(n-3)+3
= T(n-4)+1+1+1+1= T(n-4)+4
…
= T(0)+1+1+1…+1=T(n-n)+n
=T(0)+n
=n

 D’ouT(n)= O(n)

28
Exemple de récurrence :
Tours de Hanoi Procédure Hanoï(n, départ, Intermédiaire,
destination) Début
 On veut calculer la Si (n>0) alors
Hanoï(n-1, départ, destination, Intermédiaire)
complexité en deplacer(départ, destination)
nombre de // opération élémentaire
déplacements Hanoï(n-1, Intermédiaire, départ, destination)
invoqués sur n Fin Si
disques Fin
temps pour déplacer les (n-1)
 T(n) = T(n-1) + 1 + T(n-1) disques de la tige intermédiaire
vers la tige destination.
temps pour déplacer les (n-1)
disques de la tige 1 de départ une opération de déplacement du
à la tige intermédiaire. disque de la tige de départ vers
la tige destination.

T(n) = 1 si n=1
2T(n-1) +1 si n>1
29
Exemple de récurrence : Tours de Hanoi

 Résolution :
T(n) = 2T(n-1)+1
= 2[2T(n-2)+1]+1
= 2[22 T(n-3)+ 2 +1]+1
= 23 T(n-3)+ 22 +21 +1
= …
= 2n-1 T(1)+ 2n-2 + …+21+ 20
n−1
 1− q n 
n−1
 q =
i

T(n) =  2 i= 2n-1 i= 0  1− q 
i=0

T(n)=O(2n) : Exponentiel
30
 Equation de récurrence linéaire
d’ordre k
● Une équation récurrente est dite linéaire d’ordre k si chaque terme
de la suite récurrente s’exprime comme combinaison linéaire des k
premiers termes qui le précèdent plus une certaine fonction de n.
T(n) = a1T(n-1) + a2T(n-2) + … + akT(n-k) +f(n)

● Pour k=1, la récurrence est dite linéaire d’ordre 1 et elle est de la

forme:
T(n) = aT(n-1)+f(n),
On en déduit la solution :
n

T (n) = a ( T(0)+
n  f (i)
ai )
i=1

31
Application – Tours de Hanoï
 On a :
T(n) = 2T(n-1) +1
 Il s’agit d’une récurrence linaire d’ordre 1, k=1

 On applique la formule
n

T (n) = a ( T(0) +
n  f (i)
ai )
i=1

avec a=2 et f(n)=1, on obtient

n

T (n) = 2 ( 1+
n  1
2i )
i=1

32
 Equation de récurrence linéaire sans
second membre
Lorsque f(n)=0, l’équation de récurrence est dite linéaire sans
second membre :
T(n) = a1T(n-1) + a2T(n-2) + … + akT(n-k)
On a :T(n) - a1T(n-1) - a2T(n-2) - … - akT(n-k) = 0
A cette équation, on associe un polynôme caractéristique :
P(x) = xk - a1xk-1- a2xk-2- … - ak-1x1 - akx0
Si la résolution de ce polynôme (P(x)=0) donne k racines distinctes r i,
i=1..k.
La solution de l’équation de récurrence est donnée par la formule
suivante :
T (n) = 1 (r1)n + 2 (r2)n+ . . . + k (rk)n
Les αi sont déterminés à partir des k premiers termes.
Cette solution est en général exponentielle.
33
Application – Suite de Fibonacci
 On considère la suite de Fibonacci donnée par la relation
de récurrence :
1 si n = 0 ou n = 1
Fib(n) =
Fib(n −1) + Fib(n − 2) sinon

 La complexité est donnée par l’équation de récurrence

suivante :
T(n) = T(n −1) + T (n − 2)
 Il s’agit d’une équation linéaire d’ordre 2 sans
second membre.
 Polynôme caractéristique associé: P(x) = x2 − x −1

34
 Application – Suite de Fibonacci
 L’équation x2-x-1=0 admet deux racines r1 et r2 tels que :

1+ 5 r2 = 1- 5
r1 =
2 2

 La solution de l’équation de récurrence est :

1 si n = 0 ou n = 1
T(n) =
1 ( 1+ 5 )n + 2 ( 1- 5 )n sinon
2 2

35
 Application – Suite de Fibonacci
 On détermine α1 et α2 à partir des conditions initiales

1 +  2 = 1 5+ 5
T (0) = 1 1 =
10
T (1) =1 1 (
1+ 5 n 1− 5 n
) + 2 ( ) =1 2 = 5 − 5
2 2 10
 D’où F(n) est définie par :

5 + 5 1+ 5 n 5 − 5 1− 5 n
T (n) = 10 ( ) + ( )
2 10 2

1+ 5 Complexité
T(n) = O( ( )n) exponentielle
2

36
 Paradigme «Diviser pour Régner »
● La majorité des algorithmes récursifs suivent le paradigme «
diviser- pour-régner». Suivant ce paradigme, un problème est
résolu d’une manière récursive en trois étapes à chaque niveau
de la récursivité:
● Diviser: le problème initial en un certain nombre de sous-
problèmes similaires de tailles plus petites.
● Régner: sur les sous-problèmes en les résolvant de façon
récursive. Si la taille d’un sous-problème est suffisamment
réduite, on a une résolution directe.
● Combiner: les solutions des sous-problèmes pour produire
le solution globale du problème originel.

37
 Analyse des algorithmes «diviser-pour-régner»
 Soit un algorithme récursif qui suit le paradigme « diviser-pour-
régner » pour la résolution d’un problème de taille n.
 Si la taille du problème est suffisamment petite (n ≤c pour une
certaine constante c) alors la résolution est directe et consomme
un temps constant O(1).
 Supposons que l’on divise le problème initial en a sous-problèmes,
chacun de taille n/b. Le temps d'exécution total T(n) de
l’algorithme est donné par la récurrence ayant la forme suivante:

T(n) = O (1) si n  c
aT( n/b ) + D(n) + C(n) sinon

38
Analyse des algorithmes «diviser-pour-
régner»

T(n) = O (1) si n  c
aT( n/b ) + D(n) + C(n) sinon

 aT (n/b) : le temps de résolution des a sous-problèmes (étape

régner)
 D(n) : le temps nécessaire à la division du problème en sous-
problèmes (étape diviser).
 C(n) : le temps nécessaire pour construire la solution finale à
partir des solutions aux sous-problèmes(étape combiner) .

39
 Exemple 1 -Maximum
 Recherche du maximum dans un tableau, soit T(n) la complexité
en nombre de comparaisons, n est la taille du tableau.
Fonction Maximum(T : Tableau , indDeb, indFin : entier) : entier
Var : M : entier
Début
Si ( indDeb = indFin) alors retourner (T[indDeb])
Sinon
M = (indDeb+indFin)/2 // division du problème
max1 = Maximum (Tab, indDeb, m ) // régner sur le 1er sous-problème
max2 = Maximum (Tab, m+1, indFin)// régner sur le 2ème sous-problème
Si (max1 > max2) alors // combiner les solutions
retourner (max1)
Sinon retourner (max2) Complexité :
FinSi T(n)=2T(n/2)+1
FinSi
Fin une comparaison

40
 Exemple 2 : Tri par fusion

Principe : On part du fait que trier un tableau de taille N, c'est

trier deux tableaux de taille N/2. Une fois les deux tableaux sont
triés, il suffit de les fusionner de sorte à ce que le tableau final soit
trié. Ce tri utilise une notion de récursivité.

41
Exemple 2 : Tri par fusion
 Principe : On part du fait que trier un tableau de taille
N, c'est trier deux tableaux de taille N/2. Une fois les
deux tableaux sont triés, il suffit de les fusionner de sorte
à ce que le tableau final soit trié. Ce tri utilise une notion
de récursivité. Fonction Tri_Fusion (T : tableau[N] , deb, fin) :
 Algorithme : tableau[N]
Variables : mil : entier; T1,T2 : tableau[N/2]
Début
Si (deb >= fin) alors Retourner T ;
Sinon
mil = (deb + fin) Div 2
T1 = Tri_Fusion (T, deb, mil) ;
T2 = Tri_Fusion (T, mil+1, fin)) ;
Retourner (Fusion (T1,T2) );
Finsi
FIN

42
Exemple 2: Tri par fusion
Exemple : Trier la séquence (5,2,4,7,1,3,2,6)
phase de descente

5 2 4 7 1 3 2 6

5 2 4 7 1 3 2 6

5 2 4 7 1 3 2 6

43
Exemple 2: Tri par fusion
phase de remonté

Fonctionnement du tri par fusion

44
Exemple 2: Fusion
Fonction Fusion (T1,T2) : tableau entier
T1 : tableau entier [1...N] ;T2 : tableau entier [1...M]; T: tableau
entier [1...M+N]; i, j: entier; i←1 ;j←1 ;
Tantque (i+j-1 <> N+M) faire
Si (i ≤ N) alors
si (j ≤ M) alors
si (T1[i] < T2[j]) alors T[i+j-1]←T1[i] ;
i←i+1 ; sinon
T[i+j-1]←T2[j] ; j←j+1 ;
Fin si
sinon T[i+j-1]←T1[i]; i←i+1;
Fin si
sinon T[i+j-1]←T2[j] ; j←j+1 ;
Fin si
FinTanque
36 Retourner T ; Tfusion = O(n)
FIN
45
Exemple 2: analyse du tri par fusion
 L’algorithme Tri_Fusion réalise les étapes suivantes:
◦ Diviser : diviser la suite de n éléments en deux sous-suites
de n/2 éléments chacune (complexité est donc en O(1)).
◦ Régner : trier les deux sous-tableaux, de tailles respectives
(n/2), de manière récursive en utilisant le tri par fusion,
d’où une complexité en 2T(n/2).
◦ Combiner : fusionner les deux sous-tableaux pour
produire la réponse. La complexité de cette étape est celle
de l’algorithme de fusion qui est de O(n) pour la
construction d’un tableau solution de taille n.
 La récursivité s’arrête quand la séquence à trier a une
longueur égale à 1 : O(1).
 T(n)=2T(n/2)+ Tfusion=2T(n/2)+ O(n)

46
 Exemple 2: arbre des appels récursifs
 On peut retrouver le même résultat pour la récurrence
T(n)=2T(n/2)+c.n en cumulant les coûts à chaque niveau de
récursivité, soit l’arbre récursif suivant:
cn cn
cn
cn/2 cn/2

cn
log2(n) cn/4 cn/4 cn/4 cn/4

c c c c c c c c cn
n
 Total =c.n (log2(n)+1) = c.n log2(n)+ c.n

47
Analyse des algorithmes «diviser-pour-
régner»
 Si les étapes « Diviser » et « Combiner » d’un
algorithme « diviser-pour-régner » prennent en tout un
temps f(n), alors la fonction T(n) prend la forme
suivante:

T (n) = aT (n/b) + f (n)

 Lorsque f(n)=[Link],
T (n) = aT (n/b) + [Link]

48
Résolution des récurrences des algorithmes «
diviser-pour-régner » :
Théorème :
 Soit T(n) une fonction définie pour les entiers
positifs par la récurrence : T(n) = aT(n/b) + [Link]
avec a ≥ 1 , b > 1 et k ≥ 1,
 T(n) peut être bornée asymptotiquement de la
façon suivante:
◦ cas 1 : Si a > bk alors T(n) = O(nlogb(a) )
◦ cas 2 : Si a = bk alors T(n) = O(nk .logb(n))
◦ cas 3 : Si a < bk alors T(n) = O(nk)

49
Résolution des récurrences des algorithmes
« diviser-pour-régner » : Interprétation
 Dans chacun des trois cas, on compare la fonction f(n)=[Link] à
la fonction nlogba .
 Intuitivement, la solution de la récurrence est déterminée par la
plus grande des deux fonctions pour n assez grand.
 Si c’est la fonction nlogba qui est la plus grande (cas 1) alors la
solution est T(n)=O(nlogba )
 Si c’est la fonction f(n) qui est la plus grande (cas 3), alors la
solution est T(n)=O(nk)
 Si les deux fonctions ont le même comportement asymptotique
(cas 2), on multiplie par un facteur logarithmique et la solution
est donnée par : T(n)= O(nlogb(a).logb n)=O(nk logb n)

50
 Applications
(1) Recherche du Maximum : T(n) = 2T(n/2) + 1
On a : a = 2 , b = 2 et k=0 (1=n0)
Puisque a>bk la solution de recurrence est :
T(n) = O(nlogb(a) )
Or logba=log2(2)=1 d’ou T(n) = O(n)

(2) Tri par fusion : T(n) = 2 T(n/2) + O(n)

On a : a = 2 , b = 2 et k=1;
logba = log22=1
On a a=bk (cas 2) => T(n) = O(nlog2(n)) ;

51
Applications
Considérons les récurrences suivantes:
(3) T(n)=9T(n/3)+n

Pour cette récurrence, on a a=9, b=3 et k=1;

nlogb(a) = nlog3(9) = n2
T(n)= O(n2)

Ona f(n)=n est inférieure à n2

(4) T(n)=T(2n/3)+1
a=1, b=3/2 , k=0
a=bk d’où T(n)=O(log(n))
Autrement nlogb(a) = nlog2(1) = n0 = 1

On est dans le cas 2, puisque f(n)=O(1)=O(nlogb(a))

T(n)=O(log(n))

52
Classes de complexités en temps
 Complexité constante O(1) : pas d'augmentation du temps
d'exécution quand le paramètre croit.
 Complexité logarithmique O(log(n)) : augmentation
très faible du temps d'exécution quand le paramètre croit.
◦ Exemple : algorithmes qui décomposent un problème en
un ensemble de problèmes plus petits (Recherche
dichotomique).
 Complexité linéaire O(n) : augmentation linéaire du temps
d'exécution quand le paramètre croit (si le paramètre double,
le temps double).
◦ Exemple : Algorithmes qui parcourent séquentiellement
des structures linéaires (Recherche dans un tableau).

53
Classes de complexités en temps
 Complexité quasi-linéaire O(nlog(n)) : augmentation un
peu supérieure à O(n).
◦ Exemple : algorithmes qui décomposent un problème en
d'autres plus simples, traités indépendamment et qui combinent
les solutions partielles pour calculer la solution générale (Tri
fusion).
 Complexité quadratique O(n2) : quand le paramètre double,
le temps d'exécution est multiplié par 4.
◦ Exemple : algorithmes avec deux boucles imbriquées.
 Complexité polynomiale O(ni) .
== >Quand le paramètre double, le temps d'exécution
est multiplié par 2i.
◦ Exemple : algorithme utilisant i boucles imbriquées.
 54
Classes de complexités en temps
 Complexité exponentielle O(in) : quand le paramètre double,
le temps d'exécution est élevé à la puissance 2.
 Complexité factorielle O(n!) : asymptotiquement équivalente
à nn
 Encore pire : la fonction d'Ackerman
◦ Ack(0,0) = 1
Fonction Ackerman
◦ Ack(1,1) = 3, Début
◦ Ack(2,2) = 7, si (m = 0) alors Ack(m,n) = n+1
Sinon si ((n=0) et (m > 0)) alors
◦ Ack(3,3) = 61, Ack(m,n) = Ack(m-1,1) Sinon
Ack(m,n) = Ack(m-1, Ack(m,n-1))

◦ Ack(4,4) est supérieur à 1080

55
Représentation graphique des
fonctions de référence
f(n)
n3
n2
2n

[Link](n)
n
Log(n)
n

56
 Exemples de temps d’exécution en fonction de la taille de la
donnée et de la complexité de l’algorithme si on suppose
qu’une instruction est de l’ordre de s

Complexité Log n n n Log n n2 2n

En temps
n=10 3 s 10 s 30 s 100 s 1000 s

n=100 7 s 100 s 700 s 1/100 s 1014 siècles

n=1000 10 s 1000 s 1/100 secondes 1 secondes astronomique

n=10000 13 s 1/100 s 1/7 s 1,7 minutes astronomique

n=100000 17 s 1/10 s 2s 2,8 heures astronomique

57
Complexité en espace mémoire

 Il est quelquefois nécessaire d'étudier la

complexité en mémoire lorsque
l'algorithme requiert de la mémoire
supplémentaire (tableau auxiliaire de
même taille que le tableau donné en
entrée par exemple).
 La complexité en espace est aussi défini
en fonction de la taille de l’entrée.

58
Complexité en espace mémoire
Structures de données
 Une structure de données indique la manière d'organisation
des données dans la mémoire.
 Le choix d'une structure de données adéquate dépend
généralement du problème à résoudre.
 Deux types de structures de données :
◦ Statiques : Les données peuvent être manipulées dans la
mémoire dans un espace statique alloué dès le début de
résolution du problème. Ex : les tableaux
◦ Dynamiques : On peut allouer de la mémoire pour y
stocker des données au fur et à mesure des besoins de la
résolution du problème. Ex: liste chainée, pile, file, …
notion des pointeurs : nécessité de la gestion des liens
entre les données d'un problème en mémoire.
59
Conclusion
 Loi de Moore (empirique) : évolution
technologique : à coût constant, la rapidité
des processeurs double tous les 18 mois (les
capacités de stockage suivent la même loi).
 Constat : le volume des données
stockées dans les systèmes d'informations
augmente de façon exponentielle.
 Conclusion : il vaut mieux optimiser ses
algorithmes qu'attendre des années qu'un
processeur surpuissant soit inventé.

60
Quelques calculs de sommes
usuelles
 Soit n ∈ ℕ∗ et q ∈ ℝ. On a :
◦ Somme de n termes constants :
∑k=1..n q=n×q
◦ Somme des n premiers entiers :
∑k=1..nn=(n×(n+1))/2
◦ Somme des n premiers carrés d'entiers :
∑k=1..n k2=(n×(n+1)×(2n+1))/6
◦ Somme des n premiers termes d'une suite géométrique :
∑k=0..n qk=(1−qn+1)/(1−q)
 Soit q ∈ ℝ.
◦ Si q<1, on a : ∑j=0..r qj ≤1/(1−q)
◦ Si q>1, on a : ∑j=0..r qj ≤qr(1+(1/(q−1))

61