算法导论 7.2 Exercises 答案

7.2-1

假设 T(n)cn2d,那么有

针对 f(n)=Θ(n),可以知道 c0,n0>0,nn0,0nc0n 成立。因此假设 nn0,那么有

T(n)=T(n1)+Θ(n)c(n1)2d+c0ncn22cn+cd+c0n=cn2(dc)(2cnc0n)cn2(2cnc0n)(A)cn2(B)

其中,步骤 (A) 假设了 dc 成立。步骤 (B) 假设了 2cc0。最终,由数学归纳法,原结论 T(n)=O(n2) 成立。

假设 T(n)cn2,那么有

T(n)=T(n1)+Θ(n)c(n1)2+Θ(n)=cn22cn+c+Θ(n)cn22cn+Θ(n)=cn2(2cnΘ(n))cn2(A)

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

c=min(1,T(1)),n0=1。由于 T(1)ccn2,那么由数学归纳法,结论 T(n)=Ω(n2) 成立。

因此,最终得到 T(n)=Θ(n2)

7.2-2

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

7.2-3

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

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

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

那么,递归树的左侧深度是满足最小的 h,使得 nαh1 成立,从而得到 hlogα1/n。经过对数的变换,最终得到 hlog1/αn。因此最浅的叶子节点高度为 hlog1/αn。同理,可以计算出最深叶子节点高度为 log1/βn

7.2-6

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

因此,不失一般性,仅仅考虑 in/2 时的情况。划分的元素是第 i 小时,只有当 j 满足 i<j<n+1i 时,以 j 划分才会更均匀,这样的 j 一共有 n+1ii1=n2i 个,占比 n2in=12in

因此令 α=i/n。对于任意常数 α 产生比 1α:α 更好的划分的概率为 12α