分治算法字面意思就是将一个复杂的数据进行分开计算，分治 的策略就是： 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：
T（n）= k T(n/m)+f(n)
通过迭代法求得方程的解：
递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当 mi≤n<mi+1时，T(mi)≤T(n)<T(mi+1)。
可用分治法求解一些经典问题例如：（可自行百度）
（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔
Paste_Image.png
那么分治算法到底是怎么分治呢？下面举个简单的例子：
比如:
f(0)=1
f(1)=8
f(n)=f(n-1)+f(n-2)
那么如果我们要求f(80)直接就可以分成f(79)+f(78),然后f(79)和f(78)继续往下一直分直接分解至f(1)+f(0)为止.
下面我们来举个例子算下，比如说有支股票从第0天到16天每天的股价分别为以下:
100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97
然后我们需要求出从哪天买入哪天卖出能够挣钱最多，这里我们有两种方法可以求得，第一种暴力求解，第二种使用分治法。
那么暴力求解怎么求得呢，下面我们用代码实现下
暴力求解
int[] priceArray = { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97 };
int[] priceFluctationArray = new int[priceArray.Length - 1];//价格从第0天到第16天内波动的数组
//求出价格波动的数值
for (int i = 1; i < priceArray.Length; i++)
{
priceFluctationArray[i - 1] = priceArray[i] - priceArray[i - 1];
}
int total = priceFluctationArray[0];//默认波动数组的第一个元素是最大数组
int startIndex = 0;
int endIndex=0;
for (int i = 0; i < priceFluctationArray.Length; i++)
{
//取得以i为子数组起点的所有子数组
for (int j = i; j < priceFluctationArray.Length; j++)
{
int totalTemp = 0;//临时 最大数组的和
for (int index = i; index < j+1; index++)
{
totalTemp += priceFluctationArray[index];
}
if (totalTemp > total)
{
total = totalTemp;
startIndex = i;
endIndex = j;
}
}
}
Console.WriteLine("购买日期是第" + startIndex+"天，出售是第"+ (endIndex+1)+"天最能挣钱,总共挣"+total);
输出结果
Paste_Image.png
那么下面我们来看看分治算法怎么实现的。
比如我们有一个数组，要求到一个最大子数组,从low到high大小，那么我们直接取一个中间的数值mid,然后这个数组就分成了[low,mid] [mid+1,hight]，这个时候就有三种情况
（1）我们需要的值在低区间[low,mid]里面
（2）我们需要的值在高区间[mid+1,hight]里面
（3）我们需要的值位于低区间和高区间之间
Paste_Image.png
这里面我们就将问题分成了小问题去解决，下面我们来看看代码怎么实现
Paste_Image.png
分治算法求解
//最大子数组的结构体
struct SubArray
{
public int startIndex;//开始索引
public int endIndex;//结束索引
public int total;//和
}
static void Main(string[] args)
{
int[] priceArray = { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97 };
int[] pf = new int[priceArray.Length - 1];//价格波动的数组
for (int i = 1; i < priceArray.Length; i++)
{
pf[i - 1] = priceArray[i] - priceArray[i - 1];
}
SubArray subArray = GetMaxSubArray(0, pf.Length - 1, pf);
Console.WriteLine("我们在第" + subArray.startIndex + "天买入， 在第" + (subArray.endIndex + 1) + "天卖出" + ",能挣钱" + subArray.total);
Console.ReadKey();
}
static SubArray GetMaxSubArray(int low, int high, int[] array)//这个方法是用来取得array 这个数组 从low到high之间的最大子数组
{
//分解的终止的条件
if (low == high)
{
SubArray subarray;
subarray.startIndex = low;
subarray.endIndex = high;
subarray.total = array[low];
return subarray;
}
int mid = (low + high) / 2; // 低区间 [low,mid] 高区间[mid=1,high]
SubArray subArray1 = GetMaxSubArray(low, mid, array);
SubArray subArray2 = GetMaxSubArray(mid + 1, high, array);
//从【low,mid】找到最大子数组[i,mid] 需要的最大子数组位于低区间
int total1 = array[mid];
int startIndex = mid;
int totalTemp = 0;
for (int i = mid; i >= low; i--)
{
totalTemp += array[i];
if (totalTemp > total1)
{
total1 = totalTemp;
startIndex = i;
}
}
//从【mid+1,high】找到最大子数组[mid+1,j] 需要的最大子数组位于高区间
int total2 = array[mid + 1];
int endIndex = mid + 1;
totalTemp = 0;
for (int j = mid + 1; j <= high; j++)
{
totalTemp += array[j];
if (totalTemp > total2)
{
total2 = totalTemp;
endIndex = j;
}
}
//需要的最大子数组位于高区间和低区间之间
SubArray subArray3;
subArray3.startIndex = startIndex;
subArray3.endIndex = endIndex;
subArray3.total = total1 + total2;
//判断三个区间的三个和哪个大。需要的最大子数组在哪个区间里面
if (subArray1.total >= subArray2.total && subArray1.total >= subArray3.total)
{
return subArray1;
}
else if (subArray2.total >= subArray1.total && subArray2.total >= subArray3.total)
{
return subArray2;
}
else
{
return subArray3;
}
}
输出结果
shuc
网友评论