Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Complexite d x27 un programme

- Cours Informatique Complexité d ? un algorithme I Généralités La question de la performance est centrale en informatique Si un problème est traité en un temps raisonnable l ? utilisateur est satisfait On s ? attache en général peu à une mesure précise du temps d ? exécution mais uniquement à une approximation de ce temps Si le temps obtenu est perçu comme relativement long se posera la question d ? une solution plus e ?cace La machine étant ?xée l ? amélioration portera alors sur la façon dont sont conçus les algorithmes en fonction du volume n de données à traiter Par exemple si en doublant le volume de données un algorithme renvoie un résultat en multipliant le temps d ? exécution par et un autre le renvoie en multipliant le temps d ? exécution par n on optera évidemment pour le premier on dit que sa complexité temporelle est meilleure Ajoutons que l ? on peut aussi dé ?nir sa complexité spatiale a ?n de prendre en compte l ? espace mémoire occupé au cours de l ? exécution d ? un algorithme Plus sa complexité est grande plus le programme mettant en oeuvre l ? algorithme aura besoin de zones mémoires pour stocker les données I Complexité temporelle et spatiale d ? un algorithme Dé ?nition La complexité temporelle d ? un algorithme est une information sur son temps d ? exécution liée au volume n de données à traiter La complexité temporelle d ? un programme est la complexité temporelle de l ? algorithme associé Remarques ? La complexité temporelle ne dépend pas ?? des performances du processeur de la machine sur laquelle le programme est exécuté ?? des modes d ? accès à la mémoire vive et des modes de stockage ?? du langage de programmation dans lequel l ? algorithme est traduit ?? du compilateur interpréteur exécuté On se place sur une machine idéalisée dont la mémoire est considérée comme in ?nie et l ? accès aux données se fait en temps constant ? Le volume de données on dit aussi la taille des données dépend du problème étudié ?? il peut s ? agir du nombre d ? éléments constituant les paramètres de l ? algorithme par exemple le nombre d ? éléments d ? un tableau ?? dans le cas d ? algorithmes de nature arithmétique le calcul de n par exemple il peut s ? agir d ? un entier passé en argument ?? dans le cas d ? algorithmes avec des cha? nes de caractères il peut s ? agir de la longueur des cha? nes de caractères Noter que le volume de données est un entier naturel caractérisant le nombre de données et non son occupation mémoire en octets ou en bits Dé ?nition La complexité spatiale d ? un algorithme est une estimation de l ? espace mémoire occupé au cours de l ? exécution d ? un programme en fonction du volume n de données à