算法导论_第四章_分治策略
分治的三个步骤：
分解：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
解决：递归的求解出子问题。如果子问题足够小，则停止递归，直接求解
合并：将子问题的解组合成原问题的解。
最大子数组问题：
给定数组A，寻找A的和最大的非空连续子数组。
可以利用暴力求解，其为Ω(n^2)
这里利用分治法解决，其时间复杂度为Θ(n*lg(n))：
既然是分治，即肯定要把数组分开，其有三种情况：
1.完全位于左边的数组
2.完全位于右边的数组
3.跨越了中点
下面给出具体代码，已经加上详细注释：
/*************************************************************************
> File Name: FIND_MAXIMUM_SUBARRAY.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月24日 星期五 08时53分20秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
void FIND_MAX_CROSSING_SUBARRAY(int A[],int low,int mid ,int high);
void FIND_MAXIMUM_SUBARRAY(int A[],int low,int high);
int _low,_high,_sum;
int main(int argc,char *argv[])
{
int A[1000]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
FIND_MAXIMUM_SUBARRAY(A,0,15);
printf("%d %d %d",_low,_high,_sum);
return 0;
}
/***********************************
* 函数功能：得到最大数组
* 参数：
* 1.数组
* 2.数组最左边坐标
* 3.数组最右边坐标
* *********************************/
void FIND_MAXIMUM_SUBARRAY(int A[],int low,int high)
{
int left_low,left_high,right_low,right_high;
int left_sum,right_sum;
int cross_low,cross_high,cross_sum;
if(low==high)
{
_low=low;
_high=high;
_sum=A[low];
return;
}
int mid=(low+high)/2;//分割点
FIND_MAXIMUM_SUBARRAY(A,low,mid);//找到第一种情况的最大数组
left_low =_low;
left_high=_high;
left_sum =_sum;
FIND_MAXIMUM_SUBARRAY(A,mid+1,high);//找到第二种情况的最大数组
right_sum=_sum;
right_high=_high;
right_low=_low;
FIND_MAX_CROSSING_SUBARRAY(A,low,mid,high);//找到第三种情况的最大数组
cross_low=_low;
cross_high=_high;
cross_sum=_sum;
//比较三种情况，哪种情况较优返回哪种情况
if(left_sum>=right_sum&&left_sum>=cross_sum)
{
_low=left_low;
_high=left_high;
_sum=left_sum;
}
else if(right_sum>=left_sum&&right_sum>=cross_sum)
{
_low =right_low;
_high=right_high;
_sum =right_sum;
}
else
{
_low =cross_low;
_high=cross_high;
_sum =cross_sum;
}
return ;
}
/**********************************
* 函数功能：寻找跨越中点的最大子数组
* 参数：
* 1.数组
* 2.数组最左边
* 3.数组中点
* 4.数组最右边
* *****************************/
void FIND_MAX_CROSSING_SUBARRAY(int A[],int low,int mid ,int high)
{
int left_sum=-INF;//左边的最大数组，从中点开始
int right_sum=-INF;//右边的最大数组，从中点开始
int sum=0;
int max_left,max_right;//最大数组左边坐标，最大数组右边坐标
for(int i=mid;i>=low;i--)//左边最大数组求解
{
sum+=A[i];
if(sum>left_sum)
{
left_sum=sum;
max_left=i;
}
}
sum=0;
for(int i=mid+1;i<=high;i++)//右边最大数组求解
{
sum+=A[i];
if(sum>right_sum)
{
right_sum=sum;
max_right=i;
}
}
//利用全局变量，代替return
_low=max_left;
_high=max_right;
_sum=right_sum+left_sum;
return ;
}
我们来分析一下其时间复杂度：
可以看出，其把一个原问题分解为两个子问题，所以2T(n/2)
又其中的寻找 跨越中点的最大子数组的时间复杂度为Θ(n^2)
所以T(n)=2*T(n/2)+Θ(n^2)
所以根据上几节的知识，其时间复杂度为Θ(n*lg(n))
下面再来介绍一个例子：
矩阵乘法的Strassen算法
对于一个矩阵乘法其可以同过一下一个简单方法实现：
/*************************************************************************
> File Name: Strassen.cpp
> Author:chudongfang
> Mail:1149669942@qq.com
> Created Time: 2016年06月27日 星期一 09时55分03秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
void SQUARE_MATRIX_MULTIPLY(int A[][100],int B[][100],int C[][100],int n);
int main(int argc,char *argv[])
{
int A[100][100];
int B[100][100];
int C[100][100];
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&A[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&B[i][j]);
SQUARE_MATRIX_MULTIPLY(A,B,C,n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
printf("%4d",C[i][j]);
printf("\n");
}
return 0;
}
void SQUARE_MATRIX_MULTIPLY(int A[][100],int B[][100],int C[][100],int n)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
C[i][j]=0;
for(int k=1;k<=n;k++)
{
C[i][j]+=A[i][k]+B[k][j];
}
}
}
}
其时间复杂度为
Θ(n^3);
下面采用分治方法计算：
由于该数组分治操作相对复杂，这里先给出伪代码，以后有时间再给出相应代码：
跟据代码可以看出其递归式为：
T(n)=8*(n/2)+Θ(n^2)
则根据主方法计算出其时间复杂度为Θ(n^3);
所以其分治并不能降低其时间复杂度
下面介绍一个可以降低其时间复杂度的方法
Strassen方法
其算法核心思想是利用空间换换时间，利用加减法减少递归次数，使其递归次数由8次降低到了7次。减少一次的代价
可能是额外的几次n/2*n/2矩阵的加法，但只是常数次。
下面给出其伪代码：
其根据加减法进行一些转换，最后的结果还是不变的。
这里给出书上的解释：
求解递归式
这里重点为主方法，其运用最广
1.代入法求解递归式
思想：
(1)猜测解的形式
(2)用数学归纳法，求出解中的常数，并证明解是正确的。
在这里，先跟据情况猜测出解的大概情况，然后代入，根据前面的对渐进符号的定义最终求出常数符合条件，则其等
式成立。
2.用递归树求解递归式
在递归树中，每个节点表示一个单一的子问题的代价，子问题对应某次递归函数调用。我们将树中每层代价求和，得
到每层代价，然后将所有层的代价求和，得到所有层次的递归调用的总代价。
3.利用主方法求解递归式
主方法为如下形式的递归式提供了一种“菜谱”式的求解方法
T(n)=a*T(n/b)+f(n)
其中a>=1和b>1是常数，f(n)是渐进正函数。
主定理
令a>=1和b>1是常数，f(n)是一个函数，T(n)是定义在非负整数上的递归式：
T(n)=a*T(n/b)+f(n)
其中我们将n/b解释为向上取整或向下取整，那么T(n)有如下渐进界：
1.若对某个常数e>0有f(n)=O(n^ log(b) a-e)则，T(n)=Θ(n^log(b)a)
2.若f(n)=Θ(n^log(b)a)则T(n)=Θ(n^log(b)a*lg(n))
3.若对某个e>0有f(n)=Ω(n^(log(b)a-e))其对某个常数c<1和所有足够大的n有a*f(n/b)
<=c*f(n),则T(n)=Θ(f(n))
简明一点，就是拿f(n)和函数n^(log(b)a)比较，
如果n^(log(b)a)更大，就满足情况1其解为：T(n)=Θ(n^log(b)a)
若函数f(n)更大，如情况3则解为：T(n)=Θ(f(n))
如果两个函数大小相当就为情况2,其解为：
T(n)=Θ(n^log(b)a*lg(n))
以上比价都必须满足多项式大于或小于
这里举几个例子：
a=9 b=3;
f(n)=n
应用于情况1,所以其为Θ(n^2)
a=1 b=3/2 f(n)=1
应用于情况2所以其为Θ(lgn)
a=3 b=4 f(n)=n*lg(n)
应用于情况3所以其为Θ(n*lg(n))
a=2 b=2 f(n)= Θ(n)
应用于情况2所以其为Θ(n*lg(n))
a=8 b=2 f(n)= Θ(n^2)
应用于情况1所以其为Θ(n^3)
a=7 b=2 f(n)= Θ(n^2)
应用于情况1所以其为Θ(n^lg(7))
总结一下，其用法，比较f(n)和n^(log(b)a),
如果不相同，则取其较大的那个，
如果相同 ，则取log(b)a再乘上lg(n)
下面还有对主定理的证明内容，由于我们先只是会运用主定理，这里先不证，留到以后
进阶时在进行分析。