Java TreeMap 时间复杂度 - lowerKey

Question

Java 实现

lowerKey()

中

TreeMap

操作的时间复杂度是多少？

我认为它是 log(n) 但我在文档中找不到它。

更基本操作的复杂性已有详细记录：

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

顺便说一句：我也对

subMap()

的复杂性感兴趣。我猜

lowerKey()

的 log(n) 复杂度将允许 log(n) 时间用于恒定大小

subMap()

。

Answer 1

lowerKey()

是平衡二叉搜索树中的搜索，所以显然是

O(log n)

。您可能想阅读源代码，例如从这里，看看树是如何遍历的。

类似地，从

NavigableMap

返回

subMap()

的每个操作也需要

O(log n)

，因为您需要遍历树来查找所需的元素。

Answer 2

对于

subMap()

，时间复杂度为 O(log n + m)，其中 m 是子图返回所需的条目数。

参见 https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/RedBlackBST.html#size(Key,Key)

keys 方法需要 O(log n + m) 时间，其中 m 是迭代器返回的键数。