关于testQueue时间复杂度

来源：3-8 数组队列和循环队列的比较

kxning

2018-04-22

【问题】

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

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

写回答

1回答

0xbadf00d

2018-04-22

已采纳

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

kxning

liuyubobobo

谢谢老师，懂了:)

2018-04-23

共4条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1