time-complexity - 使用 3 块的中位数的中位数 - 为什么它不是线性的？

Question

我理解为什么在最坏的情况下，其中 T 是算法的运行时间，使用中位数算法的中位数和大小为 3 的块会给出递归关系

T(n) = T(2n / 3) + T(n / 3) + O(n)

中位数算法的维基百科文章说，对于大小为 3 的块，运行时间不是 O(n)，因为它仍然需要检查所有 n 个元素。我不太明白这个解释，在我的作业中说我需要通过归纳来展示它。

在这种情况下，我如何证明中位数的中位数需要时间 Ω(n log n)？

Answer 1

由于这是一个家庭作业问题，我将让您自己找出这个结果的严格证明，但是通过查看递归树的形状来考虑这个可能会有所帮助，这将类似于这个：

                      n                         Total work: n
      2n/3                        n/3           Total work: n
4n/9        2n/9             2n/9      n/9      Total work: n

本质上，每个节点的子节点将共同完成与节点本身完全相同的工作量，因此如果您总结跨层完成的工作，您应该看到每个级别完成的大致线性工作。每个级别的工作不会完全是线性的，因为最终较小的调用开始触底，但是对于顶层，您会看到这种模式成立。

您可以通过猜测运行时是 cn log n 形式的东西来通过归纳来形式化这一点，可能添加了一些低阶术语，但是（恕我直言）查看运行时的来源比查看运行时的来源更重要和更有启发性。能够归纳证明。

Answer 2

如果我们将 T(2n/3) 和 T(n/3) 的小数部分相加，得到 T(n)。然后，使用 Master 定理，我们有 n^(log_(b)(a)) = n^(log_(1)(1)) = n。我们也有 f(n) = O(n)。所以 n^(log_(b)(a)) = O(n) = Theta(f(n))，因此适用主定理的情况 2。因此 T(n) = Theta(n^(log_(b)(a)) * log(n)) = Theta(n*log(n))。