算法导论19.2 Exercises 答案

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

19.2-1

每个链表\(L\)由三个属性决定：\(head,tail,size\)，分别表示链表\(L\)的头节点，尾节点和节点个数，每个链表节点\(z\)都由两个属性来决定：\(next,r\)，前者用途和普通链表一致，后者代表其所属链表，即指向链表本身的指针。那么可以写出如下关于算法MAKE-SET，FIND-SET和UNION-SET的代码：

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
MAKE-SET(z)
  Let L be a new link list
  L.head = z
  L.tail = z
  L.size = 1
  z.next = NIL
  z.r = L

FIND-SET(z)
  return z.r

UNION(x, y)
  L1 = x.r
  L2 = y.r
  if L1.size > L2.size
    exchange L1 with L2
  // 此时保证了L1.size <= L2.size
  L2.size = L2.size + L1.size
  p = L1.head
  // 先让L1中的所有节点的r属性指向L2
  while p != NIL
    p.r = L2
    p = p.next
  L2.tail.next = L1.head
  L2.tail = L1.tail
  //销毁已经没用的头节点
  Destroy link list L1
  return L2

19.2-2

在第1-2行初始化完成后，有如下链表和元素（为了方便，使用表达式来表示）：

\(\begin{aligned} S_{1}&=\langle x_{1}\rangle\\ S_{2}&=\langle x_{2}\rangle\\ S_{3}&=\langle x_{3}\rangle\\ S_{4}&=\langle x_{4}\rangle\\ S_{5}&=\langle x_{5}\rangle\\ S_{6}&=\langle x_{6}\rangle\\ S_{7}&=\langle x_{7}\rangle\\ S_{8}&=\langle x_{8}\rangle\\ S_{9}&=\langle x_{9}\rangle\\ S_{10}&=\langle x_{10}\rangle\\ S_{11}&=\langle x_{11}\rangle\\ S_{12}&=\langle x_{12}\rangle\\ S_{13}&=\langle x_{13}\rangle\\ S_{14}&=\langle x_{14}\rangle\\ S_{15}&=\langle x_{15}\rangle\\ S_{16}&=\langle x_{16}\rangle\\ \end{aligned}\)

在第3-4行的循环完成后，有：

\(\begin{aligned} S_{1}&=\langle x_{1}, x_{2}\rangle\\ S_{3}&=\langle x_{3}, x_{4}\rangle\\ S_{5}&=\langle x_{5}, x_{6}\rangle\\ S_{7}&=\langle x_{7}, x_{8}\rangle\\ S_{9}&=\langle x_{9}, x_{10}\rangle\\ S_{11}&=\langle x_{11}, x_{12}\rangle\\ S_{13}&=\langle x_{13}, x_{14}\rangle\\ S_{15}&=\langle x_{15}, x_{16}\rangle\\ \end{aligned}\)

在第5-6行的循环完成后，有：

\(\begin{aligned} S_{1}&=\langle x_{1}, x_{2}, x_{3}, x_{4}\rangle\\ S_{5}&=\langle x_{5}, x_{6}, x_{7}, x_{8}\rangle\\ S_{9}&=\langle x_{9}, x_{10}, x_{11}, x_{12}\rangle\\ S_{13}&=\langle x_{13}, x_{14}, x_{15}, x_{16}\rangle\\ \end{aligned}\)

第7行完成后为：

\(\begin{aligned} S_{1}&=\langle x_{1}, x_{2}, x_{3}, x_{4},x_{5}, x_{6}, x_{7}, x_{8}\rangle\\ S_{9}&=\langle x_{9}, x_{10}, x_{11}, x_{12}\rangle\\ S_{13}&=\langle x_{13}, x_{14}, x_{15}, x_{16}\rangle\\ \end{aligned}\)

第8行完成后为：

\(\begin{aligned} S_{1}&=\langle x_{1}, x_{2}, x_{3}, x_{4},x_{5}, x_{6}, x_{7}, x_{8}\rangle\\ S_{9}&=\langle x_{9}, x_{10}, x_{11}, x_{12},x_{13}, x_{14}, x_{15}, x_{16}\rangle\\ \end{aligned}\)

第9行完成后为：

\(\begin{aligned} S_{1}&=\langle x_{1}, x_{2}, x_{3}, x_{4},x_{5}, x_{6}, x_{7}, x_{8}, x_{9}, x_{10}, x_{11}, x_{12},x_{13}, x_{14}, x_{15}, x_{16}\rangle\\ \end{aligned}\)

