算法导论7.2 Exercises 答案

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

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

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

1
2
3
4
5
6
7
8
9
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\)。