java - TreeMap<>操作的时间复杂度: get() and subMap()

Question

根据这篇文章， Time complexity of TreeMap operations- subMap, headMap, tailMap

subMap() 本身的复杂度是 O(1)，而 O(n) 来自于迭代子映射。

那么，为什么要使用 get(key) 呢？

我们可以使用 subMap(key, true, key, true) 来代替，

这是 O(1) 并且迭代这个子映射也是 O(1)。

比 get(key) 更快，时间复杂度为 O(log(n))。这里出了点问题...

Answer 1

We can use subMap(key, true, key, true) instead, which is O(1)

这是正确的

and iterating this sub map is also O(1).

O(n) 来自问题。答案没有暗示这一点，这很好，因为这不是真的。

迭代子树的时间复杂度为 O(log n + k)，其中 n 是整个映射中的元素数量，k 是子 map 中的元素。换句话说，当你开始迭代时，仍然需要 O(log n) 才能到达第一个位置。查找 getFirstEntry() 实现以了解它是如何完成的。

这使您的方法的整体复杂性达到 O(log n)，但它肯定会比简单的 get 慢，因为在此过程中会创建并丢弃中间对象。