这段代码的时间复杂度是什么？（关于Java中的PriorityQueue）

Question

这段代码的时间复杂度是什么？（关于Java中的PriorityQueue）

javaalgorithmtime-complexitycomparatorpriority-queue

3

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

}

问题：

第35行和第39行的时间复杂度分别是什么？

第35 - 40行（整体）的时间复杂度是多少？

第44 - 46行（整体）的时间复杂度是多少？

在最好情况，最坏情况和平均情况下，整个getKNearestPoints()方法的总体时间复杂度是多少？如果n>>k怎么办？如果我们没有n>>k怎么办？

实际上，这些问题是我技术面试中的几个问题，但我还是有些困惑。感谢您的帮助。

- Peter

2

这篇很像作业。你具体困惑在哪里？你认为答案是什么，为什么？ - Krease

我在面试中回答了以下问题：Q1: log(K), log(K)，Q2: log(K)或log(K) ^ 2，Q3: klog(K)，Q4: NlogK + klogK，但总体而言是NlogK？我不确定。 - Peter

1

我知道对于PQ，所有的操作如add/offer、remove/poll都需要OlogK的时间复杂度，除了peek是O1。但是对于这些问题，我真的有点迷茫了... - Peter

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harmands · Accepted Answer

从外观上看，我认为编写这段代码的人必须知道这些问题的答案。

无论如何，这里的优先队列是基于最大堆实现的。

因此，复杂性如下：

第35行 - O（log k）将元素插入堆中所需的时间。在插入时，堆采用自底向上的方法。

第37行 - O（1），检查堆的大小所需的时间，通常与堆一起维护。

第39行 - O（log k），删除堆头所需的时间，在堆的根部应用堆化方法以删除堆的顶部。

第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)。

这里是一个学习这个主题的绝佳地方。