Skip to content

Texte

Application des règles de calcul

Note : Les algorithmes dont les codes python sont donnés ici sont expliqués dans le chapitre 8 du cours : http://di.ulb.ac.be/verif/tmassart/Prog/html/chapitre8.html#recherche-sequentielle

Ayant ces règles d'évaluation du grand \(O\) pour chaque type d'instruction, le calcul de la complexité d'un algorithme se fait en partant des complexités des instructions simples, et en calculant, de proche en proche, les complexités des instructions non simples à partir des résultats déjà calculés. Ces calculs procèdent en quelque sorte par des regroupements en suivant la structure de l'algorithme.

Complexité de la recherche du minimum

Prenons l'exemple de la recherche du minimum c'est-à-dire du traitement suivant (après traduction en utilisant un while en ayant n = len(s):

1     res = s[0]                 
2     i = 1                      
3     while i < len(s):                
4        if s[i] < res:             
5           res = s[i]           
6        i = i + 1               
7     return res                 
Nous supposons que chaque instruction simple est prise en compte pour le calcul de la complexité.

Rappelons que le traitement, comme tout algorithme, peut être décomposé sous forme d'arbre syntaxique comme donné par la figure suivante où chaque noeud représente une instruction Python simple ou composée.

Arbre syntaxique du code  de recherche du minimum

Décomposition d'un traitement en suivant la structure

Les noeuds sans fils, appelés les feuilles de l'arbre, correspondant aux instructions 1, 2, 5, 6 et 7, représentent des instructions d'assignations simples ou return qui, d'après la règle 1, sont en \(O(1)\).

De ce fait, d'après la règle 3, le noeud 4-5 correspondant à l'instruction if est en \(O(1)\).

D'après la règle 2, la complexité de la séquence d'instructions 4-6 est en \(O(1)\).

On peut maintenant évaluer la complexité du while (noeud 3-6), il s'exécute \(n-1\) fois et la complexité du corps de la boucle est, comme on vient de le voir, en \(O(1)\). Donc d'après la règle 4, la complexité du while est en \(O(n)\).

Finalement, d'après la règle 2, la complexité de tout le traitement est en \(O(1+1+n+1)\) qui peut être simplifié par \(O(n)\).

Note

  • Si, par exemple, un algorithme \(A\) est en \(O(n)\) et un algorithme \(B\) est en \(O(n^2 )\), \(A\) est 'meilleur', en terme, de complexité que \(B\).

    Par contre si \(A\) et \(B\) sont tous les deux en \(O(f(n))\), il faut détailler le calcul de la complexité pour déterminer lequel est plus complexe que l'autre.

  • D'après la définition du \(O\), l'algorithme de recherche du minimum est en \(O(n)\) et donc trivialement également en \(O(n^2)\), \(O(n^3)\), ..., \(O(n^n)\). Lorsque l'on cherche la complexité d'un algorithme, on essaye bien évidemment de donner la valeur la plus précise (Exemple: \(O(n)\) pour la recherche du minimum)

  • Rappelons que l'on peut évaluer plusieurs complexités différentes. Par exemple, pour les algorithmes de tris de liste, on peut regarder la complexité en terme de nombre d'instructions ou seulement regarder les instructions qui effectuent des déplacements d'éléments (le déplacement d'un élément peut prendre beaucoup plus de temps que les autres instructions). Certains tris sont en \(O(n^2)\) si l'on regarde toutes les instructions, mais en \(O(n)\) en terme de déplacement d'informations.

Complexité de la recherche séquentielle et dichotomique

Il est facile de voir que l'algorithme de recherche séquentielle, vue plus haut, est également en \(O(n)\)\(n\) est la longueur de la liste et en supposant que les tests s[i] == x sont effectués en \(O(1)\).

Recherche dichotomique

Une version Python de l'algorithme classique de recherche dichotomique de l'indice d'un élément dans un vecteur (une liste python) s est donné ici :

def recherche_dichotomique(s,x):                                # O(log n)
  """Renvoie un indice où se trouve la valeur de x dans s
  None s'il n'existe pas.
  La méthode de recherche dichotomique ou binaire est utilisée.
  """
  bi, bs = 0, len(s)                                            # O(1)
  m = (bi+bs)//2                                                # O(1)
  while bi < bs and x != s[m][0]:                               # O(log n) (O(log n) itérations)
     m = (bi+bs)//2                                                # O(1)
     if s[m][0] < x:                                               # O(1)
        bi = m+1                                                     # O(1)
     else:                                                         # O(1)
        bs = m  # x est avant ou est trouvé                          # O(1)

  if  len(s) <= m or s[m][0] != x:  # pas trouvé                # O(1)
      m = None                                                    # O(1)
  return m                                                      # O(1)

Attention, ici on suppose que chaque élément de s contient un couple avec la clé en sous composante 0 et une information satellite en sous composante 1. Ainsi s[m][0] représente la clé de l'élément d'indice m dans la liste et s[m]représente tout l'élément (clé et information satellite).

Pour calculer la complexité de la recherche dichotomique, en utilisant les règles vues précédemment, on peut assez rapidement observer que la complexité moyenne ou maximale en nombre d'actions élémentaires de cet algorithme est en \(O(f(n))\)\(f(n)\) est le nombre respectivement moyen \((f_{moyen(n)})\) ou maximum \((f_{max(n)})\) de fois que la boucle while est exécutée.

Pour évaluer \(f_{max(n)}\), commençons par analyser le comportement de l'algorithme. Nous pouvons tout d'abord remarquer qu'à chaque tour de boucle, au pire des cas, l'intervalle de recherche est divisé par deux, quelle que soit la valeur de x.

La figure suivante donne une évolution possible de l'intervalle de recherche dans s pour une liste à 100 éléments en supposant que x n'est pas dans s mais que s[40] < x < s[41]

intervalle de recherche dichotomique

Evolution de l'intervalle de recherche lors d'une recherche dichotomique

Le while s'exécute donc au maximum 7 fois. De façon générale on peut voir que:

\(2^{f_{max}(n)-1} \leq n < 2^{f_{max}(n)}\)

et donc que \(f_{max(n)} <= \log_2(n) + 1\)

La recherche dichotomique a donc une complexité maximale en \(O(ln \; n)\). On peut calculer que la complexité moyenne (en supposant ou non que x est dans s) est également en \(O(ln \; n)\).

Notons que dans la section algorithmique, nous verrons que cette complexité peut être calculée avec le master theorem (https://fr.wikipedia.org/wiki/Master_theorem) et la relation de récurrence \(T(n) = T(n/2) + O(1)\)