在这种情况下，PriorityQueue add()和poll()的时间复杂度是多少

Question

如果我有一个大小为4的PriorityQueue，并且我正在对大小为'n'的数组进行迭代，并且我只想要数组中最大的4个元素。当我到达数组的末尾时，这个程序是否花费了O(n(时间或O(nlogn(时间。我知道PQ add((和remove((取O(logn(，但因为PQ的大小永远不会大于4，这是否意味着这是一个O(n(程序。

如果你想参考，这是代码

class Solution {
public int minDifference(int[] nums) {
if(nums.length <= 4) return 0;
PriorityQueue<Integer> maxq = new PriorityQueue();
PriorityQueue<Integer> minq = new PriorityQueue(new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return (a - b) * -1;
}
});

for(int i = 0; i < nums.length; i++){
if(minq.size() < 4){
minq.add(nums[i]);
maxq.add(nums[i]);
}else
{

if(nums[i] > maxq.peek()){
maxq.poll();
maxq.add(nums[i]);
}

if(nums[i] < minq.peek()){
minq.poll();
minq.add(nums[i]);
}
}
}

int smallest4 =  minq.poll();
int smallest3 = minq.poll();
int smallest2 = minq.poll();
int smallest = minq.poll();

int biggest4 = maxq.poll();
int biggest3 = maxq.poll();
int biggest2 = maxq.poll();
int biggest = maxq.poll();

int remove3End = biggest4 - smallest;
int remove3Beg = biggest - smallest4;
int twoEnd_oneStart = biggest3 - smallest2;
int oneEnd_twoStart = biggest2 - smallest3;

int a = Math.min(remove3End,remove3Beg);
int b = Math.min(twoEnd_oneStart, oneEnd_twoStart);

return Math.min(a,b);


}
}```

Answer 1

我知道PQ add((和remove((取O(logn(，但因为PQ的大小永远不会大于4，这是否意味着这是一个O(n(程序？

是的，你说得对。O(logn(中的n实际上是4，因此它变为O(log4(，即O(1(。所以你可以说add()和remove()在你的情况下是恒定时间运行的。