Diskussion:Potentialfunktionmethode

Hmm, also ich hab jetzt schon mehrere Quellen zur Potenzialfunktion-Methode gelesen und in allen steht, dass $\Phi :D_{i}\rightarrow \mathbb {R}$ ist. Wie kommt es, dass das hier anders ist? {{subst:unsigned|85.183.158.13|20:43, 4. Jan. 2007}

Ich vermute mal dass der Wertebereich hier eine geringe Rolle spielt, da am Schluss ja nur die Differenz zählt. 92.226.149.137 14:27, 17. Aug. 2008 (CEST)

Ich habe das mal geändert, da auch im Artikel zu Potentialfunktion der Wertebereich $\mathbb {R}$ ist. -- Moritz schlarb 14:40, 11. Dez. 2011 (CET)

Verständnisfragen

1. (Nur am Rande:) Bezeichnet $D_{i}$ hier also die Menge der möglichen Zustände der Datenstruktur nach Ausführung der Operation $Op_{i}$?
2. Mich verwirrt die Aussage der Potenzialfunktionmethode. Im Endeffekt lese ich hier, dass die Summe der Realkosten beliebiger Operationen auf einer Datenstruktur grundsätzlich höchstens linear wachsend ist, was ja nicht sein kann -- offensichtlich habe ich etwas übersehen. Was? Bzw., eine Unklarheit:
3. Für $n$ Operationen wird eine Abschätzung der maximalen amortisierten Kosten vorgenommen; aber diese obere Schranke $C$ kann doch -- in Abhängigkeit von $n$ -- auch wachsen und somit beliebig groß werden? Verwirrt so nicht die Darstellung als $\leq C\cdot n$ nicht etwas?

Mir scheint, als hätte ich die Pointe bei der Potenzialfunktionmethode noch nicht ganz erfasst... :-) -- the contented ^[D] 00:00, 10. Feb. 2010 (CET)

Ist zwar schon etwas her, aber ich antworte trotzdem mal: Der Punkt ist, dass keine Konstante als obere Schranke existieren muss. Der Artikel suggeriert ein wenig, dass das für eine amortisierte Analyse notwendig ist. Ich habe zumindest mal ein "beispielsweise" davor gesetzt um zu zeigen, dass das nicht immer der Fall ist. --141.44.233.233 12:28, 25. Jan. 2012 (CET)