首页 > 试题广场 >

假设你得到了k个排好序的数组，每个都有n个元素，希望将它们整

[单选题]

假设你得到了k个排好序的数组，每个都有n个元素，希望将它们整体组合成一个有着kn个元素的有序数组。考虑以下方法：将k个数组分为k/2对，并使用归并排序来合并每对，则你有了k/2个排序好的数组；重复此方法，直到合并结束。那么程序运行的时间复杂度是：

查看正确选项

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)

beyond201809081347576

归并时间复杂度为nlogn,假设直接对nk归并，时间复杂度为nklognk,因为已经归并好K个n维序列，相当于节省了Knlogn的时间，所以时间复杂度为nklognk-nklogn=nklogk

发表于 2019-12-28 10:53:52 回复(0)

牛客628325967号

假如n=1，就是普通归并排序的情况了，klogk～

发表于 2020-08-01 11:52:51 回复(0)

提交观点

问题信息

算法工程师猿辅导 2020

上传者：小小

难度：

3条回答 27收藏 2244浏览

扫一扫，把题目装进口袋