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'autres. L'analyse amortie est utile si on peut borner la fréquence de ce dernier cas.

L'analyse amortie est différente de l'analyse en moyenne :

  • dans l'analyse en moyenne, on cherche à exploiter le fait que le pire cas est peu probable en faisant des hypothèses sur la distribution des entrées ou sur les choix aléatoires effectués dans l'algorithme ;
  • dans l'analyse amortie, on cherche à exploiter le fait que le pire cas de l'algorithme ne peut pas se produire plusieurs fois consécutivement, ou de manière trop rapprochée, quelle que soit l'entrée.

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 de façon adéquate le coefficient d'accroissement du tableau, on peut s'assurer que le coût de cette opération reste globalement marginal.

Par exemple, si on ajoute N éléments à chaque fois que c'est nécessaire, le tableau sera plein toutes les N opérations. La complexité d'ajout sera donc de \frac{\scriptscriptstyle (N-1)*O(1)+O(N)}{\scriptscriptstyle 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.

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 — 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… …   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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”