2.2.2 顺序表中基本操作的实现 六、插入和删除操作的性能分析 试问,在顺序表中任何一个合法位置上进行"一次"插入或删除操作时,需要移动的元素个数的平均值是多少? 令 表示在长度为 n 的顺序表中进行一次插入操作时所需进行"移动"元素个数的期望值(即平均移动个数),则 其中,是在第 i 个元素之前插入一个元素的概率,n-i+1 是在第 i 个元素之前插入一个元素时所需移动的元素个数。由于可能插入的位置 i=1,2,3,…,n+1 共 n+1 个,假设在每个位置上进行插入的机会均等,则 由此,在上述等概率假设的情况下,
类似地,令
表示在长度为 n 的顺序表中进行一次删除操作时所需进行"移动"元素个数的期望值(即平均移动个数),则 |
前面已经分析过,在顺序表中插入或删除一个数据元素的操作的时间复杂度为O (ListLength(L)),而实际上,基本操作(移动元素)的执行次数不仅和表长有关,还依赖于插入和删除的位置。由于插入和删除可能在线性表的任何位置上进行,则从统计意义上讲,考虑在顺序表的任一位置上进行插入或删除的"平均时间特性"更有实际意义。 |