Cours Algorithme : Fusion et Recherche Algorithme Fusion-Recherche

- Les méthodes de fusion.
- Les méthodes de recherches.

Le problème de Fusion-Recherche 

    

Soit un nombre n d'objets (disons les entiers 1...n). Au départ chaque objet constitue un ensemble.

 

Considérons deux opérations: FUSIONner deux ensembles et CHERCHer dans quel ensemble se trouve un objet donné (on peut supposer que l’on est libre de choisir comme nom d'un ensemble produit le nom qui convient parmi les deux noms des ensembles fusionnés). 

  

Quel est le temps de faire une suite d'opérations? 

  

Quelques méthodes

  

Une Méthode naïve: temps linéaire

  

Quand on fait la fusion de A et B, choisir comme nom celui de A et parcourir B en changeant le nom associé à chaque élément de B. Cette méthode nécessite que les éléments de chaque ensemble soient reliés (par exemple dans une liste avec pointeurs). Dans le pire cas on fusionne toujours un A d'un seul élément avec un grand B.  

  

On obtient donc un temps n-1 pour la dernière fusion. Et la moyenne dépend de l'application. 

  

Une astuce simple: temps (amorti) O(logn)

  

IL faut toujours choisir comme nom principal celui de l'ensemble le plus grand (ce qui nécessite le stockage de la taille de chaque ensemble. Cette taille est facile à mettre à jour après une fusion).

  

Remarque : un objet est renommé au plus log(i) fois dans une suite de i fusions. On obtient alors un temps (amorti) par opération O(logn). 

    

Une astuce de plus: temps (pire cas) O(logn)

  

On utilise une nouvelle structure de données: un arbre où les pointeurs sont orientés vers la racine: la racine contient le nom de l'ensemble. Dans ce cas, il faut toujours fusionner selon les deux tailles : le plus grand des deux ensembles devient père de l'autre. Il n’est pas nécessaire de chercher à mettre à jour les noms (en fait ne plus les stocker). 

 

Deux remarques :

   

• Pour trouver le nom d'un objet, il suffit alors de suivre les pointeurs à la racine : en montant vers la racine pour trouver le nom.

• La taille des ensembles double (au moins) à chaque itération. Donc, au plus, on a logn itérations. 

  

Et encore une astuce

  

Chaque fois qu'on a parcouru le chemin d'un objet vers la racine, on le parcourt une deuxième fois, en remplaçant chaque pointeur par un raccourci directement à la racine !
 

Remarque : Le pire des cas d'une opération reste O(logn). Mais chaque recherche rend plus rapide des recherches à venir. Dans ce cas, quel est l'effet sur le temps total ? 

 

Les fonctions log^* et T

  

Log^*(n) est une fonction qui croît très lentement avec n. Le nombre de fois qu'il faut appliquer log₂ à n (avec arrondi vers le bas chaque fois) pour arriver à 1. T(n) une fonction qui croît TRES vite avec n : la valeur d'un tour de n fois 2. log^* est l'inverse de T. 

  

On va démontrer que le temps (amorti) d'une opération de fusion/recherche est O(log^*(n)). 

  

Majoration

 

Majorer le temps amorti: (1) les gros sauts de taille

  

Le temps d'une fusion est constante : on ne fait qu'ajouter un pointeur et sommer les deux tailles. Le temps de suivre un pointeur en cherchant la racine est « facturé » à l'opération de recherche ou à l'opération de fusion qui a ajouté l'objet comme un fils; selon les tailles des ensembles père et fils. Si les deux tailles ont des valeurs différentes de log^*, facturer à la recherche. Le nombre facturés à une recherche est forcément O(log^*(n)).

  

Majorer le temps amorti: (2) les petits sauts

  

Si les deux tailles ont la même valeur de log^*, facturer à la fusion. Pour un ensemble de taille s, où T(i) £ s £ T(i+1), le nombre facturé est au plus log₂ T(i+1), c'est-à-dire T(i) et donc £ s. Deux sous-arbres sont disjoints si le rapport entre leurs deux tailles (grand:petit) est inférieur à 2. Donc :

  

• pour les s tels que T(i) <= s < 2T(i), le total facturé est inférieur à n

• pour ceux tels que 2T(i) <= s < 4T(i), à n/2.

• pour les s tels que T(i)  <= s < T(i+1), à 2n

• et enfin, pour tous les s, inférieur à 2nlog^*(n) 

  

Conclusion

On obtient donc :

  

• temps total O((nombre de fusions + nombre de recherches)*log^*(n))

• temps amorti de chaque opération O(log^*(n)) 

Il n’est pas évident que ce majorant soit strict (pour cet algorithme ou un autre).

 
-------------------------------------------------------------------------------------------------------
Précédent : Étude du Fonctionnement d'un Programme
  
                  Suivant : Recherche chaînes de caractères