hello everyone！ 云狗今天教的更多的是一种思想，而不是比较实用的数据结构或者某种算法，可以跳过，因为这些东西太细了，细的有点不会在八股中出现，但是对于我们对于代码的理解的提升我觉得是值得的

依旧叠甲：

摊还分析（amortized analysis）定义：

我们在求数据结构的一个操作序列中所执行的所有操作的平均时间，来评价操作的代价

——《算法导论》

显然地，这是一种过程，根据一个算法平均的操作时间，来评价算法的“性价比”的一种过程
到这里你可能会有个疑问：
这东西不就是时间复杂性的平均情况吗？

事实上，我们用摊还分析的时候，并不涉及概率，所以相对来讲，这样的分析并不适合评价数据在随机算法中的表现，这样的分析其实是在最差的情况下能保证的平均性能，这样也给我们程序员的另一个“保证”

一般的分析方法：

聚合分析

通过计算操作序列的总时间复杂度，得出每个操作的平均代价，从而避免单个操作高代价对整体性能的影响。即：

          

核算法

通过分析每个操作的摊还代价来评估操作的平均代价。摊还分析的目的是通过求数据结构的一系列操作的平均时间，来评价操作的代价，即使某个单一操作的代价很高，也可以证明平均代价很低。即：

对任意n个序列要求：

总摊还代价：

势能法

它通过引入势能函数，将操作的实际代价分摊到多个操作中，从而简化复杂度分析。

如图所示：图片来源： 千葉原 的帖子，（主要我不太擅长输入函数……偷个懒）

总结

摊还分析其目的就是为了更好的去评估算法的性能，这个过程是一个数学味道特别重的分析，我们在初期不要求用这样的东西来分析自己的代码，但是摊还分析给我提供了一种很好的视角去理解算法的复杂度的意义，以及在设计代码时，我们也会在脑海中知道哪一种方案是更加高效和稳定的

（本文主要作为科普，若有没看懂的地方，无妨，主要是一种分析代码性能的思想，毕竟我们评价一个算法不能只看最差情况下时间复杂度、空间复杂度）