因此第10行和第11行的返回结果均为\(S_1\)。

19.2-3

考虑目前总共有\(m\)个操作，其中有\(a(a< n)\)个UNION操作，\(b\)个FIND-SET操作以及\(m-a-b\)个MAKE-SET操作。

令\(c_i\)表示第\(i\)个操作的代价，\(\widehat{c_i}\)为第\(i\)个操作的均摊代价。按照定理19.1的分析，对于某一个元素而言，只要对它更新到一个新的集合，那么新的集合的大小至少为当前集合的\(2\)倍。由于只有\(a\)个UNION操作，因此这部分时间的总和为\(O(a\lg n)\)。最终，存在正常数\(c\)，使得\(\displaystyle{\sum_{i=1}^m c_i\le cm+ca\lg n}\)成立。

假设MAKE-SET和FIND-SET的均摊代价为\(c\)，UNION的均摊代价为\(c(\lg n+1)\)，那么其总均摊代价为\(\displaystyle{\sum_{i=1}^m\widehat{c_i}=cb+c(m-a-b)+ca(\lg n+1)=cm+ca\lg n}\)。即可有\(\displaystyle{\sum_{i=1}^m\widehat{c_i}\ge \sum_{i=1}^mc_i}\)，均摊代价足够。

因此可知，MAKE-SET和FIND-SET的均摊代价为\(O(1)\)，UNION的均摊代价为\(O(\lg n)\)。

19.2-4

前\(n\)个MAKE-SET操作的时间复杂度保持，仍然为\(O(1)\)。对于后面的\(n-1\)个UNION操作，第\(i\)个操作是将\(1\)个元素所代表的集合合并到\(n-1\)个元素所代表的集合中。由于使用了启发式合并策略，较小的集合总是只有\(1\)个元素，因此一次UNION操作只需要\(O(1)\)的时间。因此图19-3的运行时间为\((2n-1)\cdot O(1)=O(n)\)。

19.2-5

考虑如下改造：这时每个链表的最后一个节点成为了代表元素，每个节点的属性\(r\)将不会再链接到某个链表，取而代之的是指向链表的最后一个节点\(z\)，并且链表\(L\)舍去了属性\(tail\)，只保留属性\(head\)。此外，\(L\)中的所有节点将会和\(L\)自身构成一个循环链表，也就是说，\(z.next\)将指向\(L\)。

改写后的算法MAKE-SET'和UNION'的代码如下所示。可以发现，UNION'操作均摊后的时间复杂度仍然为\(O(\lg n)\)。

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
MAKE-SET'(z)
  Let L be a new link list
  L.head = z
  L.size = 1
  z.next = L
  z.r = z

UNION'(x, y)
  L1 = x.r.next
  L2 = y.r.next
  if L1.size > L2.size
    exchange L1 with L2
  // 此时保证了L1.size <= L2.size
  // 这个操作是将链表L1接在了L2前面  
  L1.size = L2.size + L1.size
  p = L1.head
  // 先让L1中的所有节点的r属性指向L2的tail
  while p != T1
    p.r = L2.head.r
    p = p.next
  // L1.head.r是L1.tail
  L1.head.r.next = L2.head
  L2.head.r.next = L1
  L2.tail = L1.tail
  //销毁已经没用的头节点
  Destroy link list L2
  return L1

19.2-6

考虑同时使用两个指针在链表\(L_1,L_2\)上进行遍历，并且随着遍历过程进行，这两个链表逐渐被一个接一个地合并在一起，直到其中一个链表到达终点，最终将这些链表的代表节点重新进行标记即可。在这种情况下，每个节点的\(r\)属性可以指向链表自身。改写后的算法MAKE-SET''和UNION''的代码如下所示。

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
33
34
35
36
MAKE-SET''(z)
  Let L be a new link list
  L.head = z
  z.r = L
  z.next = NIL

UNION''(x, y)
  L1 = x.r
  L2 = y.r
  p = L1.head.next
  q = L2.head.next
  head = L1.head
  head.next = L2.head
  o = head.next
  while p != NIL and q != NIL
    o.next = p
    o.next.next = q
    p = p.next
    q = q.next
    o = o.next.next
  o.next = NIL
  s = head
  if p != NIL
    while s != NIL
      s.r = T1
      s = s.next
    T1.head = r
    Destroy link list L2
    return T1
  else
    while s != NIL
      s.r = T2
      s = s.next
    T2.head = r
    Destroy link list L1
    return T2