Séance 1 : Complexité et optimalité
Enseignante: Jamila Sassi
Matière: Complexité appliqué à la RO
Année universitaire :2025/2026
1. Déroulement
1 2 3 4 5 6 7
Cours intégré : Application
- Partie itérative
- Partie récursive
Evaluation écrite
2
1. Déroulement
5 6 7
Présentation par Solution individuelle Calcul de complexité
groupe:
Problématique Limite de la méthode utilisée
Comparaison des solutions
proposées entre les membres de
groupe
3
Complexité algorithmique: Motivation
Pour un problème donné, il existe souvent plusieurs algorithmes.
La question la plus fréquente que se pose à chaque programmeur est la suivante:
Comment peut on désigner le meilleur code parmi les solutions proposées ?
Le code le plus courts: est-il meilleur ?
4
Qualité d’un bon algorithme
Un bon algorithme doit satisfaire les qualités suivantes:
Correct: Il faut que le programme exécute correctement les tâches pour lesquelles il a été conçu
Complet: Il faut que le programme considère tous les cas possibles et donne un résultat dans chaque cas.
Efficace: Il faut que le programme exécute sa tâche avec efficacité c’est à dire avec un coût minimal. Le
coût pour un ordinateur se mesure en termes de temps de calcul et d’espace mémoire nécessaire.
5
Complexité algorithmique
La complexité algorithmique est une métrique (mesure) de l’efficacité d’un algorithme indépendamment
de l’environnement (machine, système, compilateur, …). Elle consiste en l’étude formellement de la
quantité de ressources ( de temps ou d’espace) nécessaire l'exécution de cet algorithme.
La complexité temporelle d’un algorithme La complexité spatiale d’un algorithme quantifie la
quantifie le temps nécessaire à un algorithme quantité d’espace ou de mémoire prise par un
pour s’exécuter en fonction de la longueur algorithme pour s’exécuter en fonction de la longueur
d’entrée d’entrée (Allocation dynamique)
6
Règles de Calcul de la complexité
Pour calculer la complexité temporelle, il faut compter le nombre d’opérations de base qu’il effectue
en examinant chaque ligne de code.
Pour simplifier le calcul de le complexité temporelle, on va faire l'hypothèse que toutes les opérations
élémentaires ont un coût uniforme soit 1 « unité » de temps.
La complexité de
chaque opération
élémentaire est
constante ou 1
« unité » de temps
a🡨 1
Exemple: b🡨 5 T(n)=4 « unité » de temps.
T(n)=?
7
c🡨 a+b
Notation de LANDAU
La notation de LANDAU « O » est celle qui est le plus communément utilisée pour expliquer
formellement les performances d’un algorithme.
Cette notation donne une borne supérieure de la complexité pour toutes les données de même taille
8
Exemple
9
Règles de Calcul de la complexité
La complexité de la structure si/sinon correspond à la complexité de la condition plus la complexité la
plus grande entre si et sinon.
Exemple:
Vérification d’une condition: 1
Si <condition Tc(n)> alors Si n< 5 alors « unité » de temps
Traitement 1 T1(n) Ecrire(" RO complexite " ); Ecriture: 1 « unité » de temps
Sinon sinon
Traitement 2 T2(n) Ecrire(" RO complexite " ); Ecriture : 1 « unité » de temps
🡺 T(n) =Tc(n) + max(T1(n),T2(n) Ecrire(" RO complexite " );
Ecriture: 1 « unité » de temps
Finsi
🡺 La complexité de l’exemple ci-dessus est: 1 + Max(1, 2) 2+1 3
Exemple:
a🡨 1
Si (a>0)
a🡨 a+1 //2 opérations T(n)=1+(1+Max(4,1))=6 « unité » de temps.
T(n)=?
b🡨 a*2 //2 opérations
Sinon
a🡨 0 10
Règles de Calcul de la complexité
La complexité d’une boucle est la complexité du bloc interne dans la boucle multipliée par le nombre
de fois que le bloc interne est répété.
Dans une boucle, on néglige le temps de l’incrémentation du compteur devant celui des instructions du
corps de la boucle.
Exemple:
pour i de k à n faire (pas=1) pour i de 1 à n faire (pas=1)
Traitement i Ti(n) Ecrire(" entrer un nombre a" ); Ecriture: 1 « unité » de temps
finpour Lire(a) Lecture : 1 « unité » de temps
Ecrire(" i*a= " ,i*a); Ecriture: 1 « unité » de temps *n
Fin pour Opération arithmétique: 1
« unité » de temps
🡺 La complexité de l’exemple ci-dessus est: 4n « unité » de temps
Exemple:
somme🡨 0
Pour i de 1 à n faire T(n)=1+(3*n)=3n+1
T(n)=? « unité » de temps
somme🡨 somme+i*i
finpour 11
Règles de Calcul de la complexité
Règles de Calcul de la complexité
Classes de complexité
14
Exponentielle an
n3
Quadratique
n2
T(n)
[Link](n)
Log(n)
15
log2(n) n nlog2(n) n2 n3 n4 exp(n)
1 0,00 1 0,00 1 1 1 3
2 1,00 2 2,00 4 8 16 7
3 1,58 3 4,75 9 27 81 20
4 2,00 4 8,00 16 64 256 55
5 2,32 5 11,61 25 125 625 148
6 2,58 6 15,51 36 216 1296 403
7 2,81 7 19,65 49 343 2401 1097
8 3,00 8 24,00 64 512 4096 2981
9 3,17 9 28,53 81 729 6561 8103
10 3,32 10 33,22 100 1000 10000 22026
11 3,46 11 38,05 121 1331 14641 59874
12 3,58 12 43,02 144 1728 20736 162755
13 3,70 13 48,11 169 2197 28561 442413
14 3,81 14 53,30 196 2744 38416 1202604
15 3,91 15 58,60 225 3375 50625 3269017
16 4,00 16 64,00 256 4096 65536 8886111
17 4,09 17 69,49 289 4913 83521 24154953
18 4,17 18 75,06 324 5832 104976 65659969
19 4,25 19 80,71 361 6859 130321 178482301
20 4,32 20 86,44 400 8000 160000 485165195
16
Les types de complexité
Il existe trois types de complexité:
Nous notons Dn l’ensemble des données de taille n et T(n) le nombre d’opérations sur un jeu de donnée de taille n.
Un algorithme est dit optimal si sa complexité est la complexité minimale parmi les algorithmes de sa classe.
Exemple 3 : recherche d’un élément
dans un tableau
1 9 8 … 100 20
Case 0 Case N-1
Si j’ai de la chance :
-x se trouve dans la première case : 1 seule comparaison
Chercher l’élément x dans le tableau
Complexité au meilleure
Algo 1
Si je n’ai pas de chance :
for(i=0;i<N;i++)
-x se trouve dans la dernière case : N comparaisons
comparaison
- x ne se trouve pas dans le tableau : N comparaisons
Complexité au pire
Complexité au moyenne : N/2 Comparaisons
18
• Séquences itératives
• Blackboard
19
Exemple 4 : tableau est ordonné
1 8 9 … 20 100
Case 0 Case N-1
Algo 1 Algo 2
Chercher l’élément x dans le tableau N=100 100 7
Algo 2 : recherche dichotomique N=200 200 8
N=100 : N=400 400 9
50, 25, 12, 6, 3, 2, 1
N=800 800 10
Exponentielle
T(n) N=1600 1600 11
n N=3200 3200 12
Log(n) N=6400 6400 13
n 20
Classes de complexité
• Les algorithmes usuels peuvent être classés en un certain nombre de grandes classes de
complexité :
• O(logn) : Les algorithmes sub-linéaires dont la complexité est en général en O(logn).
• O(n) : Les algorithmes linéaires en complexité O(n)
• O(nlogn) : et ceux en complexité en O(nlogn)
• O(nk) : Les algorithmes polynomiaux en O(nk) pour k > 3
• Exp(n) : Les algorithmes exponentiels
• Les trois premières classes sont considérées rapides alors que la quatrième est
considérée lente et la cinquième classe est considérée impraticable.
21
Exercice
• 3log(n)= O(log(n))
• 100n= O(n)
• 1000n2+5n3= O(n3)
• 10000n8+10n9= O(n9)
• n+nlog(n)= O(nlog(n))
• n5+2n= O(2n)
• n2+100000= O(n2)
22
Conclusion
• Existence de plusieurs solutions pour un problème donné
• Ces solutions peuvent être correctes mais n’ont pas la même
efficacité (coût)
• Avant de proposer un algorithme, il faut estimer son coût
• Et se poser la question de l’existence d’une autre solution moins
coûteuse
23
Complexité de séquences itératives
Exercice 2: Déterminer (en fonction de n à O( ) près) la complexité en nombre « d’opérations » de
chaque séquence
Séquence-1 :
For i = 1 to N do Nombre d’exécution de l’opération: n fois
Opération ;
Endfor La complexité est 𝑂(𝑛)
Complexité de séquences itératives
Exercice 2: Déterminer (en fonction de n à O( ) près) la complexité en nombre « d’opérations » de
chaque séquence
Séquence-2 :
For i = 1 to N do Nombre d’exécution de l’opération: n*n fois
For j = 1 to i do
Opération ;
Endfor La complexité est 𝑂(𝑛2 )
Endfor
Complexité de séquences itératives
Exercice 2: Déterminer (en fonction de n à O( ) près) la complexité en nombre « d’opérations » de
chaque séquence
N=2=21 ->1 opération
N=4=22 ->2 opérations 𝑁 = 2𝑎
Séquence-3 :
N=8=23 ->3 opérations a: nombre d’opérations
i=1; 𝑎 = 𝑙𝑜𝑔2 (𝑁)
While ( i < N) Do N=16=24 ->4 opérations
i = 2*i; N=32=25 ->5 opérations
La complexité est 𝑂(𝑙𝑜𝑔2 (𝑛))
Opération ; N=64=26 ->6 opérations
Endwhile
Opérations
N
Complexité de séquences itératives
Exercice 2: Déterminer (en fonction de n à O( ) près) la complexité en nombre « d’opérations » de
chaque séquence
Séquence-4 :
For i = 1 To N Do
J=1;
While (J < N ) Do
J = 2 * J;
𝑂(𝑙𝑜𝑔2 (𝑛))
Opération;
Endwhile
Endfor 𝑂(𝑛𝑙𝑜𝑔2 (𝑛))