此代码的时间复杂度
给定一个包含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呢?
其实这些问题都是我的技术面试时的几个问题,但我仍然在它有点困惑。任何帮助表示赞赏。
从外观上来看,我觉得谁写这种代码的人必须知道这些问题的答案。
总而言之,此处的优先级队列基于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是一个很棒的地方来研究这个话题。
嗨!这个答案真的很有帮助。但我仍然有点困惑* 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
这看起来很像家庭作业。你到底迷惑了什么?你认为答案是什么?为什么? – Krease
我在回答采访时回答:Q1:log(K),log(K),Q2:log(K)或log(K)^ 2 Q3:klog(K)Q4:NlogK + klogK,但总体来说是NlogK?我不知道 – Peter
我知道PQ,所有的操作像添加/提供,删除/轮询需要OlogK,除非偷看是O1。但专门针对这些问题。我真的有点失落.. – Peter