Mise en situation:
Lorsque vous envisagez d’acheter un PC, sur quels critères les prix sont-ils basés ?
Bien entendu, cela dépend principalement de:
- La puissance du processeur (qui permet de traiter les données rapidement)
- La capacité de stockage (qui assure un fonctionnement fluide sans que l’ordinateur ne se bloque).
Remarque pour les PC Gamer : le GPU est inclus dans la partie dédiée au traitement, car GPU signifie Graphics Processing Unit, ou unité de traitement graphique.
Ainsi, si vous développez un système ou une application en Python, le code optimal (du point de vue de l’utilisateur) est celui qui nécessite le moins de temps d’exécution et occupe le moins d’espace possible.
Introduction
Comme tu le sais, il existe souvent différents algorithmes pour résoudre un problème.
Si le nombre d’opérations à effectuer est faible et si les données d’entrée sont de petite taille, le choix de la solution a peu d’importance.
En revanche, lorsque le nombre d’opérations et la taille des données d’entrée augmentent, deux facteurs deviennent essentiels : le temps d’exécution et l’occupation mémoire.
Ainsi, pour qu’un algorithme soit efficace, il ne doit pas seulement résoudre un problème, mais aussi répondre aux critères suivants :
- être rapide (en termes de temps d’exécution): C’est ça pourquoi on cherche un PC avec un bon processeur
- être économe en ressources (utilisation de mémoire et d’espace de stockage): C’est ça pourqoui on cherche un PC avec un bon processeur
Des outils sont donc nécessaires pour évaluer la qualité théorique des algorithmes proposés. Aujourd’hui, avec la diminution des coûts de mémoire, l’accent est davantage mis sur l’amélioration de la complexité en temps plutôt qu’en mémoire. Pour cette raison, nous nous concentrerons principalement sur le temps d’exécution.
Notion de complexité
Définition :
- La complexité d’un algorithme en temps : donne le nombre d’opérations effectuées lors de l’exécution d’un programme.
On appelle Ci le coût en temps d’une opération i. - La complexité en mémoire : donne le nombre d’emplacements mémoires occupés lors de l’exécution d’un programme.
Intérêt de la complexité :
La complexité permet de :
- Classer les problèmes selon leur difficulté,
- Classer les algorithmes selon leur efficacité,
- Comparer les algorithmes correspondant à un problème donné sans avoir à les implémenter, c’est-à-dire à les traduire dans un langage particulier.
Complexité dans différents cas
- Complexité au meilleur des cas : C’est le nombre minimal d’opérations qu’un algorithme doit effectuer pour résoudre un problème donné, avec un ensemble de données de taille fixe. Cela représente une borne inférieure de la complexité, indiquant la performance optimale de l’algorithme dans les meilleures conditions possibles.
- Complexité au pire des cas : Il s’agit du nombre maximal d’opérations que l’algorithme peut effectuer, également pour un ensemble de données de taille fixe. Cette valeur permet de connaître le temps d’exécution dans les scénarios les plus défavorables, où l’algorithme doit effectuer le maximum d’opérations avant de terminer. Cependant, ce cas ne reflète pas toujours le comportement typique de l’algorithme, car le pire des cas peut être rare.
- Complexité en moyenne : Elle est plus complexe à déterminer, car elle prend en compte la probabilité de chaque scénario et représente le comportement général de l’algorithme. Elle est utile si les cas extrêmes sont peu probables ou si la complexité varie peu en fonction des données.
🔎 En général, les études de complexité se concentrent sur le cas le plus défavorable, c’est-à-dire le pire des cas, pour garantir que l’algorithme répondra même aux demandes les plus exigeantes.
Exemple
Soit cette fonction qui recherche un élément dans une liste, combien d’opérations vont etre exécutées?
def recherche (L, x):
for i in L:
if i == x:
return True
return False- Au meilleur des cas:
x = L[0]et la fonction va s’arreter après seulement une seule comparaison - Au pire des cas :
xn’existe pas dans la liste et on doit parcourrir toute la liste (n comparaisons)
Calcul du coût d’un algorithme
Pour mesurer la complexité d’un algorithme, il est essentiel de considérer le coût des instructions élémentaires et composées :
Opérations élémentaires :
Une opération élémentaire est une opération de base qui comprend :
- Affectation ;
- Test de comparaison :
==,<,<=,>=,!=; - Opération de lecture (input) et écriture (print) ;
- Opération arithmétique :
+,-,*,/,%.
Le coût d’une opération élémentaire est généralement considéré comme égal à 1.
Exemple 1 :
somme = n + 1 ## Affectation + Addition -> coût = 2
somme = somme + n ## Affectation + Addition -> coût = 2
somme = somme / 2 ## Affectation + Division -> coût = 2Coût total = Coût(ligne 1) + Coût(ligne 2) + Coût(ligne 3)
= 2 + 2 + 2 = 6
Opérations composées
Les opérations composées incluent des instructions plus complexes comme les conditionnelles et les boucles.
- Instruction conditionnelle : Pour une instruction conditionnelle de type
Si P alors Q1 sinon Q2, le nombre d’opérations est donné par : $$ \text{Coût(P)} \leq \text{Coût(test)} + \max(\text{Coût(Q1)}, \text{Coût(Q2)}) $$ - Boucle : Le coût d’une boucle est le produit du nombre de répétitions par la somme des coûts de chaque instruction
xidans le corps de la boucle.- Pour une boucle
for: $$\text{Coût(boucle for)} = \sum \text{Coût(xi)}$$ - Pour une boucle
while: $$ \text{Coût(boucle while)} = \sum (\text{Coût(condition de while)} + \text{Coût(xi)}) $$
- Pour une boucle
Les boucles et les instructions conditionnelles sont des composants essentiels pour déterminer la complexité d’un algorithme, car elles influencent directement le nombre d’opérations nécessaires à l’exécution.
Exemple 2 :
if i % 2 == 0: # Modulo + comparaison -> cout = 2
n = i // 2 # Affectation + division -> cout = 2
else:
i = i + 1 # Affectation + Addition -> cout = 2
n = i // 2 # Affectation + division -> cout = 2Coût total = Coût(condition) + max(Coût(intérieur de if), Coût(intérieur de else))
= 2 + max(2, 4) = 6
Exemple 3 :
i = 1 # Affectation -> Cout = 1
while i <= n: # Comparaison -> Cout = 1
somme = somme + i # Affectation + Addition -> Cout = 2
i = i + 1 # # Affectation + Addition -> Cout = 2Dans ce cas, la boucle va se répéter n fois donc:Coût total = 1 + (1 + 2 + 2)*n = 1 + 5*n
Pour le dernier exemple, lorsque n est assez grand (tend ver l’infini), le 1 est négligeable . C’est pourquoi on va parler de l’ordre de grandeur de la complexité
La complexité asymptotique : Notation Grand-O
La complexité asymptotique d’un algorithme décrit son comportement lorsque la taille n des données d’entrée devient très grande (tend vers l’infini). Elle ne fournit pas une mesure exacte du temps d’exécution, mais une estimation de la croissance du temps d’exécution.
La notation O(f) est utilisée pour décrire ce comportement asymptotique d’une fonction f, indiquant comment l’algorithme se comporte pour de grandes valeurs.
Classes de complexités
Les classes de complexité des algorithmes (dans le pire des cas, notées avec la notation O) les plus courantes sont :
| Complexité | Temps d’exécution | Description |
|---|---|---|
| O(1) | Temps constant | Le temps d’exécution ne dépend pas des données traitées, ce qui est assez rare ! Exemple : recherche dichotomique |
| O(log(n)) | Logarithmique | Réponse immédiate Exemple : recherche dichotomique |
| O(n) | Linéaire | Augmentation linéaire du temps d’exécution quand le paramètre croît (si le n double, le temps double). Exemple : recherche séquentielle |
| O(n log(n)) | Quasi-linéaire | Augmentation un peu supérieure à O(n) Exemple : Tri par fusion |
| O(n²) | Quadratique | Algorithmes avec deux boucles imbriquées. Exemple : Tris standards (Sélection, Bulle, Insertion) |
| O(np) | Polynomiale | ici, np est le terme de plus haut degré d’un polynôme en n ; il n’est pas rare de voir des complexités en O(n³) ou O(n⁴). |
| O(pn) | Exponentielle | Quand le paramètre double, le temps d’exécution est élevé à la puissance p avec p > 1. |
Un algorithme logarithmique est considérablement plus efficace qu’un algorithme linéaire (lui même plus efficace qu’un algorithme quadratique ou pire exponentiel).
Cette différence devient fondamentale si la taille des données est importante
Exemple
Avec un ordinateur de $10^{9}$ instructions par seconde:
| Complexité | temps d’exécution en fonction du nombre d’opérations | |||||
|---|---|---|---|---|---|---|
| n | 5 | 10 | 15 | 20 | 100 | 1000 |
| log n | 3.10⁻⁹ s | 4.10⁻⁹ s | 4.10⁻⁹ s | 5.10⁻⁹ s | 7.10⁻⁹ s | 10⁻⁸ s |
| 2n | 10⁻⁸ s | 2.10⁻⁸ s | 3.10⁻⁸ s | 4.10⁻⁸ s | 2.10⁻⁷ s | 2.10⁻⁶ s |
| n log n | 1,2.10⁻⁸ s | 3.10⁻⁸ s | 6.10⁻⁸ s | 4.10⁻⁷ s | 7.10⁻⁶ s | 10⁻³ s |
| n² | 2,5.10⁻⁸ s | 10⁻⁷ s | 2,3.10⁻⁷ s | 4.10⁻⁷ s | 10⁻⁵ s | 10⁻³ s |
| n⁵ | 3.10⁻⁶ s | 10⁻⁴ s | 7,6.10⁻⁴ s | 3,10⁻³ s | 10 s | 11 jours |
| 2ⁿ | 3,2.10⁻⁸ s | 10⁻⁶ s | 3,3.10⁻⁵ s | 10⁻³ s | 4.10¹³ ans | 3.10²⁸⁴ s |
| n! | 1,2.10⁻⁷ s | 4.10⁻³ s | 23 minutes | 77 ans | 3.10¹⁴¹ ans | 10⁵⁰⁰ s |
| nⁿ | 3.10⁻⁶ s | 10 s | 13 ans | 3.10¹⁹ ans | 3.10¹⁸³ ans | 10³⁰⁰ s |
Remarque
L’efficacité d’un algorithme ne se mesure pas en secondes, car cela impliquerait de les implémenter et ces mesures ne seraient pas significatives, étant dépendantes de la machine utilisée.
Règles de calcul du grand O
- Si le coût d’un algorithme est une valeur constante : O(1)
Exemple : $C(\text{algorithme}) = 15$ alors la complexité asymptotique est O(1). - Si le coût d’un algorithme dépend de n : on prend le plus grand degré
Exemple : $ C(\text{algorithme}) = 5n^2 + 2n + 13 $ alors la complexité asymptotique est $O(n^2)$
Pour calculer la complexité de cet algorithme :
for i in range(n): # nombre de répétitions = n
for j in range(n - 3): # nombre de répétitions = n - 3
print(i + j) # coût est 2 (print + addition)- La complexité de l’algorithme est donnée par :
$\sum_{i=0}^{n-1} \sum_{j=0}^{n-4} 2 = \sum_{i=0}^{n-1} 2(n – 3) = 2n \times (n – 3) = 2n^2 – 6n \quad \Rightarrow \quad O(n^2)$
L’appel d’une fonction
Lorsque vous appelez une fonction, le coût de cet appel est le nombre total d’opérations élémentaires générées par cet appel.
Exemple : Calcul de la complexité de l’algorithme
def somme(n):
s = 0 # coût est 1
for i in range(n + 1): # répétitions = n + 1
s += i # coût est 2
return s # coût est 1
y = 0 # coût est 1
for i in range(n): # répétitions = n
y += somme(i) # coût est 2 + coût de somme(i) = 2 + (2i + 4)
print(y) # coût est 1- Complexité de la fonction
somme(n):- $Coût = 1 + \left( \sum_{i=0}^{n} 2 \right) + 1 = 1 + 2(n + 1) + 1 = 2n + 4 \Rightarrow O(n)$
- Complexité de l’algorithme principal :
- $ Coût total = 1 + \left( \sum_{i=0}^{n-1} (2i + 6) \right) + 1 \Rightarrow O(n^2) $
L’appel d’une fonction récursive
Pour les fonctions récursives, le temps de calcul est exprimé en termes de relation de récurrence, en comptant le nombre d’appels récursifs.
Exemple 1 : Complexité de la fonction récursive suivante
def factoriel(n):
if n == 0:
return 1
else:
return n * factoriel(n - 1)- Analyse de la complexité : $C(n) = C(n-1) + 1$ avec $C(0)=1 $
Pour les problèmes de type Diviser pour régner, on peut appliquer le théorème Master pour analyser la complexité.
Théorème : Master Theorem
Lorsqu’on a un problème de taille ($ n$ ) que l’on divise en ($ a$ ) sous-problèmes de taille ( $\frac{n}{b}$ ), le coût de l’algorithme peut être exprimé comme suit :
- $C(1) = 1$
- $C(n) = a \times C\left(\frac{n}{b}\right) + f(n)$
Où \( f(n) \) correspond au coût de reconstruction, souvent \( c \times n^{\alpha} \). Pour le théorème, on suppose \( a \geq 1 \), \( b > 1 \), et on note \( k = \log_b(a) \).
Il existe trois cas pour déterminer la complexité asymptotique de \( C(n) \) :
- Cas 1 : Si \( O(f(n)) = O(n^k) \), alors \( C(n) = O(n^k \log(n)) \).
- Cas 2 : Si \( O(f(n)) = O(n^{k – \epsilon}) \) pour une constante \( \epsilon > 0 \), alors \( C(n) = O(n^k) \).
- Cas 3 : Si \( O(f(n)) = O(n^{k + \epsilon}) \) pour une constante \( \epsilon > 0 \), et si \( a f\left(\frac{n}{b}\right) < c f(n) \) pour une constante \( c < 1 \), alors \( C(n) = O(f(n)) \).
Exemple :
Pour un problème où \( C(n) = 4C\left(\frac{n}{2}\right) + n \), nous avons :
- \( f(n) = n \)
- \( a = 4 \), \( b = 2 \) donc \( k = \log_2(4) = 2 \)
La complexité est donc : \( O(n^2) \).
