Analyse amortie? (Garanties de performance dans le pire des cas)

Qu'est-ce que l'analyse amortie? Et comment peut-il m'aider à obtenir les garanties de performances les plus défavorables dans mes programmes?

Je lisais que les techniques suivantes peuvent aider le programmeur à obtenir les garanties de performances les plus défavorables (c'est-à-dire, selon mes propres mots: garantir que le temps d'exécution d'un programme ne dépassera pas le temps d'exécution dans le pire casting):

• Algorithmes randomisés (par exemple, l'algorithme de tri rapide est quadratique dans le pire des cas, mais le classement aléatoire de l'entrée donne une garantie probabiliste que son temps de fonctionnement est linéithmique)
• Séquences d'opérations (notre analyse doit prendre en compte à la fois les données et la séquence d'opérations effectuées par le client)
• Analyse amortie (une autre façon de fournir une garantie de performance consiste à amortir le coût, en gardant une trace du coût total de toutes les opérations, divisé par le nombre d'opérations. Dans ce cadre, nous pouvons autoriser certaines opérations coûteuses, tout en conservant le coût moyen En d'autres termes, nous répartissons le coût des quelques opérations coûteuses, en affectant une partie de celles-ci à chacune d'un grand nombre d'opérations peu coûteuses)

L'auteur a mentionné l'utilisation du redimensionnement de la structure de données du tableau pour Stack comme un exemple de la façon de réaliser une analyse amortie, mais je ne comprends toujours pas ce qu'est l'analyse amortie et comment elle peut être réellement mise en œuvre (structure de données? Algorithme?) Pour obtenir le pire - garanties de performances de diffusion

Vous n'implémentez pas l'analyse amortie. C'est une technique pour obtenir des Olimites plus précises .

L'observation essentielle que vous devez faire est que des opérations coûteuses ne peuvent se produire à aucun moment.

Dans le cas d'une structure de données basée sur un tableau, le tableau doit être redimensionné de temps en temps - lorsqu'il est plein. C'est l'opération la plus coûteuse et prend du O(n)temps. Toutes les autres insertions dans le tableau le sont O(1).

Pour déterminer le temps d'exécution pour l'insertion d' néléments, vous pouvez multiplier npar l'opération la plus coûteuse O(n), ce qui se traduit par un comportement d'exécution global de O(n^2).

Cependant, cela est inexact car le redimensionnement ne peut pas se produire très souvent.

Lorsque vous parlez d'argent, vous amortissez le coût, lorsque vous remboursez votre dette avec plusieurs petits paiements au fil du temps.

Nous pouvons également utiliser ce modèle pour penser aux algorithmes. Nous substituons simplement le «temps» à «l'argent» pour éviter la cartographie mentale.

Une fois que le tableau est rempli à sa longueur n, nous pouvons doubler sa taille. Nous devons effectuer les opérations suivantes:

• Allouer des 2nmorceaux de mémoire
• copier des néléments

Si nous supposons que l'allocation de mémoire et la copie se produisent en temps linéaire, cela va être une opération très coûteuse. Cependant, nous pouvons maintenant utiliser l'idée de la dette et l'amortir pour notre analyse. Seulement, nous allons amortir notre dette avant de la faire.
Supposons que notre solde (argent / temps) soit de retour à 0 (c'est-à-dire que nous n'avons pas de dette ni de surplus) une fois que nous avons redimensionné le tableau.

Cela a l'implication suivante:

• L'insertion des néléments suivants couvrira le coût du redimensionnement et de la copie (nous avons nutilisé des emplacements et ndes emplacements inutilisés`)

Nous pouvons maintenant penser au montant que chaque opération d'insert doit payer:

• L'insert
• Le coût de l'allocation d'un morceau de mémoire
• le coût du déplacement vers la mémoire nouvellement allouée

Nous avons maintenant couvert les coûts d'allocation de mémoire, de copie et d'insertion des néléments suivants . Cependant, nous avons encore négligé d'allouer de l'espace pour les anciens néléments ainsi que de les copier.

Nous répartissons simplement les coûts de nos anciens néléments sur nos nouveaux éléments (à insérer) n:

• Le coût de l'allocation d'un morceau de mémoire
• le coût du déplacement vers la mémoire nouvellement allouée

Au total, chaque opération d'insertion coûtera 5 unités. Cela paie sa propre insertion, le déplacement et l'allocation d'espace pour lui-même et l'un des anciens éléments.

Chaque opération d'insertion prend toujours un temps constant, mais le redimensionnement est gratuit: nous l'avons amorti en consacrant plus de temps à chaque insertion.

Par conséquent, l'insertion d' néléments prend du O(n)temps.

D'autres techniques d'analyse amortie sont expliquées ici .

Tout d'abord: c'est une technique d'analyse des temps d'exécution des programmes, pas une technique d'implémentation des algorithmes.

L'exemple mentionné dans votre liste est bon: ajouter un seul élément à la structure de données basée sur un tableau. Pour chaque opération d'ajout, le pire des cas consiste à copier tous les éléments existants. Ce type d'analyse est beaucoup trop pessimiste, car vous n'avez pas à le faire si vous utilisez une stratégie de redimensionnement saine (en multipliant la taille par quelques x> 1,0). L'analyse indique ensuite que vous avez une limite O (n ^ 2) - O (n) par élément fois n éléments - alors que le temps d'exécution réel n'est que O (n).

Si vous faites la moyenne du coût de redimensionnement sur tous les éléments insérés (dont la plupart n'ont pas besoin d'être redimensionnés), vous effectuez une analyse amortie. L'analyse amortie donne une limite O (n) qui correspond au comportement réel de l'algorithme.