插入算法的时间性能分析 ◆顺序表上的插入运算,时间主要消耗在了数据的移动上, 在第价个位置上插入x,从a1到an都要向下移动一个位置, 共需要移动n-1+1个元素,而1的取值范围为:1sks n+1,即有n+1个位置可以插入。设在第个位置上作插入 的概率为P,则平均移动数据元素的次数: 设:P=1/(n+1),即为等概率情况,则: n+1 n+1 pic (n-i+1) n ◆这说明:在顺序表上做插入操作需移动表中一半的数据 元素。显然时间复杂度为O(n) 2021年1月21日 数据结构讲义2021年1月21日 数据结构讲义 9 插入算法的时间性能分析 顺序表上的插入运算，时间主要消耗在了数据的移动上， 在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置， 共需要移动 n－i＋1个元素，而 i 的取值范围为 ：1≤ i≤ n+1，即有 n＋1个位置可以插入。设在第i个位置上作插入 的概率为Pi，则平均移动数据元素的次数： 设：Pi=1/ (n+1) ，即为等概率情况，则： 这说明：在顺序表上做插入操作需移动表中一半的数据 元素。显然时间复杂度为Ｏ(n)。  + = = − + 1 1 E ( 1 ) n i i n i p n i