对于数组的添加操作时间复杂度分析
来源：2-8 简单的复杂度分析
30K必胜
2019-01-13
开始第二遍看这个教程，但是有些地方还是没想通，比如数组的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) 请教老师，我分析的结论在哪个环节出了问题。
写回答
1回答
-
你的这个公式把在index = 0, 1, 2, ... , n ，n次添加操作的时间复杂度给加了起来；
所以是执行n次添加操作的时间复杂度是O(n^2)；
平均每次添加操作的时间复杂度是：O(n^2)/n = O(n) ：）
00
