1. Complexité d'un algorithme et performanceNous faisons la distinction entre les méthodes (algorithmes) de tri d'un grand nombre d'éléments (plusieurs milliers ou plus), et le tri de quelques éléments (quelques dizaines, voir quelques centaines ). Pour de très petits nombres d'éléments, la méthode importe peu. Il est intéressant de pouvoir comparer différents algorithmes de tris afin de savoir quand les utiliser.
Ce que nous énonçons dans ce paragraphe s'applique en général à tous les algorithmes et en particulier aux algorithmes de tris qui en sont une excellente illustration.
1.1 Notions de complexité temporelle et spatiale
L'efficacité d'un algorithme est directement liée au programme à implémenter sur un ordinateur. Le programme va s'exécuter en un temps fini et va mobiliser des ressources mémoires pendant son exécution; ces deux paramètres se dénomment complexité temporelle et complexité spatiale.
Dès le début de l'informatique les deux paramètres "temps d'exécution" et "place mémoire" ont eu une importance à peu près égale pour comparer l'efficacité relative des algorithmes.
Il est clair que depuis que l'on peut, à coût très réduit avoir des mémoires centrales d'environ 1 Giga octets dans une machine personnelle, les soucis de place en mémoire centrale qui s'étaient fait jour lorsque l'on travaillait avec des mémoires centrales de 128 Kilo octets (pour des gros matériels de recherche des années 70) sont repoussés psychologiquement plus loin pour un utilisateur normal. Comme c'est le système d'exploitation qui gère la mémoire disponible ( RAM, cache, virtuelle etc...), les analyses de performances de gestion de la mémoire peuvent varier pour le même programme.
Aucun commentaire:
Enregistrer un commentaire