摊还分析与动态表
摊还分析(Amortized Analysis)
通常算法分析的“目标问题”都是给定1个规模为\(n\)的数据结构和1个算法,分析该算法关于\(n\)的代价并表示为\(O(f(n))\)。如果在此基础上继续分析“在该数据结构连续执行\(k\)次该算法”的问题,用乘法可得\(O(kf(N))\),其中\(N\)是\(k\)次中最大的\(n\)。由于\(O\)是上界所以该结论完全正确,但可能不够“精确”(离确界不够近)。因为没考虑到每次算法执行后,数据结构本身的变化。如果考虑到,则可能得到小于\(O(kf(N))\)的界,并且其更能反映出该场景下的真实代价。
举例说明上述观点,假设有个“包含\(popAll\)运算”的栈,其除了能\(O(1)\)完成\(push,pop,top\),还支持\(popAll\)运算,其实现是“循环\(pop\)直到栈顶为空”,如果\(popAll\)执行前栈中有\(n\)个元素,\(popAll\)的代价就是\(O(n)\)。然后带入场景“这个栈是某算法的一部分,该算法会多次调用这个栈的\(push,pop,popAll\),由于这个算法很复杂,不能确定每次都调用什么运算,也不能确定每次调用前栈的元素数。只知道算法开始时栈是空的”。由于不知道元素数,\(popAll\)的\(O(n)\)代价就不精确了,但我们很想衡量这个栈在该算法中的性能表现,所以构造下面这个需要做算法分析的“目标问题”:… 阅读全文