algorithm - 二进制计数器的平均情况

Question

INCREMENT(A)
i = 0
while i< A.length and A[i] ==1
    A[i]=0
    i=i+1
if i< A.length
    A[i]=1

我现在正在自学摊销分析，我在思考平均案例分析和摊销分析之间的区别，我知道二进制计数器操作 INCREMENT(Array) 的摊销成本是 O(1) 但是什么如果我想分析增量的平均情况？我正在考虑假设我们需要翻转的平均位数是 n/2，其中 n 是总位数，但我在 Average Case Time Complexity Analysis of Binary Counter Increment 中看到了答案。 ，这对我来说没有多大意义。谁能解释一下？这会很有帮助，因为我真的知道答案是什么:D

Answer 1

我假设“平均”意味着我们选择一个长度为 n 的随机数组 0 和 1以相同的概率选择每个可能的选项。这相当于设置每个 n数组的元素到 0以 1/2 的概率到达 1以相同的概率。

while 循环体至少被执行一次的概率是多少？它是 1/2(当且仅当数组的第一个元素为 1 时才执行)。循环体至少执行两次的概率是多少？它是前两个元素等于1的概率，等于1/2 * 1/2 = 1/4(因为第一个和第二个元素等于1的概率是独立的)。我们可以通过归纳证明，while循环体被执行的概率至少是i。次 ( 1 <= i <= n ) 是 (1/2)^n .

这意味着它将以 1/2 的概率进行一次迭代，以 1/4 的概率再进行一次迭代，以 1/8 的概率再进行一次迭代，依此类推。因此，迭代次数的期望值为sum for 1 <= i <= n (1/2)^i。 , 以无限级数之和为界 1/2+1/4+1/8+... ，它等于 1(这显然是一个常数)。无论输入如何，除了 while 循环之外的所有其他操作都执行恒定次数。因此，总时间复杂度平均不变。