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

    Je crois que ce qui provoque notre désaccord provient d'une définition différente de la complexité. Devant le f(n) d'une complexité en O(f(n)), il y a une formule g(n) qui est de complexité moindre. Donc, le nombre d'opérations est f(n).g(n) dans la réalité (pour le pire cas toujours), mais on ne considère que les plus gros facteurs lorsqu'on parle de complexité. Mais par contre, c'est tout le temps la complexité pire cas qui est utilisée. La complexité en moyenne est extremement dure à calculer (pour ne pas dire impossible dans certains cas). Pour ce qui est de la complexité en temps et en espace, tu as raison.