1

在我的算法课上，我们讨论了摊销复杂度。不幸的是，由于参加体育比赛，我无法参加。在尝试联系教授解释这一点失败后，我被困在这里问了。什么是摊销复杂度，我如何找到它？我被分配了要做的工作，但不知道该怎么做。如果你们可以帮助我解决一个非常有帮助的问题或提供其他解释的参考。

这是问题所在：

假设没有溢出，考虑以下算法并将二进制数加 1，表示为 n 位数组：

increment is
    local
        i: INTEGER;
    do
        from i:=n until a.item(i) = 0 loop
            a.put(0,i);
            i:=i - 1
        end;
        a.put(1,i)
    end

这个算法在最坏的情况下显然是 O(n)。证明它的摊销复杂度是 O(1)。

我可以看到为什么最坏的情况是 O(n)，但我不知道为什么它的摊销复杂度是 O(1)。甚至就此而言，摊销复杂性是多少。

4

1 回答 1

1

考虑数字中的实际位如何影响算法将花费多少时间。

时间将在很大程度上取决于数字中最后一个零的位置。因此，'01010111' 将比 '01010110' 花费更多的时间来处理，即使它们都具有相同的位数。发生这种情况是因为循环中的停止条件在线性时间中寻找最右边的零。

直觉

现在，考虑一系列操作，在每次调用时，您将数字末尾的每个非零位都设为零。所以下次执行肯定不会进入循环（因为会以0结束）。

摊销复杂度在预期的一系列操作中寻找平均复杂度。在这种情况下，让我们证明从某个任意数字开始，increment重复调用将具有平均 O(1) 复杂度。

证据

让我们调用loop(n)内部循环increment执行的次数。微不足道loop(n)是复杂性的主要因素increment。

从那开始，我们开始争论loop(n) = 0当且仅当n是偶数。之所以如此，是因为如果n%2 = 0，则数字中最右边的位是 0。这至少每 2 次对 的后续调用发生一次increment。

我们可以遵循这个论点，看看loop(n) = 1当且仅当n%4 = 1。之所以如此，是因为如果n%4 = 1，那么最后 2 位n是01。这种情况至少每 4 次后续调用increment.

使用相同的逻辑，loop(n) = 2当且仅当n%8 = 3。之所以如此，是因为如果n%8 = 3，那么最后 3 位n是011。这种情况至少每 8 次调用increment.

我们可以概括并说loop(n) = x当且仅当n % 2^(x+1) = 2^x-1。之所以如此，是因为如果该条件为真，则 的最后x+1一位n是011...11。这至少发生一次，每次2^(x+1)调用increment.

loop(n)为了找到后续调用后的平均值increment，我们必须根据发生的机会对可能的成本进行加权。

average(loop(n)) = 1/2 + 1/4 + 1/8 + ... = 1

之所以如此，是因为在每 2 次呼叫中，将有 1 个loop(n) = 0，在每 4 个呼叫中，将有 1 个loop(n) = 1，依此类推......

于 2015-04-08T02:27:17.437 回答