本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- 均摊分析
题目
1.4.32 均摊分析。请证明，对一个基于大小可变的数组实现的空栈的 M 次操作访问数组的次数和 M 成正比。
1.4.32 Amortized analysis. Prove that, starting from an empty stack, the number of ar- ray accesses used by any sequence of M operations in the resizing array implementation of Stack is proportional to M.
分析
均摊分析在本书中只是稍微描述了一下：
均摊分析wiki：https://en.wikipedia.org/wiki/Amortized_analysis
后来百度了一下，了解到貌似《算法导论》对均摊分析有详细的论述，这里引用一点:
均摊分析又被称为摊还分析。是用来评价程序中的一个操作序列的平均代价，有时可能某个操作的代价特别高，但总体上来看也并非那么糟糕，可以形象的理解为把高代价的操作“分摊”到其他操作上去了，要求的就是均匀分摊后的平均代价。
摊还分析有三种常用的技术；聚合分析，核算法，势能法。
聚合分析
核算法
势能法
答案
当栈Push的时候，如果小于数组大小N，那操作M次，需要访问数组M次；当大于数组N了，需要操作数组2M次。综上，和M成正比。
