4.6 技术解惑

4.6.1 顺序表插入操作的时间复杂度是多少

在顺序表上实现插入操作的过程看似比较复杂，其实实现起来比较简单，只是一个插入并重新排序的过程。在整个过程中，时间主要消耗在数据的移动上。在第i个位置插入一个元素，从ai到an都要向后移动一个位置，一共需要移动n−i+1个元素。i的取值范围为1≤i≤n+1。当i等于1时，需要移动的元素个数最多，为n个；当i为n+1时，不需要移动元素。如果在第i个位置插入的概率为pi，则平均移动数据元素的次数为n/2。这说明在顺序表上执行插入操作，平均需要移动表中一半的数据元素。所以，插入操作的时间复杂度为O(n)。