程序设计方法与实践-分治法
分而治之
- 一个问题可以分成若干个子问题进行求解（子问题规模最好相同）
- 对子问题进行求解（可以递归进行）
- 然后对子问题的解进行合并
所以分治法的通用步骤可以概括为：分、治、合。
分治法与主定理
这里大家回忆一下，算法效率分析中的主定理法分析递归算法的原则：
这不就是分治法的一种体现吗？也就是将规模为的问题，划分成a个规模为
的子问题，后面跟着的余项
即为”合“的时间复杂度。
归并排序
- 将待排序数组分成两部分：
和
- 分别将两部分递归方式进行排序
- 然后将两部分有序数列合并
伪码描述：
MergeSort(A[0...n-1]){
copy A[0...n/2-1] to B[0...n/2-1]
copy A[n/2...n-1] to C[0...n/2-1]
MergeSort(B[0...n/2-1])
MergeSort(C[0...n/2-1])
Merge(B,C,A)
}看起来好像什么都没干，但却是解决了这个问题。这就是递归函数的魅力，同样它可能会让你忽视时间的效率。 当然这个算法是比较优的啦：
如果使用主定理法去计算该算法的时间复杂度的话，不难发现其时间复杂度为：的。
然后下面给出一个过程详解：
给出数列：
合并过程如下：
大整数乘法
对于位数大于100的十进制或二进制较大整数的乘法，我们先分析一下常规解法：
对于常规的计算方法，取问题规模衡量标准为乘数的位数n，则时间复杂度为，所以当这个乘数较大时，所花费的时间就会增大得比较快，故而希望有一种更优的算法。来解决这个问题。
那么我们试着从分治法的角度去思考一下这道题：
- 首先将两个整数X，Y分别分成两部分，例如：X=1024，分为两部分XL=10，XR=24。
- 若X，Y为二进制数，则
，
- 又因为
- 那么这两个较大整数的乘法就换了一种形式，变成了由2的幂运算，以及乘法和加法组成的运算，而2幂运算是可以在线性时间内完成的（位运算），加法也是线性时间
那么由此我可以写出递归公式：
其中先是将规模为n大整数乘法问题分治成了三个规模为n/2的子问题，子问题同样包含整数乘法，而子问题的解可以通过线性的操作时间合并，得到原问题的解。
而如果使用主定理法则求解一下这个算法的时间复杂度，
可以求得该算法的时间复杂度为，。
快速排序
快速排序是一个经典的体现分治法的算法
- 先选取基准值，根该值做划分
- 递归地进行排序
- 将各个划分将进行合并
快排模板
QuickSort( A[ l,...r ] )
{
s = Partition( A[ l,...r ] ) //分
QuickSort( A[ l,...s-1 ] ) //治
QuickSort( A[ s,...r ] )
}
在讲解快排中的划分之前，我们先回忆一下Lomuto划分方法：
伪码描述：
LomutoPartition(A[l,...r]){
p = A[l];
s = l;
for(int i=l+1; i<=r; i++){
if(A[i]<p){
s=s+1;
swap(A[s],A[i])
}
}
swap(A[l],A[s])
return s
}与Lomuto划分不同的是，快速排序使用的是霍尔划分（HoarePartition）：
- 与LomutoPartition不同的是，HoarePartition是通过两个指针i，j分别从数组的两端进行扫描
- 取基准值p，i从左边遍历，当A[i]>=p时停止
- j从右边开始遍历，当A[j]<=p停止
- 然后swap(A[i],A[j])
这是我们理想的情况，但有可能碰到的一种情况就是i>=j（即两个指针相交了）。
所以针对这些特殊情况，我们需要做特殊处理：
- 首先考虑i>j时，我们先分析一下，i只有碰见A[i]>=p才会停止，而j只有碰见A[j]<=p才会停止，所以请问i，j在这种情况下的位置关系是怎样的？
只有可能是我的划分已经完成了，那么此时我不能swap(A[j],A[i]),而是应该swap(A[j],p)。
- 还有一种更为特殊的情况就是，i=j，同样大家考虑一下不难得出结论，此时只可能A[i]=A[j]=p
所以可以将这两种情况合并，也就是在碰见指针相交的情况的话就直接swap(A[j],p)。
伪码描述：
HoarePartition(A[l,..r]){
i=l; j=r+1;
repeat{
repeat i++ until A[i]>=p
repeat j-- until A[j]<=p
swap(A[i],A[j])
} until i>=j
swap(A[i],A[j]) //撤销指针相交的那次交换
swap(A[l],A[j]) //与基准值做交换
return j //将基准值的正确位置返回
}时间效率分析：
最差情况：
最优（平均）情况：
Strassen矩阵乘法
假定有两个n*n的矩阵A，B，C=AB,则有：
也就是说，对于每一个都需要进行n次乘法，n-1次加法，那么对于n^2个元素来说，时间复杂度就是
。
这样的效率显然难以接受，Strassen通过分治技术，将时间复杂度降低了：
首先将n阶矩阵划分为四个部分，每个部分是n/2阶的矩阵，然后就会有：
这样会进行8次乘法，以及4 次加法，但是不难通过主定理法计算得到这个算法的时间复杂度依然为。
于是前人又开始动脑子了，他将刚才的8次乘法继续优化成了7次乘法：
这样的话递归方程式就可以写成：
此时再通过主定理计算该算法的时间复杂度的话，就会发现时间复杂度由原来的3次方变成了2.81次方。虽然从数字上看起来并没有多么大的变化，但是当输入规模足够大时，节省的时间还是比较客观的。
以上是分治法的部分经典算法，当然还有像最近对问题、凸包问题的分治解法等问题后面会陆续更新。
原文地址：https://blog.csdn.net/MaverickCoder/article/details/143584460
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！