相关疑难解决方法(0)

有人可以帮助解释如何构建堆是O(n)复杂性？

将项插入堆中O(log n),并且插入重复n/2次(其余为叶,并且不能违反堆属性).所以,这意味着复杂性应该是O(n log n),我想.

换句话说,对于我们"堆积"的每个项目,它有可能必须针对堆的每个级别过滤一次(这是log n级别).

我错过了什么？

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

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