java - 设置时间和速度复杂度

Question

我正在复习算法和数据结构，有几个问题和陈述希望您检查一下。

ArrayList - O(1)(大小、获取、设置...)，O(n) - 添加操作。
LinkedList - 所有操作 O(1)(包括 add() )，除了检索第 n 个元素是 O(n)。我假设 size() 操作也在 O(1) 中运行，对吗？

TreeSet - 所有操作 O(lg(N))。 size() 操作需要 O(lg(n))，对吧？

HashSet - 如果应用适当的哈希函数，所有操作 O(1)。
HashMap - 所有操作 O(1)，类似于 HashSet。

非常欢迎任何进一步的解释。提前谢谢你。

Answer 1

ArrayList.add() 是 amortized O(1)。如果操作不需要调整大小，则为 O(1)。如果它确实需要调整大小，则为 O(n)，但随后会增加大小，以便暂时不会发生下一次调整大小。

来自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.

就性能分析而言，该文档通常对 Java 集合相当不错。

哈希算法的 O(1) 不仅仅是应用“适当的”哈希函数的问题 - 即使使用非常好的哈希函数，您仍然可能碰巧遇到哈希冲突。 通常 的复杂度是 O(1)，但如果所有哈希碰巧发生冲突，它当然可以是 O(n)。

(另外，这是将散列的成本计算为 O(1) - 实际上，例如，如果您正在对字符串进行散列，则每次调用 hashCode 的长度可能为 O(k)的字符串。)