为什么中位数算法被描述为使用 O(1) 辅助 space？
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 的子数组进行递归调用，以找到中位数的中位数。在这个递归调用returns的时候，我们使用中位数的returned中位数作为枢轴对数组进行分区。
作为递归的一部分，此算法不会将 O(lg n) 激活记录推送到 运行 时间堆栈吗？据我所知，这些用于查找中位数的连续中位数的递归调用无法进行尾调用优化，因为我们在递归调用 return 之后做了额外的工作。因此，该算法似乎需要 O(lg n) 辅助 space（就像快速排序一样，维基百科将其列为需要 O(lg n) 辅助 space，因为 space 使用运行-时间栈）。
我是不是遗漏了什么，或者维基百科文章有误？
（注意：我指的递归调用是维基百科页面上的 return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10)。）
虽然我不能排除 O(1) 的可能性，但维基百科的信息似乎是错误的。
- 那里显示的实现需要 O(log n) 而不仅仅是 O(1)。
- 如何用 O(1) 实现它绝对不明显，也没有 explanation/reference。
- 我问作者谁originally added that information and he replied他不记得了，估计是弄错了
- A paper from 2005 致力于用 O(n) 时间和 O(1) 额外时间解决选择问题 space 说 BFPRT（又名中位数的中位数）使用 Θ(log n) 额外 space。另一方面，该论文的主要结果是 O(n) 时间和 O(1) 额外 space 是可能的，并且作为证明提供的两个算法之一是 BFPRT 的一些 "emulation"。所以从这个意义上说，这是可能的，但我认为仿真反而使它成为一种不同的算法，O(1) 不应归因于 "regular" BFPRT。至少不是没有解释。
（感谢 Yu-HanLyu 在评论中展示该论文和更多内容）
复杂度为 O(1)。
假设我们从一个长度为 n 的数组开始，我们打算找到排序列表的第 k 个元素。
第一次调用 median of medians 后会吐出一个较小的数组，现在我们需要计算这个较小数组的第 i 个元素。请注意，这个较小数组的第 i 个元素是结果，因此我不需要将任何信息传递回之前的调用。
在快速排序中，我需要将排序后的小数组放回正确的位置，因此发生递归。使用中位数的中位数，在循环（尾递归）之后，我将得到答案。
递归深度 = O(1)
Wikipedia lists the median-of-medians algorithm as requiring O(1) auxiliary space.
然而，在算法的中间，我们对大小为 n/5 的子数组进行递归调用，以找到中位数的中位数。在这个递归调用returns的时候，我们使用中位数的returned中位数作为枢轴对数组进行分区。
作为递归的一部分，此算法不会将 O(lg n) 激活记录推送到 运行 时间堆栈吗？据我所知，这些用于查找中位数的连续中位数的递归调用无法进行尾调用优化，因为我们在递归调用 return 之后做了额外的工作。因此，该算法似乎需要 O(lg n) 辅助 space（就像快速排序一样，维基百科将其列为需要 O(lg n) 辅助 space，因为 space 使用运行-时间栈）。
我是不是遗漏了什么，或者维基百科文章有误？
（注意：我指的递归调用是维基百科页面上的 return select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10)。）
虽然我不能排除 O(1) 的可能性，但维基百科的信息似乎是错误的。
- 那里显示的实现需要 O(log n) 而不仅仅是 O(1)。
- 如何用 O(1) 实现它绝对不明显，也没有 explanation/reference。
- 我问作者谁originally added that information and he replied他不记得了，估计是弄错了
- A paper from 2005 致力于用 O(n) 时间和 O(1) 额外时间解决选择问题 space 说 BFPRT（又名中位数的中位数）使用 Θ(log n) 额外 space。另一方面，该论文的主要结果是 O(n) 时间和 O(1) 额外 space 是可能的，并且作为证明提供的两个算法之一是 BFPRT 的一些 "emulation"。所以从这个意义上说，这是可能的，但我认为仿真反而使它成为一种不同的算法，O(1) 不应归因于 "regular" BFPRT。至少不是没有解释。
（感谢 Yu-HanLyu 在评论中展示该论文和更多内容）
复杂度为 O(1)。
假设我们从一个长度为 n 的数组开始，我们打算找到排序列表的第 k 个元素。
第一次调用 median of medians 后会吐出一个较小的数组，现在我们需要计算这个较小数组的第 i 个元素。请注意，这个较小数组的第 i 个元素是结果，因此我不需要将任何信息传递回之前的调用。
在快速排序中，我需要将排序后的小数组放回正确的位置，因此发生递归。使用中位数的中位数，在循环（尾递归）之后，我将得到答案。
递归深度 = O(1)