Complexité des algorithmes.

Mustapha JOHRI

CRMEF Marrakech-Sa
Département d'informatique
CPA Informatique
Marrakech

6 janvier 2021
 Introduction

Introduction

Un algorithme utilise plusieurs ressources : le processeur pour exécuter

les instructions, la mémoire pour stocker les données et les résultats, la
bande passante pour envoyer et recevoir les données qui circulent dans un
réseau informatique, etc. Une qualité importante d'un algorithme est son
ecacité (ou sa complexité). C'est grâce à elle que l'on peut dénir ce
qu'est un  bon algorithme et comparer les diérents algorithmes
résolvant le même problème.

1/37

Complexité des algorithmes

 Introduction

Introduction à la complexité des algorithmes

Les concepteurs d'algorithmes doivent consacrer beaucoup d'eorts à

l' ecacité.
Si un algorithme produit un résultat correct et s'il est simple à
implémenter et à corriger, il n'est pas toujours très utile s'il eectue un
temps non raisonnable pour se terminer ou s'il nécessite beaucoup
de mémoire qu'ore un ordinateur ou s'il entraîne des problèmes de
trac réseau, etc.

2/37

Complexité des algorithmes

 Introduction

Introduction à la complexité des algorithmes

Les concepteurs d'algorithmes doivent consacrer beaucoup d'eorts à

l' ecacité.
Si un algorithme produit un résultat correct et s'il est simple à
implémenter et à corriger, il n'est pas toujours très utile s'il eectue un
temps non raisonnable pour se terminer ou s'il nécessite beaucoup
de mémoire qu'ore un ordinateur ou s'il entraîne des problèmes de
trac réseau, etc.
An d'étudier l'ecacité d'un algorithme, les informaticiens
demandent comment ses performances changent en fonction de la
taille du problème. Si l'on double le nombre de valeurs traitées par
l'algorithme, le temps d'exécution double-t-il aussi ? Est-ce qu'il
augmente par un facteur de 4 ? Augmente-t-il de façon exponentielle
de sorte qu'il faut soudainement des années, voir des cycles pour se
terminer ?

2/37

Complexité des algorithmes

Introduction

La théorie de la complexité algorithmique étudie les questions

