Diviser pour régner


Retour vers la recherche dichotomique

Rechercher une valeur dans un tableau

On commence par un algorithme en apparence très simple: on dispose dun tableau de valeurs, et on cherche à savoir si une valeur donnée est présente dans le tableau, ou non (alternativement, on peut vouloir rechercher le premier indice où se trouve une telle valeur).

Lalgothme le plus naturel semble le meilleur:

def recherche(tableau, but):
   for valeur in tableau:
      if valeur == but:
         return True
   return False

Notons quil nest pas possible de savoir si la valeur à rechercher est absente du tableau avant davoir examiné toutes les valeurs du tableau: à cause de cela, on en déduit immédiatemment que la complexité dans le pire des cas est proportionnelle à la taille du tableau \(N\). On dit quil sagit dun algorithme de complexité linéaire.

Comme la valeur à rechercher peut très bien se trouver à la dernière position, il est impossible de trouver un algorithme plus rapide, car dans le pire des cas il faudra obligatoirement examiner toutes les valeurs présentes avant de conclure.

Recherche dans un tableau trié

Supposons à présent que les valeurs du tableau sont triées dans lordre croissant. Peut-on améliorer lalgorithme précédent afin de le rendre plus efficace ?

Une première amélioration très simple vient à lesprit: dès que lon tombe sur une valeur supérieur à la valeur à rechercher, on peut stopper la recherche car toutes les valeurs suivantes seront elles aussi supérieures. Puisque lon souhaite stopper lalgorithme préventivement, il faut utiliser une boucle tant que (rappelons que linstruction break de python nest pas au programme de NSI et est aussi bannie de la plupart des cours dalgorithme dans lenseignement supérieur).

def recherche_ordonnée(tableau, but):
   i = 0
   N = len(tableau)
   while tableau[i] <= but and i < N:
      if tableau[i] == but:
         return True
      i += 1
   return False

Lorsque la boucle est terminée, on a soit la condition i >= N qui signifie que tout le tableau a été parcouru sans succès, soit la condition tableau[i] > but qui signifie quil est inutile de poursuivre la recherche: on peut donc bien renvoyer False.

La complexité de cet algorithme est-elle améliorée ? Il est difficile dévaluer si et quand la recherche pourra sinterrompre prématurément. En outre, il est toujours possible que la valeur à rechercher soit la dernière du tableau.

La complexité dans le pire des cas reste donc linéaire.

Un algorithme optimal: la recherche dichotomique

Il est cependant possible de faire bien mieux que cela avec un tableau trié, en sinspirant du jeu “plus petit plus grand”

  • On regarde lélément au milieu du tableau: sil est supérieur à la valeur recherchée, on sait que celle-ci ne pourra se trouver que dans la première moitié du tableau, et on réduit alors la recherche à cette première moitié. Si au contraire lélément central est inférieur, on doit réduire la recherche à la deuxième moitié du tableau, car lélément à rechercher ne peut se trouver que là.
  • On peut poursuivre ainsi, en subdivisant à chaque étape les sous-tableaux en deux moitiés à peu près égales (à un élément près), et en recommençant à létape précédente.
  • On finira par arriver à un tableau de longueur 1, contenant (ou pas) lélément à rechercher.

Le fait de couper le tableau en deux parties donne son nom à lalgorithme: dichotomie signifie couper en deux.

Plus précisément, on va utiliser deux indices \(g\) et \(d\) (pour gauche et droite) indiquant lintervalle dans lequel doit seffectuer la recherche.

Supposons que lon dispose dun tableau ordonné t, de longueur N.

  1. Au départ, on aura g = 0 et d = N - 1.

  2. On calcule lindice au milieu de lintervalle de recherche: m = (g + d) // 2. On utilise une division euclidienne afin de sassurer que cet indice est bien un entier. Trois cas peuvent se produire:

    • Si t[m] == but, on trouvé la valeur à rechercher.
    • Sinon, si t[m] < but, la valeur à rechercher se trouve (peut-être) dans la seconde moitié. On gardera la valeur actuelle de d, mais on prendra à présent g = m + 1. Reprendre à létape 1.
    • Sinon, on a nécessairement t[m] > but et la valeur à rechercher est peutêtre dans la première moitié. On gardera la valeur actuelle de g mais on posera d = m - 1. Reprendre à létape 1.
  3. Si à un moment donné on a g > d (ce qui est possible avec les instructions g = m + 1 ou bien d = m - 1), on sait que lon peut interrompre la recherche car la valeur ne se trouve pas dans le tableau.

