C'est bien là une grande partie - si ce n'est toute - la question de l'étude des algorithmes. Dans certains cas, ça paraît évident. Dans d'autres cas, c'est loin de l'être. Prenons par exemple l'algorithme d'Euclide (pour deux entiers m et n). On connait la valeur de n, et m est dans [0,+oo[. Quelle est le nombre de fois moyen Tn qu'on va opérer une "division euclidienne" ? C'est un problème mathématique pas du tout évident - et qui en fascine plus d'un, et c'est la base de l'analyse des algorithmes.
(Pour mémoire, le livre que je te conseillais plus haut, The Art of Computer Programming, vol.1, donne une solution pour les valeurs de n les plus grandes, qui donnerait : Tn (approx)= (12(ln 2)/pi2)ln n. Le genre de constantes de proportionnalité qu'on aime.)
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Manuel Menal . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 10.