《编程珠玑》第 8 章──算法设计技术

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

问题以及算法

下面将讨论用四种不同难度的算法来解决同一个问题。Leetcode 上也有原题 Maximum Subarray

输入是 n 个浮点数的向量 x,输出是输入向量的任何连续子向量中的最大和。

暴力法

直接求出所有子串的和,然后比较大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double al1(vector<double> input) {
double max_so_far = 0;
auto n = (int) input.size();
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
double tmp_sum = 0;
for (int k = i; k <= j; ++k) {
tmp_sum += input[k];
}
max_so_far = max(max_so_far, tmp_sum);
}
}
return max_so_far;
}

平方算法

这里平方是指时间复杂度为 n 的平方级别。

平方算法(一)

利用 [i, j-1] 来求 [i, j],减少了重复计算。

1
2
3
4
5
6
7
8
9
10
11
12
double al21(vector<double> input) {
double max_so_far = 0;
auto n = (int) input.size();
for (int i = 0; i < n; ++i) {
double tmp_sum = 0;
for (int j = i; j < n; ++j) {
tmp_sum += input[j];
max_so_far = max(max_so_far, tmp_sum);
}
}
return max_so_far;
}
平方算法(二)

把 [0, i] 的保存下来存入数组 cumarr 中,求子串的和只需要找到两个 cumarr 相减即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
double al22(const vector<double> &input) {
double max_so_far = 0;
auto n = (int) input.size();
vector<double> cumarr(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cumarr[i] = cumarr[i - 1] + input[i];
}
for (int j = 0; j < n; ++j) {
for (int i = j; i < n; ++i) {
double tmp_sum = cumarr[i] - cumarr[j];
max_so_far = max(max_so_far, tmp_sum);
}
}
return max_so_far;
}

分治算法

把输入分成两半,然后对左边和右边求出其子串的最大,然后再求跨越分界线的子串的最大,最后对三个最大值取最大,得到原来输入的向量的最大子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
double al3(const vector<double> &input, int left, int right) {
if (left > right) {
return 0;
} else if (left == right) {
return max(input[left], 0.0);
}
int m = left + (right - left) / 2;
double left_max(0.0), tmp_max(0.0), right_max(0.0);
for (int i = m; i >= left; --i) {
tmp_max += input[i];
left_max = max(left_max, tmp_max);
}
tmp_max = 0.0;
for (int j = m + 1; j <= right; ++j) {
tmp_max += input[j];
right_max = max(right_max, tmp_max);
}
return max(max(left_max + right_max, al3(input, left, m)), al3(input, m + 1, right));
}

double al3(const vector<double> &input) {
int left = 0;
auto right = (int) (input.size() - 1);
return al3(input, left, right);
}

扫描算法

其实就是动态规划,以 i-1 为结尾的子串的最大的和为 dp[i-1],如果 dp[i-1] 小于 0,那么它对后面的子串的求和没什么意义,那么重新开始计时。否则用 dp[i-1] 加上 input[i] 来对比目前最大的和,如果比目前最大的和还更大,那么就更新最大的和。

1
2
3
4
5
6
7
8
9
double al4(const vector<double> &input) {
double max_so_far = 0;
double tmp_max = 0;
for (auto &it: input) {
tmp_max = max(tmp_max + it, 0.0);
max_so_far = max(max_so_far, tmp_max);
}
return max_so_far;
}

原理

  1. 保存状态,避免重复计算。
  2. 将信息预处理到数据结构中。
  3. 分治算法。
  4. 扫描算法。
  5. 累加数组。
  6. 下界。

习题

4. 如果输入数组中的每个元素都是从区间 [-1, 1] 中均匀选出的随机实数,那么最大子向量的期望值是多少?

这个题目想了很久,而且在网上也没有可以参考的答案。

5. 为了简单起见,我们允许算法 al22 访问 cumarr[-1]。如果使用 C 语言处理该问题?

令 cumarr 指向 realarray[1],那么 cumarr[-1] 就指向 realarray[0]。

1
2
3
4
5
6
int main() {
int realarray[] = {1, 2, 3, 4};
int *cumarr = &realarray[1];
cout << cumarr[-1] << endl;
return 0;
}

8

修改算法 3(分治算法),使其在最坏情况下具有线性运行时间。

在求跨界的最大子串时,把左右边界记录下来,省去了左右两边求子串又把它们加入计算中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
double al3(const vector<double> &input, int left, int right) {
if (left > right) {
return 0;
} else if (left == right) {
return max(input[left], 0.0);
}
int m = left + (right - left) / 2;
double left_max(0.0), tmp_max(0.0), right_max(0.0);
int left_flag(m), right_flag(m + 1);
for (int i = m; i >= left; --i) {
tmp_max += input[i];
if (tmp_max > left_max) {
left_max = tmp_max;
left_flag = i;
}
}
tmp_max = 0.0;
for (int j = m + 1; j <= right; ++j) {
tmp_max += input[j];
if (tmp_max > right_max) {
right_max = tmp_max;
right_flag = j;
}
}
return max(max(left_max + right_max, al3(input, left, left_flag)), al3(input, right_flag, right));
}

