我正在尝试解决《算法设计手册》中的以下练习 (2-45)：
考虑以下算法来查找数字数组中的最小元素A[0, ..., n]。分配一个额外的变量tmp来保存当前最小值。从 , 开始A[0]，tmp按顺序与A[1], A[2], ...,A[n]进行比较。什么时候A[i] < tmp，tmp = A[i]。
tmp = A[i]预计执行赋值操作的次数是多少？
我在网上找到了这个解决方案，但无法理解。等式
E[n] = E[n-1] + 1/n, E[1] = 0
给出0 + 1/n + 2/n + 3/n...但我认为这是不正确的。因为所要求的不仅与最小元素有关，还与第二小元素、第三最小元素等有关。
有人能解释一下他们对这个问题的想法吗？谢谢！
您指出的解决方案是正确的，尽管没有明确解释。
\n\n对 tmp 进行赋值的预期次数是对每个元素进行赋值的概率之和。在元素 j 处进行分配的概率是元素 Xj 为 {X1, X2, \xe2\x80\xa6 Xj} 中最小的概率，根据作者的假设，该概率为 1/j，因为有 j上述集合中的元素。
\n\n期望是它们的 sum(1/j) ~ ln(n)。
\n