Нахождение локальных максимумов в 2D массив

Question

Локальный максимум в 2D массив может быть определен как значение таким образом, что все это 4 соседей меньше или равна ей, то есть для a[i][j] быть локальным максимумом,

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] 

Меня попросили найти все локальные максимумы в заданном двумерном массиве.

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

Я думал о линиях Divide и Conquer, но я чувствую, что невозможно обнаружить все локальные максимумы, не пройдя через все числа, что обязательно будет O (n^2). Я прав, или я что-то упускаю?

Answer 1

Я уверен, что это невозможно решить менее чем через O (n^2). Предположим, что матрица шахматной доски 2d, где все белые квадраты равны 1 и черные равны 0. Она будет иметь решения O (n^2), и для каждого решения требуется по крайней мере одно сравнение.

Answer 2

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

И, на мой взгляд, вы правы .. это потребует по крайней мере n^2 сравнений.

Answer 3

Если ваш массив квадратный, ваше решение на самом деле O(I * J) не O(n^2). Строго говоря, у вас есть только N элементов в вашем 2d массиве, таким образом, это решение - O(N). Единственный способ, которым это могло быть O(n^2), - это массив, который был квадратным, так что I = J = N.

Поскольку сравнение <=, а не <, вам нужно все же проверить следующий элемент, если какие-либо ярлыки вы попробуете, скорее всего, будут специфичными для процессора.

Худший случай, что весь массив является локальным максимумом, поскольку весь массив равен тому же значению.

Таким образом, вы должны посетить каждый элемент один раз, что делает его O(N)

Чтобы улучшить реальную производительность мира в этом вам нужно будет использовать указатели для доступа к вам массив, как и в большинстве языков 2d массивы выполняют значительно хуже, чем 1d массивы ,

Answer 4

ВАМ НЕ ПОСЕТИТЬ КАЖДЫЙ ЭЛЕМЕНТ:

Все, что вам нужно сделать, это визуализировать сетку, и вы увидите, что это может быть решена гораздо меньше, чем плоский п^2 (или I * J) , Ниже перечислены оптимизации по уровню:

1] для матрицы I * J вам нужен только поиск (I-2) * (J-2). Зачем? границы не могут быть максимумами из-за неопределенных элементов:

e.g. grid[0][J] or grid[I][0] could never be maxima. because of the -1 neighbor. 

Таким образом, для 10 по 12 сетке, вместо того, чтобы посетить все 120 элементов, мы смотрим на 80 элементов.

2] если сетка [I] [J] является максимальной, то мы можем пропустить все ячейки, смежные с [I] [J], по мере продолжения поиска. Это еще больше уменьшит количество элементов для сравнения.

Следовательно, ответ отрицательный, вам не нужно посещать каждый элемент.

Answer 5

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

Проверьте эти заметки по теории позади такого пик собирания алгоритмов (я уверен, что их больше материалов там):

http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf