19

维基百科将中位数算法列为需要O(1)辅助空间。

然而，在算法的中间，我们对一个大小的子数组进行递归调用n/5以找到中位数的中位数。当这个递归调用返回时，我们使用返回的中位数作为基准来划分数组。

这个算法不是将O(lg n)激活记录作为递归的一部分推送到运行时堆栈吗？从我所见，这些寻找中位数的连续中位数的递归调用不能进行尾调用优化，因为我们在递归调用返回后做了额外的工作。因此，该算法似乎需要辅助空间（就像快速排序一样，由于运行时堆栈使用的空间O(lg n)，维基百科将其列为需要辅助空间）。O(lg n)

我错过了什么，还是维基百科的文章错了？

（注意：我所指的递归调用return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10)在维基百科页面上。）

4

2 回答 2

12

虽然我不能排除 O(1) 是可能的，但维基百科的信息似乎是一个错误。

  • 那里显示的实现需要 O(log n) 而不仅仅是 O(1)。
  • 如何用 O(1) 实现它绝对不明显，也没有解释/参考。
  • 我问最初添加该信息的作者，他回答说他不记得了，这可能是一个错误。
  • 2005 年的一篇论文致力于解决 O(n) 时间和 O(1) 额外空间的选择问题，称 BFPRT（又名 Median of Medians）使用 Θ(log n) 额外空间。另一方面，论文的主要结果是 O(n) 时间和 O(1) 额外空间是可能的，并且作为证明提出的两种算法之一是 BFPRT 的某种“模拟”。所以从这个意义上说是可能的，但我认为仿真使它成为一种不同的算法，并且 O(1) 不应该归因于“常规”BFPRT。至少不是没有解释。
    （感谢 Yu-HanLyu 在评论中展示该论文及更多内容）
于 2016-01-04T22:20:00.750 回答
-2

它是 O(1)。

假设我们从一个长度为 n 的数组开始，我们打算找到排序列表的第 k 个元素。

在第一次调用中位数之后，中位数会吐出一个较小的数组，现在我们需要对这个较小数组的第 i 个元素求值。请注意，这个较小数组的第 i 个元素是结果，因此我不需要将任何信息传递回之前的调用。

在快速排序中，我需要将已排序的小数组放回正确的位置，因此会发生递归。中位数的中位数，在循环（尾递归）之后，我将得到答案。

递归深度 = O(1)

于 2017-02-18T20:42:31.550 回答