arrays - O(n) 最坏情况下的 2D 峰值查找算法？

Question

我在做 this麻省理工学院的算法类(class)。在第一个类中，教授提出了以下问题:-

二维数组中的峰值是一个值，它的所有 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]

现在给定一个 NxN 二维数组，在数组中找到一个峰。

通过遍历所有元素并返回峰值，可以在 O(N^2) 时间内轻松解决此问题。

但是，如 here 所述，可以使用分而治之的解决方案对其进行优化，使其在 O(NlogN) 时间内得到解决。 .

但是他们说存在一个O(N) 时间算法可以解决这个问题。请建议我们如何在 O(N) 时间内解决这个问题。

PS(给会python的人) 类(class)人员讲解了一个方法here (问题 1-5。Peak-Finding Proof)并且还在他们的问题集中提供了一些 python 代码。但是解释的方法是完全不明显的，很难破译。 python 代码同样令人困惑。所以我把下面的主要部分代码复制给那些懂python的人，可以从代码中看出使用的是什么算法。

def algorithm4(problem, bestSeen = None, rowSplit = True, trace = None):
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    subproblems = []
    divider = []

    if rowSplit:
        # the recursive subproblem will involve half the number of rows
        mid = problem.numRow // 2

        # information about the two subproblems
        (subStartR1, subNumR1) = (0, mid)
        (subStartR2, subNumR2) = (mid + 1, problem.numRow - (mid + 1))
        (subStartC, subNumC) = (0, problem.numCol)

        subproblems.append((subStartR1, subStartC, subNumR1, subNumC))
        subproblems.append((subStartR2, subStartC, subNumR2, subNumC))

        # get a list of all locations in the dividing column
        divider = crossProduct([mid], range(problem.numCol))
    else:
        # the recursive subproblem will involve half the number of columns
        mid = problem.numCol // 2

        # information about the two subproblems
        (subStartR, subNumR) = (0, problem.numRow)
        (subStartC1, subNumC1) = (0, mid)
        (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1))

        subproblems.append((subStartR, subStartC1, subNumR, subNumC1))
        subproblems.append((subStartR, subStartC2, subNumR, subNumC2))

        # get a list of all locations in the dividing column
        divider = crossProduct(range(problem.numRow), [mid])

    # find the maximum in the dividing row or column
    bestLoc = problem.getMaximum(divider, trace)
    neighbor = problem.getBetterNeighbor(bestLoc, trace)

    # update the best we've seen so far based on this new maximum
    if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
        bestSeen = neighbor
        if not trace is None: trace.setBestSeen(bestSeen)

    # return when we know we've found a peak
    if neighbor == bestLoc and problem.get(bestLoc) >= problem.get(bestSeen):
        if not trace is None: trace.foundPeak(bestLoc)
        return bestLoc

    # figure out which subproblem contains the largest number we've seen so
    # far, and recurse, alternating between splitting on rows and splitting
    # on columns
    sub = problem.getSubproblemContaining(subproblems, bestSeen)
    newBest = sub.getLocationInSelf(problem, bestSeen)
    if not trace is None: trace.setProblemDimensions(sub)
    result = algorithm4(sub, newBest, not rowSplit, trace)
    return problem.getLocationInSelf(sub, result)

#Helper Method
def crossProduct(list1, list2):
    """
    Returns all pairs with one item from the first list and one item from 
    the second list.  (Cartesian product of the two lists.)

    The code is equivalent to the following list comprehension:
        return [(a, b) for a in list1 for b in list2]
    but for easier reading and analysis, we have included more explicit code.
    """

    answer = []
    for a in list1:
        for b in list2:
            answer.append ((a, b))
    return answer

Answer 1

1. 假设数组的宽度大于高度，否则我们将向另一个方向拆分。
2. 将数组分成三部分:中心列、左侧和右侧。
3. 遍历中心列和两个相邻列并寻找最大值。
   • 如果它在中央列 - 这是我们的高峰
   • 如果它在左侧，则在子数组 left_side + central_column 上运行此算法
   • 如果它在右侧，则在子数组 right_side + central_column 上运行此算法

为什么会这样:

对于最大元素位于中心列的情况 - 显而易见。如果不是，我们可以从那个最大值开始往递增的元素走，肯定不会越过中间那一行，所以对应的一半肯定有峰。

为什么这是 O(n):

第 3 步需要小于或等于 max_dimension 次迭代，并且 max_dimension 每两个算法步骤至少减半。这给出了 n+n/2+n/4+...，即 O(n)。重要细节:我们按最大方向分割。对于正方形阵列，这意味着拆分方向将交替进行。这与您链接到的 PDF 中的最后一次尝试不同。

注意:我不确定它是否与您提供的代码中的算法完全匹配，它可能是也可能不是不同的方法。