时间戳

首页 > 解决方案 > 平均案例分析与摊销分析

time-complexity - 平均案例分析与摊销分析

问题描述

现在我正在学习平均案例分析和摊销案例分析，我开始想知道你什么时候会使用平均案例分析以及什么时候使用摊销案例分析。他们也完成同样的事情吗？

标签： time-complexityruntimecomplexity-theory

解决方案

平均情况分析不同于摊销分析。差异是微妙的。

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

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

考虑以下算法：

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))（在最坏的情况下，n=1、3、7、15、31 , ...，你必须减去和减半，直到你一直下降到 1)。

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

推荐阅读