算法导论8.1 Exercises 答案

8.1-1

当\(a\)具有单调性，即\(a_1\le a_2\le \dots\le a_n\)或\(a_1\ge a_2\ge \dots\ge a_n\)时，这时仅需要\(n-1\)次决策决定出这个序列，其深度为\(n-1\)。

8.1-2

可以发现，函数\(f(x)=\lg x\)是单调递增函数。因此根据不等式\(A.18\)，有

\(\begin{aligned} \lg n! =\sum_{k=1}^{n} \lg k \le \int_{1}^{n+1} \lg x dx = \left. x\lg x-\dfrac{x}{\ln 2}\right|_1^{n+1} = (n+1)\lg (n+1)-\dfrac{n}{\ln 2} \le (n+1)\lg (n+1) \end{aligned}\)

同时有

\(\begin{aligned} \lg n! =\sum_{k=1}^{n}\lg k=\sum_{k=2}^{n}\lg k \ge \int_{1}^{n} \lg x dx = \left. x\lg x-\dfrac{x}{\ln 2}\right|_1^{n} = n\lg n-\dfrac{n-1}{\ln 2} \end{aligned}\)

因此可以得出\(\lg n! = \Theta(n\lg n)\)。

8.1-3

至少\(\dfrac{n!}{2}\)个叶节点的树的高度\(h\)满足\(2^h\ge l\ge \dfrac{n!}{2}\)，可以得到\(h\ge \lg n!-1=\Theta(n\lg n) - 1=\Theta(n\lg n)\)。由此可知，不存在排序算法使得至少一半的排列拥有线性排序的算法。

类似的，至少\(\dfrac{1}{n}\cdot n!\)个叶节点的树的高度\(h\)满足\(2^h\ge l\ge (n-1)!\)，可以得到\(h\ge \lg (n-1)!=\Theta((n-1)\lg (n-1)) -=\Theta(n\lg n)\)。得出的结论与之前相同。

至少\(\dfrac{1}{2^n}\cdot n!\)个叶节点的树的高度\(h\)满足\(2^h\ge l\ge \dfrac{n!}{2^n}\)，可以得到\(h\ge \lg n! - n=\Theta(n\lg n)-n =\Theta(n\lg n)\)。得出的结论与之前仍然相同。

8.1-4

为了方便进行分析，假设长度\(n\)是\(4\)的倍数。

那么对于每个第\(k\)小（注意\(k\)是\(4\)的倍数），那么除了最后一个元素仅有\(2\)种，每个元素都有\(3\)种选择。剩下的\(3n/4\)个元素任意排列，因此这种序列一共有\((3n/4)!\cdot 3^{n/4-1}\cdot2\)个。哪怕忽略掉不符合这些条件的序列，这\((3n/4)!\cdot 3^{n/4-1}\cdot2\)个叶节点，组成的决策树的高度\(h\)至少为\(2^h\ge l\ge (3n/4)!\cdot 3^{n/4-1}\cdot2\)。即\(h\ge 3n/4 \lg(3n/4)+(n/4-1)\lg3+1\)，最终得到\(h= \Omega(n\lg n)\)。

因此，如果这种排序算法，它的时间复杂度依然有下界\(\Omega(n\lg n)\)。