Complexité
Objectifs
Comment comparer des algorithmes ?
- Différencier complexité en temps et en espace
- Estimer la complexité d'un algorithme
Cours
Complexité
Algorithmique et programmation avancéeRecettes pour une omelette
Complexité algorithmique
Mesurer l'efficacité d'un algorithme
En temps (opérations effectuées)
1 opération = 1 unité de temps
1 opération = 1 comparaison, 1 addition, 1 affectation, ou …
En espace (espaces dans la mémoire utilisés)
1 variable = 1 espace
1 liste de n élément = n espaces
Notation grand O de Landau
Ordre de grandeur selon des entrées possibles
Multiplication
FONCTION mult(a, b)
RETOURNER a*b
FIN FONCTION
Instance : a=3, b=4
Opérations
2 (mult. + retour)
Espaces
2 (variables a et b)
Instance : a=2048, b=130
Opérations
2
Espaces
2
Complexité temporelle : constante O(1)
Complexité spatiale : constante O(1)
Multiplication
FONCTION mult(a, b)
r ← 0
POUR i DE 1 À b FAIRE
r ← r + a
FIN POUR
RETOURNER r
FIN FONCTION
Instance : a=3, b=4
Opérations
4 (assign. + add.)
Espaces
4 (var. a, b, r, i)
Instance : a=2048, b=130
Opérations
130
Espaces
4
Complexité temporelle : linéaire O(b) ou O(n)
Complexité spatiale : constante O(1)
Grand O de Landau
O(1) : Constant (min, max)
O(log(n)) : Logarithmique (recherche dichotomique)
O(n) : Linéaire (recherche dans liste)
O(n log(n)) : Log-linéaire (tri fusion)
O(n2) : Quadratique (tri par insertion/sélection)
2O(n) : Exponentiel
O(n!) : Factorielle
n | O(1) | O(n) | O(n2) |
|---|---|---|---|
1 | 1 | 1 | 1 |
10 | 1 | 10 | 100 |
100 | 1 | 100 | 10000 |
1000 | 1 | 1000 | 1000000 |
… | … | … | … |
Grand O de Landau
https://www.sfeir.dev/front/comprendre-la-complexite-des-algorithmes/
Pire & meilleur cas
Pire cas : l'instance (le choix des entrées) où l'algorithme sera le plus lent et/ou utilisera le plus d'espace
Meilleur cas : l'instance où l'algorithme sera le plus rapide et/ou utilisera le moins d'espace
Exercice
FONCTION max(a, b)
SI a < b
RETOURNER b
SINON
RETOURNER a
FIN SI
FIN FONCTION
Complexité temporelle
O(1)
Complexité spatiale
O(1)
Exercice
FONCTION factorielle(n)
r ← 1
POUR i DE 1 À n FAIRE
r ← r*i
FIN POUR
RETOURNER r
FIN FONCTION
Complexité temporelle
O(n)
Complexité spatiale
O(1)
Versions sans animation, plein écran, imprimable.
Exercices
Calculer la complexité temporelle et spatiale des algorithmes suivants pour le pire et le meilleur cas :
| Temps | Espace | |
|---|---|---|
| Pire cas | ||
| Meilleur cas |
Commencer par trouver les complexités temporelle et spatiale de quelques cas au hasard, puis chercher à généraliser pour les cas extrêmes.
Max
FONCTION max(a, b)
SI a < b ALORS
RETOURNER b
SINON
RETOURNER a
FIN SI
FIN FONCTION
Solution
| Temps | Espace | |
|---|---|---|
| Pire cas | O(1) : pas de boucle | O(1) : pas de liste |
| Meilleur cas | O(1) : on ne peut pas faire mieux que contant | O(1) : pas de liste |
Max Liste
FONCTION max_liste(liste)
max ← liste[0]
POUR i DE 1 À liste.taille - 1 FAIRE
SI liste[i] > max ALORS
max ← liste[i]
FIN SI
FIN POUR
RETOURNER max
FIN FONCTION
Solution
| Temps | Espace | |
|---|---|---|
| Pire cas | O(n) : on parcourt une boucle | O(n) : il y a une liste |
| Meilleur cas | O(n) : on doit de toute façon parcourir toute la liste | O(n) : il y a une liste |
Recherche
FONCTION recherche(liste, valeur)
i ← 0
TANT QUE i < liste.taille FAIRE
SI liste[i] = valeur ALORS
RETOURNER i
FIN SI
i ← i + 1
FIN TANT QUE
RETOURNER -1
FIN FONCTION
Solution
| Temps | Espace | |
|---|---|---|
| Pire cas | O(n) : l'élément cherché se trouve en dernier | O(n) : il y a une liste |
| Meilleur cas | O(1) : l'élément cherché se trouve en premier | O(n) : il y a une liste |
Inverse
FONCTION inverse(liste)
liste_inverse ← liste
POUR i DE 0 À liste.taille / 2 FAIRE
liste_inverse[i] ← liste[liste.taille - i - 1]
FIN POUR
RETOURNER liste_inverse
FIN FONCTION
Solution
| Temps | Espace | |
|---|---|---|
| Pire cas | O(n) : on parcourt une boucle | O(n) : il y a une liste |
| Meilleur cas | O(n) : on doit parcourir la boucle | O(n) : il y a une liste |