使用Java中的PriorityQueue的第k个最小数的时间复杂度

问题描述 投票:0回答:1

我正在努力解决流行的采访问题Find the k-th smallest number in an array of distinct integers。我读了一些解决方案,发现堆数据结构非常适合这个问题。

因此,我尝试使用Collections框架的PriorityQueue类实现一个解决方案,假设它在功能上与堆相同。

这是我尝试过的代码:

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) 
}

基于docs,poll和add方法需要O(log n)时间并且peek需要恒定时间。

  1. while循环的时间复杂度是多少? (我想O(k log n))。
  2. 为了这个问题,O(k log n)是否应被视为高于O(n)?是否有切换的阈值?
  3. 这段代码的总时间复杂度是多少?是O(n)吗?
  4. 如果还没有O(n),有没有办法在O(n)中解决它,同时使用PriorityQueue类?
java algorithm collections time-complexity priority-queue
1个回答
1
投票

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(MAX(n,k log n))。

4.如果还没有O(n),有没有办法在O(n)中解决它,同时使用PriorityQueue类?

没有。在最坏情况下O(n)时间存在selection algorithms,但它们有点复杂,并且它们不使用PriorityQueue

基于PriorityQueue的最快解决方案需要O(MAX(n,n log MIN(k,n-k)))时间。 (关键是在迭代时只保留堆中的k个最小元素 - 或者n-k个最大元素并使用max-heap,如果k足够大则值得。)

© www.soinside.com 2019 - 2024. All rights reserved.