algorithm - 在 O(n) 时间内找到 n x n 矩阵中的局部最小值

Question

因此，这不是我的家庭作业问题，而是取自 coursera 算法和数据结构类(class)的未评分家庭作业(现已完成)。

给你一个由不同数字组成的 n × n 网格。如果一个数字小于其所有邻居，则该数字是局部最小值。 (一个数字的邻居是紧挨着上面、下面、左边或右边的一个。大多数数字有四个邻居；旁边的数字有三个；四个角有两个。)使用分而治之算法设计在数字对之间仅进行 O(n) 次比较来计算局部最小值的范例。 (注意:由于输入中有 n² 个数字，所以您无法查看所有这些数字。提示:考虑一下哪些类型的递归会为您提供所需的结果上限。)

由于数字没有按任何顺序排列，除了 O(n²) 次比较，我看不出我们还能如何逃脱。

Answer 1

我们可以调整 Words Like Jared 的回答，看看它是如何出错的。

该答案中的想法——这是一个很好的想法——是“滚下坡”。这只是意味着，如果你在一个元素上，检查它是否是局部最小值。如果是这样，你就完成了；否则，步到其最近邻居中的最小者。最终这必须终止，因为每一步都是针对一个较小的元素，并且在有限数组中不能永远持续下去。

这种方法的问题是“滚动”可能到处都是:

20 100 12  11 10 100  2
19 100 13 100  9 100  3
18 100 14 100  8 100  4
17  16 15 100  7   6  5

如果从左上角开始“滚下坡”，您将访问数组中大约一半的元素。那太多了，所以我们必须稍微限制一下。

首先检查中间列和中间行。在所有这些元素中找到最小的元素并从那里开始。

从那里“下坡”滚动一步进入四个象限之一。您将进入其中一个象限，因为中间列和/或行中的相邻元素较大，因此两个相邻象限中只有一个可能是“下坡”。

现在想想如果你从那里“滚下坡”会发生什么。显然，您最终会达到局部最小值。 (我们实际上不会这样做，因为它会花费太长时间。)但是，在滚动的过程中，你永远不会离开那个象限......因为这样做，你必须穿越中间列或中间行，并且这些元素都不小于您开始的位置。因此，该象限在某处包含局部最小值。

因此，在线性时间内，我们确定了一个必须包含局部最小值的象限，并将 n 减半。现在只是递归。

这个算法需要时间 2n + 2n/2 + 2n/4 + ...，等于 4n，也就是 O(n) 所以我们完成了。

有趣的是，除了关键部分:证明算法有效之外，我们根本没有使用“滚下坡”。

[更新]

作为Incassator points out ，这个答案并不完全正确，因为在你“只是递归”之后你可能会再次滚出象限......

最简单的解决方法是在“滚下山”之前找到中间行、中间列、和边界中的最小元素。