Коллекция TreeMap рассматривает итераторы сложность времени?

Question

Сложность по времени всех трех итераторов представления коллекции для HashMap (myHashMap.entrySet().iterator().next() и myHashMap.keySet().iterator().next() и myHashMap.values().iterator().next()) хорошо документирована в javadoc, это O (n + c)) для всех этих 3 итераторов (n - количество отображений, c - емкость, которая является физическим количеством сегментов в хеш-таблице).

Но как быть с соответствующими 3 итераторами из 3 соответствующих представлений коллекции TreeMap?Ничего не сказано в официальном Javadoc.Каковы их сложности?Я посмотрел исходный код SE8, но не могу судить оттуда.

Answer 1

Попытайтесь ответить на этот вопрос, основываясь на этих замечательных комментариях:

1. Один вызов next() имеет совершенно другую сложность времени по сравнению со всем итерационным процессом.

2. TreeMap в Java основан на Red-Black Tree, который является сбалансированным бинарным деревом поиска.

См. https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

Итерирование всей TreeMap должно иметь ту же сложность времени, что и обход Red-Balck Tree (для перемещения по предварительному заказу или после заказа).Таким образом, временная сложность должна составлять O(n), где n - это значение ключа (или значения, или сопоставления значения ключа).

Для одного next вызова мы можем выполнитьэто в O(1).Если сложность времени O(n) истинна, это должно быть тривиально.