Cours : Algorithmique Avancée (AA)

Chapitre 1:Théorie de la complexité

COURS : ALGORITHMIQUE AVANCÉE

CHAPITRE 1: THÉORIE DE LA COMPLEXITÉ

Section: 1 Mastère Infotronique

Enseignante: Dr. Souad BOUASKER

Source: Cours Dr. D. MAATER (ESEN, Mannouba)

Année Universitaire 2020-2021

PLAN DU COURS

Chapitre 1: La théorie de la complexité

Chapitre 2: La récursivité et le paradigme « diviser pour régner »
Chapitre 3: Algorithmes de tri
Chapitre 4: Structures de données élémentaires
Chapitre 5: Programmation dynamique
Chapitre 6: Algorithmes gloutons
Chapitre 7: NP-complétude
Chapitre 8: Heuristiques: algorithmes d’approximation
Outline
 Introduction
 Théorie de la complexité
 Complexité algorithmique
 Application: algorithmes de recherche (séquentielle et
dichotomique)
 Application: algorithmes de tri (à bulles et sélection)

1
Introduction Qu’est ce que l’algorithmique?

 L’algorithmique est l’étude des algorithmes.

 Un algorithme est une suite d’instructions qui décrit comment
résoudre un problème particulier en un temps fini.

Avez-vous déjà ouvert un livre de recettes de cuisine ?

ou déjà indiqué un chemin à un touriste?

Si oui, sans le savoir, vous avez déjà exécuté des algorithmes.

Si l’algorithme est juste, le résultat est le résultat voulu, et le touriste se retrouve là où il

voulait aller. Si l’algorithme est faux, le résultat est aléatoire, et le touriste est perdu.

Pour fonctionner, un algorithme doit contenir uniquement des instructions

compréhensibles par celui qui devra l’exécuter.
3
Introduction Algorithme et programme

 Un programme (code) : la réalisation (l’implémentation) d’un algorithme au moyen

d’un langage donné (sur une architecture donnée). Il s’agit de la mise en œuvre du principe.

Informations Résultats mis

du problème en forme
machine

Données Obtention de
structurées résultats

Traitement

2
Introduction du raisonnement à l’algorithme au code

Exemple de tâche: Décider si un tableau L est trié en ordre croissant.

 Raisonnement: Un tableau L est trié si tous ses éléments sont dans l’ordre
croissant.
 Algorithme: Une fonction vérifiant cette propriété, supposera donc le tableau L,
de taille n, trié au départ et cherchera une contradiction.
Fonction trie (L: tab, n: entier) : booleen
Variables i, n: entier; Ok: booeen
Début
Ok  vrai
pour i de 1 à n faire
si (L[i ] > L[i +1]) alors
Ok  Faux
Finsi
Finpour
Retourner OK
Fin trie
boolean trie (tab L, int n)
 Code: {
Ok =true;
For (i =0; i< n ; i++)
{ if (L[i ] > L[i +1])
Ok= Faux; } 5
return Ok;}
Introduction double problématique de l’algorithmique

 La question la plus fréquente que se pose à chaque programmeur est la

suivante:
Comment choisir parmi les différentes approches pour résoudre un problème?
Exemples: Trier un tableau: algorithme de tri par insertion ou de tri rapide?…, etc

On attend d’un algorithme qu’il résolve correctement et de manière efficace le

problème à résoudre, quelles que soient les données à traiter.

1. La correction: résout il bien le problème donné?

Trouver une méthode de résolution (exacte ou approchée) du problème.

2. L’efficacité: en combien de temps et avec quelles ressources?

Il est souhaitable que nos solutions ne soient pas lentes, ne prennent pas de
l’espace mémoire considérable.

Savoir résoudre un problème est une chose, le résoudre efficacement en est une autre!
6

3
Introduction Efficacité

L’efficacité d’un algorithme peut être évaluée par:

 Rapidité (en terme de temps d’exécution)

 Consommation de ressources (espace de stockage, mémoire utilisée)

 La théorie de la complexité étudie l’efficacité des algorithmes.

On s’intéresse dans ce cours, essentiellement, à l’efficacité en terme de temps

d’exécution.

7
Théorie de la complexité Définition et Objectifs

 La théorie de la complexité est une branche de l’informatique théorique, elle

cherche à calculer, formellement, la complexité algorithmique nécessaire pour
résoudre un problème P au moyen de l’exécution d’un algorithme A.

La théorie de la complexité vise à répondre aux besoins d’efficacité des

algorithmes (programmes):

Elle permet:

• Classer les problèmes selon leur difficulté.

• Classer les algorithmes selon leur efficacité.

• Comparer les algorithmes résolvant un problème donné afin de faire un choix

sans devoir les implémenter. 8

4
Théorie de la complexité Evaluation de la rapidité d’un algorithme

 On ne mesure pas la durée en heure, minute, seconde… cela impliquerait

d’implémenter les algorithmes qu’ on veut comparer.

Ces mesures ne seraient pas pertinentes car le même algorithme sera plus
rapide sur une machine plus puissante.

Au lieu de ça, on utilise des unités de temps abstraite proportionnelles au

nombre d’opérations effectuées.

Au besoin, on pourra alors adapter ces quantités en fonction de la machine sur
laquelle l’algorithme s’exécute.

9
Théorie de la complexité Calcul du temps d’exécution

Règles:
• Chaque instruction basique consomme une unité de temps (affectation d’une
variable, lecture, écriture, comparaison,…).

• Chaque itération d’une boucle rajoute le nombre d’unités de temps

consommés 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 d’opération effectuées par l’algorithme, on additionne

le tout.

10

5
Théorie de la complexité Calcul du temps d’exécution

Exemple: Temps d’exécution de la fonction factorielle

L’algorithme suivant calcule : n! = n*(n-1)*(n-2)*…*1 avec 0! =1

11
Théorie de la complexité Calcul du temps d’exécution

Exemple: Temps d’exécution de la fonction factorielle

L’algorithme suivant calcule : n! = n*(n-1)*(n-2)*…*1 avec 0! =1

Temps de calcul = 1+1+(2+2+1)*(n-1)+1= 5n-2 opérations

12

6
Théorie de la complexité Calcul du temps d’exécution

Problèmes
Unités de temps abstraites:
 Dépends des données.
 Dépend de la nature des données: on ne sait pas toujours combien de fois
exactement on va exécuter une boucle.
 De même lors d’un branchement conditionnel, le nombre de comparaisons
effectués n’est pas toujours le même.

Temps exacte:
 Dépend de la puissance de la machine.
 Dépend de la nature des données (variables): si on change les données, le temps
change.

Solution
Calcul de la complexité algorithmique
13
Complexité algorithmique Définition

La complexité d’un algorithme est la mesure du nombre d’opérations

fondamentales qu’il effectue sur un jeu de données. Elle est exprimée comme
une fonction de la taille du jeu de données.
Il existe trois types de complexité:
 Complexité au meilleur
C’est le plus petit nombre d’opérations qu’aura à exécuter l’algorithme sur
un jeu de données de taille n.

 Complexité au pire
C’est le plus grand nombre d’opérations qu’aura à exécuter l’algorithme
sur un jeu de données de taille n.

Complexité en moyenne
C’est la moyenne des complexités de l’algorithme sur des jeux de données
de taille n.
14

7
Complexité algorithmique Définition générale

De façon générale: La complexité d’un algorithme est une mesure de sa

performance asymptotique dans le pire des cas.

 asymptotique ?
 on s’intéresse à des données très grandes parce que les petites valeurs ne
sont pas assez informatives.

 Pire des cas ?

on s’intéresse à la performance de l’algorithme dans les situations où le
problème prend le plus de temps à résoudre parce qu’on veut être sûr que
l’algorithme ne prendra jamais plus de temps que ce qu’on a estimé.

Un algorithme est dit « optimal » si sa complexité est la complexité

minimale parmi les algorithmes de sa classe.

15
Complexité algorithmique 0-notation (Notation de Landau)

Quand on calcule la complexité d’un algorithme, on ne calcule

généralement pas sa complexité exacte, mais son ordre de grandeur.

C’est une approximation du temps de calcul de l’algorithme.

Pour ce faire, on a recours à la notation asymptotique O(.) ou

Notation de Landau.
16

8
Complexité algorithmique 0-notation (Notation de Landau)

Cette notation exprime la limite supérieure d’une fonction dans un

facteur constant.
 Soit n la taille des données à traiter, on dit qu’une fonction f(n) et en O(g(n)) si :

 f(n) et en O(g(n))s’il existe un seuil à partir duquel la fonction f(.) est toujours
dominée par g(.), à une constante multiplicative fixée près.

Utilité: Le temps d’exécution est borné

Signification: Pour toutes les grandes entrées (i.e., N >= n0), on est assuré que
l’algorithme ne prend pas plus de c*g(n) étapes.
Borne supérieure. 17
Complexité algorithmique 0-notation (Notation de Landau)

18

9
Complexité algorithmique 0-notation (Notation de Landau)

19
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 1: Prouver que f1(n) = 5n+37 est en O(n)

But: trouver une constante et un seuil à partir duquel

On remarque que 5n +37 <= 6n si n >= 37

On déduit donc que c=6 fonctionne à partir de n0 =37

Remarque: on ne demande pas d’optimiser (le plus petit c ou n0 qui fonctionne)

juste il faut donner des valeurs qui fonctionnent.

20

10
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 2: Prouver que est en

But: trouver une constante et un seuil à partir duquel