Une implémentation de la recherche dichotomique en python

def recherche_dichotomique(tableau, but):
   g = 0
   d = len(tableau) - 1
   while g <= d:
      m = (g + d) // 2
      if tableau[m] == but:
         return True
      elif tableau[m] < but:
         g = m + 1
      else:
         d = m - 1
   # La recherche n'a rien donné
   return False

Preuve de la correction de cet algorithme de recherche dichotomique

Comment prouver que cet algorithme fonctionne, cest-à-dire quil renvoie le bon résultat et quil ne sarrête et ne boucle pas indéfiniment ?

On considère pour cela la valeur L = d - g + 1 qui est la largeur de lintervalle de recherche, cest-à-dire le nombre de valeurs quil y a entre les indices g et d (inclus). À chaque étape, cet entier sera divisé par 2 (puisquon ne garde quune seule moitié de lintervalle de recherche), arrondi à lentier inférieur. On a donc une suite de valeurs positives strictement décroissantes. Or, une suite dentiers positifs strictement décroissantes doit nécessairement être finie en mathématique: lalgorithme ne peut donc pas boucler indéfiniment.

Voir lexplication plus précise dans le paragraphe suivant, où lon cherche à évaluer précisément le nombre détapes dans le pire des cas.

On dit que L = g - d + 1 est un variant de lalgorithme: cest une quantité entière positive qui décroit au minimum dune unité à chaque passage de la boucle, garantissant ainsi la complétion en un temps fini de lalgorithme.

Par ailleurs, au départ, on peut avoir deux situations:

  • Si la valeur but est comprise entre la première et la dernière valeur du tableau, on aura alors la contrainte tableau[g] <= but <= tableau[d], et cette contrainte restera valable à chaque étape de la boucle, puisque les changements effectués soit sur g, soit sur d, garantissent justement que cette contrainte reste vérifiée tout en divisant la largeur de la recherche par deux: on dit que la condition tableau[g] <= but <= tableau[d] est un invariant de la boucle. Cet invariant garantit que, si la valeur à rechercher se trouve bien dans le tableau, elle sera toujours trouvée parce quelle est bien comprise entre les valeurs tableau[g] et tableau[d].
  • Si la valeur but est plus petite ou plus grande que toutes les valeurs du tableau, alors quoi quil arrive lalgorithme sarrêtera en nayant pas trouvé la valeur, ce qui est la réponse correcte. On peut même tester et éliminer ce cas fréquent en début dalgorithme afin de ne pas faire une recherche inutile:

    def recherche_dichotomique(tableau, but):
      g = 0
      d = len(tableau) - 1
      while g <= d and tableau[g] <= but <= tableau[d]:
         m = (g + d) // 2
         if tableau[m] == but:
            return True
         elif tableau[m] < but:
            g = m + 1
         else:
            d = m - 1
      # La recherche n'a rien donné
      return False

On a rajouté explicitement la contrainte de linvariant dans la condition de la boucle while: celle-ci ne sexécutera pas du tout si cette contrainte nest pas vérifiée au départ.

À retenir:

  • Un variant est une suite strictement décroissante dentiers naturels associé à chaque étape de lalgorithme. Celle-ci ne pouvant pas être mathématiquement infinie, elle garantit la terminaison de lalgorithme, cest-à-dire que celui-ci ne pourra pas boucler infiniment.

  • Un invariant est une condition qui est toujours vérifiée à chaque étape de lalgorithme, et permet de démontrer (sil est bien choisi) que lalgorithme donne toujours la bonne réponse.

Trouver des variants et/ou des invariants peut savérer très compliqué pour un algorithme arbitraire.

