我要招人

去企业版

首页 > 试题广场 >

排序时，若不采用计数排序的等空间换时间的方法，合并m个长度为

[单选题]

排序时，若不采用计数排序的等空间换时间的方法，则合并m个长度为n的已排序数组的最好时间复杂度为（）

```
O(mn(logm))
```
```
O(mlog(n))
```
```
O(nm^2)
```
```
O(nm)
```

查看正确选项

nik_zhang

当n=1时，就成了m个数的归并排序，时间复杂度为O(mlogm)

发表于 2017-07-22 09:55:19 回复(14)

cyanlong

1.分别将m个数组的第一个数(都是各自数组的最小值)取出，建立一个最小堆。//最小堆的初始化

2.取出堆顶元素(目前最小值)，放入最终的数组中。并将取出的那个元素原先的数组的下一个数放在堆顶，然后进行一次由上至下(下沉)的堆有序操作。注意：如果有一个数组遍历完，则将堆大小减1。

3.重复执行步骤2直至所有的数组都遍历完。

4.最后将堆中还剩下的m个数据按照堆排序的规则依次放入最终数组中。

整个过程中最耗时的步骤是2 3的重复。堆的有序化为O(lgm)，我们需要将所有的元素(m * n个)都遍历出来让堆过滤一遍(就是找到最小值)，所有大约会有 m * n 次 2 3 步的循环。

所以，最终的复杂度为m * n * lg(m)。

发表于 2017-01-24 23:08:50 回复(4)

牛客吴彦祖QAQ

堆的大小为m，每次调整的时间复杂度为logm，一共需要调整mn次。

发表于 2017-09-20 20:05:25 回复(0)

sunlight_run

最优情况我觉得是数组间有序，数组内部有序，时间复杂度为O（m）

但是题目给出的答案意思是：先每个数组取一个数，进行比较，时间复杂度为mlog2m，一共可以取n次，所以总时间复杂度为mnlog2m

发表于 2017-07-08 18:28:02 回复(0)

梅老板

我怎么这么多题目都看不懂呢？

发表于 2022-03-05 17:01:52 回复(0)

牛客849049333号

用堆排序，一次堆排序mlogm，使用了n次，所以n*mlogm。

因为给的m个数组有序，所以先取m个数组第一个元素进行堆排序，输出值，然后取m个数组第二个元素进行堆排序，输出值，重复n次。

发表于 2020-09-08 16:04:29 回复(0)

Mr.DoubleU

不对啊,他说最优,最优的话比如[12345], [6789 10],[11 12 13 14 15],这种数组,合并的话复杂度不是mn吗3个长度为5的数组,每个数组遍历一次就是mn了

发表于 2018-05-19 14:00:07 回复(2)

欧阳大铁柱

每次取m个数据排序，最小m*log(m)，一共n次，所以最优mn*log(m)

发表于 2017-03-14 00:16:16 回复(0)

牛客马MAXEY

看做n个长度为m的归并排序：即n* mlog（m）

发表于 2023-11-18 18:21:05 回复(0)

牛客808362388号

两个长度n数组按顺序拼接的时间复杂度是o(n²),嵌套循环。两个有序数组顺序拼接时间复杂度是o(n)，两层嵌套并行时间复杂度降为一次遍历。普通的归并排序，每趟分解数组长度都在变小，所以均摊下来整体光数组比较复杂度为o(n)。这一题不管分解什么时候，数组长度都为n，所以每次合并都为o(n),合并m/2次o(m/2)，再加上递归o(logm),最终为o(nm/2logm)删去常数部分o(nmlogm)。

发表于 2022-01-14 12:31:45 回复(0)

牛客848476880号

归并属于空间换时间了，这里应该是快排比较合适，o(mlogm)

发表于 2021-04-07 13:23:32 回复(0)

XiaoJie

不是子数组已排序了吗？有这个信息的话，时间复杂度不应该是线性的吗？

发表于 2018-06-25 11:11:36 回复(2)

黏黏糖

每次排m个数，时间复杂度最小为mlog2m；排n次，因此总的时间复杂度为mnlog2m。

时间复杂度最小时，可以采用堆排序的方式，首先把每组的第一个元素（即最小的元素）取出来，建立初始堆，建立初始堆的时间复杂度为log2m。然后进行调整，调整的时间复杂度为mn（所有的元素都要进行一次堆排序，一次只取出一个堆顶元素）

发表于 2017-06-19 15:44:24 回复(0)

提交观点

问题信息

复杂度排序

上传者：牛100

难度：

13条回答 831收藏 5207浏览

排序时，若不采用计数排序的等空间换时间的方法，合并m个长度为

问题信息

热门推荐

相关试题