开发者

Is there a comprehensive Big-O listing of Java data structures? [duplicate]

开发者 https://www.devze.com 2023-01-23 08:08 出处:网络
This question already has answers here: Big-O summary for Java Collections Framework implementations? [closed]
This question already has answers here: Big-O summary for Java Collections Framework implementations? [closed] (4 answers) Closed 8 years ago.

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开发者_StackOverflow中文版 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)


I would review the standard Big-O information about algorithms in Introduction_to_Algorithms.


I am not sure is there a spreadsheet or other list, but you can get this information in docs for every structure, for example TreeSet:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).


There really cannot be. Each JVM can have it's own runtime, with its own implementations. A few methods have specified O() characteristics, but the rest are whatever Sun, or Oracle, or IBM, or Apple, or Azul, does.

0

精彩评论

暂无评论...
验证码 换一张
取 消