Возможно, скоро я преподаю «Курс на Java». Хотя, вероятно, можно с уверенностью предположить, что члены аудитории будут знать нотацию Big-O, вероятно, небезопасно предполагать, что они будут знать, каков порядок различных операций в различных реализациях коллекций.
Я мог бы потратить время на создание сводной матрицы самостоятельно, но если она уже где-то есть в свободном доступе, я бы, конечно, хотел бы использовать ее повторно (с должным уважением, конечно)
У кого-нибудь есть указатели?
java
collections
big-o
Джаред
источник
источник
Ответы:
Этот веб-сайт довольно хорош, но не относится к Java: http://bigocheatsheet.com/
источник
Книга Java Generics and Collections содержит эту информацию (страницы: 188, 211, 222, 240).
Список реализаций:
Установите реализации:
Реализация карт:
Реализация очередей:
Нижняя часть javadoc для пакета java.util содержит несколько хороших ссылок:
источник
Javadocs от Sun для каждого класса коллекции, как правило, скажет вам именно то, что вы хотите. HashMap , например:
TreeMap :
TreeSet :
(акцент мой)
источник
Парень выше дал сравнение для HashMap / HashSet против TreeMap / TreeSet.
Я буду говорить о ArrayList против LinkedList:
ArrayList:
get()
add()
ListIterator.add()
илиIterator.remove()
, будет O (n), чтобы сдвинуть все следующие элементыLinkedList:
get()
add()
ListIterator.add()
илиIterator.remove()
, это будет O (1)источник
if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1)
Зачем? Сначала нам нужно найти элемент посередине, так почему же это не O (n)?ListIterator.add()
илиIterator.remove()
" У нас есть итератор.