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

Question

Проблема состоит в том, чтобы найти максимум в каждом подмассиве размера 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?

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

Как добиться n * k? На каждом шаге нам нужно сделать k «хлопков» из дэка. Таким образом, элементы в 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 он должен выдавать гораздо меньше (иначе деко будет пустым с самого начала). Дерьмо ... нет n * k для тебя: (

---

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

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

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

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