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

    Ok, je précise. Le O(n) permet de ne pas avoir à évaluer la constante qui est devant le 'n'. Le nombre d'étapes que l'algorithme devra faire au pire est en 'C.n' (avec 'C' une constante). Mais le 'C' change d'un algo à un autre alors on ne considère que les plus gros facteurs, on parle alors de O(n) (et non de 'C.n') pour la classe d'algorithmes ou pour un problème donné. Évidemment, lorsque 'n' tends vers l'infini on peut négliger le 'C'. Jusque là, tu as raison. Cependant, lorsque tu dis que la 'complexité' est 'n' pour un 'n' grand, là je dis non ! :-) Ta complexité est toujours 'n' (la complexité est la mesure générale de ton algorithme ou de ton problème). Par contre, le nombre de tes opérations pour un algorithme précis va tendre vers 'n'. Je crois que c'est seulement, là-dessus que repose notre divergence... Juste un point de détail quoi. :-)