在O（n）时间中找到nxn矩阵中的局部最小值
因此，这不是我的家庭作业问题，而是取自有关算法和数据结构的课程课程的未分级作业（现已完成）。
您会得到一个n×n的不同数字网格。如果数字小于其所有邻居的数字，则该数字是本地最小值。（一个数字的邻居是一个在上，下，左或右的数字。大多数数字有四个邻居；侧面的数字有三个；四个角有两个。）使用分治算法设计仅用数对之间的O（n ）比较来计算局部最小值的范例。（注意：由于输入中有 n 2个数字，因此您无法查看所有这些数字。提示：请考虑哪种类型的重复会给您所需的上限。）
由于数字不是按任何顺序排列的，所以除了O（ n 2）比较之外，我看不到其他方法。
回答：
通过查看它可能出错的方式，我们可以像贾里德的答案那样改编单词。
答案中的一个主意是“滚下坡路”，这是一个好主意。这只是意味着，如果您在元素上，请检查它是否是局部最小值。如果是这样，那么您就完成了；否则，请移至与其最近的邻居中的最小邻居。最终，这必须终止，因为每一步都是针对较小的元素，并且不能永远在有限的数组中进行。
这种方法的问题在于，“滚动”会在各处蔓延：
20 100 12 11 10 100 219 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指出的那样，这个答案并不完全正确，因为在您“递归”之后，您可能会再次退出象限…
最简单的解决方法是在“下坡”之前找到中间行，中间列 和边界 中的最小元素。
以上是 在O（n）时间中找到nxn矩阵中的局部最小值 的全部内容， 来源链接： utcz.com/qa/423561.html
