算法第五章作业.docx
文本预览下载声明
算法第五章作业
张杰 2013E8018661133
1．最大子段和问题：给定整数序列 ，求该序列形如的子段和的最大值：
已知一个简单算法如下：
int Maxsum(int n,int a,int best i,int bestj){
int sum = 0;
for(int i=1;i=n;i++){
int suma = 0;
for(int j=i;j=n;j++){
suma + = a[j];
if(suma sum){
sum = suma;
besti = i;
bestj = j;
}
}
}
return sum;
}试分析该算法的时间复杂性。
试用分治算法解最大子段和问题，并分析算法的时间复杂性。
试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。
（提示：令）
解
该算法的时间复杂性为
2) 分治算法：将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有三种可能：
①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；
②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；
③a[1:n]的最大子段和为两部分的字段和组成，即；
int MaxSubSum ( int *a, int left , int right){
int sum =0;
if( left==right)
sum = a[left] 0? a[ left]:0 ;
else
{
int center = ( left + right) /2;
int leftsum =MaxSubSum ( a, left , center) ;
int rightsum =MaxSubSum ( a, center +1, right) ;
int left_sum =0;
for ( int i = center ; i = left; i--){
left_sum + = a [ i ];
if( left_sum 0)
left_sum=0;
}
int right_sum =0;
for ( int i = center +1; i = right ; i++){
right_sum + = a[ i];
if( right_sum 0)
right_sum=0;
}
sum = left_sum + right_sum;
if ( sum leftsum)
sum = leftsum;
if ( sum rightsum)
sum = rightsum;
}
return sum;
}
int MaxSum2 (int n){
int a[]；
return MaxSubSum ( a, 1, n) ;
}
该算法所需的计算时间T(n)满足典型的分治算法递归分式
T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)
3) 设,即
那么问题的答案就在.
而对于b(j)和b(j-1)，二者有如下关系
所以有最优子结构性质，动态规划的公式为
int MaxSum (int* a，int n )
{
int b[n]=0;
int sum = 0;
b[1]=a[1];
for( int i=2;i=n;i++)
{ if( b[i-1] 0)
b[i] = b[i-1] + a [i];
else
b [i]= a [i];
if( b [i] sum)
sum = b[i];
}
return sum;
}
容易得到时间复杂度为O（n）
2. （双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：
解：设为完成前i个作业，系统所需的最短处理时间，
表示在完成前i个作业所需时间最少的策略下，分配到A机器上处理的作业的时间，
表示在完成前i个作业所需时间最少的策略下，分配到B机器上
显示全部