Analyse Amortie
- Analyse Amortie
-
Analyse amortie
L'analyse amortie d'un algorithme est une mesure de sa robustesse face aux pires cas. Certains algorithmes ont un bon comportement dans le cas général, et un comportement plus coûteux dans d'autres. Si on peut borner la fréquence de ce dernier cas, alors il est possible de calculer la complexité amortie de l'algorithme.
Exemple
L'insertion en fin de tableau : le coût dans le cas général est en O(1), puisqu'il suffit d'écrire le nouvel élément et d'augmenter le compteur de taille. Mais si le tableau est plein, il faut en allouer un autre et recopier tous les éléments; la complexité est donc en O(n). En choisissant correctement la nouvelle taille du tableau, on peut cependant s'assurer que cette opération reste marginale. Par exemple, si on rajoute N éléments à chaque fois, le tableau sera plein toutes les N opérations. La complexité d'ajout sera donc de ((N-1)*O(1)+O(N))/N, ce qui donne une complexité amortie de O(1).
Références
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction à l'algorithmique. MIT Press and McGraw-Hill, 2001. Chapitre 17.
Catégorie : Algorithmique
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Analyse Amortie de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Analyse amortie — En informatique, l analyse amortie consiste à borner le temps d exécution moyen d un algorithme lorsqu il est répété plusieurs fois de suite. Certains algorithmes ont un bon comportement dans le cas général, et un comportement plus coûteux dans d … Wikipédia en Français
Analyse Spectrale — En physique et dans diverses techniques apparaissent des signaux, fonctions du temps ou, plus exceptionnellement, d une variable d espace. L analyse spectrale recouvre plusieurs techniques de description de ces signaux dans le domaine des… … Wikipédia en Français
Analyse spectrale — En physique et dans diverses techniques apparaissent des signaux, fonctions du temps ou, plus exceptionnellement, d une variable d espace. L analyse spectrale recouvre plusieurs techniques de description de ces signaux dans le domaine des… … Wikipédia en Français
Complexité amortie d'une structure de donnée — Calculer la complexité amortie d une structure de donnée consiste, après avoir déterminé les opérations de base, à évaluer le coût cumulé d une suite d opérations. Voir aussi Analyse amortie Portail de l informatique théorique Cat … Wikipédia en Français
Tas de Fibonacci — En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la … Wikipédia en Français
Tas de fibonacci — En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la … Wikipédia en Français
Calcul spectral — Analyse spectrale En physique et dans diverses techniques apparaissent des signaux, fonctions du temps ou, plus exceptionnellement, d une variable d espace. L analyse spectrale recouvre plusieurs techniques de description de ces signaux dans le… … Wikipédia en Français
Méthode spectrale — Analyse spectrale En physique et dans diverses techniques apparaissent des signaux, fonctions du temps ou, plus exceptionnellement, d une variable d espace. L analyse spectrale recouvre plusieurs techniques de description de ces signaux dans le… … Wikipédia en Français
Problème spectral — Analyse spectrale En physique et dans diverses techniques apparaissent des signaux, fonctions du temps ou, plus exceptionnellement, d une variable d espace. L analyse spectrale recouvre plusieurs techniques de description de ces signaux dans le… … Wikipédia en Français
Exemples d'équations différentielles — Sommaire 1 Une équation différentielle linéaire 2 Une oscillation simple non amortie 3 Prise en compte de l amortissement 4 Voir aussi … Wikipédia en Français
