Я делал [этот] (https://www.youtube.com/watch?v=HtSuA80QTyo&t=2592s) курс по алгоритмам из MIT. В самой первой лекции профессор представляет следующую проблему: -
Пик в двумерном массиве - это значение, при котором все его 4 соседа меньше или равны ему ie. для
a[i][j] to be a local maximum,
a[i+1][j] <= a[i][j]
&& a[i-1][j] <= a[i][j]
&& a[i][j+1] <= a[i][j]
&& a[i+1][j-1] <= a[i][j]
Теперь, учитывая двумерный массив NxN, найдите пик в массиве. Итак, профессор объясняет простое все go. : [Просмотр лекционных заметок] (https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf)
• Pick middle column j = m/2.
• Find a 1D-peak at i, j.
• Use (i, j) as a start point on row i to find 1D-peak on row i.
Однако это не удается для примера, показанного в заметке.
Итак, новый импровизированный аль go. предлагается:
• Pick middle column j = m/2
• Find global maximum on column j at (i, j)
• Compare (i, j − 1),(i, j),(i, j + 1)
• Pick left columns of (i, j − 1) > (i, j)
• Similarly for right
• (i, j) is a 2D-peak if neither condition holds ← WHY?
• Solve the new problem with half the number of columns.
• When you have a single column, find the global maximum and you‘re done.
Этот al go работает правильно и находит 2D пик в O(n logm) времени.
Интересно, что произойдет, если я использую 1D пик соответствующего столбца вместо его глобального максимума. Тогда я смогу уменьшить сложность времени до O(logm x logn) времени. Будет ли это всегда возвращать правильное значение?