Chapitre 2 • Notions de complexité
46
opérationnel, quand elles peuvent être déterminées, de juger pratiquement de l’efficacité en temps d’un algorithme.
Considérons un algorithme A et D la donnée d’un problème résolu par A. Nous
notons par n la taille de D et définissons T A 1 D, n 2 , le nombre d’opérations élémentaires exécutées par A lors de son exécution pour D.
La complexité dans le pire des cas
La complexité dans le pire des cas pour un algorithme A est le maximum sur toutes
les données D de même taille n des valeurs T A 1 D, n 2 , soit max DHD n 5T A 1 D, n 2 6, où
D n est l’ensemble des données de taille n.
Pour l’exemple ci-dessus, le pire des cas intervient lorsque la valeur v se trouve
dans la dernière position de T. La complexité dans le pire des cas de l’algorithme est
donc O(n).
La complexité dans le meilleur des cas
La complexité dans le meilleur des cas de A est le minimum sur toutes les données
D de taille n des valeurs T A 1 D, n2 , soit min
DPD n
5T A 1 D, n 2 6, où D n est l’ensemble des
données de taille n.
Ainsi dans notre exemple, le meilleur des cas intervient lorsque la valeur v se
trouve dans la première position de T. La complexité dans le meilleur des cas de
l’algorithme est donc O(1).
La complexité en moyenne
La complexité dans le cas moyen de A est la moyenne arithmétique sur toutes les
données D de taille n, des valeurs T A 1 D, n 2 , soit
1
Card D n
a
DHD n
T A 1 D, n 2 , où D n est
l’ensemble des données de taille n.
La complexité en moyenne d’un algorithme est généralement très difficile à évaluer. Des hypothèses probabilistes doivent être faites sur la distribution des données.
Ainsi pour notre exemple, nous supposerons que toutes les positions de l’élément v
dans T sont équiprobables. Même ces hypothèses faites, à ce jour rares sont les algorithmes pour lesquels la complexité en moyenne a pu être déterminée.
Pour notre exemple, nous allons pouvoir calculer la complexité en moyenne en considérant que les positions de l’élément v dans T sont équiprobables. Supposons que v soit
en position k dans T alors k 3 O1 12 opérations sont exécutées pendant le déroulement
de l’algorithme. En sommant sur les n positions possibles de v dans T et en divisant par
ce nombre de positions nous obtenons la complexité en moyenne suivante :
1
n a
n
k51
kO1 12 5 O1 n2 car
1
1
1
2
1
2
O
1
n
k n
n n
n
n
k
n
=
∑ =
+
(
)
=
+ ∈ ( ) .
46
opérationnel, quand elles peuvent être déterminées, de juger pratiquement de l’efficacité en temps d’un algorithme.
Considérons un algorithme A et D la donnée d’un problème résolu par A. Nous
notons par n la taille de D et définissons T A 1 D, n 2 , le nombre d’opérations élémentaires exécutées par A lors de son exécution pour D.
La complexité dans le pire des cas
La complexité dans le pire des cas pour un algorithme A est le maximum sur toutes
les données D de même taille n des valeurs T A 1 D, n 2 , soit max DHD n 5T A 1 D, n 2 6, où
D n est l’ensemble des données de taille n.
Pour l’exemple ci-dessus, le pire des cas intervient lorsque la valeur v se trouve
dans la dernière position de T. La complexité dans le pire des cas de l’algorithme est
donc O(n).
La complexité dans le meilleur des cas
La complexité dans le meilleur des cas de A est le minimum sur toutes les données
D de taille n des valeurs T A 1 D, n2 , soit min
DPD n
5T A 1 D, n 2 6, où D n est l’ensemble des
données de taille n.
Ainsi dans notre exemple, le meilleur des cas intervient lorsque la valeur v se
trouve dans la première position de T. La complexité dans le meilleur des cas de
l’algorithme est donc O(1).
La complexité en moyenne
La complexité dans le cas moyen de A est la moyenne arithmétique sur toutes les
données D de taille n, des valeurs T A 1 D, n 2 , soit
1
Card D n
a
DHD n
T A 1 D, n 2 , où D n est
l’ensemble des données de taille n.
La complexité en moyenne d’un algorithme est généralement très difficile à évaluer. Des hypothèses probabilistes doivent être faites sur la distribution des données.
Ainsi pour notre exemple, nous supposerons que toutes les positions de l’élément v
dans T sont équiprobables. Même ces hypothèses faites, à ce jour rares sont les algorithmes pour lesquels la complexité en moyenne a pu être déterminée.
Pour notre exemple, nous allons pouvoir calculer la complexité en moyenne en considérant que les positions de l’élément v dans T sont équiprobables. Supposons que v soit
en position k dans T alors k 3 O1 12 opérations sont exécutées pendant le déroulement
de l’algorithme. En sommant sur les n positions possibles de v dans T et en divisant par
ce nombre de positions nous obtenons la complexité en moyenne suivante :
1
n a
n
k51
kO1 12 5 O1 n2 car
1
1
1
2
1
2
O
1
n
k n
n n
n
n
k
n
=
∑ =
+
(
)
=
+ ∈ ( ) .