2 NotioNs de
complexité
2.1 complexité des Algorithmes
Un même problème peut être, le plus souvent, résolu par plusieurs algorithmes, c’est
pourquoi il est très important, dans le cadre de la recherche opérationnelle, de pouvoir comparer l’efficacité des différents algorithmes pouvant être mis en œuvre pour
résoudre ce problème. Deux critères principaux sont généralement considérés quand
le chercheur opérationnel étudie l’efficacité d’un algorithme : le premier est le temps
de calcul, le second est l’espace mémoire nécessaire à l’exécution de l’algorithme.
Si l’espace mémoire reste un critère important de l’évaluation de l’efficacité d’un
algorithme, en pratique, dans la grande majorité des problèmes que le chercheur opérationnel doit résoudre, le temps de calcul devient le paramètre principal mesurant
l’efficacité d’un algorithme. En effet, que le problème soit à traiter en temps réel ou
que le chercheur opérationnel dispose de quelques heures, la quantité de temps dont
il dispose pour obtenir une réponse au problème posé est toujours limitée.
Dans ce chapitre, nous nous intéresserons d’abord à la complexité en temps d’un
algorithme que, par abus de langage, nous appellerons simplement « complexité d’un
algorithme ». Après avoir donné les outils mathématiques nécessaires, nous définirons les différentes notions de complexité utilisées et fournirons quelques exemples
du calcul de la complexité d’algorithmes classiques.
2.1.1 La notation O
Soit f une fonction croissante définie sur l’ensemble des entiers positifs. Nous définissons O1 f 2 la classe des fonctions g définies sur l’ensemble des entiers positifs
telles que : 'c . 0, 'n 0 . 0 tels que ;n > n 0 , g1 n 2 < c # f 1 n 2 (soit en langage
usuel : il existe une constante c strictement positive et il existe un entier naturel n 0
tels que pour tout entier naturel n supérieur à n 0 , la valeur de la fonction g calculée
pour n est inférieure ou égale au produit de la constante c et de la valeur de la fonction f calculée pour ce même n). La figure 2.1 illustre cette définition formelle. Nous
noterons alors : g H O1 f 2 .
Nous noterons O1 12 l’ensemble des fonctions majorées par une constante à partir
d’un certain rang ; par exemple g(n) 5
1
n
PO(1) car pour n > 1, on a :
1 1
n
≤ .
complexité
2.1 complexité des Algorithmes
Un même problème peut être, le plus souvent, résolu par plusieurs algorithmes, c’est
pourquoi il est très important, dans le cadre de la recherche opérationnelle, de pouvoir comparer l’efficacité des différents algorithmes pouvant être mis en œuvre pour
résoudre ce problème. Deux critères principaux sont généralement considérés quand
le chercheur opérationnel étudie l’efficacité d’un algorithme : le premier est le temps
de calcul, le second est l’espace mémoire nécessaire à l’exécution de l’algorithme.
Si l’espace mémoire reste un critère important de l’évaluation de l’efficacité d’un
algorithme, en pratique, dans la grande majorité des problèmes que le chercheur opérationnel doit résoudre, le temps de calcul devient le paramètre principal mesurant
l’efficacité d’un algorithme. En effet, que le problème soit à traiter en temps réel ou
que le chercheur opérationnel dispose de quelques heures, la quantité de temps dont
il dispose pour obtenir une réponse au problème posé est toujours limitée.
Dans ce chapitre, nous nous intéresserons d’abord à la complexité en temps d’un
algorithme que, par abus de langage, nous appellerons simplement « complexité d’un
algorithme ». Après avoir donné les outils mathématiques nécessaires, nous définirons les différentes notions de complexité utilisées et fournirons quelques exemples
du calcul de la complexité d’algorithmes classiques.
2.1.1 La notation O
Soit f une fonction croissante définie sur l’ensemble des entiers positifs. Nous définissons O1 f 2 la classe des fonctions g définies sur l’ensemble des entiers positifs
telles que : 'c . 0, 'n 0 . 0 tels que ;n > n 0 , g1 n 2 < c # f 1 n 2 (soit en langage
usuel : il existe une constante c strictement positive et il existe un entier naturel n 0
tels que pour tout entier naturel n supérieur à n 0 , la valeur de la fonction g calculée
pour n est inférieure ou égale au produit de la constante c et de la valeur de la fonction f calculée pour ce même n). La figure 2.1 illustre cette définition formelle. Nous
noterons alors : g H O1 f 2 .
Nous noterons O1 12 l’ensemble des fonctions majorées par une constante à partir
d’un certain rang ; par exemple g(n) 5
1
n
PO(1) car pour n > 1, on a :
1 1
n
≤ .