二元计数器增量的平均案例时间复杂度分析 [英] Average Case Time Complexity Analysis of Binary Counter Increment

问题描述

我试图找到二进制计数器的平均案例时间复杂度，而不是摊销分析.由于我对时间复杂度分析技巧并不完全自信，因此我想确认我对下面提供的伪代码的平均情况分析是正确的.

I am attempting to find the average case time complexity, not amortized analysis, of a binary counter. As I am not entirely confident in my time complexity analyzing skills, I would like to confirm that my average case analysis of the pseudocode provided below is correct.

让 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 .

In order to find the average time taken, I find the average amount of bits flipped per run. As a result, I found this to be O(2+k/(2^k)), which equals O(1) for a large k.

这是正确的平均案件运行时间吗?如果没有，我将如何开始解决这个问题?

Is this the correct average case running time? If not, how would I begin to approach this problem?

推荐答案

我假设每个输入都具有相同的发生概率

I am assuming each input has the same probability to occur

这意味着每个位以1/2的概率独立打开或关闭.

This means that each bit is independently on or off with probability 1/2.

几何分布是复杂性的相关分布:翻转硬币并结束关于第一个尾巴结局的实验(没有其他可携带的内容).

The geometric distribution is the relevant distribution for the complexity: you flip coins, and end the experiment on the first tail outcome (there is nothing further to carry).

这里的几何分布的平均值正好是2(请参阅上面的链接，或者从基本原理中得出)，因此平均复杂度确实为 O(1).

The mean of the geometric distribution here is exactly 2 (see above link, or derive it from basic principles), so the average complexity is indeed O(1).

这篇关于二元计数器增量的平均案例时间复杂度分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！