算法导论19 Problems 答案

发表于 更新于 分类于 阅读次数： 本文字数： 4.1k 阅读时长 ≈ 4 分钟

19-1

a

随着操作进行，集合$T$和数组$extracted$的变化如下：

$\begin{array}{|l|l|l|}\hline
S&T&extracted\\hline
4&4&\\hline
8&4,8&\\hline
E&8&4\\hline
3&3,8&4\\hline
E&8&4,3\\hline
9&8,9&4,3\\hline
2&2,8,9&4,3\\hline
6&2,6,8,9&4,3\\hline
E&6,8,9&4,3,2\\hline
E&8,9&4,3,2,6\\hline
E&9&4,3,2,6,8\\hline
1&1,9&4,3,2,6,8\\hline
7&1,7,9&4,3,2,6,8\\hline
E&7,9&4,3,2,6,8,1\\hline
5&5,7,9&4,3,2,6,8,1\\hline
\end{array}$

b

当某一个数$i$在OFFLINE-MINIMUM的第2行被确认位置后，此后再也不需要再访问它，因此可以认为$i$从这些集合${K_j}$中被删除了（符合EXTRACTED-MIN的定义）。我们从小到大枚举数$i$，并且确认了$i$的位置$j$后，$extract[j]$被填上了$i$，此后集合$K_j$中的所有元素被合并到了比$j$大的仍然存在的一个集合$K_l$中，并且集合$j$被销毁。因此，随着每一步的进行，对于$p\in[1,m]$，要么$extract[p]$未被填充；要么$K_p$被销毁，每次$K_p$被销毁，它总是会将这些数转移到下一个潜在的最优集合中。因此整个算法的正确性是成立的。

c

直接使用并查集，并在其中维护一些信息即可。初始化一个长度为$m$的链表$L$，用于表示哪些集合被删除了。随着合并过程的进行，$L$中的节点将被删除。

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
OFFLINE-MINIMUM'(m, n, K)
  let L be a new doublie link list
  let P[1 : m + 1] be a new array
  let extracted[1 : m] be a new array
  for i = 1 to m + 1
    Let p be a new list node
    p.key = i
    P[i] = p
    LIST-INSERT'(L, p)
    // 链表节点的q属性是指属于这个集合的某个元素。
    if K[i].size > 0
      p.q = K[i][1]
    else
      p.q = NIL
  // 每个节点（关键字）都会多一个属性g，表示在哪一个组里。
  for i = 1 to m + 1
    for each x in K[i]
      MAKE-SET(x, i)
      x.g = i
  for i = 1 to n
    j = i.g
    if j != m + 1
      extracted[j] = i
      z = P[i]
      z = z.next
      LIST-DELETE'(L, P[i])
      if z.q != NIL
        UNION(i, z.q)
      x = FIND-SET(i)
      x.g = z.key
  return extracted

由于OFFLINE-MINIMUM'中的所有过程都只是调用了$n$次MAKE-SET，至多$m-1$次UNION操作和FIND-SET操作（$m<n$），其余操作都是常数开销的操作，因此整个OFFLINE-MINIUM'算法的时间复杂度为$O(n\alpha(n))$。

19-2

a

考虑如下$m$个操作序列：前$m/3$个操作为MAKE-TREE操作，它们创建了$m/3$棵包含唯一节点的树，所需要花费的时间总共为$O(m)$；之后的$m/3-1$个为GRAFT操作，将前面的$m/3$个节点首尾相接串联了起来，所需要花费的时间总共为$O(m)$；剩下的$m/3+1$个操作是FIND-DEPTH操作，每次调用的都是这棵树的叶子节点，每次所需要花费的时间为$\Theta(m)$（因为需要上升到根），那么最终，这$m/3+1$次操作花费了$\Theta(m^2)$的时间来完成。

因此，如上构造的操作序列需要花费$\Theta(m^2)$的时间来完成，原结论成立。

b

这个实现仅仅是多添加了一个属性$d$，并且将其初始化成$0$。