concernant l'ecacité des algorithmes. Dans ce cours, on s'intéressera
uniquement à l'ecacité temporelle des algorithmes. La mesure
usuelle pour l'ecacité temporelle est la rapidité d'un algorithme,
c'est-`a-dire le temps que va prendre un algorithme pour produire son
résultat. Il s'agit de mesurer le temps d'exécution intrinsèque d'un
algorithme (qui ne dépend que de l'algorithme et pas de son
environnement : la conguration matérielle de l'ordinateur, le compilateur
utilisé, le système d'exploitation, etc).

3/37

Complexité des algorithmes

Introduction

La théorie de la complexité algorithmique étudie les questions

concernant l'ecacité des algorithmes. Dans ce cours, on s'intéressera
uniquement à l'ecacité temporelle des algorithmes. La mesure
usuelle pour l'ecacité temporelle est la rapidité d'un algorithme,
c'est-`a-dire le temps que va prendre un algorithme pour produire son
résultat. Il s'agit de mesurer le temps d'exécution intrinsèque d'un
algorithme (qui ne dépend que de l'algorithme et pas de son
environnement : la conguration matérielle de l'ordinateur, le compilateur
utilisé, le système d'exploitation, etc).

Dénition

On appelle complexité d'un algorithme le nombre asymptotique

d'opérations de base qu'il doit eectuer en fonction de la taille de l'entrée.
Cette complexité est indépendante de l'environnement où s'exécute
l'algorithme.

3/37

Complexité des algorithmes

 Introduction

Introduction

Une optimisation qui fait diminuer le nombre asymptotique d'opérations de

base (et donc la complexité) doit être vue comme une amélioration de la
performance d'algorithme. La dénition précédente met en jeu deux notions
très importantes :

4/37

Complexité des algorithmes

 Introduction

Introduction

Une optimisation qui fait diminuer le nombre asymptotique d'opérations de

base (et donc la complexité) doit être vue comme une amélioration de la
performance d'algorithme. La dénition précédente met en jeu deux notions
très importantes :

La taille de l'entrée : comment l'identier ?

Les opérations de base d'un algorithme : comment les identier et
comment les compter ?

4/37

Complexité des algorithmes

 Introduction

Introduction

Une optimisation qui fait diminuer le nombre asymptotique d'opérations de

base (et donc la complexité) doit être vue comme une amélioration de la
performance d'algorithme. La dénition précédente met en jeu deux notions
très importantes :

La taille de l'entrée : comment l'identier ?

Les opérations de base d'un algorithme : comment les identier et
comment les compter ?

Remarque

Dans ce cours, on s'intéressera le plus souvent à la recherche d'une

estimation par excès (à une constante positive multiplicative près) du
cas le plus défavorable sur le sous-ensemble des instances de taille xée
n → complexité dans le pire des cas).

4/37

Complexité des algorithmes

 Introduction

Notations asymptotiques

Par la suite, on ne considère que des fonctions dénies de N vers

R.

5/37

Complexité des algorithmes

 Introduction

Notations asymptotiques

Par la suite, on ne considère que des fonctions dénies de N vers

[Link] de Big O (notation de Landau)
Dénition (Borne supérieure asymptotique)

Une fonction g(n) est une borne supérieure asymptotique pour une fonction
f (n), si et seulement si :

(∃C > 0)(∃n0 ≥ 0) : f (n) ≤ C.g(n); (∀n ≥ n0 )

On note : f (n) = O(g(n)).

Exemple (n + 1)2 = O(n2 ).

5/37

Complexité des algorithmes

 Introduction

Notations asymptotiques

Dénition (Borne inférieure asymptotique)

Une fonction g(n) est une borne inférieure asymptotique pour une fonction
f (n), si et seulement si :

(∃C > 0)(∃n0 ≥ 0) : f (n) ≥ C.g(n); (∀n ≥ n0 )

On note : f (n) = Ω(g(n)).

Exemple (n + 1)2 = Ω(n2 ).

6/37

Complexité des algorithmes

 Introduction

Notations asymptotiques

Dénition (Borne asymptotique)

Une fonction g(n) est une borne asymptotique pour une fonction f (n), si et
seulement si :

(∃C1 > 0)(∃C2 > 0)(∃n0 ≥ 0) : C1 .g(n) ≤ f (n) ≤ C2 .g(n); (∀n ≥ n0 )

On note : f (n) = Θ(g(n)).

Exemple (n + 1)2 = Θ(n2 ).

7/37

Complexité des algorithmes

 Introduction

Notations asymptotique

Propositions

f (n) = Θ(g(n)) ⇐⇒ f (n) = O(g(n)) et f (n) = Ω(g(n)).

Si f (n) = O(g(n)) alors g(n) = Ω(f (n))

8/37

Complexité des algorithmes

 Introduction

Notations asymptotique

Propositions

f (n) = Θ(g(n)) ⇐⇒ f (n) = O(g(n)) et f (n) = Ω(g(n)).

Si f (n) = O(g(n)) alors g(n) = Ω(f (n))

Remarque

Les écritures f (n) = O(g(n)), f (n) = Ω(g(n)) ou f (n) = Θ(g(n)) ne sont

pas des égalités au sens mathématique. Il s'agit d'abréviations d'écritures.

8/37

Complexité des algorithmes

 Introduction

Notations asymptotique

Propositions

f (n) = Θ(g(n)) ⇐⇒ f (n) = O(g(n)) et f (n) = Ω(g(n)).

Si f (n) = O(g(n)) alors g(n) = Ω(f (n))

Remarque

Les écritures f (n) = O(g(n)), f (n) = Ω(g(n)) ou f (n) = Θ(g(n)) ne sont

pas des égalités au sens mathématique. Il s'agit d'abréviations d'écritures.

Par exemple, l'écriture f (n) = O(g(n)) signie que la fonction f (n)

appartienne à l'ensemble des fonctions qui sont asymptotiquement majorées
par la fonction g(n)), à une constante positive près.
On écrit f (n) = O(g(n)) pour dire que f (n) ∈ O(g(n)), sachant que :

O(g(n)) = {h(n)|(∃C > 0), (∃n0 ≥ 0) : h(n) ≤ C.g(n), (∀n ≥ n0 )}

8/37

Complexité des algorithmes

Introduction

Proposition

(Réexivité).
1 f (n) = O(f (n)).
2 f (n) = Ω(f (n)).
3 f (n) = Θ(f (n)).

9/37

Complexité des algorithmes

Introduction

Proposition

