Topic 1 | Amortized Analysis¶
约 1041 个字 预计阅读时间 5 分钟
说明
计划在一段时间内重写这一部分的内容，现在的内容是从原来的 Lec01 里直接迁移过来的。
摊还分析¶
link
Wikipedia: https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%91%8A%E5%88%86%E6%9E%90
不好意思
我实在不知道怎么清晰地讲明白“摊还”是什么，感觉讲不太清楚，所以就比较简单的介绍了，但是我仍然会指出我学习过程中认为对我启发性比较大的地方。
所谓的摊还分析，分析的是摊还边界，或者说摊还时间复杂度。平常我们分析时间复杂度时，针对的往往是某个具体的操作。而摊还分析的对象则是一个数据结构的一系列操作，而这一系列操作中有成本较低的，也有成本较高的，而且操作之间也可能有互相影响。
而摊还分析则是以一个更全局的角度来计算“平均”的操作代价，它计算的是从初始状态开始，连续的 M 次任意操作最多有 的代价。需要注意的是，它不同于平均时间分析（所有可能的操作出现概率平均，也就是直接求平均）和概率算法的概率分析（平均话所有可能的随机选择，也就是加权求平均）不同，摊还分析和概率完全无关。
容易得到如下等式：
我们知道，由于 amortized bound 限制了所有的 M 次操作，所以其上界就等于最差的情况发生 M 次（当然，很多情况下不一定能取到全都是最差情况）；同样的，由于需要对任意组合都成立，所以一定不会小于统计学意义上的平均情况。
刚开始学到摊还分析的时候，看着这些内容有一种莫名其妙的感觉，不知道它在干嘛，后来我才发现我误解了摊还分析的目的。所以我感觉还是需要就此给出我自己的理解。
摊还分析
在我理解中，摊还分析实际上是一系列证明方法，更进一步的说，在我们之后会讲到的三个分析方法中，有一些可能难以直接得到摊还复杂度。但是实际上，他们的过程更像是已知一个摊还边界，并证明它确实是边界。
常见的摊还分析有三种：聚合(aggregate)法、核(accounting)法、势能(potential)法，接下来一一介绍。
聚合法¶
聚合法相对简单，就是直接累积连续 M 次操作的代价，再除以 M。
核法¶
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 的这篇文章，讲的非常好。