java - 数组/堆栈/队列的大 O 表示法

Question

我想知道，为什么 avg 中的 Array/Stack/Queue 的 Big O 表示法是 O(1)。当我们插入和删除元素时的情况？

根据我的理解，它是 O(1)，因为无论集合中的数据量有多少，插入和删除元素都需要恒定的时间，但我仍然有点困惑。任何帮助消除我的困惑的帮助将不胜感激。

Answer 1

O(1) - 表示法表示该操作在恒定时间内执行。

O(n) - 表示法表示操作在线性时间内执行，例如遍历列表。

数组

我们从最明显的一个开始。数组A具有固定长度n，并且可以通过寻址内存中的适当位置来在恒定时间内访问其元素，即

A[i]=10;

堆栈

栈是一种后进先出的数据结构。我们总是有一个指向顶部元素的指针/引用。因此，即使堆栈被实现为列表，我们也无法在恒定时间内寻址其中的特定元素(我们必须在O(n)中遍历列表)，我们正在访问最顶层具有 pop/peak 的元素，我们有一个指针/引用，因此可以在常数时间内访问 O(1)。

Stack.pop(); //or peak() perhaps

队列

队列是先进先出的数据结构。与堆栈一样，访问队列的特定元素可以在线性时间 O(n) 内完成，因为我们需要遍历它。但我们通常有一个指向队列的第一个和最后一个元素的指针/引用。因此入队和出队都可以在常数时间内执行O(1)。