对于数组的添加操作时间复杂度分析

Question

开始第二遍看这个教程，但是有些地方还是没想通，比如数组的add(index,e) 的时间复杂度是O(n/2),而我得出的却不是，因为index在每个位置都分为“出现”与“不出现”这两种情况，因此它的概率是1/2，比如，index =1 那就意味着移动(n-1)个元素，index = 10 ,意味着移动(n-10)个元素 ，以此类推，所以可以列出公式 1/2*0+1/2*1+1/2*2+.......+1/2*(n-1) = 1/2*(1+2+3+....+n) = 1/2 *(1+n-1)+1/2 =n^2/2+1/2 =O(n^2)    请教老师，我分析的结论在哪个环节出了问题。

Answer 1

liuyubobobo 2019-01-14 01:37:40

你的这个公式把在index = 0, 1, 2, ... , n ，n次添加操作的时间复杂度给加了起来；

所以是执行n次添加操作的时间复杂度是O(n^2)；

平均每次添加操作的时间复杂度是：O(n^2)/n = O(n) ：）