1
2
3
4
MAKE-TREE(x)
  MAKE-SET(x)
  // 一开始节点x并没有祖先
  x.d = 0

c

修正后给出的是FIND-SET'算法，先从当前节点到根节点求出一条路径，求出这条路径后，再自顶向下更新伪距离值，从而成为真实距离。当$x.p$的真实距离被求出后，加上当前$x$的伪距离$x.d$就成为了$x$的真实距离，在这个过程中，路径也被压缩。

1
2
3
4
5
6
7
8
9
10
11
FIND-SET'(x)
  if x != x.p
    q = FIND-SET'(x.p)
    x.d = x.p.d + x.d
    x.p = q
  return x.p

FIND-DEPTH(x)
  FIND-SET'(x)
  // 此时确保了x直接连上了根，并且d属性已经被更新好
  return x.d

d

为了方便操作，我们将类似LINK操作合并到了UNION操作中。假设$r$所在不相交集合$S_i$的根为$x$，$v$所在不相交集合$S_j$为的根为$y$。需要注意的是，当$S_j$被合并入$S_i$时，如果直接合并，那么$y$从没有父节点，到变成了多出一个父节点$x$，其伪距离值为$x.d$。但实际上，$S_j$所在子树的深度并没有增加，因此需要对$y.d$减去$x.d$，以保证伪距离仍然正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
GRAFT(r, v)
  x = FIND-SET'(r)
  y = FIND-SET'(v)
  if x.rank > y.rank
    y.p = x
    // 也就是说，以x为根的所有子树的深度都增加了v.d + 1
    x.d = x.d + v.d + 1
    // 但是y.p = x意味着y多了一个父节点x，以y为子树的深度增加了x.p + 1。按照差分的思想，需要减回去。
    y.d = y.d - x.d
  else
    // 此时y没有受到影响，故不需要改变。
    x.p = y
    x.d = x.d + v.d + 1
    if x.rank == y.rank
      y.rank = y.rank + 1

e

由于MAKE-TREE操作和并查集的MAKE-SET类似，FIND-DEPTH操作以并查集的一次FIND-SET操作为子程序，GRAFT操作类似UNION，它们和并查集中对应的操作均摊时间都是紧逼的。因此长度为$m$的序列的操作序列时间复杂度与并查集一致，为$O(m\alpha(n))$。

19-3

a

由于$T$是一棵有根树，根据第3行对$u$的孩子$v$进行遍历，第4行对孩子节点$v$进行递归调用，可见算法LCA是对整棵树进行DFS，每个节点$u$都会被遍历一次。

在第8行，遍历对象是将满足$(u,\cdot)$或者是$(\cdot,u)$的所有询问节点对都进行一次遍历。对于一个询问对$p={u,v}$，接下来证明要么是以$(u,v)$的形式进入到第10行，要么是以$(v,u)$的形式进入第10行。考虑两种情况：

  1. $u,v$具有祖孙关系。不失一般性，假设$u$是$v$的祖先，那么处于调用LCA(v)时，$v$在第7行已被染色，并在第9行访问到询问对$p$时，$u$仍然是白色，因此无法到达第10行。回溯到调用LCA(u)时，第3行的for循环已经结束，$u$的所有子孙节点都被染成黑色，$u$自己才被染成黑色，此时在第9行访问到询问对$p$时，由于$v$已经被染成黑色，因此进入第10行，询问对$p$正式被访问，此后节点$u,v$不再被访问，因此询问对$p$只被访问了一次。

  2. $u,v$不具有子孙关系，那么令$l$为$u,v$的最近公共祖先。在访问$l$的子树时，不失一般性，先访问$u$所在的子树，再访问$v$所在的子树。那么调用LCA(u)时，到了第9行，询问对$p$的另一个节点$v$仍然是白色，因此无法到达第10行，此时$u$已经被染成黑色。之后调用LCA(v)时，询问对$p$的另一个节点$u$此前已经被染成黑色，因此可以进入第10行，询问对$p$正式被访问，此后节点$u,v$不再被访问，因此询问对$p$只被访问了一次。

