• [^] # Re: [HS ?] Ordre de complexité d'un alogrithme

    Posté par . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 8.

    Moi, je connais et j'ai même implémenté des algos en O(e^n). Enfin pas completement exponentiels car ils sont P-space complet. Ce sont des algos de vérification de logiciels (model-checking). Mais, il est vrai qu'il s'agit là d'une limite. Cela dit, il est important de se rendre compte que lorsqu'on parle de O(.) on parle de complexité au pire et non pas en moyenne. Pour certains algorithmes les problèmes que l'on considère en pratique ont une complexité moindre que la complexité au pire. C'est le cas de l'algorithme du simplexe par exemple qui devrait être NP mais qui est P en pratique.