• [^] # 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é à 7.

    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. Cf mon autre commentaire, non, il y a plusieurs complexités pour un même algorithme: complexité en temps ou en espace mémoire, et complexité en pire cas ou en moyen cas. Ce que l'on appelle usuellement la complexité tout court, c'est la complexité moyenne en temps, qui est celle qui est la plus souvent utilisée. La complexité en pire cas n'est rellement utilisée qu'en temps réel ou ce qui compte ce n'est pas d'avoir un algo globalement performant, mais de pouvoir dire "on peut garantir que le résultat sera disponible à temps".