algorithm - 在数组中找到最小值所需的赋值次数？

Question

有人问我脑筋急转弯，我不知道；摊销分析后我的知识变慢了，在这种情况下，这是 O(n)。

public int findMax(array) {
  int count = 0;
  int max = array[0];
  for (int i=0; i<array.length; i++) {
    if (array[i] > max) {
      count++;
      max = array[i];
    }
  } 
  return count;
}

对于大小为 n 的数组，count 的期望值是多少？

数字是从均匀分布中随机选取的。

Answer 1

设 f(n) 为分配的平均数。

那么如果最后一个元素不是最大的，f(n) = f(n-1)。

如果最后一个元素是最大的，则 f(n) = f(n-1) + 1。

由于最后一个数字最大的概率为 1/n，而不是最大的概率为 (n-1)/n，我们有:

f(n) = (n-1)/n*f(n-1) + 1/n*(f(n-1) + 1)

展开并收集术语以获得:

f(n) = f(n-1) + 1/n

并且 f(1) = 0。所以:

f(1) = 0
f(2) = 0 + 1/2
f(3) = 0 + 1/2 + 1/3
f(4) = 0 + 1/2 + 1/3 + 1/4

也就是说，f(n) 是第 n_th 个“谐波数”，您只能以闭合形式得到它 approximately . (好吧，比第 n_th 谐波数少一个。如果将 max 初始化为 INT_MIN 并让循环运行，那么问题会更漂亮，这样 f(1) = 1.)

以上不是严格的证明，因为我对预期值与实际值比较马虎。但我相信答案无论如何都是正确的:-)。