ADS_analysis1_Amortised Analysis
Amortized Analysis（挪还分析）
| Edited by 颍川散人 | Data: 2022.2.26 |
|---|
Worst-case bound
Amortized bound
Average-case bound
worst-case bound is stronger than amortised bound,如果worst case bound是O(logN),那么amortised bound一定是O(logN),正如AVL tree一定是splay tree.但反过来就不成立了，splay tree不一定是AVL tree.
amortised bound is strong than average bound,在很多情况下无法准确定义平均，为了做平均分析通常需要一些概率方面的假设
amortised bound没有任何概率方面的假设，不管概率是多少，amortised bound是真实情况下均值的一个上界
three methods to do amortised analysis
Aggregate analysis（总量分析）
aggregate mains a total sum of something
对于所有的n，n个操作（无论操作是什么）所花费的worst case的时间总和是T(n)，所以每个操作的挪还时间就是T(n)/n
拿入栈和多次出栈举例子，单看一次multiPOP可以把n个元素全部POP出来，花费的时间是O(N)，但是我们不能连续执行N次multiPOP,因为栈里得有东西才能POP出来，不可能每次调用multiPOP都花费O(N)的时间。事实上，任意一个被我们push进去的元素最多只能被POP出来一次，如果我们想POP什么东西出来，它得先push进去。为了multiPOP出n个元素，我们需要先push进去n个元素，所以对于这n个元素，我们至多执行2n步，花费总时间是 O(N),对于每个操作的amortised cost就是O(n)/n=1
总量分析适合那种容易计算总和的简单情况，但是实际上计算总和并不容易
accounting method（会计法）
当actual cost少于amortised cost时，可以把少用的那一部分存起来，当作credit，当下次actual cost多于amortised cost时，可以用credit补充差值那一部分，从而整体上是符合amortised cost的
同样的，在multiPOP stack的例子中，我们假设push的amortised cost是2，POP和multiPOP都是0，每执行一个push操作，我们都能省下1当作credit，执行了n个push后，就有了n个credit。这些credit刚好能把push进stack的n个元素都pop出来
The key part of accounting method is to guarantee that our account will never go negative
it always satisfies
在势能法当中，把credit定义为势能函数两个值的差
Sum up both sides, we can get
所以我们不用猜一个好的credit了，但是得猜测当前问题结构中一个好的势能函数
一般来说，一个好的势能函数总是在序列开始的时候取最小值
还是在multiPOP stack的例子
我们把势能函数定义为执行i个操作后当前堆栈的元素个数
for PUSH:
