Introduction à la complexité

Résumé du document

Pascal

Introduction à la complexité

Extraits

[...] la multiplication de deux matrices, la taille sera la dimension des matrices. On parle de complexité : dans le meilleur des cas (complexité minimale sur tous les ensembles de données de taille dans le pire des cas (complexité maximale sur tous les ensembles de données de taille en moyenne (moyenne de le complexité sur tous les ensemble de données de taille Notation : On notera le temps d'exécution d'un programme sur des données de taille n. Temps d'exécution Temps d'exécution des composants élémentaires (hors entrée / sortie) : Constantes qui dépendent des conditions matérielles et logicielles. [...]

[...] Introduction à la complexité Intérêt Importance de l'efficacité d'un programme et des algorithmes sous- jacents. But du calcul de la complexité algorithmique : comparer différents algorithmes, pour choisir le plus efficace. On veut pouvoir dire : l'algorithme A est meilleur que l'algorithme B pour des données de telle taille quels que soient la machine et le langage de programmation utilisé L'étude de cette efficacité consiste à étudier : le d'exécution la place mémoire nécessaire. Le temps d'exécution d'un programme dépend : de la qualité du code généré par le compilateur de la nature et de la vitesse d'exécution des instructions du microprocesseur des données entrant dans le programme de la complexité algorithmique du programme. [...]