摊还复杂度分析——势能分析

2020-08-01 08:21:37


鸽着

一些定义

定义 $\phi(x)$ 为第 $x$ 次操作后的势能,$c(x)$ 为第 $x$ 次操作的实际复杂度,$a(x)$ 为第 $x$ 次操作的摊还复杂度。

定义 $a(x)=c(x)+\phi(x)-\phi(x-1)$。

则总复杂度$=\phi(n)-\phi(0)+\sum a(x)$。

如何理解?

我们可以这么理解:一次操作为下面的操作垫付了 $\phi(x)$ 的时间。

参考资料