Резюме Big-O для реализаций Java Collections Framework? [закрыто]

164

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

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

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

Джаред
источник
Вот ссылка, которая показалась мне полезной при обсуждении некоторых очень распространенных объектов Java и стоимости их операций с использованием нотации Big-O. objectissues.blogspot.com/2006/11/…
Ник
Хотя не в общественном достоянии, отличный Java Дженерик и Коллекция по Морис Нафталину и Филипп Wadler списков во время выполнения информационных обзоров в главах о различных классах коллекций.
Фабиан Стиг

Ответы:

149

Этот веб-сайт довольно хорош, но не относится к Java: http://bigocheatsheet.com/ Вот изображение на случай, если эта ссылка не будет работать

Бен Дж
источник
27
И именно поэтому мы не используем URL-адреса в качестве ответов. Этот документ / сервер, насколько я могу судить, больше недоступен!
Джейсон Мок
1
@Ben J Ссылки больше не работают
Vikas V
Ссылки на веб-архивы также не работают.
MikeFHay
Кажется, добавлены новые рабочие URL. Спасибо за усилия, это очень полезно.
Tejas C
1
@AndreaZilio LinkedList.remove (Object) - постоянное время, если вы уже знаете соседа. Если вы не знаете соседа, самое время найти его первым.
Пол Эванс
217

Книга 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
Вы должны указать, для какого варианта сценария эти цифры, например, удаление из Arraylist может занять O (n), если вы удаляете элемент в середине или конце массива.
Попай
@popeye не O обычно худший случай?
Ясин Хаджадж
Как упомянул @Popeye, должно быть четкое описание того, о каком случае идет ответ. Случай может быть либо средним / наихудшим для сложности времени. Похоже, что ответ относится к «среднему» случаю для всех DS.
Яшвин Мансадвала
12

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

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

TreeMap :

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

TreeSet :

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

(акцент мой)

Мэтт Б
источник
Я не согласен с частью HashMap. Я знаю положение Солнца, но ... например, get должен вызывать obj.equals (key), который может быть линейным по размеру содержащихся объектов. Учтите, что вы обычно должны читать поля для этого сравнения. Исключениями будут целые числа или строки (интернированные) ???
переполнен
Прежде всего, если они ошиблись, вам должно быть не слишком сложно создать контрольный пример, опровергающий производительность в постоянном времени? Во-вторых, если вы посмотрите на исходный код для HashMap, он не вызывает equals () для каждого ключа на карте - только тогда, когда хеш-коды равны.
Мэтт Б
5
Если вы читаете цитату выше, она говорит, что это постоянное время, «предполагая, что хеш-функция правильно распределяет элементы по корзинам». Согласно теории CS, хеш-таблицы имеют операции с постоянным временем, когда хеш-функция «хорошая» (что происходит в среднем), но в худшем случае может потребовать линейного времени.
newacct
4
@Overflown - технически это не имеет значения, сколько времени занимает obj.equals () с точки зрения сложности, так как это всего лишь часть «константы» по отношению к количеству элементов в коллекции.
Микера
6

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

Я буду говорить о ArrayList против LinkedList:

ArrayList:

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

LinkedList:

  • На) get()
  • O (1) add()
  • если вы вставляете или удаляете элемент посередине, используя ListIterator.add()или Iterator.remove(), это будет O (1)
newacct
источник
1
if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1) Зачем? Сначала нам нужно найти элемент посередине, так почему же это не O (n)?
MyTitle
@ MyTitle: прочитайте это снова. "Использование ListIterator.add()или Iterator.remove()" У нас есть итератор.
newacct