根据Big-O表示法对不同数据结构执行不同操作的复杂性 [英] Complexity of different operations on different data structures according to the Big-O notation
本文介绍了根据Big-O表示法对不同数据结构执行不同操作的复杂性的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在阅读有关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.
我的问题是:
- 如果要删除数组中的项目,它是
O(n ^ 2)
吗?(搜索和删除) - 如果我要删除堆栈中的项目,是
O(n)
吗? - 哪个更有效,它是单链表还是双链表?
- 在哪种情况下,插入操作是哈希表中的
O(1)
或O(n)
? - 如果要删除二进制搜索树中的项目,是
O(log(n)* log(n))
,而insert只是O(log(n))
?
- If I want to delete an item in an array, is it
O(n^2)
? (search and delete) - If I want to delete an item in a stack, is it
O(n)
? - Which one is more effective, is it a single linked list or double single list?
- In what case is that the insert operation is
O(1)
orO(n)
in a hash table? - If I want to delete an item in a binary search tree, is it
O(log(n)*log(n))
while insert is justO(log(n))
?
谢谢.
推荐答案
让我回答您的问题:
- 不.
O(n)+ O(n)= O(n)
. - 不是,它是
O(1)
,但是您只能访问一个,位于最上面的元素.其他元素为O(n). - 单重列表不会更糟,有时可能会更快,但需要更多的内存用于其他引用.
- 最佳时间-当尚无带有该哈希的元素时,最糟糕的情况是,根据某种模,所有插入的元素都具有相同的哈希.例如,如果您比较哈希的模数3,并且您的哈希函数始终返回一个3k对应一个k的数字,则您将具有
O(n)
. - 不,根据您的表格,这是最糟糕的情况O(n).
- Nope. It's
O(n) + O(n) = O(n)
. - Nope, it's
O(1)
but you only have access to one, very on top element. For other elements it's O(n). - Double single list will be not worse, might be faster sometimes, but needs more memory for additional references.
- 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)
. - Nope, according to your table, it's worst case O(n).
我会在稍后解释.
这篇关于根据Big-O表示法对不同数据结构执行不同操作的复杂性的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文