Méthode potentielle - Potential method

Dans la théorie de la complexité computationnelle , la méthode potentielle est une méthode utilisée pour analyser la complexité en temps et en espace amortis d'une structure de données , une mesure de ses performances sur des séquences d'opérations qui atténue le coût des opérations peu fréquentes mais coûteuses.

Définition du temps amorti

Dans la méthode potentielle, une fonction Φ est choisie qui mappe les états de la structure de données à des nombres non négatifs. Si S est un état de la structure de données, Φ ( S ) représente le travail qui a été comptabilisé («payé») dans l'analyse amortie mais pas encore effectué. Ainsi, Φ ( S ) peut être considéré comme le calcul de la quantité d' énergie potentielle stockée dans cet état. La valeur potentielle avant l'opération d'initialisation d'une structure de données est définie comme étant zéro. Alternativement, Φ ( S ) peut être considéré comme représentant la quantité de désordre dans l'état S ou sa distance par rapport à un état idéal.

Soit o toute opération individuelle dans une séquence d'opérations sur une structure de données, avec S _{avant de} désigner l'état de la structure de données avant l'opération o et S _{après avoir} dénoté son état une fois l'opération o terminée. Une fois Φ choisi, le temps amorti de l'opération o est défini comme étant

${\ displaystyle T _ {\ mathrm {amorti}} (o) = T _ {\ mathrm {réel}} (o) + C \ cdot (\ Phi (S _ {\ mathrm {après}}) - \ Phi (S _ {\ mathrm {avant}})),}$

où C est une constante non négative de proportionnalité (en unités de temps) qui doit rester fixe tout au long de l'analyse. C'est-à-dire que le temps amorti est défini comme étant le temps réel pris par l'opération plus C fois la différence de potentiel provoquée par l'opération.

Lors de l'étude de la complexité de calcul asymptotique en utilisant la notation big O , les facteurs constants ne sont pas pertinents et la constante C est donc généralement omise.

Relation entre le temps amorti et le temps réel

Malgré son apparence artificielle, le temps total amorti d'une séquence d'opérations fournit une limite supérieure valide sur le temps réel pour la même séquence d'opérations.

Pour toute séquence d'opérations , définissez: ${\ displaystyle O = o_ {1}, o_ {2}, \ dots, o_ {n}}$

• Le temps total amorti: ${\ displaystyle T _ {\ mathrm {amorti}} (O) = \ sum _ {i = 1} ^ {n} T _ {\ mathrm {amorti}} (o_ {i}),}$
• Le temps réel total: ${\ displaystyle T _ {\ mathrm {réel}} (O) = \ sum _ {i = 1} ^ {n} T _ {\ mathrm {réel}} (o_ {i}).}$

Ensuite:

${\ displaystyle T _ {\ mathrm {amorti}} (O) = \ sum _ {i = 1} ^ {n} \ left (T _ {\ mathrm {réel}} (o_ {i}) + C \ cdot (\ Phi (S_ {i}) - \ Phi (S_ {i-1})) \ right) = T _ {\ mathrm {réel}} (O) + C \ cdot (\ Phi (S_ {n}) - \ Phi (S_ {0})),}$

où la séquence de valeurs de fonction potentielles forme une série télescopique dans laquelle tous les termes autres que les valeurs de fonction potentielle initiale et finale s'annulent par paires. En réorganisant cela, nous obtenons:

${\ displaystyle T _ {\ mathrm {réel}} (O) = T _ {\ mathrm {amorti}} (O) -C \ cdot (\ Phi (S_ {n}) - \ Phi (S_ {0})). }$

Depuis et , donc le temps amorti peut être utilisé pour fournir une limite supérieure précise sur le temps réel d'une séquence d'opérations, même si le temps amorti pour une opération individuelle peut varier considérablement de son temps réel. ${\ displaystyle \ Phi (S_ {0}) = 0}$${\ displaystyle \ Phi (S_ {n}) \ geq 0}$${\ displaystyle T _ {\ mathrm {réel}} (O) \ leq T _ {\ mathrm {amorti}} (O)}$

Analyse amortie des données les plus défavorables

En règle générale, l'analyse amortie est utilisée en combinaison avec une hypothèse du pire des cas concernant la séquence d'entrée. Avec cette hypothèse, si X est un type d'opération qui peut être effectué par la structure de données, et n est un entier définissant la taille de la structure de données donnée (par exemple, le nombre d'éléments qu'elle contient), alors le temps amorti pour les opérations de type X est défini comme étant le maximum, parmi toutes les séquences possibles d'opérations sur des structures de données de taille n et toutes les opérations o _i de type X dans la séquence, du temps amorti pour l'opération o _i .

Avec cette définition, le temps pour effectuer une séquence d'opérations peut être estimé en multipliant le temps amorti pour chaque type d'opération de la séquence par le nombre d'opérations de ce type.

Exemples

Tableau dynamique

Un tableau dynamique est une structure de données permettant de gérer un tableau d'éléments, permettant à la fois un accès aléatoire aux positions dans le tableau et la possibilité d'augmenter la taille du tableau de un. Il est disponible en Java sous le type "ArrayList" et en Python sous le type "liste".

