在一个数组中寻找最大值所需的期望赋值次数

Question

在以下Java代码中：

int max = arr[0];
for (int i = 0; i < arr.length i++) {
    if (arr[i] > max) {
         max = arr[i];
    }
} 

假设数组未排序，代码行max = arr[i];会运行多少次？

- 12345webster12345

---

每次它在数组中找到一个小于最大值的数值。 - sAm

但是必须有一个预期的数字次数来运行它。 - 12345webster12345

那段代码是用于最小值，而不是最大值。 - Paul Boddington

抱歉 - 我把 > 符号弄反了。 - 12345webster12345

Answer 1

预期值可以通过期望的线性计算得出。如果这个网站支持MathJax，我可以提供更严谨的答案。

答案是对于i = 1到n，求和1/(n-i+1) = 对于i = 1到n，求和1/i = O(log n)，其中n是数组的大小（假设数组的所有元素都不同）。

警告：接下来是数学部分。

关键思想是，如果我们为每个元素分配一个词典索引'i'，其中'i'表示元素是第'i'小的元素，则只有在数组中第i个元素之前没有出现任何n-i+1个较大的元素时才会发生分配。对于所有i，这在随机数组中发生的概率是1/(n-i+1)。然后我们只需使用指示随机变量的期望线性计算即可 :)

- Banach Tarski