当前位置：首页 -> 基础 -> 数据库编程

数据结构-线性表顺序存储结构(二)

2015-07-24 06:09:01 · 作者: · 浏览: 4
标签: 数据结构 线性 顺序 存储 结构
中的位置为i ，则在线性表L中删除第i个元素。
设在线性表L删除数据元素概率为Pi，不失一般性，设各个位置是等概率，则Pi=1/n。
◆ 比较的平均次数： Ecompare=∑pi*i (1?i?n)
∴ Ecompare=(n+1)/2 。
◆ 删除时平均移动次数：Edelete=∑pi*(n-i) (1?i?n)
∴ Edelete=(n-1)/2 。
平均时间复杂度：Ecompare+Edelete=n ，即为O(n)