République Algérienne Démocratique et Populaire

Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Université des Sciences et de la Technologie d’Oran – Mohamed Boudiaf

Faculté des Mathématiques et Informatique
Département Informatique

Polycopié de cours

Algorithmique et Complexité

Offre de formation : Tronc Commun Ingénieur

Domaine : Mathématiques et Informatique
Filière : Informatique
Année : Deuxième Année

Elaboré par :
Dr Mahmoud ZENNAKI
Maître de Conférences
[email protected]

Objectifs :
L’objectif est de permettre aux étudiants d’aborder, d’une part, le calcul de la complexité et la mise au
point d’algorithmes de base en informatique principalement les algorithmes de tri et d’autre part, la
manipulation de structures de données développées.
UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Table des Matières

CHAPITRE 1 : COMPLEXITE ALGORITHMIQUE ........................................................................................... 2
1. Rappels d’algorithmique........................................................................................................................................ 2
2. Qualités et caractéristiques d’un algorithme ........................................................................................................ 5
3. Définition de la complexité algorithmique ............................................................................................................ 5
4. Calcul de la complexité .......................................................................................................................................... 6
5. Exemples de calcul de complexité ......................................................................................................................... 12
6. Complexité spatiale .............................................................................................................................................. 13
7. Différentes formes de complexité ......................................................................................................................... 14
8. Complexité polynomiale et complexité exponentielle .......................................................................................... 14
9. Introduction à la théorie de la complexité ............................................................................................................ 15

CHAPITRE 2 : ALGORITHMES DE TRI .......................................................................................................... 17

1. Présentation .......................................................................................................................................................... 17
2. Tri par sélection ..................................................................................................................................................... 17
3. Tri par insertion ..................................................................................................................................................... 18
4. Tri à bulles.............................................................................................................................................................. 19
5. Tri fusion ................................................................................................................................................................ 20
6. Tri rapide................................................................................................................................................................ 21
7. Etude comparative de la complexité des algorithmes de tri étudiés .................................................................... 24

CHAPITRE 3 : LES ARBRES........................................................................................................................... 25

1. Introduction ........................................................................................................................................................... 25
2. Définitions.............................................................................................................................................................. 25
3. Arbres binaires ....................................................................................................................................................... 27
4. Arbres binaires particuliers.................................................................................................................................... 34

CHAPITRE 4 : LES GRAPHES ........................................................................................................................ 45

1. Introduction aux graphes ...................................................................................................................................... 45
2. Définitions.............................................................................................................................................................. 45
3. Représentation des graphes .................................................................................................................................. 46
4. Parcours des graphes............................................................................................................................................. 48
5. Problème des chemins optimaux .......................................................................................................................... 50

REFERENCES
• D. Beauquier, J. Berstel, P. Chretienne, et al., "Eléments d’algorithmique", volume 8, Masson, 1992.
• G. Brassard, P. Bratley, "Fundamentals of algorithmics", ISBN : 0-13-335068-1, Prentice Hall, Inc. Upper Saddle
River, NJ, USA, 1996.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction à l’algorithmique", ISBN : 2-10-003922-9,
2ème édition, Dunod, 2002.
• S. Kannan, M. Naor, S. Rudich, "Implicit Representation of Graphs", SIAM J. on Discrete Math., volume 5, pages
596-603, 1992.
• A. D. Mishra, D. Garg, "Selection of best sorting algorithm", International Journal of Intelligent Information
Processing, 2(2), 363-368, 2008.
• R. Sedgewick, P. Flajolet, "Introduction à l’analyse des algorithmes", ISBN : 2841809579, International
Thomson Publishing, 1998.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 1

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

CHAPITRE 1 : COMPLEXITE ALGORITHMIQUE

Plan
1. Rappels d’algorithmique
2. Qualités et caractéristiques d’un algorithme
3. Définition de la complexité algorithmique
4. Calcul de la complexité
5. Exemples de calcul de complexité
6. Complexité spatiale
7. Différentes formes de complexité
8. Complexité polynomiale et complexité exponentielle
9. Introduction à la théorie de la complexité

1. Rappels d’algorithmique
Intuitivement un algorithme est n’importe quelle procédure de calcul non ambiguë pouvant prendre
une ou plusieurs valeurs en entrée et produisant une ou plusieurs valeurs en sortie. C’est un outil pour
la résolution d’un problème bien spécifié dont l’énoncé indique la relation entre les entrées et les
sorties. L’algorithme peut aussi être défini plus simplement comme une suite finie d’instructions non
ambiguës pouvant être exécutées de façon automatique. Parmi les exemples classiques d’algorithmes,
on cite :
- Calcul du produit de deux matrices
- Calcul de la solution d’un système d’équations linéaire
- Calcul du plus court chemin (algorithme de Dijkstra)
- Tri d’une liste
- Recherche d’un mot dans un dictionnaire
- Recherche sur le Web

A titre d’exemple, on définit formellement l’algorithme de tri comme suit :

Entrée : Une suite de 𝑛 nombres {𝑎1 , 𝑎2 , … , 𝑎𝑛 }.

Sortie : Une permutation (ordonnancement) {𝑎1′ , 𝑎2′ , … , 𝑎𝑛′ } telle que 𝑎1′ ≤ 𝑎2′ ≤ ⋯ ≤ 𝑎𝑛′

Par exemple, la séquence {1,18,5,4,33} doit être transformée en {1,4,5,18,33} par l’algorithme de
tri. La séquence d’entrée est appelée instance du problème de tri.

• Description d’un algorithme. Il y a trois façons de décrire un algorithme :

a- Principe de fonctionnement
Exemple : recherche séquentielle d’un élément dans une liste non triée. Il s’agit de comparer
successivement tous les éléments de la liste avec l’élément recherché jusqu’à rencontrer celui-ci
ou bien arriver à la fin de la liste.

b- Pseudo code ou formalisme permettant d’exprimer :

- Les affectations : 
- Les instructions conditionnelles : Si … Alors … Sinon… Finsi
- Les boucles : Tant que condition …..Fin boucle

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 2

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Exemple : Recherche séquentielle dans un tableau

// Entrée : n données se trouvant dans un tableau T.

// La donnée recherchée notée clé. On utilise une variable booléenne
// notée trouvé et un entier i.

i  1;
trouvé  faux;
Tant que ((non trouvé) et (i <= n))
Si (T[i] = clé) Alors trouvé  vrai;
Sinon i  i+1;
Fin boucle
Renvoyer trouvé

c- Langage de programmation tel que Python, C, C++ ou Java.

Exemple :

Tri par insertion en Java : en Python :

public void insertionSort()
{ int i, j; def insertionSort():
for (j=1; j<nElems; j++) for j in range(1,nElems):
{ long temp = A[j]; temp = A[j]
i = j; i = j
while (i>0 && A[i-1]>=temp) while i>0 and A[i-1]>=temp:
{ A[i] = A[i-1]; A[i] = A[i-1]
--i; i -= 1
} A[i] = temp
A[i] = temp;
}
}

Remarques
• Les trois méthodes précédentes de description d’un algorithme sont de plus en plus précises et
donc de moins en moins ambiguës.
• Une bonne manière de programmer un algorithme consiste à enchaîner les trois méthodes c'est-
à-dire : avant de passer à la programmation il faut donner le principe puis l’exprimer en pseudo-
code.
• Il est généralement nécessaire de prouver l’algorithme en question c'est-à-dire s’assurer qu’il est
correct dans tous les cas. Il existe des techniques de preuve d’algorithmes mais dépassent le
niveau de ce cours.

• Implémentation d’un algorithme

L’implémentation d’un algorithme consiste à le traduire dans un langage de programmation et ceci dans
le but de l’exécuter sur ordinateur. L’implémentation nécessite le choix de la représentation des
données ou la structure de données.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 3

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

• Convergence des algorithmes

La convergence des algorithmes désigne la capacité d'un algorithme à atteindre un résultat correct
après un certain nombre d'itérations. Pour qu'un algorithme soit considéré comme convergent, il doit
tendre vers une solution précise et stable, quel que soit le point de départ des calculs. Ce concept est
crucial pour garantir que l'algorithme produit des résultats fiables.

Les critères de convergence varient selon les types d'algorithmes. Par exemple, dans les algorithmes de
tri, la convergence est atteinte lorsque les éléments sont correctement ordonnés. La vitesse de
convergence, c’est-à-dire le nombre d'itérations nécessaires pour atteindre le résultat final, est
également une considération importante. Elle peut être influencée par divers facteurs tels que la taille
des données et la complexité des opérations à effectuer.

La convergence des algorithmes est essentielle pour assurer qu'ils sont efficaces et qu'ils donnent des
résultats précis et constants après un nombre fini d'itérations.

En termes formels, un algorithme 𝒜 est dit convergent s'il existe une solution 𝒮 telle que pour toute
séquence d'itérations {𝑥𝑘 } générée par 𝒜, on a lim 𝑥𝑘 = 𝒮.
𝑘→∞

Techniques de Test de la Convergence

1. Analyse de la Stabilité : On étudie si les solutions obtenues après un grand nombre d'itérations sont
insensibles aux perturbations initiales. Cela implique d'évaluer si des variations mineures dans les
conditions initiales ou les paramètres de l'algorithme produisent des résultats similaires.
2. Critères de Tolérance : On définit un critère de tolérance 𝜖 tel que l'algorithme est considéré comme
convergent si la différence entre les résultats successifs est inférieure à 𝜖. Formellement, pour un
critère de convergence basé sur la norme euclidienne, on a ‖𝑥𝑘+1 − 𝑥𝑘 ‖ < 𝜖.
3. Critère de Cauchy : Un algorithme est convergent selon ce critère si, pour toute tolérance 𝜖 > 0, il
existe un rang N tel que ‖𝑥𝑛+𝑚 − 𝑥𝑛 ‖ < 𝜖 pour tout 𝑛 > 𝑁 et 𝑚 ≥ 0.
4. Test de Monotonie : Pour certains algorithmes, on peut tester la convergence en vérifiant si une
certaine séquence (par exemple, les valeurs de la fonction objectif) est monotone et bornée.
5. Tests Empiriques : Impliquent l'exécution de l'algorithme sur divers jeux de données et l'observation
de la stabilité et de la précision des résultats obtenus.

Amélioration de la Convergence
1. Ajustement des Paramètres : Les paramètres de l'algorithme, tels que les taux d'apprentissage ou les
coefficients de régularisation, peuvent être ajustés pour améliorer la convergence.
2. Techniques de Relaxation : Incluent des méthodes comme la sous-relaxation ou la sur-relaxation, qui
modifient les étapes de mise à jour pour accélérer la convergence.
3. Méthodes Multi-échelles : Utilisent différentes échelles de résolution pour améliorer l'efficacité et la
convergence de l'algorithme.

En résumé, la convergence des algorithmes est une propriété essentielle qui garantit leur fiabilité et leur
précision. Les techniques de test de convergence sont variées et peuvent inclure des analyses formelles
ainsi que des évaluations empiriques pour assurer que les algorithmes fonctionnent correctement dans
des conditions variées.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 4

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

2. Qualités et caractéristiques d’un algorithme

La résolution d’un problème peut être souvent effectuée par plusieurs algorithmes et pour chaque
algorithme, il existe plusieurs structures de données. L’algorithme ainsi que la structure de donnée
associée à son implémentation est caractérisé par :
• Sa simplicité : un algorithme simple est facile à comprendre, à implémenter et généralement à
prouver.
• Son temps d’exécution (complexité en temps ou complexité temporelle) : On préfère un
algorithme qui s’exécute en une seconde à un autre qui prend une heure sur une même
machine. De même, on rejette tout algorithme dont le temps d’exécution dépasse un siècle !!
• Son requis mémoire (complexité en mémoire ou complexité spatiale) : cette mémoire dépend à
la fois de l’algorithme et des structures des données choisies. Le requis mémoire ne doit jamais
dépasser une certaine limite qui dépend de la machine utilisée. Ceci a pour conséquence de
mettre une limite sur la taille des problèmes pouvant être résolus.

Structures de données
Les structures de données sont une principale caractéristique des algorithmes et peuvent avoir un
impact direct sur leurs complexités. Les structures de données spécifient la manière de représenter les
données d’un problème qui peut être résolu par ordinateur à l’aide d’un algorithme. Le choix d’une
structure de données doit prendre en considération la taille mémoire nécessaire à son implémentation
ainsi que sa facilité d’accès. Une structure de données peut être choisie indépendamment du langage de
programmation qui est utilisé pour l’écriture du programme manipulant ses données. Ce langage est
supposé offrir, d’une façon ou d’une autre, les mécanismes nécessaires pour définir et manipuler ces
structures de données. Les langages de programmation modernes permettent d’attribuer et manipuler
la mémoire disponible de la machine sous forme de variables isolées les unes des autres, sous forme de
tableaux, de pointeurs indiquant la localisation dans la mémoire de l’objet qui nous intéresse ou à l’aide
de structures prédéfinies plus complexes.
Dans le cas des variables isolées ou des tableaux statiques, la place en mémoire est attribuée par le
compilateur et ne peut faire l’objet de modification pendant l’exécution du programme. Cependant
dans le cas de tableaux dynamiques ou listes chaînées, l’allocation de la mémoire nécessaire est
effectuée pendant l’exécution et par conséquent, elle peut augmenter ou diminuer selon le besoin.

