这个函数的时间复杂度是多少？

下面是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; 
}

来源

2017-04-15 Yar

'k'确实是一个常数？ – Boggartfly

如果k不是常数，那么如何从等式'O（（n-k）（k * logk））'中消除？ – Boggartfly

你说得对大多数部分除外 -

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。

来源

2017-04-17 04:09:00

这个函数的时间复杂度是多少？

回答

相关问题