Jar*_*sie 4 algorithm complexity-theory computer-science median-of-medians
我在网上搜索并访问了wiki页面,找到了中位数算法的中位数.但似乎无法在我的问题中找到明确的陈述:
如果一个人拥有一个非常大的整数列表(TB的大小),并希望以分布式方式找到该列表的中位数,那么会将列表分成不同大小的子列表(或者相等并不重要),然后继续计算那些较小的子列表的中位数,然后计算这些中位数的中位数得到原始大型列表的中位数？
此外,这个陈述也适用于任何第k个统计数据吗？我对这个领域的研究等方面感兴趣.
Mas*_*aro 12
你的问题的答案是否定的.
如果你想了解如何在并行设置中实际选择第k顺序统计数据(包括当然的中位数)(分布式设置当然不是真的不同),请看看最近的这篇论文,其中我提出了一个改进以前的并行选择算法的新算法:
在这里,我们使用两个加权的3中位数作为枢轴,并使用五向分割围绕这些枢轴进行分区.我们还使用MPI实现并测试了算法.考虑到这是利用最坏情况O(n)选择算法的确定性算法,结果非常好 .使用随机O(n)QuickSelect算法提供了一种极其快速的并行算法.
如果一个人有一个整数的非常非常大名单(大小TBS),并希望找到这个列表中位数以分布式的方式,将打破名单成大小不等的子列表(或等于其实并不重要),然后继续计算那些较小的子列表的中位数,然后计算这些中位数的中位数得到原始大型列表的中位数？
不是.整个列表的实际中位数不一定是任何子列表的中位数.
由于距离实际中位数比随机选择的元素更接近,因此中位数中位数可以为您提供快速选择的枢轴选择,但您必须执行其余的quickselect算法以找到较大列表的实际中位数.