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算法的时间复杂度正确吗？我知道在treemap中插入时间是log(n ),但是如果我们遍历一个包含10个元素的数组，它会变成nlog(n)吗？

Answer 1

使用TreeMap算法的时间复杂度是否正确。

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

我知道在树映射中，插入时间是log（n）

正确。

但是如果我们迭代一个10个元素的数组，它会变成nlog（n）。

如果这意味着插入这 10 个元素，则时间复杂度为 M*log（N），其中 M 是数组的大小，N 是 TreeMap 的大小。如果不是这个意思，问题就不清楚了。

Answer 2

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

平均案例：

• 哈希映射 O（1）
• TreeMap O（logn） -- 因为底层结构是一棵红黑相间的树

最坏的情况：

• 哈希映射 O（n） -- 在哈希冲突的情况下
• 树状图 O（logn）

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

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

Answer 3

在HashMap的情况下，后备存储是一个数组。当你尝试插入十个元素时，你会得到散列，从散列中计算出特定的数组索引，因为它是后面的一个数组，所以你会注入O（1）。

• 对于第一个元素，插入所需的时间=O（1）
• 对于第二个元素，插入所需的时间=O（1）
• 。
• 。
• 对于n^th元素，插入所需的时间=O（1）

因此，在HashMap中插入n个元素的总时间=n*O（1）=O（n）

在本例中，后备存储是树。对于总共有 k 个元素的树，平均而言，查找位置的时间是 O（Log k）。

< li >插入第一个元素的时间= O(1) < li >插入第二个元素的时间= O(Log 1) = 0 = O(1) < li >插入第三个元素的时间= O(Log 2) <李>。 <李>。 < li >插入第n个元素的时间= O(Log (n-1))

总时间 = 日志 1 日志 2 日志 3 ... 日志 （n-1）

现在，日志1

这意味着插入树图的时间总和为一个值

_{日志的属性之一是日志a、日志b=Log（ab）。使用该函数，树映射情况下的插入时间总和为鲜为人知的运行时间值O（Log（n！））。但是，因为，O（Log（n！））在树映射中插入n个元素的时间复杂度松散地写为O（n Log（n））。}