4.6.2 顺序表删除操作的时间复杂度是多少

顺序表的删除操作与插入操作一样，时间主要消耗在数据的移动上。当在第i个位置删除一个元素时，从ai+1到an都要向前移动一个位置，共需要移动n−i个元素，而i的取值范围为1≤i≤n。当i等于1时，需要移动n−1个元素；当i为n时，不需要移动元素。假如在第i个位置删除的概率为pi，则平均移动数据元素的次数为(n−1)/2。这说明在顺序表上进行删除操作平均需要移动表中一半的数据元素。所以，删除操作的时间复杂度为O(n)。