Временная сложность k-го наименьшего числа с использованием PriorityQueue в Java - PullRequest
Новая
       51

Временная сложность k-го наименьшего числа с использованием PriorityQueue в Java

0 голосов
/ 15 марта 2019

Я пытаюсь решить вопрос популярного интервью Find the k-th smallest number in an array of distinct integers.Я прочитал некоторые решения и обнаружил, что структура данных кучи очень хорошо подходит для этой проблемы.

Итак, я попытался реализовать решение с использованием класса PriorityQueue платформы Collections, предполагая, что оно функционально идентичнокуча.

Вот код, который я пробовал: 

public static int getKthMinimum(int[] input, int k){
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

    // Total cost of building the heap - O(n) or O(n log n) ?
    for(int num : input){
        heap.add(num);      // Add to heap - O(log n)
    }

    // Total cost of removing k smallest elements - O(k log n) < O(n) ?
    while(k > 0){
        heap.poll();        // Remove min - O(log n)
        k--;
    }
    return heap.peek();     // Fetch root - O(1) 
}

Основываясь на документах , методы poll & add принимают O (log n)Время и просмотр занимает постоянное время.

  1. Какова будет временная сложность цикла while?(Я думаю, что O (k log n)).
  2. Следует ли считать O (k log n) выше, чем O (n) для целей этого вопроса?Есть ли порог, где он переключается?
  3. Какова будет общая сложность времени этого кода?Это будет O (n)?
  4. Если это еще не O (n), есть ли способ решить это в O (n), используя класс PriorityQueue?

1 Ответ

1 голос
/ 15 марта 2019

1. Какова будет временная сложность цикла while? (Я думаю O (k log n)).

O ( k log n ) правильно.

2. Следует ли считать O (k log n) выше, чем O (n) для целей этого вопроса? Есть ли порог, где он переключается?

Вы не можете этого допустить. k может быть в любом месте от 0 до n -1, что означает, что k log n может быть в любом месте от 0 до n log n .

3. Какова будет общая временная сложность этого кода? Это будет O (n)?

O ( n log n ), потому что это стоимость сборки кучи.

Возможно построить кучу за O ( n ) времени, но ваш код этого не делает; если это произойдет, ваша общая сложность будет O ( n + k log n ) или, что эквивалентно, O (МАКС. ( n , k log n )).

4. Если еще не O (n), есть ли способ решить это в O (n), используя класс PriorityQueue?

Нет. Существует алгоритмов выбора в худшем случае O ( n ), но они немного сложны и не используют PriorityQueue.

Для самых быстрых решений на основе PriorityQueue потребуется O (MAX ( n , n log MIN ( k , *) 1088 * n - k ))) время. (Ключ заключается в том, чтобы во время итерации сохранять в куче только самые маленькие элементы k или самые большие элементы n - k и использовать max-heap, если k достаточно большой, чтобы это стоило того.)

...