Какова временная сложность получения headSet TreeSet в Java?Кроме того, что если я вызову метод headSet n раз?

Question

Я задавал хакерский вопрос, который требует, чтобы я выяснил, сколько сдвигов должно произойти, чтобы отсортировать массив с помощью сортировки вставкой без фактической сортировки массива с сортировкой вставкой, потому что в противном случае это было бы за 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 раз это O(N).

Однако причина, по которой ваш код не O(N), заключается в том, что

  set.headSet(someElement).size();

НЕ O(1). Причина в том, что метод size() в представлении подмножества TreeSet вычисляется путем подсчета элементов в представлении.

(AFAIK, это не указано в javadocs, но вы можете сделать вывод, посмотрев на исходный код TreeSet и TreeMap.)