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

    Pourquoi 'n' devrait-il etre "suffisamment grand" ? Ça, ça vient de la définition mathématique de O(). Si tu as un algo qui prend n^4+500*n^3, il est O(n^4), pourtant pour n=10, c'est le 500*n^3 qui compte. Il s'agit de la complexité dans le pire cas. C'est toujours vrai. Euh, pas toujours, non. L'algo de tri rapide, par exemple, est O(n^2) en pire cas, mais O(n ln(n)) en moyen cas. Et on le considère souvent comme un algo en O(n ln(n)) parce que sauf dans les applis temps réel, c'est plus la complexité en cas moyen qui nous intéresse.