今天迅雷的面试题,并行merge排序的复杂度
k个核的机器,并行进行merge排序的复杂度是多少呢?
[解决办法]
将数据拆分成k分,每份的复杂度为O((n/k)*log(n/k)) 然后和并;
总的复杂度为O((n/k)*log(n/k))+logk
发布时间: 2012-10-13 11:38:17 作者: rapoo
今天迅雷的面试题,并行merge排序的复杂度
k个核的机器,并行进行merge排序的复杂度是多少呢?
[解决办法]
将数据拆分成k分,每份的复杂度为O((n/k)*log(n/k)) 然后和并;
总的复杂度为O((n/k)*log(n/k))+logk