算法导论 9 Problems 答案

发表于 2023-01-19 更新于 2023-07-03 分类于算法导论阅读次数： 304 本文字数： 9.8k 阅读时长 ≈ 9 分钟

9-1

a

先直接进行排序，需要 $O (n \lg n)$ 的运行时间，然后直接返回最后 $i$ 个数。这个算法的总体时间复杂度为 $O (n \lg n)$ 。

b

使用算法 BUILD-MAX-HEAP 对整个数组进行建堆，需要 $O (n)$ 的运行时间。然后使用 $i$ 次算法 EXTRACT-MAX 分别弹出当前最大值，每次使用的运行时间为 $O (\lg n)$ 。这个算法的总体时间复杂度为 $O (n + i \lg n)$ 。

c

先用算法 SELECT 求出第 $n - i + 1$ 小的数（也就是第 $i$ 大的数），需要 $O (n)$ 的运行时间。然后直接对后面 $i$ 个元素进行排序后直接返回，这个过程需要 $O (i \lg i)$ 的运行时间。这个算法的总体时间复杂度为 $O (n + i \lg i)$ 。

9-2

a

如果第 3 行代码返回的 $q$ 恰好是下标最大值 $r$ ，那么 $k = r - p + 1$ ，由于 $i \leq r - p + 1$ 是恒成立的，因此必定进入第 6 行的分支。此时的递归调用相当于是 SIMPLER-RANDOMIZED-SELECT(A, p, r, i)，这没有对区间做任何的缩减。因此，在最坏情况下相当于进行无限递归，程序不会终止。

b

算法 SIMPLER-RANDOMIZED-SELECT 的第 3 行相当于从区间 $A [p : r]$ 中均匀随机选择一个数作为支点，最终划分完成后（假设这是第 $i$ 小的数），在第 6-7 行中选择一个分支继续进行查找。

假设在最坏情况下，每次递归查找的都是大小比较大的那个区间，那么假设 $T (n)$ 为运行时间，有

$T (n) \leq \frac{1}{n} \cdot \sum_{i = 1}^{n} T (max {i, n - i}) + O (n)$

整理一下，可以写成

$T (n) \leq \frac{1}{n - 1} \cdot \sum_{i = 1}^{n - 1} T (max {i, n - i}) + O (n)$

考虑消去 $max$ 。如果 $n - 1$ 是奇数，那么项 $T (n / 2)$ 会出现 $1$ 次，项 $T (n / 2 + 1), T (n / 2 + 2), \dots, T (n - 1)$ 都会出现 $2$ 次；如果 $n - 1$ 是偶数，那么项 $T ((n + 1) / 2), T ((n + 1) / 2 + 1), \dots, T (n - 1)$ 都会出现 $2$ 次。

因此为了避免分别讨论，缩放时， $n - 1$ 为奇数的情况再添加多一个项，那么可以写出

$T (n) \leq \frac{2}{n - 1} \cdot \sum_{i = ⌈ n / 2 ⌉}^{n - 1} T (i) + O (n)$

假设 $T (n) \leq c n$ ，那么有

$\begin{aligned} T (n) & \leq \frac{2}{n - 1} \cdot \sum_{i = ⌈ n / 2 ⌉}^{n - 1} T (i) + O (n) \\ \leq \frac{2 c}{n - 1} \cdot \frac{(⌈ n / 2 ⌉ + n - 1) (n - ⌈ n / 2 ⌉)}{2} + O (n) \\ = c \cdot \frac{(⌈ n / 2 ⌉ + n - 1) (n - ⌈ n / 2 ⌉)}{n - 1} + O (n) \\ \leq c \cdot \frac{(n / 2 + 1 + n - 1) (n - n / 2 - 1)}{n - 1} + O (n) \\ = \frac{3 c n (n - 2)}{4 (n - 1)} + O (n) \\ \leq \frac{3 c n (n - 2)}{4 (n - 2)} + O (n) \\ = \frac{3}{4} c n + O (n) \\ \leq c n & (A) \end{aligned}$

其中步骤 $(A)$ 使用了如下假设： $c$ 足够大，使得 $\frac{c n}{4}$ 的渐进增长快于 $O (n)$ 。

因此有 $T (n) = O (n)$ 。

9-3

这里的中位数默认是第 $⌈ \frac{n}{2} ⌉$ 小的数。

需要注意的是，通过哈希表，我们可以把相同的 $x$ 合并成一个，并且其权值进行相加。只要哈希表的性能足够优秀，那么这个预处理需要 $Θ (n)$ 的时间复杂度完成。因此在接下来的过程中，我们默认 $x$ 是两两不同的。

a

小于中位数的数有 $⌈ \frac{n}{2} ⌉ - 1$ 个。那么这些数的权值之和为 $\frac{1}{n} (⌈ \frac{n}{2} ⌉ - 1)$ 。可以发现，当 $n$ 为偶数时，权值和为 $\frac{1}{2} - \frac{1}{n}$ ，当 $n$ 为奇数时，权值和为 $\frac{n - 1}{2 n}$ 。无论那种情况都小于 $\frac{1}{2}$ 。

大于中位数的数有 $n - ⌈ \frac{n}{2} ⌉ = ⌊ \frac{n}{2} ⌋$ 个。那么这些数的权值之和为 $\frac{1}{n} ⌊ \frac{n}{2} ⌋$ 。无论 $n$ 取何值，权值之和总小于等于 $\frac{1}{2}$ 。

因此， ${x}$ 的普通中位数就是这种特殊情况下的带权中位数。

b

算法 GET-WEIGHTED-MEDIAN1 给出了求取一个带权中位数的算法。其中排序算法的时间复杂度假设为 $O (n \lg n)$ 。

// 数组A中的每一个元素都有两个属性，分别为x和w，x表示数值，w表示权重。
GET-WEIGHTED-MEDIAN1(A, n)
  sort A[1 : n] by key x
  s = 0
  for i = 1 to n
    s = s + A[i].w
    if s >= 0.5
      return A[i].x
  return NIL

直接排完序后，从小到大将所有数的权值逐渐相加，将第一个大于等于 0.5 的数直接返回。如果输入是合法的（权值之和为 $1$ ），那么第 7 行的代码 return NIL 不会被运行到。

c

整个算法通过如下伪代码给出给出。子程序 RANDOMIZED-PARTITION-WEIGHTED 和 PARTITION-WEIGHTED 与原版的行为基本相同，多统计了一个权值之和。它们的时间复杂度为 $Θ (n)$ 。

算法 MEDIAN-WEIGHT 的时间复杂度 $T (n)$ 的分析过程和 9-2-b 完全一致，为 $T (n) = O (n)$ 。第 5 行代码第一次对整个数组进行了一次划分，因此有 $T (n) = Ω (n)$ 。那么整个算法的时间复杂度为 $T (n) = Θ (n)$ 。

// PARTITION-WEIGHTED返回两个值，一个是划分后这个数的下标q，一个是A[p : q]中所有数的权值之和。
PARTITION-WEIGHTED(A, p, r)
  s = 0
  x = A[r].x // the pivot
  i = p – 1 // highest index into the low side
  for j = p to r – 1 // process each element other than the pivot
    if A[j].x < x // does this element belong on the low side?
      i = i + 1 // index of a new slot in the low side
      exchange A[i] with A[j] // put this element there
  exchange A[i + 1] with A[r] // pivot goes just to the right of the low side
  return i + 1, s + A[i + 1].w

RANDOMIZED-PARTITION-WEIGHTED(A, p, r)
  i = RANDOM(p, r)
  exchange A[r] with A[i]
  return PARTITION-WEIGHTED(A, p, r)

// 目标是求出最小的数x，使得小于等于x的所有权值之和大于等于0.5.
MEDIAN-WEIGHT(A, n)
  pw = 0.5
  p = 1
  r = n
  while p < r
    q, nw = RANDOMIZED-PARTITION(A, p, r)
    if nw >= pw
      r = q
    else
      pw = pw - nw
      p = q + 1
  return A[p].x

d

假设 $x$ 是目前的最小值解，且 $x$ 不是带权中位数，即不满足带权中位数条件 $\sum_{x_{i} < x_{k}} w_{i} < \frac{1}{2}, \sum_{x_{i} > x_{k}} w_{i} \leq \frac{1}{2}$ 中的一个。

不失一般性，假设不满足第 $2$ 个条件，那么有 $\sum_{p_{i} > x} w_{i} - \sum_{p_{i} < x} w_{i} > 0$ 。

