Home | | Programming and Data Structure II | Potential Method

Chapter: Programming and Data structures : Advanced Non-Linear Data Structures

Potential Method

Same as accounting method: something prepaid is used later.

THE POTENTIAL METHOD:

 

         Same as accounting method: something prepaid is used later.

 

         Different from accounting method

 

–   The prepaid work not as credit, but as “potential energy”, or “potential”.

 

The potential is associated with the data structure as a whole rather than with specific objects within the data structure.

 

         Initial data structure D0, n operations, resulting in D0, D1,…, Dn with costs c1, c2,…, cn.

 

         A potential function F: {Di} à R (real numbers)

 

         F(Di) is called the potential of Di.

 

         Amortized cost ci' of the ith operation is:

 

ci' = ci + F(Di) - F(Di-1). (actual cost + potential change)

 

åi=1n ci' = åi=1n (ci + F(Di) - F(Di-1))

 

= åi=1nci + F(Dn) - F(D0)

 

         If F(Dn) ³ F(D0), then total amortized cost is an upper bound of total actual cost.

 

         But we do not know how many operations, so F(Di) ³ F(D0) is required for any i.

 

         It is convenient to define F(D0)=0,and so F(Di) ³0, for all i.

 

         If the potential change is positive (i.e., F(Di) - F(Di-1)>0), then ci' is an overcharge (so store the increase as potential), otherwise, undercharge (discharge the potential to pay the actual cost).

 

 

Potential method: stack operation

 

         Potential for a stack is the number of objects in the stack.

 

         So F(D0)=0, and F(Di) ³0

 

         Amortized cost of stack operations:

 

–   PUSH:

 

         Potential change: F(Di)- F(Di-1) =(s+1)-s =1.

 

         Amortized cost: ci' = ci + F(Di) - F(Di-1)=1+1=2.

 

–   POP:

 

         Potential change: F(Di)- F(Di-1) =(s-1) –s= -1.

 

         Amortized cost: ci' = ci + F(Di) - F(Di-1)=1+(-1)=0.

 

–   MULTIPOP(S,k): k'=min(s,k)

 

         Potential change: F(Di)- F(Di-1) = –k'.

 

         Amortized cost: ci' = ci + F(Di) - F(Di-1)=k'+(-k')=0.

 

         So amortized cost of each operation is O(1), and total amortized cost of n operations is O(n).

 

         Since total amortized cost is an upper bound of actual cost, the worse case cost of n operations is O(n).

 

 

Potential method: binary counter

 

         Define the potential of the counter after the ith INCREMENT is F(Di) =bi, the number of 1‟s. clearly, F(Di)³0.

 

         Let us compute amortized cost of an operation

 

–   Suppose the ith operation resets ti bits.

 

–   Actual cost ci of the operation is at most ti +1.

 

–   If bi=0, then the ith operation resets all k bits, so bi-1=ti=k.

 

–   If bi>0, then bi=bi-1-ti+1

 

–   In either case, bi£bi-1-ti+1.

 

–   So potential change is F(Di) - F(Di-1) £bi-1-ti+1-bi-1=1-ti.

 

–   So amortized cost is: ci' = ci + F(Di) - F(Di-1) £ ti +1+1-ti=2.

 

         The total amortized cost of n operations is O(n).

 

         Thus worst case cost is O(n).

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Advanced Non-Linear Data Structures : Potential Method |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.