7.2-1
假设 ,那么有
针对 ,可以知道 成立。因此假设 ,那么有
其中,步骤 假设了 成立。步骤 假设了 。最终,由数学归纳法,原结论 成立。
假设 ,那么有
其中步骤 假设了 渐进上界比 大。
令 。由于 ,那么由数学归纳法,结论 成立。
因此,最终得到 。
7.2-2
,因为每一次的划分都会将所有元素划分到同一侧。每进行一层递归只划分出了一个空数组和一个长度为 的数组。因此根据题目 7.2-1 的结论,时间复杂度为 。
7.2-3
由于序列已经排好序,因此算法 PARTITION
每次选择的支点都将会是最小值。最终算法 PARTITION
完成后,支点到达了最左端,并且所有元素都在右侧,依然保持降序。和题目 7.2-2 一样,每进行一层递归只划分出了一个空数组和一个长度为 的数组。因此根据题目 7.2-1 的结论,时间复杂度为 。
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
|
考虑使用逆序数 来衡量一个序列的排序程度。如果逆序数越小,可以认为排序程度越小。
根据题目 2-4-c 的结论,插入排序的时间复杂度为 。如果逆序数越小,说明插入排序的效率越高。
如果一个序列 排序程度越高,那么在使用算法 PARTITION
进行划分时,在 取到的支点 可能在 中是比较接近最大值的。那么最终划分完成后,左侧元素数量比右侧多很多,从而划分情况不是特别理想。此时糟糕的划分将会导致快速排序算法效率不会太好。
因此,总而言之,对一个接近排序的数组进行排序使用插入排序效果比快速排序好。
7.2-5
不失一般性,假设分得的 一直在左侧,否则可以旋转整个区间。
那么,递归树的左侧深度是满足最小的 ,使得 成立,从而得到 。经过对数的变换,最终得到 。因此最浅的叶子节点高度为 。同理,可以计算出最深叶子节点高度为 。
7.2-6
由于所有排列出现的概率都均等,因此出现在数组 最后一个数的概率是均等的。对于一个长度为 的数组,如果最后一个数是第 小的,那么使用算法 PARTITION
进行划分后,将会有 个元素在左侧(包括支点), 个元素在右侧,划分比例为 。可以发现,当 时,划分比例是一样的。
因此,不失一般性,仅仅考虑 时的情况。划分的元素是第 小时,只有当 满足 时,以 划分才会更均匀,这样的 一共有 个,占比 。
因此令 。对于任意常数 产生比 更好的划分的概率为 。