이 코드의 시간 복잡도

Question

N 점을 포함하는 배열이 주어지면 K 평면은 원점 (0, 0)을 가리 킵니다. K가 N 보다 훨씬 작고 N이 매우 크다고 가정 할 수 있습니다.

예컨대 :

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

} 

질문 :

1. 라인 35, 라인 39, 각각 독립적으로 의 시간 복잡도는 어떻게됩니까?

2. 줄 35-40 (전체적으로)의 시간 복잡도는 어떻게됩니까?

3. 라인 44 - 46 (전체적으로)의 시간 복잡도는 어떻게됩니까?

4. 전체 메소드 getKNearestPoints()에 대한 전반적인 시간 복잡도는 무엇입니까? n >> k라면? 그리고 n >> k가 없으면 어떻게 될까요?

사실이 질문은 내 기술 면접시 질문의 몇 가지,하지만 난 여전히에 좀 혼란 스러워요. 어떤 도움을 주셔서 감사합니다.

Answer 1

이 코드를 작성한 사람은이 질문에 대한 대답을 알고 있어야합니다.

어쨌든 우선 순위 대기열은 최대 힙 구현을 기반으로합니다.

그래서, 복잡성은 다음과 같습니다

라인 35-O(log k) 힙의 요소를 삽입 할 수있는 시간입니다. 삽입시 힙에서 Bottom up 방식을 따른다.

라인 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은이 주제를 공부하는 데 아주 좋은 장소입니다.