Quelle est la complexité temporelle de cette fonction?

Question

Voici un exemple de solution pour le problème Sliding Window Maximum en Java.

Compte tenu d'une nums de réseau, il y a une fenêtre glissante de taille k qui est passer de l'extrême gauche de la rangée à l'extrême droite. Vous pouvez seulement voir les k numéros dans la fenêtre. Chaque fois que la fenêtre coulissante se déplace à droite d'une position.

Je souhaite connaître la complexité temporelle et spatiale de cette fonction. Voici ce que je pense, serait la réponse:

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

Espace (auxiliaire): O(n) pour le retour int[] et O(k) pour pq. Total de O(n).

Est-ce correct?

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

Vous avez raison dans la plupart de la partie, sauf -

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

Ici nombre total d'exécutions est log1 + log2 + log3 + log4 + ... + logk. La somme de cette série -

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

Et seconde pensée est, vous pouvez le faire mieux que votre solution de temps linearithmic en utilisant la propriété de Deque qui sera O(n). Voici ma solution -

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.