Java 设置时间和速度复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6634816/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Set time and speed complexity
提问by Anton K.
I am brushing up algorithms and data structures and have a few questions as well as statements I would like you to check.
我正在复习算法和数据结构，并有一些问题和陈述，我希望您检查一下。
ArrayList- O(1) (size, get, set, ...), O(n) - add operation.
LinkedList- all operation O(1) (including add() ), except for retrieving n-th element which is O(n). I assume size() operation runs in O(1) as well, right?
ArrayList- O(1) (size, get, set, ...), O(n) - 添加操作。
LinkedList- 所有操作 O(1)（包括 add() ），除了检索 O(n) 的第 n 个元素。我假设 size() 操作也在 O(1) 中运行，对吗？
TreeSet- all operations O(lg(N)). size() operation takes O(lg(n)), right?
TreeSet- 所有操作 O(lg(N))。size() 操作需要 O(lg(n))，对吗？
HashSet- all operations O(1) if proper hash function is applied.
HashMap- all operations O(1), anologous to HashSet.
HashSet- 如果应用了适当的散列函数，则所有操作 O(1)。
HashMap- 所有操作 O(1)，类似于 HashSet。
Any further explanations are highly welcome. Thank you in advance.
任何进一步的解释都非常受欢迎。先感谢您。
采纳答案by Jon Skeet
ArrayList.add()is amortizedO(1). If the operation doesn't require a resize, it's O(1). If it doesrequire a resize, it's O(n), but the size is then increased such that the next resize won't occur for a while.
ArrayList.add()是摊销O（1）。如果操作不需要调整大小，则为 O(1)。如果确实需要调整大小，则为 O(n)，但随后会增加大小，以便在一段时间内不会发生下一次调整大小。
From the Javadoc:
从Javadoc：
The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
add 操作在分摊常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。与 LinkedList 实现相比，常量因子较低。
The documentation is generally pretty good for Java collections, in terms of performance analysis.
在性能分析方面，该文档通常非常适合 Java 集合。
The O(1) for hash algorithms isn't a matter of just applying a "proper" hash function - even with a very good hash function, you could still happen to get hash collisions. The usualcomplexity is O(1), but of course it can be O(n) if allthe hashes happen to collide.
散列算法的 O(1) 不仅仅是应用“适当”散列函数的问题——即使使用非常好的散列函数，您仍然可能碰巧遇到散列冲突。在通常的复杂度为O（1），但当然也可以是O（N），如果所有的散列发生碰撞。
(Additionally, that's counting the cost of hashing as O(1) - in reality, if you're hashing strings for example, each call to hashCodemay be O(k) in the length of the string.)
（此外，这将散列的成本计算为 O(1) - 实际上，例如，如果您正在散列字符串，则每次调用hashCode的字符串长度可能是 O(k)。）
回答by sgokhales
Visit the following links. It will help you getting your doubts cleared.
访问以下链接。它将帮助您消除疑虑。
