算法导论19.3 Exercises 答案

发表于 2023-06-14 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 3.5k 阅读时长 ≈ 3 分钟

19.3-1

为了方便，此处作图忽略了箭头和自环。

一开始，所有树的\(rank\)都为\(0\)。

graph TB
A((1));B((2));C((3));D((4));
E((5));F((6));G((7));H((8));
I((9));J((10));K((11));L((12));
M((13));N((14));O((15));P((16));

在第3-4行的循环完成后，所有的树的\(rank\)变成了\(1\)。

graph TB
A((1));B((2));C((3));D((4));E((5));F((6));G((7));H((8));I((9));J((10));K((11));L((12));M((13));N((14));O((15));P((16));A---B;C---D;E---F;G---H;I---J;K---L;M---N;O---P;

在第5-6行的循环完成后，所有的树的\(rank\)变成了\(2\)。

graph TB
A((1));B((2));C((3));D((4));
E((5));F((6));G((7));H((8));
I((9));J((10));K((11));L((12));
M((13));N((14));O((15));P((16));
D---B;D---C;B---A;H---F;
H---G;F---E;L---J;L---K;
J---I;P---N;P---O;N---M;

第7行完成后如下，其中第一棵树的\(rank\)为\(3\)，其余的\(rank\)为\(2\)。

graph TB
A((1));B((2));C((3));D((4));
E((5));F((6));G((7));H((8));
I((9));J((10));K((11));L((12));
M((13));N((14));O((15));P((16));
H---D;H---E;H---F;H---G;
D---A;D---B;D---C;L---J;
L---K;J---I;P---N;P---O;
N---M;

第8行完成后如下，两棵树的\(rank\)都是\(3\).

graph TB
A((1));B((2));C((3));D((4));
E((5));F((6));G((7));H((8));
I((9));J((10));K((11));L((12));
M((13));N((14));O((15));P((16));
H---D;H---E;H---F;H---G;
D---A;D---B;D---C;P---L;
P---M;P---N;P---O;L---J;
L---K;J---I

第9行完成后如下，这棵树的\(rank\)为\(4\)。

graph TB
A((1));B((2));C((3));D((4));
E((5));F((6));G((7));H((8));
I((9));J((10));K((11));L((12));
M((13));N((14));O((15));P((16));
H---D;H---E;H---F;H---G;
H---A;D---B;D---C;P---H;P---L;
P---M;P---N;P---O;P---J;
L---K;J---I

第10行完成后如下，这棵树的\(rank\)为\(4\)。

graph TB
A((1));B((2));C((3));D((4));
E((5));F((6));G((7));H((8));
I((9));J((10));K((11));L((12));
M((13));N((14));O((15));P((16));
P---B;P---D;H---A;H---E;
H---F;H---G;D---C;P---H;
P---J;P---L;P---M;P---N;
P---O;L---K;J---I

第11行完成后如下，这棵树的\(rank\)为\(4\)。

graph TB
A((1));B((2));C((3));D((4));
E((5));F((6));G((7));H((8));
I((9));J((10));K((11));L((12));
M((13));N((14));O((15));P((16));
P---B;P---D;H---A;H---E;
H---F;H---G;D---C;P---H;
P---I;P---J;P---L;P---M;P---N;
P---O;L---K;

19.3-2

FIND-SET-ITERATIVE(x)
  let A be new array
  while x != x.p
    INSERT(A, x)
    x = x.p
  for each y in A
    y.p = x
  return x

19.3-3

当\(m\)足够大时（也就是有\(m\ge 2n-1\)），我们只需要构造一个\(m\)个操作序列，从而证明其总共所需要的操作时间为\(\Omega(n\lg m)\)即可。这个操作序列如下：

UNION-SEQUENCE(n, m)
  for i = 1 to n
    MAKE-SET(x_{i})
  k = 2
  while k <= n
    for i = k / 2 to n by k
      UNION(x_{i - k / 2}, x_{i})
  for i = 1 to m - (2 * n - 1)
    FIND-SET(x_{1})

