TreeMap<> 操作的时间复杂度：get() 和 subMap()

基于这篇文章，TreeMap 操作的时间复杂度 - subMap、headMap、tailMap https://stackoverflow.com/questions/14290751/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))。这里出了点问题...

我们可以使用 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，因为在此过程中创建并丢弃了一个中间对象。