double al3(const vector<double> &input) {
int left = 0;
auto right = (int) (input.size() - 1);
return al3(input, left, right);
}

9. 我们将负数数组的最大子向量的和定义为 0,即空向量的总和。假设我们重新定义,将最大子向量的和定义为最大元素的值,那么,应该如何修改各个程序呢?

max_so_far 修改为最小值。

1
double max_so_far = - std::numeric_limits<double>::max();

这样的话肯定有一个数的值会大于 max_so_far

10. 假设我们想要查找的是综合最接近 0 的子向量,而不是具有最大总和的子向量。你能设计出的最有效的算法是什么?可以应用哪些算法设计技术?如果我们希望查找总和最接近某一个给定实数 t 的子向量,结果又如何?

初始化累加数组 cum,使得 cum[i] = x[0] + ... + x[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void min_delta(const vector<double> &input, double t) {
auto n = (int) input.size();
vector<double> cum(static_cast<unsigned long>(n + 1), 0);
for (int i = 1; i <= n; ++i) {
cum[i] = cum[i - 1] + input[i - 1];
}
double tmp = fabs(t - cum[0]);
int left(0), right(0);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n + 1; ++j) {
double sum_delta = cum[j] - cum[i];
if (fabs(t - sum_delta) < tmp) {
tmp = fabs(t - sum_delta);
left = i;
right = j;
}
}
}
cout << "left: " << left << "\n";
cout << "right: " << right - 1 << "\n";
cout << "delta: " << tmp << endl;
}

11. 收费公路由 n 个收费站之间的 n-1 段公路组成,每一段公路都有相关的使用费。如果在O(n)O(n) 时间内驶过两个收费站,并且仅使用一个费用数组;或在固定时间内试过两个收费站,并且使用一个具有O(n2)O(n^2) 个表项的表,那么给出两站之间的行驶费很容易。请描述一个数组结构,该结构仅需要O(n)O(n) 的空间,却可以在固定的时间内完成任意路段的费用计算。

使用类似上一题中的 cum 数组即可。

12. 将数组 x[0…n-1] 初始化为全 0 后,执行下面 n 个运算:

1
2
for i in [l, u]
x[i] += v

其中 l、u 和 v 为每次运算的参数(l 和 u 为满足0lu<n0 \leq l \leq u < n 的整数,v 为实数)。完成这 n 次运算后,x[0…n-1] 中的各个值将按顺序排列。上面刚刚描述的方法需要O(n2)O\left(n^2\right) 的运行时间。你能给出一个更快的算法么?

这个题目有点绕,解释一下。就是说某个东西落到某个区间,然后区间内每个数字都加上该值,那么一共要执行 n 次这样的动作。每次动作中,如果不优化,那么遍历来给区间内每个数字加上 v,时间复杂度就是O(n)O\left(n\right),总共的时间复杂度就是O(n2)O\left(n^2\right)。如果要将时间复杂度降低的话,需要增大空间复杂度。

1
2
3
4
cum[u] += v
cum[l-1] -=v
for (i = n-1; i >= 0; --i)
x[i] = x[i+1] + cum[i]

举个例子,初始化后 x 数组为 [0, 0, 0, 0, 0]。我们想给1index31 \leq \text{index} \leq 3 该区间内所有的数字都加 1。那么我们只需要让:

1
2
cum[3] = 1
cum[0] = -1

然后从后往前遍历:

1
2
3
4
5
x[4] = x[4] = 0;
x[3] = x[4] + cum[3] = 1;
x[2] = x[3] + cum[2] = 1 + 0 = 1;
x[1] = x[2] + cum[1] = 1 + 0 = 1;
x[0] = x[1] + cum[0] = 1 - 1 = 0;

13. 在最大子数组问题中,给定n×nn\times n 的实数数组,我们需要求出矩阵子数组的最大总和。该问题的复杂度如何?

在一个维度上使用扫描算法,但是另外一个维度必须是平方算法了,因为平方算法才遍历所有组合子串。所以时间复杂度是O(n3)O\left(n^3\right)

14. 给定整数 m、n 和实数向量 x[n],请找出使总和x[i]++x[i+m]x[i]+\dots+x[i+m] 最接近 0 的整数 i(0i<nm0\leq i <n-m)。

遍历一遍,用绝对值来决策 min_so_far 即可。

15.T(1)=0T\left(1\right)=0 且 n 为 2 的幂时,递推公式T(n)=2T(n2)+cnT\left(n\right)=2T\left(\frac{n}{2}\right) + cn 的解是什么?请用数学归纳法证明你的结果。如果T(1)=cT\left(1\right)=c ,结果又怎样?

递推即可。前者的答案为T(n)=log2n×cnT\left( n \right) = \log_2n \times cn。后者的答案是T(n)=n×c+log2n×cnT\left( n \right) = n\times c + \log_2n \times cn