Was ist die zeitliche Komplexität dieser Funktion?

Question

Hier ist eine Beispiellösung für Sliding Window Maximum Problem in Java.

ein Array nums Gegeben ist ein Schiebefenster k der Größe, die sich von ganz links des Arrays ganz rechts ist. Sie können nur die k Zahlen im Fenster sehen. Jedes Mal, wenn sich das Schiebefenster um um eine Position verschiebt.

Ich möchte die Zeit und Raum Komplexität dieser Funktion zu bekommen. Hier ist, was ich denke, wäre die Antwort:

Zeit: O((n-k)(k * logk)) == O(nklogk)

Raum (Hilfs-): O(n) für die Rückkehr int[] und O(k) für pq. Insgesamt O(n).

Ist das korrekt?

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

Du hast Recht in den meisten der Teil mit Ausnahme -

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

Hier Gesamtzahl der Hinrichtungen ist log1 + log2 + log3 + log4 + ... + logk. Die Summe dieser Reihe -

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

Und zweiter Gedanke ist, können Sie es besser als Ihre linearithmic Zeitlösung mit Deque Eigenschaft, die O(n) sein wird. Hier ist meine Lösung -

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.