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

Question

Локальный максимум в двумерном массиве может быть определен как значение, так что все его 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).Я чувствую, что вы не можете добиться большего успеха, чем это, хотя мой друг настаивает на том, что должен существовать асимптотически лучший алгоритм.Есть намеки?

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

Answer 1

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

Ознакомьтесь с этими замечаниями по теории, лежащей в основе таких алгоритмов выбора пиков (я уверен, что их больше):

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

Answer 2

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

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

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

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

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

Answer 3

Вам дан массив размером 4 x 4. Вам нужно будет выполнить следующую задачу.

1. Заполните массив несколькими случайными числами, используя функцию rand ().

2. Для каждой ячейки (i, j) вам необходимо найти ячейку с максимальным числом среди всех возможных соседей, которые имеет ячейка (i, j).

3. Затем поместите это максимальное число в эту ячейку (i, j)

Пример ввода:

177 -90 12 7
1 34 43 67
11 11 122 45
6 90 98 93

Пример вывода:

34 177 67 67
177 177 122 122
90 122 98 122
90 98 122 122

Answer 4

Над ответами просто защищайте математическую модель.
Который является результатом упрощенного взгляда на проблему.

Если вы работаете программистом, вы должны знать, на что способен процессор. И вы должны знать, что код выполняется в потоке. Вы должны задаться вопросом, является ли задача подразделяемой в меньших задачах, чтобы вы могли выполнять ее многопоточно и получить почти полное ускорение выполнения 1 / total-thread.

Код для этого зависит от языка, поэтому я не привожу здесь пример.

Answer 5

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

Все, что вам нужно сделать, это визуализировать сетку, и вы увидите, что это может быть решено гораздо меньше, чем в плоском n ^ 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 6

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

Answer 7

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

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