TreeMap的时间复杂度；操作:get()和subMap() [英] Time complexity of TreeMap<> operations: get() and subMap()

问题描述

基于此帖子， TreeMap操作的时间复杂度-subMap，headMap，tailMap

subMap()本身是O(1)，而O(n)来自迭代子图.

subMap() itself is O(1), and O(n) comes from iterating the sub map.

那么，为什么还要使用get(key)?

我们可以改用subMap(key，true，key，true)

We can use subMap(key, true, key, true) instead,

是O(1)，并且迭代此子映射也是O(1).

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

比get(key)更快，它是O(log(n)).这里出了点问题...

Faster than get(key), which is O(log(n)). Something wrong here...

推荐答案

我们可以改用subMap(key，true，key，true)，它是O(1)

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

这是正确的

并迭代此子映射也是O(1).

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

O(n)来自这个问题.答案中没有任何内容暗示这一点，这很好，因为它不是真的.

O(n) comes from the question. The answer says nothing to imply this, which is good, because it's not true.

子树的迭代时间复杂度为O(log n + k)，其中n是整个图中的元素数量，而k是子图中的元素数量.换句话说，当您开始迭代时，仍然需要O(log n)才能到达第一个位置.查找getFirstEntry()实现，以了解其实现方式.

Time complexity of iterating a subtree is O(log n + k), where n is the number of elements in the whole map, and k is the number of elements in the sub-map. In other words, it still takes O(log n) to get to the first position when you start iterating. Look up getFirstEntry() implementation to see how it is done.

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

This brings the overall complexity of your approach to O(log n), but it is bound to be slower than a simple get, because an intermediate object is created and discarded in the process.

这篇关于TreeMap的时间复杂度；操作:get()和subMap()的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！