算法导论7.4 Exercises 答案

7.4-1

假设\(T(n)\ge cn^2\)。那么有

\(\begin{aligned} T(n)&=\max_{q=0}^{n-1} \{T(q)+T(n-q-1)\}+\Theta(n)\\ &\ge\max_{q=0}^{n-1} \{c(q^2+(n-q-1)^2)\}+\Theta(n)\\ &=c\max_{q=0}^{n-1} \{q^2+(n-q-1)^2\}+\Theta(n)\\ \end{aligned}\)

可以发现，当\(q=0\)或\(q=n-1\)时，\(\max\)中包含的内容将达到最大，因此有

\(\begin{aligned} T(n)&\ge c\max_{q=0}^{n-1} \{q^2+(n-q-1)^2\}+\Theta(n)\\ &=c(n-1)^2+\Theta(n)\\ &= cn^2-2cn+c+\Theta(n)\\ &\ge cn^2-2cn+\Theta(n)\\ &= cn^2-(2cn-\Theta(n))\\ &\ge cn^2&\qquad(A) \end{aligned}\)

其中步骤\((A)\)假设了\(2cn\)渐进上界比\(\Theta(n)\)大。

令\(c=\min(1,T(1)),n_0=1\)。由于\(T(1)\ge c\ge cn^2\)，那么由数学归纳法，结论\(T(n)=\Omega(n^2)\)成立。

7.4-2

