你真的需要第n个元素,还是需要一个"靠近"中间的元素？
有更快的方法让元素"靠近"中间.一个例子大致如下:
function rough_middle(container)
divide container into subsequences of length 5
find median of each subsequence of length 5 ~ O(k) * O(n/5)
return rough_middle( { median of each subsequence} ) ~ O(rough_middle(n/5))
结果应该是大致在中间的东西.一个真正的第n个元素算法可能会使用类似上面的东西,然后在之后清理它以找到实际的第n个元素.
在n=5,你得到中间.
在n=25,你得到短序列中间的中间.这将大于每个短序列中的所有较小序列,或者至少第9个元素并且不多于第16个元素,或者距离边缘36%.
在n=125,你得到每个短序列中间的粗略中间.这至少是第9中间,所以有8*3 + 2 = 26个元素比粗糙的中间要少,或者距边缘有20.8%.
在n=625,你得到每个短序列中间的粗略中间.这至少是第26中间,所以有77个元素比粗糙的中间要少,或者距离边缘有12%.
在n=5^k,你得到粗糙中间的5^(k-1)粗糙中间.如果5^k序列的粗糙中间是r(k),那么r(k+1) = r(k)*3-1 ~ 3^k.
3^k 在O符号中生长慢于5 ^ k.
3^log_5(n)
= e^( ln(3) ln(n)/ln(5) )
= n^(ln(3)/ln(5))
=~ n^0.68
是rough_middle对一系列n元素最终结束位置的下界的粗略估计.
从理论上讲,它可能需要大约n^0.33一段时间的减少才能达到单个元素,这实际上并不是那么好.(n ^ 0.68中的位数是n中位数的~0.68倍.如果我们在每个粗糙的中间区域刮掉那么多,我们需要重复它大约n^0.33n次中的位数来消耗所有位 -更多,因为当我们从中减去时n,下一个n得到的值略小一些).
我见过的第n个元素解决方案解决这个问题的方法是在每个级别进行分区和修复:而不是rough_middle递归,你可以进入middle.然后保证中位数的真正中间非常接近序列的实际中间位置,并且您可以相对快速地(以O表示法)"找到真正的中间".
可能我们可以通过rough_middle在有更多元素的情况下进行更精确的迭代来优化此过程,但从不强制它成为实际的中间体？结尾越大n,越靠近中间我们需要递归调用到中间,最终结果合理地接近中间.
但实际上,你的序列是一个非常糟糕的实际上需要n ^ 0.33步骤才能将其分解为空的概率可能非常低.有点像快速排序问题:3个元素的中位数通常足够好.
快速统计分析.
你随机挑选5个元素,然后选择中间元素.
2m+1均匀分布的一组随机样本的中值索引遵循具有粗略参数的β分布(m+1, m+1),可能有一些非[0,1]间隔的缩放因子.
中位数的平均值显然为1/2.方差是:
(3*3)^2 / ( (3+3)^2 (3+3+1) )
= 81 / (36 * 7)
=~ 0.32
弄清楚下一步是超出我的统计数据.我会作弊.
如果我们想象从平均值为0.5且方差为0.32的一组项中取中值索引元素与平均其索引一样好......
n现在让我们原始集合中的元素数量.
那么短序列的中值指数之和平均为n次n/5*0.5 = 0.1 * n^2.短序列中值的索引之和的方差是n次n/5*0.32 = 0.064 * n^2.
如果我们然后将值除以n/5,我们得到:
所以意味着n/2和方差1.6.
哦,如果那是真的,那就太棒了.不随大小增长的方差n意味着随着n变大,短序列的中位数的平均指数变得非常紧密地分布.我想这有点道理.可悲的是,我们并没有这么做 - 我们希望分配短序列的中位数的伪中位数.这几乎肯定更糟.
实施细节.我们可以用对数的内存开销做一个就地粗略中位数.(我们甚至可以在没有内存开销的情况下做到这一点!)
我们维护一个包含5个索引的向量,其中包含"nothing here"占位符.
每个都是一个连续的层.
在每个元素,我们推进底部指数.如果它已满,我们抓住中位数,然后将其插入下一级别,并清除底层.
最后,我们完成了.
using target = std::pair<size_t,std::array<size_t, 5>>;
bool push( target& t, size_t i ) {
t.second[t.first]=i;
++t.first;
if (t.first==5)
return true;
}
template<class Container>
size_t extract_median( Container const& c, target& t ) {
Assert(t.first != 0);
std::sort( t.data(), t.data()+t.first, [&c](size_t lhs, size_t rhs){
return c[lhs]<c[rhs];
} );
size_t r = t[(t.first+1)/2];
t.first = 0;
return r;
}
template<class Container>
void advance(Container const& c, std::vector<target>& targets, size_t i) {
size_t height = 0;
while(true) {
if (targets.size() <= height)
targets.push_back({});
if (!push(targets[height], i))
return;
i = extract_median(c, targets[height]);
}
}
template<class Container>
size_t collapse(Container const& c, target* b, target* e) {
if (b==e) return -1;
size_t before = collapse(c, b, e-1);
target& last = (*e-1);
if (before!=-1)
push(before, last);
if (last.first == 0)
return -1;
return extract_median(c, last);
}
template<class Container>
size_t rough_median_index( Container const& c ) {
std::vector<target> targets;
for (auto const& x:c) {
advance(c, targets, &x-c.data());
}
return collapse(c, targets.data(), targets.data()+targets.size());
}
它概述了它如何在随机访问容器上工作.