Java教程

复杂度分析

本文主要是介绍复杂度分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

复杂度分析

前言

\(O(x)\) 表示 \(x\) 的严格上界,\(\Omega(x)\) 表示 \(x\) 的严格下界,\(\Theta(x)\) 表示 \(x\) 的严格界(即严格上下界同阶)。

让人遗憾的是,人们在OI往往滥用了它们,严格来说,除了 \(O(1)\) 和 \(\Theta(1)\) 可以无歧义的混用,其他地方都应该保持谨慎。

均摊分析

势能分析

对于一类问题,某些操作可能会占用大量的时间,而另一些操作的代价则较小,导致整个算法的运行时间依然在可以接受的范围内。

举一个例子,一次压入一个数或者删除前一半的数,压入是 \(\Theta(1)\) 的,但删除的复杂度是 \(\Theta(\frac{|s|}{2})\) 的,其中 \(|s|\) 表示当前的数据量。假如操作 \(n\) 次,看起来我们的上界是 \(O(n^2)\),但仔细想一想,一个数至多被压入和删除各一次,贡献为 \(\Theta(1)\),数的个数至多有 \(n\) 个,于是复杂度为 \(O(n)\)。

对于类似的问题,一种更为泛用的方法是势能分析

联想物理中的保守力做功,我们往往习惯于定义一个势能去计算其贡献,再考虑其他部分,而这种势能往往是只和出初末状态相关的。

对于上面那个简单的例子,我们定义势函数 \(\phi=|s|\),操作 \(i\) 次后的势能为 \(\phi(i)\),总时间复杂度为 \(T(n)\)

则有

\[T(n)=\phi(n)-\phi(0)+\sum c(i)=\sum t(i) \]

其中 \(c(i)\) 第 \(i\) 次操作的实际复杂度,\(t(i)\) 表示均摊复杂度

形式化地,我们有

\[t(i)=c(i)+\phi(i)-\phi(i-1)=c(i)+\Delta\phi \]

实际上,对于一次 \(\Theta(1)\) 的压入

\[\phi(i+1)=\phi(i)+1\\ t(i+1)_\text{insert}=O(1)+\Delta\phi=O(1) \]

实际上,如果一次插入是log的话会更容易看出中间 \(O(1)\) 项的作用。这告诉我们,一个算法即使是基于均摊的,其复杂度上界也不一定是由势能贡献的

对于一次删除

\[\phi(i+1)=\frac{\phi(i)}{2}\\ t(i+1)_\text{delete}=\frac{|s|}{2}+\phi(i+1)-\phi(i)=0 \]

之前“存储”在势能中的能量被释放出来,完成了一次操作。

Splay

容易说明 \(Splay\) 的复杂度就是 \(splay\) 操作的复杂度(\(splay\) 之后就可以 \(O(1)\) 直接操作点了)

不是一般性的,设 \(Splay\) 的大小和操作次数均为 \(\Theta(n)\)

一次 \(splay\) 可以分为 \(zig,zag,zig-zig,zig-zag,zag-zig,zag-zag\) 六种,考虑 \(zig,zag\) 是对称的,于是只需要分析 \(zig,zig-zig,zig-zag\)

记一个点的子树大小为 \(siz\)

对于这种较为一复杂的数据结构,我们考虑定义每个点的势能,整个结构的势能就是每个点的势能之和

设一个点的势能为 \(\varphi_{node}\),\(Splay\) 的势能为 \(\phi\),操作 \(i\) 次后为 \(\phi(i)\)

\[\varphi_{node}=\log_2siz_{node}\\ \phi=\sum_{node\in Splay}\varphi_{node} \]

显然有势能上界为 \(O(n\log n)\),下界为 \(\Omega(log^2n)\)

于是

\[T(n)=\phi(n)-\phi(0)+\sum c(i)=O(n\log n)+\sum c(i) \]

只需放缩出 \(\sum c(i)\) 的上界即可

\[t(i)=c(i)-\Delta\phi(i) \]

\[c(i)=O(1) \]

画图之后合理放缩(画图太麻烦了,可以看看这个)

设 \(a(i)\) 表示一次旋转的复杂度

可以得到

\[a(i)\le 3(\varphi^\prime_{node}-\varphi_{node}) \]

对于一次 \(splay\),是由一段连续的旋转操作构成的,即

\[t(i)_{splay}=\sum_{j=a}^bO(\varphi^{(j)}_{node}-\varphi^{(j-1)_{node}})=O(\varphi^{last}_{node}-\varphi_node) \]

该节点初末势能的变化量,对于 \(\varphi_{node}\) 显然有其上界 \(O(\log n)\),下界 \(\Omega(1)\)

于是 \(t(i)_{splay}=O(\log n)\)

总的复杂度就是 \(O(n\log n)\)

LCT

\(LCT\) 的势能变化有链上的 \(Splay\) 和虚实边的变化两种,然后就发现所有操作都可以看做 \(access\)

依然假设树的大小和操作次数都为 \(\Theta(n)\)

还是考虑之前一样的做法

\[\varphi_{i}=\log siz_i\\ \phi=\sum\varphi_i \]

值得一提的,这里的 \(siz_i\) 表示所有虚边和实边连接的 \(i\) 的子树大小(也就是虚子树大小加 \(Splay\) 上的子树大小)

我们发现虽然 \(access\) 时,节点所属的 \(Splay\) 会改变,但这和直接合并成一条实链后再旋转没有区别(先不考虑跳虚边的复杂度),于是这一部分和 \(Splay\) 没有什么区别,依然是 \(O(n\log n)\)

再考虑虚实剖分的复杂度,和轻重剖分做比较,我们定义势函数为

\[\phi=\sum_{(u,v)\in LCT}[siz_u\le2siz_v\and fa_v=u\and son_u\ne v] \]

可以改写为更加显然的形式

\[\phi=\sum_{(u,v)\in LCT}[v\text{是}u\text{的重儿子}\and(u,v)\text{为虚边}] \]

轻重链剖分中,我们知道一个点到根的路径上至多有 \(O(\log n)\) 条轻边,自然至多产生 \(O(\log n)\) 条重虚边,而对于原本的重虚边,需要花费 \(\Theta(1)\) 的代价使之变为重实边,不会产生重虚边,于是这一部分的复杂度上界也为 \(O(n\log n)\)

至此就说明了 \(LCT\) 是均摊 \(O(n\log n)\) 的

这篇关于复杂度分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!