跳转至

Topic 1 | Amortized Analysis

约 1041 个字 预计阅读时间 5 分钟

说明

计划在一段时间内重写这一部分的内容,现在的内容是从原来的 Lec01 里直接迁移过来的。


摊还分析

不好意思

我实在不知道怎么清晰地讲明白“摊还”是什么,感觉讲不太清楚,所以就比较简单的介绍了,但是我仍然会指出我学习过程中认为对我启发性比较大的地方。

所谓的摊还分析,分析的是摊还边界,或者说摊还时间复杂度。平常我们分析时间复杂度时,针对的往往是某个具体的操作。而摊还分析的对象则是一个数据结构的一系列操作,而这一系列操作中有成本较低的,也有成本较高的,而且操作之间也可能有互相影响。

而摊还分析则是以一个更全局的角度来计算“平均”的操作代价,它计算的是从初始状态开始,连续的 M 次任意操作最多有 的代价。需要注意的是,它不同于平均时间分析(所有可能的操作出现概率平均,也就是直接求平均)和概率算法的概率分析(平均话所有可能的随机选择,也就是加权求平均)不同,摊还分析和概率完全无关。

容易得到如下等式:

\[ \text{worst-case bound} \geq \text{amortized bound} \geq \text{average-case bound} \]

我们知道,由于 amortized bound 限制了所有的 M 次操作,所以其上界就等于最差的情况发生 M 次(当然,很多情况下不一定能取到全都是最差情况);同样的,由于需要对任意组合都成立,所以一定不会小于统计学意义上的平均情况。

刚开始学到摊还分析的时候,看着这些内容有一种莫名其妙的感觉,不知道它在干嘛,后来我才发现我误解了摊还分析的目的。所以我感觉还是需要就此给出我自己的理解。

摊还分析

在我理解中,摊还分析实际上是一系列证明方法,更进一步的说,在我们之后会讲到的三个分析方法中,有一些可能难以直接得到摊还复杂度。但是实际上,他们的过程更像是已知一个摊还边界,并证明它确实是边界。

常见的摊还分析有三种:聚合(aggregate)法、核(accounting)法、势能(potential)法,接下来一一介绍。


聚合法

聚合法相对简单,就是直接累积连续 M 次操作的代价,再除以 M。

\[ T_{amortized} = \frac{\sum_i{T_i}}{n} \]

核法

link

关于 Accounting Analysis 可以参考这篇文章:https://www.baeldung.com/cs/amortized-analysis

做一个比喻的话,可以这么理解:

你去吃午饭,吃素菜要 ¥1(对标消耗较小的操作),吃荤菜要 ¥4(对标消耗较大的操作),现在你知道你每天吃午饭的摊还开销为 ¥2(从证明的角度来理解),并且我无脑的认为每个操作的摊还代价都是 ¥2(在核法中,整体的摊还开销和单个操作的摊还开销是不一样的,单个操作的摊还开销是可能互不一样的,M 个操作求和取平均以后才是整体的摊还代价)。那么你今天吃素菜,账户入账 ¥1(2 - 1 = 1);明天你也吃素菜,账户也入账 ¥1;后天你吃荤菜了,那么账户就出账 ¥2(2 - 4 = -2)……

核法大概就是按照这么一个思路来证明,不过具体细节和上面这个案例还是有区别的,可以详细参考上面那片文章,我觉得配图和说明都很详细。


势能法

link

关于 Potential Analysis 可以参考这篇文章:https://en.wikipedia.org/wiki/Potential_method 以及 ltgg 的这期周报讲的也很好:https://www.yuque.com/xianyuxuan/saltfish_shop/weekly002_amortized_analysis#KmnY6

势能法强推 ltgg 的这篇文章,讲的非常好。


最后更新: 2024年1月13日 19:00:24
创建日期: 2024年1月13日 19:00:24

评论