首页 > 代码库 > Chapter 4 分治策略
Chapter 4 分治策略
分治策略：
在每层递归中应用如下三个步骤：
分解：将问题划分为一些子问题（子问题的形式与原问题一样，只是规模更小）。
解决：递归地求解子问题，当然，当子问题规模到你满意时就直接求解！
合并：将子问题的解合并为原问题的解
注： 有时会遇到需求解与原问题不完全一样的子问题，将其求解视为合并的一部分（出现此类情况可以思考下有没必要用分治）
4.1 最大子数组问题
即找出一个数组中元素和最大的子数组(对于全正的数组没意义)
最简单的方式是暴利求解，即两个for循环，但该方法的时间复杂度为θ(n2)
分治策略求解：分两种情况，最大子数组位于两侧子数组或者最大子数组跨越了中点
跨越中点的情况单独取出进行判断，code如下：(由于不知道如何对于T实现+,因此未采用泛型。)
static List<int> MaxCrossingSubarray(List<int> array,int low,int mid,int high ) { int sum=0; int leftsum = array[mid],rightsum=array[mid+1]; //用于记录左右两边最大子和 int maxleft = mid,maxright=mid+1; //记录最大和时的下标 for(int i=mid;i>=low;i--) //左边最大和(必须从mid开始) { sum+=array[i]; if(sum>leftsum) { leftsum = sum; maxleft = i; } } sum = 0; for(int j=mid+1;j<=high;j++) //右边最大值(必须从mid+1开始) { sum += array[j]; if(sum>rightsum) { rightsum = sum; maxright = j; } } List<int> max = new List<int> { maxleft, maxright, rightsum + leftsum }; return max; }
对整体进行递归分解成更小的情况，直到都变为单个，此时单个便无需判断是否是最小子数组
static List<int> MaxSubarray(List<int> array,int low,int high) { int mid; List<int> listleft = new List<int>(); List<int> listright = new List<int>(); List<int> listcross = new List<int>(); if (low == high) return new List<int>{low, high, array[low]}; else { mid = (low + high) / 2; listleft = MaxSubarray(array, low, mid); listright = MaxSubarray(array, mid + 1, high); listcross = MaxCrossingSubarray(array, low, mid, high); if (listleft[2] >= listright[2] && listleft[2] >= listcross[2]) return listleft; else if (listright[2] >= listleft[2] && listright[2] > listcross[2]) return listright; else return listcross; } }
为了便于理清该递归的执行顺序，绘制了如下图形(其中的数字代表执行顺序，最好自行调试看看具体运行的步骤)
---------练习-----------
4.1-2 暴力求解法如下：(主要就是将每一种情况全都试出来后进行比较)
static List<int> MaxSubarray(List<int> array) { List<int> maxsub = new List<int>(); int max=array[0],temp=0; int left=0, right=0; //用于记录最大子数组在元数组中的下标 for(int i=0;i<array.Count;i++) { temp = 0; for(int j=i;j<array.Count;j++) //此处将j从i开始是为了满足全负数时的情况 { temp += array[j]; if (temp > max) { left = i; max = temp; right = j; } } } return new List<int> { left, right, max }; }
4.1-5 线性时间的搜索最大子数组：
核心思想：从左往右，叠加，并记录其中叠加结果最大的，如果叠加到小于0则将其归零，在往后叠加，将叠加结果与之前记录的最大结果进行比较，超过则换！
static int FindMax(List<int> array) { int sum = 0, maxsum = 0, k = Int32.MinValue; for(int i=0;i<array.Count;i++) { sum += array[i]; if (array[i] > k) k = array[i]; if (sum > maxsum) maxsum = sum; else if (sum < 0) //此处为核心 sum = 0; } if (maxsum == 0) //为了满足全负数的情况 return k; return maxsum; }
注：此方法没返回最大子数组在元数组中的下标
4.2 矩阵乘法的Strassen算法
矩阵的乘法：
nxn的矩阵乘法代码如下：
static int[,] MatrixMultiply(int[,] arr1,int[,]arr2,int n) { int[,] arr=new int[n,n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { arr[i, j] = 0; for (int k = 0; k < n; k++) arr[i, j] = arr[i, j] + arr1[i, k] * arr2[k, j]; } return arr; }
其他两种方法：简单的分治算法和Strassen方法此处先省略
4.3 用代入法求解递归式
步骤
1.猜测解得形式
2.用数学归纳法求出解中的常数，并证明解是正确的
4.4 用递归树方法求解递归式
主要在于根据递归式绘出树图，进行分析，对每一层进行叠加获得总的代价，进行一定的“不精确”假设获得一个较好的猜测解！
4.5 用主方法(master theorem)求解递归式★
针对情况： a≥1 and b>1, f(n)是函数
表达式： T(n)=aT(n/b)+f(n)
Step1：计算出logba
Step2：比较f(n)与nlogba
以下分为三种情况（以下c代表存在一个常数）
- f(n)<cnlogba，并且要在多项式意义上的小于，即,f(n)<cnlogba-ε 此时T(n)就取决于nlogba，所以有T(n)=θ(nlogba)
- f(n)>cnlogba, 并且要在多项式意义上的大于，即f(n)>cnlogba+ε,此时T(n)就取决于f(n)，所以有T(n)=θ(f(n))
- f(n)=θ(nlogba)，则此时 T(n)=θ(nlogba*lgn)
若三种情况均不符合，则不能使用主定理！！！
Chapter 4 分治策略