Les structures de données classiques peuvent être classées en trois catégories distinctes :
- Les structures linéaires ou séquentielles : appelées ainsi parce que les données sont
organisées sous forme d’une liste les unes derrières les autres. Ce sont des structures qui
peuvent être représentées par des listes linéaires telles que les tableaux ou les listes
chaînées ayant une seule dimension. Dans cette catégorie, il y a lieu de citer les piles,
pour lesquelles les données peuvent être ajoutées ou supprimées à partir d’une même
extrémité ; et les files où les données peuvent être ajoutées à partir d’une extrémité
tandis qu’elles sont supprimées de l’autre extrémité.
- Les structures arborescentes et en particulier les arbres binaires.
- Les structures relationnelles qui prennent en compte des relations existant ou non entre
les entités qu’elles décrivent.

3. Définition de la complexité algorithmique

L’étude de la complexité des algorithmes a pour objectif l’estimation de la qualité d’un algorithme
(assorti d’une structure de données). Cette mesure permet la comparaison de deux algorithmes sans
avoir à les programmer. La complexité peut être étudiée sous deux aspects : temporel (Temps
d’exécution) et spatial (Espace mémoire).

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 5

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

• Complexité temporelle
Si l’on prend en compte pour l’estimation de la complexité les ressources de la machine telles que la
fréquence d’horloge, le nombre de processeurs, le temps d’accès disque etc., on se rend compte
immédiatement de la complication voire l’impossibilité d’une telle tâche. Pour cela, on se contente
souvent d’estimer la relation entre la taille des données et le temps d’exécution, et ceci
indépendamment de l’architecture utilisée.
On définit la complexité d’un algorithme comme étant la mesure du nombre d’opérations élémentaires
qu’il effectue sur un jeu de données. La complexité est exprimée comme une fonction de la taille du jeu
de données.
L’analyse de la complexité consiste généralement à mesurer asymptotiquement le temps requis pour
l’exécution de l’algorithme sur une machine selon un modèle de calcul. Cette mesure permet juste
d’avoir une idée imprécise mais très utile sur le temps d’exécution de l’algorithme en question. Elle
nous permet, entre autres, d’estimer la taille des instances pouvant être traitées sur une machine
donnée en un temps raisonnable. Cependant, l’analyse de la complexité peut s’avérer très difficile
même pour des algorithmes relativement simples nécessitant parfois des outils mathématiques très
poussés.
D’une façon formelle, on peut aussi définir la complexité d’un algorithme 𝒜 comme étant tout ordre de
grandeur du nombre d’opérations élémentaires effectuées pendant le déroulement de 𝒜. Ces notions
seront définies au fur et à mesure de ce chapitre.

• Complexité spatiale
La complexité spatiale représente, quant à elle, l’utilisation mémoire que va nécessiter l’algorithme.
Celle-ci peut aussi dépendre comme pour la complexité temporelle de la taille de l’instance à traiter par
l’algorithme. La complexité spatiale sera brièvement décrite dans la section 6.

On abordera essentiellement dans ce qui suit la complexité temporelle ou en temps.

4. Calcul de la complexité

4.1. Modèle d’analyse de la complexité

Il s’agit d’un modèle simplifié qui tient compte des ressources technologiques ainsi que leurs coûts
associés. On prendra comme référence un modèle de machine à accès aléatoire et à processeur unique
où les opérations sont exécutées l’une après l’autre sans opérations simultanées. Suivant le type
d’instruction, la complexité est évaluée comme suit :

Séquence
𝓐 :  𝓙;
 𝓚;  𝑇𝒜 (𝑁) = 𝑇𝒥 (𝑁) + 𝑇𝒦 (𝑁)

Alternative
𝓐 : Si 𝓒 Alors 𝓙 Sinon 𝓚  𝑇𝒜 (𝑁) = 𝑇𝒞 (𝑁) + 𝑚𝑎𝑥{𝑇𝒥 (𝑁) , 𝑇𝒦 (𝑁)} : Pire cas
 𝑇𝒜 (𝑁) = 𝑇𝒞 (𝑁) + 𝑚𝑖𝑛{𝑇𝒥 (𝑁) , 𝑇𝒦 (𝑁)} : Meilleur cas
Boucles
𝓐 : nb  𝓑  𝑇𝒜 (𝑁) = 𝑛𝑏 × 𝑇ℬ (𝑁)

Récursivité
Etablir la formule de récurrence et en déduire la complexité (voir section 4.5)

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 6

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

4.2. Opérations élémentaires

On appelle opérations élémentaires les opérations suivantes :
• un accès mémoire pour lire ou écrire la valeur d’une variable ou d’une case d’un tableau ;
• une opération arithmétique entre entiers ou réels telle que l’addition, soustraction,
multiplication, division ou calcul du reste d’une division entière ;
• une comparaison entre deux entiers ou réels.

Exemple :
L’instruction « c  a + b ; » nécessite les quatre opérations élémentaires suivantes :
1- un accès mémoire pour la lecture de la valeur de a,
2- un accès mémoire pour la lecture de la valeur de b,
3- une addition de a et b,
4- un accès mémoire pour l’écriture de la nouvelle valeur de c.

Remarques :
• Il est recommandé de repérer les opérations fondamentales d’un algorithme. Leur nombre
intervient principalement dans l’étude de la complexité. Voici quelques exemples :
Algorithme Opérations fondamentales
Recherche d’un élément Comparaisons
Tri Comparaisons et déplacements (permutations)
Multiplication de matrices Additions et multiplications
• Faire attention aux boucles et à la récursivité ; la complexité finale d’un algorithme provient
généralement de ces deux types d’instructions.

4.3. Exemple d’illustration : Le Tri par insertion

Considérons l’algorithme de tri par insertion permettant de trier un tableau A de taille N. Considérons le
modèle de complexité qui associe à chaque ligne i (du code) son coût (ou temps d’exécution) C i.
L’analyse peut se faire donc comme suit :

void triInsertion (int *A, int N) // coût Nombre de fois

{ // ==========================
int j, temp, i;
for (j=2 ; j<=N ; j++) // coût C1 ........ N
{
temp = A[j]; // coût C2 ........ N-1
i = j-1; // coût C3 ........ N-1
while (i>0 && A[i]>temp) // coût C4 ........ 2+3+...+N
{
A[i+1]=A[i]; // coût C5 ........ 1+2+...N-1
i=i-1; // coût C6 ........ 1+2+...N-1
}
A[i+1]=temp; // coût C7 ........ N-1
}
}

Pour finaliser le calcul de la complexité du tri par insertion, des notions mathématiques sont nécessaires
notamment les suites numériques et la notion d’ordre de grandeur.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 7

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

4.4. Rappels mathématiques

Suites numériques

• Suite arithmétique :
𝑛
𝑛(𝑛 + 1)
∑𝑖 = 1 + 2 + ⋯+ 𝑛 =
2
𝑖=1
• Suite géométrique :
𝑛
𝑥 𝑛+1 − 1
∑ 𝑥𝑖 = 1 + 𝑥 + 𝑥2 + ⋯ + 𝑥𝑛 =
𝑥−1
𝑖=0
• Suite harmonique :
𝑛
1 1 1 1
∑ = 1 + + + ⋯ + = 𝐿𝑛(𝑛)
𝑖 2 3 𝑛
𝑖=1

La complexité de l’algorithme de tri par insertion est donc :

C 4 + C5 + C6 C 4 − C5 − C6
T(N) = ( ) N 2 + (C1 + C 2 + C 3 + + C 7 ) N − (C 2 + C 3 + C 4 + C 7 )
2 2
Et puisqu’on s’intéresse aux valeurs de N très grandes (comportement asymptotique de la complexité),
nous pouvons noter la complexité en utilisant les ordres de grandeurs (voir rappel ci-après) comme suit :

T(N) = O(N2)
Note :
T(N) représente la complexité dans le pire des cas car on n’a pas tenu compte dans notre calcul de la
valeur de l’expression logique de la condition (A[i] > temp) qui détermine le nombre d’exécutions de la
boucle interne. L’algorithme de tri par insertion peut donc prendre moins de temps pour des tableaux
ayant une structure particulière et par conséquent, la complexité est une variable aléatoire. C’est
pourquoi on parle de complexité en moyenne d’un algorithme qu’on peut calculer comme étant
l’espérance de cette variable aléatoire.

Ordres de grandeurs

- Notation  (thêta) : soit g une fonction positive d’une variable entière n. (g(n)) désigne l’ensemble
des fonctions positives de la variable n, pour lesquelles il existe deux constantes c 1, c2 et un entier n0,
satisfaisant la relation :
0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)  n ≥ n0

Par abus de notation on écrit f(n) = (g(n)) pour exprimer que f  (g(n)) (malgré que (g(n)) est un
ensemble et f est un élément de celui-ci).

Exemple :
Soit g(n) = n2 et f(n) = 50n2+10n.
Il s’agit de trouver c1, c2 et n0 tels que : c1n2 ≤ 50n2+10n  c1 ≤ 50,
50n2+10n ≤ c2n2  c2 ≥ 50.

donc on a bien f(n) = (g(n)) = (n2)

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 8

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

La figure suivante montre les graphes de trois fonctions f1, f2 et f3. On peut facilement vérifier que
f2 = (f1(N)) et aussi f3 = (f1(N)).

On peut interpréter la relation f(n)=(g(n)) comme suit : pour n assez grand, la fonction f est bornée à
la fois supérieurement et inférieurement par la fonction g, c'est-à-dire que les fonctions f et g sont
égales, à une constante près.
8
x 10
10

6 f1=N3

f2=N3-100N2
2

f3=N3-1000N2
0

-2
0 100 200 300 400 500 600 700 800 900 1000
N

- Notation O (grand o) : Lorsque la fonction f est bornée uniquement supérieurement par la fonction g
on utilise la notation O. O(g(n)) désigne donc l’ensemble des fonctions positives de la variable n, pour
lesquelles il existe une constante c et un entier n0, satisfaisant la relation : 0 ≤ f(n) ≤ c g(n)  n ≥ n0

La relation f(n) = O(g(n)) indique que la fonction f est bornée supérieurement par la fonction g pour des
valeurs suffisamment grandes de l’argument n. Donc f(n) = (g(n)) implique que f(n) = O(g(n)) (par abus
de notation). Formellement, on peut écrire (g(n))  O(g(n)).

Exemple : 100n2 + 10n = O(n2) mais on peut aussi écrire 100n = O(n2) ! Car ceci est équivalent à dire que
100n est asymptotiquement bornée supérieurement par n2.

- Notation Ω (grand oméga): Ω(g(n)) désigne l’ensemble des fonctions positives de la variable n, pour
lesquelles il existe une constante c et un entier n0, satisfaisant la relation : 0 ≤ cg(n) ≤ f(n)  n ≥ n0

La relation f(n) = Ω(g(n)) indique que la fonction f est bornée inférieurement par la fonction g pour des
valeurs suffisamment grandes de l’argument n. Par conséquent, f(n) = (g(n)) implique que f(n) =
Ω(g(n)) (par abus de notation). Formellement, on peut écrire : (g(n))  Ω(g(n)). Le théorème suivant
découle immédiatement des définitions données :

Théorème : f(n) = (g(n)) si et seulement si : f(n) = Ω(g(n)) et f(n) = O(g(n))

Les trois notations précédentes peuvent être récapitulées par le schéma suivant :

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 9

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Ө
Borne Supérieure et Inférieure
Large

Ω O
Borne Inférieure Borne Supérieure

Quelques propriétés de la notation O

1. Les facteurs constants peuvent être ignorés (Ex : 3x² = O(x²))

2. Une grande puissance de n croît plus vite qu’une puissance inférieure (nr = O(ns) si 0≤r≤ s)

3. Le taux de croissance d’une somme de termes est le taux de croissance du terme le plus rapide
en croissance. (Ex : an3 + bn2 = O(n3))

4. Les fonctions exponentielles sont plus rapides en croissance que les puissances (polynômes)

5. Tous les logarithmes ont un même taux de croissance.

IMPORTANT
La complexité d’un algorithme peut être dans certains cas facilement trouvée si on arrive à analyser et
comprendre l’algorithme et repérer ses opérations fondamentales. Ainsi pour le tri par insertion, on
peut s’intéresser aux comparaisons comme suit :

Le nombre de comparaisons exécutées à l’itération 𝑖 est au plus 𝑖. Le nombre total de comparaisons est :
𝑁
𝑁(𝑁 + 1)
∑𝑖 = − 1 = 𝑂(𝑁 2 )
2
𝑖=2

4.5. Complexité et récursivité

Pour calculer la complexité d’un algorithme récursif, il faut déterminer la formule de récurrence
correspondante à la complexité puis développer cette formule. Illustrons ceci avec le calcul récursif du
factoriel d’un nombre entier 𝑛 :

int fact(int n) {
if (n==0) return 1;
else return n * fact(n-1);
}

Dans ce cas, le paramètre de complexité (taille du problème) est la valeur de 𝑛. Aussi il n’y a qu’un seul
cas d’exécution (pas de meilleur ou pire cas). On remarque donc que :

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 10

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

• Si 𝑛 ≠ 0, le calcul de la factorielle de 𝑛 coûte un accès mémoire, une comparaison d’entiers, et

deux opérations arithmétiques (soustraction pour calculer 𝑛 − 1 et une multiplication d’entiers)
en plus du calcul de la factorielle de 𝑛 − 1, soit le calcul de la factorielle de 𝑛 − 1 et 4 opérations
élémentaires.

• Si 𝑛 = 0, le calcul de la factorielle coûte un accès mémoire et une comparaison d’entiers (deux

opérations élémentaires).

On pose donc la formule ou l’équation de récurrence suivante ; appelons 𝑇(𝑛) la complexité de la

