Royaume du Maroc
Université Cadi Ayyad
Faculté des Sciences Semlalia
Marrakech
Algorithmique II
Pr. Ilyass OUAZZANI TAYBI
E-mail : [Link]@[Link]
Département : Informatique FSSM
Université Cadi Ayyad
Filière TC-INFO S2
Année universitaire : 2024/2025
Plan du cours
❑ Rappel (Algorithmique I)
❑ Tableaux
❑ Fonctions et procédures
❑ Récursivité
❑ Algorithmes de tri
❑ Pointeurs et Enregistrements
❑ Fichiers
❑ Complexité algorithmique
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 2
Plan du cours
CHAPITRE 7 : COMPLEXITÉ ET PREUVES D’ALGORITHMES
[Link]
[Link]é
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 3
VII. Complexité
1. Introduction
➢ Lors de l’exécution d’un algorithme, quelles que soient les données, les trois questions
suivantes se posent :
1. Se termine-t-il ? (La terminaison de l’algorithme)
2. Résout-il correctement le problème posé ? (La correction de l’algorithme)
3. Suivant la taille des données, en combien de temps et avec quelle quantité de mémoire
l'algorithme se termine-t-il ? (La complexité temporelle et spatiale de l’algorithme)
4
VII. Complexité
2. Complexité
➢ Imaginez par exemple qu'après avoir lancé une requête sur un moteur de recherche, il faille
attendre plusieurs heures pour avoir le résultat! Les moteurs de recherche n'auraient pas
autant de succès.
➢ Un algorithme doit déjà être correct (preuve de la correction), c'est-à-dire faire ce qu'il est
supposé faire! Mais il doit aussi être efficace, c'est-à-dire donner “rapidement” la réponse.
➢ Plusieurs algorithmes permettent de résoudre un même problème.
➢ Par exemple : Pour trier les éléments d'un tableau, il y a différents algorithmes :
➢ tri par sélection,
➢ tri par insertion,
➢ tri par fusion
➢ … 5
VII. Complexité
2. Complexité
➢ Evaluer l'efficacité spatiale d'un algorithme, cela consiste à déterminer la quantité maximale
de mémoire (RAM) nécessaire à l'exécution de l'algorithme. Plus cette quantité de mémoire
est réduite, plus l'efficacité spatiale de l'algorithme est élevée.
➢ Evaluer l'efficacité temporelle d'un algorithme, cela consiste à évaluer la durée nécessaire à
l'exécution de l'algorithme. Plus cette durée est courte, plus l'efficacité temporelle de
l'algorithme est élevée.
➢ Dans la suite de ce chapitre nous nous intéresserons uniquement à l'efficacité temporelle
(complexité temporelle) d'un algorithme. En fait, les mêmes notions permettent de traiter la
complexité spatiale.
6
VII. Complexité
2. Complexité
La durée d'exécution
➢ La première impression consiste souvent à mesurer l'efficacité temporelle d'un algorithme en
évaluant le temps nécessaire à l'exécution d'un programme qui met en œuvre cet algorithme.
Cependant, de nombreux critères entrent en jeu. Par exemple:
➢ Le langage de programmation utilisé pour traduire l'algorithme;
➢ Le processeur et le type de mémoire de l'ordinateur utilisé;
➢ Les autres programmes s'exécutant sur l'ordinateur (qui peuvent ralentir le programme
testé);
➢ …
➢ La durée d'exécution permet de comparer l'efficacité de deux algorithmes traduits dans le
même langage et exécutés sur le même ordinateur, mais ne permet pas d'évaluer l'efficacité
intrinsèque d'un algorithme.
7
VII. Complexité
2. Complexité
Coût d'un algorithme
➢ La seconde (et la bonne) idée pour évaluer l'efficacité temporelle d'un algorithme est de
compter le nombre d'opérations élémentaires effectuées par cet algorithme lors de son
exécution.
➢ Le coût d'un algorithme est le nombre d'opérations élémentaires effectuées par cet
algorithme.
➢ On appelle opération élémentaire l'une des actions suivantes :
➢ Faire une opération mathématique de base (addition, soustraction, multiplication, division)
➢ Lire la valeur d’une variable
➢ Affecter une valeur à une variable
➢ Effectuer un test
➢ Faire une opération booléenne (“et”, “ou”, “non”)
➢ … 8
VII. Complexité
2. Complexité
Exemple :
Fonction somme (n: Entier): Entier
Variables total : Entier
Cette fonction (qui calcule la somme des entiers de 1
Début
à n) fait:
total 0;
• 2n opérations mathématiques
Tant que n > 0 Faire
• 4n + 1 lectures
total total + n;
• 2n + 1 affectations
n n – 1,
• n+1 comparaisons
FinTantQue
Le coût est de 9n + 3 opérations élémentaires
Retourner total;
FinFonction
9
VII. Complexité
2. Complexité
➢ Remarquons que:
• Parmi ces opérations certaines prennent en pratique plus de temps que d'autres.
• Pour une même opération, le temps d'exécution est proportionnel à la taille des données
(pour la multiplication des entiers, par exemple).
➢ On fait alors les hypothèses suivantes pour ne pas rendre les calculs compliqués:
• Nous ferons l'approximation que toutes ces opérations élémentaires prennent le même
temps.
• Nous compterons souvent non pas toutes les opérations élémentaires, mais seulement
une partie d'entre elles, suivant le type d'algorithme. Il faudra choisir les opérations
élémentaires les plus significatives de l'algorithme.
10
VII. Complexité
2. Complexité
La taille des données :
➢ La taille des données d'un algorithme est, en général, un entier n qui “mesure” les données à
traiter. Un algorithme est ici écrit comme une fonction, les données à traiter sont les
paramètres d'appels de cette fonction.
Objectif
➢ Nous chercherons à calculer le coût (ou plutôt la complexité, une estimation du coût) en
fonction de la taille des données.
11
VII. Complexité
2. Complexité
Estimation du coût d'un algorithme: la complexité :
➢ Calculer le coût exact d'un algorithme devient vite délicat, fastidieux et souvent impossible.
De plus, qu'il y ait 𝒏𝟐 ou 𝒏𝟐 + 𝟐𝒏 + 3 opérations élémentaires, c'est pareil ou presque pareil
lorsque 𝑛 est grand.
➢ Le rôle de la complexité est d'estimer, dans le cas le plus défavorable, un ordre de grandeur
du coût d'un algorithme en fonction de la taille n des données lorsque cette taille augmente
et tend vers l'infini.
➢ Nous sommes plus intéressés par un comportement asymptotique: que se passe-t'il quand la
taille des données tend vers l'infini ?
➢ Cette mesure d'efficacité est appelée: Complexité asymptotique.
12
VII. Complexité
2. Complexité
Exemple illustratif : 𝑓 𝑛 = 𝑛2 + 100𝑛 + 𝑙𝑜𝑔10 𝑛 + 1000
➢ La fonction f est composée de 4 termes : 𝑛2 , 100𝑛, 𝑙𝑜𝑔10 𝑛 , 𝑒𝑡 1000 .
➢ Analyser la contribution de chaque terme en fonction de n (taille de données) :
n f(n) 𝒏𝟐 𝟏𝟎𝟎𝒏 𝒍𝒐𝒈𝟏𝟎 𝒏 𝟏𝟎𝟎𝟎
valeur valeur % valeur % valeur % valeur %
1 1101 1 0,10 100 9,10 0 0,00 1000 90,82
10 2101 100 4,76 1000 47,6 1 0,05 1000 47,62
100 21002 10 000 47,6 10 000 47,6 2 0,99 1000 4,76
1000 1 101 003 1 000 000 90,8 100 000 9,10 3 0,00 1000 0,09
10 000 101 001 004 100 000 000 99,0 1 000 000 0,99 4 0,00 1000 0,00
100 000 10 010 001 005 10 000 000 000 99,9 10 000 000 0,09 5 0,00 1000 0,00
• Pour des valeurs importantes de n la fonction f(n) dépend principalement de son premier
terme 𝑛2 . Les autres termes peuvent être ignorés. 13
VII. Complexité
2. Complexité
Définition de la complexité d'un algorithme :
➢ Soit A un algorithme et 𝑛 une donnée d'entrée de A. On appelle complexité de A pour 𝑛,
notée CA(𝑛), le nombre d'opérations élémentaires effectuées lors de l'exécution de A sur 𝑛.
➢ Le nombre d'opérations est exprimé en fonction de paramètres associés aux instances à
traiter.
➢ Exemple: la complexité d'un tri est en fonction du nombre de données à trier. La complexité
n'est pas la même avec deux jeux de données différents à savoir:
• rapide si des données sont déjà triées.
• moins rapide si les données sont désordonnées.
➢ Le rôle de la complexité est d'estimer, un ordre de grandeur du coût d'un algorithme en
fonction de la taille n des données lorsque cette taille augmente et tend vers l'infini.
14
VII. Complexité
2. Complexité
Types de complexité :
➢ La complexité dans le pire des cas : on considère le plus grand nombre d'opérations
élémentaires effectuées sur les données. C'est la mesure la plus utilisée.
➢ La complexité dans le meilleur des cas : on considère le plus petit nombre d'opérations
élémentaires effectuées sur les données.
➢ La complexité en moyenne : la moyenne des nombres d'opérations élémentaires effectuées
sur tous les jeux de données. Ce calcul est généralement difficile à formuler car il faut
connaitre la probabilité de chacun des jeux de données pour un calcul pertinent de cette
moyenne.
15
VII. Complexité
2. Complexité
Exemple :
Début Supposons que (avec t1, t2, t3, et t4 sont des
K ← 1; constantes) :
j ← 0; t1: temps d'exécution des instructions 1-2.
Tant Que j <= n FAIRE t2: temps d'exécution de l'instruction 3
r ← r + j; (comparaison).
j ← j + 1;
t3: temps d'exécution de l'instructions 4.
Fin Tant Que
t4: temps d'exécution de l'instructions 5.
FIN
• Le temps d'exécution : 𝑡 𝑛 = 𝑡1 + σ𝑛1 (𝑡2 + 𝑡3 + 𝑡4) + 𝑡2 = 𝑡1 + 𝐧 ∗ 𝐭𝟓 + 𝑡2 avec 𝑡5 = 𝑡2 + 𝑡3 + 𝑡4
• Le temps d'exécution dépend linéairement de la taille 𝑛.
• Comportement asymptotique: valeur de 𝑡(𝑛) quand 𝑛 tend vers l'infini est équivalente à 𝑛∗𝑡5
• La complexité de l'algorithme est donc asymptotiquement linéaire.
16
VII. Complexité
2. Complexité
Complexités usuelles :
• 𝑓 𝑛 =1 : l'algorithme a une complexité constante (rare et excellent)
• 𝑓 𝑛 = log(𝑛) : l'algorithme a une complexité logarithmique (excellent)
• 𝑓 𝑛 =𝑛 : l'algorithme a une complexité linéaire (très bon)
• 𝑓 𝑛 = 𝑛 ∗ log(𝑛) : l'algorithme a une complexité quasi linéaire (très bon)
• 𝑓 𝑛 = 𝑛2 : l'algorithme a une complexité quadratique (moyen)
• 𝑓 𝑛 = 𝑛3 : l'algorithme a une complexité cubique (mauvais)
• 𝑓 𝑛 = 𝑛𝑝 : l'algorithme a une complexité polynomiale (p > 3) (très mauvais)
• 𝑓 𝑛 = 𝑎𝑛 : l'algorithme a une complexité exponentielle (a > 1) (nul)
• 𝑓 𝑛 = 𝑛! : l'algorithme a une complexité factorielle (nul)
Plus la complexité est “élevée”, moins l'algorithme est efficace. En pratique, à partir d'une
complexité exponentielle, un algorithme n'est pas intéressant, à moins de ne pas en avoir un
autre pour résoudre le problème.
18
VII. Complexité
2. Complexité
Ordre de grandeur des temps d'exécution :
➢ On suppose que l'ordinateur effectue un milliard d'opérations élémentaires par seconde. On
donne le temps d'exécution T(n) en fonction de n suivant la complexité C(n) de l'algorithme.
❑ Ces tableaux parlent d'eux mêmes: un algorithme qui résout théoriquement un problème
mais qui ne donne jamais la réponse est une curiosité guère utile.
19
VII. Complexité
2. Complexité
Règles de calcul de la complexité (en pire des cas) :
➢ La complexité est évaluée en temps ou en nombre d'opérations d'un algorithme. Les règles
générales sont :
➢ Le temps d'exécution (TE) d'une opération élémentaire est considère comme constant.
➢ Le temps d'une séquence d'instructions = la somme de TE des instructions qui la
composent.
➢ Le temps d'un branchement conditionnel = TE du test + le max des deux TE correspondant
aux deux alternatives.
➢ Le temps d'une boucle = (le coût du test + le coût du corps de la boucle)*(nombre
d'itérations) + le test de la sortie de la boucle.
20
VII. Complexité
2. Complexité
Exemple 1 :
Algorithme avec une boucle.
Début • Soit Op(n) le nombre d'opérations élémentaires.
B ← 0; • 𝑂𝑝 𝑛 = 1 + 1 + σ𝑛𝑖=1 3 + 3 + 3 + 3
i ← 1; = 9𝑛 + 5
TantQue i <= n FAIRE ❑ On peut dire aussi que 𝑂𝑝 𝑛 = 𝑂 𝑛 .
B ← B + 2; L'algorithme a une complexité asymptotique
i ← i + 1;
linéaire.
FinTantQue
FIN
21
VII. Complexité
2. Complexité
Exemple 2 : Deux boucles imbriquées sans dépendance des indices.
Début Soit Op(n) le nombre d'opérations élémentaires.
B ← 0; // 1 op
i ← 1; // 1 op 𝑛 𝑛
TantQue i <= n FAIRE // 3 ops : lecture i et n, comparaison 𝑂𝑝 𝑛 = 1 + 1 + 3 + 3 + 1 + 3 + 3 + 5 + 3 + 3 + 3
B ← B + 2; // 3 ops 𝑖=1 𝑗=1
j ← 1; // 1 op = 11𝐧𝟐 + 13𝑛 + 5
TantQue j <= n FAIRE // 3 ops : lecture j et n, comparaison
T[i][j] ← (T[i][j] + 1) * B; // 5 ops : lecture T[i][j], +1, On peut dire aussi que 𝑂𝑝 𝑛 = 𝑂 𝑛2
// lecture B, *, affectation
j ← j + 1; // 3 ops : lecture j, +1, affectation
FinTantQue
L'algorithme a une complexité asymptotique
i ← i + 1; // 3 ops : lecture i, +1, affectation quadratique.
FinTantQue
FIN
22
VII. Complexité
2. Complexité
Exemple 3 : Deux boucles imbriquées avec dépendance des indices.
Début Soit Op(n) le nombre d'opérations élémentaires.
B ← 0; // 1 op 𝑛 𝑖
i ← 1; // 1 op 𝑂𝑝 𝑛 = 1 + 1 + 3 + 3 + 1 + 3 + 4 + 3 + 3 + 3 + 3
TantQue i <= n FAIRE // 3 ops 𝑖=1 𝑗=1
B ← B + 2; // 3 ops = 5 + σ𝑛𝑖=1 13 + σ𝑖𝑗=1 10
j ← 1; // 1 op
= 5 + 13𝑛 + σ𝑛𝑖=1 10𝑖
TantQue j <= i FAIRE // 3 ops
T[i][j] ← T[i][j] * B; // 4 ops = 5 + 13𝑛 + 10 σ𝑛𝑖=1 𝑖
𝑛 𝑛+1
j ← j + 1; // 3 ops = 5 + 13𝑛 + 10( )
2
FinTantQue = 5𝐧𝟐 + 18𝑛 + 5
i ← i + 1; // 3 ops
On peut dire aussi que 𝑂𝑝 𝑛 = 𝑂 𝑛2
FinTantQue
FIN L'algorithme a une complexité asymptotique quadratique.
23
VII. Complexité
2. Complexité
Exemple 4 :
Cas d’une fonction récursive Soit :
• c1: temps d'exécution pour le test
Fonction fact (n : Entier) : Entier
• c2: le temps d'exécution pour la multiplication.
Début
Si n = 0 alors
▪ T(n = 0) = c1
retourner 1; ▪ T(n = 1) = c1 + c2 + T(n = 0)
Sinon ▪ T(n = 2) = c1 + c2 + T(n = 1)
retourner n*fact (n-1); ▪ T(n) = c1 + c2 + T(n - 1)
Finsi ▪ T(n) = n*(c2 + c1) + c1
FinFonction ➢ Donc l'algorithme a une complexité asymptotique
linéaire O(n).
24
VII. Complexité
2. Complexité
Exercice 1 :
Déterminer la complexité asymptotique dans la notation Grand-O, pour chacun des fonctions
Ti(n) suivant. Exemple : T0(n) = 3n ∈ O(n).
➢ T1(n) = 6n3 + 10n2 + 5n + 2
➢ T2(n) = 3 log2 n + 4
➢ T3(n) = 2n + 6n2 + 7n
➢ T4(n) = 7k + 2
➢ T5(n) = 4 log2 n + n
➢ T6(n) = 2 log10 k + kn2
25
VII. Complexité
2. Complexité
Exercice 1 : Corrigé
Déterminer la complexité asymptotique dans la notation Grand-O, pour chacun des fonctions
Ti(n) suivant. Exemple : T0(n) = 3n ∈ O(n).
➢ T1(n) = 6n3 + 10n2 + 5n + 2 ∈ O(n3)
➢ T2(n) = 3 log2 n + 4 ∈ O(log n)
➢ T3(n) = 2n + 6n2 + 7n ∈ O(2n) ∈ O(an)
➢ T4(n) = 7k + 2 ∈ O(1)
➢ T5(n) = 4 log2 n + n ∈ O(n)
➢ T6(n) = 2 log10 k + kn2 ∈ O(n2)
26
Merci de votre
attention
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 27
Royaume du Maroc
Université Cadi Ayyad
Faculté des Sciences Semlalia
Marrakech
Algorithmique II
Pr. Ilyass OUAZZANI TAYBI
E-mail : [Link]@[Link]
Département : Informatique FSSM
Université Cadi Ayyad
Filière TC-INFO S2
Année universitaire : 2024/2025
