马克斯·真题

Wandersss用户错了。即使改成“非降序列表”，确切答案也是O(m+n)，而不是O(max(m，n))。比如列表1是100~999(900个数，m=900)，列表2是1 ~。

我来说说我这个问题的原因。首先，这个问题的精确答案是O(m+n)，但是没有选项，所以我只能选择一个最符合精确答案的选项，即使不一定正确。

假设m大于n，

如果m非常接近n，那么o(m * n)~ = o(N2)> & gt；O(m+n)~=O(2n)，所以b不正确。

如果m & gt& gtn，那么O(m+n)>& gtO(n)，O(m+n)>& gtO(min(m，n)) =O(n)，所以A和C不正确。

o(n)；d、如果m非常接近n，则O(m+n)~=O(2n)约等于O(n)；如果m & gt& gtn，O(m+n)也近似等于O(max(m，n))=O(m)。

合并这个有序链表的问题，如果按照原来的顺序排列，最好是O(min(m，n))，最坏是O (m+n)。如果按原顺序的逆序排列，最好的情况是O(m+n)，最坏的情况是O(m+n)。

一开始，我们讨论的是最坏的情况。先说最好的情况。比如链表1是100~999(900个数，m=900)，链表2是0~99(100个数，n=100)，整个比较数是65438+。