Временная сложность Java TreeMap - lowerKey

Question

Какова временная сложность операции lowerKey() в Java-реализации TreeMap?

Я думаю, что это журнал (n), но я не могу найти его нигде в документации.

Сложность более основных операций хорошо документирована:

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

BTW: Меня также интересует сложность subMap(). Я предполагаю, что сложность log (n) lowerKey() позволит log (n) время для постоянного размераsubMap().

Answer 1

lowerKey() - это поиск в сбалансированном двоичном дереве поиска, поэтому это, очевидно, O(log n). Возможно, вам захочется прочитать исходный код, например. от here, чтобы увидеть, как проходит дерево.

Аналогично, для каждой операции с NavigableMap, возвращенной с subMap(), также требуется O(log n), потому что вам нужно будет пересечь дерево, чтобы найти нужные элементы.