java - 最大值的预期数量

Question

我有一个算法，它接受一个数组作为参数，并返回它的最大值。

find_max(as) :=
    max = as[0]
    for i = 1 ... len(as) {
        if max < as[i] then max = as[i]
   }
    return max

我的问题是:鉴于数组最初处于(均匀)随机排列并且其所有元素都是不同的，max 变量更新的预期次数是多少(忽略初始值)作业)。

例如，如果 as = [1, 3, 2]，则 max 的更新次数将为 1(读取值 3 时)。

Answer 1

假设原始数组包含值 1、2、...、N。

令 X_i, i = 1..N 为取值 1 的随机变量，如果 i 在算法过程中的某个时刻是最大值。

那么算法取最大值的个数就是随机变量:M = X_1 + X_2 + ... + X_N。

平均数是(根据定义)E(M) = E(X_1 + X_2 + ... + X_N)。使用线性期望，这是 E(X_1) + E(X_2) + .. + E(X_N)，即概率(1 表现为最大值)+ 概率(2 表现为最大值)+ ... + 概率(N 显示为最大值)(因为每个 X_i 取值 0 或 1)。

我什么时候出现最大值？它是当它首先出现在数组中的 i、i+1、i+2、...、N 中时。这种情况的概率是 1/(N-i+1)(因为这些数字中的每一个都同样可能成为第一个)。

所以... prob(i appears as a max) = 1/(N-i+1), 总体期望是 1/N + 1/(N-1) + ..+ 1/3 + 1/2 + 1/1

这是谐波 (N)，它与 ​​ln(N) + emc 非常接近，其中 emc ~= 0.5772156649，欧拉-马歇罗尼常数。

由于在该问题中您没有将最大值的初始设置计算为第一个值，因此实际答案是 Harmonic(N) - 1，或大约 ln(N) - 0.4227843351。

一些简单案例的快速检查:

• N=1，只有一个排列，没有最大更新。谐波 (1) - 1 = 0。
• N=2，排列为 [1, 2] 和 [2, 1]。第一个更新最大值一次，第二个更新零次，所以平均值是 1/2。谐波 (2) - 1 = 1/2。
• N=3，排列为[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [ 3, 2, 1]。最大更新分别为 2、1、1、1、0、0。平均值是 (2+1+1+1)/6 = 5/6。谐波 (3) - 1 = 1/2 + 1/3 = 5/6。

所以理论上的答案看起来不错!