算法设计分析题,求高手解答,高分

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)。