Вывод Big-O для реализации Java Collections Framework?

Возможно, я скоро научусь "Крушению по Java". Хотя, вероятно, можно с уверенностью предположить, что члены аудитории будут знать нотацию Big-O, вероятно, небезопасно предположить, что они будут знать, что такое порядок различных операций над различными реализациями коллекции.

Я мог бы потратить время на создание сводной матрицы сам, но если он уже там где-то в общественном достоянии, я бы хотел снова его использовать (с надлежащим кредитом, конечно.)

У кого-нибудь есть указатели?

Ответы

Ответ 1

Этот сайт довольно хорош, но не специфичен для Java: http://bigocheatsheet.com/

Ответ 2

В книге Java Generics and Collections содержится эта информация (страницы: 188, 211, 222, 240).

Реализации списков:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

Установить реализации:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Реализации карт:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

Реализации очереди:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

В нижней части javadoc для пакета java.util содержатся хорошие ссылки:

Обзор коллекций содержит хорошую сводную таблицу.
Аннотированная схема перечисляет все реализации на одной странице.

Ответ 3

Javadocs от Sun для каждого класса коллекции обычно скажет вам, что именно вы хотите. HashMap, например:

Эта реализация обеспечивает постоянную производительность для основных операций (get and put), предполагая, что хеш-функция правильно распределяет элементы среди ковшей. Для итераций по представлениям коллекции требуется время, пропорциональное "емкости" экземпляра HashMap (количество ковшей) плюс его размер (количество отображений значений ключа).

TreeMap:

Эта реализация обеспечивает гарантированную log (n) временную стоимость для операций containsKey, get, put и remove.

TreeSet:

Эта реализация обеспечивает гарантированную log (n) временную стоимость для основных операций (добавление, удаление и содержит).

(акцент мой)

Ответ 4

Парень выше дал сравнение для HashMap/HashSet против TreeMap/TreeSet.

Я расскажу о ArrayList и LinkedList:

ArrayList:

O (1) get()
амортизируется O (1) add()
если вы вставляете или удаляете элемент в середине с помощью ListIterator.add() или Iterator.remove(), то O (n) будет перемещать все следующие элементы.

LinkedList

O (n) get()
O (1) add()
если вы вставляете или удаляете элемент в середине с помощью ListIterator.add() или Iterator.remove(), это будет O (1)