5.顺序表（续）

5.顺序表（续）

顺序表主要操作的性能分析

顺序表所有操作的实现中，最复杂、最耗时的就是查找、插入和删除操作的实现。分析顺序表主要操作的性能，主要分析这三个操作实现代码的时间代价。

1.查找操作的性能分析

程序2-8所示的函数Search是顺序表的顺序查找算法，算法的时间代价用数据比较次数来衡量。在查找成功的场合，若要找的正好是表中第一个元素，数据比较次数为1，这是最好的情况；若要找的是表中最好的第n个元素，数据比较次数为n（设表的长度为n），这是最坏的情况。若要计算平均数据比较次数，需要考虑个个元素的查找概率pi及找到该元素时的数据表交次数ci。查找的平均数据比较次数ACN（Average Comparing Number）为

ACN=∑pi•ci （∫1～n）

计算平均值是为了了解算法对表操作的整体性能。若仅考虑相等查找概率大情形，有p1=p2=…=pn=1/n，且查找第一个元素的数据比较次数为1，查找第二个元素的数据比较次数为2，……，查找第i个元素的数据比较次数为i，则

ACN=∑(1/n)i=(1/n)∑i=(1/n)(1+2+…+n)
=(1/n)•(n+1)n/2=(n+1)/2（∫1～n）

即平均要比较(n+1)/2个元素

在查找不成功的场合，需要把整个表全部检测一遍，数据比较次数达到n次

2.插入与删除操作的性能分析

在顺序表中插入一个新元素时，如果要求插入后仍保持各元素原来的互相位关系，就必须做元素的成块移动。

[例 2-1] 在新元素x插入到指定位置后i前，必须把从i到n的所有元素成块向后移动一个元素位置，空出第i个位置后才可插入新元素，如下表所示

在顺序表中删除一个元素时，如果要保持表中个元素原来的互相位置关系，就必须做元素的成块移动。

[例 2-2] 删除第i个元素后必须把从i+1到n的所有元素成块向前移动一个元素位置，如下表所示