Texte

Calcul du grand \(O\)

Classes de complexité

Si on peut calculer qu'un algorithme est un \(O(n^2 )\), il n'est pas intéressant, même si cela est trivialement vrai, d'exprimer le fait que \(T(n)\) est en \(O(n^3 )\), \(O(n^4 )\), ....

Lorsque l'on évalue le grand \(O\) d'une complexité, c'est la meilleure estimation "simple" que l'on cherche à obtenir.

Ainsi on classe généralement les complexités d'algorithmes selon leur grand \(O\) comme donné par la table suivante :

D'abord les code qui prennent un temps borné qui sont en \(O(1)\) complexité constant ensuite les algorithmes de complexité logarithmique en \(O(log \, n)\) ensuite linéaires en \(O(n)\) ensuite \(O(n \, log \, n)\) ensuite les algorithmes à complexité polynomiales \(O(n^2 )\) : quadratique,
\(O(n^3 )\) , cubique, etc

Ensuite les complexités exponentielles avec \(O(2^n )\) , \(O(3^n )\) , ETC, \(O(n^n )\) , exponentiel en base n et ainsi de suite

Classes de complexité

Remarquons qu'en vertu du fait que pour tout a,b positif : \(log_a n = (log_a b).(log_b n)\)

et comme \(log_a b\) est une constante pour \(a\) et \(b\) fixés, si \(T(n)\) est en \(O(log_a n)\) il est également en \(O(log_b n)\). (la base du logarithme n'a donc pas d'importance pour exprimer un grand \(O\)). Notons encore que ceci n'est pas vrai pour la base des complexités exponentielles.

Règles de calcul du grand O

Donnons ici un petit nombre de règles permettant d'évaluer la complexité d'un algorithme. Ces règles ne donnent en général qu'une surapproximation parfois grossière; une estimation plus précise devant tenir compte du fonctionnement de l'algorithme.

Tout d'abord, l'évaluation se fait en "bottom-up", depuis les instructions simples, vers les instructions plus complexes. Si l'on regarde l'arbre syntaxique du code de la recherche du minimum, on détermine donc d'abord la complexité des feuilles (avec les instructions 1, 2, 5, 6 et 7) pour ensuite remonter en déterminant la complexité de l'instruction if et ensuite du while pour enfin avoir la complexité de tout le code qui correspond à la racine de l'arbre syntaxique.

   1  res = s[0]                
   2  i = 1                      
   3  while i < n     :           
   4     if s[i] < res:             
   5        res = s[i]           
   6     i = i + 1               
   7  return res                 

Règle 1 (unité)

Il faut clairement définir l'unité utilisée et les éléments pris en compte. Ainsi, si l'on regarde la complexité en temps d'exécution et si l'on tient compte des tests élémentaires, des assignations, des lectures de données et des écritures de résultats, une assignation à une variable simple, une instruction input ou print d'une donnée simple, ou l'évaluation d'une expression (ou d'une condition) simple ne donnant pas lieu à l'exécution de fonctions, prend un temps constant fixé et est donc en \(O(1)\). L'assignation à des objets plus complexes ou des input ou print de données plus complexes peut ne plus être en \(O(1)\) en fonction de leur taille qui peut dépendre de la taille du problème (\(n\)).

Par exemple, en comptabilisant le temps de toutes les instructions, chacune des instructions suivantes est en O(1) :

  x = 3.14
  z = 3 ** 25 + x - 36
  x == 3.14
  print(3.14)
  y = int(input()) (pour une petite valeur lue)

Règle 2 (séquence)

• Si un traitement 1 prend un temps \(T_1(n)\) qui est en \(O(f_1(n))\) et
• un traitement 2 prend un temps \(T_2(n)\) qui est en \(O(f_2(n))\) alors
• le traitement 1 suivi du traitement 2 prend \(T_1(n) + T_2(n)\) et est en \(O(f_1(n) + f_2(n)) = O (max(f_1(n) , f_2(n)))\)

où max prend la fonction qui croît le plus vite c'est-à-dire de plus grand ''ordre''.

