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

[单选题]

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

查看正确选项

learner111111

不采用空间换时间的方法，最优时间复杂度也能达到O（nm）？我怎么不知道这么无敌的算法呢？

发表于 2018-09-12 18:03:13 回复(0)

万雨

思路是：首先将m个已排序数组的第一个数，建立大小为m的小根堆，时间复杂度O(m)。然后每次输出堆顶的数，再将其所属已排序数组的后一个数放入堆顶，调节小根堆。因为我们有m*n个数，小根堆调整时间为O(logm)，所以时间复杂度O(nmlogm)。

发表于 2018-12-25 11:21:39 回复(0)

紫夜丶听雨

考虑归并排序，平均时间复杂度O(nlogn)？最优O(nlogn)?

发表于 2018-09-04 09:34:31 回复(0)

提交观点

问题信息

复杂度

上传者：1185925亓乂

难度：

3条回答 60收藏 1819浏览

扫一扫，把题目装进口袋