根据Big-O表示法对不同数据结构执行不同操作的复杂性 [英] Complexity of different operations on different data structures according to the Big-O notation

问题描述

我正在阅读有关Java编程中的大O表示法的信息.我发现下表显示了针对不同数据结构的不同大O.

I was reading about big O notation in java programming. I found the following table it shows different big O for different data structures.

http://bigocheatsheet.com/

我的问题是:

1. 如果要删除数组中的项目，它是 O(n ^ 2)吗?(搜索和删除)
2. 如果我要删除堆栈中的项目，是 O(n)吗?
3. 哪个更有效，它是单链表还是双链表?
4. 在哪种情况下，插入操作是哈希表中的 O(1)或 O(n)?
5. 如果要删除二进制搜索树中的项目，是 O(log(n)* log(n))，而insert只是 O(log(n))?

1. If I want to delete an item in an array, is it O(n^2)? (search and delete)
2. If I want to delete an item in a stack, is it O(n)?
3. Which one is more effective, is it a single linked list or double single list?
4. In what case is that the insert operation is O(1) or O(n) in a hash table?
5. If I want to delete an item in a binary search tree, is it O(log(n)*log(n)) while insert is just O(log(n))?

谢谢.

推荐答案

让我回答您的问题:

1. 不. O(n)+ O(n)= O(n).
2. 不是，它是 O(1)，但是您只能访问一个，位于最上面的元素.其他元素为O(n).
3. 单重列表不会更糟，有时可能会更快，但需要更多的内存用于其他引用.
4. 最佳时间-当尚无带有该哈希的元素时，最糟糕的情况是，根据某种模，所有插入的元素都具有相同的哈希.例如，如果您比较哈希的模数3，并且您的哈希函数始终返回一个3k对应一个k的数字，则您将具有 O(n).
5. 不，根据您的表格，这是最糟糕的情况O(n).

1. Nope. It's O(n) + O(n) = O(n).
2. Nope, it's O(1) but you only have access to one, very on top element. For other elements it's O(n).
3. Double single list will be not worse, might be faster sometimes, but needs more memory for additional references.
4. Best time - when there is no element with that hash yet, Worst when all inserted elements have the same hash according to some modulo. For example, if you compare modulo 3 of hashes and your hashing function always returns a number which is 3k for some k, you'll have O(n).
5. Nope, according to your table, it's worst case O(n).

我会在稍后解释.

这篇关于根据Big-O表示法对不同数据结构执行不同操作的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！