Question

在一个具有n个结点的有序单链表中，插入一个新结点并仍然保持有序的算法时间复杂度是（ ）

在一个具有n个结点的有序单链表中，插入一个新结点并仍然保持有序的算法时间复杂度是（ ） A．O（1） B．O（n） C．O（n 2 ） D．O（nlog 2 n）

Answer 1

在一个具有n个结点的有序单链表中插入一个新结点，并使其仍然有序的时间复杂性为O（n）；因为单链表保存的信息只有表头如果要在特定位置插入一个节点，需要先从表头一路找到那个节点。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

扩展资料：

链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) +指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

Answer 2

答案：选B 时间复杂度是 O（n）
原因：
链接：
最坏时间复杂度是：O（n）
最好时间复杂度是：O（1）
可以求平均时间复杂度：
每一种情况出现的可能性相同所以概率都为1/n+1
1/n+1 + 2/n+1 + 3/n+3 ··········+ n/n+1
= (n+1)*n/ n+1 (等差数列求和)
=n

Answer 3

B