Un tableau dynamique peut être mis en œuvre par une structure de données consistant en un tableau A d'éléments, d'une certaine longueur N , avec un nombre n  ≤  N représentant les positions dans le tableau qui ont été utilisées jusqu'à présent. Avec cette structure, des accès aléatoires au tableau dynamique peuvent être mis en œuvre en accédant à la même cellule du tableau interne A , et lorsque n  <  N une opération qui augmente la taille du tableau dynamique peut être implémentée simplement en incrémentant  n . Cependant, lorsque n  =  N , il est nécessaire de redimensionner A , et une stratégie courante pour ce faire est de doubler sa taille, en remplaçant A par un nouveau tableau de longueur 2 n .

Cette structure peut être analysée à l'aide de la fonction potentielle:

Φ = 2 n  -  N

Puisque la stratégie de redimensionnement fait toujours que A soit au moins à moitié plein, cette fonction potentielle est toujours non négative, comme souhaité.

Lorsqu'une opération d'augmentation de taille ne conduit pas à une opération de redimensionnement, Φ augmente de 2, une constante. Par conséquent, le temps réel constant de l'opération et l'augmentation constante du potentiel se combinent pour donner un temps amorti constant pour une opération de ce type.

Cependant, lorsqu'une opération d'augmentation de taille provoque un redimensionnement, la valeur potentielle de n diminue à zéro après le redimensionnement. L'allocation d'un nouveau tableau interne A et la copie de toutes les valeurs de l'ancien tableau interne vers le nouveau prend O ( n ) temps réel, mais (avec un choix approprié de la constante de proportionnalité C ) ceci est entièrement annulé par la diminution de la fonction potentielle, laissant à nouveau un temps total amorti constant pour l'opération.

Les autres opérations de la structure de données (lecture et écriture des cellules du tableau sans changer la taille du tableau) ne provoquent pas le changement de la fonction potentielle et ont le même temps amorti constant que leur temps réel.

Par conséquent, avec ce choix de stratégie de redimensionnement et de fonction potentielle, la méthode potentielle montre que toutes les opérations de tableau dynamique prennent un temps amorti constant. En combinant cela avec l'inégalité relative au temps amorti et au temps réel sur des séquences d'opérations, cela montre que toute séquence de n opérations de tableau dynamique prend O ( n ) temps réel dans le pire des cas, malgré le fait que certaines des opérations individuelles peuvent elles-mêmes prendre une durée linéaire.

Lorsque le tableau dynamique comprend des opérations qui réduisent la taille du tableau et l'augmentent, la fonction potentielle doit être modifiée pour éviter qu'elle ne devienne négative. Une façon de faire est de remplacer la formule ci-dessus pour Φ par sa valeur absolue .

Pile multi-pop

Considérez une pile qui prend en charge les opérations suivantes:

• Initialiser - crée une pile vide.
• Pousser - ajoutez un seul élément au-dessus de la pile, en agrandissant la pile de 1.
• Pop ( k ) - supprime k éléments du haut de la pile, où k n'est pas supérieur à la taille actuelle de la pile

Pop ( k ) nécessite un temps O ( k ), mais nous souhaitons montrer que toutes les opérations prennent un temps amorti O (1).

Cette structure peut être analysée à l'aide de la fonction potentielle:

Φ = nombre d'éléments dans la pile

Ce nombre est toujours non négatif, selon les besoins.

Une opération Push prend un temps constant et augmente Φ de 1, donc son temps amorti est constant.

Une opération Pop prend du temps O ( k ) mais réduit également Φ de k , de sorte que son temps amorti est également constant.

Cela prouve que toute séquence de m opérations prend un temps réel O ( m ) dans le pire des cas.

Compteur binaire

Considérez un compteur représenté comme un nombre binaire et prenant en charge les opérations suivantes:

• Initialiser: créez un compteur avec la valeur 0.
• Inc: ajoutez 1 au compteur.
• Lire: renvoie la valeur actuelle du compteur.

Pour cet exemple, nous n'utilisons pas le modèle de machine transdichotomique , mais demandons à la place une unité de temps par opération de bit dans l'incrément. Nous souhaitons montrer que Inc prend du temps amorti O (1).

Cette structure peut être analysée à l'aide de la fonction potentielle:

Φ = nombre de bits égal à 1 = poids marteau (compteur)

Ce nombre est toujours non négatif et commence par 0, selon les besoins.

Une opération Inc retourne le bit le moins significatif . Ensuite, si le LSB a été basculé de 1 à 0, le bit suivant est également basculé. Cela continue jusqu'à ce que finalement un bit soit basculé de 0 à 1, moment auquel le retournement s'arrête. Si le compteur se termine initialement par k 1 bits, on retourne un total de k +1 bits, en prenant le temps réel k +1 et en réduisant le potentiel de k −1, donc le temps amorti est de 2. Par conséquent, le temps réel pour exécuter m Opérations Inc est O ( m ).

Applications

La méthode de la fonction potentielle est couramment utilisée pour analyser les tas de Fibonacci , une forme de file d'attente prioritaire dans laquelle la suppression d'un élément prend un temps amorti logarithmique, et toutes les autres opérations prennent un temps amorti constant. Il peut également être utilisé pour analyser les arbres de splay , une forme auto-ajustable d' arbre de recherche binaire avec un temps amorti logarithmique par opération.

Références