Complexité de lalgorithme de recherche dichotomique

La complexité est bien plus compliquée à évaluer. À chaque étape (passage de la boucle), le nombre de valeur à rechercher est à peu près divisé par 2.

Pourquoi à peu près ? Plus précisément (et cela ressemble énormément au raisonnement utilisé en mathématique pour déterminer la médiane dune série de données):

  • Si L = d - g + 1 est pair, alors à la moitié à gauche de la valeur dindice m = (g + d) // 2 comportera (L // 2) - 1 valeurs, celle de droite en comportera L // 2. Le cas le plus défavorable étant L // 2, on considérera cette valeur pour nos calculs.
  • Si L = d - g + 1 est impair, alors il y aura une valeur centrale dindice m = (g + d) // 2, et les deux moitiés du tableau comporteront exactement L // 2 valeurs.

Dans tous les cas, L prendra pour valeur suivante L // 2: cest pour cela que lon a écrit à peu près divisé par 2 un peu plus haut. Pour un entier donné, on a la garantie que L // 2 est strictement inférieur à L, ce qui montre que L est bien un variant de la boucle.

Voyons cela sur un exemple avec un tableau de taille \(N = 100\).

  • À la première étape, on gardera une moitié de taille 49 ou 50. Supposons que ce soit 50.
  • À létape suivante, on aura un tableau de taille 24 ou 25. Prenons le cas défavorable \(L = 25\).
  • À létape suivante, on aura un tableau nécessairement de taille 12.
  • À létape suivante, on aura un tableau de taille au plus 6.
  • puis un tableau de taille au plus 3.
  • puis un tableau de taille 1: la recherche sarrêtera nécessairement à ce moment là (si le tableau contient lélément à rechercher), ou bien à la suivante sil ny est pas.

Comptons: nous aurons au maximum 7 étapes (il peut y en avoir moins si lélément à trouver est lun des pivot dindice m examiné par une boucle), cest qui est largement inférieur à la valeur initiale \(N = 100\).

Est-il possible de calculer à lavance ce nombre 7 ? En fait oui: il suffit de remarquer que la plus petite puissance de 2 inférieure ou égale à 100 est \(2^6 = 64\), la puissance de 2 immédiatemment supérieure étant \(2^7 = 128\). Cest pour cela quil faut au maximum 7 étapes pour effectuer une recherche dichotomique.

Le principe est donc très simple: il suffit de trouver la plus petite puissance de 2 strictement supérieure à \(N\), cest-à-dire le plus petit entier \(k\) tel que \(N < 2^k\), le nombre détapes dans le pire des cas sera alors \(k\).

Il existe en mathématique une fonction réalisant exactement cela: cest la fonction \(\log_2\) (logarithme de base 2), qui renvoie exactement \(N\) lorsquelle est calculée sur \(2^N\), et un nombre réel pour les valeurs intermédiaires. On a par exemple \(\log_2(100) \approx 6,64\), ce qui est bien compris entre 6 et 7.

On peut démontrer de manière rigoureuse en mathématique que la complexité de lalgorithme de recherche dichotomique est proportionnelle à \(\log_2(N)\), ce qui est bien meilleur quune complexité linéaire. Par exemple avec \(N = 1000000000\) (un milliard), on aura \(\log_2(N) \approx 29,9\), soit au maximum 30 étapes de recherche. Difficile de faire mieux: en effet, dans le pire des cas on aura réellement besoin de ces 30 étapes (si lélément à trouver est détecté lors de la dernière étape uniquement, ou bien sil nest pas dans le tableau et selon la valeur que lon recherche).

Un algorithme de recherche dichotomique récursif

Rappelons lexplication informelle donnée initialement pour expliquer lalgorithme de recherche dichotomique en Première:

  • On regarde lélément au milieu du tableau: sil est supérieur à la valeur recherchée, on sait que celle-ci ne pourra se trouver que dans la première moitié du tableau, et on réduit alors la recherche à cette première moitié. Si au contraire lélément central est inférieur, on doit réduire la recherche à la deuxième moitié du tableau, car lélément à rechercher ne peut se trouver que là.
  • On peut poursuivre ainsi, en subdivisant à chaque étape les sous-tableaux en deux moitiés à peu près égales (à un élément près), et en recommençant à létape précédente.
  • On finira par arriver à un tableau de longueur 1, contenant (ou pas) lélément à rechercher.

