具有线性时间复杂度的嵌套循环？

Question

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0) {
        return nums;
    }
    int[] result = new int[n - k + 1];
    LinkedList<Integer> dq = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (!dq.isEmpty() && dq.peek() < i - k + 1) {
            dq.poll();
        }
        while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
            dq.pollLast();
        }
        dq.offer(i);
        if (i - k + 1 >= 0) {
            result[i - k + 1] = nums[dq.peek()];
        }
    }
    return result;
}

据我了解，此代码的最坏情况复杂度为 n*k，因为在最坏情况下，内部 while 循环将执行 k 次。然而，作者说过分摊时间复杂度是 O(n)。那个怎么样？我不是很明白？

Answer 1

由于内部 (while) 循环对于外部 (for) 循环的每次迭代都有不同的迭代次数，您不能简单地用 k 限制该循环的迭代次数，因为该限制不会够紧吧。

相反，我们可以尝试计算内循环所有迭代中的操作总数。

外循环将每个索引恰好添加到队列中一次（dq.offer(i)）。

添加到队列中的每个索引只能删除一次 - 通过 dq.poll() 或 dq.pollLast()。

由于 while 循环的每次迭代都必须从队列中删除一个元素，因此 while 循环的所有迭代（跨越外部 for 循环的所有迭代）都以 n 为界（因为不能超过 n 次移除）。因此，while 循环的所有迭代对总运行时间的贡献为 O(n)。

除了 while 循环，外层 for 循环内的其他操作显然需要常数时间，因此在添加外层循环的所有迭代时它们花费 O(n) 时间。

因此总运行时间为 O(n)。

具有线性时间复杂度的嵌套循环？

nested loops having linear time complexity?

java

big-o

time-complexity

nested-loops