本文共 1607 字，大约阅读时间需要 5 分钟。

分治法寻找数组最大最小值

问题描述

输入一组数据，找出其中的最大值和最小值。这是一种典型的分治问题，可以通过将数据不断划分，然后分别处理子部分来解决。

分治思想

在传统的分治方法中，我们采用递归的方式来解决问题。以下为寻找数组最大最小值的分治实现思路：

代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;void search(int *a, int l, int r, int &maxi, int &mini) {    if(l == r) {        maxi = mini = a[l];        return;    }    int mid = (l + r) / 2;    int max1, max2, min1, min2;    search(a, l, mid, max1, min1);    search(a, mid+1, r, max2, min2);    maxi = max(max1, max2);    mini = min(min1, min2);}int main() {    int n, i;    LARGE_INTEGER nFreq, nBegin, nEnd;    double time;    ifstream in("input.txt");    ofstream out("output.txt");    in >> n;    int a[n];    for(i = 0; i < n; ++i) {        in >> a[i];    }    QueryPerformanceFrequency(&nFreq);    QueryPerformanceCounter(&nBegin);    search(a, 0, n-1, maxi, mini);    QueryPerformanceCounter(&nEnd);    time = (double)(nEnd.QuadPart - nBegin.QuadPart) / (double)nFreq.QuadPart;    out << "maxi: " << maxi << " mini: " << mini << "\n"         << "search time: " << time << "s\n";    in.close();    out.close();    return 0;}
      
     
    
   

复杂度分析

主函数时间复杂度分析

递归函数复杂度：

迭代处理：

迭代方法虽然也能解决问题，但速度是线性的，时间复杂度为O(2n)，与分治法相当。

测试数据及结果分析

以下是不同规模数据的运行时间测试结果：

转载地址：http://ozdyk.baihongyu.com/