分治算法寻找数组最大元素

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

首先，我感兴趣的是尽管算法工作得正确，但我仍然不明白它如何找到最大元素。我将展示我如何理解这个算法：

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

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

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

- user466534

---

是的，我知道它是递归最大元素搜索，我只想要理解它如何找到最大值。我试图在纸上做一些工作，但没有结果。 - user466534

@ Konrad Rudolph，我的问题是，最后一行写的比较是否正确？ - user466534

@MooingDuck 这个算法的渐进复杂度是多少？ - Faizan

@Faizan：渐进复杂度相同，但常数乘数至少是两倍大，因此这至少要慢两倍。 - Mooing Duck

这是大O(n)。我想出来了。 - Faizan

Answer 1

你的困惑是可以理解的：该算法存在一些错误。它访问了a数组的末尾之外的内存，这非常非常糟糕。此外，判断一个范围是否只包含一个元素的测试也是不正确的。如果不加以解决，这将导致堆栈溢出。

最大函数的调用方式表明，下限包含在范围内，但上限不包括在内。a [0]是有效的，但 a [n]访问了a数组之外的内存。在分割范围时，我们希望第一部分从l开始到m，但不包括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

---

这个算法的渐进复杂度是多少？ - Faizan

它的时间复杂度为O(n)，因为T(n) = 2T(n/2) + 1。 - codenut

Answer 2

主要思路是将数组分为两个子数组，那么最大值必然在数组的左半部分或右半部分中；没有其他可能性。

所以我们找到左半部分的最大值，找到右半部分的最大值，全局最大值显然是两个最大值中的最大值，这就是最大函数的最后一行返回的内容。

- Simone

---

谢谢回复，我知道这个。我不是在问这个算法做什么，请问它如何确定每个子数组中的最大值，如何找到最大值？比较是在最后一步进行的，所以这让我感到困惑。 - user466534

这个算法的运行时间或渐进复杂度是多少？ - Faizan

Answer 3

你的错误在这里：

每次迭代中，它并没有进行任何比较，只有最后一步。

这是错误的。实际上，在递归的每一步中都会进行比较（除了基本情况，即数组大小为1的情况）。

- Konrad Rudolph

---

好的，谢谢@Konrad Rudolph回复。我会尽力更深入地理解。 - user466534

Answer 4

main() 函数出现错误，测试数组应该有10个元素：

cout << maxsimum(a,0,n-1) << endl;

- alex

Answer 5

让我为您注释大部分代码，尽量不添加混乱：

if (l==r)  return a[l]; //trivial case, if there is only one value in the array return it
int m=(l+r)/2; //find value halfway into the array
int u=maxsimum(a,l,m); //find the maximum value for the lower part of the array
int v=maxsimum(a,m+1,r); //find the maximum value for the top part of the array
return u>v?u:v; //return the highest value of them.

所以数组0..10被分成0..5和6..10并传递到同一个函数中。只有当只有一个值时，递归才会结束，并将该单个值传递给其调用者。然后在第二个最低的情况下，例如值a[0]和a[1]，它将进行第一次比较。这些结果将向上传递到更高的情况，直到它最终退出函数，返回所有情况中最大的值。

我希望能为您澄清一些问题。

- daramarak

Answer 6

这个答案可能有点晚，但对于理解递归调用可能对某些人有用，我修改了上面的代码以跟踪函数调用。 看到输出后，很容易看出如何创建递归树。

#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