Introduction à l'algorithmique (thomas Cormen, Charles Leiserson, Ronald Rivest)
extrait :
"Les notation que nous utilisons pour décrire le temps d'execution asymptotique d'un algorithme sont définies en termes de fonctions, dont le domaine est l'ensemble des entiers naturels. De telles notations sont pratique pour décrire la fonction T(n) du temps d'executiondans le pire des cas, qui n'est en général définique sur des tailles d'entrées entières. Cependant, il est parfois avantageux d'étendre abusivement la notation asymptotique, et ce de plusieurs manières différentees(...) Mais il est important de comprendre la signification précise de la notation, de sorte q'en en abusant, on n'en mésus pas.
(...)
La notation \Theta borne une fonction asymptotique à la fois par excès et par défaut. (...) De même que la notation O (grand ô) fournit une borne asymptotique supérieur pour une fonction, la notation \Omega fournit une borne asymptotique inférieur.(...) La borne supérieur asymptotique fournie par la notation O peut être ou non asymptotiquement approchée.(...)On utilise la notation o pour signifier que la borne supérieure n'est pas asymptotiquement approchée.(...) Par analogie, la notation \omega est à la notation \Omega ce que la notation o est à la notation O. On utilise la notation /omega pour indiquer une borne inférieure qui n'est pas approchée asymptotiquement."
Même en étant nul en math et en ne connaissant pas cet outil (comme moi), après avoir lu ce que je viens de citer, je pense que tu as tord et qu'Alan_T à raison quand il dit que tu confond complexité et développement limité. Le second est un outil utilisé par le premier.
Le bouquin est évidement bien plus détaillé, j'ai coupé pour mettre les choses en valeur.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par ldng . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 2.
extrait :
"Les notation que nous utilisons pour décrire le temps d'execution asymptotique d'un algorithme sont définies en termes de fonctions, dont le domaine est l'ensemble des entiers naturels. De telles notations sont pratique pour décrire la fonction T(n) du temps d'executiondans le pire des cas, qui n'est en général définique sur des tailles d'entrées entières. Cependant, il est parfois avantageux d'étendre abusivement la notation asymptotique, et ce de plusieurs manières différentees(...) Mais il est important de comprendre la signification précise de la notation, de sorte q'en en abusant, on n'en mésus pas.
(...)
La notation \Theta borne une fonction asymptotique à la fois par excès et par défaut. (...) De même que la notation O (grand ô) fournit une borne asymptotique supérieur pour une fonction, la notation \Omega fournit une borne asymptotique inférieur.(...) La borne supérieur asymptotique fournie par la notation O peut être ou non asymptotiquement approchée.(...)On utilise la notation o pour signifier que la borne supérieure n'est pas asymptotiquement approchée.(...) Par analogie, la notation \omega est à la notation \Omega ce que la notation o est à la notation O. On utilise la notation /omega pour indiquer une borne inférieure qui n'est pas approchée asymptotiquement."
Même en étant nul en math et en ne connaissant pas cet outil (comme moi), après avoir lu ce que je viens de citer, je pense que tu as tord et qu'Alan_T à raison quand il dit que tu confond complexité et développement limité. Le second est un outil utilisé par le premier.
Le bouquin est évidement bien plus détaillé, j'ai coupé pour mettre les choses en valeur.