Может ли мин / макс движущегося windows достичь в O (N)?

У меня есть входной массив A

A[0], A[1], ... , A[N-1] 

Я хочу, чтобы функция Max (T, A), возвращающая B, представляла максимальное значение на A над предыдущим движущимся окном размера T, где

  B[i+T] = Max(A[i], A[i+T]) 

Используя максимальную кучу для отслеживания максимального значения для текущих движущихся окон A [i] до A [i + T], этот алгоритм дает наихудший случай O (N log (T)).

Я хотел бы знать, есть ли лучший алгоритм? Может быть, алгоритм O (N)

O (N) возможно с использованием структуры данных Deque. Он содержит пары (Value; Index).

 at every step: if (!Deque.Empty) and (Deque.Head.Index <= CurrentIndex - T) then Deque.ExtractHead; //Head is too old, it is leaving the window while (!Deque.Empty) and (Deque.Tail.Value > CurrentValue) do Deque.ExtractTail; //remove elements that have no chance to become minimum in the window Deque.AddTail(CurrentValue, CurrentIndex); CurrentMin = Deque.Head.Value //Head value is minimum in the current window 

он называется RMQ (минимальный запрос диапазона). На самом деле я однажды написал статью об этом (с кодом C ++). См. http://attiix.com/2011/08/22/4-ways-to-solve-%C2%B11-rmq/

или вы можете предпочесть википедию, Минимальный запрос диапазона

после подготовки вы можете получить максимальное количество любого заданного диапазона в O(1)

В обработке изображений имеется подполе, называемое математической морфологией. Операция, которую вы выполняете, является основной концепцией в этой области, называемой расширением . Очевидно, что эта операция изучена широко, и мы знаем, как ее реализовать очень эффективно.

Наиболее эффективный алгоритм для этой проблемы был предложен в 1992 и 1993 годах независимо от ван Херка, Гила и Вермана. Для этого алгоритма требуется ровно 3 сравнения на выборку, независимо от размера T

Спустя несколько лет Гил и Киммель дополнительно уточнили алгоритм, которому требуется всего 2,5 сравнения на выборку. Хотя повышенная сложность метода может компенсировать меньшее количество сравнений (я считаю, что более сложный код работает медленнее). Я никогда не реализовывал этот вариант.

Алгоритм HGW, как он называется, нуждается в двух промежуточных буферах того же размера, что и вход. Для смехотворно больших входов (миллиардов образцов) вы можете разделить данные на куски и обработать их по кусочкам.

В своем роде вы просматриваете данные вперед, вычисляя совокупный максимум над кусками размера T Вы делаете то же самое, что и вы идете назад. Каждое из них требует одного сравнения на выборку. Наконец, результатом является максимум по одному значению в каждом из этих двух временных массивов. Для местоположения данных вы можете одновременно выполнить два прохода над входом.

Я думаю, вы могли бы даже выполнить текущую версию, где временные массивы имеют длину 2*T , но это было бы сложнее реализовать.

  • ван Херк, «Быстрый алгоритм локальных минимальных и максимальных фильтров на прямоугольных и восьмиугольных ядрах», Письма о распознавании образов 13 (7): 517-521, 1992 ( doi )

  • Гил, Верман, «Вычисление двухмерных, средних и максимальных фильтров», IEEE Transactions на анализ шаблонов и машинный интеллект 15 (5): 504-507, 1993 ( doi )

  • Gil, Kimmel, «Эффективные алгоритмы расширения, эрозии, открытия и закрытия», IEEE Transactions по анализу паттерна и машинного интеллекта 24 (12): 1606-1617, 2002 ( doi )

(Примечание: перекрестная ссылка на этот связанный вопрос по обзору кода .)

Давайте будем гением компьютера.