平行查找中位数
平行查找中位数
提问于 2010-07-23 16:09:08
如果你有一个巨大的数字和一百台计算机，你如何找到这些数字的中位数？
回答 1
Stack Overflow用户
回答已采纳
发布于 2010-07-23 16:13:12
使用选择算法。
partitions.
- Each处理器应使用通用枢轴将数组拆分为两个组每个处理器应将这两个组的大小发送给领导者
- 领导者应计算哪个组较小并广播消息以从其中一个组中剔除。
- 返回步骤2，直到找到中位数
此解决方案的平均运行时间为O(n)为了使其渐近运行时间为O(n)，每个处理器应将数字分成5个元素的组找到每个组的中位数(使用插入排序)并将这些中位数发送回领导者，领导者将选择这些中位数的中位数(使用相同的算法)，这将是枢轴
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3316398
复制相关文章
相似问题