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

AAC спросил: 07 октября 2018 в 12:52 в: algorithm

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

0 ответов