Analyse amortie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, l'analyse amortie consiste à borner le temps d'exécution moyen d'un algorithme en le considérant globalement. Elle majore la complexité cumulée, en prenant en compte le fait que les cas chers surviennent rarement et isolément. L'analyse amortie est utile si la fréquence des cas les plus coûteux peut être bornée. Une analyse amortie garantie la performance moyenne de chaque opération dans le cas le plus défavorable[1]. L'analyse amortie est aussi une technique de conception d'algorithmes.

L'analyse amortie est liée à une structure de données et consiste alors, après avoir déterminé les opérations de base, à évaluer le coût cumulé d'une suite d'opérations.

Définition[modifier | modifier le code]

L'analyse amortie étudie la complexité (temporelle) d'une suite d'opérations effectuées sur une même structure de données. Elle répartit le surcoût de certaines opérations dispendieuses sur toutes les opérations en prenant en compte le fait que la plupart des opérations sont économes. Elle attribue à chaque opération d'une suite un temps qui est la moyenne arithmétique sur l'ensemble de ces opérations. Due aux compensations entre opérations (les opérations bon marché en temps contrebalançant les opérations coûteuses), ce temps est en général nettement meilleur que celui que donnerait une analyse dans le pire cas.

En répartissant les coûts élevés de certaines opérations sur toutes les opérations elle espère qu'un coût moyen raisonnable sera associé à chaque opération. La répartition du coût sur une séquence d'opération ressemble à un amortissement en comptabilité. Le résultat de cette analyse est une majoration de la performance moyenne de chaque opération.

L'analyse amortie peut être utilisée pour montrer que le coût moyen d'une opération est petit, si on en fait la moyenne sur une séquence d'opérations, et ce, même si cette opération est dispendieuse dans une séquence d'exécution. L'intérêt de cette démarche est donc de fournir une majoration de la complexité tout en donnant le poids qui leur revient (c'est-à-dire très faible) aux opérations les plus coûteuses d'une suite d'opérations[2]. En gros les opérations coûteuses le sont parce qu'elles réarrangent, une fois de temps en temps la structure de données, ce dont profitent toutes les autres opérations.

Mise en œuvre[modifier | modifier le code]

Trois méthodes peuvent être utilisées pour déterminer la complexité amortie d'un algorithme :

  • méthode par agrégation
  • méthode comptable
  • méthode du potentiel

La méthode de l'agrégat calcule le coût amorti de chaque opération comme une moyenne arithmétique des opérations dans le cas le plus défavorable. Le coût amorti est donc un majorant du coût moyen. Cette méthode affecte le même coût amorti à chaque opération.

La méthode comptable fait porter sur des opérations simples le coût des opérations complexes qu'elles occasionneront dans certaines exécutions seulement. Ce surcoût, présent lors de certaines exécutions d'une séquence, est ainsi totalement absorbé. Cette méthode affecte des coûts amortis éventuellement différents aux opérations différentes.

La méthode du potentiel associe les surcoûts à la structure de données, et non plus à une opération comme dans la méthode comptable. Conceptuellement, elle envisage un potentiel qui peut être libéré pour couvrir le surcoût de certaines opérations futures.

Différences avec l'analyse du cas moyen[modifier | modifier le code]

L'analyse amortie diffère de l'analyse du cas moyen pour les raisons suivantes :

  • dans l'analyse du cas moyen, on cherche à exploiter le fait que les cas onéreux sont peu probables 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 ne fait pas appel au calcul des probabilités mais on cherche à exploiter le fait que, dans une suite d'opérations partant d'une donnée quelconque, les cas onéreux ne peuvent pas se produire très souvent, ou de manière très rapprochée et que surtout ils profitent aux autres. Cette analyse requiert seulement que nous puissions caractériser le cas le plus défavorable lors de l'exécution d'une séquence d'opérations.

Exemple : les tableaux dynamiques[modifier | modifier le code]

Nous allons mettre en œuvre l'analyse amortie pour calculer la complexité temporelle d'un algorithme d'insertion dans un tableau dynamique. Pour simplifier, nous ferons l'hypothèse que notre structure de données est une zone de mémoire contigüe (un tableau) de quelque dizaines de cases sur laquelle la seule opération disponible est l'insertion. La taille de ce tableau peut augmenter si nécessaire. Pour ajouter un élément, ou bien le tableau contient encore au moins une case vide ou bien il est totalement rempli. Dans le premier cas l'adjonction du nouvel élément se fait en une opération élémentaire de copie. Dans le second cas, nous devons d'abord créer un nouveau tableau dont la taille sera supérieure à celle du tableau précédent, puis recopier les éléments qui y figuraient et finalement copier l'élément à ajouter.

Tant que le tableau n'est pas plein l'adjonction se fait en temps constant. Ce cas, qui est le plus courant, comprend deux opérations : l'écriture du nouvel élément dans la première case vide et l'incrémentation du compteur de remplissage du tableau.

En revanche quand le tableau est plein, ce qui est vrai plus rarement, il faut en allouer un autre et recopier tous les éléments ; la complexité est donc alors en O(n), où n est la taille du tableau courant.

L'analyse amortie s'applique particulièrement bien à ce type d'algorithme dans la mesure où le surcoût occasionné par la réallocation des données survient rarement et jamais deux fois de suite. Si n est la taille initiale du tableau, amortir la réallocation consistera à répartir également son coût sur les n premières adjonctions ainsi majorées de ce coût exceptionnel apparaissant dans le cas le plus défavorable.

En choisissant de façon adéquate le coefficient d'accroissement n du tableau, on peut s'assurer que le coût de l'insertion en fin de vecteur reste globalement marginal, c'est-à-dire en O(1) en moyenne amortie. Une bonne tactique peut consister à doubler la taille du tableau à chaque défaut[3].

Technique de conception d'algorithmes[modifier | modifier le code]

Historique[modifier | modifier le code]

L'une des première utilisations de l'analyse amortie a été faite par Robert Tarjan, un théoricien de l'informatique américain, pour développer une variante de la recherche dans un arbre binaire[4],[5]. Elle a été rendue populaire en analysant avec succès la structure de donnée Union-Find.

Notes et références[modifier | modifier le code]

  1. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to algorithms, Dunod,‎ 2009, 3e éd., 1292 p. (ISBN 978-0-262-03384-8). Chapitre 17, p. 472.
  2. alors que la complexité dans le pire des cas représente une borne extrêmement pessimiste car elle privilégie l'opération la plus coûteuse lors d'une exécution sur des données particulières qui forcent l'algorithme à se comporter de façon extrémale
  3. Voir le paragraphe expansion géométrique et coût amorti de l'article en anglais Dynamic array.
  4. Introduction to The design & Analysis of algorithms, Pearson, 2011, Anany Levitin, 3em edition, p. 49
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l’algorithmique, Dunod,‎ 2002, 2e éd., 1146 p. [détail de l’édition] (ISBN 2-10-003922-9) Chapitre 17. Notes. p. 419.

Bibliographie[modifier | modifier le code]