求查找数组中所有最小值的平均比较次数

代码逻辑与比较次数分析 #

给定的代码用于遍历数组并记录所有最小值的位置，其比较次数的逻辑如下：

let all_min = [(0, vec[0])]
let cur_min = vec[0]

for i in 1..vec.len() {
  if vec[i] == cur_min {
    all_min.push((i, vec[i]))
  } else if vec[i] < cur_min {
    cur_min = vec[i]

    all_min.clear()
    all_min.push((i, vec[i]))
  }
}

对数组的第i个元素（从索引1到n-1，共n-1次迭代）：

• 若vec[i]等于当前最小值cur_min：仅执行1次比较（==判断成立，无需进入下一个分支）
• 若vec[i]小于或大于cur_min：会执行2次比较（先判断==不成立，再判断<，无论结果如何都结束当前迭代）

因此，总比较次数可表示为：2*(n-1) - K，其中K是迭代中vec[i]等于当前最小值的次数（每次这种情况会比默认的2次比较少1次）。

平均比较次数推导 #

利用线性期望的性质，平均比较次数等于2*(n-1) - E[K]，其中E[K]是K的期望（即平均有多少次迭代满足vec[i] == cur_min）。我们分常见场景推导：

场景1：元素互异（无重复概率） #

假设数组元素两两不同（比如从连续分布中采样），则vec[i] == cur_min的概率为0，因此E[K] = 0。

此时平均比较次数为：
2*(n-1)
这和最坏情况（逆序数组）的比较次数一致，因为所有迭代都需要执行2次比较。

场景2：元素取自大小为M的离散均匀集合 #

假设每个元素独立从{1,2,...,M}中随机选取，每个值的概率为1/M。

通过望远镜求和可证明：任意一次迭代i中，P(vec[i] == cur_min) = 1/M（与i无关）。因此E[K] = (n-1)/M。

此时平均比较次数为：
(n-1)*(2 - 1/M)

• 当M=1（所有元素相同）：结果为n-1，即最佳情况
• 当M→∞（元素几乎无重复）：结果趋近于2*(n-1)，等同于场景1

场景3：一般离散分布 #

若元素取值为x的概率为q_x，则对于迭代i，P(vec[i] == cur_min)等于所有可能的最小值x的概率乘以q_x的总和：
P(vec[i] == cur_min) = sum_{x} P(前i个元素的最小值为x) * q_x

通过望远镜求和可简化计算，最终平均比较次数仍为2*(n-1) - sum_{i=1}^{n-1} P(vec[i] == cur_min)。

内容的提问来源于stack exchange，提问作者terrabyte