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

n/2是怎么得来的？

每个位置概率是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(等差数列求和)

希望能帮到你http://blog.csdn.net/zzy1078689276/article/details/77961691

一般来说，算法的时间复杂度只是一个近似值，只要其精度可以帮助你正确的估算运行时间就行了。
顺序表的时间复杂度为：
最坏：O(n)
最好: O(1)
平均：O((1+2+3+......+n)/(n+1))=O((n(n+1)/2)/(n+1))=O(n/2)

http://blog.csdn.net/zzy1078689276/article/details/77961691