二进制计数器增量的平均个案时间复杂度分析
二进制计数器增量的平均个案时间复杂度分析
提问于 2016-11-13 05:24:08
我试图找到二进制计数器的平均案例时间复杂度，而不是摊销分析。由于我对我的时间复杂性分析技巧并不完全有信心，我想确认我对下面提供的伪码的平均案例分析是正确的。
设k为数组的长度。
Increment(Array)
i = 0
while i < k and Array[i] == 1
Array[i] = o
i = i + 1
if i < k
Array[i] = 1为了找到平均花费的时间，我找到了每次运行时翻转的平均位数。因此，我发现这是O(2+ k /(2^k))，对于一个大k等于O(1)。
这是正确的平均运行时间吗？如果没有，我会如何处理这个问题呢？
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-11-13 10:39:54
我假设每个输入都有相同的发生概率。
这意味着每一个位都是独立开或关的，概率为1/2。
几何分布是复杂性的相关分布:你抛硬币，结束第一个尾巴结果的实验(没有更多的东西可携带)。
这里的几何分布的平均值正好是2(见上面的链接，或者从基本原理推导出来)，所以平均复杂度确实是O(1)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40570866
复制相关文章
相似问题
腾讯云开发者
