Complexité - Cours

1 Complexité

La complexité d’un algorithme est une mesure de l’efficacité de cet algorithme en termes de ressources qu’il consomme. Les deux principales ressources considérées sont le temps (complexité en temps) et la mémoire (complexité en espace). Comprendre la complexité d’un algorithme est crucial pour plusieurs raisons :

Performance : Choisir un algorithme avec une meilleure complexité peut grandement améliorer la performance de votre programme, surtout avec des entrées de grandes tailles.
Limitation : Un algorithme avec une mauvaise complexité peut devenir inemployable lorsque la taille de l’entrée augmente.
Optimisation : Calculer la complexité permet d’identifier les parties de l’algorithme qui peuvent être optimisées.

Important

Dans ce module, nous allons uniquement étudier la complexité en temps des algorithmes. Les problèmes liés au temps d’exécution sont plus courants et universels que ceux liés à la mémoire.

1.1 Complexité en temps

La complexité en temps mesure le temps d’exécution d’un algorithme en fonction de la taille de l’entrée. On l’exprime généralement en utilisant la notation grand O de Landau, qui décrit le pire cas (le plus grand temps d’exécution possible pour une taille d’entrée donnée). Voici les classes de complexité les plus connues, du meilleur au pire :

\(O(1)\) – Complexité constante : Le temps d’exécution ne dépend pas de la taille de l’entrée.
- Exemple: Trouver la valeur médianne d’un tableau trié.
\(O(log \; n)\) – Complexité logarithmique : Le temps d’exécution croît logarithmiquement avec la taille de l’entrée.
- Exemple: Recherche dichotomique dans un tableau trié.
\(O(n)\) – Complexité linéaire : Le temps d’exécution croît linéairement avec la taille de l’entrée.
- Exemple: Recherche séquentielle dans un tableau trié.
\(O(n \; log \; n)\) – Complexité quasi-linéaire : Courante dans les algorithmes de tri efficaces.
- Exemple: Tri par fusion d’un tableau.
\(O(n^2)\) – Complexité quadratique : Le temps d’exécution croît quadratiquement avec la taille de l’entrée.
- Exemple: Tri par insertion d’un tableau.
\(O(2^n)\) – Complexité exponentielle : Le temps d’exécution double avec chaque élément supplémentaire dans l’entrée.
- Exemple: Calcul récursif de la suite de Fibonacci.
\(O(n!)\) – Complexité factorielle : Le temps d’exécution croît de manière factorielle avec la taille de l’entrée.
- Exemple: Recherche exhaustive pour résoude le problème du voyageur de commerce.

1.2 Méthode de calcul

Calculer le nombre d’opérations effectuées par l’algorithme, noté \(T(n)\), en fonction de la taille \(n\) des données en entrée.
Déterminer l’ordre de grandeur asymptotique de l’algorithme, noté \(O(f(n))\), à partir de \(T(n)\).

1.3 Calculer le nombre d’opérations \(T(n)\)

Pour calculer le nombre d’opérations \(T(n)\) d’un algorithme, on additionne celles provenant des expressions, des boucles et des alternatives en exprimant le résultat en fonction de la taille \(n\) des données en entrée.

1.3.1 Expressions

On suppose que toutes les opérations élémentaires (déclarations, affectations, comparaisons, calcul arithmétiques, etc.) sont à égalité de coût, soit 1 « unité » de temps.

Exemple

# default_start
def mystere(x):
    y = x * 3             # 1 affectation + 1 multiplication
    z = y - 2             # 1 affectation + 1 soustraction
    yz = y * z            # 1 affectation + 1 multiplication
    result = y + z + yz   # 1 affectation + 1 addition + 1 addition
    return result         # 1 retour
# default_end

Calcul

\[ \begin{align} n & = x \\ T(n) & = 2 + 2 + 2 + 3 + 1 \\ & = 10 \\ \end{align} \]

1.3.2 Boucles

Pour toute boucle dans un algorithme, on compte le nombre d’opérations élémentaires à l’intérieur de la boucle et on le multiplie par le nombre d’itérations de la boucle.

Exemple

