首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

N个机器,每个机器上有N个数,每个机器只得容纳O(N)个数并操作,找到这N^2个数的中数

2013-03-27 
N个机器,每个机器上有N个数,每个机器只能容纳O(N)个数并操作,找到这N^2个数的中数网上方法说:方法1:将这些

N个机器,每个机器上有N个数,每个机器只能容纳O(N)个数并操作,找到这N^2个数的中数
网上方法说:方法1:将这些数分成一段段的。。可是怎么保证每个机器都是O(N)?
            方法2:对每个机器上的N个分别排序,然后进行N路归并,找到第N^2/2个数就可以。这个时间复杂度是怎么估计的?
[解决办法]
多路归并应该可以用败者树(loser tree)来实现,效率应该是n*log(n)吧

热点排行