摊还分析理解笔记

摊还这个词儿，初看容易让人摸不着头脑。至少对我是如此。实际也没什么神秘的。摊还的英文是 amortize，牛津词典的解释是：

~ sth (business 商业) to pay back a debt by making small regular payments over a period of time 分期偿还，摊还（债款）

再看国语辞典对”摊还”的解释，

分期償還。例如：「這項貸款，可以分期攤還。」

说白了就是一次借用，不一定就要在这一次就全部偿还，我可以分期分多次偿还，只要我固定的分期可以没有压力地把贷款偿还就可以了。

而这个在算法中，可以把算法运行所需的时间看成是贷款。

关于摊还的解释，我认为维基百科中的解释是相当好的。我们这里为了简便，就只看一个动态数组的例子，如下。

考虑一个动态数组，其大小随着添加更多元素而增长，例如 Java 中的 ArrayList 或 C++ 中的 std::vector。如果我们从一个大小为 4 的动态数组开始，我们可以将 4 个元素推入其中，并且每个操作将花费常数时间。然而，将第五个元素推入该数组将花费更长的时间，因为该数组必须创建一个当前大小两倍(8)的新数组，将旧元素复制到新数组中，然后添加新元素。接下来的三个推送操作同样需要恒定的时间，然后后续的添加将需要再次缓慢地将数组大小加倍。

一般来说，如果我们考虑将任意数量的 n + 1 推送到大小为 n 的数组，我们会注意到推送操作需要恒定的时间，除了最后一次需要 $\Theta(n)$ 时间来执行大小加倍操作。由于总共有 n + 1 次操作，我们可以取其平均值，并发现将元素推送到动态数组需要：$\frac{n\Theta(1) + \Theta(n)}{n + 1} = \Theta(1)$，恒定时间。

从上面的分析来看，如果我们从最坏时间复杂度来看，这个时间界是相当坏的，而使用摊还分析来看，则可以发现动态数组的操作所付出的时间代码其实并没有那么夸张。

关于摊还分析的解释，我觉得 Weiss 的数据结构与算法分析这本书的相应章节的开头部分的概念解释和开头的一个例子算是比较形象，如下，