可能有不少不严谨之处，太菜了请谅解。
之前对于 \(\text{splay}\) 的复杂度一直不是很懂，今天进行了一个势能分析的学习。
势能分析，就是借助势能函数，将中间过程用势能函数来刻画以得到发杂度的一个上界，这样分析出来的一般是均摊复杂度。
例如，第 \(i\) 此操作的代价是 \(c_i\)，那么设第 \(i\) 次操作的复杂度 \(C_i\) 是：
\[C_i = c_i + \phi(i) - \phi(i-1) \]即
\[\sum {C_i} = \sum {c_i} + \phi(n) - \phi(0) \]若 \(\sum{c_i}\) 和 $ \phi(n) - \phi(0) $ 存在一个上界，那么我们就算出了一个复杂度的上界。
一些例子：
1. 栈
维护一个栈，支持 \(\mathrm{push}\)，\(\mathrm{pop}\)，\(\mathrm{multipop}\) 三种操作，\(\mathrm{push}\) 和单次 \(\mathrm{pop}\) 的复杂度都是 \(O(1)\)，进行 \(n\) 次操作，分析其复杂度。
直觉来看，复杂度是 \(O(n)\) 的，怎么证明呢？现定义势能函数 \(\phi(i)\) 为第 \(i\) 次操作后栈内元素个数。那么：
- \(\mathrm{push}\)：\(C_i = c_i + \phi(i) - \phi(i-1) = 1 + 1 =2\)
- \(\mathrm{pop}\)：\(C_i = c_i + \phi(i) - \phi(i-1) = 1 - 1 =0\)
- \(\mathrm{multipop(k)}\)：\(C_i = c_i + \phi(i) - \phi(i-1) = k - k =0\)
\(n\) 次操作，因此复杂度 \(O(n)\)。
2. 二进制加法
一个二进制数，从 \(1\) 加到 \(n\)。证明时间复杂度。
定义 \(\phi(i)\) 为第 \(i\) 次操作后 \(1\) 的个数。
一次加 \(1\) 相当于 \(k\) 次 \(1 \rightarrow 0\) 和一次 \(0 \rightarrow 1\)，则：
\[C_i = c_i + \phi(i) - \phi(i-1) = k + 1 + \phi(i-1) - k + 1 - \phi(i-1) = 2 \]一次操作均摊 \(O(1)\)，总的就是 \(O(\log n)\)。
2.5 一些理解
- 势能分析的作用，就在于通过设计函数，把时间长的操作拼到时间短的上面。
- 由上一条的启发，我们得到一个设计函数的思路：执行时间长的操作时，势能一般是降低的，时间短的操作时反之。
- \(C_i = c_i + \phi(i) - \phi(i-1)\)，中间的代价和势能之间的相加有什么意义吗？其实这没有任何实际意义，只是我们利用其来进行一个平衡。
3. Splay
现在要设计一个势能函数，根据我们的直觉，势能函数理应与 \(\mathtt{Splay}\) 的平衡有关。
下面记 \(\left|x\right|\) 为 \(x\) 子树的大小。
若一 \(n\) 个点的 \(\mathtt{Splay}\) 进行了 \(m\) 次 \(\mathtt{Splay}\) 操作。
记 \(\phi(i) = \log(size(i))\)，整棵 \(\mathtt{Splay}\) 的势能函数 \(\Phi(T) = \sum{\phi(x)}\)。
则一次旋转的代价为 \(C_i = O(1) + \Delta\Phi(T)\)。
设要旋转的节点为 \(x\)，其父亲和父亲的父亲分别为 \(y\) 和 \(z\)，那么：
- 进行一次 \(\text{zig}\) 操作时：
- 进行 \(\text{zig-zag}\) 操作时：
然后进行一个神秘的放缩：
因为旋转后
\[\left|x'\right| > \left|y'\right| + \left|z'\right| \]因此
\[\phi'(z) + \phi'(y) - 2\phi'(x) < -1 \]所以
\[\begin{align*} C_i & = 1 + \phi'(y) + \phi'(z) - \phi(x) -\phi(y)\\ & \le \phi'(y) + \phi'(z) - \phi(x) -\phi(y) - (\phi'(z) + \phi'(y) - 2\phi'(x))\\ & = 2\phi'(x) - \phi(x) - \phi(y)\\ & \le 2(\phi'(x) - \phi(x)) \end{align*} \]- 进行 \(\text{zig-zig}\) 操作时：
又因为
\[\begin{equation} \left|x'\right| = \left|x\right| + \left|z'\right| + 1 \end{equation}\]因此
\[\phi(x) + \phi(z') - 2\phi'(x) = \log \frac{|x||z'|}{|x'|} < \log \frac{|x'|}{4|x'|} = -2 < -1 \]代换得：
\[\begin{align*} C_i & = 1 + \phi'(y) + \phi'(z) - \phi(x) -\phi(y) \\ & = \phi'(y) + \phi'(z) - \phi(x) -\phi(y) - (\phi(x) + \phi(z') - 2\phi'(x)) \\ & \le \phi'(x) + \phi'(z) - \phi(x) -\phi(x) - (\phi(x) + \phi(z') - 2\phi'(x)) \\ & = 3(\phi'(x) -\phi(x)) \end{align*} \]- 如果 \(\text{zig-zig}\) 操作两次都转的是 \(x\) 的话，\((1)\) 式就不在成立，我们也很难通过放缩把那个 \(O(1)\) 消掉，那复杂度就不对了。
综上，除了最后一次旋转外，其余的常数都被我们消掉了。因此一次 \(Splay\) 复杂度为 \(O(1) + 3(\phi(root) - \phi(x_0)) < 3\log n\)。
\(m\) 次操作，总复杂度为 \(m\log n + \Delta \Phi(T) = (m+n)\log n\)。
4. LCT
咕咕咕~
标签：分析,势能,align,phi,关于,操作,复杂度,mathrm From： https://www.cnblogs.com/11-twentythree/p/18355623