用于在大小为 N 的数组中查找最大值的分而治之策略的时间分析

Question

我编写了这个算法，用于查找大小为 N 的数组中的 MAX 数：

find_max (s,e,A){
if (s != e){
    mid = floor((e-s)/2) + s;
    a = find_max(s,mid,A);
    b = find_max(mid + 1, e,A);
    if (a > b){
        return a;
    }
    return b;
}
return A[s];

}

我想知道时间成本、T(n) 方程以及该算法是否渐近更大、更快或相当于非分而治之策略（顺序比较每个数字）。

我想出了一些答案，但我认为它们都不正确。

谢谢你！

Answer 1

该代码执行 n-1 次比较，这与代码的迭代版本相同，并且是最佳的（请参阅“网球锦标赛拼图中的网球比赛数量”）。

您的代码使用 n-1 比较的证明来自归纳：

T(1) = 0

T(n) = 1 + T(floor(n/2)) + T(n - floor(n/2))
      = floor(n/2)-1 + n - floor(n/2)-1 + 1 (by induction)
      = n - 2 + 1
      = n - 1

您的递归代码使用 O(log N) 存储，与使用 O(1) 存储的迭代版本不同。