Je crois que tu confonds la complexité d'un algorithme ou d'un problème et son nombre d'opérations. Ce n'est pas bien grave car c'est souvent la même chose. Cependant, il existe ce que l'on appelle des 'classes de complexité' qui regroupent des problèmes de façon indépendante des algorithmes.
Par exemple, le test de primalité est P-complet(polynomial), le problème du voyageur de commerce est NP-complet (non polynomial), le problème de l'accessibilité dans un automate temporisé est P-space complet (polynomial en espace, on se fiche du temps), la résolution d'un système d'inéquations Diophantiennes est EXP-Time complet (exponentielle en temps), etc...
Tous ces problèmes peuvent avoir des algorithmes différents mais aucun algorithme ne peut avoir une complexité plus basse que la classe de complexité à laquelle appartient le problème. Maintenant, si tu considères le nombre d'opérations au pire cas, les algorithmes varient beaucoup, mais l'intéret est de considérer des problèmes et non des algorithmes. Évidemment, lorsque tu résouds un problème avec un algorithme calculer la complexité de ton algorithme te permet de voir si tu résoud de façon 'efficace' ou non ton problème (en gros, ton algorithme doit appartenir à la même classe de complexité que ton problème).
Par exemple, résoudre le problème du tri par bubble sort est une mauvaise idée car tu est au-dessus de la complexité du problème du tri (sans hypothèse sur les données).
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 6.
Par exemple, le test de primalité est P-complet(polynomial), le problème du voyageur de commerce est NP-complet (non polynomial), le problème de l'accessibilité dans un automate temporisé est P-space complet (polynomial en espace, on se fiche du temps), la résolution d'un système d'inéquations Diophantiennes est EXP-Time complet (exponentielle en temps), etc...
Tous ces problèmes peuvent avoir des algorithmes différents mais aucun algorithme ne peut avoir une complexité plus basse que la classe de complexité à laquelle appartient le problème. Maintenant, si tu considères le nombre d'opérations au pire cas, les algorithmes varient beaucoup, mais l'intéret est de considérer des problèmes et non des algorithmes. Évidemment, lorsque tu résouds un problème avec un algorithme calculer la complexité de ton algorithme te permet de voir si tu résoud de façon 'efficace' ou non ton problème (en gros, ton algorithme doit appartenir à la même classe de complexité que ton problème).
Par exemple, résoudre le problème du tri par bubble sort est une mauvaise idée car tu est au-dessus de la complexité du problème du tri (sans hypothèse sur les données).