Complexité

La théorie

Temps d'exécution

Il ne suffit pas d'écrire du code correct, il faut aussi que ce code soit efficace. On peut ainsi chercher à minimiser :

  • le temps d'exécution du code,
  • la place mémoire nécessaire pour exécuter le code,
  • voire la consommation en énergie.

Nous nous intéressons ici au temps d'exécution. Pour réduire ce temps d'exécution, une solution est d'utiliser une machine plus puissante. Mais c'est une solution très coûteuse voire impossible à mettre en oeuvre si ce temps doit être divisé par 1000. L'autre solution est de trouver un algorithme plus efficace pour résoudre le problème.

L'étude de la complexité en temps d'un algorithme consiste à raisonner sur le code pour établir des propriétés du genre :

Lorsque la taille de la donnée est multipliée par 10, le temps d'exécution du code est approximativement multiplié par 100.

Opérations élémentaires

Pour analyser l'efficacité d'un algorithme on cherche à calculer le nombre d'opérations élémentaires exécutées par cet algorithme. Les opérations élémentaires n'ont pas toutes le même temps d'exécution. Le dénombrement du nombre d'opérations élémentaires est cependant un bon critère d'évaluation de l'efficacité de l'algorithme.

La lecture et l'écriture d'un int, d'un float ou d'un bool ainsi que toutes les opérations arithmétiques et logiques sont des opérations élémentaires.

Opérations élémentaires sur les listes :

  • création d'une liste vide,
  • lecture ou écriture d'un élément,
  • ajout ou retrait d'un élément en fin de liste,
  • la lecture de la longueur d'une liste.

Coût asymptotique

Le coût d'une instruction est le nombre d'opérations élémentaires qu'elle implique. Ce nombre peut dépendre d'un paramètre $n$. Dans ce cas on se satisfait d'une majoration asymptotique en énonçant par exemple que le coût $C(n)$ est en $O(n^2)$.

Rappelons que $C(n)=O(g(n))$ signifie qu'il existe une constante $K$ et un entier $n_0$ tels que $n\geq n_0$ entraine $C(n)\leq Kg(n)$.

Remarque : Dire qu'une instruction à un coût en $O(1)$ signifie qu'elle implique un nombre fini d'opérations élémentaires indépendant du paramètre $n$. Une telle instruction peut être assimilée à une opération élémentaire.

Coût asymptotique des opérations sur les list

Opération Effet Coût
L = [] Création d'une liste vide $O(1)$
L[i] Lecture/écriture d'un élément $O(1)$
L.append(x) Ajout d'un élément en fin de liste $O(1)$
x = L.pop() Retrait de l'élément de fin de liste $O(1)$
len(L) Lecture de la longueur d'une liste $O(1)$
L = [0] * n Création d'une liste de taille $n$ $O(n)$
T = list(L) Copie d'une liste de taille $n$ $O(n)$
L.sort() Tri d'une liste de taille $n$ $O(n\log n)$

La pratique

Recherche de l'élément minimal d'une liste

In [ ]:
def mini(T):
    """ Retourne le plus petit élément de la liste T.
    """
    n = len(T)
    k = 0
    for j in range(1, n):  #6
        if T[j] < T[k]:    #7
            k = j          #8
    return T[k]

Soit $n$ la longueur de la liste T.

  • Toutes les instructions sont en $O(1)$.
  • La boucle 6-8 est exécutée $n-1$ fois.

Ceci montre que le coût de la fonction mini est en $O(n)$.

Le tri par selection

In [ ]:
def tri_selection(T):
    """ Tri en place la liste T par ordre croissant.
    """
    n = len(T)
    for i in range(n - 1):
        k = i
        for j in range(i + 1, n):   #7
            if T[j] < T[k]:         #8
                k = j               #9
        T[i], T[k] = T[k], T[i]

Soit $n$ la longueur de la liste T.

  • Toutes les instructions sont en $O(1)$.
  • L'instruction de la ligne 8 est celle qui est exécutée le plus souvent.
  • Lors de l'itération i la boucle lignes 7-9 est exécutée $n-i-1$ fois.
  • Le nombre total d'exécution de la ligne 8 est $\sum_{i=0}^{n-2}(n-i-1)=\frac{n(n-1)}{2}=O(n^2)$.

