此代码的时间复杂度

给定一个包含N个点的数组，在2D平面中查找K最接近原点（0，0）的点。你可以假设K比N小得多，N非常大。此代码的时间复杂度

E.g：
given array: (1,0), (3,0), (2,0), K = 2 
     Result = (1,0), (2,0) 
（结果应该是在由距离升序）

代码：

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呢？

其实这些问题都是我的技术面试时的几个问题，但我仍然在它有点困惑。任何帮助表示赞赏。

来源

2017-10-08 Peter

这看起来很像家庭作业。你到底迷惑了什么？你认为答案是什么？为什么？ – Krease

我在回答采访时回答：Q1：log（K），log（K），Q2：log（K）或log（K）^ 2 Q3：klog（K）Q4：NlogK + klogK，但总体来说是NlogK？我不知道 – Peter

我知道PQ，所有的操作像添加/提供，删除/轮询需要OlogK，除非偷看是O1。但专门针对这些问题。我真的有点失落.. – Peter

从外观上来看，我觉得谁写这种代码的人必须知道这些问题的答案。

总而言之，此处的优先级队列基于Max Heap实现。

所以，复杂性如下：

线35 - O(log k)在堆插入元素的时间。自下而上的方法在插入时在堆中进行。

第37行 - O(1)，检查堆大小的时间，一般与堆一起保存。

第39行 - O(log k)，以除去堆的头的时间，在堆的根的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是一个很棒的地方来研究这个话题。

来源

2017-10-08 05:13:43 harman786

嗨！这个答案真的很有帮助。但我仍然有点困惑* 35-40行*。说这个PQ满了的时候，会有（n-k）次，pq.offer（p）;和pq.poll（）;应该一起执行。这应该是O（logk）+ O（logk），对吧？但为什么我们仍然认为它是O（logk）运行时？ – Peter

好吧，把它放在数学上，O（logk）+ O（logk）= O（2logk）= O（logk^2）= O（logk），我的意思是它们可以用所有这些方法来写。 – harman786

这很有道理！谢谢！还有一个问题，为什么我们可以“放弃”“进行第二次传球以获得最接近的k个结果”的时间。（klogk）？总的来说是O（nlogK），但不是O（nlogk）+ O（klogk） – Peter

此代码的时间复杂度

回答

相关问题