(Réexivité).
1 f (n) = O(f (n)).
2 f (n) = Ω(f (n)).
3 f (n) = Θ(f (n)).
(Transitivité).
1 f (n) = O(g(n)) et g(n) = O(h(n)) → f (n) = O(h(n)).
2 f (n) = Ω(g(n)) et g(n) = Ω(h(n)) → f (n) = Ω(h(n)).
3 f (n) = Θ(g(n)) et g(n) = Θ(h(n)) → f (n) = Θ(h(n)).

9/37

Complexité des algorithmes

Introduction

Proposition

(Réexivité).
1 f (n) = O(f (n)).
2 f (n) = Ω(f (n)).
3 f (n) = Θ(f (n)).
(Transitivité).
1 f (n) = O(g(n)) et g(n) = O(h(n)) → f (n) = O(h(n)).
2 f (n) = Ω(g(n)) et g(n) = Ω(h(n)) → f (n) = Ω(h(n)).
3 f (n) = Θ(g(n)) et g(n) = Θ(h(n)) → f (n) = Θ(h(n)).
(Symétrie)
1 f (n) = Θ(g(n)) ⇐⇒ g(n) = Θ(f (n))

9/37

Complexité des algorithmes

Introduction

Proposition

(Réexivité).
1 f (n) = O(f (n)).
2 f (n) = Ω(f (n)).
3 f (n) = Θ(f (n)).
(Transitivité).
1 f (n) = O(g(n)) et g(n) = O(h(n)) → f (n) = O(h(n)).
2 f (n) = Ω(g(n)) et g(n) = Ω(h(n)) → f (n) = Ω(h(n)).
3 f (n) = Θ(g(n)) et g(n) = Θ(h(n)) → f (n) = Θ(h(n)).
(Symétrie)
1 f (n) = Θ(g(n)) ⇐⇒ g(n) = Θ(f (n))
(Symétrie transposée)
1 f (n) = O(g(n)) ⇐⇒ g(n) = Ω(f (n))

9/37

Complexité des algorithmes

 Introduction

Notations asymptotiques

(Fonctions classiques).

Parties entières : bnc = Θ(n) et dne = Θ(n).

Polynômes (asymptotiquement positifs) :
d
X
P (n) = ai ni = ad nd + . . . + a0 = Θ(nd )
i=0

Exponentielles : limn→∞ ( annb ) = 0 ⇐⇒ Toute fonction exponentielle

dont la base est strictement plus grande que 1 croit plus vite que toute
fonction polynomiale.

10/37

Complexité des algorithmes

 Introduction

Notations asymptotiques

(Fonctions classiques).

Parties entières : bnc = Θ(n) et dne = Θ(n).

Polynômes (asymptotiquement positifs) :
d
X
P (n) = ai ni = ad nd + . . . + a0 = Θ(nd )
i=0

Exponentielles : limn→∞ ( annb ) = 0 ⇐⇒ Toute fonction exponentielle

dont la base est strictement plus grande que 1 croit plus vite que toute
fonction polynomiale.

Logarithmes : limn→∞ ( lognba(n) ) = 0 ⇐⇒ Toute fonction polynomiale

croit plus vite que toute fonction poly-logarithmique.
√
Factorielles : n! = 2πn( ne )n (1 + Θ(1/n)) (Formule de Stirling).

10/37

Complexité des algorithmes

 Introduction

Théorème maître

(Récurrences de partition)

