插入操作的算法性能分析 据结构 >空间复杂度是O(1) >时间复杂度:O(m),其中n= Llength 步骤(1)、(2)、(4)的时 间复杂度都是常数,即:O(1); 步骤(3)的基本操作是数据移动 线性表 最坏的情况下(在第一个位置上插入元素), 需要移动n个元素; 平均情况下(等概率),需移动表中n/2 个元素,最好的情况是不移动元素 因此,插入操作算法的时间复杂度是Om) 删除操作:长为n的线性表L(a1,a2,… 数据结构 an),删除a1,并把它送入某单元e n-1 n-1 18 顺序存储结构的删除操作9 数 据 结 构 之 线 性 表 17 ¾插入操作的算法性能分析 ¾空间复杂度是 O( 1 ) ¾时间复杂度： O(n) , 其中n= L.length ¾步骤（１）、（２）、（４）的时 间复杂度都是常数，即：O ( 1 ); ¾步骤（３）的基本操作是数据移动， 最坏的情况下(在第一个位置上插入元素)， 需要移动n个元素； 平均情况下（等概率），需移动表中 n/2 个元素，最好的情况是不移动元素。 因此，插入操作算法的时间复杂度是O(n); 数 据 结 构 之 线 性 表 18 ¾ 删除操作：长为n的线性表L(a1,a2, … , an ), 删除ai ，并把它送入某单元e e ai a1 a2 a3 ai-1 ai an : : 1 2 3 i-1 i n-1 i+1 n : : a1 a2 a3 ai-1 an : : 1 2 3 i-1 i n-1 i+1 n : : ai+1 顺序存储结构的删除操作