本算法的主要时间花在元素移动上,元素移动的次数不 仅与表长n有关,而且与插入位置有关,共有n+1个位置可以 插入元素:当n1时,移动次数为0;当i1时,移动次数为 n,达到最大值。假设每个位置插入元素的概率相同,P表示 在第个位置上插入一个元素的概率,则=1(n+1),所以在长 度为n的线性表中插入一个元素时所需移动元素的平均次数为: n(n+ P2(n-+1 (n-2+1) (n-2+1) n+1本算法的主要时间花在元素移动上，元素移动的次数不 仅与表长n有关，而且与插入位置i有关，共有n+1个位置可以 插入元素：当i=n+1时，移动次数为0；当i=1时，移动次数为 n，达到最大值。假设每个位置插入元素的概率相同，pi表示 在第i个位置上插入一个元素的概率，则pi=1/(n+1)，所以在长 度为n的线性表中插入一个元素时所需移动元素的平均次数为：