在这个序列中，可以知道while循环最多可以迭代\(\lceil\lg (n+1)\rceil\)轮，其中当\(k\)为某个\(2\)的幂时，内部的for循环恰好会执行\(\lfloor n/k\rfloor\)次。可以发现，\(\displaystyle{\sum_{i=1}^{\infty}\left\lfloor\dfrac{n}{2^i}\right\rfloor=n-1}\)，也就是说，这\(n-1\)个操作将所有集合合并在了一起。考虑第\(i(i\ge 1)\)轮操作，其中\(k=2^i\)。那么在第\(i\)轮合并开始前，每\(2^{i-1}\)个元素都会合并在一起，它们所在树的秩都是一样的（除了最后一棵可能不足）；合并后，每\(2^i\)个元素都会合并在一起，它们所在树的秩仍然都是一样的（除了最后一棵可能不足），相比之前，这些树的秩都增加了\(1\)。因此，最终经过这\(n-1\)次操作后，这棵树的高度为\(\Omega(\lg n)\)。

在这\(m\)次操作中，有\(n\)次MAKE-SET操作，\(n-1\)次UNION操作，其余\(m-(2n-1)\)次都是FIND操作。由于每次UNION操作都会调用\(2\)次FIND-SET操作，因此这个操作序列中总共进行了\(m-1\)次FIND-SET操作。如果每次FIND-SET操作都是取秩大的那棵树下最深的点，那么一次FIND-SET操作需要花费的时间为\(\Omega(\lg n)\)，最终全部操作所需要花费的时间为\(\Omega(m\lg n)\)。

19.3-4

添加一个参数\(next\)即可。将这些节点使用一个循环链表组织起来，在进行一次合并操作时，就将这两个循环链表断开并合并即可。打印时，只需要遍历这一整个循环链表即可。

只需要修改MAKE-SET和UNION操作，不需要修改FIND-SET操作。此后将连通PRINT-SET操作一同给出：

MAKE-SET2(x)
  x.p = x
  x.rank = 0
  x.next = x

UNION2(x, y)
  LINK(FIND-SET(x), FIND-SET(y))
  p = x.next
  x.next = y.next
  y.next = p

PRINT-SET(x)
  print x
  p = x.next
  while p != x
    print p

\(\star\) 19.3-5

注意到每次LINK操作只需要花费\(O(1)\)的时间，并且它的LINK操作所输入的参数都是每棵树的根节点。

由于所有LINK操作都在FIND-SET操作的前面，因此在第一个FIND-SET操作执行前，整个森林的结构已经确定好了。

考虑使用核算法证明这个长度为\(m\)的操作序列的时间复杂度为\(O(m)\)：

每个MAKE-SET操作均摊\(2\)美元，其中\(1\)美元用于自身节点的创建，另\(1\)美元用于信用预支，在FIND-SET操作中使用。
每个LINK操作均摊\(1\)美元，这类操作仅仅用于将一棵树的根指向另外一棵树的根。
每个FIND-SET操作均摊\(1\)美元。分别考虑两种情况：如果节点\(x\)曾经被FIND-SET调用过，那么直接返回\(x.p\)即可，\(1\)美元支撑此开销；否则，预支的\(1\)美元用于寻找\(x.p\)的祖先。考虑从\(x\)到它的根\(r\)这一条路径\(v_1,v_2,\dots,v_k\)，其中\(v_1=x,v_{k}=r\)。那么对于\(i=1,2,\dots,k-2\)，节点\(v_i\)必定未被调用过FIND-SET（否则，\(v_i\)的下一个节点必定是\(r\)）。因此，这些节点的预支的\(1\)美元仍未被使用，这总共\(k-2\)美元的预支都将帮助到\(v_1,v_2v\dots,v_{k-2}\)指向根节点。接下来，只需要花费\(1\)美元将\(x.p\)返回即可。

由于所有操作中，单个操作需要不超过\(2\)美元即可。因此，这\(m\)个操作总共需要花费的时间为\(O(m)\)。

如果再添加上按秩合并，并不影响它仍然只需要\(O(m)\)的时间，因为LINK操作的花费仍然是常数。