树状图插入的复杂性与哈希图插入

algorithm time-complexity java

2022-09-01 18:08:33

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

//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);
    }
}

使用TreeMap算法的时间复杂度是否正确。我知道在树状图中，插入时间是log（n），但是如果我们迭代一个包含10个元素的数组，它会变成nlog（n）。

答案 1

哈希映射的复杂性

对于 HashMap，后备存储是一个数组。当你尝试插入十个元素时，你会得到哈希，从该哈希计算特定的数组索引，并且由于它是后面的数组，所以你注入O（1）。

对于第一个元素，插入所花费的时间 = O（1）
对于第二个元素，插入所花费的时间 = O（1）
.
.
对于^{第 n 个}元素，插入所花费的时间 = O（1）

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

树状图的复杂性

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

插入第一个元素的时间 = O（1）
插入第二个元素的时间 = O（Log 1） = 0 = O（1）
插入第三个元素的时间 = O（Log 2）
.
.
插入^{第 n 个}元素的时间 = O（Log （n-1））

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

现在，日志 1 <= 日志 n，日志 2 < = 日志 n ...Log （n-1） <= Log n，导致我们得到 n-1 个值，每个值都小于或等于 Log n。

这意味着在树状图中插入的时间总和为值<= （n-1） * Log （n），从而导致 O（n Log （n））的复杂性。

_{日志的属性之一是 Log a + Log b = Log （ab）。。使用此功能，TreeMap情况下的插入时间总和为人所知的运行时间值O（Log（n！））。但是，由于 O（Log（n！））受 O（n Log（n））的约束，因此在 TreeMap 中插入 n 个元素的时间复杂度大致写为 O（n Log（N））。}

答案 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)