令 $k = {min}_{i = 1}^{n} {| x - p_{i} |}$ ，那么取 $l$ 使得 $l \in [0, k)$ 。从 $x$ 向右迈出一小步 $l$ ，那么此时有

$\begin{aligned} \sum_{i = 1}^{n} w_{i} d (x + l, p_{i}) & = \sum_{p_{i} < x} w_{i} (x + l - p_{i}) + \sum_{p_{i} > x} w_{i} (p_{i} - x - l) \\ = \sum_{p_{i} < x} w_{i} (x - p_{i}) + \sum_{p_{i} > x} w_{i} (p_{i} - x) - l (\sum_{p_{i} > x} w_{i} - \sum_{p_{i} < x} w_{i}) \\ = \sum_{i = 1}^{n} w_{i} d (x, p_{i}) - l (\sum_{p_{i} > x} w_{i} - \sum_{p_{i} < x} w_{i}) \\ \leq \sum_{i = 1}^{n} w_{i} d (x, p_{i}) \end{aligned}$

由此可见，得到了一个更优秀的解 $x + l$ 。

当不满足第 $1$ 个条件时，则是按反方向走，证明方法类似。

因此，当 $x$ 是带权中位数时，得到的解是最优的。

e

由于 $\sum_{i = 1}^{n} d (p, p_{i}) = \sum_{i = 1}^{n} w_{i} (| x - x_{i} | + | y - y_{i} |) = (\sum_{i = 1}^{n} w_{i} | x - x_{i} |) + (\sum_{i = 1}^{n} w_{i} | y - y_{i} |)$ ，可以分别将两个维度的坐标看成是两个独立的一维问题进行解决。分别求出 $x$ 坐标和 $y$ 坐标后进行组合即可。

9-4

a

这个算法由 SELECT' 给出。基本思想是先一对对元素进行比较并且绑定，完成 $⌊ \frac{n}{2} ⌋$ 次比较后，递归划分出 $⌈ \frac{n}{2} ⌉$ 个小元素中前 $i$ 小的元素。划分好后，第 $i$ 小数必定是这 $i$ 对数中的第 $i$ 小数。

SELECT'(A, n, i)
  if 2 * i >= n
    return SELECT(A, 1, n, i)
  if n % 2 == 1
    INSERT(A, +∞)
    n += 1
  m = n / 2
  for i = 1 to m
    if A[i] > A[i + m]
      exchange A[i] with A[i + m]
      combine A[i] and A[i + m]
  SELECT'(A[1 : m], m, i)
  let B[1 : i + i] be new array
  for j = 1 to i
    B[j] = A[i]
    B[j + i] = the number that A[i] combine
  return SELECT(B, 1, i + i, i)

b

我们使用代入法来证明 $U_{i} (n) - n = O (T (2 i) \lg (n / i))$ 。假设 $U_{i} (n) - n \leq c \cdot T (2 i) \cdot \lg (n / i)$ 。那么有

$\begin{aligned} U_{i} (n) - n & = (U_{i} (⌈ n / 2 ⌉) - ⌈ n / 2 ⌉) + T (2 i) \\ \leq c \cdot T (2 i) \cdot \lg (⌈ n / 2 ⌉ / i) + T (2 i) \\ \leq c \cdot T (2 i) \cdot (\lg (n / 2 / i) + 1) & (A) \\ \leq c \cdot T (2 i) \cdot (\lg (n / i)) \end{aligned}$

其中，步骤 $(A)$ 假设了 $c > 1$ ，并且足够大到消去符号 $⌈ ⌉$ 。

因此， $U_{i} (n) - n = O (T (2 i) \lg (n / i))$ ，即 $U_{i} (n) = n + O (T (2 i) \lg (n / i))$ 。

c

根据题目 9-4-b 的结论，可以得出： $\exists c, n_{0} > 0, \forall n > n_{0}, 0 \leq U_{i} (n) - n \leq c \cdot S (2 i) \cdot \lg (n / i)$ 恒成立。

那么有

$\begin{aligned} U_{i} (n) - n & \leq c \cdot S (2 i) \cdot \lg (n / i) \\ = c \cdot S (2 i) \cdot (\lg n - \lg i) \\ \leq c \cdot S (2 i) \cdot \lg n \end{aligned}$

