algorithm - 几何平均主元

Question

我是博士生，我正在做我的项目，

我想知道如果我使用几何平均值作为将数组划分为大致相等的两部分的基准，最坏情况下的划分时间复杂度是多少？

结果:-

Vladimir Yaroslavskiy 双轴快速选择分区:- 2307601193 纳秒

几何平均枢轴快速选择分区:- 8661916394 纳秒

我们知道它非常昂贵并且使快速分区慢得多。有许多算法比快速选择查找中位数要快得多，但在我们的项目中我们不会直接使用它们。

几何平均基准示例:-

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Input- 789654123 , 700 , 10^20 , 588412 , 900 , 5 , 500

Geometric mean :-( 789654123*700*10^20*588412*900*5*500)^(1/7)= 1846471

Pass 1- 500 700 5 588412 900 |<---> | 10^20 789654123

Geometric mean :-(500*700*5*588412*900)^(1/5)=984

Pass 2- 500, 700, 5, 900, |<---> | 588412, 10^20, 789654123
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

通过这种方式我们可以将数组分成大致相等的两部分。

我的问题是，如果我使用几何平均值作为将数组划分为近似两等份的基准，那么最坏情况(最差不平衡划分)的时间复杂度是多少？

注意:- 我们没有在数据集中使用 -ve no。

Answer 1

几何平均数相当于对数的算术平均数，所以我们只需要找到算术平均数严重失效的地方并取其指数即可。一个例子是阶乘，如果你有一个列表

1!, 2!, 3!, 4!, ..., n!

取算术平均值将恰好在最后一个元素之前拆分。证明:这个数组的总和大于最后一个元素:

s_n > n!

因此算术平均值大于它之前的元素:

av_n = s_n/n > (n-1)!

因此，快速选择需要 n 轮，其性能为 O(n^2)，而平均性能为 O(n)。要获得与几何平均值相同的行为，您必须考虑这个指数列表

a^(1!), a^(2!), ..., a^(n!)

对于任何a>1或 0<a<1 .基于几何平均值的快速选择 的结果性能为 O(n^2)。