首页 > 试题广场 >

将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序

[单选题]
将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为（） 
  • O(N * M * logN)
  • O(N*M)
  • O(N)
  • O(M)
添加回答
张博16头像 张博16
将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为()?

答案是mn*logn
方法是:tmp首先是空链表,把n个链表的首原属拿出来组成一个小根堆,
如果堆定的元素是第i个链表的,先弹出这个堆定到tmp中,那么第i个链表的就再从左边取出一个数扔到堆里面.
再调整,之后重复这个步骤(每一次都吧弹出元素所在的原来链表继续扔一个数到堆里面)
所以时间复杂度是mn*logn    一共扔mn词,每一次调整需要logn
我的理解是这样的,一开始做错了,看了答案也半天才看懂.
发表于 2020-04-12 15:02:00 回复(0)
更多回答
推荐
河湖之恋头像 河湖之恋
答案选A。
就算原有的链表是有序的，合并时还是需要将元素一一比较。
编辑于 2015-02-03 10:44:21 回复(1)
corny813头像 corny813

1. 在每一个链表中取出第一个值，然后把它们放在一个大小为N的数组里，然后把这个数组当成heap建成小(大)根堆。此步骤的时间复杂度为O(N)

2. 取出堆中的最小值(也是数组的第一个值), 然后把该最小值所处的链表的下一个值放在数组的第一个位置。如果链表中有一个已经为空（元素已经都被取出），则改变heap的大小。此步骤的时间复杂度为O(lg N).

3. 不断的重复步骤二，直到所有的链表都为空。
建堆只建一次，复杂度为O(N)；调整堆MN-1次，复杂度为(MN-1)*O(lg N)。所以为O(MN*lg N)

发表于 2015-08-12 00:37:19 回复(8)
Heap头像 Heap
选A。上面答案都说的不清晰。
其实算法不同结果也不一样。
1、两两合并链表。合并链表复杂度 * 一次合并次数 * 所有合并次数。两两合并的复杂度会指数递增，合并数会指数递减。一共应该是log（N）次。前面的合并复杂度较高。所以一般不采用该方法来合并链表。
2、利用堆来合并，（ O（N） + O（log N * N ）) * M。
  先利用最链表第一个数，N个数建立堆，复杂度 O （N）
  重构堆，并排序，复杂度 O（logN * N ）
  每个链表M个数，上述两步重复M次。结果为
  M * （O(N) + O(logN * N)）= O (M * N * logN)
编辑于 2015-03-13 13:58:17 回复(5)
<字节内推>头像 <字节内推>
！！！！！！！！！！@@@@@ 高  能  预  警 @@@@@！！！！！！！！！

你们说的都太复杂，不对！应该是这样的：

1、取每个链表第一个元素，组成一个数组，然后对数组排序：时间复杂度：O(NlogN)

2、然后取排序后数组的第一个节点，作为新链表的第一个节点。

3、从被取出节点的某链表中取出下一个节点，插入到数组中，二叉搜索，时间复杂度O(logN)

4、依次重复2、3步骤，因为剩下(M - 1) * N个节点，大约重复(M - 1) * N次

所以最终的时间复杂度：

O(NlogN) +  (M - 1) * N * O(logN)
= M * N * O(logN)

说堆排序的，都散了吧~

发表于 2018-03-28 11:41:51 回复(5)
为你扣下F键头像 为你扣下F键
我说一个最简单的想法吧 首先，两两合并，时间复杂度O(2m)*(n/2)=O(mn) 然后再两两合并，画出来是个二叉树结构，深度是O(logn) 最终结果就是O(mnlogn)
编辑于 2018-09-07 12:57:33 回复(4)
XyParaCrim头像 XyParaCrim
m*n个数排序复杂度是O(m*nlog(m*n))，即O(m*nlogm)+O(m*nlogn).又n个m长度序列已排序，即n*O(mlogm)复杂度，前后相减答案即O(m*nlogn).
发表于 2016-09-25 12:31:37 回复(0)
.牛妹头像 .牛妹
多路归并可以用堆，胜者树，败者树。他们都是二叉树，每个结点在树中比较的效率达到O(lgn)，总共有N*M个结点，每个结点都需要比较，因此是O（N*M*logN）

这3种树的区别：
堆： 其实一开始就是只有堆来完成多路归并的，但是人们发现堆每次取出最小值之后，把最后一个数放到堆顶，调整堆的时候，每次都要选出父节点的两个孩子节点的最小值，然后再用孩子节点的最小值和父节点进行比较，所以每调整一层需要比较两次。

胜者树： 每次比较只用跟自己的兄弟节点进行比较就好，所以用胜者树可以比堆少一半的比较次数。  

败者树： 而胜者树在节点上升的时候首选需要获得父节点，然后再获得兄弟节点，然后再比较。这时人们又想能否再次减少比较次数，于是就有了败者树  ； 在使用败者树的时候，每个新元素上升时，只需要获得父节点并比较即可。  
所以总的来说，减少了访存的时间。 
    
发表于 2017-07-17 22:56:39 回复(2)
crackhopper头像 crackhopper
代入 N=1，不需要排序，凡是非常数的都是错误答案。排除BD
代入 M=1，类似正常排序，NlogN

