划分并征服算法来查找数组的最大元素

我想了解以下算法是如何工作的。划分并征服算法来查找数组的最大元素

#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），并且在最终操作之后，它比较两个返回值并最终返回它们之间的最大元素。

此算法是否总能正常工作？在每次迭代中，它都不做任何比较，只是最后一步。它如何确定每次递归迭代的最大元素？它只检查什么。例如：取对（0,5），是（0大于5）？不，再重复一遍，将这些边界分成两部分，然后再次得到新的平均值m1 =（0 + 5）/ 2，并返回一些元素，但不是最大值。对于第二个子数组，我们也可以这样说。

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

来源

2011-09-06 dato datuashvili

是的，我知道这是递归的最大元素搜索我只需要要了解它是如何发现的最大我正在试图做的纸一些工作，但没有任何结果 –

你的问题是完全不知所云。我试图改进它，但我真的不知道从哪里开始。请使用段落和适当的格式。 –

@康拉德鲁道夫我的问题是比较是写在最后一行是否正确？ –

你的困惑是可以理解的：所写的算法包含一些错误。它在a的末尾访问内存，这非常非常糟糕。另外，测试一个范围是否只包含一个元素是不正确的。如果没有解决，这会导致堆栈溢出。

maxsimum函数的调用方式表明下限包含在范围内，但上限不包含在内。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;  
}

现在，我们有一个正确的程序如何，解释这个工作很简单：

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

来源

2011-09-06 23:55:59

这个算法的渐近复杂性是什么？ – Faizan

它将O（n）表示为T（n）= 2T（n/2）+1 – codenut

主要思想是如果我们将数组分成2个子数组，那么最大值必须在数组的左边或右边;没有其他的可能性。

所以我们在左边部分找到最大值，我们在右边找到最大值，全局最大值显然是两个最大值之间的最大值，也就是maxsimum函数最后一行返回的值。

来源

2011-09-06 12:55:09 Simone

感谢您的回复我知道这我不是问这个算法做什么，请问我是如何确定在每个子阵列，它如何发现最大限度，比较是在最后一步，所以它让我困惑 –

它是什么运行时间，或该算法的渐近复杂性？ – Faizan

.... Theta（n）.... – Simone

你的错误是在这里：

在每次迭代它不会做任何比较，只有最后一步。

这是错误的。实际上，它在之间每递增步骤进行比较（除了在基本情况下，即数组大小为1的情况）。

来源

2011-09-06 13:00:40

好的，谢谢@Konrad Rudolph谢谢你的回复，我会试着更深入地理解 –

让我简评供您的代码的最大部分，并尽量不要添加困惑：

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]，它将进行第一次比较。这些结果将传递到较高的案例，直到它退出最后一次返回所有案例的最大值的函数。

我希望能够为你澄清一下。

来源

2011-09-06 14:27:53 daramarak

错误main()功能，测试阵列有10个元素，应该是：

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

来源

2012-09-20 06:17:32 alex

这个答案可能是这么晚了，但它可能是有用的人掌握递归调用，我修改了以上代码来追踪函数调用。看到输出后，很容易看到如何构建递归树。

#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)

来源

2017-05-05 14:36:30

划分并征服算法来查找数组的最大元素

回答

相关问题