如何理解中位数算法中位数的复杂性？
How to understand the complexity of medians of medians algorithm?
我正在按照此处描述的说明进行操作
https://brilliant.org/wiki/median-finding-algorithm/
中位数算法部分的复杂性
它描述了大约 3n/10 最好的情况和 7n/10 最坏的情况
我不明白它是如何得到 3n/10 和 7n/10 部分的？虽然它提到 "For each of these elements, there are two elements that are smaller than it (since these elements were medians in lists of five elements—two elements were smaller and two elements were larger)."
将列表分成 n/5 组，每组 5，并找到中位数的中位数 p 后，您需要确定最坏情况下还有多少元素，您仍然需要寻找真实的元素中位数
考虑列表中有多少元素必须小于 p（或等于，在更简单的不同元素列表情况下仅为 p）
n/5 组中有一半的中位数小于 p。在这些组中，有 3 个元素 - 中位数和两个较小的值 - 必须小于 p。我们不知道较大的元素是否大于 p，也不知道中位数大于 p 的组中是否有任何元素具有小于 p 的元素。
所以在最坏的情况下，我们确定1/2 * n/5组-n/10组-每个有3个元素肯定小于p。那是 3n/10 个元素。在最坏的情况下，所有其他元素都大于 p，这使得 7n/10 个元素大于 p 以递归地执行此算法。
该算法成功的关键在于每一步都丢弃了一定比例的元素。
2k+1 的中位数两边有 k 个元素。那么(2k+1)(2l+1)个元素的中位数中位数肯定两边都有(k+1)(l+1)-1个元素（每个中位数不小于k+1个元素还有l+1个中位数，都不小于中位数的中位数）。
分数是((k+1)(l+1)-1)/(2k+1)(2l+1)。在 k=2 的情况下，我们有 (3(l+1)-1)/5(2l+1) ~ 3l/10.
我正在按照此处描述的说明进行操作 https://brilliant.org/wiki/median-finding-algorithm/ 中位数算法部分的复杂性 它描述了大约 3n/10 最好的情况和 7n/10 最坏的情况 我不明白它是如何得到 3n/10 和 7n/10 部分的？虽然它提到 "For each of these elements, there are two elements that are smaller than it (since these elements were medians in lists of five elements—two elements were smaller and two elements were larger)."
将列表分成 n/5 组，每组 5，并找到中位数的中位数 p 后，您需要确定最坏情况下还有多少元素，您仍然需要寻找真实的元素中位数
考虑列表中有多少元素必须小于 p（或等于，在更简单的不同元素列表情况下仅为 p）
n/5 组中有一半的中位数小于 p。在这些组中，有 3 个元素 - 中位数和两个较小的值 - 必须小于 p。我们不知道较大的元素是否大于 p，也不知道中位数大于 p 的组中是否有任何元素具有小于 p 的元素。
所以在最坏的情况下，我们确定1/2 * n/5组-n/10组-每个有3个元素肯定小于p。那是 3n/10 个元素。在最坏的情况下，所有其他元素都大于 p，这使得 7n/10 个元素大于 p 以递归地执行此算法。
该算法成功的关键在于每一步都丢弃了一定比例的元素。
2k+1 的中位数两边有 k 个元素。那么(2k+1)(2l+1)个元素的中位数中位数肯定两边都有(k+1)(l+1)-1个元素（每个中位数不小于k+1个元素还有l+1个中位数，都不小于中位数的中位数）。
分数是((k+1)(l+1)-1)/(2k+1)(2l+1)。在 k=2 的情况下，我们有 (3(l+1)-1)/5(2l+1) ~ 3l/10.