Java TreeMap时间复杂度-lowerKey

Question

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

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

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

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

顺便说一句:我也对 subMap() 的复杂性感兴趣。我猜想 lowerKey() 的 log(n) 复杂度将允许 log(n) 时间用于恒定大小 subMap()。

Answer 1

lowerKey()是平衡二叉搜索树中的搜索，因此显然是O(log n)。您可能想阅读源代码，例如来自here ，看看树是如何遍历的。

类似地，从 subMap() 返回的 NavigableMap 的每个操作也需要 O(log n)，因为您需要遍历树来查找您想要的元素。