是否有一个全面的Big-O Java数据结构列表？ [英] Is there a comprehensive Big-O listing of Java data structures?

问题描述

问题几乎说明了一切。具体来说，除了通常情况下，我想要一个结构中的所有方法的Big-O。文件对此很少说。

Addennum

对于那些投票关闭，我对基本的add，remove，iterator等不感兴趣
这些来源对于常用的方法很好，但是我对其余的堆栈的算法效率更感兴趣。

例如， TreeMap.keySet（）的效率是多少？

解决方案

Java集合算法效率：

ArrayList

• get，set： O（1）


• 添加，删除： O（n）

< indexOf： O（n）

HashMap

• get，put，remove，containsKey： O（1）

HashSet

• 添加，删除，包含： O（1）

LinkedHashSet

• 添加，删除，包含： O（1）

LinkedList

• 获取，设置，添加，删除（从任一端）： O（1）


• 获取，设置，添加，删除（从索引）： O（n）


• contains，indexOf： O（n）

PriorityQueue

• peek： O（1）


• 添加，删除： O（logn）

TreeMap

• remove，get，put，containsKey： O（logn）

TreeSet

• 添加，删除，包含： O（logn）

Question pretty much says it all. Specifically, I would like the Big-O of all the methods within a structure, aside from the usual. The docs say very little about this.

Addennum

For those who are voting to close, I am not interested in the basic add, remove, iterator, etc Those sources are fine for regularly used methods, but I am more interested in the algorithmic efficiency of the rest of the pile.

For example, what is the efficiency of TreeMap.keySet()?

解决方案

Java Collections Algorithm Efficiencies: Source

ArrayList

• get, set: O(1)
• add, remove: O(n)
• contains, indexOf: O(n)

HashMap

• get, put, remove, containsKey: O(1)

HashSet

• add, remove, contains: O(1)

LinkedHashSet

• add, remove, contains: O(1)

LinkedList

• get, set, add, remove (from either end): O(1)
• get, set, add, remove (from index): O(n)
• contains, indexOf: O(n)

PriorityQueue

• peek: O(1)
• add, remove: O(logn)

TreeMap

• remove, get, put, containsKey: O(logn)

TreeSet

• add, remove, contains: O(logn)

这篇关于是否有一个全面的Big-O Java数据结构列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！