摊销的复杂性

Question

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

这是问题所在：

Consider the following algorithm and adding 1 to a binary number, represented as an array of n bits, assuming that there is no overflow:

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

This algorithm is clearly O(n) in the worst case. Show that its amortized complexity is O(1).

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

Answer 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，那么 n 的最后 2 位是 01。这种情况至少每 4 次后续调用 increment.

发生一次

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

发生一次

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

至少发生一次

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

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

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

摊销的复杂性

Amortized Complexity

algorithm

big-o

eiffel

time-complexity

amortized-analysis

直觉

证明