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
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.
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)\) où \(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))\) où \(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]
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)\)