在二维数组中寻找所有峰值的高效算法

Question

在二维数组中寻找所有峰值的高效算法

9

给定一个由整数构成的矩阵 M，峰值是指该数组中的元素不小于其四个邻居（上、下、左、右）的元素。有一种很好的线性时间（对于 n × n 矩阵为 O(n)）算法可以找到峰值，例如在这些讲义中，或者在这段代码中有一个稍微简单的 O(n log n) 时间解决方案。

如果存在 k 个峰值，那么我想找到它们中的 k 个。是否有一种以 O(n + k) 或 O(n log n + k) 时间复杂度实现此操作的方法？

- Simd

这是使用核为3、步长为1和边缘填充的MaxPool算法吗？ - Mehdi

哦，很抱歉。步幅为1的最大池化操作是O(n^2)。 - Mehdi

@Mehdi 我真的不知道。听起来很不同，但也许并不是这样？ - Simd

我怀疑这是不可能的。如果数组只包含一个峰值，而你想找到两个，则必须读取整个数组才能确定只有一个峰值。 - Nico Schertler

离散网格是否代表了一个连续场的采样，你希望在其中找到最大值？ - Asad Saeeduddin

1

你必须挑选nxn数组中的每个项目，无论是查看它是否为峰值还是与其他项目进行比较。因此，无论使用何种精细技术，最佳情况都是O(n^2)。 - Ripi2

3个回答

3

假设您有一个NxN矩阵A。最初，A [i] [j] = i+j 。只有一个峰值。找到它很容易，但您正在尽快找到两个峰值。问题是，您被一个恶意的恶魔观察着，该恶魔可以更改您尚未访问过的单个元素的值。显然，您不能快速找到第二个峰值，因为恶魔了解您的动作。

具体来说，假设算法可以在不访问所有元素的情况下在矩阵中找到最多两个峰值。在 A [i] [j] = i+j 矩阵上运行它。它应该返回单个现有峰值。检查已访问的元素。将非访问元素更改为 3 * N ，从而将其变为新峰值，然后再次运行算法。它必须返回与之前相同的答案，但现在答案是错误的。

所以答案是否定的。

如果只允许输入至少具有k个峰值，则相同类型的参数也适用，只需要稍微修改即可。

假设当输入实际上具有两个或更多峰值时，算法可以找到两个峰值，同时访问

 M <N ^ 2 元素。 WLOG我们可以假设当提供仅具有一个峰值的输入时，该算法将访问所有元素（如果没有，则我们始终可以修改它以这样做而不失去其处理具有两个峰值的输入的能力，例如，在访问M次后切换到暴力搜索）。将其呈现给 A [i] [j] = i+j 矩阵。该算法将访问所有元素。请注意最后访问的元素，并将其更改为峰值（如果最后一个元素是峰值，则将倒数第二个访问的元素也更改为峰值）。再次运行算法。现在输入具有两个峰值，但是算法仍然需要访问所有元素才能找到它们。

- n. m.

1

因为我认为这不是问题的正确解释，所以我会给它点个踩——至少对我来说，问题是在问：“如果有至少k个峰值，我们能否在O(nlogn+k)的时间内找到其中的k个？”如果我错了，我会点个赞的。 - zw324

回顾来看，-1 确实有些严厉，但投票已经锁定了 :-/ - zw324

@zw324，对于你对问题的解释，同样的论点也适用。我会编辑答案，然后你可以重新投票。 - n. m.

0

我怀疑自己漏掉了些东西，因为对于我来说，“是”的答案似乎很明显。使用给定的算法找到一个峰值，但不要在找到后停止。相反，回溯；继续寻找，直到您找到 k 个峰值，或者您耗尽了您的分治算法。

在某些病态情况下——例如，有几个起点导致已知的峰值——您可以通过排列搜索顺序来提高性能。当您回溯树并横向移动时，请不要移动到相邻位置。相反，请移动到最远的未搜索节点。您可以使用一个 O(1) 距离函数来找到它，或者只需抓取一个足够远的节点（给出搜索树层级的子矩阵大小的极好估计）。

我的脑海中正在构思一个包含 k 个不同峰值的矩阵，但这种方法解决起来不太合理。二维迷宫设计的连通性提供了很多好的工具——这等效于从给定起点找到迷宫路径。

- Prune

这里的问题在于回溯。如果窗口最大值在边界上，你就没有其他地方可去，会提前终止而没有找到所有可能的峰值。否则，你可能会回溯，导致访问超过O(n)的子数组。 - Nico Schertler

@n.m. 用词不当；我在考虑提前找到已经通过另一条路径找到的峰值。修正中... - Prune

如果没有要找到的k个峰值，这种方法怎么知道在不访问(几乎)每个元素的情况下停止？在最坏情况下，它似乎是O(n^2)，但如果输入通常包含至少k个峰值，则仍然可能是一种实用的解决方案。 - myrtlecat

@NicoSchertler: "提前终止"？首先，边界上没有峰值；矩阵用“-inf”值填充。找到全局最大值不是问题；您正在寻找其他峰值，从其他起点开始。我同意，如果矩阵不包含k个峰值，则此方法将超过O（n）来耗尽所有可能性。 - Prune

恐怕问题不在于措辞不当。“回溯；继续寻找”似乎并不是一个明确定义的建议。具体在哪里继续寻找？如果你只是假装第一个峰值并不是真正的峰值（例如，将其值设置为-inf），那么你新的搜索很可能会返回一些并不是真正的峰值（例如，其中一个邻居）。展示一个算法（我会给你展示它失效的输入）。 - n. m.

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- myrtlecat · Accepted Answer

答案是否定的。如果k > 1，则最坏情况下的性能将是O(n^2)。

问题出在“如果有那么多存在”的部分。当输入包含少于k个顶峰时，我们的算法只有在确信要找到的顶峰不到k个时才能终止。我将证明（如下）只有进行了O(n^2)个相邻元素之间的比较，我们才能确定有< k个顶峰。

证明：

为了确定一个元素肯定不是顶峰，我们必须将其与至少一个邻居进行比较 - 如果邻居恰好更大，则该元素不是顶峰。如果我们尚未将一个元素与任何邻居进行比较，则它仍可能是个山峰，而每次比较最多只能排除一个元素不是峰值。知道我们的输入中有不到k个峰值等价于知道我们至少有n^2-k+1个非峰值，这就需要我们进行至少n^2-k+1次比较，这是O(n^2)。对于k > 1，存在具有<k个峰值的输入，因此在最坏情况下，我们将不得不执行这些O(n^2)次比较才能停止搜索。

注意：

对于k = 1的情况，这个问题不存在，因为每个输入都保证至少有一个峰值。当我们找到第一个山峰时就可以停止搜索，因此我们不必检查是否还有更多的山峰。