怎么样合并时间复杂度为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)就别想了,不可能的本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报 编辑记录