вложенные циклы, имеющие линейную сложность по времени?

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 l oop будет выполнена k раз. Однако автор сказал, что сложность амортизированного времени равна O (n). Как так ? я не совсем понимаю?

Answer 1

Поскольку внутренний (while) l oop будет иметь разное количество итераций для каждой итерации внешнего (for) l oop, вы не можете просто ограничить количество итераций этого l oop на k, так как эта граница не будет достаточно узкой.

Вместо этого мы можем попытаться вычислить общее количество операций на всех итерациях внутреннего l oop.

внешнего l oop добавляет каждый индекс ровно один раз в очередь (в dq.offer(i)).

Каждый индекс, добавленный в очередь, может быть удален только один раз - либо dq.poll(), либо dq.pollLast() .

Поскольку каждая итерация while l oop должна удалять элемент из очереди, все итерации while l oop (для всех итераций внешнего для l oop) ограничены n (поскольку не может быть более n удалений). Следовательно, все итерации while l oop вносят O(n) в общее время выполнения.

Помимо while l oop, другие операции внутри внешнего для l oop явно принимают постоянные время, поэтому они стоят O(n) время при сложении всех итераций внешнего l oop.

Следовательно, общее время выполнения составляет O(n).