构造一个新常数 $c^{'} = c \cdot S (2 i)$ ，那么这对常数 ${c^{'}, n_{0}}$ 说明 $U_{i} (n) - n = O (\lg n)$ ，即 $U_{i} (n) = n + O (\lg n)$ 。

d

当 $k \geq 2$ 时， $i = n / k < n / 2$ 。因此根据题目 9-4-b 的结论，代入 $i = n / k$ ，可以得到 $U_{i} (n) = n + O (S (2 n / k) \lg k)$ 。

9-5

a

和分析 RANDOMIZED-QUICKSORT 时的思想一致，如果我们选择的支点处在 $min {z_{i}, z_{j}}$ 和 $max {z_{i}, z_{k}}$ 之间时，才会有讨论的意义。否则，每次划分区间时，这 $3$ 个元素仍然处在同一个区间内部， $z_{j}$ 和 $z_{k}$ 是否被比较仍然未知。并且按照上面的思想， $z_{j}$ 和 $z_{k}$ 是否被比较，当且仅当 $z_{j}, z_{k}$ 处在同一区间内，并且着两个数之一成为支点 $q$ 。那么分别考虑三种情况：

当 $z_{i} < z_{j} < z_{k}$ 时，如果支点 $q \in {z_{j}, z_{k}}$ ，那么就会产生对 $z_{j}, z_{k}$ 的比较。如果 $q \in [z_{i}, z_{j})$ ，那么下一层递归将会进入区间 $[z_{i}, q), z_{j}, z_{k}$ 永远不会被比较。如果 $q \in (z_{j}, z_{k})$ ，那么 $z_{j}$ 和 $z_{k}$ 将会被分隔开，永远不会被比较。此时 $E [X_{i j k}] = \frac{2}{k - i + 1}$ 。
当 $z_{j} < z_{k} < z_{i}$ 时，此时和情况 1 类似。此时 $E [X_{i j k}] = \frac{2}{i - j + 1}$ 。
当 $z_{j} \leq z_{i} \leq z_{k}$ 时，类似的，如果 $q \in (z_{j}, z_{k})$ ，那么 $z_{j}$ 和 $z_{k}$ 将会被分隔开，永远不会被比较；否则必定会被比较，此时 $E [X_{i j k}] = \frac{2}{k - j + 1}$ 。

因此有：

