本文不太严谨的去论证了势函数与核算法是等价的。
另外，本文介绍了构造势函数的要点。
本文编写于 2019/1/21，20日掌握算法导论day12
- 【以下设计问题模型】
- 假设我们的实际代价函数在i=f(k)时(k=0,1,2,3…)，会突变产生巨大的代价
- ex:对于17.4动态表，i=f(k)=2^k-1
- 势函数设计核心：势函数的设计要求在每次f(k)来临之前，通过之前的操作积累足够的势，以使得φ＞＝（即将到来的巨大支出）
- 【总结分析】
- 我们看出来了，势函数的设计其实很简单很无脑。。
- （势能法→核算法）核算法实际上就是将势函数累计的势通过不均匀的方式分配给各种类型的操作。
- （核算法→势能法）从另一方面来看，如果我们将核算法不同操作的摊还代价赋予整个数据结构而非赋予在数据结构的某一部分，那么核算法就变成势能法了。
- 【hj势能与核等价定理】势能法是广义的核算法，势能法是核算法的摊还代价是一元函数（自变量操作类型)，而势能法的摊还代价是多元函数（自变量有操作类型、当前算法处于的位置等，联想一下在物理里不同高度的重力加速度不一样，因此势函数的分布是空间不均匀的。在计算机中也是如此，具体例子见P268）；因此，不严谨的说，势能法和核算法是等价的。
下面给出CLRS中势函数定义的几个例子，从这几个例子可以分析出势函数构造的几个要领
例1：
例2：
| 
转播
