Treemap插入与HashMap插入的复杂性 [英] Complexity of Treemap insertion vs HashMap insertion

问题描述

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

I am confused with the time complexity of these two algorithms.

//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).

Is the time complexity to the usingTreeMap algorithm correct.I do know in treemap the insertion time is log(n) but if we iterate over an array of 10 elements does it become nlog(n).

推荐答案

与HashMap的复杂性

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

Complexity with HashMap

In the case of HashMap, the backing store is an array. When you try to insert ten elements, you get the hash, compute the specific array index from that hash, and since it's an array in the back, you inject in O(1).

• 对于第一个元素，插入所需的时间= O(1)
• 对于第二个元素，插入所花费的时间= O(1)
• .
• .
• 对于第n个 元素，插入所花费的时间= O(1)

• For first element, time taken to insert = O(1)
• For second element, time taken to insert = O(1)
• .
• .
• For n^th element, time taken to insert = O(1)

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

So, total time for insertion of n elements in a HashMap = n * O(1) = O(n)

在这种情况下，后备存储是一棵树.对于具有总共 k 个元素的树，平均位置查找时间为O(Log k).

In this case, the backing store is a Tree. For a tree with total k elements, on an average, the time to find the location is O(Log k).

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

• Time to insert first element = O(1)
• Time to insert second element = O(Log 1) = 0 = O(1)
• Time to insert third element = O(Log 2)
• .
• .
• Time to insert n^th element = O(Log (n-1))

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

Total time = Log 1 + Log 2 + Log 3 + ... + Log (n-1)

现在，Log 1< = Log n，Log 2< = Log n ... Log(n-1)< = Log n，使我们得出n-1个值，每个值均小于或等于登录n.

Now, Log 1 <= Log n, Log 2 <= Log n ... Log (n-1) <= Log n, leading us to n-1 values each of which is less than or equal to Log n.

这意味着插入树形图的时间总和为< =(n-1)* Log(n)，从而导致O(n Log(n))的复杂性.

This means that the timing for insertion in a treemap sum to a value <= (n-1) * Log (n), leading to the complexity of 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)).}

_{One of the properties of logs is Log a + Log b = Log (ab). Using that, the insertion time in case of TreeMap sums to a lesser-known running time value of O(Log(n!)). But, since, O(Log(n!)) is bound by O(n Log(n)), the time complexity of insertion of n elements in a TreeMap is loosely written O(n Log(N)).}

这篇关于Treemap插入与HashMap插入的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！