算法导论19 Problems 答案

发表于 2023-06-14 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 4.4k 阅读时长 ≈ 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\)中的节点将被删除。

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\)。

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

c

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

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\)，以保证伪距离仍然正确。

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行。考虑两种情况：

\(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\)只被访问了一次。
\(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\)是否具有祖孙关系，考虑如下两种情况：

\(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\)，因此该算法正确。
\(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|)\)。