algorithm - 复杂度为 O(n) 的二维数组中的寻峰算法

Question

题目如题。我想弄清楚是否有一种方法可以找到峰值元素O(n) 时间内的二维数组，其中 n 是二维数组中每条边的长度，即n^2 个元素。

根据定义，二维数组中的“峰值”是这样的元素 >=到它的所有邻居(即上、下、左和右插槽中的元素)。

我在以下位置阅读了类(class)笔记: http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf并理解如何在 O(nlogn) 中做，但似乎不太掌握如何处理 O(n)。

谁能想出或解释一下如何在 O(n) 中解决这个问题？

编辑:n 是数组每一边的长度，即总共有 n^2 个元素。

Answer 1

链接的 PDF 中给出的第二个算法是 O(n)。 “窗口”被定义为当前子方 block 的边界(即所有四个外边缘)、中间列和中间行的集合。以下是该算法的摘要:

1. 在当前窗口中找到最大值
2. 如果是峰值就返回
3. 否则，找到这个最大值的较大邻居并在相应的象限中递归。

如幻灯片中所述，时间复杂度定义为 T(n) = T(n/2) + cn(T(n/2)项是由于在每个递归步骤中边长减半；cn 项是在当前窗口中找到最大值所需的时间)。因此，复杂度为 O(n)。

该算法的正确性基于其中一张幻灯片上列出的几个观察结果:

If you enter a quadrant, it contains a peak of the overall array

这基本上是同一一维论证的概括。只有当象限包含的元素大于边界上的所有元素时，您才进入象限。因此，要么该元素将成为峰值，要么您可以继续“向上攀登”，直到在象限中的某处找到峰值。

Maximum element of window never decreases as we descend in recursion

递归中的下一个窗口总是包含当前窗口的最大元素，所以这是真的。

Peak in visited quadrant is also peak in overall array

这是根据峰值的定义得出的，因为它只取决于直接的邻居。