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 / k 2 k翻转次数。
这是分母为HP的GP。
翻转总和
和= n + n / 2 + n / 4 +….. + n / k 2 <n /（1-1 / 2）= 2n
现在，芳构化的运营成本为O(n)/ 2n = O(1)
顺序为O(1)，它与数字中的位数不成正比。
以上是 C ++中计数器增量的摊销分析 的全部内容， 来源链接： utcz.com/z/316402.html
