数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中计数器增量的摊还分析
摊还分析用于确定一系列操作的运行时间，即序列所需的平均时间。它不能被视为对算法进行的平均情况分析，因为它并不总是采用平均情况。有些情况会作为分析的最坏情况出现。因此，摊还分析可以被视为对序列中多个操作的最坏情况分析。这里，每个操作的成本是不同的，对于某些操作，成本很高。这个问题是使用二进制计数器的一般视图。
让我们看看在 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/k2 k 为翻转次数。
这是一个分母为调和级数的等比级数。
翻转总和
总和 = n + n/2 + n/4 + ….. + n/k2 < n/(1-1/2) = 2n
现在，操作的摊还成本为 O(n) / 2n = O(1)
阶为 O(1)，它与数字中位的数量 n 不成比例。
更新于: 2019-10-24
477 次查看
广告