劃分並征服算法來查找數組的最大元素

我想了解以下算法是如何工作的。劃分並征服算法來查找數組的最大元素

#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

劃分並征服算法來查找數組的最大元素

回答

相關問題