2.2.2 顺序表中基本操作的实现

 六、插入和删除操作的性能分析

  试问,在顺序表中任何一个合法位置上进行"一次"插入或删除操作时,需要移动的元素个数的平均值是多少?

  令 表示在长度为 n 的顺序表中进行一次插入操作时所需进行"移动"元素个数的期望值(即平均移动个数),则
   

  其中,是在第 i 个元素之前插入一个元素的概率,n-i+1 是在第 i 个元素之前插入一个元素时所需移动的元素个数。由于可能插入的位置 i=1,2,3,…,n+1 共 n+1 个,假设在每个位置上进行插入的机会均等,则
   

  由此,在上述等概率假设的情况下,
   

  类似地,令 表示在长度为 n 的顺序表中进行一次删除操作时所需进行"移动"元素个数的期望值(即平均移动个数),则
   

  其中,是删除第 i 个元素的概率,n-i 是删除第 i 个元素时所需移动元素的个数。同样假设在 n 个可能进行删除的位置 i=1,2,…,n 机会均等,则
   

  由此,在上述等概率的假设下,
   

  由此可见,在顺序存储表示的线性表中插入或删除一个数据元素,平均约需移动表中一半元素。这个数目在线性表的长度较大时是很可观的。这个缺陷完全是由于顺序存储要求线性表的元素依次紧挨存放造成的。因此,这种顺序存储表示仅适用于不常进行插入和删除操作、表中元素相对稳定的线性表。

 



  前面已经分析过,在顺序表中插入或删除一个数据元素的操作的时间复杂度为O (ListLength(L)),而实际上,基本操作(移动元素)的执行次数不仅和表长有关,还依赖于插入和删除的位置。由于插入和删除可能在线性表的任何位置上进行,则从统计意义上讲,考虑在顺序表的任一位置上进行插入或删除的"平均时间特性"更有实际意义。