weixin_42165032 2022-07-20 13:54 采纳率: 100%
浏览 30
已结题

两个规模均为n的线性表合并一个表

怎么样合并时间复杂度为o(1)和o(n)呢 一般情况下是(n)吧，那o（1)怎么达到呢 求解谢谢！

  • 写回答

1条回答 默认 最新

  • 於黾 2022-07-20 14:08
    关注

    首先，一般情况下合并时间应该是O(n^2)
    两个表遍历一遍就已经是O(n)了
    没有任何方式能不遍历就排序，什么O(1)理论上就不可能实现
    那么如果是链表，只需要插入不需要按位挪动数据，那么时间复杂度就是遍历所需要的时间，是O(n)
    而如果顺序表（线性表），每插入一个数据，所有后续数据要按位挪动，挪动不需要操作吗
    平均下来应该是n^2/2次，在n很大时常数可以忽略，所以是O(n^2)
    -=-=-=
    想要快，那么就用空间换时间，不是在已有的线性表里插入数据然后挪动数据
    而是先建立一个空的，长度是两个表长度之和的线性表
    然后遍历两个表，比较大小，每次都把较小的那个按顺序放入新表，那么这个时间复杂度就是O(n)
    什么O(1)就别想了，不可能的

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

报告相同问题？

问题事件

  • 系统已结题 8月4日
  • 已采纳回答 7月27日
  • 创建了问题 7月20日

悬赏问题

  • ¥20 wireshark抓不到vlan
  • ¥20 关于#stm32#的问题：需要指导自动酸碱滴定仪的原理图程序代码及仿真
  • ¥20 设计一款异域新娘的视频相亲软件需要哪些技术支持
  • ¥15 stata安慰剂检验作图但是真实值不出现在图上
  • ¥15 c程序不知道为什么得不到结果
  • ¥40 复杂的限制性的商函数处理
  • ¥15 程序不包含适用于入口点的静态Main方法
  • ¥15 素材场景中光线烘焙后灯光失效
  • ¥15 请教一下各位，为什么我这个没有实现模拟点击
  • ¥15 执行 virtuoso 命令后，界面没有，cadence 启动不起来