用Java获取headSet的时间复杂度是多少？另外，如果我调用headSet方法的次数是多少次呢？

Question

我在做一个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;
}

Answer 1

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

为什么？

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

因此，N times就是O(N)。

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

  set.headSet(someElement).size();

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

(AFAIK，这在javadocs中没有说明，但是您可以通过查看TreeSet和TreeMap的源代码来推断它。)

Answer 2

斯蒂芬C甚至没有接近，我不知道它如何有积极的上升，或是公认的答案。显然，树集访问是O(log(n))，而不是O(1)。所以首先，这不可能是O(n)，它充其量是O(n*log(n))。

但这是吗？不是的。更糟的是。耳机并不是像Stephen说的那样是现有设备的一个视图，而是一个新的集合。显然是这样的，因为您可以通过向耳机添加一个元素来修改它。你不能修改一个视图，如果这是指原始的集合，那将是一个巨大的痛苦。

您可以使用以下代码对其进行测试：

        TreeSet<Integer> test=new TreeSet<>();
        long time=System.currentTimeMillis();
        Random r=new Random(5);
        for (int i=0; i<1e6; i++)
            test.add(i);
        long ans=0;
        for (int i=0; i<1e6; i++) {
            int l=r.nextInt((int)1e6);
            ans+=test.headSet(l).size();
        }
        System.out.println(ans+" "+(System.currentTimeMillis()-time));

如果它是O(n)，它将在1/100秒内运行。如果是O(log(n))，它将在大约2秒内运行。你可以看到这大约需要10^4秒。您的代码是O(n^2)。