2

这不是作业，我正在研究摊销分析。有些事情让我感到困惑。我无法完全理解摊销和平均复杂性之间的含义。不确定这是否正确。这是一个问题：

--

我们知道程序的运行时复杂度取决于程序输入的组合——假设程序运行时复杂度为 O(n) 的概率为 p，其中 p << 1，而在其他情况下（即对于 (1 -p) 可能的情况），运行时复杂度为 O(logn)。如果我们使用 K 个不同的输入组合运行程序，其中 K 是一个非常大的数字，我们可以说这个程序的摊销和平均运行时复杂度为：

--

第一个问题是：我在这里读过这个问题：Difference between average case and amortized analysis

所以，我认为平均运行时复杂度没有答案。因为我们不知道平均输入是多少。但它似乎是 p*O(n)+(1-p)*O(logn)。哪个是正确的，为什么？

二是摊销部分。我已经阅读了恒定摊销时间，我们已经知道摊销分析与平均情况分析的不同之处在于不涉及概率；摊销分析保证了在最坏情况下每个操作的平均性能。

我可以说摊销运行时间是 O(n)。但答案是 O(p n)。我对为什么涉及概率有点困惑。虽然 O(n)=O(p n)，但我真的不知道为什么 p 会出现在那里？我改变思维方式。假设我们确实损失了时间，那么 K 变得非常大，因此摊销运行时间为 (K p O(n)+K*(1-p) O(logn))/k = O(p n)。这似乎与平均情况下的想法相同。

给我添麻烦了，麻烦帮帮我，先谢谢了！

4

1 回答 1

7

对于“平均”或“预期”复杂性，您正在对问题的概率分布做出假设。如果你不走运，（或者如果你的问题生成器恶意地不符合你的假设 8^），你的所有操作将非常昂贵，并且你的程序可能需要比你预期的更多的时间。

摊销复杂性是对任何操作序列的总成本的保证。这意味着，无论您的问题生成器有多恶意，您都不必担心一系列操作花费的时间比您预期的要长得多。

（根据算法的不同，不难发现最坏的情况。经典的例子是天真的快速排序，它在大多数排序的输入上表现非常糟糕，即使“平均”情况很快）

于 2014-01-29T02:16:03.723 回答