分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
分治算法的求解步骤 (1) 划分：把规模为 n 的原问题划分为 k 个规模较小的子问题，并尽量使这 k 个子问题的规模大致相同。 (2) 求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。 (3) 合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。 分治算法的适用条件 (1) 问题的规模缩小到一定的程度就可以容易地解决。为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足该特征。 (2) 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。这是应用分治法的前提，反映了递归思想的应用。 (3) 问题分解出的子问题的解可以合并为该问题的解。能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备这条特征，则可以考虑贪心算法或动态规划。 (4) 问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题不独立，则分治法要做许多重复工作，重复地求解公共子问题，此时虽然也可用分治法，但一般用动态规划较好。接下来以一个实验例子来体现分治算法（用分治法查找数组元素的最大值和最小值）
实验内容 用分治法查找数组元素的最大值和最小值 （1）问题描述 给定任意几组数据，利用分治法的思想，找出数组中的最大值和最小值并输出。 （2）实验步骤 ① 先解决小规模的问题，如数组中只有 1 个元素或者只有两个元素时候的情况。 ② 将问题分解，如果数组的元素大于等于 3 个，将数组分为两个小的数组。 ③ 递归的解各子问题，将 中分解的两个小的数组再进行以上两个步骤最后都化为小规模问题。 ④ 将各子问题的解进行比较最终得到原问题的解。
实验所用语言为python3,参考代码如下：
import time import numpy def find_bestvalue(array): if len(array) <= 2: Max = max(array) Min = min(array) return [Max,Min] L = find_bestvalue(array[: len(array)//2]) R = find_bestvalue(array[len(array)//2 :]) return merge(L,R) def merge(L,R): Max = (L[0] if L[0]>R[0] else R[0]) Min = (L[1] if L[1]<R[1] else R[1]) return [Max,Min] if __name__ == '__main__': print("请输入随机数组的范围和长度(格式：下界 上界 长度):") cin = input().split(' ') info = [] info.append(int(cin[0])) info.append(int(cin[1])) info.append(int(cin[2])) array = numpy.random.randint(info[0],info[1],info[2]) print('产生的随机数组为：'+str(array)) true_max = max(array) true_min = min(array) print('真实的最大最小值分别为：'+str(true_max)+' '+str(true_min)) start = time.clock() res = find_bestvalue(array) end = time.clock() print('分治法得到的最大最小值分别为：'+str(res[0])+' '+str(res[1])) print('分治算法的运行时间为：'+str(end-start)+'s')C++代码实现：
#include <iostream> #include <windows.h> #include <cmath> #include <bits/stdc++.h>//后面计算时间用得上 using namespace std; void func(int *a , int left , int right , int &Max , int &Min){ int max1=-1; int max2=-1; int min1=1; int min2=1; if(left==right){ Max=Min=a[left]; }else if(right-left==1){ Max=max(a[left],a[right]); Min=min(a[left],a[right]); }else{ int m=(left+right)/2; func(a,left,m,max1,min1); func(a,m+1,right,max2,min2); if(max1>max2){ Max=max1; }else{ Max=max2; } if(min1<min2){ Min=min1; }else{ Min=min2; } } } int main(int argc, char** argv){ int n; int Max=-1; int Min=1; cout<<"input the length of array:"<<endl; cin>>n; int *a=new int[n]; for(int i=0;i<n;i++){ cin>>a[i]; } clock_t start=clock(); func(a,0,n-1,Max,Min); clock_t end=clock(); cout<<"the max value of the array is :"<<Max<<endl; cout<<"the min value of the array is :"<<Min<<endl; cout<<"the time of the fuction has runned:"<<(double)(end-start)*1000000/CLOCKS_PER_SEC <<"μs"<<endl; delete []a; system("pause"); return 0; }
