给出一个能找出某一集合的是分位数的 O(nlgk) 时间的算法

Question

9.3-6
The k-th quantiles Of an n-element set are the k - 1 order statistics that divide the sorted set into k equal-sized sets (to within l).
Give an O(n lg k)-time algorithm to list the k-th quantiles of a set.

中文翻译：
对一个包含 n 个元素的集合来说 ， k 分位敢是指能把有序集合分成 h 个等大小集合的第
k-1个顺序统计量。给出一个能找出某一集合的是分位数的 O(nlgk) 时间的算法。

我的想法是进行二分，每次找中位数。可话说，那个时间复杂度为什么是O(n lg k)呢？其中找中位数的最优时间复杂度是O(n)。

附录：
分位数（英语：Quantile），亦称分位点，是指将一个随机变量的概率分布范围分为几个等份的数值点，常用的有中位数（即二分位数）、四分位数、百分位数等。

四分位数：
https://zh.wikipedia.org/wiki...
即把所有数值由小到大排列并分成四等份，处于三个分割点位置的数值就是四分位数。
一个算法如下（可以兼用TI-83计算器）：
利用中位数使数据分成两列（不要把中位数放入已分好的数列），
第一四分位数为第一组数列的中位数；第三四分位数为第二组数列的中位数。

Answer 1

输入始终是已排序的集合，此时找中位数应该是 O(1)

3. if k is odd

此时不能把下面的数据 等分 成两份，而是要分成相差1的两份。比如k是5时，分成一边2一边3，再递归下去。

T(n, k) = ...

对应分析中的2和3，这两种情况中都会得到两个（把n/2大小分成k/2份）的子问题