时间戳

首页 > 解决方案 > 在 Java 中获取 TreeSet 的 headSet 的时间复杂度是多少？另外，如果我调用 headSet 方法'n'次怎么办？

java - 在 Java 中获取 TreeSet 的 headSet 的时间复杂度是多少？另外，如果我调用 headSet 方法'n'次怎么办？

问题描述

我正在做一个hackerrank问题，要求我找出使用插入排序对数组进行排序所需发生的移位次数，而无需实际使用插入排序对数组进行排序，否则将是O（n ^ 2）时间复杂度！这是我的超时代码。据我所知，调用 headSet 方法 n 次应该在 O(n logn) 左右。

static class MyComp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 <= o2 ? -1: 1;
    }
}



// Complete the insertionSort function below.
static int insertionSort(int[] arr) {

    SortedSet<Integer> set = new TreeSet<>(new MyComp());
    int count=0;
    for(int i=arr.length-1; i>=0;i--){
        set.add(arr[i]);
        int pos = set.headSet(arr[i]).size();
       // System.out.println(pos);
        if(pos>0){
            count=count+pos;
        }

    }

    return count;
}

标签： javaalgorithmtime-complexitytreeset

解决方案

创建耳机的复杂性是O(1)

为什么？

因为耳机不是新套装。它实际上是现有集合的视图。创建一个不涉及复制原始集合，甚至不涉及在集合中找到“绑定”元素。

因此，做它N的时间是O(N)。

但是，您的代码不是的原因O(N)是

  set.headSet(someElement).size();

不是O(1)。原因是size()a 的子视图上的方法TreeSet是通过计算视图中的元素来计算的。

（AFAIK，javadocs 中没有说明这一点，但您可以通过查看TreeSetand的源代码来推断它TreeMap。）

推荐阅读