算法时间复杂度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 则 若认为