2.2 Complexité des Problèmes
47
© Dunod – Toute reproduction non autorisée est un délit.
Remarque. Dans notre exemple les complexités dans le pire des cas et dans le
cas moyen sont asymptotiquement les mêmes : O(n). En effectuant plus précisément le calcul des deux complexités, on constatera que le temps moyen pour
l’exécution de l’algorithme est deux fois moindre que le temps dans le pire des
cas. Cependant comme O a
1
2
nb 5 O1 n 2 , à une constante multiplicative près
ces deux complexités sont les mêmes.
2.1.5 Conclusion
Nous venons de voir que les trois mesures de complexité définies, le sont à une
constante multiplicative près, et pour des données de taille suffisamment grande.
Cela pourrait paraître quelque peu imprécis et ne pas refléter véritablement l’efficacité d’un algorithme. Cependant, pour être pertinente, l’étude d’un algorithme doit se
faire indépendamment de l’ordinateur sur lequel il devra s’exécuter. D’une machine
à l’autre, les opérations « élémentaires » effectivement exécutées peuvent être différentes. Le plus généralement, ce sont des problèmes de grande taille qui doivent être
traités efficacement ; pour un problème de taille réduite un “mauvais” algorithme
car lent, voire une résolution manuelle peuvent être suffisants. Pour ces différentes
raisons, il apparaît que le comportement “asymptotique” (c-à-d sur les problèmes de
grande taille) d’un algorithme est une mesure pertinente de son efficacité pratique.
La connaissance actuelle de la complexité de la majeure partie des algorithmes
est essentiellement concentrée sur la complexité dans le pire des cas. Cette mesure
n’est pas nécessairement la plus pertinente, le pire des cas pouvant ne se présenter
que très occasionnellement. L’étude probabiliste d’un algorithme, l’espérance et la
variance du temps de calcul sont certainement des mesures plus précises mais, malheureusement, les outils mathématiques actuels n’ont permis de mener à bien cette
étude que pour très peu d’algorithmes (certains algorithmes de tri, par exemple).
Cependant une étude statistique plus facile à mener, ainsi que la complexité dans
le pire des cas d’un algorithme, sont des informations souvent suffisantes pour le
chercheur opérationnel.
2.2 complexité des problèmes
Très souvent, plusieurs algorithmes sont susceptibles de résoudre un même problème donné. Le chapitre dédié à la complexité des algorithmes fournit les éléments permettant de comparer les efficacités d’algorithmes résolvant un même
problème. Après s’être informé de l’efficacité d’un algorithme particulier, le chercheur opérationnel doit se poser la question suivante : l’algorithme proposé est-il le
« meilleur possible » pour résoudre le problème à traiter. Par « meilleur possible »
nous entendons, de complexité moindre que celle de tout autre algorithme susceptible de résoudre le problème considéré. La théorie de la complexité des problèmes
a pour objectif de répondre à ce point. La problématique de cette théorie est la suivante : étant donné un problème, déterminer, si possible, la complexité minimale
47
© Dunod – Toute reproduction non autorisée est un délit.
Remarque. Dans notre exemple les complexités dans le pire des cas et dans le
cas moyen sont asymptotiquement les mêmes : O(n). En effectuant plus précisément le calcul des deux complexités, on constatera que le temps moyen pour
l’exécution de l’algorithme est deux fois moindre que le temps dans le pire des
cas. Cependant comme O a
1
2
nb 5 O1 n 2 , à une constante multiplicative près
ces deux complexités sont les mêmes.
2.1.5 Conclusion
Nous venons de voir que les trois mesures de complexité définies, le sont à une
constante multiplicative près, et pour des données de taille suffisamment grande.
Cela pourrait paraître quelque peu imprécis et ne pas refléter véritablement l’efficacité d’un algorithme. Cependant, pour être pertinente, l’étude d’un algorithme doit se
faire indépendamment de l’ordinateur sur lequel il devra s’exécuter. D’une machine
à l’autre, les opérations « élémentaires » effectivement exécutées peuvent être différentes. Le plus généralement, ce sont des problèmes de grande taille qui doivent être
traités efficacement ; pour un problème de taille réduite un “mauvais” algorithme
car lent, voire une résolution manuelle peuvent être suffisants. Pour ces différentes
raisons, il apparaît que le comportement “asymptotique” (c-à-d sur les problèmes de
grande taille) d’un algorithme est une mesure pertinente de son efficacité pratique.
La connaissance actuelle de la complexité de la majeure partie des algorithmes
est essentiellement concentrée sur la complexité dans le pire des cas. Cette mesure
n’est pas nécessairement la plus pertinente, le pire des cas pouvant ne se présenter
que très occasionnellement. L’étude probabiliste d’un algorithme, l’espérance et la
variance du temps de calcul sont certainement des mesures plus précises mais, malheureusement, les outils mathématiques actuels n’ont permis de mener à bien cette
étude que pour très peu d’algorithmes (certains algorithmes de tri, par exemple).
Cependant une étude statistique plus facile à mener, ainsi que la complexité dans
le pire des cas d’un algorithme, sont des informations souvent suffisantes pour le
chercheur opérationnel.
2.2 complexité des problèmes
Très souvent, plusieurs algorithmes sont susceptibles de résoudre un même problème donné. Le chapitre dédié à la complexité des algorithmes fournit les éléments permettant de comparer les efficacités d’algorithmes résolvant un même
problème. Après s’être informé de l’efficacité d’un algorithme particulier, le chercheur opérationnel doit se poser la question suivante : l’algorithme proposé est-il le
« meilleur possible » pour résoudre le problème à traiter. Par « meilleur possible »
nous entendons, de complexité moindre que celle de tout autre algorithme susceptible de résoudre le problème considéré. La théorie de la complexité des problèmes
a pour objectif de répondre à ce point. La problématique de cette théorie est la suivante : étant donné un problème, déterminer, si possible, la complexité minimale