算法导论摊还分析笔记

摊还分析在分析什么？
分析一种数据结构上所有操作的平均性能，之前的性能分析，例如红黑树，我们分析的是每种单独的操作性能如何，如红黑树的查找、插入和删除分别性能如何。摊还分析则是分析查找、插入和删除操作的平均性能。
其现实意义是摊还分析的结果更能表现出一种数据结构在实际使用中的性能。

聚合分析

聚合分析的方法是，分析一种数据结构上 n 个操作（任意操作）的最坏时间消耗 T(n)，然后摊还代价即为 T(n)/n

举了两个例子，扩展的栈操作、二进制计数器递增，用聚合分析的方法得出的结果更为紧确。

核算法

核算法是对不同的操作赋予不同的摊还代价，这个代价可能与其实际操作代价不同，但是通过整体的调整，会使得对一系列操作的整体摊还代价的分析变得简单。

例如，将入栈操作赋予 2 的摊还代价，那么其实际代价是 1，每个入栈存储了 1 的信用，当该元素出栈时即可用其关联的信用覆盖实际代价，所以各种出栈（POP，MULTIPOP）操作的摊还代价都可以设置为 0，方便分析。

势能法

势能法选择一个合适的势能函数，势能函数的值即是当前的总信用（类比核算法）。

个人认为势能法的好处是，通过公式 17.2 可以更有条理的定义各个操作的摊还代价。算法的难度集中在了如何选择一个合适的势能函数。

动态表

动态表是一个被填满或删减后，会扩张或收缩空间的数据结构。

简单的说动态表只有插入和删除两个操作，但每次插入操作的性能可能会差距很大，原因是在扩张临界的插入会引发表的复制（收缩临界的删除操作同理）

那么问题来了，在动态表的一系列插入删除操作中，操作的平均性能如何？

摊还分析的意义在于可以证明动态表的 n 个操作实际运行时间为 O(n)，即平均运行时间为 O(1)

书中用 3 中方法分析了只有插入操作的动态表的性能，用势能法分析了同时有插入和删除操作的动态表的性能

PS：iOS 中的可变数组就是一个典型的动态表，不过有文章分析它只实现了表的扩张，不进行收缩，完全符合上述第一部分的分析