【05：00】开始

• 平摊分析不涉及到 概率分析

• 3种方法中势函数是应用最广泛的

• 怎么验证势函数是否正确？对于二进制这个例子，证明如下

  

• 平摊分析

  第i次操作的平摊代价：

  

【32：50】8.5 动态表

扩张和收缩

• 什么时候扩张，扩张多少合适，要如何确定高效合理的扩展策略？
• 

【53：00】开始分析n次插入操作的平摊代价是多少？

传统方法：

【01：03：00】合计法分析

【01：10：00】休息

【01：21：00】记账法分析

巧妙收3元怎么得出来的，先1，后2，一步步试。

【01：34：10】势函数法

理想情况：

• 动态表的装载因子由一个常数的下界
• 表操作的平摊代价由一个常数的上界，就是O(1)

【01：56：00】自然管理策略不够好，开始改进

为什么不好？：扩张和收缩的点都在同一个地方，怎么办？拉开距离。

【-2 15：53】第i次操作是删除操作的情况下的平摊分析

【15次课-04：59】接着前面讲

【19：20】例

• 实际问题势函数是没有限制的。有些得到的是松上届。势函数不唯一

• 对势函数进行平摊分析

  • 没有引起扩招

  

  • 引起扩张