2.2.3 基本操作算法分析

在以上顺序表的基本操作算法中，除了按内容查找运算、插入和删除操作外，算法的时间复杂度都为O（1）。

在按内容查找的算法中，如果要查找的元素在第一个位置，则需要比较一次；如果要查找的元素在最后一个位置，则需要比较n次（n为线性表的长度）。设p_i为在第i个位置上找到与e相等元素的概率，假设在任何位置上找到元素的概率相等，即p_i=1/n。则查找过程中需要比较的平均次数为：

因此，按内容查找的平均时间复杂度为O（n）。

在顺序表的插入算法中，时间的耗费主要集中在移动元素上。如果要插入的元素在第一个位置，则需要移动元素的次数为n次；如果要插入的元素在最后一个位置，则需要移动元素的次数为1次；如果插入位置在最后一个元素之后，即第n+1个位置，则需要移动元素的次数为0次。设p_i为在第i个位置上插入元素的概率，假设在任何位置上找到元素的概率相等，即p_i=1/（n+1）。则顺序表的插入操作需要移动元素的平均次数为：

因此，插入操作的平均时间复杂度为O（n）。

在顺序表的删除算法中，时间的耗费同样在移动元素上。如果要删除的元素是第一个元素，则需要移动元素的次数为n-1次；如果要删除的元素是最后一个元素，则需要移动0次。设p_i表示删除第i个位置上的元素的概率，假设在任何位置上找到元素的概率相等，即p_i=1/n。则顺序表的删除操作需要移动元素的平均次数为：

因此，删除操作的平均时间复杂度为O（n）。