2021年算法优化策略.ppt

*
算法设计策略的比较与选择
算法优化策略
*
*
最大子段和问题
给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为０。依此定义，所求的最优值为:
例如:
A=(-2，11，-4，13，-5，-2)
最大子段和为
算法优化策略
*
*
简单算法
public static int maxSum()
{
int n=-1;
int sum=0;
for (int i=1;i<=n;i++) {
int thissum=0;
for (int j=i;j<=n;j++) {
for (int k=i;k<=j;k++) thissum+=a[k];
if (thissum>sum) {
sum=thissum;
besti=i;
bestj=j;
}
}
return sum;
}
thissum+=a[j];
注意到 ，则可将算法中的最后一个for循环省去，避免重复计算只需要O(n2)的计算时间。
算法优化策略
*
*
分治算法
如果将所给的序列a[1:n]分为长度相等的2段a[1:n/2]和a[n/2+1:n]，分别求出这2段的最大子段和，则a[1:n]的最大子段和有3种情况。
(1)a[1:n]的最大子段和与a[1:n/2]最大子段和相同；
(2)a[1:n]的最大子段和与a[n/2+1:n]最大子段和相同；
(3)a[1:n]的最大子段和为 ，且1≤i≤n/2，n/2+1≤j≤n。
对于情形(3)。容易看出，a[n/2]与a[n/2+1]在最优子序列中。因此，可以在a[1:n/2]中计算出 ，并在a[n/2+1:n]中计算出 。则s1＋s2即为出现情形(3)时的最优值。据此可设计出求最大子段和的分治算法。
复杂度分析
T(n)=O(nlogn)
算法优化策略
*
*
动态规划算法
记 ，1 j n，则所求的最大子段和为
当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得计算b[j]的动态规划递归式
b[j]=max{b[j-1]+a[j]，a[j]}， 1 j n
算法显然需要O(n)计算时间和O(n)空间。
public static int maxSum()
{
int n=-1;
int sum=0,
b=0;
for (int i=1;i<=n;i++) {
if (b>0) b+=a[i];
else b=a[i];
if (b>sum)sum=b;
}
return sum;
}
算法优化策略
*
*
最大子矩阵和问题
记
最大子矩阵和问题的最优值为
由于
其中，
设 ，则
给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其各元素之和为最大。
由于解最大子段和问题的动态规划算法需要时间O(n)，故算法的双重for循环需要计算时间O(m2n)。
算法优化策略
*
*
最大m子段和问题
给定由n个整数(可能为负整数)组成的序列a1,a2,…,an,以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和达到最大。
设b(i，j)表示数组a的前j项中i个子段和的最大值，且第i个子段含a[j](1 i m，i j n)。则所求的最优值显然为
与最大子段和问题类似地，计算b(i，j)的递归式为
初始时，b(0，j)=0，(1 j n);b(i，0)=0，(1 i m)。
优化：注意到在上述算法中，计算b[i][j]时只用到数组b的第i-1行和第i行的值。因而算法中只要存储数组b的当前行，不必存储整个数组。另一方面，b(i-1，t)的值可以在计算第i-1行时预先计算并保存起来。计算第i行的值时不必重新计算，节省了计算时间和空间。
算法优化策略
*
*
动态规划加速原理
四边形不等式
算