首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
假设你得到了k个排好序的数组,每个都有n个元素,希望将它们整
[单选题]
假设你得到了k个排好序的数组,每个都有n个元素,希望将它们整体组合成一个有着kn个元素的有序数组。考虑以下方法:将k个数组分为k/2对,并使用归并排序来合并每对,则你有了k/2个排序好的数组;重复此方法,直到合并结束。那么程序运行的时间复杂度是:
查看正确选项
添加笔记
求解答(4)
邀请回答
收藏(27)
分享
纠错
3个回答
添加回答
4
Shermo
起始每个数组大小n,有k个,
第一趟归并: 做 k/2 次, 每次 O(N), 复杂度为 nk/2
第二趟: 做 k/4次, 每次 2n(每个序列变长了), 复杂度为 nk/2
```
一共要做logk轮归并,总的复杂度为 O(n k logk)
发表于 2020-07-27 13:47:59
回复(0)
7
beyond201809081347576
归并时间复杂度为nlogn,假设直接对nk归并,时间复杂度为nklognk,因为已经归并好K个n维序列,相当于节省了Knlogn的时间,所以时间复杂度为nklognk-nklogn=nklogk
发表于 2019-12-28 10:53:52
回复(0)
0
牛客628325967号
假如n=1,就是普通归并排序的情况了,klogk~
发表于 2020-08-01 11:52:51
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
算法工程师
猿辅导
2020
上传者:
小小
难度:
3条回答
27收藏
2252浏览
热门推荐
相关试题
看图回答
判断推理
2020
人力资源
安永
审计
税务服务
风险管理
管理咨询
行政管理
评论
(3)
来自
职能类模拟题2
看图回答
判断推理
2020
人力资源
安永
审计
税务服务
风险管理
管理咨询
行政管理
评论
(1)
来自
职能类模拟题2
0-100的N个数(数的值范围为0...
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2017
测试工程师
猿辅导
golang工程师
评论
(2)
来自
猿辅导2017校招面试题...
分页系统的逻辑地址结构是一维的,分...
操作系统
评论
(1)
你说在销售运营这个岗位上会涉及到一...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题