编程珠玑第八章探讨

这一章节给出的问题让人从直觉上判断就是动态规划。不过,本章的分治算法也非常的巧妙,他们的优势都是避免了一些重复计算。动态规划本质也就是对于穷举法的优化。作者在指出这些算法时,由简单到困难的描述了复杂的算法有时能让效率大幅提高。对于O(n^2)的暴力来说,O(nlogn)的分治算法的确印证了这一点。但是O(n)的动态规划却不算复杂,相反,比起暴力他还来的简单些。而除了这道特定的题目以外,其他凡是用到DP的地方都能够反映出动态规划的简洁美,不失为一种优美且高效精巧的解决方案。

复杂深奥的算法有时可以极大地提高程序性能

问题探讨

书中围绕着最大连续子串和分析了暴力,分治和DP的不同解决方案。这个问题是提出者对于二维模型的简化版本。我们可以只管判断,因为我们至少要扫描完整个子串才能断定最大的子串,所以这个算法的时间复杂度下界至少不小于O(n):

先给出O(nlogn)的改进分治算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maxsum(int left, int right){
if (left > right) return 0;
if (left == right) return MAX(num[left], 0);
int mid = (left + right) / 2;
lmax = sum = 0;
lrec = mid;
rrec = mid + 1;
for(int i = mid; i >= left; i--){
sum += num[i];
if(sum > lmax){
lmax = sum;
lrec = i;
}
}
rmax = sum = 0;
for(int i = mid + 1; i <= right; i++){
sum += num[i];
if(sum > rmax){
rmax = sum;
rrec = i;
}
}
return MAX(MAX(lmax + rmax, maxsum(left, lrec)), maxsum(rrec, right));
}

然后是DP:

1
2
3
4
for(int i = 1; i <= n; i++){
temp = MAX(temp + num[i], 0);
ans = MAX(temp, ans);
}

4.试验表明,不是太容易看出来,取决于串的长度。

10.这道题目其实需要对判别条件做出理解,原本是MAX,我们要把这个MAX改为最接近0。但是其实我们可以得到任一区间的和,用累加数组num,那么从i到j的和就是num[j] - num[i - 1],我们要求的就是num[j] - num[i - 1]最小。显然两个值越接近,他们的差就越小。直接找需要O(n^2)的复杂度,所以我们排个序,然后遍历找到最小的区间,O(nlogn)。

13.问题要求是求出矩形的数组,势必需要对行或者列进行遍历扫描。我们先划定一个维度,比如行。我们每次无重复的处理i到j行,所有的组合需要n^2的复杂度。然后每一对行组合,比如i1到j1行已经界定后,我们可以把它看成是一维的,用动态规划去处理。总的复杂度O(n^2m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 1; i <= n; i++){
memset(col, 0, sizeof(col));
for(int j = i; j <= n; j++){
for(int k = 1; k <= m; k++)
col[k] += num[j][k];
temp = 0;
tot = 0;
for(int k = 1; k <= m; k++){
temp = MAX(temp + col[k], 0);
tot = MAX(tot, temp);
}
ans = MAX(ans, tot);
}
}
  1. T(1) = 0时,T(n) = 2nc。T(1) = c时,T(n) = nlognc。这里面有一定的启示,刚好印证着分治算法和动态规划的时间复杂度关系。

摘录

本章故事中的这些算法给出了几个重要的算法设计技术。

  • 保存状态,避免重复计算。算法2和算法4使用了简单的动态规划。通过使用一些空间来保存中间计算结果,我们避免了花时间对其重复计算。
  • 将信息预处理至数据结构中。算法2b中得cumarr结构允许对子向量中的总和进行快速计算。
  • 分治算法。算法3使用了简单地分治算法形式;有关算法设计的教科书介绍了更高级的分治算法形式。
  • 扫描算法。与数组相关的问题经常可以通过思考“如何将x[0..i-1]的解扩展为x[0..i]的解”来解决。算法4通过同时存储已有的答案和一些辅助数据来计算新答案。
  • 累积。算法2b使用了一个累积表,表中第i个元素的值为x中前i个值的总和;这一类表常用于处理有范围限制的问题。例如,业务分析师要确定3月份到10月份的销售额,可以从10月份的本年迄今销售额中减去2月份的销售额。
  • 下界。只有在确定了自己的算法是所有可能算法中最佳的算法以后,算法设计师才可能踏踏实实地睡个好觉。为此,他们必须证明某个相匹配的下界。对问题线性下界的讨论见习题6,更复杂的下界证明可能会十分困难。