Introduction¶
Nous avons vu que si l’on cherche un élément dans une liste de taille n, alors dans le cas où l’élément se trouve à la fin de la liste nous aurons à effectuer n opérations. On dit que la complexité est linéaire et on note cela \(O(n)\).
On va voir que dans le cas où le tableau est trié, on peut faire bien mieux et atteindre une complexité logarithmique.
Mais, quand on dit “bien mieux”, quelle différence y-a-t-il entre une complexité linéaire et une complexité logarithmique ?
1) Linéaire et logarithmique¶
On considérera le logarithme en base 2 dans ce cours.
Définition : logarithme base 2
La fonction logarithme de base 2 est la fonction logarithme telle que :
\(log_2(2) = 1\)
Et plus généralement :
\(log_2(2^n) = n\)
Une fonction logarithmique croît beaucoup plus lentement qu’une fonction linéaire.
Par exemple : \(log_2(4 294 967 296) = 32\)
Si on a une complexité linéaire, on aura de l’ordre de 4 millions d’opérations, et dans le cas d’une complexité uniquement de l’ordre de 32 opérations.
D’ailleurs on voit dans les courbes ci-dessus, que la fonction logarithme lorsque n s’approche de l’infini est relativement proche d’une fonction de classe constante.
Etudions désormais le fonctionnement de l'algorithme de recherche dichotomique.
2) L’algorithme de recherche dichotomique¶
Etymologie
Le mot “dichotomie” vient du grec dikha (en deux) et tomos (couper).
Supposons que l’on souhaite trouver le nombre 18 dans la liste L suivante :
Cette liste est triée donc on va pouvoir appliquer notre algorithme :
Etape 1 : On cherche l’élément se trouvant au centre de la liste : on effectue une division entière entre l’indice du premier élément de la liste et le dernier élément de la liste :
On effectue une division entière pour gérer le cas où on a un nombre d’éléments pairs, et donc où la somme de l’indice de début et l’indice de fin est impaire.
Etape 2 : On compare la valeur se trouvant au centre de la liste (à l’indice 4 dans notre exemple), soit 25. On compare 25 et la valeur que l’on recherche, 18. 25 est plus grand que 18, donc on sait que l’on doit chercher 18 à gauche de 25 puisque la liste est triée par ordre croissant.
On répète à nouveau l’étape 1 mais en cherchant dans la partie à gauche de 25. On cherche alors 18 sur la partie gauche de la liste:
Le milieu de cette partie de la liste L se trouve à l’indice
car la fin se trouve à l’indice 3. La valeur du milieu correspond donc à 5.
On répète à nouveau l’étape 2, on compare 18 et 5. On constate que 18 est plus grand que 5, on doit donc chercher 18 à droite de 5.
On divise à nouveau l’espace de recherche en deux en commençant à l’indice juste après celui de 5 :
puisque le début de l’espace de recherche commence à l’indice 2 et se termine à l’indice 3. On compare 7 et 18. 18 est plus grand que 7, on cherche donc à droite de 7.
Il nous reste alors une seule valeur
Le milieu correspond à l’indice de 18
L'élément au milieu est égal à 18, on a donc trouvé 18, on renvoie l’indice i qui correspond à la position de la valeur recherchée. Dans ce cas on renvoie 3.
Si on n’avait pas trouvé 18, on aurait alors renvoyé None (ou éventuellement -1).
Voici le code correspondant à cet algorithme en Python :
def recherche_dichotomique(valeur, tableau):
gauche = 0
droite = len(tableau) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if valeur == tableau[milieu]:
return milieu
elif tableau[milieu] > valeur:
droite = milieu - 1
else:
gauche = milieu + 1
return None
Malgré sa simplicité, cet algorithme est quelquefois implémenté de manière erronée. A titre d’exemple dans la version implémentée en Java dans la librairie officielle il existait un bug depuis des dizaines d’années. Ce bug était lié à un possible dépassement (overflow) lors de l’addition de deux entiers de grande taille lors de l’appel à (gauche + droite). Ce problème arrive très rarement en Python étant donné que les entiers sont de taille arbitraire, ce qui veut dire que la limite est liée à la quantité de mémoire disponible sur la machine.
Exemple de code Java permettant de reproduire ce bug :
class Main {
public static int recherche_dichotomique(int valeur, int[] tableau){
int milieu = 0;
int gauche = 0;
int droite = tableau.length - 1;
while (gauche <= droite){
milieu = (gauche + droite) / 2;
if(tableau[milieu] == valeur){
return milieu;
}
else if (tableau[milieu] < valeur){
gauche = milieu + 1;
}
else{
droite = milieu - 1;
}
}
return -1;
}
public static void main(String args[]) {
int[] intArray = new int[1200000000];
for (int i = 0; i < 1200000000; i++){
intArray[i] = i;
}
intArray[1190000017] = 1190000016;
System.out.print(recherche_dichotomique(1190000017, intArray));
}
}
Pour corriger ce bug et donc éviter le dépassement, il faut prendre en compte le fait que droite est supérieur ou égal à gauche et effectuer l'addition suivante :
gauche + (droite - gauche) / 2
Nous avons annoncé que la complexité de cet algorithme était logarithmique. Analysons la complexité de cet algorithme.
3) Complexité algorithmique¶
Nous allons montrer pourquoi la complexité de cet algorithme est logarithmique.
Dans le pire des cas, la valeur que nous recherchons ne se trouve pas dans le tableau. A la toute dernière étape il nous reste uniquement une valeur dans le tableau que nous comparons alors avec la valeur recherchée.
Supposons que nous partons d’un tableau de taille \(n\). A chaque étape nous divisons la taille du tableau par deux.
- A la première itération, la taille du tableau est égale à \(\Large{\frac{n}{2}}\).
- A la deuxième itération la taille du tableau est égale à \(\Large{\frac{n}{4}}\).
- Plus généralement, à la k ième itération la taille du tableau est égale à \(\Large{\frac{n}{2^{k}}}\).
Pour déterminer le maximum d’itérations possible de l’algorithme il faut résoudre l’équation \(\Large{\frac{n}{2^{k}} = 1}\).
On utilise le logarithme base 2 pour résoudre cette équation.
\(n = 2^k\)
\(log_2(n) = log_2(2^k)\)
Soit :
\(k = log_2(n)\).
On peut aussi représenter cette recherche sous la forme d’un arbre binaire :
On voit que dans le pire des cas, la complexité est précisément de ⌊\(log_2(n) + 1\)⌋, ce qui correspond à la hauteur de l’arbre binaire, c'est-à-dire à la profondeur maximale de l'arbre si on le parcours de la racine (ici 8), jusqu’à une des feuilles qui se trouve tout en bas de l’arbre. Cette complexité est bien de l’ordre de \(log_2(n)\)
Prouvons que cet algorithme est correct, c’est à dire qu’il renvoie bien le bon résultat et se termine nécessairement (pas de boucle infinie).
4) Preuve de correction¶
Un algorithme correct, c'est-à -dire un algorithme qui renvoie bien le résultat attendu (la valeur recherchée ici) en fonction des données en entrée (ici le nombre que l’on cherche et une liste de nombres triés par ordre croissant), doit se terminer. Commençons par montrer dans un premier temps que l’algorithme donne bien le bon résultat (correction partielle) et montrons ensuite qu’il se termine.
4.1) Preuve de correction partielle¶
Pour montrer la correction partielle, nous allons utiliser un invariant de boucle, c’est à dire une propriété qui est vraie avant l’entrée dans la boucle, vrai avant la nième itération et qui reste vraie avant la n + 1 ième itération (ce qui revient à dire qu’elle est vraie à la fin de la nième itération). Nous pouvons choisir comme invariant le fait que si la valeur recherchée est dans le tableau, alors elle se situe entre l’indice gauche et l’indice droite inclus.
Une des préconditions de cet algorithme (c’est à dire une condition qui est requise avant l’exécution de l’algorithme) est que le tableau est trié.
Initialisation
Avant l'exécution de la boucle, la propriété est vraie, puisque gauche = 0 et droite = taille du tableau - 1, ce qui revient à dire que si la valeur recherchée est dans la tableau alors elle est dans le tableau (on appelle cela une tautologie).
Conservation
Supposons que la propriété P : “si la valeur recherchée est dans le tableau, alors elle se situe entre l’indice gauche et l’indice droite inclus” est vraie avant la k ième itération. Alors, soit :
-
La valeur se trouve au centre du tableau et l’indice milieu est renvoyé et l’algorithme est correct. Pas besoin d’utiliser l’invariant dans ce cas.
-
Soit la valeur recherchée est inférieure à la valeur se trouvant au milieu du tableau et alors, puisque le tableau est trié, la valeur (si elle est présente) se trouve entre l’indice gauche et milieu - 1, en posant droite = milieu - 1 (comme dans le code), on constate que la propriété est vérifiée.
-
Soit la valeur recherchée est supérieure à la valeur se trouvant au milieu du tableau et alors, puisque le tableau est trié, la valeur (si elle est présente) se trouve entre l’indice milieu + 1 et droite. En posant gauche = milieu + 1 (comme dans le code), on constate que la propriété est vérifiée.
Conclusion
Ainsi si la propriété P est vraie avant d’entrer dans la boucle et au début d’une itération quelconque et de l’itération suivante. Elle est donc également vraie à la fin de l’exécution de la boucle, ce qui prouve la correction de l’algorithme.
4.2) Preuve de terminaison¶
Pour montrer que l’algorithme se termine on va chercher ce qu’on appelle un “variant de boucle”, c’est une suite dont les termes sont positifs et qui est strictement décroissante à chaque itération.
On remarque qu’à chaque étape la différence droite - gauche est décroissante.
Au début nous avons gauche <= milieu <= droite.
Ensuite, nous avons trois cas exclusifs (qui ne peuvent pas avoir lieu de manière simultanée) possibles :
-
Si
tableau[milieu]correspond à la valeur alors l’algorithme renvoie l’indice que l’on cherche et se termine. -
Si
tableau[milieu]est supérieur à la valeur recherchée, on modifie la valeur de droite. Si on appelle cette valeur droite2, on a alors droite2 = milieu - 1 < milieu et donc droite2 - gauche < milieu - gauche <= droite - gauche
Donc l’invariant a strictement décru. -
Si
tableau[milieu]est inférieur à la valeur recherchée, on modifie la valeur de gauche. Si on appelle cette valeur gauche2, on a alors gauche2 = milieu + 1 > milieu et donc droite - gauche2 < droite - milieu <= droite - gauche
Donc l’invariant a strictement décru.
La condition de la boucle étant gauche <= droite, la boucle s’arrête lorsque le variant de boucle n’est plus positif ou nul.
Conclusion¶
On a vu que cet algorithme était très efficace lorsqu’il s’agissait de rechercher une valeur dans un tableau trié. On remarquera qu’à chaque itération l’espace de recherche (c'est-à-dire l’ensemble des valeurs sur lesquelles ont doit rechercher l’élément) est divisé par deux.
Cette technique algorithmique qui consiste à diviser un problème : rechercher un élément dans une liste triée, en sous-problèmes de plus petite taille : rechercher un élément dans une liste dont la taille est la moitié de la liste précédente, a bien d’autres applications.
En terminale nous verrons notamment l’utilisation de cette technique appelée “diviser pour régner” pour trier les éléments d’une liste dans le cadre du tri fusion.