在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是为什么是O（n)?

Question

如题所述

Answer 1

因为单链表保存的信息只有表头 如果要在特定位置插入一个节点 需要先从表头一路找到那个节点。

数量级递增排列，常见的时间复杂度有：

常数阶O(1),对数阶O(  ),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

扩展资料：

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。 

参考资料来源：百度百科-时间复杂度

Answer 2

因为单链表保存的信息只有表头 如果要在特定位置插入一个节点 需要先从表头一路找到那个节点 这个过程是O(n)的本回答被提问者采纳