用於在數組中找到最小值的除法和征服算法

Question

某個有序類型元素的數組a [1..n]（即總是定義了x< y），我想要在數組中找到最小值使用「分而治之」的算法。

這個分配究竟意味着什麼？

Answer 1

分而治之是一種算法技術，它通過將問題分解爲更小的部分，解決每個部分中的問題，並將結果組合在一起形成全面答案來解決問題。當問題變得十分簡單時，可以直接解決。

在這種情況下，請考慮如果將數組分成兩半會發生什麼情況。如果你知道每一半的最小值，你能找出整體的最小值嗎？當數組中只剩下一個元素時，數組中的最小值是多少？如果你回答這個問題，你可以直接想出一個遞歸的分而治之的算法來解決這個問題。

希望這會有所幫助！

Answer 2

1. 如果數組的內容是隨機的，這意味着你有，直到你找到你要找的人來搜索每一個元素。數組越長，搜索時間越長。這被稱爲「linear search」。

2. 如果數組的內容已經以某種順序排列，則可以利用此順序優化搜索（並縮短搜索時間）。例如，電話簿中的姓名按字母順序排序。您可以在中間打開電話簿：如果您要查找的名稱「低於」中間的名稱，則繼續在本書左側進行搜索。如果它更高，然後搜索右半部分。這被稱爲「binary search」，或「分而治之」。

3. 可以量化給定搜索算法的效率或低效率。這就是所謂的「Asymptotic」，或「Big O-Notation」：

  
    Class       Search algorithm 
    -----       ---------------- 
    Data structure    Array 
    Worst case performance  O(log n) 
    Best case performance   O(1) 
    Average case performance  O(log n) 
    Worst case space complexity O(1)

Answer 3

分而治之的策略以解決問題：

1. 它闖入本身是較小的情況下，子問題同類型 問題的

2. 遞歸解決這些子問題

個

3. 適當地組合自己的答案

一個很好的例子是合併排序！

http://en.wikipedia.org/wiki/Merge_sort

Answer 4

通常，「分而治之」是指劃分的問題成更小的（通常更簡單）的問題，分別解決每一個，然後以某種方式結合的解決方案。

在您的具體示例中，您應該以某種方式將數組分成較小的數組（例如，，將它除以一半），找出每個較小陣列中的最小值，然後選擇這些子問題的最小解決方案作爲整體問題的解決方案。每個子問題都可以使用相同的分而治之的方法來解決，限制的情況是一個足夠小的數組（例如1或2），您可以直接解決問題。

Answer 5

U可以與下面的算法去。在鏈路

getSmallest(int a[]) 
{ 
    int n=a.length; 
    if(n==1) 
    return a[0]; 
    else 
    { 
     x=remove first element from a; 
     create another array b with a size smaller by 1 than array a 
     if(x<getSmallest(b)) 
      return x; 
     else 
      return the smallest returned by the recursive call 
    } 
} 

Answer 6

http://ankzcode.blogspot.in/2012/11/find-minimum-without-linear-search.html

代碼實現相同。