Алгоритм поиска пиков в 2d-массиве со сложностью O (n) - PullRequest
Новая
       22

Алгоритм поиска пиков в 2d-массиве со сложностью O (n)

0 голосов
/ 01 июня 2018

Вопрос, как гласит заголовок.Я пытаюсь выяснить, есть ли способ найти пиковый элемент в 2d-массиве за время O (n), где n - длина каждой стороны в 2d-массиве, т.е. всего n ^ 2 элементов.

По определению, «пик» в двумерном массиве - это такой элемент, что он> = для всех своих соседей (то есть элементов в слотах вверх, вниз, влево и вправо).

Я читаю заметку о курсеat: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf и понимал, как это сделать в O (nlogn), но, похоже, не совсем понимает, что делать с O (n).

Может кто-нибудь придумать или объяснить, как этопроблема может быть решена в O (n)?

Редактировать: n - длина каждой стороны массива, т.е. всего n ^ 2 элементов.

1 Ответ

0 голосов
/ 02 июня 2018

Второй алгоритм, приведенный в связанном PDF, - это O (n).«Окно» определяется как совокупность границы (т. Е. Всех четырех внешних ребер), среднего столбца и среднего ряда текущего субквадрата.Вот краткое изложение алгоритма:

  1. Найти максимальное значение в текущем окне
  2. Вернуть его, если это пик
  3. В противном случае, найти более крупного соседа этого максимума иrecurse в соответствующем квадранте.

Как описано в слайдах, сложность времени определяется как T (n) = T (n / 2) + cn (* 1013Член * T (n / 2) обусловлен уменьшением длины ребра на каждом рекурсивном шаге; член cn - это время, необходимое для нахождения максимума в текущем окне).Следовательно, сложность составляет O (n).

Правильность этого алгоритма основана на нескольких наблюдениях, которые перечислены на одном из слайдов:

Если вы введетеквадрант, он содержит пик всего массива

Это в основном обобщение одного и того же 1D-аргумента.Квадрант вводится только в том случае, если он содержит некоторый элемент, превышающий все элементы на границе.Таким образом, либо этот элемент будет вершиной, либо вы можете продолжать «подниматься», пока не найдете вершину где-то в квадранте.

Максимальный элемент окна никогда не уменьшается, когда мы спускаемся врекурсия

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

Пик в посещенном квадрантетакже является пиковым в общем массиве

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

...