王道书第七面的第六题，理解了一下午终于解决！
- 算法的本质：两个表进行比较，其中一个表比较完之后，剩下的直接插入。
- 因此最好的情况，不用想的太复杂，其实就只是短的那个表比较完了：O（min(m,n)）。
- 最坏的情况，就只是长的那个表比较完了：O（max(m,n)）
课后答案证明，用了极限：
O(max(m,n))等价于O(m+n)。
就是m+n>=max(m,n)且m+n<=2max(m,n)，三者取量级，所以O(m+n)和O(max(m,n))等价，夹逼定理。
- 最好情况举例，1，2和3，5，9。1和3比，头部插1，2和3比，头部插2，短的升序链表全部比完且插入完，剩下的长的链表按顺序头部插入。形成9，5,3,2,1.
- 最差情况举例，1,3,5和2,6。头部插入法，12比，先插1，32比，插2，36比，插3，56比，插5，此时长的链表全部比完且都已插入，另一个链表剩下的元素按顺序头部插入即可。形成6,5,3,2,1
。一共插入了5个元素，但只比了4次，因为当一个链表已经全部插入完的时候，另一个链表还会剩一个元素或者很多个元素，如13578,26，这里的578最后都会用头插法按序插入，不需要再比较，相当于”1”，这种最坏情况下的时间复杂度其实是o(n+m-1)。这个减1是因为最后一个元素不需要再和另一个链表比较了，因为另一个链表已经没元素了。
而o(n+m-1)=o(m+n),再用上面那个夹逼一下，就是答案了o(max(m,n))了。
结束，索然无味。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
