固定大小为4的PriorityQueue的add/poll时间复杂度及程序复杂度分析

结论 #

该程序的时间复杂度为 O(n)，你提到的「优先队列大小固定不超过4，对应操作为常数开销」的推导是完全正确的。

核心逻辑说明 #

• 优先队列的add()、poll()操作的时间复杂度实际为 O(log k)，这里的k是当前优先队列内的元素个数，而非被遍历数组的大小n，这是很多人容易混淆的参数定义。
• 本题中两个优先队列的大小永远不会超过4，因此log 4是固定常量，在大O复杂度表示规则里，常量项可以直接忽略不计。

逐段开销拆解 #

1. 数组遍历环节共执行n次循环：
   • 前4次循环仅执行add操作，每次最多执行2次add，开销为固定常数
   • 后续n-4次循环，每次最多执行2次poll+2次add，每次操作的开销都是固定常数，和数组大小n没有关联
2. 遍历结束后从两个队列取出8个元素的操作执行次数固定，同样属于常数开销

整体时间复杂度为n × 常数，也就是 O(n)。

补充说明：只有当你需要获取的元素数量k和数组大小n成正比（比如要取前n/2大的元素），队列大小k会随n同步增长时，整体时间复杂度才会是 O(n log 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);
    }
}

内容的提问来源于stack exchange，提问作者Abed Sheriff