在数组中找到最小值所需的分配次数？

小编典典

在数组中找到最小值所需的分配次数？

algorithm

有人问我一个脑筋急转弯，但我不知道。经过摊销分析后，我的知识变慢了，在这种情况下，这是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的数组的期望值是多少？

从均匀分布中随机选择数字。

阅读 209

2020-07-28

共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个谐波数小1。如果初始化max为INT_MIN并让循环运行，则问题会更漂亮，这样f（1）=1。）

以上并不是严格的证明，因为我对预期值与实际值不满意。但是我仍然相信答案是正确的:-)。

2020-07-28