如何理解中介算法的复杂性？

Question

我遵循这里描述的中间中值算法部分的https://brilliant.org/wiki/median-finding-algorithm/复杂性，它描述了3n/10最佳情况和7n/10更坏的情况，我不知道它是如何得到3n/10和7n/10部分的？虽然它提到“对于每一个元素，有两个元素比它小(因为这些元素是五个元素列表中的中间元素-两个元素更小，两个元素更大)”。

Answer 1

在将列表划分为5的n/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可以递归地执行该算法。

Answer 2

该算法成功的关键在于，每一步都会丢弃一定比例的元素。

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。