TreeMapvalues()方法和keySet()方法时间复杂度

Question

我试图找出在 TreeMap 数据结构中实现的 value() 和 keySet() 方法的时间复杂度。

谁能告诉我这些方法的时间复杂度是多少？

非常感谢。

汤姆

    public class SuperStruct<K,V> 
{
    private Map<K,V> mInternalKeyToValueMap;//all the keys and their values 
    public SuperStruct(){
            mInternalKeyToValueMap = new TreeMap<K,V>();
    }

    public Collection<V> values() {     
            return mInternalKeyToValueMap.values();
        }
    public Collection<K> keySet() {

            return mInternalKeyToValueMap.keySet();
        }
    }

Answer 1

keySet几乎肯定会使用Collections.newSetFromMap(this)因为这是一个非常有效的方法 - 所以O(1)那么。

Collection<V>通过简单的适配器从地图创建 应该非常简单entrySet，因此我建议它的复杂性与可能是entrySet或O(1)但O(n)最有可能的相同O(1)。一些浏览GrepCode源代码的人建议O(1)- 它只是创建一个新对象（如果需要），而不是增长一个结构。