V数组下标 内存 元素序号 V数组下标 内存 元素序号 0 ar 0 a 1 a 2 1 a2 2 i-1 ai i-1 X i+1 a i+l ai+l n-】 an n-1 an-I n n n+1 n an n+1
内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 an-1 x
冬算法时间复杂度T(n) ●设P是在第个元素之前插入一个元素的概率，则在长度为门 的线性表中插入一个元素时，所需移动的元素次数的平均次 数为： Ei= i=1 若认为=1 +1 1 n+1 则Ei= n+1 (n-i+1)= i=1 ∴.T(n)=O(n)
❖算法时间复杂度T(n) ⚫设Pi是在第i个元素之前插入一个元素的概率，则在长度为n 的线性表中插入一个元素时，所需移动的元素次数的平均次 数为： + = = − + 1 1 ( 1) n i i Eis P n i T(n) O(n) n n i n Eis n P n i i = − + = + = + = + = 1 1 2 ( 1) 1 1 1 1 则 若认为
★删除 冬定义：线性表的删除是指将第ⅰ（1≤≤门)个元素删除 使长度为n的线性表 (a1,a2.2a,-12a,.an） 变成长度为n-1的线性表 (a1a2.a-1,a+1,.am) 需将第i+l至第n共(n-i)个元素前移 必算法 Ch2 2.txt Ch2 2.c
删除 ❖定义：线性表的删除是指将第i（1i n）个元素删除， 使长度为n的线性表 (a1 ,a2,,ai−1 ,ai , an ) 变成长度为n-1的线性表 (a1 ,a2,,ai−1 ,ai+1 , an ) 需将第i+1至第n共（n-i)个元素前移 ❖算法 Ch2_2.c
V数组下标 内存元素序号 V数组下标 内存 元素序号 0 ar 0 a 1 a2 2 1 a 2 i-1 ai i-1 ai+ i aitl i+1 i a+2 计1 n-1 an n n-2 an n-1 n n+1 n-1 n
内存 a1 a2 ai ai+1 an 0 1 i-1 V数组下标 n-1 i n 1 2 i 元素序号 i+1 n n+1 内存 a1 a2 ai+1 V数组下标 0 1 i-1 n-2 i n-1 1 2 i 元素序号 i+1 n-1 n an ai+2