算法导论第三版习题7.4

7.4-1

我们可以猜测 T(n)≥cn2 ：

T(n)≥max0≤q≤n−1[cq2+c(n−q−1)2]+Θ(n)=max0≤q≤n−1[cq2+c(n−q−1)2]+Θ(n)=cn2−2cn+c+Θ(n)≥cn2−2cn+Θ(n)≥cn2

最后一步可以使 c 为恰当的数，与 Θ(n) 抵消得到。

7.4-2

在最好的情况下，数组每次都被分成 ⌊n/2⌋和⌈n/2⌉−1 规模的两个字问题，故算法的复杂度为

T(n)=T(⌊n/2⌋)+T(⌈n/2⌉−1)+Θ(n)

假设 T(n)≥cnlgn :

T(n)≥c⌊n/2⌋lg⌊n/2⌋+c(⌈n/2⌉−1)lg(⌈n/2⌉−1)+Θ(n)≥cn/3lg(n/3)+cn/3lg(n/3)+Θ(n)≥2cn/3lgn−2cnlg3+Θ(n)≥2cn/3lgn

最后一步可以令 2cnlg3 足够大使 2cnlg3−Θ(n)<0 从而使不等式成立。故 T(n)=Ω(nlgn)

7.4-3

直接对 q2+(n−q−1)2 对 q 求导并使导数为0可求得 q=(n−1)/2 ，故该二次函数的最小值在区间的正中间，那么最大值就在区间的两个端点上取得。

7.4-4

同样的，

E(X)=∑i=1n−1∑j=i+1n2j−i+1=∑i=1n−1∑k=1n−i2k+1≥∑i=1n−1∑k=1n−i22k=∑i=1n−1Ω(lgn)=Ω(nlgn)

7.4-5

此时快速排序的层数为 n⋅(12)x≤k 的解 lgnk ，则快速排序阶段的时间复杂度为 O(nlgnk) ;
然后进行插入排序，由于只有每个长度小于 k 的子数组内部没有排序，所以在插入排序过程中，每个元素不再需要和它前面所有的元素相比较，而最多只需要比较 k 次，一共有 n 个元素，所以插入排序过程的时间复杂度为 O(nk) ，总的时间复杂度为 O(nk+nlgnk)

7.4-6

要使最坏划分比例为 a:(1−a) ，则必须选出的三个数至少有两个是在数组的前面 an 个数中，故概率是 C23a2=3a2