C ++中计数器增量的摊销分析
一系列操作的摊销分析用于确定运行时间,即该序列所需的平均时间。In不能视为对算法进行的平均情况分析,因为它并不总是采用平均情况。有些情况是最坏情况下的分析情况。因此,摊销分析可以视为序列中多个操作的最坏情况分析。在这里,以不同方式进行每个操作的成本很高。此问题是使用二进制计数器的一般视图。
让我们看一下c++编程语言的工作和实现,以便我们可以清楚地了解这些概念。
使用长度为k的二进制数组实现k位二进制计数器,该数组的初始值为0。对该值进行多次递增操作。这是二进制8位数组在对其执行的增量操作时的行为。
最初,00000000>00000001>00000010>00000011>00000100>00000101>....>11111111。
此逻辑是检查从数字的最后一位开始是否出现第一个0,并将其翻转为1,然后将其后的所有位依次翻转为0。
示例
#include <iostream> using namespace std; int main(){ int number[] = {1,0,0,1,0,1,1,1}; int length = 8; int i = length - 1; while (number[i] == 1) { number[i] = 0; i--; } if (i >= 0) str[i] = 1; for(int i = 0 ; i<length ; i++) cout<<number[i]<<" "; }
输出结果
1 0 0 1 0 0 0 0
在这个问题中,每个操作的成本是恒定的,并且与位数无关,
在这里,序列成本的渐近分析为O(n)。
在n次操作中完成的翻转总数为-n+n/2+n/4+…..+n/k2k翻转次数。
这是分母为HP的GP。
翻转总和
和=n+n/2+n/4+…..+n/k2<n/(1-1/2)=2n
现在,芳构化的运营成本为O(n)/2n=O(1)
顺序为O(1),它与数字中的位数不成正比。