algorithm - 为什么中位数算法被描述为使用 O(1) 辅助空间？

Question

Wikipedia lists the median-of-medians algorithm as requiring O(1) auxiliary space.

但是，在算法的中间，我们对大小为 n/5 的子数组进行递归调用，以找到中位数的中位数。当此递归调用返回时，我们使用返回的中位数中位数作为对数组进行分区的基准。

这个算法不是将 O(lg n) 激活记录作为递归的一部分压入运行时堆栈吗？据我所知，这些用于查找中位数的连续中位数的递归调用无法进行尾调用优化，因为我们在递归调用返回后做了额外的工作。因此，该算法似乎需要 O(lg n) 辅助空间(就像 Quicksort 一样，维基百科将其列为需要 O(lg n) 辅助空间，因为使用的空间通过运行时堆栈)。

我是不是遗漏了什么，或者维基百科文章有误？

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

Answer 1

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

• 那里显示的实现需要 O(log n) 而不仅仅是 O(1)。
• 如何用 O(1) 实现它绝对不是显而易见的，也没有任何解释/引用。
• 我问作者是谁originally added that information和 he replied他不记得了，这可能是个错误。
• A paper from 2005致力于用 O(n) 时间和 O(1) 额外空间解决选择问题的 BFPRT(又名中位数的中位数)使用 Θ(log n) 额外空间。另一方面，该论文的主要结果是 O(n) 时间和 O(1) 额外空间是可能的，并且作为证明提供的两种算法之一是 BFPRT 的某种“模拟”。所以从这个意义上说，这是可能的，但我认为仿真反而使它成为一种不同的算法，并且 O(1) 不应归因于“常规”BFPRT。至少不是没有解释。
  (感谢 Yu-HanLyu 在评论中展示该论文和更多内容)