数据结构之顺序表上基本运算的实现[11]

算法

删除算法的时间性能分析

与插入运算相同其时间主要消耗移动在表中元素上删除第i个元素时其后面的元素 ai+～an 都要向上移动一个位置共移动了 ni 个元素所以平均移动数据元素的次数为

由于≤ i≤ n共有 n 个删除位置在等概率情况下pi =/ n则

因此在顺序表上做删除操作运算该算法的时间复杂度为O(n)

请读者思考在上述删除算法中被删除的数据元素并没有保存下来如果要保存的话算法应如何修改?

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []