根据 Big-O 表示法对不同数据结构进行不同操作的复杂性

Question

我正在阅读有关 java 编程中的大 O 表示法的内容。我发现下表显示了不同数据结构的不同大O。

http://bigocheatsheet.com/

我的问题是：

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

谢谢。

Answer 1

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

Answer 2

让我回答你的问题：

1. 没有。它是O(n) + O(n) = O(n)。
2. 不，它O(1)只是你只能访问一个非常顶层的元素。对于其他元素，它是 O(n)。
3. 双单列表不会更糟，有时可能会更快，但需要更多内存用于附加引用。
4. 最好的时间 - 当还没有具有该哈希的元素时，最差的时间是所有插入的元素根据某个模数具有相同的哈希。例如，如果您比较哈希值的模 3，并且您的哈希函数始终返回一个数字，对于某些 k，该数字为 3k，则您将得到O(n)。
5. 不，根据你的表，最坏的情况是 O(n)。

我稍后会解释更多。