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

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) .