Tel quil est écrit ici, on a limpression quil est structuré autour dune boucle (et cest effectivement comme cela que lon peut linterpréter en Première), alors quen réalité il sagit dune définition récursive. Reformulons légèrement cet algorithme:

  • Pour effectuer une recherche dichotomique sur un tableau, on commence par regarder lélément au milieu du tableau: sil est supérieur à la valeur recherchée, on sait que celle-ci ne pourra se trouver que dans la première moitié du tableau, et on effectue alors une recherche dichotomique sur cette première moitié. Si au contraire lélément central est inférieur, on doit effectuer la recherche dichotomique sur à la deuxième moitié du tableau, car lélément à rechercher ne peut se trouver que là.
  • On sarrête soit lorsque lélément central est la valeur à rechercher, soit lorsque le sous-tableau ne contient plus aucune valeur (largeur inférieure à 0).

Cette fois, la récursivité intrinsèque de lalgorithme apparaît explicitement. Donnons-en une implémentation en python. Nous utiliserons les mêmes paramètres \(g\) et \(d\) que pour limplémentation itérative de Première:

def recherche_dichotomique_rec(tableau, but, g, d):
   if g > d:
      # La "largeur" de la zone de recherche est négative: 
      # La recherche a été infructueuse
      return False
   else:
      # On sait que g <= d: la "largeur" de la zone est positive ou nulle
      # (nulle = il ne reste plus qu'un seul élément)
      m = (g + d) // 2
      if tableau[m] == but:
         return True
      elif tableau[m] < but:
         return recherche_dichotomique_rec(tableau, but, m + 1, d)
      else:
         return recherche_dichotomique_rec(tableau, but, g, m - 1)

def recherche_dichotomique(tableau, but):
   return recherche_dichotomique_rec(tableau, but, 0, len(tableau) - 1)

Cette implémentation récursive de lalgorithme est plus simple à comprendre que limplémentation itérative, car elle est plus proche de la description initiale de lalgorithme.

La complexité de lalgorithme est exactement la même en version récursive quitérative, puisque le nombre dappels récursifs est égal au nombre de passage de la boucle pour la version de Première.

Est-il possible de dépasser la pile dappel de python (en général 1000 appels maximum) ? Difficilement, car pour cela il faudrait que la taille du tableau \(N\) soit supérieure à \(2^{1000}\), ce qui donne environ \(10^{300}\), un nombre largement supérieur au nombre estimé datomes de lunivers (lordre de grandeur est denviron \(10^{80}\)). Aucune chance davoir assez de mémoire dans un ordinateur pour ne serait-ce que stocker un tableau aussi grand.

Le tri fusion

Principe du tri fusion

La méthodologie «diviser pour régner» peut être avantageusement utilisée pour trier une liste, donnant à la fois un algorithme simple à décrire, mais qui savérera aussi beaucoup plus efficace que les algorithmes de tri par insertion ou par sélection étudiés en classe de Première.

Le principe est schématisé ci-dessous:

tri fusion à 8 éléments

  • À chaque étape, on sépare la liste en deux sous-listes (flèches bleues sur le diagramme).
  • Lorsque toutes les sous-listes ont été décomposées, on les fusionne deux par deux (flèches rouges). Lopération de fusion prend 2 listes déjà triées (ce qui est notamment le cas pour les listes de longueur 1), et les combine en une unique liste elle aussi triée.

Lorsque le nombre déléments de la liste nest pas une puissance de 2, on obtient un schéma légèrement disymétrique, mais qui ne perturbe en rien le fonctionnement de lalgorithme:

tri fusion à 10 éléments

Description de lalgorithme

La méthode décrit à la section précédente peut se résumer en lalgorithme suivant:

