分治算法找到数组的最大元素

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;
}

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

Step 1: we say that in case of an array, l=0 and r=10 , it checks if (l>r) which does not hold of course so it calculates m=(0+10)/2; .然后再次执行新边界的过程。第一对是 (0,5)，第二对是 (6,10)，在最后的操作之后，它比较两个返回值，最后返回它们之间的最大元素。

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

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

原文由 user466534 发布，翻译遵循 CC BY-SA 4.0 许可协议

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. 如果范围包含多个元素，我们将其分成两部分。我们递归调用该函数来计算每个部分的最大值。这两个值的最大值是整个范围的最大值。

原文由 Jeffrey Sax 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这个答案可能为时已晚，但它可能对某人掌握递归调用有用，我修改了上面的代码以跟踪函数调用。看到输出后，很容易看到递归树是如何制作的。

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

cout<<"values gonna get computed in 1st recursive call"<< l<<" "<< m<<"\n";
int u = maxsimum(a,l,m);

cout<<"value of u "<<u<<"\n";

cout<<"value gonna get computed in 2nd recursion  call "<<m+1 <<" "<<r<<"\n";
int v = maxsimum(a,m+1,r);

cout<<"value of v : "<<v<<"\n";
cout<<"current u value :"<<u <<"current v value "<<v <<"\n";

return u>v?u:v;
}

int main() {
int a[] = {5,6,7,8,9};
int n = sizeof(a)/sizeof(int);
cout << maxsimum(a,0,n-1) << endl;
return 0;
}

这是上述程序的递归树，树首先向左侧移动，即第一个递归语句，然后每次调用都返回其基值，返回条件确保每次调用只选择最大元素。

                  (9)
                (0,4)
              /      \
           7 /        \9
        (0,2)          (3,4)
         /  \          /    \
       6/    \7      8/      \9
       (0,1)  (2,2)  (3,3)     (4,4)
        / \
      5/   \6
     (0,0) (1,1)

原文由 Kishy Nivas 发布，翻译遵循 CC BY-SA 3.0 许可协议