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 algorithmique complexite des algorithmes recursifs algorithme de la programmation dynamique

Complexité algorithmique Complexité des algorithmes récursifs Algorithme de la programmation dynamique C - Complexité algorithmique CIntroduction CComment 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 ? Exactitude des programmes ? Simplicité des programmes ? Convergence et stabilité des programmes ? E ?cacité des programmes C ? 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 ? Temps 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 ? L ? espace 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 CFacteurs a ?ectant 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 CPire cas meilleur cas et cas moyen 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 C Recherche séquentielle dans un tableau de taille n Commencer au début du tableau et considérer chaque élément jusqu ? à ce que l ? élément cherché soit trouvé soit déclaré inexistant Recherche dichotomique tient compte du fait que les éléments du tableau soient déjà triés Information ignorée par l ? algorithme de la recherche séquentielle Ces deux algorithmes sont présentés comme suit CProcédure Recherche T Tab x Entier Variables i Entier Début i ? Répéter i ? i Jusqu ? à T i x ou i n Si T i x Alors Ecrire ? Indice ? i Sinon Ecrire ? Elément introuvable ? ? FinSi Fin Cint recherche int tab int C int i i while i ?n de la fonction CProcédure Rechdicho T Tab x entier Variables premier milieu dernier Entier trouve Booléen Début Premier ? dernier ? n Trouve ? Faux Répéter Milieu ? premier dernier div Si x T milieu Alors dernier ? milieu ?? Sinon Si x