c++ - 分而治之算法找到数组的最大元素

Question

我正在尝试了解以下算法的工作原理。

#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
    if (l == r)  
        return a[l];
    int m = (l+r)/2;
    int u = maxsimum(a,l,m);
    int v = maxsimum(a,m+1,r);
    return u>v?u:v;    
}

int main() {
    int a[] = {34,23,45,56,30,31,57,33,55,10};
    int n = sizeof(a)/sizeof(int);
    cout << maxsimum(a,0,n) << endl;         
    return 0;
}

首先，我感兴趣的是，尽管算法工作正常，但它如何找到最大元素对我来说还是个谜。我将展示我是如何理解这个算法的:

第 1 步:我们说在数组的情况下，l=0 和 r=10，它检查 if (l>r) 当然不成立，所以它计算 m=(0+10)/2;。然后再次执行新边界的过程。第一对是 (0,5)，第二对是 (6,10)，在最后的操作之后它比较两个返回值，最后返回它们之间的最大元素。

这个算法总是有效吗？在每次迭代中它不做任何比较，只做最后一步。它如何确定每次递归迭代的最大元素？它只检查什么。例如:取 pair(0,5)，(0 大于 5) 吗？不，所以再次重复并将这些界限一分为二，得到新的平均值 m1=(0+5)/2 然后再次返回一些元素但不是最大值。对于第二个子阵列，我们也可以这样说。

这个算法的主要思想是什么？

Answer 1

您的困惑是可以理解的:所编写的算法包含一些错误。它访问 a 末尾之后的内存，这是非常非常糟糕的。此外，测试范围是否仅包含一个元素是不正确的。如果不解决，这将导致堆栈溢出。

最大函数的调用方式表明下限包含在范围内，但上限不包含在内。 a[0] 是有效的，但是 a[n] 访问 a 结尾之后的内存。拆分范围时，我们希望第一部分从 l 开始运行但不包括 m，第二部分从 m 开始运行到但不包括 r。换句话说:第一部分的“不包含”上限等于第二部分的“包含”下限。对 maxsimum 的第一次内部调用是正确的。第二次内部调用应该是:

int v=maxsimum(a,m,r); 

这给我们留下了检测长度为 1 的范围的问题。就目前而言，该算法实际上是在寻找一个空 范围。正确的测试是查看上限和下限之间的差异:

if (r-l == 1) return a[l];

完整的函数如下:

int maxsimum(int a[],int l,int r){
   if (r-l==1)  return a[l];
   int m=(l+r)/2;
   int u=maxsimum(a,l,m);
   int v=maxsimum(a,m,r);
   return u>v?u:v;    
}

现在我们有了一个正确的程序，对其工作原理的解释就很简单了:

1. 如果范围内只包含一个元素，那么这个元素就是最大值。
2. 如果范围包含多个元素，我们将其分成两部分。我们递归地调用该函数来计算每个部分的最大值。这两个值的最大值是整个范围的最大值。