早教吧作业答案频道 -->数学-->
已知两个长度分别为m和n的升序链表若将它们合并为一个长度为m+n的降序链表,则最坏情况下的时间复杂度是A.O(n)B.O(mn)C.O(min(m,n))D.O(max(m,n))
题目详情
已知两个长度分别为m 和n 的升序链表
若将它们合并为一个长度为m+n 的降序链表,则
最坏情况下的时间复杂度是
A.O(n) B.O(mn) C.O(min(m,n)) D.O(max(m,n))
若将它们合并为一个长度为m+n 的降序链表,则
最坏情况下的时间复杂度是
A.O(n) B.O(mn) C.O(min(m,n)) D.O(max(m,n))
▼优质解答
答案和解析
wandersss 网友说的不对,即使改成“非降序链表”,准确答案是O(m+n)而不是O(max(m,n)),比如链表1为100~999(900个数,m=900),链表2为1~99、1000(100个数,n=100),整个比较次数为99+900=999次.
下面我说说我对这道题的理首先这道题的准确答案是O(m+n),可是选项中没有,所以只能选一个最符合准确答案的选项,即使它不一定是正确的.
假设m大于n,
如果m非常接近于n,则O(m*n)~=O(n^2)>>O(m+n)~=O(2n),所以B不正确
如果m>>n,则O(m+n)>>O(n),O(m+n)>>O(min(m,n)) =O(n),所以A、C不正确
只有D,如果m非常接近于n,则O(m+n)~=O(2n)约等于O(n);如果m>>n,O(m+n)也约等于O(max(m,n))=O(m)
这道有序链表合并的问题,如果是按照原序排列,则最好的情况是O(min(m,n)) ,最坏的情况是O(m+n);如果是按照原序的逆序排列,则无论最好最坏都是O(m+n)
一开始说了最坏情况,下面说一下最好情况.比如链表1为100~999(900个数,m=900),链表2为0~99(100个数,n=100),整个比较次数为100次.在比较完成之后直接把链表1剩余所有链表直接挂在新链表(也可以直接是链表2)的后面.
下面我说说我对这道题的理首先这道题的准确答案是O(m+n),可是选项中没有,所以只能选一个最符合准确答案的选项,即使它不一定是正确的.
假设m大于n,
如果m非常接近于n,则O(m*n)~=O(n^2)>>O(m+n)~=O(2n),所以B不正确
如果m>>n,则O(m+n)>>O(n),O(m+n)>>O(min(m,n)) =O(n),所以A、C不正确
只有D,如果m非常接近于n,则O(m+n)~=O(2n)约等于O(n);如果m>>n,O(m+n)也约等于O(max(m,n))=O(m)
这道有序链表合并的问题,如果是按照原序排列,则最好的情况是O(min(m,n)) ,最坏的情况是O(m+n);如果是按照原序的逆序排列,则无论最好最坏都是O(m+n)
一开始说了最坏情况,下面说一下最好情况.比如链表1为100~999(900个数,m=900),链表2为0~99(100个数,n=100),整个比较次数为100次.在比较完成之后直接把链表1剩余所有链表直接挂在新链表(也可以直接是链表2)的后面.
看了已知两个长度分别为m和n的升序...的网友还看了以下:
关于一元二次方程,1、m取何值时,关于x的二次方程(2m+1)x²+4m+2m-3=0有两个不等实 2020-05-13 …
如图,边长为(m+3)的正方形纸片剪出一个边长为m的正方形之后,剩余部分可剪拼成一个长方形(不重叠 2020-05-14 …
当n等于1时m等于3,n等于2时m等于6,n等于3时m等于10,n等于4时m等于15,求m与n的关 2020-05-22 …
圆锥底面半径为R,母线长3R,M是底面圆上一点,从点M拉一条绳子绕圆锥一圈,再回到点M,求M这根绳 2020-06-06 …
应用题.闻名世界的万里长城总长达50000千米,它的主体部分是在秦朝.汉朝.和明朝修建的,这三个朝 2020-07-28 …
30mT梁梁边长和梁长的区别小弟路桥专业刚出来实习现在回学校了,看到预制厂的预制梁的长度不是图纸上的 2020-11-07 …
然后回答后面的问题.一会议室有长椅m条,今有若干人再会议室开会,若一部分长椅每条坐a人,另椅条坐b人 2020-11-18 …
匀速提起重绳之迷!一根重绳,质量M,长L,拉直放在水平地面上,水平面是光滑的,以速度V匀速提起,求当 2020-11-27 …
高二数学圆动点M圆心轨迹方程问题已知圆C:(x-1)^2+y^2=11,一动点M到y轴的距离等于它到 2020-12-05 …
自由释放的滑块m在斜面上匀速下滑时,M对水平地面的静摩擦力为零,这一过程中在m上加上任何方向的作用力 2021-01-16 …