在大小为 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

当你有一个元素时，你的算法成本为 1（return 唯一元素的成本）

T(1) = 1

否则，它是两个递归调用，将输入分成两半，加上恒定数量的操作：

T(n) = T(floor(n / 2)) + T(ceil(n / 2)) + c

利用master theorem我们可以找到如下渐近解：

T(n) = O(n)

例如线性算法。所以渐进地，算法的迭代版本和递归版本需要相同的时间。

Answer 2

该代码执行 n-1 次比较，与代码的迭代版本相同，并且是最优的（参见 "number of tennis matches in a tennis tournament puzzle"）。

您的代码使用 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(1) 存储的迭代版本不同，您的递归代码使用 O(log N) 存储。

Answer 3

请记住，在 N 个元素的未排序数组中查找最大元素的 space 个解决方案是 N 本身。这个问题是输入维度的线性下界，Ω(n)，所以找到比这更好的东西是不可能的。

在大小为 N 的数组中寻找最大值的分治策略的时间分析

Time Analysis of a divide-and-conquer strategy fo find the max value in a array of size N

arrays

algorithm

time-complexity

divide-and-conquer