算法导论7.2 Exercises 答案

7.2-1

假设$T(n)\le cn^2-d$，那么有

针对$f(n)=\Theta(n)$，可以知道$\exists c_0,n_0>0,\forall n\ge n_0,0\le n\le c_0n$成立。因此假设$n\ge n_0$，那么有

$\begin{aligned}
T(n)&=T(n-1)+\Theta(n)\
&\le c(n-1)^2-d+c_0n\
&\le cn^2-2cn+c-d+c_0n\
&= cn^2-(d-c)-(2cn-c_0n)\
&\le cn^2-(2cn-c_0n)&\qquad(A)\
&\le cn^2&\qquad(B)
\end{aligned}$

其中，步骤$(A)$假设了$d\ge c$成立。步骤$(B)$假设了$2c\ge c_0$。最终，由数学归纳法，原结论$T(n)=O(n^2)$成立。

假设$T(n)\ge c’n^2$，那么有

$\begin{aligned}
T(n)&=T(n-1)+\Theta(n)\
&\ge c’(n-1)^2+\Theta(n)\
&= c’n^2-2c’n+c’+\Theta(n)\
&\ge c’n^2-2c’n+\Theta(n)\
&= c’n^2-(2c’n-\Theta(n))\
&\ge c’n^2&\qquad(A)
\end{aligned}$

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

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

因此，最终得到$T(n)=\Theta(n^2)$。

7.2-2

$\Theta(n^2)$，因为每一次的划分都会将所有元素划分到同一侧。每进行一层递归只划分出了一个空数组和一个长度为$n-1$的数组。因此根据题目7.2-1的结论，时间复杂度为$\Theta(n^2)$。

7.2-3

由于序列已经排好序，因此算法PARTITION每次选择的支点都将会是最小值。最终算法PARTITION完成后，支点到达了最左端，并且所有元素都在右侧，依然保持降序。和题目7.2-2一样，每进行一层递归只划分出了一个空数组和一个长度为$n-1$的数组。因此根据题目7.2-1的结论，时间复杂度为$\Theta(n^2)$。

7.2-4

以下是插入排序算法的代码：

INSERTION-SORT(A, n)
  for i = 2 to n
    key = A[i]
    j = i – 1
    while j > 0 and A[j] > key
      A[j + 1] = A[j]
      j = j – 1
    A[j + 1] = key

考虑使用逆序数$I$来衡量一个序列的排序程度。如果逆序数越小，可以认为排序程度越小。

根据题目2-4-c的结论，插入排序的时间复杂度为$O(n+I)$。如果逆序数越小，说明插入排序的效率越高。

如果一个序列$A$排序程度越高，那么在使用算法PARTITION进行划分时，在$A[p:r]$取到的支点$A[r]$可能在$A[p:r]$中是比较接近最大值的。那么最终划分完成后，左侧元素数量比右侧多很多，从而划分情况不是特别理想。此时糟糕的划分将会导致快速排序算法效率不会太好。

因此，总而言之，对一个接近排序的数组进行排序使用插入排序效果比快速排序好。

7.2-5

不失一般性，假设分得的$\alpha$一直在左侧，否则可以旋转整个区间。

那么，递归树的左侧深度是满足最小的$h$，使得$n\cdot\alpha ^h\le 1$成立，从而得到$h\ge \log{\alpha} 1/n$。经过对数的变换，最终得到$h\ge \log{1/\alpha} n$。因此最浅的叶子节点高度为$h\ge \log{1/\alpha} n$。同理，可以计算出最深叶子节点高度为$\log{1/\beta} n$。

7.2-6

由于所有排列出现的概率都均等，因此出现在数组$A$最后一个数的概率是均等的。对于一个长度为$n$的数组，如果最后一个数是第$i$小的，那么使用算法PARTITION进行划分后，将会有$i$个元素在左侧（包括支点），$n-i$个元素在右侧，划分比例为$\dfrac{i}{n}:\dfrac{n-i}{n}$。可以发现，当$j=n+1-i$时，划分比例是一样的。

因此，不失一般性，仅仅考虑$i\le n/2$时的情况。划分的元素是第$i$小时，只有当$j$满足$i< j< n+1-i$时，以$j$划分才会更均匀，这样的$j$一共有$n+1-i-i-1=n-2i$个，占比$\dfrac{n-2i}{n}=1-\dfrac{2i}{n}$。

因此令$\alpha=i/n$。对于任意常数$\alpha$产生比$1-\alpha:\alpha$更好的划分的概率为$1-2\alpha$。