为什么将中位数算法描述为使用O（1）辅助空间？ [英] Why is the median-of-medians algorithm described as using O(1) auxiliary space?
问题描述
Wikipedia lists the median-of-medians algorithm as requiring O(1) auxiliary space.
但是，在算法中间，我们对大小为 n /的子数组进行了递归调用5 来找到中位数。当此递归调用返回时，我们将返回的中位数中位数用作对数组进行分区的支点。
However, in the middle of the algorithm, we make a recursive call on a subarray of size n/5 to find the median of medians. When this recursive call returns, we use the returned median of medians as a pivot to partition the array.
此算法不是将 O（ lg n）激活记录是否作为递归的一部分记录到运行时堆栈中？从我的看到，这些递归调用无法找到尾数的中位数，因此无法对尾调用进行优化，因为在递归调用返回后，我们会做额外的工作。因此，似乎此算法需要 O（lg n）辅助空间（就像Quicksort一样，维基百科将其列为需要 O（lg n）辅助空间，因为运行时堆栈会使用该空间）。
Doesn't this algorithm push O(lg n) activation records onto the run-time stack as a part of the recursion? From what I can see, these recursive calls to find successive medians of medians cannot be tail-call optimized because we do extra work after the recursive calls return. Therefore, it seems like this algorithm requires O(lg n) auxiliary space (just like Quicksort, which Wikipedia lists as requiring O(lg n) auxiliary space due the space used by the run-time stack).
我遗漏了某些东西，还是维基百科的文章有误？
Am I missing something, or is the Wikipedia article wrong?
（注意：我要引用的递归调用是 return select（list，left，left + ceil（（right-left）/ 5）- 1，在Wikipedia页面上为左+（右-左）/ 10）。）
(Note: The recursive call I'm referring to is return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10) on the Wikipedia page.)
推荐答案
虽然我不能排除O（1）的可能性，但Wikipedia信息似乎是一个错误。
While I can't rule out that O(1) is possible, that Wikipedia information appears to be a mistake.
- 此处显示的实现
- 用O（1）实现O（log n）不仅是O（1）。
- 如何用O（1）实现它绝对不是很明显，并且没有解释/引用。 >
- 我问作者最初添加了该信息，并且他回答了他不记得了，可能是一个错误。
- A 2005年的论文致力于解决O（n）时间和O（1）多余空间的选择问题，说BFPRT（又名中位数中值）使用Θ（log n）多余的空间。另一方面，本文的主要结果是O（n）时间和O（1）额外空间是可能的，作为证明的两种算法之一是BFPRT的模拟。因此从某种意义上说是有可能的，但是我认为仿真可以使它成为一种不同的算法，并且O（1）不应归因于常规 BFPRT。至少并非没有解释。
（感谢Yu-HanLyu在评论中显示了该论文及更多内容）
- The implementation shown there takes O(log n) and not just O(1).
- It's absolutely not obvious how to implement it with O(1) and there's no explanation/reference for it.
- I asked the author who originally added that information and he replied that he doesn't remember and that it's probably a mistake.
- A paper from 2005 devoted to solving the selection problem with O(n) time and O(1) extra space says BFPRT (aka Median of Medians) uses Θ(log n) extra space. On the other hand, the paper's main result is that O(n) time and O(1) extra space is possible, and one of the two algorithms presented as proof is some "emulation" of BFPRT. So in that sense it's possible, but I think the emulation rather makes it a different algorithm and the O(1) shouldn't be attributed to "regular" BFPRT. At least not without explanation.
(Thanks to Yu-HanLyu for showing that paper and more in the comments)
这篇关于为什么将中位数算法描述为使用O（1）辅助空间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