$E [X_{i j k}] = {\begin{aligned} \frac{2}{k - i + 1} & if z_{i} < z_{j} < z_{k} \\ \frac{2}{i - j + 1} & if z_{j} < z_{k} < z_{i} \\ \frac{2}{k - j + 1} & if z_{j} \leq z_{i} \leq z_{k} \end{aligned}$

b

根据示性随机变量 $X_{i}$ 的定义，有 $X_{i} = \sum_{j = 1}^{n - 1} \sum_{k = j + 1}^{n} X_{i j k}$ 。那么有

$\begin{aligned} E [X_{i}] & = E [\sum_{j = 1}^{n - 1} \sum_{k = j + 1}^{n} X_{i j k}] \\ = \sum_{j = 1}^{n - 1} \sum_{k = j + 1}^{n} E [X_{i j k}] \\ = \sum_{j = i + 1}^{n - 1} \sum_{k = j + 1}^{n} E [X_{i j k}] + \sum_{j = 1}^{i - 2} \sum_{k = j + 1}^{i - 1} E [X_{i j k}] + \sum_{j = 1}^{i} \sum_{k = i}^{n} E [X_{i j k}] \\ = \sum_{j = i + 1}^{n - 1} \sum_{k = j + 1}^{n} \frac{2}{k - i + 1} + \sum_{j = 1}^{i - 2} \sum_{k = j + 1}^{i - 1} \frac{2}{i - j + 1} + \sum_{j = 1}^{i} \sum_{k = i}^{n} \frac{2}{k - j + 1} \\ = 2 (\sum_{j = i + 1}^{n - 1} \sum_{k = j + 1}^{n} \frac{1}{k - i + 1} + \sum_{j = 1}^{i - 2} \sum_{k = j + 1}^{i - 1} \frac{1}{i - j + 1} + \sum_{j = 1}^{i} \sum_{k = i}^{n} \frac{1}{k - j + 1}) \\ = 2 (\sum_{k = i + 2}^{n} \frac{k - i - 1}{k - i + 1} + \sum_{j = 1}^{i - 2} \frac{i - j - 1}{i - j + 1} + \sum_{j = 1}^{i} \sum_{k = i}^{n} \frac{1}{k - j + 1}) \\ \leq 2 (\sum_{k = i + 1}^{n} \frac{k - i - 1}{k - i + 1} + \sum_{j = 1}^{i - 2} \frac{i - j - 1}{i - j + 1} + \sum_{j = 1}^{i} \sum_{k = i}^{n} \frac{1}{k - j + 1}) \end{aligned}$

c

由题目 9-5-b 的推导继续进行。

$\begin{aligned} E [X_{i}] & \leq 2 (\sum_{k = i + 1}^{n} \frac{k - i - 1}{k - i + 1} + \sum_{j = 1}^{i - 2} \frac{i - j - 1}{i - j + 1} + \sum_{j = 1}^{i} \sum_{k = i}^{n} \frac{1}{k - j + 1}) \\ \leq 2 (\sum_{k = i + 1}^{n} 1 + \sum_{j = 1}^{i - 2} 1 + \sum_{j = 1}^{i} \sum_{k = i}^{n} \frac{1}{k - j + 1}) \\ = 2 (n - 2 + \sum_{j = 1}^{i} \sum_{k = i}^{n} \frac{1}{k - j + 1}) \\ = 2 (n - 2 + \sum_{c = 1}^{n} \frac{1}{c} \cdot \sum_{1 \leq j \leq i, i \leq j + c - 1 \leq n} 1) \\ \leq 2 (n - 2 + \sum_{c = 1}^{n} \frac{1}{c} \cdot c) \\ \leq 2 (n - 2 + n) \\ \leq 4 n \end{aligned}$

d

算法 RANDOMIZED-SELECT 的整个过程是围绕子程序 RANDOMIZED-PARTITION 进行的，比较过程就在这个子程序中进行。

根据题目 9-5-c 的结论，所有调用子程序 RANDOMIZED-PARTITION 的过程中，总期望比较次数不超过 $4 n$ 。因此算法 RANDOMIZED-SELECT 的时间复杂度为 $O (n)$ 。

9-6

假设单个组的大小为 $2 k + 1$ ，其中 $k$ 是一个正整数，且是常数。

a

此时意味着有前提条件： $k \geq 2$ .

前 11 行代码，无非就是将所有为 $5$ 的常量转化成 $2 k + 1$ 。这一段的代码运行时间仍然为 $Θ (n)$ 。

第 12-13 行代码对每组 $2 k + 1$ 个元素进行原地排序。由于每组内部元素数量相同，一共有 $Θ (n)$ 组，这一段的运行时间仍然为 $Θ (n)$ 。

第 16 行对中间的一组再进行一次调用，产生了 $T (n / (2 k + 1))$ 的开销。

第 17 行对数组进行了一次划分，这一段的运行时间仍然为 $Θ (n)$ 。

总而言之，上面这部分算法内部开销的时间复杂度为 $Θ (n)$ 。

第 20-24 行递归进入所划分的区间。按照这种划分方法，可以知道，第 16 行中的 $x$ 至少有 $\frac{n \cdot (k + 1)}{2 \cdot (2 k + 1)} = \frac{k + 1}{4 k + 2} n$ 个数比它大，至少有 $\frac{k + 1}{4 k + 2} n$ 个数比它小。因此每次进行下一次递归时，至多可以去除 $\frac{k + 1}{4 k + 2} n$ 个数。假设 $T (n)$ 为对 $n$ 个元素进行选择的运行时间，那么有

$T (n) \leq T (n / (2 k + 1)) + T ((3 k + 1) n / (4 k + 2)) + Θ (n)$

使用代入法，假设 $T (n) \leq c n$ ，那么有

$\begin{aligned} T (n) & \leq T (n / (2 k + 1)) + T ((3 k + 1) n / (4 k + 2)) + Θ (n) \\ \leq \frac{c}{2 k + 1} n + \frac{c (3 k + 1)}{4 k + 2} n + Θ (n) \\ = c n - \frac{c (k - 1)}{4 k + 2} n + Θ (n) \\ \leq c n & (A) \end{aligned}$

其中，步骤 $(A)$ 假设了 $c$ 足够大，以至于项 $\frac{c (k - 1)}{4 k + 2} n$ 的渐进增长速度超过 $Θ (n)$ 。并且，由于 $k \geq 2$ ，因此这个项是恒正的。

因此有 $T (n) = O (n)$ 。

由于第 17 行对数组进行了一次 $Θ (n)$ 的划分，因此说明 $T (n) = Ω (n)$ 。

因此最终有 $T (n) = Θ (n)$ 。

b

此时意味着有前提条件： $k = 1$ .

那么 $T (n)$ 可以写成

$T (n) \leq T (n / 3) + T (2 n / 3) + Θ (n)$

由于 $k = 1$ ，项 $\frac{c (k - 1)}{4 k + 2} n$ 的值恒为 $0$ ，因此题目 9-6-a 的结论不适用。

那么假设 $T (n) \leq c n \lg n$ ，有

$\begin{aligned} T (n) & \leq T (n / 3) + T (2 n / 3) + Θ (n) \\ \leq \frac{c n}{3} \lg \frac{c n}{3} + \frac{2 n}{3} \lg \frac{2 n}{3} + Θ (n) \\ = c n \lg n - \frac{c}{3} \cdot \lg \frac{27}{4} \cdot n + Θ (n) \\ \leq c n \lg n & (A) \end{aligned}$

其中，步骤 $(A)$ 假设了 $c$ 足够大，以至于 $\frac{c}{3} \cdot \lg \frac{27}{4} \cdot n$ 的渐进增长速度超过 $Θ (n)$ 。

因此有 $T (n) = O (n \lg n)$ 。

c

前 11 行代码是为了调整整个数组的长度是 $9$ 的倍数。

第 12-13 行代码则是对组内的所有元素进行排序，每组有 $3$ 个元素。排完序后的示意图如下：

第 16-17 行代码则是对大组中的所有中位数再次进行排序，由于排序元素数量恒定为 $3$ 个。排完序后的示意图如下：

其中，蓝色区域表示比 $x$ 小的数，黄色区域表示比 $x$ 大的数。

因此可以发现，整个序列可以划分成大小为 $9$ 的组，也就是说一共有 $\frac{n}{9}$ 组。其中一半的大组至少有 $4$ 个数比 $x$ 小，一半的大组至少有 $4$ 个数比 $x$ 大。那么在每一次的划分过程中，我们可以排除掉至少 $\frac{n \cdot 4}{2 \cdot 9} = \frac{2}{9} n$ 个数。

由此继续进行划分下去，最终可以成功找到一个第 $i$ 大的数。

d

第 1 行的 while 循环次数最多为 $8$ ，内部嵌套的 for 循环长度为 $Θ (n)$ ，因此前 11 行代码的运行时间为 $Θ (n)$ 。

第 12-13 行代码则是对组内的所有元素进行排序，由于排序元素数量恒定为 $3$ 个，组数为 $Θ (n)$ 。因此第 12-13 行代码的运行时间为 $Θ (n)$ 。

第 16-17 行代码则是对大组中的所有中位数再次进行排序，由于排序元素数量恒定为 $3$ 个，大组的组数也是 $Θ (n)$ 。因此第 12-13 行代码的运行时间为 $Θ (n)$ 。

第 20 行对中间的一个大组再进行一次调用，产生了 $T (n / 9)$ 的开销。

第 21 行对数组进行了一次划分，这一段的运行时间仍然为 $Θ (n)$ 。

第 23-28 行递归进入所划分的区间。按照题目 9-6-c 的描述，这个开销最大为 $T (7 n / 9)$ 。

那么可以写出 $T (n)$ 的递推关系式：

$T (n) \leq T (n / 9) + T (7 n / 9) + Θ (n)$

进一步化简，有

$\begin{aligned} T (n) & \leq T (n / 9) + T (7 n / 9) + Θ (n) \\ \leq c n / 9 + 7 c n / 9 + Θ (n) \\ = c n - c n / 9 + Θ (n) \\ \leq c n & (A) \end{aligned}$

其中，步骤 $(A)$ 假设了 $c$ 足够大，以至于项 $c n / 9$ 的渐进增长速度超过 $Θ (n)$ 。

因此有 $T (n) = O (n)$ 。