Remerciez-le!

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

Algo avnc 0 Analyse des algorithmes CLa question abordée dans ce chapitre est la suivante Comment choisir parmi les di ?érentes approches pour résoudre un problème Exemples Liste cha? née ou tableau algorithme de tri par insertion de tri rapide ? etc CPou

Analyse des algorithmes CLa question abordée dans ce chapitre est la suivante Comment choisir parmi les di ?érentes approches pour résoudre un problème Exemples Liste cha? née ou tableau algorithme de tri par insertion de tri rapide ? etc CPour comparer des solutions plusieurs points peuvent être pris en considération ? Exactitude des programmes démontrer que le résultat de l ? implantation est celui escompté ? Simplicité des programmes ? Convergence et stabilité des programmes il est souhaitable que nos solutions convergent vers la solution exacte la perturbation des données ne chamboule pas d ? une manière drastique la solution obtenue ? E ?cacité des programmes il est souhaitable que nos solutions ne soient pas lentes ne prennent pas de l ? espace mémoire considérable C ? Le point que nous allons développer dans ce chapitre est celui de l ? e ?cacité des algorithmes C ? Dé ?nition Un algorithme est un ensemble d ? instructions permettant de transformer un ensemble de données en un ensemble de résultats et ce en un nombre ?ni étapes ? Pour atteindre cet objectif un algorithme utilise deux ressources d ? une machine le temps et l ? espace mémoire C ? Dé ?nition la complexité temporelle d ? un algorithme est le temps mis par ce dernier pour transformer les données du problème considéré en un ensemble de résultats ? Dé ?nition la complexité spatiale d ? un algorithme est l ? espace utilisé par ce dernier pour transformer les données du problème considéré en un ensemble de résultats CComparaison de solutions Pour comparer des solutions entre-elles deux méthodes peuvent être utilisées ? Méthode empirique ? Méthode mathématique Cette comparaison se fera en ce qui nous concerne relativement à deux ressources critiques temps espace mémoire Dans ce qui suit nous allons nous concentrer beaucoup plus sur le temps d ? exécution CFacteurs a ?ectant le temps d ? exécution machine langage programmeur compilateur algorithme et structure de données Le temps d ? exécution dépend de la longueur de l ? entrée Ce temps est une fonction T n o? n est la longueur des données d ? entrée CExemple x la longueur des données dans ce cas est limitée à une seule variable Exemple sum for i i n i for j j n j sum En revanche dans ce cas elle est fonction du paramètre n CLa longueur des données d ? entrée dé ?nissant le problème considéré est dé ?nie comme étant l ? espace qu ? elle occupe en mémoire Cet espace est logarithmique de la valeur considérée Par exemple le nombre N occupe log N bits d ? espace mémoire CPire cas meilleur cas et cas moyen Toutes les entrées d ? une taille donnée ne nécessitent pas nécessairement le même temps d ? exécution Exemple soit à rechercher un élément C dans un tableau de n élément triés dans un ordre croissant Deux solutions s ? o ?rent à nous ? Recherche séquentielle dans un tableau de