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)，它与数字中的位数不成正比。