顺序表的时间复杂度简单计算

Question

n/2是怎么得来的？

Answer 1

每个位置概率是1/(n+1)，可以插入的位置是0~n。插在位置0需要移动n个元素，插在位置n需要移动0个元素，那么插在位置k就需要移动n-k个元素。
平均次数是(1+2+3+......+n)/(n+1)=(n(n+1)/2)/(n+1)=n/2(等差数列求和)