11 fév. 2010
Tout étudiant d’un cours d’algorithmique de base apprend que la complexité moyenne de l’algorithme QuickSort est en O(n log n), celle de QuickSelect est en O(n) et celle de RadixSort est en O(n log n). De tels énoncés ont le mérite d’être simples, mais leur simplicité est trompeuse, car ils sont fondés sur des hypothèses spécifiques à chaque algorithme : pour les deux premiers algorithmes, le coût unitaire est la comparaison entre clés, tandis que, pour le troisième, le coût unitaire est la comparaison entre symboles.
Ces études soufrent donc de deux inconvénients majeurs : il n’est pas possible de comparer réellement ces algorithmes entre eux, car les mesures de coût sont différentes. Ensuite, la mesure de coût adoptée pour analyser QuickSort ou QuickSelect est peu réaliste, dès que les clés ont une structure complexe, ce qui est le cas dans le contexte des bases de données ou de la langue naturelle, par exemple.
Pour effectuer une analyse réaliste, il faut donc d’abord travailler en théorie de l’information pour définir un cadre adapté. En théorie de l’information, une source est un mécanisme aléatoire qui produit des symboles d’un alphabet donné. On construit ici un modèle de source très général, qui prenne en compte la possibilité de corrélations importantes entre symboles émis. Les clés considérées par l’algorithme sont alors des mots produits (indépendamment) par la même source.
Il faut ensuite considérer un coût unitaire qui soit le même pour tous les algorithmes : c’est la comparaison entre symboles, et le coût de l’algorithme est donc le nombre total de comparaisons effectuées entre symboles. Nous revisitons ainsi, dans un tel modèle, à la fois unifié et réaliste, l’analyse probabiliste de trois principaux algorithmes : QuickSort, QuickSelect, et les algorithmes de dictionnaire fondés sur la structure de tri.
Cet exposé est fondé sur des travaux communs avec Julien Clément, James Fill, et Philippe Flajolet.
Brigitte Vallée (Université de Caen)
[Vidéo indisponible]
