Question

一个关于数据结构线性表的题

一个关于数据结构线性表的题在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂性为______。
A．O(1)
B．O(n)
C．O(n2)
D．O(log2n)
求给出解释，谢谢

Answer 1

假设有序的链表存放的都是整数，其值为：1,2，。。。。，n
逆序的分析也是一样的。
（1）如果你插入1，那么时间是1个单位时间；
（2）如果你要插入n+1,那么时间是n个单位时间；
（3）如果你要插入n/2，那么时间是n/2个时间；
那么算法复杂度到底以哪个为准呢？
算法分析里有约定，这种情况我们假设插入的数据可以是任意的数，那么各种情况下平均的插入时间作为算法的时间复杂度。
明显平均时间是(1+2+。。。+n)/n=(1+n)*n/2/n=(1+n)/2约等于0.5n;
算法分析里也有约定，对于时间是n的k倍的：k*n，其中k为常数，那么算法复杂度统一称为O(n)，也就是说你的算法时间不管是（1/10000）*n还是10000*n，其实都是一样的复杂度。

所以这一题选B