algorithm - TADM 2-45 : What's the expected number of times tmp=A[i] is performed?

Question

我正在尝试解决算法设计手册中的以下练习 (2-45):

考虑以下算法来查找数字数组中的最小元素 A[0, ..., n] .一个额外的变量 tmp被分配以保存当前的最小值。从 A[0] 开始, tmp与 A[1] 进行比较, A[2] , ..., A[n]为了。当A[i] < tmp , tmp = A[i] .

赋值操作tmp = A[i]的期望次数是多少？执行了吗？

我找到了 this solution在线但看不懂。等式

E[n] = E[n-1] + 1/n, E[1] = 0

给出 0 + 1/n + 2/n + 3/n...但我认为那是不正确的。因为所要求的不仅与最小的元素有关，而且与第二小的元素、第三小的元素等有关。

有人可以解释一下他们对这个问题的看法吗？谢谢!

Answer 1

您指出的解决方案是正确的，尽管没有明确解释。

对 tmp 进行赋值的预期次数是在每个元素上进行赋值的概率之和。在元素 j 处进行赋值的概率是元素 Xj 在 {X1, X2, … Xj} 中最小的概率，根据作者的假设，它是 1/j 因为上面集合中有 j 个元素.

他们的期望是 sum(1/j) ~ ln(n)。