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

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)

为什么？

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

因此，执行 N 次是 O(N)。

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

  set.headSet(someElement).size();

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

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

Answer 2

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

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

What is the time complexity of getting the headSet of a TreeSet in Java? Also, what if I call the headSet method 'n' times?

java

algorithm

time-complexity

treeset