向一个长度为n的顺序表中第i(1≤i≤n)个元素之间插入一个元素时,需向后移动( )个元素。
【正确答案】:N-I+1
【题目解析】:
顺序表实现算法的分析:
(1)设表的长度length=n,插入算法在最坏情况下,其时间复杂度为O(n)。一般情况下元素比较和移动的次数为n-i+1次,插入算法的平均移动次数约为n/2,其时间复杂度是O(n)。
(2)删除算法,可得其在最坏情况下元素移动次数为n-1,时间复杂度为O(n),元素平均移动次数约为(n-1)/2,时间复杂度为O(n)。
向一个长度为n的顺序表中第i(1≤i≤n)个元素之间插入一个元素时,需向后移动( )个元素。
顺序表实现算法的分析:
(1)设表的长度length=n,插入算法在最坏情况下,其时间复杂度为O(n)。一般情况下元素比较和移动的次数为n-i+1次,插入算法的平均移动次数约为n/2,其时间复杂度是O(n)。
(2)删除算法,可得其在最坏情况下元素移动次数为n-1,时间复杂度为O(n),元素平均移动次数约为(n-1)/2,时间复杂度为O(n)。