根据 Big-O 符号对不同数据结构进行不同操作的复杂性

Question

我正在阅读 java 编程中的大 O 表示法。我发现以下 table 它显示了不同数据结构的不同大 O。

http://bigocheatsheet.com/

我的问题是：

1. 如果我要删除数组中的某一项，是O(n^2)吗？ （搜索并删除）
2. 如果我想删除一个堆栈中的项目，是O(n)吗？
3. 哪个更有效，是单链表还是双单链表？
4. 在什么情况下插入操作是O(1)或O(n)在哈希table中？
5. 如果我想在二叉搜索树中删除一个项目，是O(log(n)*log(n))而插入只是O(log(n))吗？

谢谢。

Answer 1

1. 当您执行一个操作然后执行另一个操作时，您不会增加它们的复杂性 - 最大的一个获胜。在这种情况下 O(n) + O(n) = O(n)
2. 堆栈是否有 'delete arbitrary item' API？如果您公开底层数据结构，那是另一回事，但堆栈通常只有一种方法可以 "pop" 元素
3. 用例是什么？
4. 查看hash collisions期间发生的事情。

Answer 2

让我来回答你的问题：

1. 没有。这是 O(n) + O(n) = O(n).
2. 不，它是 O(1)，但您只能访问一个非常重要的元素。对于其他元素，它是 O(n)。
3. 双单列表不会更差，有时可能会更快，但需要更多内存来进行额外的引用。
4. 最佳时间 - 当还没有元素具有该哈希值时，最差时所有插入的元素根据某个模数具有相同的哈希值。例如，如果您比较哈希的模 3 和您的哈希函数总是 returns 一个数字，对于某些 k 是 3k，您将得到 O(n).
5. 不，根据您的 table，这是最坏的情况 O(n)。

稍后我会详细解释。

Answer 3

1. 如果你想从数组中删除一个项目，首先你必须搜索它（需要 O(n)）然后你必须移动项目来填补空白（需要 O(n)） .所以，有效时间复杂度是O(n).
2. 如果要从栈中删除一个项目，只能删除最顶层的元素（栈数据结构的属性）。因此，可以在 O(1).
中完成
3. 哪种类型的链表更有效取决于您的要求。例如，如果你想节省内存，那么由于维护额外指针引用的开销，你可能不会使用双向链表。但是，如果您希望能够双向遍历您的列表，则必须使用双向链表。双向链表的实现有点冗长，因为你必须执行更多的指针操作，但是，许多操作（如删除最后一个元素）可以轻松执行。
4. 我们更喜欢使用Hash tables，因为我们可以实现O(1)的插入和查找时间。 O(n) 几乎所有其他数据结构都占用了插入时间。 （O(n) class 包括 O(log n)、O(1) 等）。假设我们在散列 table 中使用 separate chaining ，其中每条链都是一个排序的链表。然后，对于每次插入，我们需要搜索链表以找到插入的正确位置（就像插入排序一样），这将花费 O(n) 最坏情况时间。
5. 如果你必须从 BST 中删除一个元素，首先你必须搜索它（在平均情况下需要 O(log n)）然后你必须用它的顺序后继或前导替换删除的节点（需要O(log n))。因此，有效平均案例删除时间为 O(log n).