算法导论第七章习题答案（第三版） Introduction to Algorithm
Exercises
7.1-1.略。
7.1-2.
返回的q值等于r，当数组中所有元素都相同时，可以将等于主元的值轮流放到两个集合中。
7.1-3
for循环正好是Θ(n)的复杂度，所以PARTITION的时间复杂度是Θ(n)。
7.1-4.略。
7.2-1
\[T(n) = T(n – 1) + \Theta (n) = c{n^2} – (2cn – 1 – bn)\]
当c>b时，2cn-1-bn>0,当c<b/2时，2cn-1-bn<0，所以上式的时间复杂度是Θ(n2)。
7.2-2
Θ(n2)。
7.2-3
降序排列的话，会导致每一次划分都是最坏情况，所以时间复杂度是Θ(n2)。
7.2-4
因为银行的支票编号基本上都是有序的，插入排序只需插入最小的元素即可，而对于快速排序来说，这已经接近最坏情况，所以INSERTION-SORT的性能往往要优于QUICKSORT。
7.2-5
画出递归树即可求得。
7.2-6
若按α:1-α的比例来划分的话，左子树拥有元素个数是nα，右子树是(1-α)n，所以若想得到更平衡的划分，共有(1-α)n-nα中可能，所以概率为((1-α)n-nα)/n。
7.3-1
因为随机化算法的目的是减小期望的运行时间，而去降低最坏运行时间的概率。
7.3-2
随机数生成器RANDOM被调用的次数就为选出主元的次数，所以无论是最好还是最坏情况，被调用的次数都为Θ(n)。
7.4-1.略。
7.4-2
最好情况下：
\[T(n) = 2T(\frac{n}{2}) + \Theta (n)\]
可计算出快速排序的运行时间为Ω(nlgn)。
7.4-3
数学问题，计算即可。
7.4-4.略。
7.4-5
显然根据递归树等的分析即可证出该式。至于k的选择，这是在网上找的大神的分析：
7.4-6
Thinking Problems
7-1
a.略。
b.一旦进入循环，i和j的值就会加1或者减1，所以永远不会访问子数组以外的元素。
c.因为永远不会访问数组以外的元素，所以返回的时候j仍是在[p,r]之间，所以p≤j<r,因为A[i]=A[p]，观察循环可以得知至少要循环两遍，所以j不能等于r。
d.用循环不变式证明即可。
e.略。
7-2
a.Θ(n2)。
b.在partition的过程中，记录等于A[q]的个数count，在结尾返回t的值即为q+count。
c.略。(稍微改动即可)。
d.p到t中的元素不用参与下一次的比较。
7-3
a.E[Xi]=1/n。
b.该式的意思就是利用指示器随机变量，将所有情况列出和，再求出期望。
c.因为T(q-1)和T(n-q)在q=1…n的区间中，有重复的值，所以\(\sum\limits_{q = 1}^n {(T(q – 1) + T(n – q)} ) = 2\sum\limits_{q = 2}^n {(T(q)} \)
将q=1，2归入后面的Θ(n)中………这时候结果已经很显然了。
d.拆开之后根据级数和不等式的知识即可证明。
e.此时结果已经很显然了。
7-4
a.略。
b.最坏情况划分即为下次递归调用的比上一次少1。这样，栈的深度即为n。
c.可以随机化选择主元。也可以通过比较划分之后的两个子数组去选择较小的数组去递归，留大的子数组去循环。
7-5
a.\[{p_i} = \frac{{(i – 1)(n – i)}}{{C_n^3}}\]
b.用上式所求的期望与1/n做比即可求得（数学能力不好，还望广大网友告知计算方法）。
c.\[lim_{n \to \infty } \frac{1}{n}\sum_{i=\frac{n}{3}}^{\frac{2n}{3}} \frac{6(i-1)(n-i)}{n^2} = \int_{\frac{1}{3}}^{\frac{2}{3}} 6x(1-x) dx = \frac{13}{27}\]
d.递归树的高度是不变的，只是使递归树划分的更加均匀而已，所以只会影响时间复杂度的常数因子。
7-5
区间的模糊排序只是为了能在各个区间里找到数，使其能组成一个排序序列，所以，区间里有重合的部分即可视为相等，共分为三段。这样题目结果就很显然了。
（若有错误和不足，欢迎大家积极指正！）