Par exemple si \(T_1(n)\) est en \(O(n^2 )\) et \(T_2(n)\) est en \(O(n)\), \(T_1(n) + T_2(n)\) est en \(O(n^2 + n) = O(n^2)\)

En particulier une séquence d'instructions simples (dont on tient compte) ne faisant aucun appel à une procédure ou à une fonction ne dépend pas de \(n\) et sont donc en \(O(1)\).

Par exemple la séquence de toutes les instructions simples précédentes est en \(O(1)\).

Règle 3 (if)

Pour un if condition: instruction_1 else: instruction_2

où

• instruction_1 est en \(O(f_1(n))\)
• instruction_2 est en \(O(f_2(n))\)
• l'évaluation de la condition est en \(O(g(n))\)

suivant le test, le if sera en \(O(max(f_1(n),g(n)))\) ou en \(O(max(f_2(n),g(n)))\) et peut être borné par: \(O(max(f_1(n), f_2(n), g(n)))\)

Notons que souvent \(g(n)\) est en \(O(1)\).

Par exemple le code suivant est en \(O(1)\)

   a = int(input())                          # O(1)
   if (a > 100):                             # O(1)
       print('a dépasse le centaine')         #   O(1)
   else:                                     # O(1)
       print('a ne dépasse pas la centaine')  # O(1)

Cette règle peut être généralisée pour une instruction if ayant une ou des parties elif.

Règle 4 (while)

Pour un while, sachant que - le corps de la boucle est en \(O(f_1(n))\) et que - l'évaluation de la condition est en \(O(f_2(n))\), - si on a une fonction en \(O(g(n))\) qui donne une borne supérieure du nombre de fois que le corps sera exécuté, alors

le while est en \(O(f(n).g(n))\) avec \(f(n) = max(f_1(n),f_2(n))\).

Par exemple, la fonction de recherche dans une liste s, de l'indice i de l'élément de s dont la composante \(s[i][0]\) vaut x en est \(O(n)\) où \(n\) est la taille de s(on suppose que les éléments de s sont des tuples.)

def recherche(s,x):                      # O(n)
   """Renvoie l'indice où se trouve la valeur x dans s.

   None si x n'existe pas.
   """
   i = 0                                 # O(1)
   while i < len(s) and s[i][0] != x:    # O(n) (cond en O(1), nb d'it en O(n))
      i = i+1                              # O(1)
   if i == len(s)                        # O(1)
      i = None # pas trouvé                # O(1)
   return i                              # O(1)

Règle 5 (for)

Pour une boucle for, il suffit de ''traduire'' le for en while.

Donnons de simples exemples de complexité avec des for

  for i in range(100):
    print(i)

est en \(O(1)\) car le nombre d'itération est de \(100\) qui est en \(O(1)\).

Par contre, pour une liste s de taille \(n\) d'entiers (de petite valeur) où \(n\) est un paramètre qui dépend de la taille du problème :

   for elem in s:
       print(elem)

est en \(O(n)\).

Règle 6 (fonction)

L'appel à une fonction est en \(O(f(n))\) correspondant à la complexité du traitement de cette fonction pour les paramètres effectifs donnés.

Par exemple on peut voir que la complexité de la fonction ecrit_carre_nxn est en \(n^2\) où n est l'entier reçu en paramètre. Si l'on appelle cette fonction avec la valeur taille ** 3 où taille est un entier lu, la complexité résultant de l'exécution est donc en \(O(taille^6)\) (soit \(O(n^2)\) pour \(n = taille^3\)).

   def ecrit_carre_nxn(n):        #     complexité de la fonction O(n^2)
       for i in range(n):
            for j in range(n):
                print('X', end='')
            print()

   taille = int(input())                                  #     O(1)
   ecrit_carre_nxn(taille**3) # carré de taille taille^3  #     O((taille^3)^2) = O(taille^6)

On peut raffiner ces calculs, selon que l'on essaye de trouver une complexité minimale, moyenne ou maximale. Ce raffinement se situera dans le nombre de fois qu'une instruction sera répétée, ayant par exemple certaines hypothèses sur la probabilité que certaines conditions de if ou de boucles sont vérifiées.