两个升序链表合并成一个降序链表的时间复杂度

王道考研P7 第六题

【2013年统考真题】已知两个长度分别为m和n的升序链表，若将它们合并为长度为m+n的一个降序链表，则最坏情况下的时间复杂度是（）

A. O(n)

B. O(mn)

C. O(min(m,n))

D. O(max(m,n))

答案是D

注意，此题中的时间复杂度并不是指移动的次数，因为你无论如何怎么移动，移动的次数都是m+n，这里指的是链表中元素的比较次数。

比较的最好情况是一个链表n比另一个链表m短，并且链表n的最大元素比链表m的最小元素小，所以比较的时间复杂度是O(min(n,m))

为什么是O(min(n,m))??

如下图所示

用双指针比较的话，步骤如下

指针分别指向n[1]和m[1]

①1和2比较，1小，出去了，n指针指向3，m指针还是指向2

②2和3比较，2小，出去了，n指针指向3，m指针指向4

③3和4比较，3小，出去了，n指针指向5，m指针指向4

④4和5比较，4小，出去了，n指针指向5，m指针指向6

⑤5和6比较，5小，出去了，n指针指向7，m指针指向6

⑥6和7比较，6小，出去了，n指针指向7，m指针指向8

⑦7和8比较，7小，出去了，n链表结束，8插在7后面

所以一共比较了m+n-1次

在最坏情况下，不管n和m是多长，只要相互交错的情况下，比较的次数就是m+n-1

例如下面的情况也是m+n-1

n链表中5比较了三次，8比较了三次，10比较了三次，13比较了三次，一共是4+6-1=9次

但是，答案中并没有O(n+m-1)或O(n+m)这个选项

注：当n和m无限大的时候，-1忽略掉

这里就需要提醒的是，时间复杂度是一个级数概念，即O(2n)，O(n+1000)，,O(n-50)，都是属于O(n)这个级别（范畴）
并且是一个线性变化的常数项级，同理O(m)也一样

包括取大去小原则

如果一个算法的时间复杂度是n³＋n²+n+1

那么算法复杂度是O(n³)

回到题目，如果我们以链表m长度远大于链表n的情况下来看，那么在相互比较的情况下，O(m+n)是否可以看成O(m)？同理，如果我们以链表n长度远大于链表m的情况下来看，O(m+n)是否可以看成O(n)？

那么结论就是：O(m+n)==O(max(m,n))

当然也可以用夹逼定理去说明这个结论

O(max(m,n))≤O(m+n)≤2O(max(m,n))

2O(max(m,n))还是属于O(max(m,n))这个级别

所以可证：O(m+n)==O(max(m,n))

所以答案就是D

本篇博客有参考本题类似的解答（一开始我也对这题的答案感到不解，去百度搜了下，最后总结），研友在参考解答的时候也可以提出自己的疑问！