若长度为n的线性表采用顺序存储结构,在第i≤1≤i≤n＋1) 个位置插入一个新元素的算法时间复杂度为(1)

Question

若长度为n的线性表采用顺序存储结构，在第i≤1≤i≤n+1) 个位置插入一个新元素的算法时间复杂度为(1)。

A．O(0)

B．O (1)

C．O(n)

D．O(n2)

Answer 1

正确答案：C
解析：性表上插入元素，时间主要耗费在移动元素上。不失一般性，假定性表上的任何位置插入元素是等概率的，即：Pi=1/(n+1)，那么在插入一个元素时所需要移动元素的次数的平均值为：。因此，在长度为n的线性表中插入一个元素的时间复杂度为。