Java TreeMap 时间复杂度 - lowerKey

Question

lowerKey()Java 实现中操作的时间复杂度是TreeMap多少？

我认为它是 log(n) 但我在文档中的任何地方都找不到它。

更基本操作的复杂性有据可查：

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。

顺便说一句：我也对subMap(). 我猜 log(n) 复杂度lowerKey()将允许 log(n) 时间为常数 size subMap()。

Answer 1

lowerKey()是平衡二叉搜索树中的搜索，所以很明显O(log n)。您可能想要阅读源代码，例如从这里，以查看树是如何遍历的。

同样，每个NavigableMap返回 from 的操作subMap()也需要，O(log n)因为您将需要遍历树来查找您想要的元素。