Почему решение задачи "Максимум скользящего окна" в стиле deque вместо O (nk)?

Задача состоит в том, чтобы найти максимум в каждом подмассиве размера k в массиве длины n.

Метод грубой силы O (nk). Но используя deque, решение предположительно O (n). Однако я не уверен, что он попадает в O (n), в частности из-за этого цикла while:

# Remove all elements smaller than 
# the currently being added element  
# (Remove useless elements) 
while Qi and arr[i] >= arr[Qi[-1]] : 
    Qi.pop()

который находится внутри цикла for от k до n. Не может ли это технически выполнить до k раз каждый цикл, давая где-то между O (n) и O (kn)? Является ли сложность времени наихудшего случая на самом деле O (kn) даже для решения deque?

Ответ 1

Каждый элемент добавляется в деку ровно один раз.

Таким образом, вы не можете иметь больше операций pop, чем количество элементов, которое равно O (n).

Условие while иногда будет проверяться без всплывающего окна, но количество выполненных операций не более чем равно количеству циклов, которые мы получаем для цикла while (т.е. Числу итераций обоих для циклов), что На).

Остальная часть кода также O (n), таким образом, общее время выполнения O (n + n + n) = O (n).

Ответ 2

Давайте докажем, что операции с крайним наихудшим случаем n * k невозможны (просто чтобы понять, а остальные промежуточные операции можно доказать аналогичным образом):

Как добиться n * k? На каждом шаге нам нужно сделать k "pops" из deque. Таким образом, элементы в deque выглядят так (на этой иллюстрации k == 5):

до:

| ,              #
| | | ,          #   (like a heavy bowling ball)
| | | | ,        #  
---------------------------------------------------             
^^^^^^^^^        ^
our deque        new badass element coming *vruuuum*

после

#
#     *bang* (sound of all pins knoked down)
#  
---------------------------------------------------             
^
this new guy totally smashed our deque in 5 operations!

но эй... погоди

Как наша дека накопила k элементов?

Ну, для того, чтобы накопить k элементов, он должен бросить намного меньше на предыдущих k шагах (иначе deque будет пустым с самого начала). Дерьмо... нет n * k для тебя :(

Это делает более общее утверждение о динамике нашего алгоритма:

Если i й элемент массива выдает m "pops" из очереди, предыдущие элементы наверняка будут достаточно "хромыми", чтобы выровнять "задиру" i го элемента.

Теперь, если вы смотрите не с точки зрения deque, а с точки зрения целого массива: каждый раз вы бросаете уникальный элемент массива. Таким образом, количество "всплывающих окон" не должно быть больше, чем количество элементов в массиве, которое равно n.

Что делает нашу сложность O(n).

Ответ 3

Я не знаю математического доказательства, но следующая мысль может помочь понять его:

Обратите внимание, что индексы элементов хранятся в deque, но для простоты объяснения сложности я говорю об элементах, а не об индексе.

Когда новый элемент в окне не больше самого большого элемента в deque (элемент в начале dequeue), но больше, по крайней мере, наименьшего элемента в deque (элемент в задней части deque), тогда мы не только сравниваем новый элемент с элементами deque (от задней части к передней), чтобы найти правильное место, , а также отбросить элемент из deque, который меньше, чем новый элемент.

Так что не рассматривайте вышеупомянутую операцию как поиск нужного места нового элемента в отсортированной деке длиной k, вместо этого смотрите на это как выталкивание элементов deque, меньших, чем новый элемент. Эти более мелкие элементы были добавлены в deque в некоторый момент, они жили некоторое время, и теперь они появляются. В худшем случае каждый элемент может получить эту привилегию вставлять и извлекать из deque (хотя это делается вместе с операцией поиска первого числа сзади, большего, чем новый элемент, и это приводит к путанице).

И поскольку каждый элемент может быть нажат и вытолкнут максимум один раз, следовательно, сложность является линейной.