Aller au contenu

L. Complexité des algorithmes

Objectif

L'objectif de cette notion de complexité est double :

  • Évaluer l'efficacité d'un algorithme A
  • Pouvoir comparer l'efficacité de cet algo A avec un autre B qui ferait la même chose.

On a déjà vu que l'on pouvait essayer de chronométrer le temps d'exécution des algorithmes et même faire des graphiques de performance, mais on souhaite ici une technique qui soit indépendante de la machine sur laquelle on exécute ces algorithmes (le chronométrage peut-être affecté par beaucoup de paramètres extérieurs...)

I. Le principe

On va essayer d'évaluer le nombre d'opérations élémentaires en fonction de la taille des données (par exemple le nombre d'éléments à trier).

Notations :

  • n : taille des données
  • T(n) : nombres d'opérations élémentaires

On distinguera parfois plusieurs situations caractéristiques:

  • Le meilleur des cas,
  • Le pire des cas (c'est souvent celui-là que l'on privilégie, et c'est celui-là qui est au programme !),
  • le cas moyen.

La technique pour évaluer T(n):

  1. On cumule les coûts de traitements successifs:

    \[\boxed{ \left.\begin{array}{l} Traitement\ 1 : T_1(n) \\ Traitement\ 2 : T_2(n) \end{array} \right\} T(n)=T_1(n)+T_2(n)} \]

  2. Lorsqu'il y a un conditionnement, on prendra le maximum des coûts possibles:

    \[ \boxed{ \left.\begin{array}{ll} Si\ < condition >\ alors : & \quad T_c(n)\\ \quad Traitement\ 1 & \quad T_1(n)\\ Sinon & \\ \quad Traitement\ 2 & \quad T_2(n) \end{array}\right\} T(n)=T_c(n)+max(T_1(n),T_2(n)) } \]

  3. En présence de boucle, on cumule:

    \[\boxed{ \left.\begin{array}{ll} Tant\ que < condition > faire : & \quad C_i(n)\\ \quad Traitement & \quad T_i(n) \end{array}\right\} T(n)=\sum_{i=1}^{k}(C_i(n)+T_i(n))+C_{k+1}(n) } \]

Un premier exemple : On considère la fonction python:

def recherche(L:list, e : int)->bool :
    """reçoit une liste d'entiers `L` et un entier `e`,
    et renvoie `True` si l'élément `e` est dans la liste `L`
    et `False` sinon."""
    for k in L :
        if e==k :
            return True
    return False
  • Pour la taille des données (le couple (L,e)), un choix raisonnable serait de prendre la taille de la liste L.
  • Pour les opérations élémentaires un choix raisonnable serait de considérer l'opération de comparaison (e==k). Remarquons que cela revient ici à dénombrer le nombre d'itérations.

Question : quelle est la complexité de cet algorithme de recherche ?

Réponse

