arrays - 用于查找数组中最小值的分治算法

Question

某个有序类型的元素数组 a[1..n]（即 x < y 总是被定义），我想使用“分而治之”算法找到数组中的最小值。

任务的真正含义是什么？

Answer 1

分而治之是一种算法技术，它通过将问题分解成更小的部分来解决问题，在每个部分中解决问题，然后将结果组合在一起形成一个整体的答案。当问题变得足够简单时，可以直接解决。

在这种情况下，想想如果将数组分成两半会发生什么。如果你知道每一半的最小值，你能算出整体的最小值吗？当数组中只剩下一个元素时，数组中的最小值是多少？如果你回答了这个问题，你可以直接为这个问题想出一个递归的分治算法。

希望这可以帮助！

Answer 2

分治策略通过以下方式解决问题：

1. 将其分解为子问题，这些子问题本身就是同一类型问题的较小实例

2. 递归解决这些子问题

3. 适当地结合他们的答案

一个很好的例子是合并排序！

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

Answer 3

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

链接处的代码实现相同。

Answer 4

你可以使用以下算法。

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 5

1. 如果数组的内容是随机的，这意味着您必须搜索每个元素，直到找到您要查找的元素。数组越长，搜索时间越长。这称为“线性搜索”。

2. 如果数组的内容已经按某种顺序排列，您可以利用此顺序来优化搜索（并减少搜索时间）。例如，电话簿中的姓名按字母顺序排序。您可以打开中间的电话簿：如果您要查找的名字“低于”中间的名字，则在电话簿的左侧继续搜索。如果它更高，则搜索右半部分。这称为“二分查找”或“分而治之”。

3. 可以量化给定搜索算法的效率或低效率。这称为“渐近”或“大 O 表示法”：

    
    类搜索算法
    ---------
    数据结构数组
    最坏情况性能 O(log n)
    最佳案例性能 O(1)
    平均案例性能 O(log n)
    最坏情况空间复杂度 O(1)

Answer 6

一般来说，“分而治之”意味着将一个问题分成更小（通常更简单）的问题，分别解决每个问题，然后以某种方式组合解决方案。

在您的具体示例中，您应该以某种方式将数组分成较小的数组（例如，将其分成两半），在每个较小的数组中找到最小值，然后选择这些子问题的最小解作为整体问题。每个子问题都可以使用相同的分而治之的方法来解决，限制情况是一个足够小的数组（例如，1 或 2），您可以直接解决问题。