Pour de nombreux problèmes, l'algorithme avec la meilleure complexité asymptotique a un très grand facteur constant qui est caché par une grande notation O. Cela se produit dans la multiplication matricielle, la multiplication d'entiers (en particulier, le récent algorithme de multiplication d'entiers O (n log n) de Harvey et van der Hoeven), les réseaux de tri à faible profondeur et la recherche de mineurs de graphes, pour en faire quelques-uns. De tels algorithmes sont parfois appelés algorithmes galactiques.
Notez que pour d'autres algorithmes, tels que le tri général et l'addition d'entiers, les algorithmes sont connus avec une complexité asymptotique optimale et de petits facteurs constants.
Quelles recherches ont été menées pour séparer les premiers algorithmes des seconds, d'un point de vue théorique?
Je suis conscient que les constantes cachées sont souvent omises pour masquer la distinction entre les différents modèles de calcul. Cependant, je suis convaincu que sous une grande variété de modèles différents, ces algorithmes galactiques seront plus lents que les algorithmes asymptotiquement pires pour des entrées de taille un milliard, par exemple. La distinction n'est pas subtile, dans certains cas. At-il été rendu rigoureux?
Par exemple, on pourrait inventer un modèle de calcul très simple, comme une machine von Neumann avec un ISA très simple, puis implémenter les algorithmes et lier leurs temps d'exécution avec des constantes explicites. Cela a-t-il été fait pour une variété d'algorithmes?
Réponses:
La méthodologie ne nécessite pas de fixer un modèle de calcul spécifique, bien que cela puisse être utile bien sûr. Notez également que vous pouvez essayer de calculer le comportement le plus défavorable ou le comportement attendu, ou encore autre chose.
L'ingrédient le plus important de cette méthodologie est l'analyse des fonctions génératrices de ces valeurs. Vous pouvez parfois obtenir des approximations asymptotiques très précises en utilisant des méthodes d'analyse complexe.
En fait, dans quicksort, vous triez une liste en triant récursivement les sous-listes, de sorte que vous obtiendrez une amélioration pour toutes les tailles si vous utilisez mergesort sur des listes plus petites que la taille 10. Une note intéressante dans le livre mentionne que dans certaines bibliothèques Microsoft open source, l'algorithme de tri générique est implémenté en tant que tri rapide jusqu'à ce que vous atteigniez une taille de 10, après quoi le mergesort est utilisé. Dans les commentaires du code, il est mentionné que les tests de performances ont montré que cette valeur était optimale.
la source