(算法分析习题参考答案第五章.doc
文本预览下载声明
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;
}试分析该算法的时间复杂性。
试用分治算法解最大子段和问题，并分析算法的时间复杂性。
试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。
（提示：令）
解：1）分析按照第一章，列出步数统计表，计算可得
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]的最大子段和为两部分的字段和组成，即；
intMaxSubSum ( 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 s_1 =0;
int left_sum =0;
for ( int i = center ; i = left; i--){
left_sum + = a [ i ];
if( left_sum s1)
s1 = left_sum;
}
int s2 =0;
int right_sum =0;
for ( int i = center +1; i = right ; i++){
right_sum + = a[ i];
if( right_sum s2)
s2 = right_sum;
}
sum = s1 + s2;
if ( sum leftsum)
sum = leftsum;
if ( sum rightsum)
sum = rightsum;
}
return sum;
}
int MaxSum2 (int n){
int a；
returnMaxSubSum ( a, 1, n) ;
} 该算法所需的计算时间T(n)满足典型的分治算法递归分式
T(n)=2T(n/2)+O(n)，分治算法的时间复杂度为O(nlogn)
3）设,则最大子段和为
最大子段和实际就是.
要说明最大子段和具有最优子结构性质，只要找到其前后步骤的迭代关系即可。
若, ；
若，。
因此，计算的动态规划的公式为：
intMaxSum (int* a，int n )
{
int sum = 0, b = 0，j=0;
for( int i=1;i=n;i++)
{ if( b 0)
b = b + a [i];
else
b = a [i];
end{if}
if( b sum)
sum = b;
j=i；
end{if}
}
return sum;
}
自行推导，答案：时间复杂度为O（n）。
动态规划算法的时间复杂度为O（n）（双机调度问题）用两台处理机A和B处理个作业。设第个作业交给机器A处理时所需要的时间是，若由机器B来处理，则所需要的时间是。现在要求每个作业只能由一台机器处理，每台机器都不能同时处理两个作业。设计一个动态规划算法，使得这两台机器处理完这个作业的时间最短（从任何一台机器开工到最后一台机器停工的总的时间）。以下面的例子说明你的算法：
解：（思路一）删除
（思路二）在完成k个作业，设机器A了x时间，机器B时间是
显示全部