关于testQueue时间复杂度

Question

【问题】

在视频第8分钟，提到testQueue的时间复杂度，对于ArrayQueue来说，enqueue时间复杂度是0(1)，dequeue时间复杂度是O(n)，这个理解，不理解为什么由前面可以推导出testQueue的时间复杂度是O(n^2)。

我理解当N无穷大时，enqueue的时间(因为O(1)是个常数)可以忽略，所以testQueue的时间复杂度等于O(n)，麻烦老师看看我理解哪里有问题，谢谢。

Answer 1

0xbadf00d 2018-04-22 21:58:23

因为每一次dequeue时间复杂度是O(n)，而testQueue用for循环dequeue了n次，所以是O(n^2) .

• 提问者 kxning #1

  非常感谢，理解了。

• liuyubobobo #2

  谢谢你的回答：）

• liuyubobobo 回复 提问者 kxning #3

  是的：）我说的O(n^2)，是对于整个testQueue这个方法计算的，而不是我们队列中的一次操作：）

点开查看后面1条评论