已知两个长度分别为m和n的升序链表若将它们合并为一个长度为m+n的降序链表,则最坏情况下的时间复杂度是A.O(n)B.O(mn)C.O(min(m,n))D.O(max(m,n))

Question

已知两个长度分别为m 和n 的升序链表
若将它们合并为一个长度为m+n 的降序链表,则
最坏情况下的时间复杂度是
A.O(n) B.O(mn) C.O(min(m,n)) D.O(max(m,n))

Answer 1

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）的后面.