引言
一个哈希表多大合适?
数据量为(n),如果哈希表无限大(>=(n)),那么时间复杂度是(O(1))的,不过很显然,虽然节省了时间,但是浪费了空间.
实际上在我们不知道数据量的情况下,我们无法确定哈希表的大小,这时我们有个很美丽的数据结构->动态表
动态表的工作原理
- 建立一个表,初始化大小为1.
- 如果表的容量不够,那么就把大小扩大为原来的两倍,将原来表的内容复制一遍
- 把原来表的内存释放,再执行插入
- 容量会以1,2,4,8,16……(2的幂次)的增长
接下来我们来分析一下插入操作的复杂度:
- 当表里存在(n)个元素,最坏复杂度是(O(n))
- 那(n)个元素插入的最坏复杂度是(O(n^2))
这个复杂度分析肯定是错的,理由是并不是每一项都是最坏的(O(n))的复杂度
这时就要用到平摊分析了,我们先从最简单的聚集分析说起.
聚集分析
容易发现,(n)个元素的插入必然需要一个(n),但是只有当2的幂次的时候才会复制一遍
复杂度应该是:
]
右边这个最后也不会超过(2n)
证明
[sum_{j=0}^{lfloor log_2(n-1)floor} 2^j<=2n
]
最后总复杂度为(3n),就是(O(n)),平均下来每个操作就是(O(1)).
用平摊分析来分析一个操作序列,证明每个操作的平均代价很小,尽管有个别操作可能代价很大.值得注意的是这个平均并没有用到概率论.它是最坏情况下的平均操作.就像上面这个例子,平均下来每步操作是常数级别的.(frac{O(n)}{n})
综上所述:
- 平摊分析可以用来证明在一系列操作中,通过对所有操作求平均之后,即使其中单一的操作具有较大的代价,平均代价还是很小的
- 平摊分析与平均情况分析的不同之处在于它不牵涉到概率
- 平摊分析保证在最坏情况下,每个操作具有平均性能。
上文采用的方法是聚集分析,在聚集分析中,如证明对所有的n,由n个操作所构成的序列的总时间在最坏情况下为(O(n))。因此,在最坏情况下,每个操作的平均代价(或称平摊分析)为(frac{O(n)}{n})。请注意这个平摊代价对每个操作都是成立的,即使当序列中存在几种类型的操作时也是一样的
换句话说,就是对(n)条操作整体考虑其复杂度,而不是单独考虑一条指令的最坏复杂度,然后再平摊.
但是,并不是所有情况都能像上文一样轻易地求出平摊复杂度,要采用更精确的方法.
记账方法
算法导论上称为核算法
设想自己是一个财务会计,而你要做的就是给第(i)个操作“付钱”,设一个虚构的平摊代价,称之为(check C_i),而每个操作的实际代价为(C_i) .
设每一步运算要花费1元.例如执行一次普通的插入操作要花费1元,由空间为2的表扩大为空间为4的表再复制需要2元.
如果还有剩余的钱,那就把钱存起来,用于支付以后的操作.
如果$ check C_i$不足以支付给这些操作,那就从银行里取出钱来付款.
存款余额要求不能是负数,当然所有的平摊代价减去操作代价的余额必须是非负数.
也就是相当于
]
以动态表为例:
-
初始设置(check C_i=3),其中1元用于插入,2元用于将表翻倍的预存费用.
-
当表扩大两倍,就从存款里取出1美元来移动新项,还有1美元来移动旧项.
-
当长度为8的时候:
里面的数字就是余额,前四个余额为0,这时开始执行插入操作
花费1元用于插入,余额为2元,插入四个之后:
- 这时动态表需要扩大两倍,扩大两倍需要多少钱?没错,非常完美地,余额为8刚好可以支付复制操作,然后新插入的第九项也是花费1元进行插入,余额为2元.
通过这个计算,我只需要每个操作预设(F_i=3),就可以足够支付了.
这样就可以得到总复杂度是 (3n)
当然进行平摊分析并不只有一个可行方案,若将平摊代价设置为4也是可以的,但是设置为2就不行了.
对记账方法进行总结:
在平摊分析的记帐方法中,决定每一个操作的均摊成本,对不同的操作赋予不同的费用,某些操作的费用比它们的实际代价或多或少。我们对一个操作的收费的数量称为平摊代价(check C_i)。当一个操作的平摊代价超过了它的实际代价$ C_i $时,两者的差值就被当作存款,并赋予数据结构中的一些特定对象,可以用来补偿那些平摊代价低于其实际代价的操作。这种方法与聚集分析不同的是,对后者,所有操作都具有相同的平摊代价,对前者,操作的平摊代价被分解为实际代价和余额。数据结构中存储的总存款等于总的平摊代价和总的实际代价之差。注意:总存款不能是负的。在开始阶段的存款,是为了在后面的操作序列中再支付。
势能法
好的势能方法,就像初恋一样无法忘怀.
我们由数据结构(D_0)开始讲起
-
操作(i)将(D_{i-1})转化为(D_i),操作(i)的操作代价还是$ C_i $
-
定义势能函数(phi),将数据结构映射为实数
-
这样初始的势能是(phi (D_0)=0) ,对于所有(i)都有$phi (D_0) geq 0 $
-
平摊代价(check C_i=C_i+phi(D_i)-phi(D_{i-1}))
-
(Delta phi_i=phi(D_i)-phi(D_{i-1}))是势能的改变量
势能法与记账法不同的是后者考虑的是平摊代价,前者考虑的是银行存款,也就是势能函数.
其中:
- 如果(Delta phi_i geq 0) ,第(i)次操作存储了后面数据结构所需的代价
- 如果(Delta phi _i leq0), 第(i)次操作消耗了之前数据结果存储的代价
平摊代价正确性证明:
]
]
]
动态表的势能法分析:
-
定义势能函数(phi(D_i)=2i-2^{lceil logi ceil})
-
可得(phi(D_0)=2^{log0}=0)
-
因为(lceil lgi ceil)向上取整,所以最大取到$ lgi +1$,所以(2^{lceil lgi ceil})最大取到(2i),(phi(D_i)ge0)
-
由$ check C_i=C_i+phi(D_i)-phi(D_{i-1})$
-
实际代价(C_i)由上文可知分两种情况,一般情况下是(1),而当(i-1)为(2)的幂时为(i)
[phi(D_i)-phi(D_{i-1})=(2i-2^{lceil lgi ceil})-(2(i-1)-2^{lceil lg(i-1)ceil})
][=2-2^{lceil lgi ceil}+2^{lceil lg(i-1) ceil}
] -
分情况分析:当(i-1)为(2)的幂次时:
[check C_i=i+2-2^{lceil lgi ceil}+2^{lceil lg(i-1) ceil}
][= i+2-2(i-1)+i-1
=3
] -
其他情况:
[check C_i=1+2-2^{lceil lgi ceil}+2^{lceil lg(i-1) ceil}
][=1+2=3
]
总结
- 平摊分析为数据结构的性能提供了一个简洁的抽象概念。
- 在不关注实时表现,只关注聚集行为时,平摊分析是一种很好的描述方式。
- 在有些情况中,不同的操作会有不同的平摊代价,它们的和仍然是实际代价的上限。
- 三种方法都是可用的,但都有各自的适用情况使得它们是简单准确的,不同的方法可能得到不同的上限结果。