Что такое пик?
В массиве любая позиция является пиком тогда и только тогда, когда соседние элементы меньше или равны этому элементу в позиции. Если позиция находится на любом конце массива, то в условии учитывается только соседний элемент.
Обратите внимание, что в этом случае пик всегда будет существовать.
Теперь мы попробуем найти пик в массиве из n элементов, и мы постараемся минимизировать время, затрачиваемое программой, с применением различных алгоритмов.
Для одномерного массива:
Случай 1, линейное перемещение:
Худший случай - смотреть на каждый элемент и сравнивать соседние элементы.
Обход по массиву займет линейное время, то есть время, затрачиваемое на обход, имеет порядок n или O (n). В то время как сравнение занимает постоянное время, общее время, затрачиваемое в этом случае, составляет O (n) + C, умноженное на O (n), то есть O (n) {C + 1} единицы времени.
Случай 2, метод двоичного поиска:
В этом случае мы применим алгоритм двоичного поиска, чтобы найти пик. Пусть массив будет a.
Необходимые шаги:
- Посмотрите на позицию (n-1) / 2.
- Сравните сначала справа, а затем слева. (особенно по порядку).
- If a[(n-1)/2] < a[(n-1)/2 -1]:
Затем переходите к левой половине массива.
Иначе, если a [(n-1) / 2] ‹a [(n-1) / 2 +1]:
Затем переходите к правой половине массива.
Иначе [(n-1) / 2] - это пик.
В этом случае время значительно сокращается. Обход массива с помощью метода двоичного поиска занимает время порядка n.
Сравнение здесь также требует постоянного времени. Таким образом, общее время, затраченное здесь, равно O (log (n)) {C + 1}.
Обратите внимание, здесь журнал относится к базе 2, а ln используется как журнал для базы e.
Для двумерного массива:
Пик - это позиция, в которой элементы по сторонам всех четырех сторон, вверх - вниз - влево - вправо, меньше, чем элемент в этой позиции.
Случай 1, прямое движение вперед:
Просмотрите всю двумерную матрицу и сравните все элементы.
Это займет O (n2) {C + 1} раз.
Случай 2, алгоритм жадного восхождения:
В этом случае мы можем начать с любой точки. Алгоритм жадного восхождения говорит, что мы сравниваем значения во всех направлениях и переходим к направлению, которое имеет большее число, и в конце, когда все условия выполнены, мы находим пик.
Если в какой-то точке все четыре направления имеют меньшее, чем центральное значение, то это пик.
НАИХИЙ СЛУЧАЙ - нам нужно пройти большую часть двумерной матрицы, даже если это выгодно в конце с точки зрения затраченного времени.
Сложность по времени в этом случае равна O (mn), где m и n - строки и столбцы. Для квадратной матрицы m = n.
Случай 3, алгоритм метода двоичного поиска с помехами, приведенный выше:
Для этого мы выполним следующие шаги:
- Выберите средний столбец j = m / 2. Найдите глобальный максимум в столбце j в точке (i, j).
- Сравнить (i, j-1); (i, j); (я, j + 1)
- Выберите левые столбцы, если (i, j-1) ›(i, j), или выберите правые столбцы, если (i, j + 1)› (i, j).
- Else (i, j) - пик.
