【文件属性】：
文件名称：时间复杂度分析-数据结构全套
文件大小：3.3MB
文件格式：PPT
更新时间：2021-04-25 23:12:41
数据结构
时间复杂度分析
在线性表L中的第i个元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中的第i个元素之前插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。
总的平均移动次数： Einsert=∑pi*(n-i+1) (1≦i≦n)
∴ Einsert=n/2 。
即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。