Chercher d’abord c, c=6 ne peut pas marcher, donc c=7

On doit donc trouver un seuil n0 à partir du quel :

c=7 et n0 =1

21
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 3: Calculer la complexité de

On remarque que

pour tout n>= 1

Donc est en

22

11
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 4: Calculer la complexité de l’initialisation d’un tableau:

On remarque qu’il y a n itérations; chaque itération nécessite un temps

d’exécution <= c où c est une constante (accès au tableau + une affectation)

 le temps est donc T(n)<= c n

Donc T(n) est en O(n)

23
Complexité algorithmique Règles de calcul

On calcule le temps d’exécution, mais on effectue les simplifications

suivantes:
On oublie les constantes multiplicatives (elles valent 1)
On annule les constantes additives
On ne retient que les termes dominants

Exemple (simplifications) soit :

• On remplace les constantes multiplicatives par 1:
• On annule les constantes additives :
• On garde le terme de plus haut degré:

• On a donc la complexité de

24

12
Complexité algorithmique Règles de calcul

De façon générale, les règles de la notation en O sont les suivantes:

Les termes constants :

O(c) = O(1)
Les constantes multiplicatives sont omises:
O(cT) = c O(T)=O(T)
 L’addition est réalisée en prenant le maximum:
O(T1)+O(T2)= O(T1+T2)=max(O(T1); O(T2))
La multiplication reste inchangée:
O(T1) O(T2)= O(T1*T2)

25
Complexité algorithmique Règles de calcul

Exemple:
Supposons que le temps d’exécution d’un algorithme est décrit par la fonction:
calculer O(T(n))?

Remarque:
Pour n=10, nous avons:

Le poids de devient encore plus grand pour n=100, soit 96,7%, on peut donc négliger les
quantités10n et 10. 26
Ceci explique les règles de notation O.

13
Complexité algorithmique Calcul de complexité

 Cas d’une instruction simple : Les instructions de base (lecture, écriture,

affectation …) prennent un temps constant, noté O(1).
Cas d’une suite d’instructions: le temps d’exécution d’une séquence est
déterminé par la règle de la somme.

Cas d’une branche conditionnelle: le temps d’exécution est déterminé aussi par
la règle de la somme.

27
Complexité algorithmique Calcul de complexité

 Cas d’une boucle: On multiplie la complexité du corps de la boucle par le

nombre d’itérations.
Exemple pour la boucle while (tant que), la complexité se calcule comme suit:

Pour calculer la complexité d’un algorithme:

•On calcule la complexité de chaque partie de l’algorithme.

•On combine ces complexités conformément aux règles déjà vues.
•On effectue sur le résultat les simplifications possibles déjà vues.

28

14
Complexité algorithmique Calcul de complexité

Exemple: calcul de la complexité de la fonction factorielle

Complexité de la fonction = O(1) +O(1)+O[(n -1)*(1+1+1)]+O(1)

= O(1)+O(1)+O(n)+O(1)
= O(n)
29
Complexité algorithmique Classes de complexité

On peut ranger les fonctions équivalentes dans la même classe.

Deux algorithmes de la même classe sont considérés de même complexité.

Les classes de complexité les plus fréquentes (par ordre croissant selon O(.) )

30

15
Complexité algorithmique Classes de complexité

31
Complexité algorithmique Classes de complexité

32

16
Application Algorithmes de recherche

Recherche séquentielle
Principe:
Le principe consiste à parcourir un tableau d'éléments dans l'ordre de
ses indices jusqu'à ce qu'un élément recherché soit trouvé ou bien
que la fin du tableau soit atteinte et l’élément recherché est alors
inexistant.
Exemple:
Soit T un tableau contenant les10 éléments suivants:

Pour x =-2, le programme affichera que ‘’-2 existe’’

Pour x =5, le programme affichera que ‘’5 n’existe pas’’ 33
Application Algorithmes de recherche
Recherche séquentielle
Algorithme:
Fonction Recherche_séquentielle (x:entier,T:tab, n:entier) : booleen
Var
i: entier
trouve: booleen
Début
i←0
trouve ← faux
Tant que ((i<n) et (non trouve)) faire
i ← i +1
si (T[i] = x) alors
trouve ← vrai
finsi
fintq
Retourner (trouve) 34
Fin

17
Application Algorithmes de recherche
Recherche séquentielle
Calcul de complexité:
Fonction Recherche_séquentielle (x:entier,T:tab, n:entier) : booleen
Var i: entier
trouve: booleen
Début
i←0
trouve ← faux
Tant que ((i<n) et (non trouve)) faire
i ← i +1
si (T[i] = x) alors
trouve ← vrai
finsi
fintq
Retourner (trouve)
Fin 35
Application Algorithmes de recherche

