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

Question

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

但是,在算法的中间,我们对一个大小的子数组进行递归调用,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)实现它并不是很明显,并且没有解释/参考.
• 我问谁笔者最初添加的信息和他回答说,他不记得,它可能是一个错误.
• 2005年专门用O(n)时间和O(1)额外空间解决选择问题的论文称BFPRT(中位数中位数)使用Θ(log n)额外空间.另一方面,论文的主要结果是O(n)时间和O(1)额外空间是可能的,并且作为证明的两种算法之一是BFPRT的一些"仿真".所以在这个意义上它是可能的,但我认为仿真相当于使它成为一种不同的算法而且O(1)不应归因于"常规"BFPRT.至少没有解释.
  (感谢Yu-HanLyu在评论中展示了这篇论文以及更多内容)