答案是A
发表于 2018-08-25 11:31:17 回复(0)
黏黏糖头像 黏黏糖
采用堆排序的方法进行合并。
（1）首先取出每个链表的第一个元素放在大小为N的数组中，此处的时间复杂度为O(N)；并调整成为小根堆，调整堆的时间复杂度为O（lgN）
（2）取出数组的第一个元素。将该元素所在链表的下一个元素放在数组的第一个位置，继续调整，使之成为小根堆；
（3）重复（2），如果有一个链表已经为空，则改变数组的大小。
共调整MN-1次，调整堆的时间复杂度为O(M*N*lgN）；建堆的时间复杂度为O(N)；故总的时间复杂度为 O(M*N*lgN）
发表于 2017-05-05 10:07:42 回复(1)
philian头像 philian
先来看常规的归并排序如何求解复杂度。
将任意两个有序序列（长度分别为NA、NB）进行二分归并，所需时间为线性，O(max(NA,NB))
如果递归基为n==1，那么有
T（n）=2*T（n/2）+O（n）
T（1）=O（1）
其中，O（n）是指将等长的两个有序子序列进行二分归并所需的时间，是线性时间。
联立上述两个方程，再加上由线性推导可得的O（n）=n*O（1），能得到
T（n）/n = T（n/2）/（n/2） + O（1）
设T（n）/n为S（n）
那么就有
S（1）=O（1）
S（n）=S（n/2）+O（1）=S（n/4）+O（2）=...=S（n/(2^k)）+O（k）
由上述二式可得，k=logn时抵达递归基S（1），因此有S（n）=O（logn）
T（n）=n*S（n）=O（nlogn）

回到本题，因为长度为M的子序列都已经有序，就相当于把上述从n到1的递归截了一块儿，截掉了M到1的递归部分，因此需要用总的时间复杂度减掉这被截去的一块儿。
n=N*M，因此如果递归到1，时间复杂度应为O（N*M*log（N*M））
而如果n=M，那么递归到1的时间复杂度为O（M*logM），共有N段这样的子序列，因此加起来需要O（N*M*logM）的时间
前后相减，O（N*M*log（N*M）- N*M*logM）=O（N*M*logN）

发表于 2016-12-19 13:01:29 回复(3)
Abstract——World头像 Abstract——World
参考归并排序。归并排序是N*log（N），这里在归并基本单元是一个M个元素的链表。所以所以是N*M*log（N）。
发表于 2017-03-22 22:44:07 回复(0)
新玥头像 新玥
两个有序数组合并的复杂度为O(m+n)。m，n分别为两个数组的元素个数。现有N个大小为M的有序列表进行合并。首先两两一组进行合并，共有N/2组，时间复杂度为(M+M)*N/2。一轮合并结束完后剩余N/2个大小为2M的有序数组。再次两两合并，以此类推。总共时间复杂度为2M*N/2+4M*N/4+8M*N/8+....＝M*N*logN
发表于 2018-10-04 12:14:15 回复(0)
purple燕头像 purple燕

为每条链表建立一个指针。

因为有N条链表，则取每条链表的第一个数，建立一个堆，复杂度为O(N)

（建立堆的时间复杂度为O(N)）

loop:然后取出此堆的最大/最小值，即数组的第一个元素
找到这个数所在链表，此链表指针+1，并此指针所指数之间放在堆数组第一个位置
调整堆
loop loop


发表于 2015-09-05 21:03:16 回复(1)
小海豹头像 小海豹
o(N)
发表于 2014-10-08 15:06:51 回复(0)
Pikahui头像 Pikahui
为什么你们都不考虑二路归并，二路归并比较1次乘以n 多路归并当然是m-1次乘以n 再乘以递归深度logn
发表于 2022-03-24 16:54:09 回复(0)
Idealis妙头像 Idealis妙

代入 M=1，类似正常排序，NlogN
发表于 2021-08-24 19:41:51 回复(0)
牛客260047603号头像 牛客260047603号
这就是归并排序的“归”的步骤。
两条长度M的链表合并需要O(M)
现在有N条这样的链表，这个过程需要重复多少次呢？log(N)次。
注意每次归并后，链表的长度变为两倍。所以O(M)并不准确，因为他不能反映合并后链表长度的变化，所以需要乘上一个N（长度翻了N倍）。

所以合起来，最后的复杂度就是O(NM log N)。
发表于 2021-04-08 17:14:56 回复(1)
牛客917779347号头像 牛客917779347号
直接带入M=1的情况便可
发表于 2020-09-17 20:29:53 回复(0)
Ezeref头像 Ezeref
每个链表取第一个值，初始化堆，时间复杂度  O(N * logN)
去最小数 ，此时  还剩下MN-N个数未排列
因为取最小数后堆是有序的，每个数加进来重建堆的时间复杂度为  logN
一共  （MN-N)*logN
加上初始化堆的时间 N * logN  + （MN-N)*logN  = MN * logN
编辑于 2019-03-03 19:03:44 回复(1)
ChrisZZ头像 ChrisZZ
T(N)=2T(N/2)+O(MN)，Nlog22=N=θ(N)=O(MN) ==>复杂度为O(MN log N)
发表于 2017-07-25 16:22:06 回复(0)
厅一头像 厅一
合并排序需要对N链表的头元素进行一次排序, 其时间复杂度为Nlog(N)；总复杂度为A

发表于 2016-09-22 12:01:27 回复(0)
提交观点

问题信息

链表 复杂度 阿里巴巴 排序
来自：算法工程师能力评估
上传者：小海豹
难度：
41条回答 29300浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号