Potential-Methode


Potential-Methode

Die Potenzial- bzw. Potenzialfunktionmethode ist eine Verfahrensweise der amortisierten Laufzeitanalyse.

Ziel dabei ist es, jeder Operation auf der betrachteten Datenstruktur einen mittleren Kostenwert zuzuweisen, um über diese die erwartete Laufzeit einer beliebigen Folge von Operationen nach oben abzuschätzen. Im Unterschied zur Bankkonto-Methode werden die Kosten ai einer Operation Opi nicht im Voraus festgesetzt, sondern hergeleitet. Hierzu wird eine Potenzialfunktion \Phi: D_i \to \mathbb{N} eingeführt. Diese ordnet jedem inneren Zustand Di der Datenstruktur ihr Potenzial zu. Seien ci nun die maximalen realen Kosten der Operation Opi, so ergibt sich der amortisierte Aufwand ai als:

a_i = c_i + \Phi\left(D_i\right) - \Phi(D_{i-1})

Gilt nun, dass das Potenzial des Initialzustandes D0 für alle Operationen Opi einer beliebigen Operationenfolge nie unterschritten wird:

  \forall i \in \{1,\dots,n\}: \Phi(D_0) \le \Phi(D_i)

Dann ist die Summe der realen Kosten nie höher als die der amortisierten Kosten:

\sum_{i=1}^n c_i \le \sum_{i=1}^n a_i

Existiert nun eine Konstante C, welche die obere Grenze der amortisierten Kosten jeder Operation angibt:

 i \in \{1,\dots,n\}:  a_i \le C

So können die Gesamtkosten der Operationenfolge mit n Operationen mit:

\sum_{i=1}^n c_i \le n \cdot C

angegeben werden.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Metra-Potential-Methode — Die Metra Potential Methode (MPM, auch Tätigkeits Knoten Darstellung oder Vorgangs Knoten Darstellung genannt) ist eine Netzplantechnik sowie eine Methode der Graphentheorie zur Berechnung von Netzplänen. Es handelt sich hierbei um ein sehr… …   Deutsch Wikipedia

  • Potential [1] — Potential ist eine Funktion V (x, y, z) des Ortes, d.h. der Koordinaten xyz eines Punktes P, deren partielle Differentialquotienten nach den Koordinaten die Komponenten einer gerichteten Größe (Kraft, Geschwindigkeit), die diesem Punkt P… …   Lexikon der gesamten Technik

  • Methode 635 — ist unter den Kreativitätstechniken eine Brainwriting Technik, was ein Problemlösungsverfahren zur Erzeugung von neuen, ungewöhnlichen Ideen in einer Gruppe von Menschen fördert. Sie wurde 1968 von dem Marketing und Unternehmensberater Bernd… …   Deutsch Wikipedia

  • Potential der einfachen Schicht — Als Potential der einfachen Schicht wird eine von Karl Rudolf Koch in den 1970er Jahren entwickelte Methode bezeichnet, mit der durch Einführung von Flächenbelegungen die Berechnung des Erdschwerefeldes vereinfacht oder beliebig verfeinert werden …   Deutsch Wikipedia

  • méthode nodale — mazgų potencialų metodas statusas T sritis automatika atitikmenys: angl. nodal analysis; nodal solution; nodal potential method; nodal voltage method; node voltage method vok. Knotenspannungsmethode, f rus. метод узловых потенциалов, m pranc.… …   Automatikos terminų žodynas

  • méthode nodale — mazginių potencialų metodas statusas T sritis radioelektronika atitikmenys: angl. nodal potential method; nodal voltage method vok. Knotenspannungsmethode, f rus. метод узловых потенциалов, m pranc. méthode nodale, f …   Radioelektronikos terminų žodynas

  • méthode de potentiel retardateur — vėlinamojo potencialo metodas statusas T sritis radioelektronika atitikmenys: angl. retarding potential method vok. Verzögerungspotentialmethode, f rus. метод задерживающего потенциала, m pranc. méthode de potentiel retardateur, f …   Radioelektronikos terminų žodynas

  • méthode potentiocinétique — potenciodinaminis metodas statusas T sritis Standartizacija ir metrologija apibrėžtis Tyrimo metodas, pagrįstas elektrodo poliarizavimu kintamuoju potencialu. atitikmenys: angl. potential sweep method; potentiodynamic method rus.… …   Penkiakalbis aiškinamasis metrologijos terminų žodynas

  • potential sweep method — potenciodinaminis metodas statusas T sritis Standartizacija ir metrologija apibrėžtis Tyrimo metodas, pagrįstas elektrodo poliarizavimu kintamuoju potencialu. atitikmenys: angl. potential sweep method; potentiodynamic method rus.… …   Penkiakalbis aiškinamasis metrologijos terminų žodynas

  • Metra Potential Method — Die Metra Potential Methode (MPM, auch Tätigkeits Knoten Darstellung oder Vorgangs Knoten Darstellung genannt) ist eine Netzplantechnik sowie eine Methode der Graphentheorie zur Berechnung von Netzplänen. Es handelt sich hierbei um ein sehr… …   Deutsch Wikipedia


Share the article and excerpts

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

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.