已知两个长度为m和n的升序链表，将他们合并为长度为m+n的降序链表，最坏情况下时间复杂度怎样求

Question

如题所述

Answer 1

已知两个长度为m和n的升序链表将他们合并为长度为m+n的降序链表，最坏情况下时间复杂度怎样求，合并时最坏情况下，长为n的链表中前n-1个都比长为m的链表中的第一元素小，而长为n的链表中最后一元素又比长为m的链表中所有元素大。这样比较元素的次数n+m,则时间复杂度为O(m+n)

Answer 2

两个升序表合并，两两比较表中的元素，每比较一次确定一个元素的位置（取较小的元素，头插法）。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素一次比较，所以时间复杂度是O（max(m,n)）本回答被网友采纳

Answer 3

设a<b，即a=min(m,n)/b=max(m,n)。
两个表都是升序，选择a长度的链表为结果表，a链表的第一个元素开始和b链表第一个元素比较，如果a0 < b0，则将a0插到b0前，然后a1和b0比较，以此类推；
最好情况是a全排在b前，时间复杂度为O(min(m,n))，最坏情况是有元素排在m后，时间复杂度为O(max(m,n))

Answer 4

这里可能比较有争议的就是o（n+m）和o（max（m，n）），按我个人的理解只有以下两种情况，1：m或n其中一个趋于无穷，另一个为常数，复杂度为o（max（m，n））；2：m和n趋于相等，即2m或2n，按复杂度的计算方法来看，无论是2m还是2n，复杂度还是o（max（m，n））

Answer 5

排序是双循环，最坏情况下的时间复杂度即为（m+n）的平方。