Complexité : Analyse des algorithmes

2AP ENSAT

1
Table de contenu
Introduction
Complexité
Notations Bachmann-Landau (1894) : Big notation
Algorithmes de tri
Algorithmes de recherche

2
Introduction
Algorithmes : Séquence d'instructions pour résoudre un problème
Entrées
Sorties
Instructions
Afin de résoudre un problème donnée, plusieurs algorithmes peuvent être envisagés
C'est quoi le bon algorithme à choisir ?

3
Complexité
Comparer deux algorithmes qui font le même traitement
Sur un même environnement:
langage de programmation
interpréteur/compilateur
ordinateur (capacité physique et système d'exploitation)
Mesurer la performance des deux algorithmes: temps

4
Définition de la complexité
La complexité d'un algorithme est la mesure du nombre d'opérations fondamentales
qu'il effectue sur un jeu de données.
Elle est exprimée comme une fonction qui dépend de la taille du jeu de données.
La complexité algorithmique est une évaluation asymptotique du nombre d’opérations
élémentaires.

5
Type de complexité
Complexité au meilleur : C'est le plus petit nombre d'opérations qu'aura à exécuter
l'algorithme sur des jeux de données de taille n (Best case scenario).
Complexité moyenne : C'est la moyenne de Complexité de l'algorithme sur les différents
jeux de données (Average case).
Complexité au pire : C’est le plus grand nombre d'opérations qu'aura à exécuter l'algorithme
sur des jeux de données de taille n (Worst case scenario).

6
Exemple : Chercher un élément dans une liste
Soit une liste:
liste = [1,2,3,4]

taille_liste = 4

element_a_chercher = x

Nous allons rédiger un programme chercher_element_liste(liste,element_a_chercher) :

envoie la position de element_a_chercher dans liste

7
 Le pseudo pour le programme chercher_element_liste()
ALGORITHME rechercheLineaire(tableau, x)
POUR i de 0 A longueur(tableau)
SI tableau[i] = x ALORS
RETOURNE i
FIN SI
FIN POUR

RETOURNE -1

FIN ALGORITHME

8
 liste = [1,2,3,4]
Meilleur scénario: element_a_chercher = 1
nombre d'opérations : 1
Pire scénario: element_a_chercher = 4
nombre d'opérations : 4
Les autres scénarios:
element_a_chercher = 2 -> 2

element_a_chercher = 3 -> 3

Moyenne des opérations est :

9
Notations Bachmann-Landau (1894) : Big notation
Les notations Bachmann-Landau (communément connu avec les notations ) sont
les mesures utilisées pour expliquer les performances d'un algorithme.
Dans la suite indique une constante positive
ssi pour tout
ssi pour tout
ssi pour tout
En informatique, on s'intéresse généralement à la borne supérieure
La notation s'appelle Big O notation
10
Les règles de la notation
Les termes constants :
Les constantes multiplicatives sont omises :
L'addition est réalisée en prenant le maximum :
La multiplication reste inchangée :

11
Les classes de complexité
La performance des algorithmes pourra appartenir à ces classes de complexité
Constante :
Logarithme :
Linéaire :
Quasilinéaire:

12
Quadratique :
Cubique :
Polynomiale : avec
Exponentielle : avec
Factorielle:

13
Comparaison des classes de complexité
n! 2ⁿ n² n log₂n n
100
90

80
70

60
N
50

40
30

20
√n
10
1 log₂n
0
0 10 20 30 40 50 60 70 80 90 100
14
n
Algorithmes de tri
Problème de tri
Le "tri" est l'opération qui consiste à ordonner un ensemble d'éléments.
Algorithme tri :
Entrée: Un tableau d’entiers de taille N
Sortie: Le même tableau, trié par ordre croissant

15
Tri par sélection
Le tri par sélection est un algorithme de tri basé sur la comparaison. Il trie un tableau en
sélectionnant à plusieurs reprises le plus petit (ou le plus grand) élément de la partie non
triée et en l'échangeant avec le premier élément non trié. Ce processus se poursuit jusqu'à ce
que l'ensemble du tableau soit trié.
1. Nous trouvons d'abord le plus petit élément et l'échangeons avec le premier élément.
De cette façon, nous obtenons le plus petit élément à sa position correcte.
2. Ensuite, nous trouvons le plus petit parmi les éléments restants (ou le deuxième plus
petit) et le déplaçons vers sa position correcte en l'échangeant.
3. Nous continuons ainsi jusqu’à ce que tous les éléments soient déplacés vers la bonne
position.
16
0 1 2 3 4 5 6
14 34 10 2 15 8 33
0 1 2 3 4 5 6
2 34 10 14 15 8 33
0 1 2 3 4 5 6
2 34 10 14 15 8 33
0 1 2 3 4 5 6
2 8 10 14 15 34 33
17
Pseudo-code de l'algorithme : tri par sélection
ALGORITHME TriParSelection(tableau)
POUR i DE 0 À longueur(tableau) - 2
minIndex ← i
POUR j DE i + 1 À longueur(tableau) - 1
SI tableau[j] < tableau[minIndex] ALORS
minIndex ← j
FIN SI
FIN POUR
ÉCHANGER tableau[i] ET tableau[minIndex]
FIN POUR
FIN ALGORITHME

18
Complexité: Tri par sélection
Temps moyen :
Temps pire cas :
Temps meilleur cas : (même si les données sont déjà triées)

19
Tri par insertion
Le tri par insertion est un algorithme de tri qui fonctionne en insérant de manière itérative
chaque élément d'une liste non triée à sa position correcte dans une partie triée de la liste.
C'est comme trier des cartes à jouer dans vos mains. Vous divisez les cartes en deux groupes
: les cartes triées et les cartes non triées. Ensuite, vous choisissez une carte du groupe non
trié et la placez au bon endroit dans le groupe trié.
1. Nous commençons par le deuxième élément du tableau car le premier élément du
tableau est supposé être trié.
2. Comparez le deuxième élément avec le premier élément et vérifiez si le deuxième
élément est plus petit, puis échangez-les.
3. Passez au troisième élément et comparez-le aux deux premiers éléments et placez-le
à sa position correcte.
4. Répétez jusqu’à ce que l’ensemble du tableau soit trié.
20
0 1 2 3 4 5 6
14 34 10 2 15 8 33
0 1 2 3 4 5 6
14 34 10 2 15 8 33
0 1 2 3 4 5 6
10 14 34 2 15 8 33
0 1 2 3 4 5 6
10 14 34 2 15 8 33
21
Pseudo-code de l'algorithme: tri par insertion
ALGORITHME TriParInsertion(tableau)
POUR i DE 1 À longueur(tableau) - 1
clé ← tableau[i]
j ← i - 1
TANT QUE j ≥ 0 ET tableau[j] > clé FAIRE
tableau[j + 1] ← tableau[j]
j ← j - 1
FIN TANT QUE
tableau[j + 1] ← clé
FIN POUR
FIN ALGORITHME

22
Complexité: Tri par insertion
Temps moyen :
Temps pire cas :
Temps meilleur cas : (dans le cas ou la liste est déjà triées)

23
Tri à bulles
Le tri à bulles fonctionne en échangeant à plusieurs reprises les éléments adjacents s'ils ne
sont pas dans le bon ordre. Cet algorithme n'est pas adapté aux grands ensembles de
données car sa complexité temporelle moyenne et dans le pire des cas est assez élevée.
1. Nous trions le tableau en utilisant plusieurs passes. Après le premier passage,
l'élément maximal va à la fin (sa position correcte). De la même manière, après le
deuxième passage, le deuxième élément le plus grand va à l'avant-dernière position et
ainsi de suite.
2. À chaque passage, nous traitons uniquement les éléments qui n'ont pas encore été
déplacés vers la position correcte.
3. Après k passages, les k éléments les plus grands doivent avoir été déplacés vers les k
dernières positions.
Lors d'un passage, nous considérons les éléments restants et comparons tous les éléments
adjacents et les échangeons si l'élément le plus grand est avant un élément plus petit. Si nous
continuons ainsi, nous obtenons le plus grand (parmi les éléments restants) à sa position 24
correcte.
0 1 2 3 4 5 6
14 34 10 2 15 8 33
0 1 2 3 4 5 6
14 34 10 2 15 8 33
0 1 2 3 4 5 6
14 10 34 2 15 8 33
0 1 2 3 4 5 6
14 10 2 34 15 8 33
25
0 1 2 3 4 5 6
14 10 2 15 34 8 33
0 1 2 3 4 5 6
14 10 2 15 8 34 33
0 1 2 3 4 5 6
14 10 2 15 8 33 34

26
Pseudo-code de l'algorithme: tri à bulles
ALGORITHME TriABulles(tableau)
POUR i DE 0 À longueur(tableau) - 2
POUR j DE 0 À longueur(tableau) - i - 2
SI tableau[j] > tableau[j + 1] ALORS
ÉCHANGER tableau[j] ET tableau[j + 1]
FIN SI
FIN POUR
FIN POUR
FIN ALGORITHME

27
Complexité: Tri à bulles
Temps moyen :
Temps pire cas :
Temps meilleur cas : (dans le cas ou la liste est déjà triées)

28
Tri par fusion
Le tri par fusion est un algorithme de tri qui suit l'approche diviser pour régner . Il fonctionne
en divisant de manière récursive le tableau d'entrée en sous-tableaux plus petits et en triant
ces sous-tableaux, puis en les fusionnant à nouveau pour obtenir le tableau trié.
En d'autres termes , nous pouvons dire que le processus de tri par fusion consiste à diviser le
tableau en deux moitiés, à trier chaque moitié, puis à fusionner les moitiés triées ensemble.
Ce processus est répété jusqu'à ce que le tableau entier soit trié.

29
 0 1 2 3 4 5 6
14 34 10 2 15 8 33
0 1 2 3 0 1 2
14 34 10 2 15 8 33
0 1 0 1 0 1 0
14 34 10 2 15 8 33
0 0 0 0 0 0 0
14 34 10 2 15 8 33
30
0 1 0 1 0 1 0
14 34 2 10 8 15 33
0 1 2 3 0 1 2
2 10 14 34 8 15 33
0 1 2 3 4 5 6
2 8 10 14 15 33 34

31
Pseudo-code de l'algorithme: tri par fusion
ALGORITHME TriParFusion(tableau)
SI longueur(tableau) > 1 ALORS
milieu ← longueur(tableau) / 2
gauche ← sousTableau(tableau, 0, milieu - 1)
droite ← sousTableau(tableau, milieu, longueur(tableau) - 1)
TriParFusion(gauche)
TriParFusion(droite)
Fusion(tableau, gauche, droite)
FIN SI
FIN ALGORITHME

ALGORITHME Fusion(tableau, gauche, droite)

i ← 0, j ← 0, k ← 0
TANT QUE i < longueur(gauche) ET j < longueur(droite) FAIRE
SI gauche[i] ≤ droite[j] ALORS
tableau[k] ← gauche[i]
i ← i + 1
SINON
tableau[k] ← droite[j]
j ← j + 1
FIN SI
k ← k + 1
FIN TANT QUE
TANT QUE i < longueur(gauche) FAIRE
tableau[k] ← gauche[i]
i ← i + 1
k ← k + 1
FIN TANT QUE
TANT QUE j < longueur(droite) FAIRE
tableau[k] ← droite[j]
j ← j + 1
k ← k + 1
FIN TANT QUE
FIN ALGORITHME

32
Complexité: Tri par fusion
Temps moyen :
Temps pire cas :
Temps meilleur cas :

33
Tri rapide
Le tri rapide fonctionne sur le principe de diviser pour régner, en décomposant le problème
en sous-problèmes plus petits.
L'algorithme se compose principalement de trois étapes :
1. Choisir un pivot : sélectionnez un élément du tableau comme pivot. Le choix du pivot
peut varier (par exemple, premier élément, dernier élément, élément aléatoire ou
médiane).
2. Partitionner le tableau : Réorganiser le tableau autour du pivot. Après partitionnement,
tous les éléments plus petits que le pivot seront à sa gauche, et tous les éléments plus
grands que le pivot seront à sa droite. Le pivot est alors à sa position correcte, et nous
obtenons l'indice du pivot.
3. Appel récursif : appliquez de manière récursive le même processus aux deux sous-
tableaux partitionnés (à gauche et à droite du pivot).
Cas de base : la récursivité s'arrête lorsqu'il ne reste qu'un seul élément dans le sous- 34
tableau, car un seul élément est déjà trié.
0 1 2 3 4 5 6
14 34 10 2 15 8 33
0 1 2 3 4 5 6
10 2 8 14 34 15 33
0 1 2 3 4 5 6
10 2 8 14 34 15 33
0 1 2 3 4 5 6
2 8 10 14 15 33 34
35
Pseudo-code de l'algorithme: tri rapide
ALGORITHME TriRapide(tableau, début, fin)
SI début < fin ALORS
pivot ← Partition(tableau, début, fin)
TriRapide(tableau, début, pivot - 1)
TriRapide(tableau, pivot + 1, fin)
FIN SI
FIN ALGORITHME

ALGORITHME Partition(tableau, début, fin)

pivot ← tableau[fin]
i ← début - 1
POUR j DE début À fin - 1
SI tableau[j] ≤ pivot ALORS
i ← i + 1
ÉCHANGER tableau[i] ET tableau[j]
FIN SI
FIN POUR
ÉCHANGER tableau[i + 1] ET tableau[fin]
RETOURNER i + 1
FIN ALGORITHME

36
Complexité: Tri rapide
Temps moyen :
Temps pire cas :
Temps meilleur cas :

37
Algorithmes de recherche
Les algorithmes de recherche sont des outils essentiels en informatique utilisés pour
localiser des éléments spécifiques dans un ensemble de données.

38
Algorithmes de recherche linéaire
Dans la recherche linéaire, nous parcourons tous les éléments du tableau et vérifions si
l'élément actuel est égal à l'élément cible. Si nous trouvons un élément égal à l'élément cible,
nous renvoyons l'index de l'élément actuel. Sinon, si aucun élément n'est égal à l'élément
cible, nous renvoyons -1 car l'élément n'est pas trouvé. La recherche linéaire est également
connue sous le nom de recherche séquentielle.

39
Pseudo-code de l'algorithme: Recherche linéaire
ALGORITHME rechercheLineaire(tableau, x)
POUR i de 0 A longueur(tableau)
SI tableau[i] = x ALORS
RETOURNE i
FIN SI
FIN POUR

RETOURNE -1

FIN ALGORITHME

40
Complexité: Recherche linéaire
Temps moyen :
Temps pire cas :
Temps meilleur cas :

41
Algorithmes de recherche dichotomique
L'algorithme de recherche binaire est un algorithme de recherche utilisé dans un tableau trié
en divisant de manière répétée l'intervalle de recherche par deux. L'idée de la recherche
binaire est d'utiliser les informations selon lesquelles le tableau est trié et de réduire la
complexité temporelle à .

42
ALGORITHME rechercheBinaire(tableau, x)
bas <- 0
haut <- longueur(tableau)

TANT QUE bas <= haut:

milieu <- (haut - bas) // 2

IF tableau[milieu] == x ALORS
RETOURNE milieu
FIN IF

IF tableau[milieu] < x ALORS

bas <- milieu + 1
FIN IF

IF tableau[milieu] > x ALORS

haut <- milieu - 1

RETOURNE -1

FIN ALGORITHME

43
Complexité: Recherche binaire
Temps moyen :
Temps pire cas :
Temps meilleur cas :

44
45