2.1 Complexité des Algorithmes
43
© Dunod – Toute reproduction non autorisée est un délit.
Figure 2.1 g une fonction appartenant à O1 f 2 .
À partir de n 0 , la courbe g1n2 est comprise entre les courbes f 1n2 et c # f 1n2.
Le comportement asymptotique des fonctions considérées étant étudié à une
constante multiplicative positive près, de nombreuses classes de fonctions sont équivalentes. Ainsi on pourra vérifier, par exemple, que O1 10 000n
2
2 5 O1 0,001n
2
2 5
O1 n
2
2 et O(e
n
) 5 O(e
n1173
) car e
n1173 5 e
n # e
173
et e
173
est une constante et, plus
généralement, O1 c # f 2 5 O1 f 2 pour toute constante positive c.
Nous allons donner, pour les fonctions les plus couramment utilisées, quelques exemples d’utilisation de cette notation. Le lecteur est encouragé à vérifier
ces exemples à partir de la définition précédente. Pour tout polynôme P1 n2 5
a p n
p 1 a p21 n
p21 1 c 1 a 1 n 1 a 0 , on a P H O1 n
p
2 .
Ainsi 12n
5 2 4n
3 1 2n
2 1 n 2 1 H O1 n
5
2 .
Nous donnons maintenant des relations d’inclusion pour les classes de fonctions les
plus usuelles : O1 12 ( O1 log log n2 ( O1 log n 2 ( O1 !n 2 ( O1 n 2 ( O1 n log n2 (
O(n
2
) ( O(n
3
) ( c ( O(n
10
) c ( O(2
n
) ( O(e
n
) ( O(n !) ( O1 n
n
2 .
Rappelons, au passage, la formule de Stirling : n ! , 1 n/e2
n
!2pn.
(1)
Dans le tableau ci-dessous, nous allons illustrer le comportement des fonctions
les plus usuelles. Pour une fonction f et une donnée de taille n, nous avons reporté
le temps nécessaire à un ordinateur qui exécuterait un milliard d’opérations par
seconde, pour effectuer f 1 n2 opérations.
(1) n ! x O(n
n1
1
2 ) car 1 1/e2
n n’est pas une constante.