fonction tri_fusion(Liste):
    Découper Liste en deux sous-listes L1 et L2
    Appliquer la fonction tri_fusion à L1
    Appliquer la fonction tri_fusion à L2
    Fusionner L1 et L2

    Renvoyer le résultat de la fusion

Implémentation du tri fusion

Lalgorithme de tri fusion se prête bien à une implémentation à laide de listes chaînées.

Outre la fonction récursive tri_fusion, nous avons besoin dune fonction coupe pour découper une liste en sous-listes, ainsi que dune fonction fusion.

Sur le schémas précédents, la coupe a toujours été effectuée en milieu de liste. Mais cela nest absolument pas une nécessité: lessentiel est que lon obtiennent deux sous-listes de tailles à peu près équivalentes (il peut y avoir une différence dune unité), peu importe comment les éléments de la liste initiale ont été répartis.

Dans le cas dune liste chaînée, cela permet notamment de prendre alternativement un élément sur deux pour la première sous-liste ou bien la seconde:

def coupe(lc):
   """
   Découpe la liste chaînée lc en deux sous-listes de tailles équivalentes.
   """

   l1 = liste_vide()
   l2 = liste_vide()

   i = 0
   pos = lc
   while not est_vide(pos):
      if i % 2 == 0:
         l1 = cellule(tête(pos), l1)
      else:
         l2 = cellule(tête(pos), l2)
      i += 1

   return l1, l2

La fonction de fusion peut se décrire facilement à laide dun algorithme récursif:

def fusion(lc1, lc2):
   if est_vide(lc1):
      return lc2
   elif est_vide(lc2):
      return lc1
   else:
      if tête(lc1) < tête(lc2):
         return cellule(tête(lc1), fusion(queue(lc1), lc2))
      else:
         return cellule(tête(lc2), fusion(queue(lc2), lc1))

On verra en TP quil est tout fait possible (et intéressant) de remplacer cet algorithme récursif par un autre algorithme, itératif. Lavantage étant quavec lalgorithme récursif, il nest pas aisé de fusionner des listes dont la taille dépasse la limite de récursion de python (normalement 1000 appels). Avec un algorithme itératif, aucun problème de ce genre.

Enfin, la fonction de tri proprement dite est une implémentation directe de lalgorithme de la section précédente:

def tri_fusion(lc):
   if est_vide(lc) or est_vide(queue(lc)):
      # On a une liste vide ou de longueur 1, déjà triée
      return lc
   else:
      lc1, lc2 = coupe(lc)
      return fusion(tri_fusion(lc1), tri_fusion(lc2))

Complexité de lalgorithme

Quel est le nombre détapes nécessaires pour effectuer un tri fusion ?

La fusion elle-même prend exactement \(N\) étapes, où \(N\) est la taille de la liste fusionnée. Si on note \(c(N)\) le nombre détapes pour fusionner une liste de taille \(N\), alors lalgorithme récursif nous donne directement la relation

\[ c(N) = 2\times c(N/2) + N\]

En effet, on a compté le nombre détapes du tri fusion des deux sous-listes, ainsi que la fusion elle-même (on peut considérer que le découpage est, quand à lui, constant, même si ce nest pas le cas dans limplémentation proposée ici).

On peut montrer en mathématiques que la fonction \(c(N)\) est proportionnelle à \(N\times\log_2(N)\) (cette démonstration est totalement hors-programme au lycée).

La complexité de lalgorithme de tri fusion est donc intermédiaire entre une complexité linéaire et une complexité quadratique. Cependant, nous verrons en TP que la complexité de lalgorithme de tri fusion est très largement supérieure à celle des tris par insertion ou sélection lorsque le nombre déléments devient grand.

Prenons par exemple le cas dune liste de taille \(N = 1000\). Un tri de complexité quadratique aurait un nombre détapes proportionnel à \(1000^2 = 1\,000\,000\), alors que le tri fusion ne prendrait que \(1000\times \log_2(1000) \approx 9966\) étapes. La différence est considérable, et lécart ne ferait que se creuser avec une liste plus longue.