在数组中找到最大值的预期分配数量

Question

在以下Java代码中：

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

max = arr[i];假设数组未排序，该行运行多少次。

Answer 1

期望值可以通过期望的线性度来计算。如果此站点支持MathJax，我可以提供更严格的答案。

答案是对于i = 1至n =和1 / i（i = 1至n = O（log n））的总和1 /（n-i + 1），其中n是数组的大小（假定数组的所有元素数组是不同的）

警告，前面的数学部分。

关键思想是，如果我们为每个元素分配字典索引“ i”，其中“ i”表示该元素是“ i”个最小元素，那么只有在n-i + 1个较大元素都不存在的情况下才会进行分配数组中第ith元素之前的apprar。对于所有i，这在随机数组中发生的概率为1 /（n-i + 1）。然后，我们只使用指标随机变量来应用期望的线性：)