首页 > 试题广场 >

设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单

[单选题]

设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为()。

  • O(log2n)
  • O(1)
  • O(n2)
  • O(n)
注意题目是有序
发表于 2022-02-25 15:08:06 回复(0)
他也没说在那插呀  o(n)的情况应该是尾插吧
发表于 2018-09-09 11:04:06 回复(0)
插入的这个过程时间复杂度虽然是O(1),但是遍历的这个过程时间复杂度为O(n)。
发表于 2018-05-06 16:36:38 回复(4)
如果是顺序表,则可以用二分法先定位,但是这是单链表,只能从头一个一个比。
编辑于 2018-01-18 09:14:49 回复(1)
时间复杂度看有没有循环 单链表插入新节点必然要用到循环 时间复杂度就是O(n)。Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)
发表于 2017-08-01 14:47:22 回复(0)
单链表插入不需要移动元素,时间复杂度为O(1),但是要保持有序状态,顺序存取需要按位置访问元素时间复杂度为O(n)。
发表于 2020-06-07 09:25:04 回复(0)
最好时间复杂度是O(1),最坏时间复杂度是O(n)
而一般都是用最坏时间复杂度进行评定,所以是O(n)
发表于 2020-09-03 17:17:13 回复(0)
插入的时间复杂度为O(1),但查找的时间复杂度为O(n),故整个操作的时间复杂度为O(1)+O(n)=O(n)。
发表于 2023-10-21 11:35:24 回复(0)
插入操作时间复杂度为O(1),但是遍历时间复杂度为O(n)
发表于 2020-12-17 14:40:38 回复(0)
害,被O(1)迷昏了头脑,就算插入操作的时间复杂度是O(1),还得遍历过去不是,总的来说还是O(n)
发表于 2020-10-09 20:47:18 回复(0)
刷完链表这一部分就能找到——还有一个删除链表元素的时间复杂度是只看删除操作来算记作O(1)的,而不是算查找+删除。那道题是拿链表结构自身,删除、插入和查找比的。
发表于 2020-08-10 22:00:25 回复(0)
需要查找到需要插入的节点位置  
发表于 2020-03-09 15:52:09 回复(0)
链表的查询时间是o(n)
发表于 2017-08-07 22:49:13 回复(0)