Le problème de Fusion-Recherche

Une Méthode naive: temps linéaire

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

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

Et encore une

Les fonctions log* et T

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

Majorer le temps amorti: (2) les petits sauts

Conclusion




File translated from TEX by TTH, version 3.05.
On 5 Dec 2006, 17:31.