最终，原结论成立。

b

我们考虑证明：只有在刚调用LCA(u)时，森林中集合的个数恰好等于$u$的深度。

当LCA(T.root)被调用时，MAKE-SET操作还没完成，因此森林中共有$0$个不相交的集合，原结论成立。假设刚调用$u$时，森林中恰好有$u.d$（这里属性$d$表示节点的深度），那么我们将证明对于$u$的每一个孩子$v$，使得刚调用LCA(v)时，都有不相交集合个数为$v.d=u.d+1$。

接下来首先使用归纳法证明：当LCA(u)的调用结束时，以$u$为子树的所有节点都被合并成了一个不相交集合。当$u$是一个叶子节点时，LCA(u)调用完成后恰好只有$u$节点所在的一个集合。当$u$不是一个叶子节点时，假设遍历完$u$的某个子节点$v$被调用了LCA(v)后，以$v$中的所有节点都被合并成一个不相交集合，那么在第5行将节点$u$所在的集合和节点$v$所在的集合进行合并。最终，for循环结束后，以$u$为子树的所有节点都处于同一个集合中。

回到原来的证明，假设目前已经调用LCA(u)，那么执行第1行后，不相交集合个数增加了$1$。那么在第3行枚举第$1$个儿子$v_1$时，此时不相交集合个数为$u.d+1$，接下来调用LCA(v_1)，此时原结论成立。当LCA(v_1)调用完成后（注意遍历LCA(v_1)后，按照上面的结论，只多产生了一个不相交集合），第5行将节点$u$和$v_1$所在的集合进行合并，因此第5行结束后，不相交集合的个数仍然位产生变化，因此当遍历第$2$个儿子$v_2$时，结论仍然成立，此后进行UNION操作后仍然保持集合数不变……也就是说，这个结论适用于$u$的所有子节点。

因此逐层向下推理，可知原结论成立。

c

按照$u,v$是否具有祖孙关系，考虑如下两种情况：

  1. $u,v$具有祖孙关系。不失一般性，假设$u$是$v$的祖先，那么处于调用LCA(v)时，$u$仍未被染色，因此第8行的for循环中，询问对${u,v}$不被处理。当回溯到LCA(u)时，$v$已经被染成黑色，此时第3行for循环结束后，$u$所在集合的所有祖先都是$u$，此时在第8行的for循环中，询问对${u,v}$被处理，其结果为$v$所在的树的根的祖先$ancestor$，也就是$u$，因此该算法正确。

  2. $u,v$不具有祖孙关系。令$w$是它们的最近公共祖先，这意味着$u,v$分别处在$w$的不同子树中。因此不失一般性，假设$u$所在的子树先被遍历。那么调用LCA(u)时，此时节点$v$仍然是白色的，因此第8行的for循环中，询问对${u,v}$不被处理。当$u$所在的子树被遍历完成后，回到了节点$w$，那么到了第5行$u$所在子树和$w$所在的节点被合并了，在第6行，这些节点的祖先被设置成了$w$，此后未被修改。当调用LCA(v)时，$u$已经被染成黑色，那么此时在第8行的for循环中，询问对${u,v}$被处理，其结果为$v$所在的树的根的祖先$ancestor$，也就是$w$，因此该算法正确。

最终可以得知，算法LCA是正确的。

d

在每次LCA(u)的调用过程中，都调用了一次MAKE-SET操作。接下来枚举$u$的每个子节点$v$，都进行了一次UNION操作和一次FIND-SET操作。

因此整个过程中，总共调用了$|V|$次MAKE-SET操作，$|V|-1$次UNION操作和$|V|-1$次FIND-SET操作。因此整个过程总共有$3|V|-1$次操作的时间复杂度为$O(|V|\alpha(|V|))$。。由于每个询问对都被访问了两次，因此第8-10行的for循环在整个过程中运行了$2$次，其花费的时间为$O(|P|)$。

故整个过程的运行时间为$O(|V|\alpha(|V|)+|P|)$。