浅谈摊还分析

前言

摊还分析最初用于计算一些单步时间复杂度可能较高,但整体时间复杂度并不是很高的问题,后面我们可以将它推广。摊还分析与期望时间复杂度有一定区别,其往往表示的是一种上界。
本文主要介绍势能法这一种摊还分析的方法。为了方便表示,本文忽略一些常数,所以可能不是很严谨。

引入

聚合法

聚合法是一种暴力的方法,简单来说就是把东西换一种方法加起来然后除以操作次数。这样我们可以得到单次操作比较紧的一个平均上界。

2个例子

假设我们要实现一个单调栈,在压入一个元素的时候要将前面比它劣的元素都弹出栈,那么单次操作有可能弹出了n个元素,那么n次操作就是$O(n^2)$。显然这个上界太宽了,我们不可能每次都弹出这么多。
换一种想法:每一个元素最多进栈一次,出栈一次,所以是$O(n)$,单词操作平均$O(1)$。
那么这个想法其实就是聚合法。
KMP算法的时间复杂度证明也是类似的。由于往next上跳会减少当前位置的next值,所以最多跳$O(n)$次,因此它单步平均$O(1)$。

动态表扩张算法

我们都知道想要二分就需要内存空间是连续的,那么C++中的vector是如何保证在能支持push_back的前提下支持lower_bound等函数的呢?
这里用到了一种动态表扩张算法。
一开始先开1的空间,每次加入元素时如果空间足够就直接加入,如果空间不够,就获取两倍于原先空间的连续内存,把整个表全部搬过去,然后再加入。
乍看之下发现新开空间的时候单步可能有$O(n)$的代价。其实其平均时间复杂度是$O(1)$的。这个用聚合法非常好证:
那么我们第i次操作的代价$c_i=i\lbrack i=2^k,k\in Z\rbrack +1$
我们把这个两部分分开来算就可以得到:
$\sum c_i\le 3n$
那么单步就是$O(1)$的了

摊还复杂度

摊还分析的另一种方法是记账法,这里不做详细介绍。
想想一下,您需要管理您的零花钱,您每天花的钱是固定的(也就是实际每步的时间复杂度),您需要安排一种合适的零花钱获取方式(我们称为摊还复杂度),使得您每次需要花钱时都有足够的钱可以花(摊还复杂度合法)。符合这个条件的话,显然您赚的钱一定会不小于您花的钱(也就是摊还复杂度的总和一定比实际时间复杂度的总和要高)
所以摊还复杂度是一种您安排的时间复杂度,而摊还分析就是一门得到一个较紧的摊还复杂度的学问。
我们可以看之前的动态表扩张算法。
如果您每天赚3元,显然可以够花。
如果您每天赚4元,依然够花。
如果您第一天赚7元,后面隔一天赚7元,也是够花的。
这些都是合法的摊还复杂度。
但是如果您每天赚2元,那么您的钱会不够花,所以这是不合法的。
如果您第一天不赚钱,后面每天赚8元也是不合法的,因为您第一天没钱花了。
记账法大概就是猜一个摊还复杂度,然后去证的方法。

势能法

我们借助物理里面势能的概念往往可以简化记账法的问题。
势能法需要您定义一个合适的势能函数$\Phi(D)$,通过这个势能函数我们得到摊还复杂度。
在实际时间复杂度产生时往往会改变一些状态,导致势能变化,势能增加时,您需要的摊还复杂度相对于实际时间复杂度就增加对应的量,势能减少时,您的摊还复杂度就会相对减少。
$\Phi(D_i)$表示第i个时刻的势能,我们有一个式子:
$\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})$
其中$\hat{c_i}$表示摊还复杂度。
可以发现,只要保证$\Phi(D_i)\ge \Phi(D_0)$我们的分析就是成立的
对于之前的单调栈问题,我们定义势能函数为栈中元素个数。
假设我们压入一个元素时弹出了k个元素,那么摊还代价为:
$\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})$
$=1+k-k+1$
$=O(1)$
对于动态表扩张问题,我们只需要定义势能为两倍的元素个数-空间大小即可。
其它的一些问题可以在本博客中找到一些证明(比如LCT,启发式合并)

splay和并查集

放一下我的latex课件:

发表评论