Livre_silo 30 août 2013 16:32 Page 149
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
149
6 – Notions de complexité et algorithmique sur les tableaux
Si n est un nombre premier, alors il faudra
√
n − 1 itérations ; pourtant, pour n − 1 et
n + 1 qui sont pairs, le programme s’arrête dès la première itération.
Si la fonction f caractérise l’efficacité d’un algorithme, on veut avoir l’assurance que l’exécution du programme sera terminée en un temps proportionnel à f (n), éventuellement
moins, mais pas plus. On cherche donc un majorant du temps d’exécution, autrement dit
on retiendra le pire des cas pour exprimer la complexité.
Complexité dans le meilleur des cas
La complexité au pire est la plus significative, mais dans certains cas, il peut être utile de
connaître aussi la complexité dans le meilleur des cas. Cette dernière reste d’un usage anecdotique mais elle peut donner une borne inférieure du temps d’exécution d’un algorithme.
En particulier, si la complexité dans le meilleur et dans le pire des cas sont du même ordre,
cela signifie que le temps d’exécution de l’algorithme est relativement indépendant des
données et ne dépend que de la taille du problème.
Complexité en espace
Jusqu’ici, on a uniquement discuté du temps d’exécution des algorithmes. Une autre ressource importante en informatique est la mémoire. On appelle complexité en espace d’un
algorithme la place nécessaire en mémoire pour le faire fonctionner. Elle s’exprime également sous la forme d’un O(f (n)) où n est la taille du problème.
Évaluer la complexité en espace d’un algorithme ne pose la plupart du temps pas de difficulté ; il suffit de faire le total des tailles en mémoire des différentes variables utilisées. Une
première exception à la règle est le cas où on alloue dynamiquement de l’espace mémoire
au cours du programme (voir chapitre 12). L’autre cas est celui des fonctions récursives,
qui cachent souvent une complexité en espace élevée (voir la section 5.3 pour un aperçu
de l’empreinte mémoire d’une fonction récursive).
POUR ALLER PLUS LOIN Complexité en moyenne et complexité amortie
Pour un même algorithme, le temps d’exécution peut être très différent suivant les données
d’entrée. C’est le cas par exemple de certains algorithmes triant un tableau de taille n, qui
prennent un temps proportionnel à n si le tableau est trié et proportionnel à n 2 dans le
pire cas. On s’intéresse donc parfois à la complexité en moyenne d’un algorithme. Parler
de moyenne des temps d’exécution n’a de sens que si l’on a une idée de la fréquence des
différentes données possibles pour un même problème de taille n. Les calculs de complexité
moyenne recourent aux notions définies en mathématiques dans le cadre de la théorie
des probabilités et des statistiques. Ils sont souvent très délicats et sortent du cadre de cet
ouvrage.
Par ailleurs, il existe des problèmes où le pire cas peut se produire mais où, sur des exécutions
répétées, on a la certitude qu’il ne se produira que peu fréquemment. On peut prendre
l’exemple d’une personne désirant envoyer un SMS depuis un téléphone mobile. Quel est
le coût en temps de cet envoi ? Si tout se passe bien, la rédaction et l’envoi se font en
2 minutes.
¯
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
149
6 – Notions de complexité et algorithmique sur les tableaux
Si n est un nombre premier, alors il faudra
√
n − 1 itérations ; pourtant, pour n − 1 et
n + 1 qui sont pairs, le programme s’arrête dès la première itération.
Si la fonction f caractérise l’efficacité d’un algorithme, on veut avoir l’assurance que l’exécution du programme sera terminée en un temps proportionnel à f (n), éventuellement
moins, mais pas plus. On cherche donc un majorant du temps d’exécution, autrement dit
on retiendra le pire des cas pour exprimer la complexité.
Complexité dans le meilleur des cas
La complexité au pire est la plus significative, mais dans certains cas, il peut être utile de
connaître aussi la complexité dans le meilleur des cas. Cette dernière reste d’un usage anecdotique mais elle peut donner une borne inférieure du temps d’exécution d’un algorithme.
En particulier, si la complexité dans le meilleur et dans le pire des cas sont du même ordre,
cela signifie que le temps d’exécution de l’algorithme est relativement indépendant des
données et ne dépend que de la taille du problème.
Complexité en espace
Jusqu’ici, on a uniquement discuté du temps d’exécution des algorithmes. Une autre ressource importante en informatique est la mémoire. On appelle complexité en espace d’un
algorithme la place nécessaire en mémoire pour le faire fonctionner. Elle s’exprime également sous la forme d’un O(f (n)) où n est la taille du problème.
Évaluer la complexité en espace d’un algorithme ne pose la plupart du temps pas de difficulté ; il suffit de faire le total des tailles en mémoire des différentes variables utilisées. Une
première exception à la règle est le cas où on alloue dynamiquement de l’espace mémoire
au cours du programme (voir chapitre 12). L’autre cas est celui des fonctions récursives,
qui cachent souvent une complexité en espace élevée (voir la section 5.3 pour un aperçu
de l’empreinte mémoire d’une fonction récursive).
POUR ALLER PLUS LOIN Complexité en moyenne et complexité amortie
Pour un même algorithme, le temps d’exécution peut être très différent suivant les données
d’entrée. C’est le cas par exemple de certains algorithmes triant un tableau de taille n, qui
prennent un temps proportionnel à n si le tableau est trié et proportionnel à n 2 dans le
pire cas. On s’intéresse donc parfois à la complexité en moyenne d’un algorithme. Parler
de moyenne des temps d’exécution n’a de sens que si l’on a une idée de la fréquence des
différentes données possibles pour un même problème de taille n. Les calculs de complexité
moyenne recourent aux notions définies en mathématiques dans le cadre de la théorie
des probabilités et des statistiques. Ils sont souvent très délicats et sortent du cadre de cet
ouvrage.
Par ailleurs, il existe des problèmes où le pire cas peut se produire mais où, sur des exécutions
répétées, on a la certitude qu’il ne se produira que peu fréquemment. On peut prendre
l’exemple d’une personne désirant envoyer un SMS depuis un téléphone mobile. Quel est
le coût en temps de cet envoi ? Si tout se passe bien, la rédaction et l’envoi se font en
2 minutes.
¯