关于testQueue时间复杂度测试的问题

Question

bobo老师，我的ArrayQueue测出来44.4s，LoopQueue测出来0.047s，并且多次测下来都是差将近1000倍。原本以为是代码的原因，特地把您的代码拓下来试了一下，还是一样的，这是出了什么问题啊？

Answer 1

liuyubobobo 2018-08-28 08:22:55

是正常的啊。就是因为ArrayQueue的remove操作时间复杂度为O(n)，而LoopQueue的所有操作，时间复杂度为O(1)啊！这也是为什么，我们要特意讲LoopQueue这种实现方式的原因：）

加油！

• 提问者 nifo #1

  嗯，但就是因为这样，所以ArrayQueue实现testQueue的复杂度才是O(n^2)，而LoopQueue实现testQueue的复杂度才是O(1)。这样的话也应该是相差100倍左右啊！

• liuyubobobo 回复 提问者 nifo #2

  大O符号描述的不是精确的时间，而是渐进时间复杂度。可以参考这里：https://coding.imooc.com/learn/questiondetail/76289.html ：）

• 提问者 nifo 回复 liuyubobobo #3

  感谢bobo老师，上大学总是误以为，大O复杂度代表精确的时间差。现在理解了，它是随着数据量的变化而变化的！

点开查看后面1条评论