time-complexity - 中位数的时间复杂度

Question

在 Google 上的几篇文章（例如https://cs.stackexchange.com/questions/125995/median-of-medians-proof-for-time-complexity）和文章中，我看到了以下时间复杂度重现中位数的中位数：

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

但我很困惑，因为这种递归似乎将 MoM 视为嵌入到快速选择中，因此是快速选择的递归公式，用于在使用 MoM 找到近似枢轴时找到精确的中位数。

如果我们只是想使用 MoM 找到一个近似中位数，那么递归是多少？会不会只是

T(n) <= T(n/5) + O(n) ?

Answer 1

中位数算法在每个级别递归调用完整的快速选择。

如果您使用“普通”妈妈而不是快速选择来获取快速排序的枢轴，那么您只是简化了顶级快速选择。所有较低级别的调用都保留下来，因此整个操作的复杂性不会改变。