算法导论16.3 Exercises 答案

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

16.3-1

构造\(\Phi'(D_i)=\Phi(D_i)-\Phi(D_0)\)。那么有\(\Phi'(D_i)=0\)。由于\(\forall i\ge 0,\Phi(D_i)\ge\Phi(D_0)\)均成立，因此\(\Phi'(D_i)\ge 0=\Phi'(D_0)\)均成立。

使用\(\Phi\)原来的方式计算摊分价值，有

\(\begin{aligned} \widehat{c_i} &= c_i +\Phi(D_i)-\Phi(D_{i-1})\\ &= c_i +(\Phi(D_i)-\Phi(D_0))-(\Phi(D_{i-1})-\Phi(D_0))\\ &= c_i +\Phi'(D_i)-\Phi'(D_{i-1})\\ \end{aligned}\)

因此构造出的\(\Phi'\)同样也可以正确地计算摊分费用。

16.3-2

按照如下方式构造势函数\(\Phi\)：

\(\Phi(D_i)= \left \{\begin{aligned} &0 & & \text{if}\quad i=0 \\ &\lfloor\lg i\rfloor+3+2(i-2^{\lfloor\lg i\rfloor}) & & \text{otherwise} \end{aligned}\right.\)

不难证明\(\Phi(D_i)\ge 0\)恒成立。

考虑如下两种情况：

  • 当\(\nexists n\in \mathbb{N},i=2^n\)时，\(\Phi(D_i)-\Phi(D_{i-1})=2\)。

  • 当\(\exists n\in \mathbb{N},i=2^n\)时，\(\Phi(D_i)-\Phi(D_{i-1})=(n+3)-(n+2+2(i-1-i/2))=3-i\)。

无论哪种情况，都有\(\widehat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})=3\)。

最终有实际代价之和\(\displaystyle{T(n)=\sum_{i=1}^n c_i=\sum_{i=1}^n \widehat{c_i}-\Phi(D_n)+\Phi(D_0)=\sum_{i=1}^n 3-\Phi(D_n)+0\le 3n}\)。平均每次操作的时间复杂度为\(\dfrac{T(n)}{n}=O(1)\)。

16.3-3

堆的EXTRACT-MIN操作分成两个步骤：

  1. 弹出一个元素，这个操作的时间为\(O(1)\)。
  2. 将堆中最后一个元素放置堆顶，然后将这个元素向下移动，这个操作需要\(O(\lg n)\)的时间。假设这个过程的时间上限为\(c\lg n\)，那么\(c_i-O(1)\le c\lg n\)。

令势函数\(\Phi(D_m)\)为

\[\Phi(D_m)=\sum_{i=1}^n c\lg i\]

其中\(n\)是数据结构\(D_m\)的元素个数。

对于一个INSERT操作，有\(\widehat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})=c_i+c\lg n\)。由于INSERT操作的实际花费\(c_i=O(\lg n)\)，因此摊分后的代价仍然为\(O(\lg n)\)。

对于一个POP操作，有\(\widehat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})=c_i-c\lg n=O(1)\)。

16.3-4

根据本节正文，势函数\(\Phi(D_i)\)的定义为栈中元素的个数。所有操作的实际代价之和为\(\displaystyle{T(n)=\sum_{i=1}^n c_i=\sum_{i=1}^n \widehat{c_i}-\Phi(D_n)+\Phi(D_0)}\)。令\(\Phi(D_n)=s_n,\Phi(D_0)=s_0\)，那么有\(T(n)\le 2n-s_n+s_0\)。因此在这个情况下，所有操作的运行时间之和为\(O(n-s_n+s_0)\)。

16.3-5

实现方式和练习10.1-7完全一致：

假设有两个栈S1, S2，那么支持队列的两个操作如下进行：

  • ENQUEUE 直接将元素推入栈S2中。此操作时间复杂度为\(\Theta(1)\)。
  • DEQUEUE 将S1栈顶的元素弹出并返回即可。如果S1为空，那么弹出S2中的所有元素，一边弹出，一边将元素推入到S1中，再将元素弹出并返回。这种操作绝大多数时间下都是\(O(1)\)，如果栈S2过于庞大，那么时间开销就是S2的长度。
1
2
3
4
5
6
7
8
9
10
11
// Q.S1和Q.S2表示队列Q内部的两个栈。
ENQUEUE(Q, x)
  PUSH(Q.S2, x)

DEQUEUE(Q)
  if STACK-EMPTY(Q.S1)
    while not STACK-EMPTY(Q.S2)
      x = POP(Q.S2)
      PUSH(Q.S1, x)
  x = POP(Q.S1)
  return x

此处使用核算法来说明整个过程。对于每个进入队列的元素\(x\)，一共需要花费\(3\)美元。\(1\)美元代表着入栈Q.S2操作；剩下的\(2\)美元用于预支之后的出队操作：\(1\)美元用于将元素从栈Q.S2转移到Q.S1，\(1\)美元用于将元素从栈Q.S1弹出。

因此，所有操作支付的代价之和为\(3n\)美元，所有ENQUEUE和DEQUEUE操作的平均代价为\(\dfrac{O(n)}{n}=O(1)\)。

16.3-6

算法DELETE-LARGER-HALF的基本实现思路是，使用算法RANDOMIZED-SELECT以\(O(n)\)的时间求出第\(\lceil n/2\rceil\)数\(x\)后，这个数右边的所有数都将比\(x\)大，将这些数全部返回并从\(S\)中删除即可。

由于算法RANDOMIZED-SELECT的时间复杂度为\(O(n)\)，那么算法RANDOMIZED-SELECT的运行时间也是\(O(n)\)，假设其一次运行时间上界为\(cn\)。这里使用记账法来证明。假设将\(x\)插入\(S\)后，\(S\)中目前有\(m\)个元素，那么对第\(m\)个元素记账\(2c+1\)美元，其中\(1\)美元是插入所需要的代价，而\(2c\)美元是预支，用于DELETE-LARGER-HALF算法。由于每调用一次DELETE-LARGER-HALF后，\(S\)中的每一个元素都以\(c\)的代价被遍历，然后有一半的元素被排除出去，因此每个元素预支\(2c\)恰好能弥补某些元素被多次遍历的亏损。

最终，所有操作的代价之和不超过\((2c+1)n\)美元，因此平均到每个操作后，它们的时间复杂度为\(O(1)\)。

1
2
3
4
5
6
7
8
9
10
11
//将S视为一个数组，INSERT(S, x)算法可以简单地将x插入到S的最后一个元素。
DELETE-LARGER-HALF(S)
  n = S.size
  p = RANDOMIZED-SELECT(S, 1, n, ⌈n / 2⌉)
  B = S[p : n]
  remove S[p : n] from S
  return B

PRINT(S)
  for each u in S
    print u