amortized analysis

势能函数的设计

对于 Splay 树，其势能函数设计为 \(\phi(x)=\log(size(x)),\phi(T)=\sum_{i=1}^n \log(size(x))\)

为什么要这么设计呢

看起来，这个函数是构造出来的，为了证明单次操作均摊 \(O(\log n)\) 而构造的

事实上，如果势能函数设计为 \(\phi(x)=size(x)\),\(\phi(x)=\sqrt{size(x)}\) ,可以分别证出均摊复杂度为 \(O(n)\) 和 \(O(\sqrt{n})\)

所以，势能函数的设计大概是在不断缩减复杂度上界，直至当前的势能函数无法证出均摊复杂度为目标复杂度为止

例如，如果设计势能函数为 \(\log\log size(x)\), 则 \(zig-zag\) 操作：

\(\hat c_i=2+\phi'(x)-\phi(x)+\phi'(p)-\phi(p)+\phi'(g)-\phi(g)\leq 2+\phi'(p)+\phi'(g)-2*\phi(x)\)

\(2+\phi'(p)+\phi'(g)=\log(4\log szp\log szg)\leq\log((\log szp+\log szg)^2)=2\log(\log(szp*szg))\leq 2\log(\log(szx^2))=2\log(2\log szx)=2\log2+2\log\log szx=2+\log\log szx\)

仍然带有常数 \(2\), 而一次Splay经过 \(x_1,\cdots,x_h\) 这些点，总的势能变化 \(= c\times h+3\times(\phi(rt)-\phi(x))\)

与高度 \(h\) 有关，而高度 \(h=O(\log(n))\), 所以单次操作 \(\log n\), 与假设矛盾

这是使用 Splay 正常的证明思路尝试证明复杂度 \(\log\log n\), 可以发现这种证明思路证不出来

其他的思路大概也是证不出来的, ~~不然就坏事了~~

• 思考：栈的 multipop 和 multipush 的摊还代价各是多少？

势能函数的合理性

一般我们有 \(\phi(n)\geq 0\), 但有些时候，我们设计出的函数 \(\phi(0)\) 不一定为\(0\), 这时我们有

\[\frac{\sum c_i}{n}=\frac{\sum \hat c_i}{n}+\frac{\phi(0)-\phi(n)}{n}\leq\max{\hat c_i}+\frac{\phi(0)}{n}(\phi(n)\geq0)=T(n)+\frac{\phi(0)}{n},\lim_{n\to\infty}\frac{\sum c_i}{n}=T(n)(\phi(0)为常数)\]

均摊分析的意义

例：证明二叉堆 INSERT 为 \(O(\log n)\), EXTRACT-MIN 为 \(O(1)\)

看起来很诡，一个堆为什么有 \(O(1)\) 操作, 实际的操作最坏都是 \(O(\log n)\) 的

但其实是想说明, 在平均了 INSERT 和 EXTRACT-MIN 两个操作后, 可以使 EXTRACT-MIN 为 \(O(1)\)

例如, 设计势能函数 \(\displaystyle \phi(D)=c\sum_{x\in D} d(x)\)

那么 INSERT 操作 \(\hat c_i=c_i+\phi_i-\phi_{i-1}\leq 2\log n=O(\log n)\)

EXTRACT-MIN 操作 \(\hat c_i=c_i+\phi_i-\phi_{i-1}= \log n-\log n=O(1)\)

所以, 说 EXTRACT-MIN 为 \(O(1)\) 实际是把它的复杂度摊到了 INSERT 上

这种证明方式和 Fibonacci Heap 很像, 是为了在理论复杂度上给出一个优势

至于实际表现, 还要看常数

不过普通二叉堆和 Fibonacci Heap 确实快