Et puis il faut arrêter de ne regarder que la complexité. Dans la vraie vie, la constante est importante.
Pour prendre un exemple bête,
Heapsort est un excellent algorithme de tri en place optimal (O(n.ln n)) dans le pire des cas.
Pourtant, tout le monde utilise quick-sort qui lui est aussi en place mais n'est certainement pas optimal puisqu'il peut avoir une execution quadratique.
Les gens seraient-ils complètement cons? Ben non parce que quick-sort est optimal en moyenne et que la constante est plus faible que pour heap-sort.
Et puis si on ne regarde que la complexité, on ne ferait pas de programmation linéaire puisque l'algorithme du simplexe est exponentiel non?
[^] # Re: nouvelle technique d'optimisation
Posté par fmaz fmaz . En réponse au journal nouvelle technique d'optimisation. Évalué à 6.
Pour prendre un exemple bête,
Heapsort est un excellent algorithme de tri en place optimal (O(n.ln n)) dans le pire des cas.
Pourtant, tout le monde utilise quick-sort qui lui est aussi en place mais n'est certainement pas optimal puisqu'il peut avoir une execution quadratique.
Les gens seraient-ils complètement cons? Ben non parce que quick-sort est optimal en moyenne et que la constante est plus faible que pour heap-sort.
Et puis si on ne regarde que la complexité, on ne ferait pas de programmation linéaire puisque l'algorithme du simplexe est exponentiel non?
Frédéric.