请问老师，数组已满先resize再增加元素，时间复杂度是不是O(2n)=O(n)?

Question

最坏情况，遍历两遍数组的时间复杂度是O(2n)吧

请问老师，这个想法是对的么？

Answer 1

liuyubobobo 2019-04-17 17:12:13

抱歉，我没有理解你的意思，为什么要遍历两遍数组？哪两遍？

• 提问者 rannrann #1

  老师不好意思，没表达清楚……
  嗯，假设一种情况。调用addFirst，数组容量已满，执行resize，时间复杂度为O(n)；然后在遍历一遍数组增加元素，时间复杂度为O(n)
  
  请问老师对于这种情况整体时间复杂度是O(2n)么？

• liuyubobobo 回复 提问者 rannrann #2

  你可以写O(2n)，但其实在大O面前，常数项是没有意义的。O(2n) = O(n)，所以你说O(n)就可以了：）