algorithm - 摊销的复杂性

Question

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

问题是:

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，等等……