Ant*_* K. 14 java algorithm collections
我正在刷新算法和数据结构,并有一些问题以及我希望你检查的语句.
ArrayList - O(1)(size,get,set,...),O(n) - 添加操作.
LinkedList - 除了检索第n个元素O(n)之外的所有操作O(1)(包括add()).我假设size()操作也在O(1)中运行,对吧？
TreeSet - 所有操作O(lg(N)).size()操作需要O(lg(n)),对吧？
HashSet - 如果应用了适当的哈希函数,则所有操作O(1).
HashMap - 所有操作O(1),与HashSet无关.
任何进一步的解释都非常受欢迎.先感谢您.
Jon*_*eet 18
ArrayList.add()被摊销 O(1).如果操作不需要调整大小,则为O(1).如果它确实需要调整大小,则为O(n),但随后增加大小,以便下一次调整大小不会发生一段时间.
来自Javadoc:
添加操作以分摊的常量时间运行,即添加n个元素需要O(n)时间.所有其他操作都以线性时间运行(粗略地说).与LinkedList实现相比,常数因子较低.
在性能分析方面,文档通常非常适合Java集合.
散列算法的O(1)不仅仅是应用"正确的"散列函数 - 即使使用非常好的散列函数,您仍然可能发生哈希冲突.在通常的复杂度为O(1),但当然也可以是O(N),如果所有的散列发生碰撞.
(此外,这将散列的成本计算为O(1) - 实际上,如果您正在散列字符串,例如,每个调用hashCode可能是字符串长度中的O(k).)