【27：50】平摊分析开始

• 平均情况下时间复杂度通常需要借助统计概率分析(比较麻烦)[基本/传统的分析方法 ]

• Tarjan提出了平摊分析

• T(n) 是调用的次数，而不是输入的规模、 实际上将n等同于输入的规模

【52：45】开始先用传统分析法分析连续n个操作

• n个multipop为什么是O(n^2^)
  • 传统方法不考虑各操作的关联性，就是这么考虑的，平摊分析要考虑 也就是②

• 传统n次操作， T(n) = O(n * k) ,

【01：22：40】合计方法分析二进制计数器的例子

• 直观分析 T(n) <= 2n

【01：32：00】记账法

​

• n次操作总的费用。
• 不能出现透支

【01：42：30】用记账法分析栈操作

【01：54：00】用记账法分析二进制计数器

• 关键就是检查平摊核定是否正确 ，要>=0
• 怎么进行平摊核定，是拍脑袋想的，有可能不正确

【01：58：30】势能法

-