（小顺序统计量）要在n个数中选出第i个顺序统计量，SELECT在最坏情况下需要的比较次数T(n)满足T(n) = (n)。但是，隐含在记号中的常数项是非常大的。当 i 相对于n来说很小时，我们可以实现一个不同的算法，它以SELECT作为子程序，但在最坏情况下所做的比较次数更少。

a.设计一个能用  次比较在n个元素中找出第i小元素的算法，其中，

（提示：从  个不相交对的两两比较开始，然后对由每对中的较小元素构成的集合进行递归。）

b.证明：如果  ，则有  。

c.证明：如果 i 是小于  的常数，则有  。

d.证明：如果对所有  有  ，则  。

a.这一问属实蛋疼，因为你需要知道  中每项对应的含义，该问的回答借鉴了以下两个回答，感兴趣也可以了解一下：

算法导论第二版9-3那个思考题如何解答？ - 牛肉豆腐干的回答 - 知乎

算法导论第二版9-3那个思考题如何解答？ - 知乎

0、对  进行拓展，不仅是在n个元素中找出第i小元素，还通过该元素运行了一次PARTITION，即  找到了n个元素中最小的i个元素的集合

1、如图所示（这里n = 13，i = 3），首先将n个元素组成不相交的对并进行比较，图中较大的元素在第一行，较小的元素在第二行，该步骤比较次数为 ，即表达式中第一项

2、如存在未经比较的元素，虚构一个元素-inf与其组对，对所有元素对中按其中较小元素运行 ，找到较小元素集中第i小（无未经比较元素时）或i+1（有未经比较元素时）的元素（即图中黑点），以及所有比其小的元素，该步骤的比较次数为 ，即表达式中第二项

ps 其实这里只需要对已成对元素进行比较就行了，这里虚构-inf是为了凑比较次数里的向上取整，但是稍麻烦了些

3、如果有未经比较元素，将其加入虚线Z块。不难发现，图中虚线Z块中除未经比较元素外，所有元素均小于步骤2中选择的较小元素集中第i小的元素（图中黑点）；Z块外所有元素均大于步骤2中选择的较小元素集中第i小的元素（图中黑点），可知，第i小的元素必然位于Z块中。再对Z块中的所有元素运行 ，因为Z块中的元素规模不超过2i，而查找的为i，因此该步骤的比较次数为T(2i)

综上可得到  的表达式

b.首先明确，i < n/2时，表达式第二部分会运行  次，然后运行依次第一部分

于是  

c.i是常数时，b表达式中T(2i)和均退化为常数，因此有 

d.代入b中可证明