MinMax算法时间复杂度分析：嵌套版比较次数疑问求解

我正在分析一个嵌套版本的MinMax算法，算法代码如下：

ALGORITHM MaxMin2(A[0..n − 1], MaxValue, MinValue)

MaxValue ← A[0]
MinValue ← A[0]

for i ← 1 to n − 1 do
    if A[i] > MaxValue
        MaxValue ← A[i]
    else
        if A[i] < MinValue
            MinValue ← A[i]

我原本认为该算法需要2n-2次比较，但有资料表明这个嵌套版本的算法比较次数为2n - ln n - 1次，请问能否有人解释这一结论的由来？

首先得明确：你一开始想到的2n-2次是最坏情况的比较次数——比如当数组元素严格递增或者严格递减时，每个后续元素都要先和MaxValue比较（不满足），再和MinValue比较，每个元素消耗2次比较，n-1个元素就是2(n-1)=2n-2次。

而资料里提到的2n - ln n -1是平均情况的近似比较次数，前提是数组元素是随机排列的，下面一步步推导这个结论：

1. 单个元素的期望比较次数 #

我们遍历从第2个元素（i=1）到第n个元素（i=n-1），共n-1个元素。对每个元素A[i]：

• 第一次比较：和当前MaxValue对比。如果A[i]是前i+1个元素中的最大值，那么只需要1次比较就完成（直接更新MaxValue）。在随机排列的数组中，每个元素成为前i+1个元素最大值的概率是1/(i+1)（所有元素平等）。
• 如果A[i]不是最大值（概率为i/(i+1)），则需要做第二次比较：和MinValue对比，此时总共消耗2次比较。

所以单个元素的期望比较次数为：
1*(1/(i+1)) + 2*(i/(i+1)) = 2 - 1/(i+1)

2. 总期望比较次数求和 #

把n-1个元素的期望比较次数加起来：

总期望次数 = Σ（i从1到n-1）[2 - 1/(i+1)]
          = 2*(n-1) - Σ（k从2到n）[1/k]  // 令k=i+1做变量替换

这里的Σ（k从2到n）[1/k]是调和级数的一部分，而完整的调和级数H_n = 1 + 1/2 + 1/3 + ... + 1/n，所以：
Σ（k从2到n）[1/k] = H_n - 1

代入后得到：

总期望次数 = 2(n-1) - (H_n - 1)
          = 2n - 2 - H_n + 1
          = 2n - H_n - 1

3. 调和级数的近似 #

当n很大时，调和级数有经典的近似公式：
H_n ≈ ln n + γ
其中γ是欧拉常数（约0.5772），当n足够大时，γ的影响可以忽略，所以近似得到：
总期望次数 ≈ 2n - ln n -1

这就是资料里结论的由来啦——它描述的是随机数组下的平均比较次数，而非最坏情况。

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