V数组下标内存元素序号V数组下标内存元素序号 0 a 0 ar a 2 a a i ai a i ai+ n-1 an n n an-1 n+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 内存 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是在第个元素之前插入一个元素的概率,则在长度为n 的线性表中插入一个元素时,所需移动的元素次数的平均次 数为: Es=∑P(n-l+1) 若认为P n+ 则Eis= +1 ∑(n-+1) T
❖算法时间复杂度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 则 若认为
★删除 ☆定义:线性表的删除是指将第i(1si≤n)个元素删除, 使长度为∩的线性表 变成长度为n-1的线性表 19 i15i+15 需将第i+1至第n共(ni)个元素前移 今算法 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 a 0 ar a 2 a a i ai ai ai+2 n-1 an n n- n 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