推导中位数的中位数算法时间复杂度为O(nlogn)，错在哪里？

你给出的推导存在两个核心错误，导致得出了错误的O(nlogn)结论：

1. 完全遗漏了算法的核心递归步骤 #

中位数的中位数算法的完整流程不仅包含递归寻找中位数的中位数，还包含以下关键步骤，你完全没纳入时间复杂度计算：

• 将原数组划分为5个元素一组后，每组排序找中位数的时间：虽然单个5元素组排序是O(1)，但n/5个组的总耗时是O(n)
• 用找到的中位数的中位数作为pivot，对原数组进行划分的时间：这部分是O(n)
• 划分完成后，递归处理目标元素所在的子数组的时间：这部分的子数组大小最多是7n/10，对应的递归项是T(7n/10)

你只计算了寻找中位数的中位数的递归链（T(n/5) + T(n/25) + ...），完全漏掉了上述O(n)和T(7n/10)的核心部分，这是最致命的错误。

2. 等比数列求和的逻辑错误 #

即使只看你计算的递归链部分，你的累加逻辑也错了：
你把每一项n/5^k * O(1)当成了O(n)，然后认为有ceil(log5(n))个O(n)项，得出O(nlogn)。但实际上：
n/5 + n/25 + n/125 + ... 是一个首项为n/5、公比为1/5的无穷等比数列，求和结果为：

n/5 / (1 - 1/5) = n/4

这部分的总时间是O(n)，而非O(nlogn)——因为等比数列的和收敛到原数组大小的常数倍，不会随着递归层数线性累加出logn的因子。

正确的递归式与结论 #

中位数的中位数算法的正确递归式是：

T(n) = T(n/5) + T(7n/10) + O(n)

用代入法或主定理可以证明，这个递归式的解是T(n) = O(n)，这也是该算法能在线性时间内找到第k大元素的原因。

内容的提问来源于stack exchange，提问作者boban dogan