在数组中查找最小值所需的分配数量？

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;
}

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

从均匀分布中随机挑选数字.

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个"谐波数",你只能大约以闭合形式获得.(嗯,一个小于n_th谐波数.这个问题将是更漂亮,如果你初始化max来INT_MIN,只是让循环运行,使F(1)= 1)

以上并不是一个严格的证据,因为我对预期值与实际值的关系很邋.但我相信答案是正确的:-).

Answer 2

我想对Nemo的答案发表评论,但我没有评论的声誉.他的正确答案可以简化:

第二个数字大于第一个数字的机会是1/2.无论如何,第三个数字大于之前的几率是1/3.这些都是独立的机会,因此总的期望

1/2 + 1/3 + 1/4 + .. + 1/n