可以知道，最好运行时间\(T'(n)\)的递推式满足\(\displaystyle{T'(n)=\min_{q=0}^{n-1} \{T(q)+T(n-q-1)\}+\Theta(n)}\)。假设\(T'(n)\ge cn\lg n\)，那么有

\(\begin{aligned} T(n)&=\min_{q=0}^{n-1} \{T(q)+T(n-q-1)\}+\Theta(n)\\ &\ge\min_{q=0}^{n-1} \{cq\lg q+c(n-q-1)\lg(n-q-1)\}+\Theta(n)\\ &=c\min_{q=0}^{n-1} \{q\lg q+(n-q-1)\lg(n-q-1)\}+\Theta(n)\\ \end{aligned}\)

将最后一行\(\max\)中的内容对\(2\)取指数，得到\(2^{q\lg q+(n-q-1)\lg(n-q-1)}=q(n-q-1)\cdot 2^{n-1}\)。可以发现，当\(q=\dfrac{n-1}{2}\)时，这个式子才能取到最小值。不过为了方便证明，如果\(T(n)\)大于等于其中的非最小值，那么\(T(n)\)一定大于等于其中的最小值，因此令\(q=\dfrac{n}{2}\)，有：

\(\begin{aligned} T(n)&\ge c\min_{q=0}^{n-1} \{q\lg q+(n-q-1)\lg(n-q-1)\}+\Theta(n)\\ &\ge c(n/2\cdot \lg(n/2)+(n/2-1)\lg(n/2-1))+\Theta(n)\\ &\ge c(n/2\cdot \lg(n/2)+(n/2-1)(\lg(n/2)-1))+\Theta(n) &\qquad(A)\\ &=cn\lg n-c\lg n+2c-\dfrac{3c}{2}n+\Theta(n)\\ &=cn\lg n-\left(\dfrac{3cn}{2}+c\lg n-2c-\Theta(n)\right)\\ &\ge cn\lg n & \qquad(B) \end{aligned}\)

其中，步骤\((A)\)使用了假设\(x\ge 2\rightarrow \lg(x-1)\ge \lg x-1\)，即\(n\ge 4\)，步骤\((B)\)假设了\(\dfrac{3cn}{2}+c\lg n-2c\)的渐进增长要高于\(\Theta(n)\)（只要\(c\)大到恰到好处）。

因此，只需要假设\(n\ge 4\)，并且\(c\)取值足够大。那么由数学归纳法，结论\(T(n)=\Omega(n\lg n)\)成立。

7.4-3

令\(f(q)=q^2 + (n - q - 1)^2\)，那么\(f'(q)=4q-2n+2,f''(q)=4\)。当\(f'(q)=0\)时，\(q=\dfrac{n-1}{2}\)。因此\(f(q)\)在区间\(\left[0,\dfrac{n-1}{2}\right]\)上递减，在\(\left[\dfrac{n-1}{2},n-1\right]\)上递增。因此\(f\)在\(0\)或者是\(n-1\)上取到最大值。

7.4-4

类似的，假设随机变量\(X\)是算法RANDOMIZED-QUICKSORT所进行的比较次数，那么按照书上的结论，有：

\(\begin{aligned} E[X]&= \sum_{i=1}^{n-1}\sum_{j=i+1}^n \dfrac{2}{j-i+1}\\ &= \sum_{i=1}^{n-1}\sum_{k=1}^{n-i} \dfrac{2}{k+1}\\ &\ge \sum_{i=1}^{n-1}\sum_{k=1}^{n-i} \dfrac{2}{2k}&\qquad(A)\\ &=\sum_{i=1}^{n-1} \Omega(\lg n)\\ &=\Omega(n\lg n) \end{aligned}\)

其中，步骤\((A)\)是因为当\(k\ge 1\)时，\(\dfrac{1}{k+1}\ge \dfrac{1}{2k}\)成立。

因此，整个算法的期望运行时间为\(\Omega(n\lg n)\)。

7.4-5

按照递归树的思想，如果数组长度小于等于\(k\)时停止递归，那么整个递归树的高度为\(\lg (n/k)\)，并且每一层所调用的划分算法的运行时间之和为\(O(n)\)。因此，快速排序部分的运行时间为\(\lg(n/k)\cdot O(n)=O(n\lg (n/k))\)。

当\(n\le k\)时，算法终止递归，由于子问题不重叠，因此划分出的叶节点大约有\(\dfrac{n}{k}\)个。根据插入排序算法的时间复杂度\(O(n^2)\)。因此，插入排序部分的时间为\(\dfrac{n}{k}\cdot O(k^2)=O(nk)\)。

因此，总共的时间复杂度之和为\(O(nk+n\lg(n/k))\)。

如果不考虑不同算法之间的常数步骤耗费时间，那么令\(f(k)=nk+n\lg(n/k)\)。

那么有\(f'(k)=n-\dfrac{n}{k\ln 2},f''(k)=\dfrac{n}{k^2\ln 2}\)。当\(f'(k)=0\)时，有\(k=\dfrac{1}{\ln 2}\)。此时\(f(k)\)在\(k=\dfrac{1}{\ln 2}\)处取到最小值。因此\(k=\dfrac{1}{\ln 2}\)。

如果考虑不同算法之间的常数步骤耗费时间，那么\(k\)需要通过实验来分析取得。

\(\star\) 7.4-6

不失一般性，假设\(\alpha\le\dfrac{1}{2}\)，因为当\(\beta=1-\alpha\)时，划分情况一致。

假设这个数组的\(n\)个元素都不相同，随机选取\(3\)个数，那么有\(\dbinom{n}{3}\)种选法。其中，第\(i\)小的数成为最终的支点的支点的选法有\((i-1)\cdot (n-i)\)种，因为比\(i\)小的数有\(i-1\)种选法，比\(i\)大的数有\(n-i\)种选法。令\(p(n,i)=\dfrac{6(i-1)(n-i)}{n(n-1)(n-2)}\)表示第\(i\)小的元素最终成为支点的概率。

划分的元素是第\(i\)小时，只有当\(j\)满足\(i\le j\le n+1-i\)时，以\(j\)划分才不会更坏，这样的\(j\)的概率占比之和为：

\(\displaystyle{g(n,i)=\sum_{j=i}^{n+1-i} p(n,j)}=\dfrac{(2 - 2 i + n) (-2 i^2 + n(n-5) + 2 i (2 + n))}{n(n-1)(n-2)}\)

考虑去除\(g(n,i)\)分子分母中的所有非三次项（即低阶项），得到\(h(n,i)\)，并令\(\alpha=\dfrac{i}{n}\)回代到\(h(n,i)\)中，得到\(p(\alpha)=(1-2\alpha)(1+2\alpha-2\alpha^2)\)。