Treemap插入与HashMap插入的复杂性

Question

我对这两种算法的时间复杂性感到困惑.

//time complexity O(nlog(n))
public void usingTreeMap(){
    Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
    for (int i = 0; i < 10; i++) {
        map.put(i, i);
    }
}
//time complexity O(n)
public void usingHashMap(){
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < 10; i++) {
        map.put(i, i);
    }
}

usingTreeMap算法的时间复杂度是否正确.我确实在树形图中知道插入时间是log(n)但是如果我们迭代10个元素的数组,它就变成了nlog(n).

Answer 1

与HashMap的复杂性

对于HashMap,后备存储是一个数组.当您尝试插入十个元素时,您将获得哈希值,从该哈希值计算特定的数组索引,并且由于它是后面的数组,因此您将注入O(1).

• 对于第一个元素,插入时间= O(1)
• 对于第二个元素,插入时间= O(1)
• .
• .
• 对于^第 n ^个元素,插入时间= O(1)

因此,在HashMap中插入n个元素的总时间= n*O(1)= O(n)

TreeMap的复杂性

在这种情况下,后备存储是一个树.对于具有总k个元素的树,平均而言,找到该位置的时间是O(Log k).

• 插入第一个元素的时间= O(1)
• 插入第二个元素的时间= O(Log 1)= 0 = O(1)
• 插入第三个元素的时间= O(Log 2)
• .
• .
• 插入^第 n ^个元素的时间= O(Log(n-1))

总时间= Log 1 + Log 2 + Log 3 + ... + Log(n-1)

由于Log a + Log b = Log(ab),因此TreeMap的插入时间总和为较不为人知的运行时间值O(Log(n!)).

此外,O(Log(n!))由O(n Log(n))约束.[ 提示: Log 1,Log 2,... Log(n-1)是总(n-1)个值,并且所有值都小于Log(n).因此,它们的总和是n*Log(n)]的上限.

因此,在TreeMap中插入n个元素的时间复杂度松散地写为O(n Log(N)).

Answer 2

插入时间复杂度通常是根据每个实例定义的。

平均情况：

• HashMap O（1）
• TreeMap O（log n）-由于基础结构是一棵红黑树

最坏的情况：

• Hashmap O（n）-在哈希冲突的情况下
• TreeMap O（log n）

在上面的代码中，由于您要插入多个项目，因此我们需要区分地图中有多少个元素（n）和要添加到地图中的有多少个元素（m）。如果映射最初是空的，则上面的运行时是正确的。如果它们已经有一些元素，那么运行时将是：

                                Avg      Worst
Insert m elements into HashMap: O(m)     O(mn)
Inset m elements into TreeMap:  O(mlogn) O(mlogn)

Answer 3

usingTreeMap算法的时间复杂度是否正确.

TreeMap在Javadoc中正确指定了基本操作的时间复杂性.

我知道在树形图中插入时间是log(n)

正确.

但如果我们迭代10个元素的数组,它会变成nlog(n).

如果这意味着插入那些10种元素的时间复杂度是M*log(N)其中M是阵列的尺寸和N是的大小TreeMap.,如果它并不意味着,问题是不清楚.

Answer 4

可能不是。（即，当 10 个元素中有 4 个具有相同的键时，则 N 将是 7），所以我相信重复的键越多，插入的时间就越长。