摊销分析用于增加基于斐波那契的整数的复杂度分析

Question

摊销分析用于增加基于斐波那契的整数的复杂度分析

algorithmfibonacciamortized-analysis

3

假设整数是由斐波那契数之和表示，而不是由二的幂表示，因此100101表示F(6)+F(3)+F(1)=8+2+1=11（我们假设F(1)=F(2)=1）。我想在O（1）摊销时间内增加一个整数。

我有一个增量算法：直觉是不应该有两个连续的1位。因此，我会先将最低有效位0位设置为1，然后从最高位开始，如果数字有两个连续的1位，比如第i位和第i-1位，则将它们都设置为0，并将i+1位设置为1。递归地重复此操作，直到没有两个连续的1位。

我使用会计方法进行分摊分析。因此，对于每个增量操作，我会授予k美元，每个位翻转将花费1美元。但是，我很难确定和证明正确的k值。根据经验，k=3可能有效，但我不知道该如何证明。

- jtsai

你是否允许使用给定数字的任何可能表示形式？例如，11也可以表示为101000（8 + 3）。（这将是Zeckendorf表示法。） - Mark Dickinson

@MarkDickinson 我假设使用这个算法从0开始递增，因此每个数字应该仅有一个唯一的表示。 - jtsai

@jbapple 这是 Jeff Erickson 很久以前布置的一道作业题目... - jtsai

请您考虑接受一个答案，或者留下评论吗？ - trincot

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jbapple · Answer 1

使用潜力方法，让表示的潜力成为其中1位的数量。然后递增最低位数将使潜力增加1，因此仍然是摊销常数时间，并且每个进位都是摊销免费的，因为将两个1位转换为一个1位会释放一单位的潜在能量。

- btilly · Answer 2

以下是如何进行的概要。

首先，证明每个整数 n 都有一个在斐波那契数列中的唯一表示，其中没有连续的 1 位。 (更正，最低位为 0。我将称之为位 0。) 因此，您将从 1 开始，应用您的算法，并以 1 结束。

其次，证明如果在操作期间翻转了第 i 位，则您得出的表示将在位 1、2、3、...、i-1 中全部为 0。 (更正说明，我忽略了位 0。)

接下来，如果在翻转之前第 i 位是 0，则将翻转成本归因于它本身。如果在翻转之前第 i 位是 1，则将翻转成本归因于 2，因为您必须翻转它和它之前的那个位。(除了特殊情况，即位 1。)

如果第i位是0，那么在它之前有一个序列...010101后你才会再次翻转。你从...000开始，下一个数字是Fib(i)，所以在这些位翻转之间的长度就是Fib(i)。由此，你可以对将第i位从0翻转为1的成本设定一个上限。（这个上限总是0。）

如果第i位是1，那么在它之前有一个序列...101010，你不会再次翻转。你从...000开始，下一个数字是Fib(i-1)，所以在这些位翻转之间的时间长度就是这个数字。通过这个，你可以对将第i位从1翻转到0的成本设定一个上限。（这个上限总是1）。由于Fib(i-1)比Fib(i)小，并且我们将2个位翻转归功于此操作，因此这个上限将大于先前的上限。

将两个上限相加，你将得出翻转第i位的成本的平均上限。这个上限将呈指数衰减。

将所有可能的位的上限相加，你将得到每个操作的位翻转的平均摊销成本的上限。这将是一个有限的数字。 :-)

- trincot · Answer 3

以下是一些命题和观察结果，它们导致结论k=3：

该算法的应用包括单次增量（从0到1）和零个或多个三元组翻转（011到100）。
在运行算法后，保证比特模式中没有更多的11模式。
增量应用于最右边的位或其左侧的一位，因为当算法开始时它们不是1。
增量后，可能在最右侧位置或其左侧一位出现11模式。它可能是双倍的（111），但然后算法将选择左边的一个。
翻转总是执行此子模式转换：011 -> 100，因此每次三元组翻转都会减少1个1位的数量。此外，在三重翻转后，剩余的1位只有0位右侧，除了最右边的位可能是1（在增量阶段结果为...111的情况下）。
在三元组翻转之后，新的11模式可能出现的唯一位置是前一次出现的两个位位置左侧的两个位。因此可能会出现向左方向的三元组翻转级联。该过程是有限的，因为每次三元组翻转都会减少1个1位的数量。
该算法是正确的，因为增量发生在表示值1的位上（由最右边的两个位表示的斐波那契数均为1），因此表示值增加1。由于斐波那契性质，三元组翻转不会改变表示值。
除了最右边的2位之外，所有其他位只能通过在某个时刻成为三元组翻转的最左边的位而变为1位。
生成的表示 F_i+1，其中 F_i 是大于2的第 i 个斐波那契数，总是恰好有两个1位，包括最右边的位。这是因为与值F_i相对应的位在所有其他位都为0时设置，除了最右边的位可能不是1。如果最右边的位不是1，则它将在下一次应用算法时变为1。因此保证会产生模式10...01，其值为F_i+1。
从0到F_i+1所执行的增量数量显然为F_i+1。从0到F_i+1所用的三元组翻转次数为F_i-1。这是因为增量将模式中的1位数增加1，而三元组翻转将此数字减少1。由于F_i+1比0的表示多2个1位，所以三元组翻转的数量比增量小2。

结论

为了增加 i，达到 F_i+1 所需的增量和三元翻转次数之比趋近于 1，因为差值为 2 变得微不足道。这意味着问题中的 k 趋近于 3（三元翻转包括 3 次翻转）。

演示

请参见 this JS Fiddle，该演示重复应用算法，显示位表示、增量和三元翻转的总数以及它们的比率。请看比率如何（非常）缓慢地趋近于 1。

上述 fiddle 中算法的实现如下：

// Apply the algorithm once
var mask; 
this.bits |= 1 << (this.bits & 1);
this.increments++;
mask = (this.bits & 6) === 6 ? 4 
     : (this.bits & 3) === 3 ? 2 : 0;
while (this.bits & mask) {
    this.bits ^= mask * 3.5; // 3 flips
    mask <<= 2;
    this.flips++;
}