On constate facilement que dans le pire des cas la complexité en nombre de comparaisons est len(L) (si e n'est pas dans la liste) et qu'elle est égale à 1 si l'élément cherché est présent en première position.

II. Notations

En réalité on n'a pas besoin de comptabiliser le nombre d'opérations à l'unité près, mais juste d'en connaître l'ordre de grandeur "asymptotique", c'est à dire lorsque la taille des données devient très grande. On introduit pour cela des notations (qui seront reprises en math...) :

  • On note \(T(n)=O(f(n))\) s'il existe une constante \(c\) et un rang à partir duquel :

    \[T(n)\leqslant c\times f(n)\qquad\text{(On majore la complexité)}\]

  • On note \(T(n)=\Theta(f(n))\) s'il existe 2 constantes \(c_1\) , \(c_2\) et un rang à partir duquel :

    \[c_1\times f(n) \leqslant T(n)\leqslant c_2\times f(n)\qquad\text{(On encadre la complexité)}\]

Exemples : donner la notation \(O\) pour les complexités suivantes:

\[ T_1(n)=n^3+2n^2+4n+2 \qquad T_2(n)=n\log n + 12 n +2\qquad T_3(n)=2n^{5}+n^6+\dfrac{2^n}{100}\]
Réponse
\[ T_1(n)=O(n^3) \qquad T_2(n)=O(n\log n) \qquad T_3(n)=O(2^n)\]

Principales classes de complexité :

Notation complexité
\(O(1)\) temps constant
\(O(\log n)\) logarithmique
\(O(n)\) linéaire
\(O(n\times\log n)\) ce sont les tris optimaux
\(O(n^2)\) quadratique (polynomial)
\(O(2^n)\) exponentiel

III. Exemples

1. Exemples très simples:

  • On a vu que la recherche d'un élément dans un tableau était linéaire (dans le pire des cas), c'est à dire en \(O(n)\). On verra dans le prochain TD que si le tableau est trié, cette recherche peut se faire en temps logarithmique \(O(\log n)\) (avec la dichotomie).

  • Les divers algorithmes classiques de tris de tableaux sont entre \(O(n^2)\) et \(O(\log n)\).

  • Le problème classique du voyageur de commerce consiste à trouver, pour un ensemble de villes données, le plus court circuit possible qui passe par chaque ville une seule fois et revient au point de départ. Sa complexité est exponentielle (on ne connait pas d'algorithme polynomial pour le résoudre, en informatique on parle de problème NP-complet). C'est un gros inconvénient (voir estimation des temps de calculs ci-après...)

  • Le problème du sac à dos consiste à sélectionner un sous-ensemble d'objets à placer dans un sac à dos de capacité limitée de manière à maximiser la valeur totale des objets sélectionnés (exemple : optimiser la tournée d'un camion de marchandises). Ce problème classique est lui-aussi non polynomial...

2. À vous de trouver

Pour les exercices suivants, dire ce que fait la fonction (rédiger la docstring) puis donner sa complexité.

Exercice 1 :

def per(S : list, i : int, j : int):
    tmp = S[i]
    S[i]=S[j]
    S[j]=tmp
    return S
Réponse

Cette fonction permute deux valeurs dans une liste. Il y a toujours trois affectations. Complexité constante \(O(1)\).

Exercice 2 :

def rec(S : list,x : int):
    i,n = 1,len(S)
    while i<n and x!=S[i]:
        i = i +1
    return i!=n
Réponse

Cette fonction détermine si un élément est dans un liste. Dans le pire des cas, on parcourt toute la liste (avec à chaque fois deux tests et une affectation). Complexité linéaire \(O(n)\).

Exercice 3 : Reprenons la fonction seuil que l'on a vu dans le chapitre sur l'image. Supposons pour simplifier que les images reçues sont carrées et font n pixels de côté:

def seuil(tab0, seuil=128):
    """ reçoit un tableau 2D représentant une image en niveaux de
    gris et renvoie un tableau de cette même image dont les valeurs
    seront 0 et 255  (0 si valeur initiale < 128, 255 sinon)"""
    lig,col = tab0.shape
    tab1 = np.zeros((lig,col))
    for l in range(lig):
        for c in range(col):
            if tab0[l,c]< seuil :
                tab1[l,c]=0
            else :
                tab1[l,c]=255
    return tab1

Que prendre comme taille de données? Quelle est la complexité?

Réponse

On peut prendre comme taille la valeur de la largeur (\(n\)). Dans tous les cas, on parcourt tout le tableau 2D (double boucle), avec à chaque passage un test et une affectation. Complexité quadratique \(O(n^2)\).

Exercice 4 : Reconnaissez-vous la méthode de tri utilisée dans la fonction suivante? Déterminer sa complexité.

def tri(S):
    n = len(S)
    for i in range(n-1,1,-1):
        for j in range(0,i):
            if (S[j]>S[j+1]) :
                per(S,j,j+1)
    return S
Réponse

On reconnait le tri à bulles. Lors de chacun des passages dans la boucle, on effectue une comparaison et éventuellement une permutation (par hypothèse, temps constant). Il reste donc à déterminer le nombre de passages dans la boucle :

\[ T(n)= \sum_{i=2}^{n-1} \sum_{j=0}^{i-1} C = C\times\sum_{i=2}^{n-1}i=C\times\dfrac{(n+1)(n-2)}{2}=O(n^2) \]

Complexité quadratique \(O(n^2)\).

On pourra consulter le site Interstices pour une visualisation du procédé et de sa complexité...

3. Cas plus élaborés

On a vu ici simplement le concept de complexité. Cette notion se travaille dans tout algorithme. Ainsi on travaillera à nouveau cette notion de complexité dans d'autres chapitres :

  • on verra comment calculer des complexités avec des algorithmes récursifs
  • on en parlera aussi dans un chapitre consacré à la dichotomie
  • et dans un chapitre sur les tris

IV. Temps de calculs usuels

Pour avoir un ordre de grandeur, voici un tableau donnant les temps mis par une machine cadencée à \(10^6\) opérations par seconde, pour traiter un problème dont la taille des données est n:

Taille \(\log_2 n\) \(n\) \(n\log_2 n\) \(n^2\) \(2^n\)
10 0.003 ms 0.01 ms 0.03 ms 0.1 ms 1 ms
100 0.006 ms 0.1 ms 0.6 ms 10 ms \(4.10^{14}\) siècles !
1000 0.010 ms 1 ms 10 ms 1 s
\(10^4\) 0.013 ms 10 ms 0.1 s 100 s
\(10^5\) 0.016 ms 100ms 1.6 s 3 h
\(10^6\) 0.020 ms 1 s 20 s 10 jours

V. Complexité en espace

Il faut savoir que la complexité en temps que l'on vient d'étudier n'est pas la seule qui a de l'importance. Parfois on s'intéresse aussi à la complexité en espace, c'est à dire à la quantité de mémoire utilisée pour résoudre un problème. Typiquement, si l'on veut trier un tableau, on peut imaginer avoir besoin de dupliquer le tableau initial (on double l'espace utilisé) ou bien trier le tableau en place c'est à dire utiliser uniquement l'espace occupé par les données.

VI. TD : visualiser des complexités

TD L1 : visualisation de complexités

Dans le TD L1, on va essayer de contrôler la complexité estimée de certains algorithmes à l'aide de graphiques:

TD L1 version interactive capytale

Versions html : Énoncé et Correction (à venir)