在寻找第 k 小元素时，将原数组分为 5 个一组，分成3，4， 6，7 个一组可以吗?

之前有童鞋问到这个问题，这里回答一下。

首先剔除偶数个，因为偶数不方便找中间元素，现在考察3和7是否可以？先看一下寻找第k小元素的复杂度（最差情况下）是由下式子（参考视频“4.3分治寻找第k小元素”）：

其中第1项是递归解决‘寻找中项的中项’的复杂度，第2项是对原问题划分的左边部分或者右边部分进行递归的复杂度。

视频“3.6 递归之几种特殊形式的复杂度”指出对于这种形式的复杂度，取决于等式右边第1项和第2项的系数，如果这两项系数之和小于1，则复杂度为\Theta(n)，如果系数之和等于1，则复杂度为\Theta(n\log n)。当分成5个一组时，上式系数之和为1/5+3/4 < 1。所以复杂度为为\Theta(n)。

7个一组的类似分析，结论可以。