也就是说，在顺序表上做插入运算，平均要移动 表上一半结点。当表长n较大时，算法的效率相 当低。虽然Esn)中n的系数较小，但就数量级而 言，它仍然是线性阶的。因此算法的平均时间复 杂度为On)。 2、删除 线性表的删除运算是指将表的第i(1s≤n) 结点删除，使长度为n的线性表： (a1,.ai-1,aj,ait1.,an) 变成长度为n-1的线性表 (a1,.ai-1yait1,an》
也就是说，在顺序表上做插入运算，平均要移动 表上一半结点。当表长 n较大时，算法的效率相 当低。虽然Eis(n)中n的系数较小，但就数量级而 言，它仍然是线性阶的。因此算法的平均时间复 杂度为O(n)。 2、删除 线性表的删除运算是指将表的第i(1≦i≦n) 结点删除，使长度为n的线性表： (a1，.a i-1，ai，a i+1.，an ) 变成长度为n-1的线性表 (a1，.a i-1，a i+1，.，an )
1.[初值] 获取线性表L,删除位置 2.[检查参数] 若（删除位置超出线性表长度范围）则输出错误 3.[删除元素] 获取删除位置i的元素e 将删除位置之后的L中的元素全部前移一格 线性表长度减1 4.[算法结束]
1.[初值] 获取线性表L，删除位置i 2.[检查参数] 若 （删除位置超出线性表长度范围） 则 输出错误 3.[删除元素] 获取删除位置i的元素e 将删除位置i之后的L中的元素全部前移一格 线性表长度减1 4.[算法结束]
该算法的时间分析与插入算法相似，结点的移动次数也是 由表长n和位置i决定。 若=n,则由于循环变量的初值大于终值，前移语句将 不执行，无需移动结点： 若i=1,则前移语句将循环执行-1次，需移动表中除开 始结点外的所有结点。这两种情况下算法的时间复杂度分 别为0(1)和0)。 删除算法的平均性能分析与插入算法相似。在长度为 的线性表中删除一个结点，令Eden)表示所需移动结点的 平均次数，删除表中第i个结点的移动次数为-i,故 Ed(n) ■式中，p表示删除表中第i个结点的概率。在等
该算法的时间分析与插入算法相似，结点的移动次数也是 由表长n和位置i决定。 若i=n，则由于循环变量的初值大于终值，前移语句将 不执行，无需移动结点； 若i=1，则前移语句将循环执行n-1次，需移动表中除开 始结点外的所有结点。这两种情况下算法的时间复杂度分 别为O(1)和O(n)。 删除算法的平均性能分析与插入算法相似。在长度为n 的线性表中删除一个结点，令Ede(n)表示所需移动结点的 平均次数，删除表中第i个结点的移动次数为n-i，故 式中，pi表示删除表中第i个结点的概率。在等 = = − n i d e i E n q n i 1 ( ) ( )
概率的假设下， p1Fp2=p3=.=pn=1/n 由此可得： E(n) 即在顺序表上做删除运算，平均要移动表中约一半的结点， 平均时间复杂度也是O()。 2.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来 表示结点间的逻辑关系，这一特点使我们可以随机存取表 中的任一结点，但它也使得
概率的假设下， p1=p2=p3=.=pn=1/n 由此可得： 即在顺序表上做删除运算，平均要移动表中约一半的结点， 平均时间复杂度也是O(n)。 2.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来 表示结点间的逻辑关系，这一特点使我们可以随机存取表 中的任一结点，但它也使得 2 1 ( ) 1 ( ) 1 − = − = = n n i n E n n i d e