40888888888 2023-01-04 20:19 采纳率: 82.8%
浏览 31
已结题

链表的时间复杂度计算

img


最坏的比较次数是如何计算的，如果m里的元素都要和n里面的做比较，那不应该是m*n次吗

  • 写回答

1条回答 默认 最新

  • 努力学习的小马 新星创作者: C/C++技术领域 2023-01-04 20:46
    关注

    建链表的方法有头插法和尾插法，使用头插法的链表是降序的，使用尾插法的链表是升序的。这题可以考虑为原始的两个链表是升序的，设置两个指针进行数据元素的大小比较，两个元素比较一次大小算作一次。在比较的过程中，同时建立一条新链表，其新建方法用头插法就能达到降序的效果，
    m和n中短的链表结束后就不用再去比较了，直接将长链表剩下的所有元素用头插法插到c链表前面即可，所以最坏情况下就是max（m，n）。我是这么理解的

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

问题事件

  • 系统已结题 1月12日
  • 已采纳回答 1月4日
  • 创建了问题 1月4日