清华大学出版社 TSINGHUA UNIVERSITY PRESS 第10章算法优化策略
1 第10章 算法优化策略
清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法设计策略的比较与选择 2
2 算法设计策略的比较与选择
最大子段和问题 RESS 给定由n个整数(可能为负整数)组成的序列a1,a2 a n 求该序列形如Σa的子段和的最大值。当所有整数均为 负整数时定义其最大子段和为0。依此定义,所求的 最优值为 max. max 1≤i≤j≤ 例如: A=(-2,11,-4,13,-5,-2) 最大子段和为∑ak=20
3 最大子段和问题 给定由n个整数(可能为负整数)组成的序列a1 ,a2 ,…,an , 求该序列形如 的子段和的最大值。当所有整数均为 负整数时定义其最大子段和为０。依此定义，所求的 最优值为: 例如: A=(-2，11，-4，13，-5，-2) 最大子段和为 = j k i k a = j k i k i j n a 1 max 0, max 20 4 2 = k = ak
清华大学出版社 public static int maxSumO 简单算法 RS/Y PRESS int n=a length-1 int sum=0 for(int i=1; i<=n; i ++)t int thissum=o for(intj=ij<≡nj+){ thissum+=aDl IT(thissum>sumi sum=thissum besti=i best= 注意到Σa=a+Σ4,则可将算法 中的最启一个fo循环省去,避 return sum 免重复计算只需要O(n2)的计算 时间。 4
4 public static int maxSum() 简单算法 { int n=a.length-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 )的计算 时间。 − = = = + j 1 k i k j k i ak aj a
清华大学出版社 分治算法 RSITY PRESS 如果将所给的序列a[1:n分为长度相等的2段a[1n/2]和 a[n/2+1n],分别求出这2段的最大子段和,则a1n的 最大乙几和2种娃 (1)复杂度分析 O ≤C (2) T(n)= 27(n/2)+O(n)n>c (3) T(n=o(nlogn) sano 对 子序 列中。因此,可以在a1n/2中计算出 ,并在 a[n/2+1n中计算出 。则ss2即为出现 情形(3)时的最优值。据龀可姗计出求最大子段和的分 治算法
5 分治算法 如果将所给的序列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)时的最优值。据此可设计出求最大子段和的分 治算法。 = j k i k a = = / 2 1 / 2 1 max [ ] n k i i n s a k = + + = i k n n i n s a k / 2 1 / 2 1 2 max [ ] 复杂度分析 T(n)=O(nlogn) n c n c T n O n O T n + = 2 ( / 2) ( ) (1) ( )