本文主要是介绍关于算法导论Amortized Analysis摊还分析的个人理解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://blog.csdn.net/u012907049/article/details/108354398?utm_source=app&app_version=4.5.8
详细的可以看下这个博主的，有公式

摊还分析

整体上，摊还就是，不是我们之前练习去求的（最坏）复杂度，而是一个平均情况的复杂度，因为每次运行都不会总是最坏的
它分为三种方法去计算，聚合分析Aggregate Analysis，核算法Accounting Method，势能法Potential Method
由于考试考了后两种，就用人话来介绍后两种

• 核算法Accounting Method
  核算法就是，不是按照常规思路来给一对常用操作中每个都分配操作产生的代价，而是只需要将这些代价都记在一个操作上，也就是说把这旗下的所有操作的代价都算在一个操作的头上。计算复杂度的时候就用这个操作的次数和代价相乘来算就可以了

• 势能法Potential Method
  势能法的这个势能正如物理中的那个势能，就是：
  本次操作摊还代价=真实代价+当前操作势能-上一次操作势能
  总摊还代价就等于每次操作摊还代价相加，就像等差数列求和一样有前后抵消的部分，故最终式子为：
  总摊还=真实代价+最后一个操作势能-第一个操作势能
  那么每个操作势能又是依照什么来定义的呢？
  这个势能的多少取决于这个adt（抽象数据结构）中的元素个数，也就是按元素或对象个数来表示

这篇关于关于算法导论Amortized Analysis摊还分析的个人理解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！