Analyse des algorithmes

Complexité algorithmique

Quand on tente de résoudre un problème, la question se pose souvent du choix d'un algorithme. Quels critères peuvent guider ce choix ? Deux besoins contradictoires sont fréquemment en présence : l'algorithme doit :

1.    Etre simple à comprendre, à mettre en œuvre, àmettre au point.

2.    Mettre intelligemment à contribution des ressources de l'ordinateur et, plus précisément, il doit s'exécuter le plus rapidement possible.

Si un algorithme ne doit servir qu'un petit nombre de fois, le premier critère est le plus important. Par contre, s'il doit être employé souvent, le temps d'exécution risque d'être un facteur plus déterminant que le temps passé à l'écriture.

L’étude de la complexité des algorithmes a pour objectif l’estimation du coût d’un algorithme. Cette mesure permet donc la comparaison de deux algorithmes sans avoir à les programmer.

Si l’on prend en compte pour l’estimation de la complexité les ressources de la machine telles que la fréquence d’horloge, le nombre de processeurs, le temps d’accès disque etc., on se rend compte immédiatement de la complication voire l’impossibilité d’une telle tâche. Pour cela, on se contente souvent d’estimer la relation entre la taille des données et le temps d’exécution, et ceci indépendamment de l’architecture utilisée.

Sommaire

Partager cette formation avec tes amis :