存在可供选择的线性时间确定性算法。我读过这个链接，分而治之的方法的递归看起来像：T(n(<=12n/5+T(n/5(+T(7n/10(
然而，我不明白为什么它必须是t(7n/10(。链接本身提到，分区的每一半都有大小(3n/10(，因此算法在(6n/10(上递归。即使我们包括中值组中的5个元素，递归也在(6n/10+5(上。我确实理解7n/10是递归大小的有效上界，但这里的上界不是太弱了吗？
7n/10不是3n/10 + 3n/10 + n/10的结果；它来自于做CCD_ 3。
来自链接：
用丢弃的元素(不包括在调用中(来谈论这一点更容易。
参数是递归调用是在由而非组成的较短列表上进行的，该列表包括一些元素。通过显示至少3n/10元素被从列表中排除，可以得出最多7n/10元素被包括在内，并且该界是紧的，因为3n/10界是紧。
因此，通过表明L1和L3各自包含来自n/10子集中的每一个子集的至少3个元素，表明它们都具有至少3n/10的大小；则L1或L3中的一个被从递归调用中排除并给出结果。由于L1或L3中只有一个被排除在外，而不是两者都被排除在一起，因此将它们的大小相加是没有意义的。