什么是最常见的数据结构及其操作的时间复杂度？

Question

我正在努力理解大O表示法。它似乎很抽象。我选择了最常见的数据结构 - 数组、哈希表、链式列表（单向和双向）和二叉搜索树，并对最常见的操作 - 插入和搜索 - 猜测了一下它们的大O表示法。这是为面试做准备。我只需要学习基础知识，而不是读整本算法书，虽然这样做是理想的。下面的表格有效吗？

Data Structure       Big O Search   Big O Insert
Array                    O(1)          O(n)
Hash                     O(1)          O(1)
Single Linked List       O(n)          O(1)
Double Linked List       O(n)          O(1)
Tree                   O(log n)      O(log n)

- user656925

Answer 1

对于数组，获取/返回一个元素的时间复杂度为O(1)，但查找一个元素的时间复杂度应该是O(n)。 对于树，我假设你指的是平衡的二叉搜索树。

- Terry Li

---

@ChrisAaker 不，我只是按照传统意义上的数组来处理。你提到的听起来像是结合了其他技术的增强型数组。与面试官分享额外的知识会很好。祝好运！ - Terry Li

@Terry，ChrisAaker所指的是查找给定索引值的地址成本。数组本身最终是一个指针，因此查找任何元素都需要进行乘法和加法运算（将索引乘以元素大小并加上数组地址）。然而，这并不是通常意义上的“搜索”。对于这种情况（在不知道索引的情况下查找值），O(n)是适当的成本，除非数组已排序，在这种情况下可以通过二分查找实现O(lgn)的成本。 - ejspencer

Answer 2

对于哈希插入，要记住O(1)是最优的。如果您的哈希表接近满，效率将接近O(n)。

此外，对于排序数组，搜索是O(log n)。

- Christian Mann

---

如果负载保持在70%以下，O(1)的平均值是可以实现的。 - user656925