数据结构之顺序表上基本运算的实现[8]

算法

顺序表的插入运算时间主要消耗在了数据的移动上在第i个位置上插入 x 从 ei 到 en 都要向下移动一个位置共需要移动 ni+个元素设在第i个位置上作插入的概率为Pi则平均移动数据元素的次数

由于 ≤ i≤ n+共有 n+个位置可以插入即在等概率情况下pi=/ (n+)则

因此在顺序表上作插入运算该算法的时间复杂度为O(n)

顺序表的删除运算

顺序表的删除运算是指将表中第 i 个元素从线性表中去掉删除后使原表长为 n 的线性表 (ee eieiei+en)变为表长为 n 的线性表

(ee ei ei+ en) 其中i≤ i≤ n

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []