王道数据结构上一道题：

 

之前我看到一个电子版的书，上边答案解析写的有点错误，

听说有些同学买的实体书上，答案解析也是这样写的

这个是刊印错误，很显然2Max( m , n )大于等于 m + n

而且这个解析也不够清晰。

解析：选D

两个升序合并为降序，操作就不多说了，两数列依次比较放入，其中一个数列结束了，剩下的就不用比了，直接依次放进去。

首先明确，题目让我们求复杂度，这里显然不是讨论移动次数，因为不论什么情况，移动次数都是(M+N)，不需要讨论

所以这里求的是合并过程中的比较次数

最好的情况，很容易想，就是长度较短的数列中最小的数还比另一个数列最大的数字大，如(7 8 9和 1 2 3 4 )，这种情况需要比较min(m,n)次就好了，复杂度为O(min(m,n))。

最差的情况，什么是最差情况，就是比较的次数最多。怎么算呢，要这样想，两个数列移动元素的次数一定是m+n，不可能比这个还多，那么如果每一次移动都需要比较，岂不就是最差情况？但是注意，最后一次移动是一定不需要比较的，因为剩最后一个元素的时候，必然另一个数列已经结束了，所以不用比。故最坏情况比较次数为(m+n-1) 次

给几个例子试试：1 3 5 7 9 和 2 4 6 8 10      /     1 3 5 和 2 4 

那么，题目要求最坏情况复杂度，就是O(m+n-1)咯

可是选项没有，哈哈，别急，比较次数是 (m+n-1) 次，m和n的次幂都是1，所以复杂度也是一次就行了，那么到底是O(n)还是O(m)呢，肯定选最大的那个啊，因为是最坏情况，故复杂度为O(Max(m,n))

-------------------------------------------------------------------------------------------------------------------------------