删除算法的时间性能分析 ◆与插入运算相同,其时间主要消耗在了移动表中元素上, 删除第个元素时,其后面的元素aan都要向上移动 个位置,共移动了n个元素,所以平均移动数据元素的次 数 e de ∑P 在等概率情况下,p1=1/n,则: E ∑P ∑ 2 ◆这说明顺序表上作删除运算时大约需要移动表中一半的元 素,显然该算法的时间复杂度为O(n)。 2021年1月21日 数据结构讲义2021年1月21日 数据结构讲义 11 删除算法的时间性能分析 与插入运算相同，其时间主要消耗在了移动表中元素上， 删除第i个元素时，其后面的元素 ai+1 ～an 都要向上移动一 个位置，共移动了 n-i 个元素，所以平均移动数据元素的次 数： 在等概率情况下，pi =1/ n，则： 这说明顺序表上作删除运算时大约需要移动表中一半的元 素，显然该算法的时间复杂度为Ｏ(n)。 = = − n i de i p n i 1 E ( )   + = = − == − = − = 1 1 1 2 1 ( ) 1 E ( ) n i n i de i n n i n p n i