Java TreeMap 时间复杂度 - lowerKey
Java TreeMap time complexity - lowerKey
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) 复杂度将允许 恒定大小 subMap().
的 log(n) 时间
lowerKey() is a search in a balanced binary search tree, so it's obviously O(log n). You might want to read the source code, e.g. from here，看看树是怎么遍历的
类似地，每个从 subMap() 返回 NavigableMap 的操作也需要 O(log n)，因为您需要遍历树以找到您想要的元素。
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) 复杂度将允许 恒定大小 subMap().
lowerKey() is a search in a balanced binary search tree, so it's obviously O(log n). You might want to read the source code, e.g. from here，看看树是怎么遍历的
类似地，每个从 subMap() 返回 NavigableMap 的操作也需要 O(log n)，因为您需要遍历树以找到您想要的元素。