算法导论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)$。