此代碼的時間複雜度

給定一個包含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

此代碼的時間複雜度

回答

相關問題