Programmation Python
Complexité algorithmique
Plusieurs questions peuvent se poser :
Comment peut-on comparer les algorithmes ?
Est-ce que l’algorithme dont le code est le plus court est le
meilleur ?
Quels sont les critères d’évaluation d’un algorithme ?
D’où la notion de complexité algorithmique
90 / 107
Programmation Python
Complexité algorithmique
Introduction
Définition de la complexité algorithmique : L’étude de la
quantité de ressources (temps et mémoire) qu’un algorithme
nécessite pour résoudre un problème en fonction de la taille
des données d’entrée.
On distingue deux types :
Complexité temporelle
Complexité spatiale
Importance et applications pratiques :
Optimisation des ressources dans des systèmes à grande
échelle.
Choisir l’algorithme le plus adapté à un problème donné.
91 / 107
Programmation Python
Complexité algorithmique
Définition : La complexité temporelle d’un algorithme
repose sur le comptage des opérations élémentaires (le coût
ou le temps d’exécution d’un algorithme en fonction de la
taille de l’entrée).
Notion des opérations élémentaires : Une opération
élémentaire est une instruction de base qui s’exécute en un
temps constant, indépendamment de la taille de l’entrée.
Exemples d’opérations élémentaires :
Affectation. x = 5.
Comparaison. x != 5.
Operations arithmétiques + − /∗.
Operations de lecture et écriture
Définition La complexité spatiale est le nombre
d’emplacements mémoire occupés lors de l’exécution d’un
programme.
92 / 107
Programmation Python
Complexité algorithmique
Notations Asymptotiques En algorithmique, on utilise trois prin-
cipales notations pour analyser la complexité temporelle et spa-
tiale : O (grand-O), Ω (grand-Omega) et Θ (Theta). Ces notations
permettent de décrire le comportement d’un algorithme pour des
entrées de grande taille (n → ∞).
O (Grand-O) : Limite supérieure, temps maximal.
Ω (Grand-Omega) : Limite inférieure, temps minimal.
Θ (Theta) : Comportement asymptotique exact.
93 / 107
Programmation Python
Complexité algorithmique
O (Grand-O) : Limite Supérieure (Temps Maximal)
La notation O décrit une borne supérieure sur le temps d’exécution
d’un algorithme. Elle représente le pire cas, ou le temps maximal
qu’un algorithme peut prendre pour traiter une entrée de taille n.
Définition formelle : Un algorithme est de complexité O(f (n)) s’il
existe des constantes positives c et n0 telles que, pour tout n ≥ n0 :
T (n) ≤ c · f (n)
Cela signifie que le temps d’exécution T (n) de l’algorithme, pour
des valeurs de n suffisamment grandes, est borné par une constante
c multipliée par f (n). Exemple :
Prenons un algorithme de recherche linéaire :
Dans le pire cas, x est absent de la liste, et la boucle parcourt tous 94 / 107
Programmation Python
Complexité algorithmique
Ω (Grand-Omega) : Limite Inférieure (Temps Minimal)
La notation Ω décrit une borne inférieure sur le temps d’exécution
d’un algorithme. Elle représente le meilleur cas, ou le temps mini-
mal qu’un algorithme peut prendre pour traiter une entrée de taille
n.
Définition formelle : Un algorithme est de complexité Ω(g (n)) s’il
existe des constantes positives c et n0 telles que, pour tout n ≥ n0 :
T (n) ≥ c · g (n)
Exemple :
Pour le même algorithme de recherche linéaire, dans le meilleur cas,
l’élément recherché x est le premier élément de la liste, et la boucle
s’exécute une seule fois.
La complexité temporelle est Ω(1).
95 / 107
Programmation Python
Complexité algorithmique
Θ (Theta) : Comportement Asymptotique Exact
La notation Θ décrit à la fois une borne supérieure et une borne
inférieure. Elle fournit une estimation précise du comportement asymp-
totique exact de l’algorithme.
Définition formelle : Un algorithme est de complexité Θ(h(n)) s’il
existe des constantes positives c1 , c2 et n0 telles que, pour tout
n ≥ n0 :
c1 · h(n) ≤ T (n) ≤ c2 · h(n)
Exemple :
Pour un algorithme de tri par insertion :
Dans le pire cas : O(n2 ).
Dans le meilleur cas : Ω(n) (liste déjà triée).
En cas moyen (éléments aléatoires), la complexité est Θ(n2 ).
96 / 107
Programmation Python
Complexité algorithmique
Comparaison des Notations
Notation Type de Borne Exemple
O(f (n)) Borne supérieure Temps maximal (pire cas) : O(n2 )
Ω(g (n)) Borne inférieure Temps minimal (meilleur cas) : Ω(1)
Θ(h(n)) Borne exacte Temps moyen ou exact : Θ(n log n)
97 / 107
Programmation Python
Complexité algorithmique
Classes de Complexité : Complexités temporelles courantes
O(1) : constante.
O(log(n)) : logarithmique.
O(n) : linéaire.
O(n log(n)) : quasi-linéaire.
O(n2 ) : quadratique.
O(np ) : polynomiale.
O(an ) avec a > 1 : exponentielle.
O(n!) : factorielle.
Hiérarchie des croissances :
O(1) ⊆ O(log(n)) ⊆ O(n) ⊆ O(n log(n)) ⊆ O(n2 ) ⊆ O(np ) ⊆
O(an ) ⊆ O(n!)
98 / 107
Programmation Python
Complexité algorithmique
Exemple : Complexité Linéaire O(n)
Code Python :
Test :
liste = [1, 2, 3, 4, 5] print(recherche-element(liste, 3)) # O(n)
99 / 107
Programmation Python
Complexité algorithmique
Exemple : Complexité Quadratique O(n2 )
Code Python : Tri à bulles
Test :
liste = [64, 34, 25, 12, 22, 11, 90] print(tri-bulle(liste)) # O(n2 )
100 / 107
Programmation Python
Complexité algorithmique
Exemple de Tri
Tri à bulles (Complexité O(n2 ))
Test : liste = [64, 34, 25, 12, 22, 11, 90] print(tri-bulle(liste)) #
O(n2 )
101 / 107
Programmation Python
Complexité algorithmique
Exemple de Tri
Tri rapide (Complexité O(n log n))
Test : liste = [64, 34, 25, 12, 22, 11, 90] print(tri-rapide(liste))
O(n log n)
102 / 107
Programmation Python
Complexité algorithmique
Complexité spatiale (en espace)
Notion de mémoire : La complexité spatiale est le nombre
d’emplacements mémoire occupés lors de l’exécution d’un
programme.
Exemples pratiques :
Récursif vs itératif
103 / 107
Programmation Python
Complexité algorithmique
Exemple : Récursif vs Itératif
Récursif (plus coûteux en mémoire) :
Test : print(fibonacci-recursive(10)) # Utilise plus de mémoire
Itératif (moins coûteux en mémoire) :
Test : print(fibonacci-iteratif(10)) # Moins de mémoire utilisée 104 / 107
Programmation Python
Complexité algorithmique
Exercice 1 : Recherche Linéaire Enoncé : Implémentez une fonc-
tion recherche linéaire(lst, x) qui prend en entrée une liste
lst et un élément x à rechercher. Retournez l’indice de l’élément
s’il est présent, sinon, retournez -1.
Objectif : Analyser la complexité temporelle de cette fonction en
fonction de la taille de la liste n.
Questions :
Quelle est la complexité temporelle dans le pire des cas ?
Quelle est la complexité spatiale de cette fonction ?
105 / 107
Programmation Python
Complexité algorithmique
Exercice 2 : Tri par Insertion
Questions :
Quelle est la complexité temporelle de cet algorithme dans le
pire des cas ?
Quelle est la complexité spatiale ?
Comparez cette complexité avec celle du tri à bulles.
106 / 107
Programmation Python
Complexité algorithmique
Exercice 3 : Somme des éléments Enoncé : Écrivez une fonction
somme elements(lst) qui calcule la somme des éléments d’une
liste de n entiers.
Objectif : Analyser la complexité temporelle et spatiale de cet al-
gorithme.
Questions :
Quelle est la complexité temporelle de cette fonction ?
Quelle est la complexité spatiale ?
107 / 107