algorithm - 变量 m 更新了多少次

Question

给定以下伪代码，问题是变量 m 平均更新了多少次。

A[1...n]: array with n random elements 
m = a[1]
for I = 2 to n do
   if a[I] < m then m = a[I]
end for

有人可能会回答，因为所有元素都是随机的，所以变量将平均更新为 for 循环迭代次数的一半加上初始化迭代次数。

但是，我怀疑必须有更好的(并且可能是唯一正确的)方法来使用 p = 1/2 的二项分布来证明它。这样，m 上的平均更新次数将是

M = 1 + Σi=1 to n-1[k.C<sub>n,k</sub>.p<sup>k</sup>.(1-p)<sup>(n-k)</sup>]

其中 C_n,k 是二项式系数。我试图解决这个问题，但由于我不知道如何继续，所以我坚持了一些步骤。

谁能告诉我这两个答案中哪一个是正确的，如果是第二个，请告诉我如何计算 M？

谢谢你的时间

Answer 1

假设数组的元素不同，m 的预期更新次数是第 n harmonic number , H_n, 是1到n范围内k的1/k之和。

求和公式也可以用递归表示:

H<sub>1</sub> = 1
H<sub>n</sub> = H<sub>n−1</sub>+1/n (n > 1)

很容易看出递归对应问题。

考虑 n−1 个数的所有排列，并假设预期的分配数为 H_n−1。现在，n 个数字的每个排列都由 n-1 个数字的排列组成，在 n 个可能的插入点之一插入一个新的最小数字:在开头或在 n-1 个现有值之一之后。由于它比现有系列中的每个数字都小，因此只有在开头插入的情况下才会分配给 m。它的概率为 1/n，因此 n 个数排列的预期分配数为 H_n−1 + 1/n。

由于长度为 1 的向量的预期分配数显然为 1，即 H₁，因此我们有递归的归纳证明。

H_n 渐近等于 ln n + γ 其中 γ 是 the Euler-Mascheroni constant ，大约为 0.577。因此它会无限增加，但会非常缓慢。

更新 m 的值称为从左到右的最大值，您可能会通过搜索该术语找到有关它们的更多信息。