算法设计分析题，求高手解答，高分考虑堆栈S，其基本操作包括：push(S,x)－元素x入栈；pop(S)－栈顶元素弹出；multipop(S,k)：栈顶连续弹出k个元素（若栈中元素个数不足k个，则将栈弹空），

Question

算法设计分析题，求高手解答，高分
考虑堆栈S，其基本操作包括：push(S, x)－元素x入栈；pop(S)－栈顶元素弹出；multipop(S, k)：栈顶连续弹出k个元素（若栈中元素个数不足k个，则将栈弹空），假设每入栈或弹出一个元素的时间成本为O(1)。请分别用聚集分析法、记账分析法、势能函数分析法证明：对含任意n个上述栈操作的序列，该序列单个操作的平均时间成本至多为O(1)

Answer 1

聚集分析：n次操作最多的插入n个元素，插入删除元素个数数最多为2n，平均每次为2，即O(1)。
记账分析：设每次插入操作为2元，一元付账，一元存款，每删除一个元素(不管是pop还是multypop)为0元(插入该元素时已存了一元账)，n次操作最多付2n元，平均2元，即O(1)。
势能函数分析：设势能函数f(i)为第i次操作后栈中的元素个数，显然f(i)恒大于0，f(0)=0；每插入一个元素代价为2，1是该操作代价，1是用来存储势能，f(i)=f(i-1)+1，删除一个元素操作代价为0，但栈中元素个数少了1，f(i)=f(i-1)-1，或者删除k个元素，代价为0，但f(i)=f(i-1)-k，操作代价用势能支付了，n次操作后，实际代价最多2n，平均每次也是O(1)。