這個函數的時間複雜度是多少？

Question

下面是Java中Sliding Window Maximum問題的示例解決方案。

給定一個數組nums，有一個大小爲k的滑動窗口，它從數組的最左邊移動到最右邊。您只能在窗口中看到 的k個數字。滑動窗口每次移動 向右移動一個位置。

我想獲得這個功能的時間和空間的複雜性。這是我覺得這是答案：

時間：O((n-k)(k * logk)) == O(nklogk)

空間（輔助）：O(n)退貨int[]和O(k)爲pq。共有O(n)。

這是正確的嗎？

private static int[] maxSlidingWindow(int[] a, int k) { 
    if(a == null || a.length == 0) return new int[] {}; 
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, new Comparator<Integer>() { 
     // max heap 
     public int compare(Integer o1, Integer o2) { 
      return o2 - o1; 
     } 
    }); 
    int[] result = new int[a.length - k + 1]; 
    int count = 0; 
    // time: n - k times 
    for (int i = 0; i < a.length - k + 1; i++) { 
     for (int j = i; j < i + k; j++) { 
      // time k*logk (the part I'm not sure about) 
      pq.offer(a[j]); 
     } 

     // logk 
     result[count] = pq.poll(); 
     count = count + 1; 
     pq.clear(); 
    } 
    return result; 
} 

Answer 1

你說得對大多數部分除外 -

for (int j = i; j < i + k; j++) { 
    // time k*logk (the part I'm not sure about) 
    pq.offer(a[j]); 
} 

處決這裏總數爲log1 + log2 + log3 + log4 + ... + logk。這一系列的總和 -

log1 + log2 + log3 + log4 + ... + logk = log(k!) 

而第二個想法是，你可以使用，這將是O(n)雙端隊列屬性做到這一點比你linearithmic時間更好的解決方案。這是我的解決方案 -

public int[] maxSlidingWindow(int[] nums, int k) {  
    if (nums == null || k <= 0) { 
     return new int[0]; 
    } 
    int n = nums.length; 
    int[] result = new int[n - k + 1]; 
    int indx = 0; 

    Deque<Integer> q = new ArrayDeque<>(); 

    for (int i = 0; i < n; i++) { 

     // remove numbers out of range k 
     while (!q.isEmpty() && q.peek() < i - k + 1) { 
      q.poll(); 
     } 

     // remove smaller numbers in k range as they are useless 
     while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) { 
      q.pollLast(); 
     } 

     q.offer(i); 
     if (i >= k - 1) { 
      result[indx++] = nums[q.peek()]; 
     } 
    } 

    return result; 
} 

HTH。