Ceci montre que le coût de la fonction tri_selection est en $O(n^2)$.

Le tri par insertion

In [ ]:
def tri_insertion(T):
    """ Trie en place la liste T en utilisant l'algorithme
        du tri par insertion.
    """
    n = len(T)
    for k in range(1, n):
        r = k
        while r > 0 and T[r - 1] > T[r]:      #8
            T[r - 1], T[r]  = T[r], T[r - 1]
            r = r - 1

Soit $n$ la longueur de la liste T.

Contrairement au tri par sélection, le nombre d'opérations élémentaires exécutées par le tri insertion ne dépend pas que de la longueur $n$ de la liste T. Il dépend aussi de la façon dont sont initialement ordonnés les éléments de la liste.

Dans ce cas, on étudie la complexité au pire.

  • Toutes les instructions sont en $O(1)$.
  • L'instruction de la ligne 8 est celle qui est exécutée le plus souvent.
  • Lors de l'itération k la ligne 8 est exécutée au maximum $k+1$ fois.
  • Le nombre total d'exécution de la ligne 8 est donc majoré par $\sum_{k=1}^{n-1}(k+1)=\frac{(n+2)(n-1)}{2}=O(n^2)$.

Ceci montre que le coût de la fonction tri_insertion est en $O(n^2)$.

On peut noter que le cas le pire correspond à une liste triée par ordre décroissant. Dans ce cas la complexité est exactement quadratique.

Le tri par comptage (version 1)

In [ ]:
def comptage(T, n):
    """ Retourne une liste C de longueur n telle que C[k] soit
        le nombre d'occurrences de l'entier k dans la liste T.
    """
    C = []
    for i in range(n):
        cpt = 0
        for k in T:
            if k == i:         #9
                cpt = cpt + 1
        C.append(cpt)          #11
    return C

def tri_comptage(T, n):
    """ Trie la liste d'entiers naturels T.
        L'entier n est un majorant strict des éléments de T.
    """
    C = comptage(T, n)         #18
    i = 0                      #19
    for k in range(n):         #20
        for _ in range(C[k]):  #21
            T[i] = k           #22
            i = i + 1          #23

Pour analyser la complexité de la fonction tri_comptage il convient tout d'abord d'établir celle de la sous-fonction comptage.

Soit $m$ la longueur de la liste T.

  • Toutes les instructions, y compris celle de la ligne 11 sont en $O(1)$.
  • À chaque itération i, l'instruction ligne 9 est exécutée $m$ fois, soit au total $mn$ fois.

On en déduit que la complexité de la fonction comptage est en $O(nm)$. Analysons maintenant la fonction tri_comptage.

  • L'appel à comptage ligne 18 est en $O(n+m)$.
  • Les autres instructions sont en $O(1)$.
  • L'instruction de la ligne 21 est exécutée $n$ fois.
  • Les instructions des lignes 22-23 sont exécutées $\sum_{k=0}^{n-1}C[k]=m$

Le coût des instructions lignes 20-23 est donc en $O(n+m)$. Ce coût est ainsi dominé par celui de l'appel à la fonction comptage. Ceci montre que le coût de la fonction tri_comptage est en $O(nm)$.

Le tri comptage (version 2)

Pour améliorer l'efficacité du tri par comptage l'analyse précédente montre qu'il convient de porter son attention sur la fonction comptage. Il est possible de créer la liste C en lisant une seule fois la liste T.

In [ ]:
def comptage(T, n):
    """ Retourne une liste C de longueur n telle que C[k] soit
        le nombre d'occurrences de l'entier k dans la liste T.
    """
    C = [0] * n     #5
    for k in T:
        C[k] += 1
    return C
  • L'instruction de la ligne 5 est en $O(n)$.
  • Les autres instructions sont en $O(1)$.
  • La boucle est exécutée $m$ fois.

On en déduit que la complexité de la fonction comptage est en $O(n + m)$. Cette fois l'appel à comptage ne pénalise pas la complexité globale de la fonction tri_comptage qui est maintenant elle aussi en $O(n+m)$.