Recherche dichotomique
Principe:
On veut chercher un élément dans un tableau trié dans le sens croissant.
Le but de cette recherche est de diviser l’intervalle de recherche par 2 à chaque itération.
Pour cela, on procède de la façon suivante:

Soient premier et dernier les extrémités gauche et droite de l’intervalle dans lequel on cherche
la valeur x, on calcule m, l’indice de l’élément médian:
m=(premier + dernier ) div 2

36

18
Application Algorithmes de recherche

Recherche dichotomique
Principe:
Il y a 3 cas possibles:
• X<T[m], l’élément x s’il existe, il se trouve dans l’intervalle [premier... m-1]
• x > T[m], l’élément de valeur x, s’il existe, se trouve dans l’intervalle [m+1... Dernier]
•X=T[m], x est trouvé, la recherche est terminée
La recherche dichotomique consiste à itérer ce processus jusqu’à ce que l’on trouve x ou
que l‘intervalle de recherche soit vide.
Exemple:
Soit T un tableau contenant les10 éléments suivants:

Pour x =-2, le programme affichera que ‘’-2 existe’’

Pour x =5, le programme affichera que ‘’5 n’existe pas’’
37
Application Algorithmes de recherche
Recherche dichotomique
Algorithme: Procédure recherche_dichotomique ((x:entier,T:tab, n:entier)
Var
premier, dernier, m: entier
trouve : booléen
sinon
Début
trouve ← vrai
premier ←1
Finsi
dernier ← n
Finsi
trouve ← faux
Jusqu’à (trouve=vrai ou premier > dernier)
répéter
Si (trouve) alors
m ← (premier + dernier) div2
écrire(x, "existe et son indice est’’, m)
si(x<T[m]) alors
Sinon
dernier ←m-1
écrire(x, " introuvable ")
sinon
Finsi
si(x>T[m]) alors
fin
premier ← m+1 38

19
Application Algorithmes de recherche
Recherche dichotomique
Calcul de complexité:
Supposant que le tableau est de taille n une puissance de 2, .
Le pire des cas pour la recherche d’un élément est de continuer à diviser jusqu’à obtenir
un tableau de taille 1.
q est le nombre d’itérations nécessaires pour aboutir à un tableau de taille 1.

39
Application Algorithmes de recherche

Optimalité des Algorithmes de recherche

Algorithme de recherche Complexité

Recherche séquentielle O(n)

Recherche dichotomique O(log₂(n))

L’algorithme de recherche séquentielle est de complexité linéaire et celui

de recherche dichotomique est de complexité logarithmique.

L’algorithme de recherche dichotomique est plus optimal que

l’algorithme de recherche séquentielle.
40

20
Algorithmes de tri Tri à bulles
Tri à bulles
Principe:
Elle consiste à répéter le traitement suivant: parcourir les éléments du tableau de 1 à (n-1): si
l’élément i est supérieur à l’élément (i+1) alors, on les permute.
Le programme s’arrête lorsqu’aucune permutation n’est réalisable après le parcours complet
du tableau.
Exemple:

41
Algorithmes de tri Tri à bulles
Tri à bulles
Algorithme: Procédure Tri_à_bulles (T:tab, n:entier)
Var echange: booléen
i: entier
Début
répéter
echange ←faux
pour i de 1 à n-1 faire
si T[i] > T[i+1] alors
x ← T[i]
T[i] ← T[i+1]
T[i+1] ← x
echange ← vrai
finsi
fin pour
jusqu’à (echange = faux) 42
Fin

21
Algorithmes de tri Tri à bulles
Tri à bulles
Calcul de complexité : Procédure Tri_à_bulles (T:tab, n:entier)
Var echange: booléen
x,i: entier
Début
répéter
echange ←faux
pour i de 1 à n-1 faire
si (T[i] > T[i+1]) alors
x ← T[i]
T[i] ← T[i+1]
T[i+1] ← x
echange ← vrai
finsi
fin pour
jusqu’à (echange = faux) 43
Fin
Algorithmes de tri Tri par sélection
Tri par sélection
Principe:
Elle consiste à chercher l’indice du plus petit nombre du tableau (de 1 à n) et le permuter avec
l’élément 1 du tableau, chercher ensuite le plus petit nombre (de 2 à n) et le permuter avec
l’élément 2 du tableau, répéter ce traitement jusqu’à arriver à l’élément n-1.
Exemple:

44

22
Algorithmes de tri Tri par sélection
Tri par sélection
Algorithme: Procédure Tri_par_sélection (T:tab, n:entier)
Var i, j, x, indmin: entier
Début
pour i de 1 à n-1 faire
indmin ← i
pour j de i+1 à n faire
si T[j] < T[indmin] alors
indmin ← j
finsi
finpour
x ← T[i]
T[i] ←T[indmin]
T[indmin] ← x
fin pour
Fin 45
Algorithmes de tri Tri par sélection
Tri par sélection
Calcul de complexité: Procédure Tri_par_sélection (T:tab, n:entier)
Var i, j, x, indmin: entier
Début
pour i de 1 à n-1 faire
indmin ← i
pour j de i+1 à n faire
si T[j] < T[indmin] alors nbres d’itérations
indmin ← j (n-1)
finsi
finpour
x ← T[i]
T[i] ←T[indmin]
T[indmin] ← x
fin pour
Fin 46

23
Outline
 Introduction
 Théorie de la complexité
 Complexité algorithmique
 Application: algorithmes de recherche (séquentielle et
dichotomique)
 Application: algorithmes de tri (à bulles et sélection)

1
Introduction Qu’est ce que l’algorithmique?

 L’algorithmique est l’étude des algorithmes.

 Un algorithme est une suite d’instructions qui décrit comment
résoudre un problème particulier en un temps fini.

Avez-vous déjà ouvert un livre de recettes de cuisine ?

ou déjà indiqué un chemin à un touriste?

Si oui, sans le savoir, vous avez déjà exécuté des algorithmes.

Si l’algorithme est juste, le résultat est le résultat voulu, et le touriste se retrouve là où il

voulait aller. Si l’algorithme est faux, le résultat est aléatoire, et le touriste est perdu.

Pour fonctionner, un algorithme doit contenir uniquement des instructions

compréhensibles par celui qui devra l’exécuter.
3
Introduction Algorithme et programme

 Un programme (code) : la réalisation (l’implémentation) d’un algorithme au moyen

d’un langage donné (sur une architecture donnée). Il s’agit de la mise en œuvre du principe.

Informations Résultats mis

du problème en forme
machine

Données Obtention de
structurées résultats

Traitement

2
Introduction du raisonnement à l’algorithme au code

Exemple de tâche: Décider si un tableau L est trié en ordre croissant.

 Raisonnement: Un tableau L est trié si tous ses éléments sont dans l’ordre
croissant.
 Algorithme: Une fonction vérifiant cette propriété, supposera donc le tableau L,
de taille n, trié au départ et cherchera une contradiction.
Fonction trie (L: tab, n: entier) : booleen
Variables i, n: entier; Ok: booeen
Début
Ok  vrai
pour i de 1 à n faire
si (L[i ] > L[i +1]) alors
Ok  Faux
Finsi
Finpour
Retourner OK
Fin trie
boolean trie (tab L, int n)
 Code: {
Ok =true;
For (i =0; i< n ; i++)
{ if (L[i ] > L[i +1])
Ok= Faux; } 5
return Ok;}
Introduction double problématique de l’algorithmique

 La question la plus fréquente que se pose à chaque programmeur est la

suivante:
Comment choisir parmi les différentes approches pour résoudre un problème?
Exemples: Trier un tableau: algorithme de tri par insertion ou de tri rapide?…, etc

On attend d’un algorithme qu’il résolve correctement et de manière efficace le

problème à résoudre, quelles que soient les données à traiter.

1. La correction: résout il bien le problème donné?

Trouver une méthode de résolution (exacte ou approchée) du problème.

2. L’efficacité: en combien de temps et avec quelles ressources?

Il est souhaitable que nos solutions ne soient pas lentes, ne prennent pas de
l’espace mémoire considérable.

Savoir résoudre un problème est une chose, le résoudre efficacement en est une autre!
6

3
Introduction Efficacité

L’efficacité d’un algorithme peut être évaluée par:

 Rapidité (en terme de temps d’exécution)

 Consommation de ressources (espace de stockage, mémoire utilisée)

 La théorie de la complexité étudie l’efficacité des algorithmes.

On s’intéresse dans ce cours, essentiellement, à l’efficacité en terme de temps

d’exécution.

7
Théorie de la complexité Définition et Objectifs

 La théorie de la complexité est une branche de l’informatique théorique, elle

cherche à calculer, formellement, la complexité algorithmique nécessaire pour
résoudre un problème P au moyen de l’exécution d’un algorithme A.

La théorie de la complexité vise à répondre aux besoins d’efficacité des

algorithmes (programmes):

Elle permet:

• Classer les problèmes selon leur difficulté.

• Classer les algorithmes selon leur efficacité.

• Comparer les algorithmes résolvant un problème donné afin de faire un choix

sans devoir les implémenter. 8

4
Théorie de la complexité Evaluation de la rapidité d’un algorithme

 On ne mesure pas la durée en heure, minute, seconde… cela impliquerait

d’implémenter les algorithmes qu’ on veut comparer.

Ces mesures ne seraient pas pertinentes car le même algorithme sera plus
rapide sur une machine plus puissante.

Au lieu de ça, on utilise des unités de temps abstraite proportionnelles au

nombre d’opérations effectuées.

Au besoin, on pourra alors adapter ces quantités en fonction de la machine sur
laquelle l’algorithme s’exécute.

9
Théorie de la complexité Calcul du temps d’exécution

Règles:
• Chaque instruction basique consomme une unité de temps (affectation d’une
variable, lecture, écriture, comparaison,…).

• Chaque itération d’une boucle rajoute le nombre d’unités de temps

consommés 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 d’opération effectuées par l’algorithme, on additionne

le tout.

10

5
Théorie de la complexité Calcul du temps d’exécution

Exemple: Temps d’exécution de la fonction factorielle

L’algorithme suivant calcule : n! = n*(n-1)*(n-2)*…*1 avec 0! =1

11
Théorie de la complexité Calcul du temps d’exécution

Exemple: Temps d’exécution de la fonction factorielle

L’algorithme suivant calcule : n! = n*(n-1)*(n-2)*…*1 avec 0! =1

Temps de calcul = 1+1+(2+2+1)*(n-1)+1= 5n-2 opérations

12

6
Théorie de la complexité Calcul du temps d’exécution

Problèmes
Unités de temps abstraites:
 Dépends des données.
 Dépend de la nature des données: on ne sait pas toujours combien de fois
exactement on va exécuter une boucle.
 De même lors d’un branchement conditionnel, le nombre de comparaisons
effectués n’est pas toujours le même.

Temps exacte:
 Dépend de la puissance de la machine.
 Dépend de la nature des données (variables): si on change les données, le temps
change.

Solution
Calcul de la complexité algorithmique
13
Complexité algorithmique Définition

La complexité d’un algorithme est la mesure du nombre d’opérations

fondamentales qu’il effectue sur un jeu de données. Elle est exprimée comme
une fonction de la taille du jeu de données.
Il existe trois types de complexité:
 Complexité au meilleur
C’est le plus petit nombre d’opérations qu’aura à exécuter l’algorithme sur
un jeu de données de taille n.

 Complexité au pire
C’est le plus grand nombre d’opérations qu’aura à exécuter l’algorithme
sur un jeu de données de taille n.

Complexité en moyenne
C’est la moyenne des complexités de l’algorithme sur des jeux de données
de taille n.
14

7
Complexité algorithmique Définition générale

De façon générale: La complexité d’un algorithme est une mesure de sa

performance asymptotique dans le pire des cas.

 asymptotique ?
 on s’intéresse à des données très grandes parce que les petites valeurs ne
sont pas assez informatives.

 Pire des cas ?

on s’intéresse à la performance de l’algorithme dans les situations où le
problème prend le plus de temps à résoudre parce qu’on veut être sûr que
l’algorithme ne prendra jamais plus de temps que ce qu’on a estimé.

Un algorithme est dit « optimal » si sa complexité est la complexité

minimale parmi les algorithmes de sa classe.

15
Complexité algorithmique 0-notation (Notation de Landau)

Quand on calcule la complexité d’un algorithme, on ne calcule

généralement pas sa complexité exacte, mais son ordre de grandeur.

C’est une approximation du temps de calcul de l’algorithme.

Pour ce faire, on a recours à la notation asymptotique O(.) ou

Notation de Landau.
16

8
Complexité algorithmique 0-notation (Notation de Landau)

Cette notation exprime la limite supérieure d’une fonction dans un

facteur constant.
 Soit n la taille des données à traiter, on dit qu’une fonction f(n) et en O(g(n)) si :

 f(n) et en O(g(n))s’il existe un seuil à partir duquel la fonction f(.) est toujours
dominée par g(.), à une constante multiplicative fixée près.

Utilité: Le temps d’exécution est borné

Signification: Pour toutes les grandes entrées (i.e., N >= n0), on est assuré que
l’algorithme ne prend pas plus de c*g(n) étapes.
Borne supérieure. 17
Complexité algorithmique 0-notation (Notation de Landau)

18

9
Complexité algorithmique 0-notation (Notation de Landau)

19
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 1: Prouver que f1(n) = 5n+37 est en O(n)

But: trouver une constante et un seuil à partir duquel

On remarque que 5n +37 <= 6n si n >= 37

On déduit donc que c=6 fonctionne à partir de n0 =37

Remarque: on ne demande pas d’optimiser (le plus petit c ou n0 qui fonctionne)

juste il faut donner des valeurs qui fonctionnent.

20

10
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 2: Prouver que est en

But: trouver une constante et un seuil à partir duquel

Chercher d’abord c, c=6 ne peut pas marcher, donc c=7

On doit donc trouver un seuil n0 à partir du quel :

c=7 et n0 =1

21
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 3: Calculer la complexité de

On remarque que

pour tout n>= 1

Donc est en

22

11
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 4: Calculer la complexité de l’initialisation d’un tableau:

On remarque qu’il y a n itérations; chaque itération nécessite un temps

d’exécution <= c où c est une constante (accès au tableau + une affectation)

 le temps est donc T(n)<= c n

Donc T(n) est en O(n)

23
Complexité algorithmique Règles de calcul

On calcule le temps d’exécution, mais on effectue les simplifications

suivantes:
On oublie les constantes multiplicatives (elles valent 1)
On annule les constantes additives
On ne retient que les termes dominants

Exemple (simplifications) soit :

• On remplace les constantes multiplicatives par 1:
• On annule les constantes additives :
• On garde le terme de plus haut degré:

• On a donc la complexité de

24

12
Complexité algorithmique Règles de calcul

De façon générale, les règles de la notation en O sont les suivantes:

Les termes constants :

O(c) = O(1)
Les constantes multiplicatives sont omises:
O(cT) = c O(T)=O(T)
 L’addition est réalisée en prenant le maximum:
O(T1)+O(T2)= O(T1+T2)=max(O(T1); O(T2))
La multiplication reste inchangée:
O(T1) O(T2)= O(T1*T2)

25
Complexité algorithmique Règles de calcul

Exemple:
Supposons que le temps d’exécution d’un algorithme est décrit par la fonction:
calculer O(T(n))?

Remarque:
Pour n=10, nous avons:

Le poids de devient encore plus grand pour n=100, soit 96,7%, on peut donc négliger les
quantités10n et 10. 26
Ceci explique les règles de notation O.

13
Complexité algorithmique Calcul de complexité

 Cas d’une instruction simple : Les instructions de base (lecture, écriture,

affectation …) prennent un temps constant, noté O(1).
Cas d’une suite d’instructions: le temps d’exécution d’une séquence est
déterminé par la règle de la somme.

Cas d’une branche conditionnelle: le temps d’exécution est déterminé aussi par
la règle de la somme.

27
Complexité algorithmique Calcul de complexité

 Cas d’une boucle: On multiplie la complexité du corps de la boucle par le

nombre d’itérations.
Exemple pour la boucle while (tant que), la complexité se calcule comme suit:

Pour calculer la complexité d’un algorithme:

•On calcule la complexité de chaque partie de l’algorithme.

•On combine ces complexités conformément aux règles déjà vues.
•On effectue sur le résultat les simplifications possibles déjà vues.

28

14
Complexité algorithmique Calcul de complexité

Exemple: calcul de la complexité de la fonction factorielle

Complexité de la fonction = O(1) +O(1)+O[(n -1)*(1+1+1)]+O(1)

= O(1)+O(1)+O(n)+O(1)
= O(n)
29
Complexité algorithmique Classes de complexité

On peut ranger les fonctions équivalentes dans la même classe.

Deux algorithmes de la même classe sont considérés de même complexité.

Les classes de complexité les plus fréquentes (par ordre croissant selon O(.) )

30

15
Complexité algorithmique Classes de complexité

31
Complexité algorithmique Classes de complexité

32

16
Application Algorithmes de recherche

Recherche séquentielle
Principe:
Le principe consiste à parcourir un tableau d'éléments dans l'ordre de
ses indices jusqu'à ce qu'un élément recherché soit trouvé ou bien
que la fin du tableau soit atteinte et l’élément recherché est alors
inexistant.
Exemple:
Soit T un tableau contenant les10 éléments suivants:

Pour x =-2, le programme affichera que ‘’-2 existe’’

Pour x =5, le programme affichera que ‘’5 n’existe pas’’ 33
Application Algorithmes de recherche
Recherche séquentielle
Algorithme:
Fonction Recherche_séquentielle (x:entier,T:tab, n:entier) : booleen
Var
i: entier
trouve: booleen
Début
i←0
trouve ← faux
Tant que ((i<n) et (non trouve)) faire
i ← i +1
si (T[i] = x) alors
trouve ← vrai
finsi
fintq
Retourner (trouve) 34
Fin

17
Application Algorithmes de recherche
Recherche séquentielle
Calcul de complexité:
Fonction Recherche_séquentielle (x:entier,T:tab, n:entier) : booleen
Var i: entier
trouve: booleen
Début
i←0
trouve ← faux
Tant que ((i<n) et (non trouve)) faire
i ← i +1
si (T[i] = x) alors
trouve ← vrai
finsi
fintq
Retourner (trouve)
Fin 35
Application Algorithmes de recherche

Recherche dichotomique
Principe:
On veut chercher un élément dans un tableau trié dans le sens croissant.
Le but de cette recherche est de diviser l’intervalle de recherche par 2 à chaque itération.
Pour cela, on procède de la façon suivante:

Soient premier et dernier les extrémités gauche et droite de l’intervalle dans lequel on cherche
la valeur x, on calcule m, l’indice de l’élément médian:
m=(premier + dernier ) div 2

36

18
Application Algorithmes de recherche

Recherche dichotomique
Principe:
Il y a 3 cas possibles:
• X<T[m], l’élément x s’il existe, il se trouve dans l’intervalle [premier... m-1]
• x > T[m], l’élément de valeur x, s’il existe, se trouve dans l’intervalle [m+1... Dernier]
•X=T[m], x est trouvé, la recherche est terminée
La recherche dichotomique consiste à itérer ce processus jusqu’à ce que l’on trouve x ou
que l‘intervalle de recherche soit vide.
Exemple:
Soit T un tableau contenant les10 éléments suivants:

Pour x =-2, le programme affichera que ‘’-2 existe’’

Pour x =5, le programme affichera que ‘’5 n’existe pas’’
37
Application Algorithmes de recherche
Recherche dichotomique
Algorithme: Procédure recherche_dichotomique ((x:entier,T:tab, n:entier)
Var
premier, dernier, m: entier
trouve : booléen
sinon
Début
trouve ← vrai
premier ←1
Finsi
dernier ← n
Finsi
trouve ← faux
Jusqu’à (trouve=vrai ou premier > dernier)
répéter
Si (trouve) alors
m ← (premier + dernier) div2
écrire(x, "existe et son indice est’’, m)
si(x<T[m]) alors
Sinon
dernier ←m-1
écrire(x, " introuvable ")
sinon
Finsi
si(x>T[m]) alors
fin
premier ← m+1 38

19
Application Algorithmes de recherche
Recherche dichotomique
Calcul de complexité:
Supposant que le tableau est de taille n une puissance de 2, .
Le pire des cas pour la recherche d’un élément est de continuer à diviser jusqu’à obtenir
un tableau de taille 1.
q est le nombre d’itérations nécessaires pour aboutir à un tableau de taille 1.

39
Application Algorithmes de recherche

Optimalité des Algorithmes de recherche

Algorithme de recherche Complexité

Recherche séquentielle O(n)

Recherche dichotomique O(log₂(n))

L’algorithme de recherche séquentielle est de complexité linéaire et celui

de recherche dichotomique est de complexité logarithmique.

L’algorithme de recherche dichotomique est plus optimal que

l’algorithme de recherche séquentielle.
40

20
Algorithmes de tri Tri à bulles
Tri à bulles
Principe:
Elle consiste à répéter le traitement suivant: parcourir les éléments du tableau de 1 à (n-1): si
l’élément i est supérieur à l’élément (i+1) alors, on les permute.
Le programme s’arrête lorsqu’aucune permutation n’est réalisable après le parcours complet
du tableau.
Exemple:

41
Algorithmes de tri Tri à bulles
Tri à bulles
Algorithme: Procédure Tri_à_bulles (T:tab, n:entier)
Var echange: booléen
i: entier
Début
répéter
echange ←faux
pour i de 1 à n-1 faire
si T[i] > T[i+1] alors
x ← T[i]
T[i] ← T[i+1]
T[i+1] ← x
echange ← vrai
finsi
fin pour
jusqu’à (echange = faux) 42
Fin

21
Algorithmes de tri Tri à bulles
Tri à bulles
Calcul de complexité : Procédure Tri_à_bulles (T:tab, n:entier)
Var echange: booléen
x,i: entier
Début
répéter
echange ←faux
pour i de 1 à n-1 faire
si (T[i] > T[i+1]) alors
x ← T[i]
T[i] ← T[i+1]
T[i+1] ← x
echange ← vrai
finsi
fin pour
jusqu’à (echange = faux) 43
Fin
Algorithmes de tri Tri par sélection
Tri par sélection
Principe:
Elle consiste à chercher l’indice du plus petit nombre du tableau (de 1 à n) et le permuter avec
l’élément 1 du tableau, chercher ensuite le plus petit nombre (de 2 à n) et le permuter avec
l’élément 2 du tableau, répéter ce traitement jusqu’à arriver à l’élément n-1.
Exemple:

44

22
Algorithmes de tri Tri par sélection
Tri par sélection
Algorithme: Procédure Tri_par_sélection (T:tab, n:entier)
Var i, j, x, indmin: entier
Début
pour i de 1 à n-1 faire
indmin ← i
pour j de i+1 à n faire
si T[j] < T[indmin] alors
indmin ← j
finsi
finpour
x ← T[i]
T[i] ←T[indmin]
T[indmin] ← x
fin pour
Fin 45
Algorithmes de tri Tri par sélection
Tri par sélection
Calcul de complexité: Procédure Tri_par_sélection (T:tab, n:entier)
Var i, j, x, indmin: entier
Début
pour i de 1 à n-1 faire
indmin ← i
pour j de i+1 à n faire
si T[j] < T[indmin] alors nbres d’itérations
indmin ← j (n-1)
finsi
finpour
x ← T[i]
T[i] ←T[indmin]
T[indmin] ← x
fin pour
Fin 46

23