用于在数组中找到最小值的除法和征服算法

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

代码实现相同。