Soeint a>0 et b≥2 (souvent des entiers). Une récurrence de partition est
une équation récurrente ayant la forme suivante :
(
Θ(1), si n = 1
T (n) =
aT (n/b) + f (n) si n > 1

11/37

Complexité des algorithmes

 Introduction

Théorème maître

(Récurrences de partition)

Soeint a>0 et b≥2 (souvent des entiers). Une récurrence de partition est
une équation récurrente ayant la forme suivante :
(
Θ(1), si n = 1
T (n) =
aT (n/b) + f (n) si n > 1

(Théorème fondamental, ou Master theorem).

Soit (
Θ(1), si n = 1
T (n) =
aT (n/b) + Θ(nd ) si n>1

1 Si d > logb (a), alors T (n) = Θ(nd ).

2 Si d = logb (a), alors T (n) = Θ(nd logb (n))
3 Si d logb (a), alors T (n) = Θ(nlogb (a) ).
11/37
Preuve : Devoir libre
Complexité des algorithmes
 Introduction

Exemples

T (n) = 8T (n/2) + 5n2 ⇐⇒ T (n) = Θ(n3 ).

Car a = 8, b = 2, d = 2 et logb (a) = 3 > d.

12/37

Complexité des algorithmes

 Introduction

Exemples

T (n) = 8T (n/2) + 5n2 ⇐⇒ T (n) = Θ(n3 ).

Car a = 8, b = 2, d = 2 et logb (a) = 3 > d.

T (n) = 4T (n/2) + n2 ⇐⇒ T (n) = Θ(n2 log2 (n)).

12/37

Complexité des algorithmes

 Introduction

Exemples

T (n) = 8T (n/2) + 5n2 ⇐⇒ T (n) = Θ(n3 ).

Car a = 8, b = 2, d = 2 et logb (a) = 3 > d.

T (n) = 4T (n/2) + n2 ⇐⇒ T (n) = Θ(n2 log2 (n)).

T (n) = T (n/2) + 3n2 ⇐⇒ T (n) = Θ(n2 ).

12/37

Complexité des algorithmes

 Introduction

Analyse de la complexité des algorithmes

Analyse de la complexité des algorithmes

Soit un problème P pour lequel on connaît un algorithme A (qui se termine
et est correct) pour le résoudre. Il prend en entrée une donnée valide d, et
produit un résultat en sortie A(d) en utilisant certaines ressources. Une
façon naturelle pour mesurer la complexité d'un algorithme est de la
considérer pour les entrées d d'une certaine taille xe, disons n. Nous
notons cet ensemble par :

Dn = {I ∈ P | size(d) = n, ∀ d ∈ I}

13/37

Complexité des algorithmes

 Introduction

Analyse de la complexité des algorithmes

Analyse de la complexité des algorithmes

Soit un problème P pour lequel on connaît un algorithme A (qui se termine
et est correct) pour le résoudre. Il prend en entrée une donnée valide d, et
produit un résultat en sortie A(d) en utilisant certaines ressources. Une
façon naturelle pour mesurer la complexité d'un algorithme est de la
considérer pour les entrées d d'une certaine taille xe, disons n. Nous
notons cet ensemble par :

Dn = {I ∈ P | size(d) = n, ∀ d ∈ I}

Il faut alors dénir une mesure de taille sur les données. Cette mesure
doit reéter la quantité d'information contenue dans une donnée d. Il
sera très commode de comparer des algorithmes traitant ce problème selon
cette mesure de taille.

13/37

Complexité des algorithmes

 Introduction

Exemples

Pour l'addition de deux nombres, la taille peut être le nombre de

chires des nombres.
Pour le cas de la recherche ou de tri, la taille peut être le nombre
des éléments du tableau.
Pour le cas du produit de matrices, la taille peut être la dimension
des matrices.

parcours d'un graphe, la taille peut être le nombre de

Pour le
sommets ou nombre d'arcs dans le graphe.

14/37

Complexité des algorithmes

 Introduction

Opérations fondamentales

Pour tout algorithme traitant un problème donné, on peut toujours mettre

opérations dites de base (ou fondamentales)
en évidence une ou plusieurs
proportionelle au
au sens où l'ecacité (temporelle) de l'algorithme soit
nombre de ces opérations. Il est donc naturel de mesurer la complexité
d'un algorithme en considérant le nombre de ces opérations de base.

15/37

Complexité des algorithmes

 Introduction

Opérations fondamentales

Pour tout algorithme traitant un problème donné, on peut toujours mettre

opérations dites de base (ou fondamentales)
en évidence une ou plusieurs
proportionelle au
au sens où l'ecacité (temporelle) de l'algorithme soit
nombre de ces opérations. Il est donc naturel de mesurer la complexité
d'un algorithme en considérant le nombre de ces opérations de base.

Il faut donc qu'étant donnée une entrée d, on sache clairement associer à

l'algorithme A sur l'entrée d, la valeur de cette mesure, notée µ(A, d). La
fonction µ(A, d) dépend de A, mais aussi de l'entrée d. La qualité d'un
algorithme A n'est donc pas un critère absolu, mais une fonction
quantitative µ(A, d) dénie de Dn vers N.

15/37

Complexité des algorithmes

 Introduction

Exemples

Pour la recherche d'un élément dans un tableau : µ(A, d) = nombre

de comparaisons entre cet élément et les éléments du tableau.
Pour la recherche d'un élément sur un disque : µ(A, d) = nombre
d'accès à la mémoire de masse.
Pour le tri interne d'un tableau : µ(A, d)= nombre de comparaisons
entre les éléments du tableau.

µ(A, d) = nombre d'additions et de

Pour multiplier deux matrices :
multiplications entre les coecients des matrices.

16/37

Complexité des algorithmes

 Introduction

Quelques règles de mesure de coût

Quelques règles de mesure de coût

Après avoir déterminé les opérations fondamentales (OF ) d'un algorithme,
il faut de compter le nombre des OF de chaque type. Notons par N OF (X),
le nombre des OF d'une construction algorithmique X. Voici quelques
règles pour compter le N OF d'un algorithme :

17/37

Complexité des algorithmes

 Introduction

Quelques règles de mesure de coût

Quelques règles de mesure de coût

Après avoir déterminé les opérations fondamentales (OF ) d'un algorithme,
il faut de compter le nombre des OF de chaque type. Notons par N OF (X),
le nombre des OF d'une construction algorithmique X. Voici quelques
règles pour compter le N OF d'un algorithme :

Lorsque les OF de base se trouvent dans une séquence d'instructions,

leurs nombres s'ajoutent.

Pour une conditionnelle :

NOF(IF (Cond) THEN I1 ELSE I2) ≤ NOF(Cond) +
max(NOF(I1),NOF(I2)).
P
Pour une boucle, le N OF dans une boucle est j N OF (Ij ), où j est
l'incrément de la boucle et N OF (Ij ) est le N OF dans la j − eme
itération.

Pour les appels de procédures récursives, le calcul des N OF donne en

général lieu à la résolution de relations de récurrence.
17/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

18/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

L'algorithme 1 échange deux entiers. L'OF est l'aectation et le NOF de

l'algorithme est 3 → l'algorithme est de complexité O(1).

18/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

19/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

L'algorithme 2 calcule la somme des n premiers entiers. L'OF est l'addition

et le NOF de l'algorithme est n ⇐⇒ la complexité de l'algorithme est alors
O(n).
19/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

20/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

L'algorithme 4 calcule le nombre de chires d'un entier n. L'OF est l'ajout

de 1. La complexité T (n) de l'algorithme vérie :
(
0, si n < 10
T (n) = n
T ( 10 ) + 1, sinon

D'après le théorème maître, on a

T (n) = Θ(log10 (n)) 20/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

21/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

L'algorithme 5 teste si le nombre entier n est premier. L'OF est le test de la

divisibilité de n par d. Soit T (n) le NOF de l'algorithme.

Si n < 2, alors T (n) = 0.

Lorsque n ≥ 2, il y a deux cas : 21/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

1 Si n est premier, l'algorithme testera pour la divisibilité les nombres de

2 jusqu'`a n/2. Donc T (n) = O((n/2 − 2) + 1) = O(n/2 − 1).
2 Si n n'est pas premier, l'algorithme testera pour la divisibilité les
nombres de 2 jusqu'à d, où d est le plus petit diviseur de n. Donc,
T (n) = O((d − 2) + 1) = O((d − 1)).
Par conséquent, T (n) ≤ O(n/2 − 1) ≤ O(n), ∀ n ≥ 0.
La complexité de l'algorithme est alors O(n).

22/37

Complexité des algorithmes

 Introduction

Exemples de calcul de complexité

√
La complexité de l'algorithme est alors O( n).

23/37

Complexité des algorithmes

 Introduction

Exercice

Donner la complexité de l'algorithme suivant :

24/37

Complexité des algorithmes

 Introduction

Exercice

Donner la complexité de l'algorithme suivant :

Pour l'algorithme 7, les OF sont les additions et les multiplications. On

s'intéresse à leur nombre. Il est clair que :

N OF (algo) = N OF (boucle1) + N OF (boucle2) 24/37

Complexité des algorithmes

 Introduction

Exercice

La 1-ère boucle s'eectue n fois, et chaque itération exécute une seule

addition. Donc, N OF (boucle1) = n.
La 2-ème boucle contient une boucle (sur j) imbriquée dans une autre
boucle (sur i). La boucle interne sur j s'eectue i fois, et chacune de ses
itérations exécute une seule addition et une seule multiplication. Donc,
N OF (boucle sur j) = [Link] boucle externe
Pn sur i s'eectue n2fois. Par
n
suite, N OF (boucle2) = i=1 (2i) = 2 i=1 i = n(n + 1) = n + n.
Finalement, N OF (algo) = n + (n2 + n) = n2 + 2n.
La complexité de l'algorithme machin1 est alors O(n2 ).

25/37

Complexité des algorithmes

 Introduction

Exercice

Donner la complexité de l'algorithme suivant :

26/37

Complexité des algorithmes

 Introduction

Exercice

Donner la complexité de l'algorithme suivant :

Pour l'algorithme machin2, les OF sont les additions et les multiplications.

Remarquons qu'il s'agit d'un algorithme récursif. Soit T (n) le NOF de
l'algorithme.
26/37

Complexité des algorithmes

 Introduction

Exercice

Si n = 0, l'algorithme s'arrête et retourne une valeur simple. C'est une

tâche en O(1).
Si n ≥ 1, l'algorithme exécute une boucle, suivie d'un appel récursif
avec l'argument n/2 et d'une addition.

Nous avons : T (n) = N OF (boucle) + T (n/2) + 1.

La boucle s'eectue n fois, et chaque itération exécute une addition et
une multiplication. Par suite, N OF (boucle) = 2n.
Finalement, T (n) = T (n/2) + (2n + 1) = T (n/2) + O(n).
Il s'agit d'une récurrence de partition, avec a = 1, b = 2 et d = 1.
Comme, logb ((a) = 0 < d, alors d'après le théorème fondamentale :

T (n) = O(nd ) = O(n).

27/37

Complexité des algorithmes

 Introduction

Types de complexités d'un algorithmes

Pour certains algorithmes, la complexité ne dépend que de la taille des

données. Mais la plupart du temps la complexité varie aussi, pour une
taille xée des données, en fonction de la conguration de la donnée.

28/37

Complexité des algorithmes

 Introduction

Types de complexités d'un algorithmes

Pour certains algorithmes, la complexité ne dépend que de la taille des

données. Mais la plupart du temps la complexité varie aussi, pour une
taille xée des données, en fonction de la conguration de la donnée.

Soit A un algorithme qui résout un problème P. L'ensemble des données d

valides (les instances) pour A et de taille n sera noté par Dn . On notera
µ(A, d) le coût en temps de calcul de l'algorithme A lorsqu'il traite la
donnée d. Soit p(d) la probabilité que l'on ait la donnée d en entrée de
l'algorithme. Il y a trois types de complexités :

28/37

Complexité des algorithmes

 Introduction

Types de complexités d'un algorithmes

Pour certains algorithmes, la complexité ne dépend que de la taille des

données. Mais la plupart du temps la complexité varie aussi, pour une
taille xée des données, en fonction de la conguration de la donnée.

Soit A un algorithme qui résout un problème P. L'ensemble des données d

valides (les instances) pour A et de taille n sera noté par Dn . On notera
µ(A, d) le coût en temps de calcul de l'algorithme A lorsqu'il traite la
donnée d. Soit p(d) la probabilité que l'on ait la donnée d en entrée de
l'algorithme. Il y a trois types de complexités :
1 La complexité dans le meilleur des cas :
M INA (n) = min{µ(A, d)| d ∈ Dn }

28/37

Complexité des algorithmes

 Introduction

Types de complexités d'un algorithmes

Pour certains algorithmes, la complexité ne dépend que de la taille des

données. Mais la plupart du temps la complexité varie aussi, pour une
taille xée des données, en fonction de la conguration de la donnée.

Soit A un algorithme qui résout un problème P. L'ensemble des données d

valides (les instances) pour A et de taille n sera noté par Dn . On notera
µ(A, d) le coût en temps de calcul de l'algorithme A lorsqu'il traite la
donnée d. Soit p(d) la probabilité que l'on ait la donnée d en entrée de
l'algorithme. Il y a trois types de complexités :
1 La complexité dans le meilleur des cas :
M INA (n) = min{µ(A, d)| d ∈ Dn }

2 La complexité dans le pire des cas :

M AXA (n) = max{µ(A, d)| d ∈ Dn }

28/37

Complexité des algorithmes

 Introduction

Types de complexités d'un algorithmes

Pour certains algorithmes, la complexité ne dépend que de la taille des

données. Mais la plupart du temps la complexité varie aussi, pour une
taille xée des données, en fonction de la conguration de la donnée.

Soit A un algorithme qui résout un problème P. L'ensemble des données d

valides (les instances) pour A et de taille n sera noté par Dn . On notera
µ(A, d) le coût en temps de calcul de l'algorithme A lorsqu'il traite la
donnée d. Soit p(d) la probabilité que l'on ait la donnée d en entrée de
l'algorithme. Il y a trois types de complexités :
1 La complexité dans le meilleur des cas :
M INA (n) = min{µ(A, d)| d ∈ Dn }

2 La complexité dans le pire des cas :

M AXA (n) = max{µ(A, d)| d ∈ Dn }

3 La complexité en moyenne :
X
M OYA (n) = p(d) × µ(A, d)
28/37
d∈Dn

Complexité des algorithmes

 Introduction

Types de complexités d'un algorithmes

1 La complexité dans le meilleur des cas donne une borne inférieure du

temps d'exécution. Elle se formule en terme de Ω(f (n)).
2 La complexité dans le pire des cas donne une borne supérieure du
temps d'exécution. C'est la complexité la plus utilisée. Elle se formule
en terme de O(f (n)).
3 La complexité en moyenne permet de savoir quel comportement
attendu en général de l'algorithme. Elle est souvent plus dicile à
calculer. Elle se formule en terme de Θ(f (n)).

29/37

Complexité des algorithmes

 Introduction

Classe des complexités

Les classes de complexités usuelles :

Algorithmes constants : O(1).
Algorithmes logarithmiques : O(log(n)).
Algorithmes linéaires : O(n).
Algorithmes quasi-linéaires : O(n log(n)).
2
Algorithmes quadratiques : O(n ).
d
Algorithmes polynomiaux : O(n ).
n
Algorithmes exponentiels : O(a ), avec a > 1.
Algorithmes factoriels : O(n!).

30/37

Complexité des algorithmes

 Introduction

Classe des complexités

Les classes de complexités usuelles :

Algorithmes constants : O(1).
Algorithmes logarithmiques : O(log(n)).
Algorithmes linéaires : O(n).
Algorithmes quasi-linéaires : O(n log(n)).
2
Algorithmes quadratiques : O(n ).
d
Algorithmes polynomiaux : O(n ).
n
Algorithmes exponentiels : O(a ), avec a > 1.
Algorithmes factoriels : O(n!).

Remarque

O(1) ⊆ O(log(n)) ⊆ O(n) ⊆ O(n log(n)) ⊆ O(n2 ) ⊆ O(nd ) ⊆ O(an ) ⊆ O(n!)

Pour certains problèmes, il n'existe pas d'algorithmes polynomiaux pour les

résoudre → problèmes NP-Complets.
Les algorithmes exponentiels ou factoriels sont de très mauvais algorithmes.
Ils sont inecaces en pratique. 30/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Résolution d'équations homogènes à coecients constants

Rappelons qu'une équation linéaire à coecients constants et homogène est
de la forme suivante :

ck T (n + k) + ck−1 T (n + k − 1) + . . . + c0 T (n) = 0 (∗∗)

T (n0 ) = d0 , . . . T (n0 + k − 1) = dk−1 .

31/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Résolution d'équations homogènes à coecients constants

Rappelons qu'une équation linéaire à coecients constants et homogène est
de la forme suivante :

ck T (n + k) + ck−1 T (n + k − 1) + . . . + c0 T (n) = 0 (∗∗)

T (n0 ) = d0 , . . . T (n0 + k − 1) = dk−1 .

Dénition

L'équation caractéristique de la relation (**) correspond à l'équation

polynomiale suivante :

ck rk + ck−1 rk−1 + . . . + c0 = 0

31/37

Complexité des algorithmes

 Introduction

Récurrence linéaire

Théorème

La solution générale de l'équation (**) est de la forme suivante :

l mi −1
X X
rin aij nj

T (n) =
i=1 j=0

32/37

Complexité des algorithmes

 Introduction

Récurrence linéaire

Théorème

La solution générale de l'équation (**) est de la forme suivante :

l mi −1
X X
rin aij nj

T (n) =
i=1 j=0

où

le paramètre l≤k désigne le nombre de racines distinctes de l'équation

caractéristique correspondante.

le paramètre ri désigne une racine de l'équation caractéristique.

le paramètre mi désigne la multiplicité de la racine ri .

les coecients aij sont des constantes qui sont déterminées à partir des
conditions initiales.

32/37

Complexité des algorithmes

 Introduction

Exemple

Résoudre l'équation suivante :

T (n + 3) − 7T (n + 2) + 16T (n + 1) − 12T (n) = 0, ∀n ≥ 3

T (0) = 0, T (1) = 1, T (2) = 2.

33/37

Complexité des algorithmes

 Introduction

Exemple

Résoudre l'équation suivante :

T (n + 3) − 7T (n + 2) + 16T (n + 1) − 12T (n) = 0, ∀n ≥ 3

T (0) = 0, T (1) = 1, T (2) = 2.

L'équation caractéristique de cette relation est :

r3 − 7r2 + 16r − 12 = 0
Les racines de cette équation sont

r1 = 3 ; racine simple,

r2 = 2 ; racine double.

Par conséquent, la solution générale

T (n) = a1 r1n + (a2 + a3 n)r2n

Autrement dit T (n) = a1 3n + (a2 + a3 n)2n
La solution nale est alors

T (n) = −2.3n + 2n+1 + 3n2n−1 33/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Résolution d'équations non homogènes à coecients constants

34/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Résolution d'équations non homogènes à coecients constants

Rappelons qu'une équation linéaire à coecients constants et homogène est
de la forme suivante :

ck T (n + k) + ck−1 T (n + k − 1) + . . . + c0 T (n) = g(n) (∗∗)

T (n0 ) = d0 , . . . T (n0 + k − 1) = dk−1 .

34/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Résolution d'équations non homogènes à coecients constants

Rappelons qu'une équation linéaire à coecients constants et homogène est
de la forme suivante :

ck T (n + k) + ck−1 T (n + k − 1) + . . . + c0 T (n) = g(n) (∗∗)

T (n0 ) = d0 , . . . T (n0 + k − 1) = dk−1 .

Le principe de résolution, adopté dans cette section, consiste à éliminer
d'abord la fonction g(n), et ensuite résoudre l'équation homogène ainsi
trouvée à l'aide de la méthode discutée précédemment.

34/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Une technique permettant d'éliminer plusieurs types de fonctions g(n),

d'une manière systématique, est l'utilisation de l'opérateur E (Opérateur
d'avancement).

Dénition

35/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Une technique permettant d'éliminer plusieurs types de fonctions g(n),

d'une manière systématique, est l'utilisation de l'opérateur E (Opérateur
d'avancement).

Dénition

Étant donnée une suite de nombres entiers, f (n), l'opérateur d'avancement

E est déni comme suit :

f (n) = c (une constante) → E(f (n)) = c

f (n) 6= constante → E(f (n)) = f (n + 1).

35/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Une technique permettant d'éliminer plusieurs types de fonctions g(n),

d'une manière systématique, est l'utilisation de l'opérateur E (Opérateur
d'avancement).

Dénition

Étant donnée une suite de nombres entiers, f (n), l'opérateur d'avancement

E est déni comme suit :

f (n) = c (une constante) → E(f (n)) = c

f (n) 6= constante → E(f (n)) = f (n + 1).

La multiplication et l'addition d'opérateurs sont dénies comme suit :

(E1E2)f (n) = E1(E2(f (n))

(E1 + E2)f (n) = E1(f (n)) + E2(f (n))

Exemple : (E − 2)2n = E(2n ) − 2(2n ) = 2n+1 − 2n+1 = 0
35/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Proposition

Si X annule f alors X annule E(f )

Si X annule f et g alors X annule f (+/−) g

Si X annule f alors X annule αf, ∀α ∈ C∗
Si X annule f et Y annule g alors XY annule f (+/−) g

36/37

Complexité des algorithmes

 Introduction

Résolution des équations récurrentes

Proposition

Si X annule f alors X annule E(f )

Si X annule f et g alors X annule f (+/−) g

Si X annule f alors X annule αf, ∀α ∈ C∗
Si X annule f et Y annule g alors XY annule f (+/−) g

Fonction Annulateur
α E−1
αan E−a
αan + βbn (a 6= b) (E − a)(E − b)
Pk n
i=1 αi ai Πki=1 (E − ai )
αn + β (E − 1)2
(αn + β)an (E − a)2
( di=0 αi ni )an (E − a)d+1
P

36/37

Complexité des algorithmes

 Introduction

Exercices

Exercice

Résoudre les récurrences suivantes :

T (n) = 2T (n − 1) + 1, avec T (0) = 0

T (n) = T (n − 1) + T (n − 2) + 1,
T (n) = T (n − 1) + 2T (n − 2) + 2n + n2

37/37

Complexité des algorithmes

 Introduction

Exercices

Exercice

Résoudre les récurrences suivantes :

T (n) = 2T (n − 1) + 1, avec T (0) = 0

T (n) = T (n − 1) + T (n − 2) + 1,
T (n) = T (n − 1) + 2T (n − 2) + 2n + n2

Corrigé

T (n) = 2n − 1, en eet
T (n) = 2T (n − 1) + 1 → (E − 2)T (n) = 1 → (E − 2)(E − 1)T (n) = 0,
n n
donc T (n) = a.2 + b.1 or T (0) = 0, → a = −b
√
T (n) = O(φn ), avec φ= 1+ 5
2
T (n) = O(n2n )

37/37

Complexité des algorithmes