Big O: стоимость операций с коллекциями

Что оценивает Big O

Big O описывает, как меняется время или дополнительная память алгоритма при росте объёма входных данных n. Это не секундомер и не обещание конкретной скорости: константы, кэш процессора, распределение памяти и качество хешей всё равно влияют на результат.

Для коллекций полезно отдельно оценивать:

доступ к элементу;
поиск по значению или ключу;
вставку и удаление;
полный обход;
сортировку;
дополнительную память.

Важно различать худший, средний и амортизированный случаи. Например, добавление в конец ArrayList иногда требует расширить массив и скопировать все элементы — O(n), но последовательность таких добавлений в среднем даёт амортизированное O(1) на операцию.

Шпаргалка

Структура	Доступ	Поиск	Добавление	Удаление	Что скрыто за оценкой
`ArrayList`	`O(1)` по индексу	`O(n)`	в конец `O(1)` амортизированно, в середину `O(n)`	`O(n)`	сдвиг хвоста массива
`LinkedList`	`O(n)`	`O(n)`	на известном конце `O(1)`	по найденному узлу `O(1)`, поиск узла `O(n)`	переходы по ссылкам и слабая локальность данных
`HashSet`	—	в среднем `O(1)`, худшее зависит от коллизий	в среднем `O(1)`	в среднем `O(1)`	качество `hashCode`, ёмкость и коллизии
`TreeSet`	—	`O(log n)`	`O(log n)`	`O(log n)`	сбалансированное дерево и сравнение элементов
`HashMap`	по ключу в среднем `O(1)`	по значению `O(n)`	в среднем `O(1)`	в среднем `O(1)`	хеширование, коллизии, расширение таблицы
`TreeMap`	по ключу `O(log n)`	по значению `O(n)`	`O(log n)`	`O(log n)`	упорядоченное сбалансированное дерево
`ArrayDeque`	концы `O(1)` амортизированно	`O(n)`	с концов `O(1)` амортизированно	с концов `O(1)`	кольцевой массив
`PriorityQueue`	минимум/максимум на вершине `O(1)`	`O(n)`	`O(log n)`	вершина `O(log n)`	двоичная куча

Для хеш-структур нельзя без оговорок говорить «всегда O(1)». При множестве коллизий корзина перестаёт быть идеальным прямым доступом; в современных реализациях HashMap длинная корзина при выполнении условий может стать деревом, но это не отменяет зависимости от корректных equals и hashCode.

Как рассуждать по коду

boolean containsDuplicate(List<String> values) {
    Set<String> seen = new HashSet<>();
    for (String value : values) {       // n итераций
        if (!seen.add(value)) {         // в среднем O(1)
            return true;
        }
    }
    return false;
}

Среднее время — O(n), дополнительная память — O(n). Если вместо HashSet для каждого элемента вызывать values.indexOf(value), появится вложенный линейный поиск и итоговая оценка станет O(n²).

Ловушки

Складывать последовательные участки и перемножать вложенные: два отдельных цикла по n — O(n), два вложенных — O(n²).
Считать LinkedList быстрым для произвольной вставки, забыв цену поиска позиции.
Игнорировать амортизированную стоимость расширения массива или хеш-таблицы.
Оценивать только время и не замечать O(n) временных коллекций.
Делать вывод по типу интерфейса: переменная List не говорит, какая реализация находится внутри.

Вопросы на собеседовании

Почему ArrayList.add в конец считают O(1), хотя иногда копируется весь массив?
Почему доступ по индексу у LinkedList остаётся O(n)?
От чего зависит сложность операций HashMap?
Когда TreeMap предпочтительнее HashMap, несмотря на O(log n)?
Как определить временную и пространственную сложность фрагмента с двумя циклами?

Связанные заметки

Иерархия коллекций · List · Set · Map · Queue and Deque · HashMap · Equals и hashCode

JavaNotes

Explorer

Big O оценка сложности операций с коллекциями