AddLast()时间复杂度问题（视频2-9，时间5:04）

来源：2-9 均摊复杂度和防止复杂度的震荡

海中小水滴

2020-05-31

平均每次AddLast()，进行两次基本操作，那么它的时间复杂度不应该是O(2)么？
为什么您视频中说是O(1)呢？

写回答

1回答

liuyubobobo

2020-06-01

在复杂度分析中，O(1) 表示的是常数个操作。即和数据规模 n 无关。1 次操作，10 次操作，100 次操作，只要这个数字不随着规模变化，就叫 O(1)。

在我们的李自力，不管动态数组中有多少个元素，AddLast 都是只有两次操作。这就叫常数级操作，被称为是 O(1)。

继续加油！：）

海中小水滴

明白了。谢谢波波老师！

2020-06-01

共1条回复

玩转数据结构

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

6221 学习 · 1704 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1