Нахождение пика в 2D сетке с обходом
У нас есть n-на-n сетка такая, что нижний левый угол имеет координаты (0,0), а верхний правый (n, n). Все ячейки в сетке имеют разные значения, и наша цель - найти локальный пик, который определяется как ячейка, значение которой больше, чем ее левые, правые, выше и ниже соседей (то есть соседние по диагонали ячейки не иметь значение).
Дело в том, что мы можем видеть значение ячейки, только посещая эту ячейку (то есть мы не можем проверить значение (i, j), не выполнив сначала (i+j) шагов, чтобы добраться из (0,0)). Как мы можем найти локальный пик за O(n) шагов?
1 ответ
Он может быть вычислен за O(nlgn) время, используя стратегию "разделяй и властвуй". Это немного лучшая временная привязка, чем алгоритм перебора, содержащийся в классе временной сложности O(n^2).
Я нашел этот PDF на Google. Надеюсь, это поможет.