# default_start
def mystere(y):
    i = 0             # 1 affectation
    total = 0         # 1 affectation
    # Boucle:
    #   de i=0 jusqu'à i>=y avec pas de 1 
    #   => (y - 0) / 1 
    #   => y itérations             
    while i < y:          # 1 comparaison                      
      total = total + i   # 1 affectation + 1 addition
      i = i + 1           # 1 affectation + 1 addition
    return True       # 1 retour
# default_end

Calcul

\[ \begin{align} n & = y \\ T(n) & = 1 + 1 + n(1 + 2 + 2) + 1 \\ & = 5n + 3 \\ \end{align} \]

1.3.3 Alternatives

Pour les alternatives, on garde le nombre d’opérations élémentaires le plus élevée entre les différentes branches.

Exemple

# default_start
def mystere(z):
    i = 0                 # 1 affectation
    if z > 10:            # 1 comparaison
      # Boucle:
      #   de i=0 jusqu'à i>=z avec pas de 1
      #   => (z - 0) / 1
      #   => z itérations   
      while i < z:          # 1 comparaison
        i = i + 1           # 1 affectation + 1 addition     
    else:                 # 1 comparaison (celui du if)
      # Boucle:
      #   de i=0 jusqu'à i>=z² avec pas de 1
      #   => (z² - 0) / 1
      #   => z² itérations   
      while i < z * z:      # 1 comparaison + 1 multiplication
        i = i + 1           # 1 affectation + 1 addition 
    return True           # 1 retour
# default_end

Calcul

\[ \begin{align} n & = z \\ T(n) & = 1 + max(1 + n(1 + 2), 1 + n^2(2 + 2)) + 1 \\ & = max(3n + 1, 4n^2 + 1) + 2 \\ & = 4n^2 + 3 \\ \end{align} \]

1.4 Déterminer l’ordre de grandeur asymptotique \(O(f(n))\)

Pour déterminer l’ordre de grandeur asymptotique d’un algorithme, il suffit de garder la terme dominant de \(T(n)\) et de lui enlever les constantes multiplicatives. Avec les \(T(n)\) calculées précédemment, on obtient les \(O(f(n))\) suivants :

\[ \begin{align} T(n) & = {\color{blue} 10} & \implies O({\color{blue} 1}) \\ T(n) & = 5{\color{blue} n} + 3 & \implies O({\color{blue} n}) \\ T(n) & = 4{\color{blue} n^2} + 3 & \implies O({\color{blue} n^2}) \\ \end{align} \]

Exemples avec d’autres fonctions \(T(n)\) :

\[ \begin{align} T(n) & = 6{\color{blue}n^3} + 4n^2 + 2n + 1 & \implies O({\color{blue}n^3}) \\ T(n) & = 3 {\color{blue}\log n} + 2 & \implies O({\color{blue}\log n}) \\ T(n) & = 5{\color{blue}n \log n} + 7 & \implies O({\color{blue}n \log n}) \\ T(n) & = {\color{blue}2^n} + 3n^2 & \implies O({\color{blue}2^n}) \\ T(n) & = 6{\color{blue}n!} + 4n^3 & \implies O({\color{blue}n!}) \\ \end{align} \]

Plus de détails

Une fonction \(T(n)\) est en \(O(f(n))\) si :

\[T(n) \in O(f(n)) \iff \exists c > 0\; et\; n_0 \in \mathbb{N}\; tels\; que\; \forall n \geq n_0,\; T(n) \le c \times f(n) \]

Autrement dit :

\(T(n)\) est en \(O(f(n))\) s’il existe un seuil à partir duquel la fonction \(T\) est toujours dominée par la fonction \(f\), à une constante multiplicative fixée \(c\) près.

Exemple 1

\(T(n) = 7\) est en \(O(1)\) car il existe \(T(n) \le c \times 1\) avec, par exemple, \(c=8\).

Exemple 2

\(T(n) = 12n + 5\) est en \(O(n)\) car il existe \(T(n) \le c \times n\) avec, par exemple, \(c=13\).

Exemple 3

\(T(n) = 4n² + 2n + 6\) est en \(O(n²)\) car il existe \(T(n) \le c \times n²\) avec, par exemple, \(c=5\).

Exemple 4

\(T(n) = 6n^3 + 4n^2 + 2n + 1\) est en \(O(n^3)\) car il existe \(T(n) \le c \times n^3\) avec, par exemple, \(c=7\).