Поиск пика в 2D сетке с обходом

Question

У нас есть сетка n-by-n, в которой нижний левый угол имеет координаты (0,0) и верхний правый (n, n). Ячейки в сетке имеют разные значения, и наша цель - найти локальный пик, который определяется как ячейка, которая имеет значение, большее его левого, правого, верхнего и нижнего соседей (т.е. диагонально смежные ячейки не дело).

Дело в том, что мы можем видеть только значение ячейки, посещая эту ячейку (т. Е. Мы не можем проверить значение (i, j) без принятия первых шагов (i + j) 0,0)). Как найти локальный пик в O (n) шагах?

Answer 1

Он может быть вычислен в O (nlgn) раз, используя стратегию разделения и завоевания. Это немного лучшая временная привязка, чем алгоритм грубой силы, содержащийся в классе сложности времени O (n^2).

Я нашел это pdf на google. Надеюсь, это поможет.

Local maxima using Divide and Conquer