fonction fact :
2 𝑠𝑖 𝑛 = 0
𝑇(𝑛) = {
𝑇(𝑛 − 1) + 4 𝑠𝑖 𝑛 ≠ 0

Le développement de cette formule peut se fait comme suit :

𝑇(𝑛) = 𝑇(𝑛 − 1) + 4 = 𝑇(𝑛 − 2) + 8 = ⋯ = 𝑇(𝑛 − 𝑝) + 4𝑝

Puis on pose 𝑛 − 𝑝 = 0 et on obtient : 𝑇(𝑛) = 4𝑛 + 2 = 𝑂(𝑛)

Il existe plusieurs techniques pour la résolution des équations de récurrence (fonction génératrice,
fractions rationnelles, transformée en Z, …). Le théorème suivant est la solution des principales
équations de récurrence.

Théorème :
Soit 𝑇(𝑛) une fonction définie par l’équation de récurrence suivante, où 𝑏 ≥ 2, 𝑘 ≥ 0, 𝑎 > 0, 𝑐 > 0 :

𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑐𝑛𝑘

Si 𝑎 > 𝑏 𝑘 alors 𝑇(𝑛) = (𝑛𝑙𝑜𝑔𝑏 (𝑎))

Si 𝑎 = 𝑏 𝑘 alors 𝑇(𝑛) = (𝑛𝑘 𝑙𝑜𝑔(𝑛))
Si 𝑎 < 𝑏 𝑘 alors 𝑇(𝑛) = (𝑛𝑘 )

Le tableau suivant résume la solution des principales équations de récurrence rencontrées

fréquemment dans la complexité des algorithmes :

Equation de récurrence Solution

𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑏 𝑇(𝑛) = 𝑂(𝑛)

𝑇(𝑛) = 𝑎𝑇(𝑛 − 1) + 𝑏 , 𝑎 ≠ 1 𝑇(𝑛) = 𝑂(𝑎𝑛 )
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑎𝑛 + 𝑏 𝑇(𝑛) = 𝑂(𝑛2 )
𝑇(𝑛) = 𝑇(𝑛/2) + 𝑏 𝑇(𝑛) = 𝑂(𝑙𝑜𝑔𝑛)
𝑇(𝑛) = 𝑎𝑇(𝑛/2) + 𝑏 , 𝑎 ≠ 1 𝑇(𝑛) = 𝑂(𝑎log(𝑛) )
𝑇(𝑛) = 𝑇(𝑛/2) + 𝑎𝑛 + 𝑏 𝑇(𝑛) = 𝑂(𝑛)
𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑎𝑛 + 𝑏 𝑇(𝑛) = 𝑂(𝑛𝑙𝑜𝑔𝑛)

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 11

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

5. Exemples de calcul de complexité

Complexité linéaire O(N)

• Recherche séquentielle : si l’élément est introuvable, tous les N éléments sont parcourus, ce qui
donne une complexité pire cas de O(N).

• Calcul de la factorielle (itérative et récursive)

Complexité constante O(1)

• Boucle à nombre d’itérations constant : for (i = 1 ; i <= 100 ; i++)

• Hachage sans collisions

Complexité logarithmique O(logN)

• Recherche dichotomique (ou binaire)

ideb = 1;
ifin = n;
trouve = false;
while (ideb<=ifin && !trouve) {
imil = (ideb+ifin)/2;
if (A[imil]==e) trouve = true;
else if (A[imil]>e) ifin = imil-1; else ideb = imil+1;
}

Le nombre d’itérations dans le pire des cas est égal à 𝑙𝑜𝑔2 (𝑛) ; en effet l’espace de recherche
évolue comme suit : 𝑛, 𝑛/2, 𝑛/4, …, 𝑛/2𝑝 , jusqu’à ce qu’il ne reste qu’une seule case. Si on pose
𝑛/2𝑝 = 1, on déduit le nombre d’itérations 𝑝 égal à 𝑙𝑜𝑔2 (𝑛).

Complexité quadratique O(N²)

• 2 Boucles linéaires imbriquées

• Tri par insertion (pire cas)

Complexité exponentielle O(2N)

• Tour de Hanoi

Procedure Hanoï(N, A, C, B)
{ si N0 alors
Hanoï(N-1,A,B,C);
Déplacer le disque de A vers C
Hanoï(N-1,B,C,A);
finsi
}

Il suffit de développer la formule de récurrence suivante : 𝑇(𝑁) = 2𝑇(𝑁 − 1) + 𝑂(1) et 𝑇(0) = 𝑂(1)

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 12

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

6. Complexité spatiale
Jusqu’à présent, nous avons abordé la complexité algorithmique seulement à travers le prisme du temps
de calcul. Pour qu’un calcul soit utilisable, il est en effet nécessaire qu’il s’exécute rapidement. Mais il
existe une autre ressource critique : la mémoire. On s’intéresse donc dans cette section à la complexité
spatiale, autrement dit, l’utilisation mémoire que va nécessiter l’algorithme. Celle-ci peut aussi
dépendre comme pour la complexité temporelle de la taille de l’instance à traiter par l’algorithme.

Prenons comme exemple, un algorithme effectuant 𝑛4 opérations qui peut éventuellement encore être
considéré comme raisonnablement efficace en termes de temps d’exécution puisque le temps
nécessaire à une machine actuelle effectuant 1011 opérations par seconde pour exécuter l’algorithme
sur une entrée de taille 10 000 est d’environ un jour. Mais si à chaque étape il utilise une nouvelle case
mémoire alors il lui faudra 1015 cases pour réaliser son calcul. C’est rédhibitoire actuellement, tout au
moins si l’on se restreint à la mémoire vive afin d’éviter les lents accès disque. Toutefois, la mémoire
n'est plus de nos jours un paramètre réellement limitant, le prix de la RAM ayant énormément baissé en
une vingtaine d'années (de plus la mémoire virtuelle est une autre réponse à ce problème).

Il y a une règle (non officielle) qui dit que pour gagner du temps de calcul, on doit utiliser davantage
d’espace mémoire. Ceci est illustré par l’exemple classique de permutation de deux variables entières 𝑥
et 𝑦 :

// échange en utilisant une variable auxiliaire z

z = x;
x = y;
y = z;

// échange sans variable auxiliaire

x = y - x;
y = y - x;
x = y + x;

La première méthode utilise une variable supplémentaire et réalise 3 affectations (complexité spatiale =
1, complexité en temps = 3) alors que la deuxième méthode n’utilise que les deux variables 𝑥 et 𝑦 à
permuter, mais réalise 3 affectations et 3 opérations (complexité spatiale = 0, complexité en temps = 6).

La mesure de la complexité spatiale se fait généralement en estimant la quantité mémoire utilisée par le
programme comme illustré dans l’exemple très simple d’une fonction permettant de déterminer l’indice
du premier élément négatif dans un tableau de 𝑛 entiers.

int firstNegative(vector <int> T) O(n)

{ int n = T.size(); O(1)
int i = 0; O(1)
while (i < n)
{ if (T[i]<0) return i;
i++;
}
return -1;
}

La complexité spatiale de la fonction firstNegative est donc O(1), car le tableau T existe déjà en entrée.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 13

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

7. Différentes formes de complexité

Il est évident que la complexité d’un algorithme peut ne pas être la même pour deux jeux de données
différents. Ceci peut avoir des conséquences sur le choix du meilleur algorithme pour un problème
donné. En pratique, on s’intéresse aux formes suivantes de la complexité :

7.1. Complexité dans le pire des cas (Worst case)

Il s’agit de considérer le plus grand nombre d’opérations élémentaires effectuées sur l’ensemble de
toutes les instances du problème ; on cherche une borne supérieure qui est atteinte même pour des
instances ayant une très faible, voire zéro, probabilité.
Cette forme de complexité est plus simple à calculer mais peut conduire à un choix erroné d’un
algorithme. En effet le pire cas peut être un cas très rare !

7.2. Complexité dans le meilleur des cas (Best case)

Il s’agit, cette fois-ci, de considérer le plus petit nombre d’opérations élémentaires ; c'est-à-dire on
cherche un minorant de la complexité au lieu d’un majorant.
Cette forme de complexité peut être considérée comme complément de la complexité dans le pire des
cas mais n’offre aucune garantie à l’utilisateur.

7.3. Complexité en moyenne (Average case)

C’est la vraie complexité d’un algorithme. Il s’agit de calculer la moyenne (espérance mathématique) des
nombres d’opérations élémentaires effectuées sur la totalité des instances. Ce calcul est généralement
très difficile et souvent même délicat à mettre en œuvre car il faut connaître la probabilité de chacun
des jeux de données pour pouvoir calculer la complexité en moyenne.
Cette forme d’analyse a fait l’objet de nombreux travaux de recherche et permet d’expliquer, d’une part
le comportement de certains algorithmes en pratique ; et d’autre part, le choix d’algorithmes pour des
problèmes ayant des tailles considérables tels que les problèmes d’apprentissage en intelligence
artificielle.

8. Complexité polynomiale et complexité exponentielle

Un algorithme est considéré pratique, relativement à une classe de problèmes, s’il est capable de
résoudre n’importe quelle instance dans le pire des cas ou en moyenne en temps polynomial, c'est-à-
dire, sa complexité est 𝑂(𝑁 𝑘 ), où 𝑘 est un entier quelconque.

En réalité une complexité est dite polynomiale si elle peut être bornée par un polynôme, on retrouve
donc :
𝑂(1) (Complexité constante)
𝑂(𝑙𝑜𝑔(𝑁)) (Complexité logarithmique)
𝑂(√𝑁) (Complexité racinaire)
𝑂(𝑁) (Complexité linéaire)
𝑂(𝑁𝑙𝑜𝑔𝑁) (Complexité quasi-linéaire)
𝑂(𝑁²) (Complexité quadratique)
𝑂(𝑁 3 ) (Complexité cubique)
…
D’autre part une complexité est dite exponentielle (𝑂(𝑘 𝑁 ) en général) si elle ne peut pas être bornée
par un polynôme, on retrouve par exemple :
O(𝑁𝑙𝑜𝑔𝑁 ) (Complexité sous exponentielle)
𝑁 𝑁
𝑂(2 ), 𝑂(3 ) (Complexité exponentielle)
𝑂(𝑁!) (Complexité factorielle)
2𝑁
𝑂(2 ) (Complexité double exponentielle)

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 14

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Un bon algorithme est polynomial. Ce critère d’efficacité est confirmé par la pratique :

- Une exponentielle dépasse tout polynôme pour 𝑛 assez grand. Par exemple, 1.1𝑛 croit d’abord
lentement, mais finit par dépasser 𝑛100 . En plus il est rare de trouver des complexités
polynomiales d’ordre supérieur à 𝑛5 en pratique.

- L’ensemble des polynômes a d’intéressantes propriétés de fermeture. L’addition, la

multiplication et la composition de polynômes donnent des polynômes. On peut ainsi constituer
de grands algorithmes polynomiaux à partir de plus petits.

L’esprit humain a du mal à appréhender ce qu’est une croissance exponentielle. Le tableau suivant
illustre ces croissances, par rapport à des croissances polynomiales. Les temps de calculs supposent 0.1
nanoseconde par instruction (équivalent à un processeur cadencé à plus de 6 GHZ). Les cases non
remplies ont des durées supérieures à 1000 milliards d’années (supérieur à l’âge estimé de l’univers !).

Taille
20 50 100 200 500 1000
Complexité
107 𝑛𝑙𝑜𝑔2 (𝑛) 0.09 s 0.3 s 0.7 s 1.5 s 4.5 s 10 s
106 𝑛² 0.04 s 0.25 s 1s 4s 25 s 100 s
105 𝑛3 0.08 s 1.25 s 10 s 80 s 21 min 2.7 h
𝑛log 𝑛 0.04 ms 0.4 s 32 min 1.2 ans 5. 107 ans --
2𝑛 100 s 31 h -- -- -- --
𝑛! 7.7 ans -- -- -- -- --

Ces calculs montrent que la croissance exponentielle rend rapidement prohibitive l’utilisation d’un
algorithme exponentiel si on doit traiter des données de grande taille. Elle laisse aussi deviner que des
progrès technologiques qui permettraient de rendre plus rapides nos ordinateurs actuels ne
changeraient pas qualitativement la conclusion de la phrase précédente à moins que les ordinateurs
quantiques voient dans le futur le jour !

9. Introduction à la théorie de la complexité

La théorie de la complexité (TC) a été développée vers 1970 pour répondre à une question
fondamentale : Existe-t-il réellement une classe de problèmes pour lesquels on ne trouvera jamais
d’algorithmes polynomiaux, ou est-ce que les problèmes difficiles ont en fait de tels algorithmes, mais
non encore découverts ? L’un des principaux résultats de la TC est que tous les problèmes difficiles sont
liés : la découverte d’un algorithme polynomial pour un seul d’entre eux permettrait de déduire des
algorithmes polynomiaux pour tous les autres.

Classes P et NP
L’ensemble des problèmes qui admettent des algorithmes polynomiaux forme la classe P.

La classe NP (Non-déterministe Polynomial) est celle des problèmes dont une proposition de solution
« Oui » est vérifiable en un temps polynomial. Prenons par exemple une variante du problème du sac à
dos :
Etant donné k, existe-t-il x tel que a.x  b et c.x  k ?

Considérons un n-vecteur x solution du problème. L’algorithme de vérification consiste à vérifier les 2

inégalités a.x  b et c.x  k. Cette vérification est possible en O(𝑛) donc en un temps polynomial. Le

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 15

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

problème est donc dans NP mais n’est pas dans P1 car aucun algorithme polynomial n’a été trouvé pour
le résoudre.

Problèmes NP-complets
Il s’agit des problèmes les plus difficiles de NP. La notion de problème NP-complet est basée sur celle de
la transformation polynomiale d’un problème. Par exemple, le problème de la recherche d’un stable
maximal d’un graphe G revient à trouver une clique maximale dans le graphe complémentaire GC.
Supposons qu’on ait un algorithme efficace pour trouver une clique maximale et qu’on veuille savoir si G
contient un stable maximal. Ce problème peut être résolu par transformation polynomiale en un
problème de clique maximale dans GC. La transformation consiste à construire GC qui est possible en
O(N²).

Les problèmes NP-complets représentent le noyau dur de NP, car si on trouvait un algorithme
polynomial pour un seul problème NP-complet X, on pourrait en déduire un autre pour tout autre
problème difficile Y de NP. En effet, ce dernier algorithme consisterait à transformer polynomialement
les données pour Y en données pour X, puis à exécuter l’algorithme pour X.

Depuis que le logicien Cook a montré en 1970 que le problème de satisfiabilité (SAT) est NP-complet,
des chercheurs ont montré que la plupart des problèmes difficiles (sans algorithme polynomial) sont en
fait NP-complets.

Exemples de problèmes NP-complets : Satisfiabilité, sac à dos, voyageur de commerce, stable max,
clique max, couverture d’ensembles, …

La conjecture P  NP
La question cruciale de la TC est de savoir si les problèmes NP-complets peuvent être résolus
polynomialement, auquel cas P = NP, ou bien si on ne leur trouvera jamais d’algorithmes polynomiaux,
auquel cas P  NP. Cette question n’est pas définitivement tranchée. La découverte d’un algorithme
polynomial pour un seul problème NP-complet permettrait de les résoudre facilement tous. Comme des
centaines de problèmes NP-complets résistent en bloc à l’assaut des chercheurs, on conjecture
aujourd’hui que P  NP.

Le schéma suivant résume bien cette conjecture. Les problèmes à statut indéterminé sont des
problèmes qui n’ont pas d’algorithme polynomial connu, mais personne n’a réussi à montrer qu’ils sont
NP-complets (problème de l’isomorphisme de 2 graphes par exemple).

NP-Complet

Problèmes à statut
indéterminé NP

1
Tout problème de la classe P est bien évidemment dans NP, puisque l’algorithme de vérification de la solution possède au plus la même
complexité que l’algorithme qui a permis d’obtenir cette solution.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 16

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

CHAPITRE 2 : ALGORITHMES DE TRI

Plan
1. Présentation
2. Tri par sélection
3. Tri par insertion
4. Tri à bulles
5. Tri fusion
6. Tri rapide
7. Etude comparative de la complexité des algorithmes de tri étudiés

1. Présentation
Le tri est sans doute un des problèmes les plus fondamentaux de l’algorithmique. Après le tri beaucoup
d’autres problèmes deviennent facile à résoudre tels que l’unicité ou la recherche.

Le tri consiste à réarranger une liste de 𝑛 objets de telle manière :

𝑋1 ≤ 𝑋2 ≤ ⋯ ≤ 𝑋𝑛 : Tri par ordre croissant

𝑋1 ≥ 𝑋2 ≥ ⋯ ≥ 𝑋𝑛 : Tri par ordre décroissant

Il existe plusieurs méthodes de tri, nous citons :

- Tri par sélection
- Tri par insertion
- Tri à bulles
- Tri par fusion
- Tri rapide
- Tri shell
- …

Dans ce qui suit, on décrit les principaux algorithmes de tri puis on analysera leur complexité
temporelle.

2. Tri par sélection (Selection Sort)

2.1. Principe
Itérativement, le tri par sélection consiste à chercher le plus petit élément puis le mettre au début.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 17

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Exemple

Liste initiale 42 17 13 28 14

1ère itération 13 17 42 28 14

2ème itération 13 14 42 28 17

3ème itération 13 14 17 28 42

4ème itération 13 14 17 28 42

2.2. Implémentation
void selectionSort(int *A, int n)
{
for (int i=0 ; i<n-1 ; i++)
{ int imin=i;
for (int j=i+1 ; j<n ; j++)
if (A[j]<A[imin]) imin=j;
swap(A,i,imin);
}
}

2.3. Complexité
Le pire et le meilleur cas sont pareils, puisque pour trouver le plus petit élément, (𝑛 − 1) itérations sont
nécessaires, pour le 2ème plus petit élément, (𝑛 − 2) itérations sont effectuées… jusqu’à l’avant dernier
plus petit élément qui nécessite 1 itération. Le nombre total d’itérations est donc :
𝑛−1
𝑛(𝑛 − 1)
∑𝑖 = = 𝑂(𝑛2 )
2
𝑖=1

Il reste néanmoins que le nombre de permutations est de l’ordre de 𝑂(𝑛)

3. Tri par insertion (Insertion Sort)

3.1. Principe
Itérativement, on insère le prochain élément dans la partie qui a été déjà triée précédemment. La partie
de départ qui est triée est le premier élément.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 18

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Exemple

Liste initiale 42 17 13 28 14

1ère itération 17 42 13 28 14

2ème itération 13 17 42 28 14

3ème itération 13 17 28 42 14

4ème itération 13 14 17 28 42

3.2. Implémentation
void insertionSort(int *A, int n)
{
for (int i=1 ; i<n ; i++)
{ int temp=A[i], j=i;
while (j>0 && A[j-1]>temp)
{ A[j] = A[j-1]; j--;}
A[j] = temp;
}
}

3.3. Complexité
Comme nous n’avons pas nécessairement à scanner toute la partie déjà triée, le pire et le meilleur cas
sont différents.

Meilleur cas : si le tableau est déjà trié, chaque élément est toujours inséré à la fin de la partie triée ;
nous n’avons à déplacer aucun élément. Comme nous avons à insérer (𝑛 − 1) éléments,
chacun générant seulement une comparaison, la complexité est 𝑂(𝑛).

Pire cas : si le tableau est inversement trié, chaque élément est inséré au début de la partie triée.
Dans ce cas, tous les éléments de la partie triée doivent être déplacés à chaque itération.
La ième itération génère (𝑖 − 1) comparaisons et échanges de valeurs :
𝑛
𝑛(𝑛 − 1)
∑(𝑖 − 1) = = 𝑂(𝑛2 )
2
𝑖=1

Remarquons pour ce tri que le nombre de permutations dans le pire des cas est de l’ordre de 𝑂(𝑛2 )

4. Tri à bulles (Bubble Sort)

4.1. Principe
Parcourir le tableau en comparant deux à deux les éléments successifs et permuter s’ils ne sont pas dans
l’ordre.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 19

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Exemple
Liste initiale 42 17 13 28 14

1ère itération 13 42 17 14 28

2ème itération 13 14 42 17 28

3ème itération 13 14 17 42 28

4ème itération 13 14 17 28 42

4.2. Implémentation
void bubbleSort(int *A, int n) {
for (int i=0 ; i<n-1 ; i++)
for (int j=n-1 ; j>i ; j--) if (A[j]<A[j-1]) swap(A,j,j-1);
}

4.3. Complexité
Globalement, c’est la même complexité que le tri par sélection. Le meilleur et le pire cas sont pareils
avec une complexité de 𝑂(𝑛²). Sauf que par rapport au tri par sélection, dans ce tri même le nombre de
permutations est de l’ordre de 𝑂(𝑛²). Néanmoins, si la liste est déjà triée, le tri à bulles peut être
amélioré pour détecter cela après une seule passe grâce à l'utilisation d'un indicateur (flag) qui détecte
si des échanges ont été effectués. Si aucun échange n'a eu lieu, cela signifie que la liste est triée et
l'algorithme peut s'arrêter immédiatement. La complexité meilleur cas devient alors 𝑂(𝑛).

5. Tri fusion (Merge Sort)

5.1. Principe
Cet algorithme divise en deux parties égales le tableau. Après que ces deux parties soient triées (de
manière généralement récursive), elles sont fusionnées pour l’ensemble des données.

Exemple 42 17 13 28 14

42 17 13 28 14

42 17 13 28 14

28 14

14 28

17 42 13 14 28

13 14 17 28 42

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 20

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

5.2. Implémentation

void mergeSort(int *A, int deb, int fin)

{
int mil;
if (deb<fin) {
mil=(deb+fin)/2; (* DIVIDE *).................................................... 𝑶(𝟏)
mergeSort(A,deb,mil); (* CONQUER *).................................................... 𝑻(𝒏/𝟐)
mergeSort(A,mil+1,fin); (* CONQUER *).................................................... 𝑻(𝒏/𝟐)
fusion(A,deb,mil,fin); (* COMBINE *).................................................... 𝑶(𝒏)
}
}

void fusion(int *A, int deb, int mil, int fin)

{
int n1,n2,i,j;
int* R = new int[50]; int* L = new int[50];
n1=mil-deb+1;
n2=fin-mil;
for (i=1;i<=n1;i++) L[i]=A[deb+i-1];
for (j=1;j<=n2;j++) R[j]=A[mil+j];
L[n1+1]=9999; //9999 = Nombre très grand
R[n2+1]=9999;
i=j=1;
for (int k=deb;k<=fin;k++) {
if (L[i]<=R[j]) {A[k]=L[i];i++;}
else {A[k]=R[j];j++;}
}
}

5.3. Complexité
La complexité peut être exprimée par récurrence :
 O(1) si n = 1
T(n) =   T(n) = O(nlog 2 n)
2T (n / 2) + O( n ) si n  1
Ou bien, on peut dire que le tableau A sera divisé par 2 jusqu’à obtention de tableaux de taille 1, ainsi :
Taille de A : n, n/2, n/4,…, 𝑛/2𝑝 avec 𝑛/2𝑝 = 1  𝑝 = 𝑙𝑜𝑔2 (𝑛)
Puisqu’à chaque étape, une (ou plusieurs) opération(s) de fusion de l’ordre de 𝑂(𝑛) est exécutée sur les
sous tableaux obtenus, on obtient donc 𝑂(𝑛𝑙𝑜𝑔2 𝑛).

6. Tri rapide (Quick Sort)

6.1. Principe
L’idée de cet algorithme est de diviser le tableau en deux parties séparées par un élément appelé pivot
de telle manière que les éléments de la partie gauche soient tous inférieurs ou égaux à cet élément et
ceux de la partie droite soient tous supérieurs à ce pivot. Cette étape fondamentale du tri rapide
s’appelle le partitionnement.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 21

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Choix du pivot : Le choix idéal serait que ça coupe le tableau exactement en deux parties égales
(voir analyse de complexité), mais cela n’est pas toujours possible. On peut
prendre le premier ou le dernier ou de manière aléatoire,…

Partitionnement :
• On parcourt de gauche à droite jusqu’à rencontrer un élément supérieur au pivot.

• On parcourt de droite à gauche jusqu’à rencontrer un élément inférieur au pivot.

• On échange ces deux éléments.

• On recommence les parcours gauche-droite et droite-gauche jusqu’à avoir :

• Il suffit alors de mettre le pivot à la frontière par un échange

Dans ce qui suit (exemple & implémentation) on choisit l’élément se trouvant au milieu du tableau
comme pivot.

Exemple

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 22

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

6.2. Implémentation

void quickSort(int *A, int deb, int fin)

{
int ipivot;
if (deb<fin) {
ipivot=partition(A,deb,fin);
quickSort(A,deb,ipivot-1);
quickSort(A,ipivot+1,fin);
}
}

int partition(int *A, int deb, int fin)

{
int pivot,aux,i,j;
pivot=A[(deb+fin)/2];
i=deb;j=fin;
while (i<j) {
while (pivot>A[i]) i++;
while (pivot<A[j]) --j;
if (i<j) swap(A,i,j);
}
return j;
}

6.3. Complexité
• Cas favorable :
La meilleure chose qui puisse arriver, c'est qu'à chaque fois que la fonction Partition() est appelée, elle
divise exactement le tableau (ou le sous-tableau) en 2 parties égales.
À la première passe, les 𝑛 éléments du tableau sont comparés avec la valeur pivot pour les balancer à la
droite ou à la gauche. Il y a donc 𝑛 comparaisons. À la seconde passe il y a 2 fonctions Partition() qui
effectuent leur rôle chacune sur leur moitié de tableau. Chaque fonction doit comparer les 𝑛/2 éléments
du sous-tableau pour effectuer le balancement. Donc de fait, il y a encore 𝑛 comparaisons pour cette
passe. Il en sera de même pour les autres itérations.
Nous pouvons exprimer la complexité sous forme de récurrence :
𝑂(1) 𝑠𝑖 𝑛 = 1
𝑇(𝑛) = { 𝑛  𝑇(𝑛) = 𝑂(𝑛𝑙𝑜𝑔2 𝑛)
2𝑇 (2) + 𝑂(𝑛) 𝑠𝑖 𝑛 > 1

• Cas défavorable :
La pire chose qui puisse arriver, c'est qu'à chaque appel de la fonction Partition(), à cause des
circonstances de la disposition des données, celle-ci place la totalité du sous-tableau à droite ou à
gauche (excluant bien sûr l'élément pivot qui est alors à sa place définitive). Dès lors le tri rapide se
transforme en un tri à bulles.
À la première passe, il y aura donc 𝑛 comparaisons. À la seconde passe il y a déjà une valeur ordonnée
et un sous-tableau de 𝑛 − 1 éléments, il y aura donc 𝑛 − 1 comparaisons effectuées par la fonction
Partition(). À la 3ème passe, il y aura 𝑛 − 2 comparaisons, etc.
Pour effectuer le tri au complet, il aura donc fallu en tout 𝑛 passes. D'où la complexité:

𝑛 + (𝑛 − 1) +. . . +2 + 1 = 𝑛(𝑛 + 1)/2
Soit donc O(𝑛²) = complexité pire cas du Quicksort. Mais il reste que la complexité en moyenne est
O(𝑛log𝑛).

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 23

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

7. Etude comparative de la complexité des algorithmes de tri étudiés

Chaque algorithme de tri a ses avantages et ses inconvénients, et le choix de l'algorithme à utiliser
dépend souvent des caractéristiques spécifiques des données à trier ainsi que des exigences en termes
de performances et de mémoire :

• Tri par sélection : Simple à comprendre et à implémenter, mais inefficace pour de grandes listes.
• Tri par insertion : Efficace pour de petites listes ou des listes partiellement triées.
• Tri à bulles : Généralement considéré comme l'un des algorithmes de tri les moins efficaces pour les
grandes listes.
• Tri par fusion : Très efficace et stable, mais nécessite un espace auxiliaire supplémentaire.
• Tri rapide : Très rapide pour la plupart des cas pratiques, mais peut être inefficace (dans le pire des
cas) si le pivot est mal choisi. Utilisé couramment en pratique avec des optimisations comme le pivot
médian de trois. Sa complexité spatiale peut être améliorée en 𝑂(𝑙𝑜𝑔𝑛) grâce à un partitionnement
en place (in-place).

Tableau récapitulatif

Algorithme Meilleur cas Cas moyen Pire cas Complexité Spatiale

Tri par sélection 𝑂(𝑛2 ) 𝑂(𝑛2 ) 𝑂(𝑛2 ) 𝑂(1)
Tri par insertion 𝑂(𝑛) 𝑂(𝑛2 ) 𝑂(𝑛2 ) 𝑂(1)
Tri à bulles 𝑂(𝑛) 𝑂(𝑛2 ) 𝑂(𝑛2 ) 𝑂(1)
Tri par fusion 𝑂(𝑛𝑙𝑜𝑔𝑛) 𝑂(𝑛𝑙𝑜𝑔𝑛) 𝑂(𝑛𝑙𝑜𝑔𝑛) 𝑂(𝑛)
Tri rapide 𝑂(𝑛𝑙𝑜𝑔𝑛) 𝑂(𝑛𝑙𝑜𝑔𝑛) 𝑂(𝑛2 ) 𝑂(𝑙𝑜𝑔𝑛)

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 24

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

CHAPITRE 3 : LES ARBRES

Plan
1. Introduction
2. Définitions
3. Arbres binaires
4. Arbres binaires particuliers

1. Introduction
Pour de grandes quantités de données, la complexité linéaire des opérations sur les listes est
prohibitive. Nous étudions dans ce chapitre, les structures de données hiérarchiques ou arborescentes
pour qui le temps d’exécution de la plupart des opérations est de l’ordre de 𝑂(𝑙𝑜𝑔𝑁). Nous
commençons par rappeler les définitions relatives aux arbres en général et les arbres binaires en
particulier, puis nous montrons comment utiliser les arbres binaires pour développer un algorithme de
recherche avec une complexité de 𝑂(𝑙𝑜𝑔𝑁). Nous terminons avec une autre application des arbres
binaires à savoir les tas ainsi qu’un nouvel algorithme efficace de tri dit tri par tas.

2. Définitions
Un arbre est défini récursivement comme étant une structure composée d’éléments appelés nœuds liés
par une relation « Parent/Fils » ; il contient un nœud particulier appelé racine (le seul qui n’a pas de
nœud parent), ainsi qu’une suite ordonnée (qui peut être vide) d’arbres disjoints 𝐴1 , 𝐴2 , … . , 𝐴𝑚 appelés
sous-arbres. Un nœud peut prendre n’importe quel type de donnée : simple (numérique, caractère,…)
ou composé (structure, classe) etc.

Un exemple typique d’arbre est celui de l’arbre généalogique où les nœuds représentent les personnes
et la relation entre nœuds est la relation classique de « parenté ». La figure suivante illustre la
schématisation d’une partie de l’arbre généalogique mathématique (http://www.genealogy.ams.org). La
relation « parenté » est interprétée comme « étudiant ou doctorant de » :

Joseph Lagrange

Jean Fourier Siméon Poisson

Giovanni Plana

Gustav Dirichlet Michel Chasles

Il y a lieu de rappeler aussi les définitions suivantes relatives aux arbres :

- Les fils d’un nœud sont les racines de ses sous arbres, par exemple les « doctorants » de Lagrange
sont Fourier, Poisson et Plana.
- Le père d’un nœud (excepté la racine) est l’unique nœud dont il est fils.
- Un nœud interne est un nœud autre que la racine qui a au moins un fils, par exemple Poisson.
- Une feuille est un nœud qui n’a pas de fils.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 25

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

- Les ancêtres d’un nœud sont les nœuds qui le relient à la racine y compris celle-ci et le nœud lui-
même.
- Les descendants d’un nœud sont les nœuds qui appartiennent au sous-arbre ayant ce nœud comme
racine.
- La profondeur d’un nœud est la longueur du chemin reliant celui-ci à la racine.
- La hauteur d’un arbre est la profondeur max. de ses nœuds.
- La taille d’un arbre est le nombre total de ses nœuds.

Parcours d’un arbre

La procédure permettant d’examiner une fois et une seule fois tous les nœuds d’un arbre est appelée
parcours d’un arbre. Il y a lieu de citer :

Parcours en préordre (préfixe) « RGD = Racine Gauche Droite »

Il s’agit d’implémenter récursivement les étapes suivantes :
- Examen de la racine
- Parcourir en préordre le premier sous-arbre (le plus à gauche)
- …
- Parcourir en préordre le dernier sous-arbre (le plus à droite).

Dans l’exemple précédent, on parcourt les nœuds Lagrange, Fourier, Poisson, Dirichlet, Chasles, Plana.

Fin
Début Joseph Lagrange

Jean Fourier Siméon Poisson Giovanni Plana

Gustav Dirichlet Michel Chasles

Le schéma ci-dessus illustre le parcours en préordre comme étant un examen des nœuds dés la
première rencontre uniquement.

Parcours en postordre (postfixe) « GDR = Gauche Droite Racine »

Dans ce type de parcours, il s’agit d’implémenter récursivement les étapes suivantes :
- Parcourir en postordre le premier sous-arbre
- …
- …
- Parcourir en postordre le dernier sous-arbre
- Examiner la racine.

Le parcours en postordre de l’arbre précèdent se fait comme suit : Fourier, Dirichlet, Chasles, Poisson,
Plana, Lagrange. Cette opération est similaire à la précédente sauf que cette fois-ci l’examen des nœuds
se fait à la dernière rencontre.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 26

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Parcours par niveaux

Consiste à parcourir l’arbre à partir de la racine (niveau 0), puis les nœuds du niveau 1 de gauche à
droite et ainsi de suite. Ce parcours est considéré comme un parcours en largeur alors que les parcours
prefixe et postfixe sont considérés comme des parcours en profondeur.
Le parcours par niveau de l’arbre cité en exemple se fait donc comme suit : Lagrange, Fourier, Poisson,
Plana, Dirichlet, Chasles.

Quelques opérations sur les arbres

On peut citer parmi les opérations sur les arbres :
- initialiserArbre() : retourne un arbre vide ou nul.
- parent (n,A) : fonction qui renvoie le parent d’un nœud n dans l’arbre A. Dans le cas de la racine un
nœud nul est renvoyé par la fonction. Ceci servira comme un signal d’arrêt lors de la navigation.
- filsLePlusAGauche(n,A) : renvoie le fils le plus à gauche du nœud n dans l’arbre A. Dans le cas d’un
nœud n’ayant pas de fils, cette fonction renvoie le nœud nul.
- filsLePlusADroite(n,A) : Idem mais renvoie le fils le plus à droite.
- racine(A) : renvoie le nœud racine. Dans le cas où l’arbre est vide, elle retourne le nœud nul.
- estFeuille(n,A) : permet de tester si le nœud n est une feuille.
- nbFeuilles(A) : retourne le nombre de feuilles de l’arbre A.

3. Arbres binaires
Un arbre binaire peut être soit vide, soit constitué du nœud racine qui pointe éventuellement vers deux
sous arbres au maximum. A chaque niveau de l’arbre binaire, les deux sous arbres binaires disjoints sont
appelés sous arbre gauche et sous arbre droit. Un arbre binaire désigne souvent un arbre non vide. Les
procédures de parcours des arbres n-aires restent valables pour les arbres binaires et la terminologie
utilisée est légèrement remaniée pour tenir compte de certaines spécificités des arbres binaires. En
effet, lorsqu’on désigne les fils d’un nœud on parle du fils gauche et fils droit dans le cas où l’un deux ou
bien les deux existent.
a

c b

h f e d

g
Remarque : Un arbre binaire est dit :
▪ homogène lorsque tous les nœuds ont deux ou zéro fils.
▪ dégénéré si tous ses nœuds n’ont qu’un seul fils.
▪ complet si chaque niveau de l’arbre est complètement rempli (i.e. le niveau 𝑖 contient 2𝑖 nœuds)
▪ parfait lorsque tous les niveaux sauf éventuellement le dernier sont remplis, et dans ce cas les
feuilles du dernier niveau sont groupées à gauche.
▪ équilibré si pour chaque nœud la différence entre la hauteur du sous arbre gauche et la hauteur
du sous arbre droit ne dépasse pas 1.
Pour implémenter un arbre binaire, on associe à chaque nœud une structure de donnée contenant la
donnée et deux adresses qui pointent vers les deux nœuds fils. Par convention, une adresse nulle
indique un arbre (ou sous arbre) vide. De cette façon, il suffit donc de mémoriser l’adresse de la racine.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 27

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

3.1. Structures de données

A l’aide de tableaux (Statique)
Les arbres binaires peuvent être représentés par la structure suivante :
const int MaxNoeuds=1000;

struct Noeud{
int element;
int filsGauche;
int filsDroit;
};

Noeud Arbre[MaxNoeuds];

A l’aide de pointeurs (Dynamique)

Au lieu d’utiliser des champs entiers pour pointer vers les fils gauche et droite, on peut faire usage des
pointeurs comme suit :
struct Noeud {
int element;
Noeud *filsGauche, *filsDroit, *parent;
};
Ainsi un arbre binaire est représenté par une structure chaînée dans laquelle chaque nœud est un objet.
En plus des champs element (clé) et adresse de la donnée, chaque nœud contient trois champs :
filsGauche, filsDroit et parent. Ces champs pointent vers le sous arbre gauche, sous arbre droit et le
parent du nœud respectivement dans le cas où ils existent. Dans le cas contraire, un ou plusieurs de ces
champs contient la valeur NULL. La racine est le seul nœud dont le champ parent est NULL.

Le pointeur parent permet de faciliter le parcours dans le sens « feuilles → racine ». Une autre variante
consiste à supprimer ce pointeur pour un gain d’espace mémoire et pour simplifier les procédures de
mise à jour de l’arbre binaire, mais au détriment du parcours de l’arbre. Ainsi on peut représenter plus
simplement l’arbre binaire comme suit :

struct Noeud {
int element;
Noeud *filsGauche, *filsDroit;
};

Note : L’arbre binaire est déclaré et initialisé avec l’instruction : Noeud *racine=NULL;

3.2. Parcours d’un arbre binaire

En plus des parcours en préordre et postordre dèjà étudiés pour les arbres en général, un troisième type
de parcours en profondeur peut être utilisé dans le cas des arbres binaires : Le parcours en ordre
(infixe).
 PARCOURS EN PREORDRE (PREFIXE) : « RGD = RACINE GAUCHE DROITE »
Il s’agit d’implémenter récursivement les étapes suivantes :
- Examiner la racine
- Parcourir en préordre le sous-arbre gauche
- Parcourir en préordre le sous-arbre droit

Ainsi le parcours en préordre de l’arbre binaire cité en exemple donne : a, c, h, f, g, b, e, d.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 28

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

 PARCOURS EN ORDRE (INFIXE) : « GRD = GAUCHE RACINE DROITE »

Il s’agit d’implémenter récursivement les étapes suivantes :
- Parcourir en ordre le sous-arbre gauche
- Examiner la racine
- Parcourir en ordre le sous-arbre droit

Ainsi le parcours en ordre du même arbre binaire donne : h, c, g, f, a, e, b, d.

 PARCOURS EN POSTORDRE (POSTFIXE) : « GDR = GAUCHE DROITE RACINE »

Il s’agit d’implémenter récursivement les étapes suivantes :
- Parcourir en postordre le sous-arbre gauche
- Parcourir en postordre le sous-arbre droit
- Examiner la racine

Le parcours en postordre du même arbre binaire donne : h, g, f, c, e, d, b, a.

Ces parcours peuvent être implementés aisément en utilisant des routines récursives comme suit :

void parcoursPrefixe(Noeud *racine)

{ if (racine!=NULL) {
cout<<racine->element<<endl;
parcoursPrefixe(racine->filsGauche);
parcoursPrefixe(racine->filsDroit); }
}

void parcoursInfixe(Noeud *racine)

{ if (racine!=NULL) {
parcoursInfixe(racine->filsGauche);
cout<<racine->element<<endl;
parcoursInfixe(racine->filsDroit); }
}

void parcoursPostfixe(Noeud *racine)

{ if (racine!=NULL) {
parcoursPostfixe(racine->filsGauche);
parcoursPostfixe(racine->filsDroit);
cout<<racine->element<<endl; }
}

Exercice : Proposer une implementation itérative de ces 3 parcours.

3.3. Construction/Destruction d’un arbre binaire

Rappelons qu’un arbre est une structure de données récursive ; en effet un arbre binaire est formé
d’une racine dont les fils gauche et droite sont aussi des arbres. Ceci permet de construire un arbre de
manière très simple grâce aux routines suivantes :

Noeud *nouveauNoeud(int x) {
Noeud *nouv = new Noeud;
nouv->element = x;
nouv->filsGauche = nouv->filsDroit = NULL;
return nouv;
}

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 29

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Noeud *joindre(Noeud *fg, Noeud *fd, int valNoeud) {

Noeud *nouv = nouveauNoeud(valNoeud);
nouv->filsGauche = fg;
nouv->filsDroit = fd;
return nouv;
}

Pour détruire un arbre et récupérer l’espace alloué ; on exécute la routine recursive suivante :

void effacer(Noeud *p) {

if (p==NULL) return;
effacer(p->filsGauche);
effacer(p->filsDroit);
delete p;
}

Le programme suivant met en œuvre les routines décrites précédemment pour construire l’arbre
suivant. L’espace mémoire est récupéré à la fin du programme.
10

6 16

2 8 14 18

int main() {
Noeud *SAG = joindre(nouveauNoeud(2),nouveauNoeud(8),6);
Noeud *SAD = joindre(nouveauNoeud(14),nouveauNoeud(18),16);
Noeud *racine = joindre(SAG,SAD,10);
parcoursInfixe(racine);
effacer(racine);
}

3.4. Opérations sur les arbres binaires

Voici des détails d’implémentation de quelques opérations sur les arbres binaires en se basant sur la
représentation chaînée :

• Tester si un nœud est une feuille :

bool estFeuille(Noeud *p)
{ return (p->filsGauche==NULL && p->filsDroit==NULL); }

• Taille d’un arbre (nombre de nœuds) :

int taille(Noeud *racine)
{ if (racine==NULL) return 0;
else return 1+taille(racine->filsGauche)+taille(racine->filsDroit);
}

• Nombre de feuilles d’un arbre :

int nbFeuilles(Noeud *racine)
{ if (racine==NULL) return 0;
else if (estFeuille(racine)) return 1;
else return nbFeuilles(racine->filsGauche)+nbFeuilles(racine->filsDroit);
}

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 30

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

3.5. Représentation d’un arbre quelconque sous forme d’un arbre binaire
Même si les arbres binaires sont les plus utilisés en algorithmique, les arbres quelconques ont aussi des
applications importantes. Les routines vues précédemment peuvent aisément être généralisées pour les
arbres quelconques. Il est néanmoins possible de convertir chaque arbre quelconque en arbre binaire en
suivant les étapes suivantes :
1. Supprimez toutes les arêtes de chaque nœud de l’arbre quelconque, à l'exception de l’arête la
plus à gauche (arêtes ℓ pour left).
2. Dessinez des arêtes d'un nœud au nœud qui est à droite, s’il existe, qui est situé au même niveau
(nœuds frères ; arêtes 𝑟 pour right).
3. Générer l’arbre binaire à partir des arêtes ainsi obtenues.

Exemple :
Soit à convertir l’arbre quelconque suivant en arbre binaire :

10

6 2 18 16

8 14 11 9 5 12

Etapes 1 et 2 : 10
ℓ
6 𝑟 𝑟 18 𝑟 16
2
ℓ ℓ
ℓ
8 14 11 9 5 12
𝑟 𝑟 𝑟

Etape 3 :
10

8 2

14 11 18

16

12

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 31

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

3.6. Implémentation des Arbres n-aires

Les arbres n-aires (quelconques) peuvent être implémentés à l’aide de tableaux et aussi à l’aide de listes
chaînées. Chaque implémentation a ses propres avantages et inconvénients quant à sa capacité et son
efficacité à implémenter les opérations classiques sur les arbres décrites précédemment.

A l’aide de tableaux
Considérons un arbre dont les n nœuds sont désignés par 0,1,…,n-1. La meilleure structure « en termes
d’efficacité » qui supporte l’opération parent (n,A) est un tableau A dont l’élément A[i] pointe sur le
parent du nœud i. Par conséquent on peut implémenter un arbre quelconque par un tableau A défini
comme suit :

A[i] = j si le nœud j est parent du nœud i

A[i] = -1 dans le cas où i est la racine de l’arbre.

Il est clair qu’avec cette représentation l’opération parent est de complexité constante
indépendamment de la taille de l’arbre. Cependant, cette représentation complique d’avantage les
opérations utilisant l’information sur les fils d’un nœud. En outre, on ne peut pas imposer un ordre sur
les fils d’un nœud, en particulier les opérations filsLePlusAGauche, filsLePlusADroite ne peuvent être
définies.

Exemple : Si on fait correspondre un indice à chaque nœud de l’arbre de la section 1, on obtient :

Nœud Indice
J. Lagrange 0
J. Fourier 1
S. Poisson 2 0 1 2 3 4 5
G.Plana 3  -1 0 0 0 2 2
G. Dirichlet 4
M. Chasles 5

A l’aide de tableaux de pointeurs

Une façon efficace de représenter un arbre consiste à construire une liste des fils de chaque nœud qui
peut être implémentée avec une liste chaînée, car le nombre de fils varie d’un nœud à un autre :
const int MaxNoeuds=1000;

struct Bloc {
int element;
Bloc *suiv;
};

struct Arbre {
Bloc *Noeuds[MaxNoeuds];
char Etiquettes[MaxNoeuds];
int racine;
};

Ainsi l’arbre cité en illustration est représenté comme suit :

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 32

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Noeuds[] Etiquettes[]
0 1 2 3 NULL 0 J. Lagrange

1 NULL 1 J. Fourier
2 4 5 NULL 2 S. Poisson

3 NULL 3 G. Plana

4 NULL 4 G. Dirichlet
5 NULL racine 5 M. Chasles
0

Exercice : Proposer une implémentation des routines citées dans la section 1 en se basant sur cette
représentation.

Représentation dynamique
Vu que le nombre de fils peut varier d’un nœud à un autre et de surcroit n’est pas connu à l’avance, une
représentation dynamique basée sur un bloc associant la donnée du nœud avec des pointeurs vers tous
ses fils serait irréalisable. La solution est simple : Il suffit de garder pour chaque nœud un lien vers le fils
le plus à gauche et un lien vers le nœud représentant le prochain « frère » comme suit :

Joseph Lagrange

Jean Fourier Siméon Poisson Giovanni Plana

Gustav Dirichlet Michel Chasles

struct Noeud {
int element;
Noeud *premierFils;
Noeud *frere;
};

Voici l’implémentation de certaines routines utilisant cette représentation :

• Affichage des fils d’un nœud
void affichFils(Noeud *p)
{ Noeud *courant = p->premierFils;
while (courant != NULL) {
cout << courant->element << endl;
courant = courant->frere; }
}
• Parcours postfixe

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 33

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

void postfixe(Noeud *racine)

{ if (racine!=NULL) {
postfixe(racine->premierFils);
cout<<racine->element<<endl;
postfixe(racine->frere);
}
}

4. Arbres binaires particuliers

4.1. Arbre binaire de recherche (Binary Search Tree ou BST)

Un Arbre Binaire de Recherche (ABR) ou arbre ordonné est un arbre où les données, présentes au
niveau des nœuds, sont régies par une relation d’ordre totale. En plus, quelque soit le nœud interne, les
données présentes dans le sous arbre à gauche sont inférieures ou égales à la donnée présente dans ce
nœud, qui elle-même est inférieure ou égale à celles présentes au niveau du sous arbre droit.

Cette manière d’organiser les données permet de rechercher les éléments avec une complexité de
l’ordre de O(logN) si l’arbre est équilibré. L’avantage de cette méthode de recherche par rapport à la
recherche dichotomique dans une liste triée réside notamment dans l’opération d’insertion. En effet
pour maintenir une liste triée, l’insertion se fait dans le pire des cas (et aussi en moyenne) en O(N), alors
que dans les arbres binaires de recherche, la complexité en moyenne de l’insertion est de l’ordre de
O(logN) pour peu que l’arbre soit équilibré.

Exemple :
25

15 30

12 20 26 35

18 23
29

De par sa structure, le parcours en ordre (infixe) d’un arbre binaire de recherche produit une liste triée
des données qu’il contient. Les procédures classiques de recherche, insertion, suppression, minimum ou
maximum peuvent être aisément effectuées à l’aide de procédures récursives ou itératives.

• Recherche

bool rechercher(Noeud *racine , int val)

{ if (racine==null) return false;
else if (racine->element==val) return true;
else if (racine->element>val)
return rechercher(racine->filsGauche,val);
else return rechercher(racine->filsDroit,val);
}

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 34

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

• Insertion

void inserer(Noeud *&racine , int val)

{ Noeud *p=racine, *prec=NULL ;
while (p!=NULL) {
prec=p;
if (p->element>val) p=p->filsGauche;
else p=p->filsDroit;
}
Noeud *nouv=new Noeud;
nouv->element=val;
nouv->filsGauche=nouv->filsDroit=NULL;
if (prec==NULL) racine=nouv;
else if (prec->element>val) prec->filsGauche=nouv;
else prec->filsDroit=nouv;
}

Il est facile de constater que la complexité des opérations insertion et recherche dans un arbre binaire
de recherche (de taille n) est égale, dans le pire des cas, à la hauteur de l’arbre soit :
- O(log2(n)) dans le cas d’un arbre équilibré.
- O(n) dans le cas d’un arbre dégénéré.

• Suppression
Plusieurs cas sont à considérer, une fois que le nœud à supprimer a été trouvé à partir de sa clé :

• Suppression d'une feuille : Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
• Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils.
• Suppression d'un nœud avec deux enfants : Supposons que le nœud à supprimer soit appelé T (le
nœud de valeur 7 dans le graphique ci-dessous). On échange le nœud T avec son successeur le plus
proche (le nœud le plus à gauche du sous-arbre droit - ci-dessous, le nœud de valeur 9) ou son plus
proche prédécesseur (le nœud le plus à droite du sous-arbre gauche - ci-dessous, le nœud de valeur
6). Cela permet de garder une structure d'arbre binaire de recherche. Puis on applique à nouveau la
procédure de suppression à T, qui est maintenant une feuille ou un nœud avec un seul fils.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 35

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

4.2. Arbre binaire de recherche équilibré : Arbre AVL

Les arbres AVL sont des arbres binaires de recherche automatiquement équilibré ; les hauteurs des sous-
arbres d’un même nœud diffèrent au plus de un. La recherche, l’insertion et la suppression sont toutes
en 𝑂(𝑙𝑜𝑔𝑛) dans le pire des cas. L’insertion et la suppression nécessitent de temps à autre d’effectuer
des opérations de rééquilibrage appelées rotations.
La dénomination « arbre AVL » provient des noms respectifs de ses deux inventeurs, respectivement
Georgii Adelson-Velsky et Evgueni Landis.

Facteur d’équilibrage 𝒇
Le facteur d’équilibrage 𝑓 d’un nœud est la différence entre la hauteur de son sous arbre droit et celle de
son sous arbre gauche. Un nœud dont le facteur d’équilibrage est 1, 0 ou -1 est considéré comme
équilibré, autrement il est considéré comme déséquilibré et requiert un équilibrage. Ce facteur est soit
calculé à partir des hauteurs respectives des sous-arbres, soit stocké dans chaque nœud de l’arbre (voir
figure ci-dessous).

Insertion dans un AVL

L’insertion d’un nœud dans un arbre AVL se déroule en deux étapes : tout d’abord, on insère le nœud
exactement de la même manière que dans un arbre binaire de recherche, puis si l’arbre devient
déséquilibré, on effectue une rotation simple (à droite ou à gauche) ou double (gauche-droite ou droite-
gauche) pour équilibrer l’arbre.

Pour cela, il faut identifier trois nœuds qui forment un triplet (grand parent, parent et enfant) et quatre
sous-arbres attachés à ces nœuds. Soit w le nœud qui vient d’être inséré et qui a provoqué un
déséquilibrage de l’arbre. On parcourt l’arbre vers la racine pour identifier les trois nœuds x, y et z
ancêtres de w. Ces trois nœuds peuvent avoir quatre sous-arbres connectés à eux : T0, T1, T2 et T3
comme dans les exemples de la figure ci-dessous :

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 36

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Puis le rééquilibrage se fait en considérant les trois nœuds dans l’ordre infixe selon les 4 opérations
suivantes :

Rotation simple à gauche

L’arbre de racine z penche à droite et son sous-arbre droit de racine y penche à droite ; 𝑓(z)=2 et 𝑓(y)=1

Rotation simple à droite

L’arbre de racine z penche à gauche et son sous-arbre gauche de racine y penche à gauche ; 𝑓(z)= –2 et
𝑓(y)= –1.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 37

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Rotation double gauche-droite

L’arbre de racine z penche à gauche et son sous-arbre gauche de racine y penche à droite ; 𝑓(z)= –2 et
𝑓(y)= 1 => rotation gauche de y suivie d’une rotation droite de z.

Rotation double droite-gauche

L’arbre de racine z penche à droite et son sous-arbre droit de racine y penche à gauche ; 𝑓(z)= 2 et 𝑓(y)=
–1 => rotation droite de y suivie d’une rotation gauche de z.

Complexité
L’arbre étant équilibré, toutes les opérations de rotation ont donc une complexité de l’ordre de
𝑂(𝑙𝑜𝑔𝑁). La routine d’insertion reste par conséquent de complexité logarithmique.

Suppression dans un AVL

La même stratégie de rééquilibrage de l’arbre peut être appliquée après la suppression d’un élément.
Soit w l’élément à supprimer ou l’élément qui s’est substitué à l’élément à supprimer. Soit z le premier
nœud déséquilibré rencontré en traversant l’arbre vers la racine à partir de w. Soit y l’enfant de z ayant
USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 38
UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

la plus grande hauteur et x l’enfant de y ayant la plus grande hauteur (x et y ne sont pas ancêtres de w).
La restructuration réduit à 1 la hauteur du sous-arbre initialement enraciné à z et ainsi pourrait
déséquilibrer un autre nœud plus haut dans l’arbre. Ainsi, il faut continuer à vérifier l’équilibre jusqu’à
ce que la racine soit atteinte.

L’exemple suivant montre le choix des nœuds x et y et z et le rééquilibrage fait après suppression de
l’élément 32.

On peut choisir un autre x (50 au lieu de 78 par exemple)

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 39

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

4.3. Structures de données Tas (Heap)

Définition d’un tas (Heap)

Un tas est représenté sous forme d’un arbre binaire parfait (rempli de la gauche vers la droite).
Les données dans les sommets doivent appartenir à un ensemble totalement ordonné et la donnée
présente au niveau d’un nœud doit être plus grande que celles présentes au niveau de ses deux nœuds
fils dans le cas où ce nœud possède deux fils ou bien au niveau de son nœud fils, dans le cas où il n’y a
qu’un seul. On parle alors de max-tas (ou tas décroissant) comme l’illustre la figure suivante. Noter la
différence avec un arbre binaire de recherche.

60

29
21

25 5 12 16

Le tas peut aussi être ordonné de manière croissante, on parle alors de min-tas (ou tas croissant).

Implémentation
Pour chaque structure de tas correspond une structure linéaire (tableau, liste) particulière obtenue par
la numérotation des nœuds niveau par niveau et de gauche à droite. La racine occupe le premier
élément de la structure.

Il est facile de vérifier (par récurrence) que les nœuds du niveau 𝑖 occupent les rangs entre [2𝑖 , 2𝑖+1 [. Le
parent d’un nœud qui se trouve en position 𝑗, autre que la racine, occupe la position 𝑗/2 , c'est-à-dire
la partie entière de 𝑗 divisé par 2.

Le tableau suivant correspond au codage de la structure de tas décrite précédemment :

1 2 3 4 5 6 7 8
60 29 21 25 5 12 16 9

La déclaration d’un tas peut donc être :

const int MaxSize=9999;

struct Tas {
int Donnees[MaxSize]; //La case indice 0 ne sera pas utilisée
int taille;
};

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 40

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Opérations sur le tas

Insertion dans un tas
L’insertion dans un tas doit respecter la structure d’arbre parfait. Pour cela, l’insertion se fait au niveau
de la dernière rangée si celle-ci n’est pas pleine. Dans le cas contraire, on doit créer une nouvelle rangée
et l’élément à insérer doit occuper la première place dans cette nouvelle rangée. Dans les deux cas
l’insertion se fait toujours à la fin de la structure linéaire, en l’occurrence le tableau correspondant.
D’autre part, pour respecter le fait que la donnée présente au niveau du père doit être supérieure à
celles présentes dans les nœuds fils (cas d’un max-tas), le nouvel élément inséré doit être échangé avec
son père si ce principe n’est pas respecté autant de fois qu’il est nécessaire. La procédure d’insertion
peut être implémentée comme suit :

void insertionTas(Tas &T, int cle)

{ int i=T.taille+1;
while (i>=2 && cle>T.Donnees[i/2])
{ T.Donnees[i]=T.Donnees[i/2]; i=i/2;}
T.Donnees[i]=cle;
T.taille++;
}

Complexité de l’insertion dans un tas

L’insertion de la kème donnée se fait toujours, en premier lieu à la fin du tableau. Ceci correspond donc
au niveau log2(k) de l’arbre qui représente le tas. Par conséquent, dans le pire des cas et lors de
l’insertion, la donnée peut remonter jusqu’au sommet de l’arbre. Par conséquent, la complexité de
l’insertion est O(log2(k)) et ceci bien sûr dans le pire des cas.

Suppression dans un tas

La suppression d’un élément d’un tas se fait d’abord en substituant l’élément à supprimer avec le
dernier élément du tas. Une fois l’élément supprimé, le dernier élément du tas, se trouvant donc à la
place de l’élément supprimé est comparé avec ses fils. Ainsi cet élément est déplacé éventuellement
vers le bas jusqu’à ce que la propriété du tas soit respectée.

Exercice : Proposer une implémentation de la suppression dans un tas et mesurer sa complexité.

Le Tri par Tas (HeapSort)

De par sa structure, le sommet d’un tas contient toujours la donnée ayant la plus grande valeur de la clé
(max-Tas) ou la plus petite (min-Tas). Cette remarque importante peut être utilisée pour le
développement d’un des algorithmes les plus efficaces pour le tri qui a une complexité dans le pire des
cas, et aussi en moyenne, égale à O(nlog2(n)).

Dans le cas d’un max-tas, le principe du tri tas consiste d’abord à échanger la donnée contenue dans la
racine avec celle contenue dans la dernière feuille de l’arbre qui correspond à la dernière case du
tableau représentant le tas. Par conséquent, après cette opération d’échange la donnée contenue dans
la dernière case du tableau est la plus grande et reste inchangée dans le cas du tri par ordre croissant
des données d’un tas. Pour compléter le tri, l’algorithme doit reconstituer les données dont les indices
se situent entre 1 et n-1 en un sous tas pour pouvoir réutiliser la remarque précédente. Pour respecter
la structure d’un tas, la nouvelle donnée qui vient d’être insérée dans la racine doit être éventuellement
déplacée vers le bas pour être plus grande que les données contenues dans ses fils. Cette opération doit
être répétée autant de fois qu’il est nécessaire jusqu'à atteinte d’une feuille du tas et que la donnée qui
descend est plus petite que celles contenues dans ses deux fils.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 41

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Exemple : Tri Tas (cas d’un min-tas) appliqué au tableau suivant :

40 16 20 23 28

a) Construction du Tas (Insertion)

• Insertion de 40 40

40 16
• Insertion de 16

16 40

• Insertion de 20 16

40 20

• Insertion de 23

16
16

40 20
23 20

23
40

• Insertion de 28
16

23 20

40 28

Tas obtenu après cette étape :

16 23 20 40 28

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 42

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

b) Tri Tas (Suppression)

• Suppression de la racine 16

16 28 20

23 20 23 23
20 28

40 28 40 40

• Suppression de 20
40 23

16 20
23 28 40 28

• Suppression de 23 28

16 20 23
40

• Suppression de 28
40
16 20 23 28

• Suppression de 40 (Tas vide)

16 20 23 28 40

Les détails d’implémentation du tri tas figurent ci-dessous.

void deplaceVersLeBas(Tas &A, int premier, int dernier)

{
int r,temp;
r=premier;
while (r<=dernier/2)
if (dernier==2*r)
{
if (A.Donnees[r]>A.Donnees[2*r])
{
temp=A.Donnees[r];
A.Donnees[r]=A.Donnees[2*r];
A.Donnees[2*r]=temp;
}
r=dernier;
}
else

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 43

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

if (A.Donnees[r]>A.Donnees[2*r] && A.Donnees[2*r]<=A.Donnees[2*r+1])

{
temp=A.Donnees[r];
A.Donnees[r]=A.Donnees[2*r];
A.Donnees[2*r]=temp;
r=2*r;
}
else
if (A.Donnees[r]>A.Donnees[2*r+1] && A.Donnees[2*r+1]<=A.Donnees[2*r])
{
temp=A.Donnees[r];
A.Donnees[r]=A.Donnees[2*r+1];
A.Donnees[2*r+1]=temp;
r=2*r+1;
}
else r=dernier;
}

void triTas(Tas& A)
{
int i,temp;
for (i=A.taille/2;i>=1;i--) deplaceVersLeBas(A,i,A.taille);
for (i=A.taille;i>=2;i--)
{ temp=A.Donnees[1];
A.Donnees[1]=A.Donnees[i];
A.Donnees[i]=temp;
deplaceVersLeBas(A,1,i-1);
}
}

La complexité du tri tas peut être évaluée comme suit : chaque opération de déplacement prend dans le
pire des cas log2(p) où p étant le nombre de nœuds concernés par cette opération. Par conséquent, la
n
complexité totale est O(  log 2 ( p) ) = O(nlog2(n)).
p =1

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 44

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

CHAPITRE 4 : LES GRAPHES

Plan
1. Introduction aux graphes
2. Définitions
3. Représentation des graphes
4. Parcours des graphes
5. Problème des chemins optimaux

1. Introduction aux graphes

Les graphes sont actuellement l’outil privilégié pour modéliser des ensembles de structures complexes.
Ils sont indispensables pour représenter et étudier des relations entre les objets.

Les graphes sont utilisés en :

• Economie (diagramme d’organisation)
• Electronique (circuits intégrés)
• Base de données (liens entre informations)
• Communications (réseaux de télécommunications)
• Transport (réseaux routiers)
• Ordonnancement (structure des projets)
• Etc.

x3 x2
2. Définitions
x1
2.1 Graphes orientés (Directed Graphs)
x4 x5
- Un graphe 𝑮 est un couple (𝑿, 𝑼) où :
▪ 𝑋 est un ensemble {𝑥1 , … , 𝑥𝑛 } de nœuds ou sommets.
▪ 𝑈 = {𝑢1 , 𝑢2 , … , 𝑢𝑚 } est une famille de couples ordonnées de sommets appelées arcs.

- Un graphe est dit valué s’il  une application 𝐶 : 𝑈 → 𝑅, associant à chaque arc 𝑢 un réel 𝑐𝑢 .

- Une boucle est un arc reliant un nœud à lui-même.

- Chaque arc 𝑢 = (𝑥, 𝑦) a deux extrémités appelées initiale (𝑥) et terminale (𝑦). 𝑢 est dit incident
intérieurement à 𝑥 et incident extérieurement à 𝑦.

- Dans un arc de la forme (𝑥, 𝑦), 𝑥 est appelé prédécesseur de 𝑦 et 𝑦 est dit successeur de 𝑥.
𝑥 et 𝑦 sont appelés sommets voisins (ou adjacents).

- L’ensemble des successeurs de 𝑥 est noté 𝛤(𝑥) et celui de ses prédécesseurs est noté 𝛤 − (𝑥).

- Le nombre de successeurs de 𝑥 est appelé demi degré extérieur et est noté 𝑑𝐺+ (𝑥) = |𝛤(𝑥)|.
Le demi degré intérieur de 𝑥 est défini comme étant 𝑑𝐺− (𝑥) = |𝛤 − (𝑥)|. Le degré de 𝑥 est défini
comme suit : 𝑑𝐺 (𝑥) = 𝑑𝐺+ (𝑥) + 𝑑𝐺− (𝑥).

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 45

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

- La densité d’un graphe est définie par le rapport 𝒎/𝒏² c'est-à-dire le nombre actuel d’arcs de 𝐺
divisé par le nombre maximum d’arcs que peut avoir 𝐺. La plupart des graphes rencontrés en
pratique ne sont pas très dense (à faible densité). Ils sont appelés creux (en Anglais sparse).

2.2 Graphes non orientés

Dans les applications où on s’intéresse uniquement aux paires de sommets reliées et non à leurs
orientations, on parle de graphes non orientés. Dans ce type de graphe, on parle d’une arête (edge en
Anglais) 𝑒 = [𝑥, 𝑦] au lieu de l’arc (𝑥, 𝑦). Un graphe non orienté est noté 𝐺 = (𝑋, 𝐸) où 𝐸 désigne une
famille d’arêtes. Les termes qui s’appliquent aux graphes orientés et sont indépendants de l’orientation
restent valables pour les graphes non orientés.

2.3 Parcours
- On appelle chemin 𝜇 de longueur 𝑝 toute suite de 𝑝 arcs (𝑢1 , … , 𝑢𝑝 ) telle que l’extrémité initiale
de 𝑢𝑖 est égale à l’extrémité terminale de 𝑢𝑖−1 ∀ 𝑖 > 1, et l’extrémité terminale de 𝑢𝑖 est égale à
l’extrémité initiale de 𝑢𝑖+1 ∀ 𝑖 < 𝑝.

- On appelle circuit tout chemin fermé, c'est-à-dire un chemin tel que 𝑢1 = 𝑢𝑝 .

- Un arc est un chemin de longueur 1 et une boucle est un circuit de longueur 1 aussi.

- Si le graphe est non orienté, on parle de chaine au lieu de chemin, et de cycle au lieu de circuit.

- Un parcours est un élément de l’ensemble des chemins, circuits, chaînes et cycles.

2.4 Graphes particuliers

- Un graphe orienté 𝐺 = (𝑋, 𝑈) est dit symétrique si (𝑥, 𝑦) ∈ 𝑈 ⇒ (𝑦, 𝑥) ∈ 𝑈. Les graphes non
orientés peuvent être représentés par des graphes orientés symétriques.

- Le graphe complémentaire de 𝐺 = (𝑋, 𝑈) est le graphe 𝐻 = (𝑋, 𝑋 2 − 𝑈).

- Un graphe est dit complet si toute paire de sommets est connectée par un arc ou une arête.

3. Représentation des graphes

3.1 Matrice d’adjacence

Considérons un graphe orienté 𝐺 = (𝑋, 𝑈) dont le nombre de sommets est 𝑛 et celui des arcs étant 𝑚.
Une matrice d’adjacence est une matrice 𝑀 (𝑛 × 𝑛) dont les éléments sont booléens indiquant si les
sommets correspondants sont reliés.

Un graphe valué 𝐺 = (𝑋, 𝑈, 𝑊) peut être représenté par une matrice 𝑊 (𝑛 × 𝑛) qui donne à la fois les
coûts des arcs et fait fonction de la matrice d’adjacence. Les matrices d’adjacence permettent de
détecter les boucles, la symétrie ainsi que la connectivité. On peut facilement à l’aide de cette structure
de données obtenir la liste des successeurs d’un sommet ainsi que celle de ses prédécesseurs.
Cependant, ces structures ne sont pas adéquates pour les graphes dont la densité est faible.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 46

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Exemple : Le graphe donné en exemple à la section 2.1. est représenté par la matrice d’adjacence M :
𝑥1 𝑥2 𝑥3 𝑥4 𝑥5
𝑥1 0 0 0 0 0
𝑥2 1 0 1 0 0
𝑥3 0 0 1 1 0
𝑥4 0 0 1 0 1
𝑥5 0 0 0 0 0

3.2 Listes d’adjacence

a. Listes Contigües
Les listes d’adjacence implémentent la structure 𝐺 = (𝑋, 𝛤) où les sommets sont rangés
consécutivement dans des tableaux ou bien dans des listes chaînées. Dans le cas des tableaux, on note
par Succ le tableau dont les éléments sont les listes des successeurs des sommets 0,1, … , 𝑛 − 1 dans
l’ordre, c'est-à-dire 𝛤(0), 𝛤(1), … , 𝛤(𝑛 − 1). Le nombre d’éléments de Succ est donc le nombre d’arcs
du graphe à savoir 𝑚. Pour délimiter ces listes successives des successeurs, on fait usage d’une structure
Tête sous forme de tableau à 𝑛 éléments, qui donne pour chaque sommet l’indice dans le tableau Succ
où commence ses successeurs. En effet, les successeurs d’un sommet 𝑦 sont rangés dans Succ de
Tete[y] à Tete[y+1]-1. Dans le cas où un sommet 𝑦 n’a pas de successeurs, on pose Tete[y]=Tete[y+1].

Les graphes non orientés sont codés comme des graphes orientés symétriques. Si [𝑥, 𝑦] est une arête, 𝑥
apparaît dans la liste des successeurs de 𝑦, et 𝑦 dans celle de 𝑥. Dans le cas d’un graphe valué 𝐺 =
(𝑋, 𝑈, 𝑊), on fait usage d’un tableau de poids W en regard du tableau Succ.

L’avantage majeur de ce codage étant sa compacité. En effet, un graphe consomme 𝑛 + 𝑚 + 1 mots

mémoire qui est bien moins que 𝑛² mots d’une matrice dans le cas où 𝐺 n’est pas dense.

Exemple : (Graphe section 2.1)

1 2 3 4 5 6
1 1 3 5 7 7 Tete

1 3 3 4 3 5 Succ
1 2 3 4 5 6

b. Listes Chaînées
Le même principe peut être appliqué en utilisant des listes chaînées comme suit :
Tete
1 null

2 1 3 null

3 3 4 null

4 3 5 null

5 null

Là aussi, il y a lieu d’ajouter pour chaque bloc une case supplémentaire dans le cas de graphe valué pour
stocker le poids de l’arc.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 47

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

4. Parcours des graphes

4.1 Construction des listes de prédécesseurs
a. Représentation en matrice d’adjacence
Soit 𝑀 la matrice d’adjacence d’un graphe G d’ordre 𝑛. Les successeurs d’un sommet quelconque 𝑖
peuvent être obtenus en parcourant la ligne 𝑖 de la matrice 𝑀 en 𝑂(𝑛) opérations. Les prédécesseurs
sont obtenus en parcourant la colonne 𝑖 également en 𝑂(𝑛).

b. Représentation en listes d’adjacence

Pour les graphes de faible densité, il est avantageux de coder le graphe par des structures linéaires
représentant les listes d’adjacence. En effet, la structure nécessite seulement 𝑂(𝑚 + 𝑛) mots-mémoire
et la liste des successeurs ne nécessite que 𝑂(𝑑 + (𝑖)) opérations. Cependant, les listes d’adjacence ne
peuvent pas être manipulées efficacement pour retrouver la liste des prédécesseurs d’un sommet 𝑖.
Pour retrouver la liste des prédécesseurs, il faut balayer tout le graphe pour détecter les sommets dont 𝑖
est successeur et ceci nécessite 𝑂(𝑚) opérations et 𝑂(𝑛𝑚) opérations pour construire les listes des
prédécesseurs de tous les sommets. Dans le cas où la liste des prédécesseurs est requise fréquemment,
il est plus avantageux, en termes de complexité temps, de construire le graphe inverse 𝐺 − de 𝐺 où les
listes des successeurs ne sont autres que les listes de prédécesseurs dans 𝐺. Dans ce cas on consomme
2(𝑚 + 𝑛) mots pour les deux graphes, mais c’est nettement inférieur à 𝑛² pour les graphes de faible
densité.

4.2. Exploration des Graphes

L’exploration consiste à déterminer l’ensemble des descendants d’un sommet 𝑠, c'est-à-dire l’ensemble
des sommets situés sur des chemins d’origine s. Le principe de l’exploration d’un graphe peut être décrit
comme suit : Au début on marque le sommet s, ensuite à chaque fois qu’on rencontre un arc (𝑥, 𝑦) avec
𝑥 marqué et 𝑦 non marqué, on marque alors 𝑦.

a. Exploration en largeur (BFS : Breadth-First Search)

Dans ce type d’exploration, on implémente l’ensemble des sommets marqués comme étant une file 𝐹.
Les sommets sont marqués par ordre de nombre d’arcs croissant à s : on commence par les successeurs
de s, puis les successeurs des successeurs de s, etc. Un sommet 𝑥 en tête de la file 𝐹 reste tant que ses
successeurs ne sont pas examinés. Pendant ce temps, tout successeur de 𝑥 non marqué est marqué et
rangé en fin de 𝐹.

Algorithme :
Marquer s ; Enfiler(F,s)
Repeter …………………………………………………………………………………………………………………N
x = Defiler(F)
pour tout successeur y non marqué de x ……………………………d+(i) = M
Enfiler(F,y)
Marquer y
Finpour
Jusqu’à FileVide(F)

Complexité : O(N+M)  O(M)

b. Exploration en Profondeur (DFS : Depth-First Search)

Il s’agit cette fois ci d’implémenter l’ensemble des sommets marqués comme étant une pile 𝑃 et
l’exploration progresse en se déplaçant le plus loin possible le long d’un chemin dont 𝑠 est l’origine
avant de rebrousser chemin. La pile 𝑃 contient les sommets explorés et permet à la procédure de
rebrousser chemin.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 48

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Algorithme :
Marquer s ; Empiler(P,s)
Repeter
Tant qu’il y a un successeur y à TetePile(P) et non marqué faire
Marquer y
Empiler(P,y)
Fintq
x = Depiler(P)
Jusqu’à PileVide(P)

Idem pour la complexité que BFS.

c. Exemple
Soit un graphe G orienté, dont les sommets sont (s1, s2, s3, s4, s5, s6) représenté par la matrice
d’adjacence suivante. Donner les ordres de parcours en largeur BFS et en profondeur DFS, à partir du
sommet s1.
0 1 1 0 0 1
1 1 0 1 1 0
1 0 0 1 1 0
𝐴=
0 1 1 1 0 1
0 1 1 0 0 1
[0 0 0 1 1 1]

BFS :
s5
s6 s4 s5
File
s3 s6 s4 s5 File
s1 s2 s3 s6 s4 s5 Vide
Sommets Marqués s1 s2,s3,s6 s4,s5

Ordre de défilement : s1,s2,s3,s6,s4,s5

DFS :

s6
s5 s5 s5
Pile s3 s3 s3 s3 s3
s4 s4 s4 s4 s4 s4 s4
s2 s2 s2 s2 s2 s2 s2 s2 s2 Pile
s1 s1 s1 s1 s1 s1 s1 s1 s1 s1 s1 Vide
Sommets Marqués s1 s2 s4 s3 s5 s6

Ordre de dépilement : s6,s5,s3,s4,s2,s1

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 49

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

5. Problème des chemins optimaux

5.1. Typologie, algorithmes et applications des problèmes des chemins optimaux
Soit 𝐺 = (𝑋, 𝐴, 𝑊) un graphe orienté valué et considérons le coût d’un chemin comme étant la somme
des coûts de ses arcs. Les principaux problèmes consistent à trouver des chemins de coût minimal. Dans
ce contexte, il y a lieu de distinguer les trois problèmes suivants :

1. Soient s, t deux sommets, trouver un plus court chemin de s à t.

2. Trouver un plus court chemin de s vers tout autre sommet de 𝐺.
3. Trouver un plus court chemin entre tout couple de sommets.

Dans cette section, on s’intéressera au second problème en calculant pour chaque sommet 𝑥 la valeur
du plus court chemin du sommet de départ vers 𝑥 ; V[x], appelée aussi étiquette ou label.
Il existe une famille d’algorithmes qui calculent V[x] d’une manière définitive pour chaque sommet 𝑥.
Ces algorithmes sont appelés à fixation d’étiquettes et le plus répandu de cette classe est l’algorithme
de Dijkstra. D’autres algorithmes affinent jusqu'à la dernière itération l’étiquette de chaque sommet x.
Cette classe est appelée à correction d’étiquettes. Il y a lieu de distinguer les cas suivants :

- Cas 𝑊 constante. Le problème se réduit à celui de la recherche des chemins contenant le plus
petit nombre d’arcs qui peut être résolu par une exploration en largeur.

- Cas 𝑊 ≥ 0. Le problème peut être résolu par l’algorithme de Dijkstra qui est du type à fixation
d’étiquettes et dont la complexité est 𝑂(𝑛²). Il existe une implémentation en structure de tas
dont la complexité est 𝑂(𝑛 𝑙𝑜𝑔 𝑛) .

- Cas 𝑊 quelconque. Il existe un algorithme dû à Bellman du type à correction d’étiquettes et dont

le principe repose sur la programmation dynamique. La complexité étant 𝑂(𝑛𝑚) qui peut être
réduite à 𝑂(𝑚) lorsque le graphe G ne contient pas de circuits.

Les applications des problèmes des chemins optimaux sont nombreuses et diverses. Dans le domaine
des transports, par exemple, on s’intéresse aux chemins optimaux d’une ville 𝑥 à une autre ville 𝑦. Dans
le routage du trafic réseau, on parle des protocoles OSPF (open shortest path first).

5.2. Algorithme de DIJKSTRA

Il fait partie des algorithmes à fixation d’étiquettes et ne peut être appliqué que pour les graphes à
valuations positives. L’algorithme fixe l’étiquette de chaque sommet x à chaque itération en mettant à
jour un tableau de booléens.

Lors de sa phase d’initialisation, l’algorithme initialise un tableau V à ∞, P à zéros et D à faux. Pour un

sommet donné s, on initialise V[s] à zéro et P[s] à s. L’itération principale de l’algorithme est constituée
de deux boucles. La première consiste à trouver un sommet non encore fixé de l’ensemble V qui est
minimal. Pour cela, la valeur ∞ est d’abord affectée à Vmin, ensuite pour tout y allant de 1 à 𝑛 dont D[y]
est faux et V[y] strictement inférieure à la valeur Vmin, l’algorithme conserve y dans une variable x et
affecte V[y] à Vmin. Dans le cas où Vmin n’est pas ∞, D[x] est remplacé par vrai. La seconde boucle
consiste à parcourir tous les sommets k successeurs de x pour mettre à jour la liste des successeurs. Si
V[x] +W[k] est inférieur à V[y] alors V[x] + W[k] est affectée à V[y]. Finalement, x est affecté à P[y].

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 50

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Algorithme de Dijkstra
s : sommet de départ
Initialiser le tableau V à +∞ //Valeur des plus court chemins
Initialiser le tableau P à 0 //Détail des chemins (Path)
V[s]=O
P[s]=s
Répéter
// Chercher sommet non fixé de V minimal
Vmin=+
Pour i=1 à n faire
Si (i non fixé et V[i]<Vmin) alors x=i; Vmin=V[i] fsi
Finpour
Si Vmin<+
Fixer x
// Mise à jour des successeurs
Pour chaque successeur y de x faire
Si V[x]+W[x][y] < V[y]
V[y] = V[x]+W[x][y];
P[y] = x
Fsi
Finpour
Fsi
Jusqu’à Vmin=+

La complexité de l’algorithme de Dijkstra dans le pire des cas est 𝑂(𝑛²). Elle peut être améliorée en
O(nlogn) en utilisant un tas pour représenter le tableau V.

Exemple : Soit le graphe orienté valué représenté par la figure suivante. Dérouler l’algorithme de
Dijkstra en prenant comme sommet de départ 1.

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 51

UEF212 - Algorithmique et Complexité 2ème Année Tronc Commun Ingénieur en Informatique - S3

Tableau V (Values)
Sommets
1 2 3 4 5 6
Marqués
0 ∞ ∞ ∞ ∞ ∞ 1
4 1 2 ∞ ∞ 3
4 2 5 7 4
4 5 7 2
5 7 5
6 6
Résultat
0 4 1 2 5 6
Final

Tableau P (Paths)
1 2 3 4 5 6
1 0 0 0 0 0
1 1 1 3 3
5

On en déduit que les chemins optimaux à partir du sommet 1 sont :

1→1 0
1→2 4
1→3 1
1→4 2
1→3→5 5
1→3→5→6 6

USTO MB – Faculté des Mathématiques & Informatique, Département Informatique 52