平均案例分析与摊销分析

Question

现在我正在学习一般案例分析和摊销案例分析，我开始怀疑什么时候会使用平均案例分析，什么时候使用摊销案例分析。他们都完成了同样的任务吗？

Answer 1

平均案例分析不同于摊销分析。差别是很微妙的。

• 平均案例分析研究是从给定大小的所有问题实例集合中随机选择单个问题实例时的预期运行时，但这些问题实例的概率分布取决于这些问题实例的某些特定概率分布。

• 摊销分析研究是在以特定顺序解决多个问题的实例时所期望的聚合运行时。

考虑以下算法：

dict = {}

Foo(bar[1...n])
1. if dict[bar] exists, return dict[bar]
2. if n is even then
3.     dict[bar] = bar[1] if n > 0, or else 0 if n = 0
4. else if n is odd then
5.     dict[bar] = foo(bar[1...(n-1)/2]
6. return dict[bar]

平均案例分析:假设所有长度为n的列表都是相同的(假设数组中的值来自有限的集合，或者不同的数组可以被放入有限数量的等价类，而不是基于绝对的，而是基于相对的大小)。因此，当n为偶数时，n大小的输入的平均情况运行时为O(1)，当n为奇数时，O(log(n))为O(log(N))(在最坏的情况下，n=1，3，7，15，31，.，你必须减去1，然后再减半，直到你一直到1为止)。

摊还分析:假设您想在只包含数字1的数组上运行此算法，从0开始的长度，k为n=0的运行需要恒定的时间。运行n=1只执行一个递归步骤，因为我们缓存了n= 0的结果。继续进行，我们只执行了一个递归步骤，因为我们的执行序列已经缓存了递归调用的所有结果。因此，要执行k次，我们做O(k)工作；这意味着每一个单独的执行都有一个摊销复杂度O(1)。