分配必要的数量，以找到一个数组的最小值？ [英] Number of assignments necessary to find the minimum value in an array?

问题描述

有人问我一个谜题，而我不知道;我所知减慢平摊分析后，在这种情况下，这是O（n）。

Someone asked me a brainteaser, and I don't know; my knowledge slows down after amortized analysis, and in this case, this is 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的数组？

What's the expected value of count for an array of size n?

数字是随机地从一个均匀分布拾取

Numbers are randomly picked from a uniform distribution.

推荐答案

设f（n）是分配的平均数。

Let f(n) be the average number of assignments.

然后，如果最后一个元素不是最大，F（N）= F（N-1）。

Then if the last element is not the largest, f(n) = f(n-1).

如果最后一个元素是最大的，则f（N）= F（N-1）+1

If the last element is the largest, then f(n) = f(n-1) + 1.

由于最后一个数字是最大的概率 1 / N ，而不是最大的概率（N-1）/ N ，我们有：

Since the last number is largest with probability 1/n, and not the largest with probability (n-1)/n, we have:

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

展开并收集方面获得：

Expand and collect terms to get:

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

和f（1）= 0。因此：

And f(1) = 0. So:

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和谐号，你可以在封闭的形式得到的只有约。 （好吧，比n_th谐波数量少，这个问题将是prettier如果初始化最高到 INT_MIN ，只是让循环运行，使F（1）= 1。）

That is, f(n) is the n_th "Harmonic number", which you can get in closed form only approximately. (Well, one less than the n_th Harmonic number. The problem would be prettier if you initialized max to INT_MIN and just let the loop run, so that f(1) = 1.)

以上是不是一个严格的证明，因为我是马虎有关预期值与实际值。但是，我相信答案是正确的呢： - ）

The above is not a rigorous proof, since I was sloppy about expected values versus actual values. But I believe the answer is right anyway :-).

这篇关于分配必要的数量，以找到一个数组的最小值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！