TreeMap <>操作的时间复杂度：get（）和subMap（）

Question

根据这篇文章， TreeMap操作的时间复杂度-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

我们可以改用subMap（key，true，key，true），它是O（1）

这是对的

并且迭代此子映射也是O（1）。

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

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

这给O（log n）带来了方法的整体复杂性，但是它肯定比简单方法要慢get，因为在此过程中会创建并丢弃中间对象。