{Java - PriorityQueue} 此代码的时间复杂度

Question

Given an array containing N points find the K closest points to the origin (0, 0) in the 2D plane. You can assume K is much smaller than N and N is very large.

E.g:
    given array: (1,0), (3,0), (2,0), K = 2 
        Result = (1,0), (2,0)  
(result should be in ascending order by distance)

代码：

import java.util.*;

class CPoint {
    double x;
    double y;
    public CPoint(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

public class KClosest {
    /**
     * @param myList: a list of myList
     * @param k: the number of closest myList
     * @return: the k closest myList
     */
    public static CPoint[] getKNearestPoints(CPoint[] myList, int k) {

        if (k <= 0 || k > myList.length)  return new CPoint[]{};                                
        if (myList == null || myList.length == 0 )  return myList; 

        final CPoint o = new CPoint(0, 0); // origin point

        // use a Max-Heap of size k for maintaining K closest points
        PriorityQueue<CPoint> pq = new PriorityQueue<CPoint> (k, new Comparator<CPoint> () {
            @Override
            public int compare(CPoint a, CPoint b) {
                return Double.compare(distance(b, o), distance(a, o));  
            }
        });

        for (CPoint p : myList) {   // Line 33
            // Keep adding the distance value until heap is full. // Line 34
            pq.offer(p);            // Line 35
            // If it is full        // Line 36
            if (pq.size() > k) {    // Line 37
                // Then remove the first element having the largest distance in PQ.// Line 38
                pq.poll();          // Line 39  
            }  // Line 40
        }       
        CPoint[] res = new CPoint[k];
        // Then make a second pass to get k closest points into result. 
        while (!pq.isEmpty()) {     // Line 44
            res[--k] = pq.poll();   // Line 45                   
        }                           // Line 46

        return res;
    }

    private static double distance(CPoint a, CPoint b) {        
        return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    }

}

问题：

What is time complexity for line 35, line 39, independently and separately?

What is time complexity for line 35 - 40 (As a whole) ?

What is time complexity for line 44 - 46 (As a whole) ?

What is overall time complexity for entire method getKNearestPoints(), in best, worst and average case? What if n >> k ? and what if we don't have n >> k ?

实际上这些问题是我在技术面试中提出的几个问题，但我仍然有点困惑。感谢任何帮助。

Answer 1

看来，我想写这段代码的人一定知道这些问题的答案了。

反正这里的Priority Queue是基于Max Heap实现的

所以，复杂度如下：

第35行 - O(log k)向堆中插入一个元素的时间。插入时在堆中遵循自下而上的方法。

37行 - O(1),检查堆大小的时候，一般是随堆一起维护的。

第39行 - O(log k)，去掉堆头的时候，root处的heapify方法应用堆的顶部以移除堆的顶部。

35-40行：从上面的复杂度我们可以看出，一次迭代的整体复杂度会是O(log k)。此循环运行 n 个元素，因此整体复杂度将为 O(n log k).

44-46行：检查堆大小的复杂度又是O(1)，轮询是O(log k)。所以我们正在进行 k 次轮询。循环的整体复杂度为 O(k log k).

总体复杂度将保持 O(n log k)。

This 是研究这个主题的好地方。

{Java - PriorityQueue} 此代码的时间复杂度

{Java - PriorityQueue} time complexity of this code

java

algorithm

priority-queue

time-complexity

comparator