算法导论10 Problems 答案

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

10-1

\(\begin{array}{|c|c|c|c|c|} \hline &\text{unsorted, singly linked} & \text{sorted, singly linked} & \text{unsorted, doubly linked} & \text{sorted, doubly linked}\\ \hline \text{SEARCH}&\Theta(n)&\Theta(n)&\Theta(n)&\Theta(n)\\ \hline \text{INSERT}&\Theta(1)&\Theta(n)&\Theta(1)&\Theta(n)\\ \hline \text{DELETE}&\Theta(n)&\Theta(n)&\Theta(n)&\Theta(n)\\ \hline \text{SUCCESSOR}&\Theta(n)&\Theta(1)&\Theta(n)&\Theta(1)\\ \hline \text{PREDECESSOR}&\Theta(n)&\Theta(n)&\Theta(n)&\Theta(1)\\ \hline \text{MINIMUM}&\Theta(n)&\Theta(1)&\Theta(n)&\Theta(1)\\ \hline \text{MAXIMUM}&\Theta(n)&\Theta(n)&\Theta(n)&\Theta(1)\\ \hline \end{array}\)

为了维持整个序列有序，插入时需要查找到合适的位置才能插入，需要耗费的时间也比较大。

求最大值时，它在有序单向链表上是最后一个元素，因此是\(\Theta(n)\)的时间。但是，如果有序单向链表\(L\)多维护一个尾指针，那么也可以改成\(\Theta(1)\)。

10-2

假设实现时\(L\)是一个单链表。

a

  • MAKE-HEAP: 产生一个空列表，仅仅需要\(O(1)\)的时间。
  • INSERT: 遍历整个链表，查找到适当的元素插入，需要\(O(n)\)的时间。
  • MINIMUM, EXTRACT-MIN: 直接返回头节点；如果有需要，那么返回并删除头节点，仅仅需要\(O(1)\)的时间。
  • UNION: 使用归并排序的合并步骤完成这两个链表的合并，需要\(O(n)\)的时间。

b

  • MAKE-HEAP: 产生一个空列表，仅仅需要\(O(1)\)的时间。
  • INSERT: 直接在头部插入新元素，仅仅需要\(O(1)\)的时间。
  • MINIMUM, EXTRACT-MIN: 遍历整个链表找到值最小的节点并返回；如果有需要，那么删除这个节点，整个过程需要\(O(n)\)的时间。
  • UNION: 直接遍历到其中一个链表的末尾，并接上另一个链表的头部即可，整个过程需要\(O(n)\)的时间。

c

问题10-2-b中的解答没有对元素的唯一性做出限制，本题的解答和问题10-2-b的完全一致。

10-3

a

对于算法COMPACT-LIST-SEARCH，它通过多次执行跳跃来接近目标值\(k\)，直到达到目标直接点\(k\)，如果跳跃失败了，第8行的代码表明它仍然能前进；

对于算法COMPACT-LIST-SEARCH'，它先执行固定次数\(t\)次的跳跃，然后在最后一步跳到的节点遍历链表，寻找目标值\(k\)。

因此两个算法的功能是一致的，返回的内容将会相同。

需要注意的是，算法COMPACT-LIST-SEARCH相比算法COMPACT-LIST-SEARCH'，while循环第8行代码多出了一个i = next[i]。如果算法COMPACT-LIST-SEARCH'在\(t\)次迭代完成后仍然找不到\(k\)，那么就需要依靠下面的while循环继续查找。由于已经假设了RANDOM结果在两个算法中返回的结果是一样的，也就是说，两个算法的跳跃记录都是一样的，因此算法COMPACT-LIST-SEARCH的while循环执行次数不超过算法COMPACT-LIST-SEARCH'的while, for循环执行次数之和。

b

算法COMPACT-LIST-SEARCH′的for循环执行了恰好\(t\)次，每次循环的步骤仅需花费常数时间；while循环仅需执行\(X_t\)次。因此算法COMPACT-LIST-SEARCH'的平均时间复杂度为\(O(t+E[X_t])\)。

c

根据C.28式，得到$ $。

考虑概率值\(\Pr\{X_t\ge r\}\)。算法COMPACT-LIST-SEARCH'的第3行代码相当于进行\(t\)次重复实验，并且要求每一次抽取出来的\(j\)都需要满足\(j\)所在的节点和\(k\)的距离都要大于等于\(r\)，这样的节点一共有\(n-r\)个，因此进行一次实验满足这个条件的概率为\(\dfrac{n-r}{n}=1-\dfrac{r}{n}\)；如果\(t\)次都要满足，那么概率值为\(\left(1-\dfrac{r}{n}\right)^t\)，即\(\Pr\{X_t\ge r\}=\left(1-\dfrac{r}{n}\right)^t\)。

因此，最终有\(\displaystyle{E[X_t]=\sum_{r=1}^n\left(1-\dfrac{r}{n}\right)^t}\)。

实际上，个人认为这个题目并不严谨，应该是\(\displaystyle{E[X_t]\le\sum_{r=1}^n\left(1-\dfrac{r}{n}\right)^t}\)才正确。因为节点\(k\)并不总是会在链表的最后一个节点。

d

由于\(t>0\)，因此函数\(f(r)=r^t\)在\(r\ge0\)处是单调递增的。那么根据A.18式，有

\[\sum_{r=0}^{n-1} r^t\le \int_{0}^{n} r^t dr=\left.\dfrac{r^{t+1}}{t+1}\right|_{0}^{n}=\dfrac{n^{t+1}}{t+1}\]

e

\(\begin{aligned} E[X_t]&=\sum_{r=1}^n\left(1-\dfrac{r}{n}\right)^t\\ &=\dfrac{1}{n^t}\sum_{r=1}^n (n-r)^t\\ &=\dfrac{1}{n^t}\sum_{s=0}^{n-1} s^t & \qquad (A)\\ &\le \dfrac{1}{n^t} \cdot \dfrac{n^{t+1}}{t+1} \\ &=\dfrac{n}{t+1} \end{aligned}\)

其中，步骤\((A)\)则是由等式A.13而来，仅仅将索引进行了变换。

f

由于\(E[X_t]\le\dfrac{n}{t+1}\le \dfrac{n}{t}\)，那么再根据题目10-3-b的结论就可以得到算法t COMPACT-LIST-SEARCH'的时间复杂度为\(O(t+n/t)\)。

g

当\(t=\sqrt{n}\)时，算法COMPACT-LIST-SEARCH'的时间复杂度为\(O(\sqrt{n})\)。并且根据题目10-3-a的结论，算法COMPACT-LIST-SEARCH'的循环次数超过了算法COMPACT-LIST-SEARCH，因此算法COMPACT-LIST-SEARCH的时间复杂度同样为\(O(\sqrt{n})\)。

h

如果元素并不满足唯一性，那么当算法COMPACT-LIST-SEARCH开始随机选择下一跳时，它将不能够选择和自身相同的值（否则，有可能会跳到之前的节点），为此，和当前节点键相等的后续一些节点将会被跳过，这违背了后续节点被均匀选择的假设，因此题目10-3-c的结果将不再适用。