在O(n)时间中找到nxn矩阵中的局部最小值

在O(n)时间中找到nxn矩阵中的局部最小值,第1张

在O(n)时间中找到nxn矩阵中的局部最小值

通过查看它可能出错的方式,我们可以像贾里德的答案那样改编单词。

答案中的一个主意是“滚下坡路”,这是一个好主意。这只是意味着,如果您在元素上,请检查它是否是局部最小值。如果是这样,那么您就完成了;否则,请移至与其最近的邻居中的最小邻居。最终,这必须终止,因为每一步都是针对较小的元素,并且不能永远在有限的数组中进行。

这种方法的问题在于,“滚动”会在各处蔓延:

20 100 12  11 10 100  219 100 13 100  9 100  318 100 14 100  8 100  417  16 15 100  7   6  5

如果从左上方开始并“下坡”,您将访问数组中大约一半的元素。太多了,因此我们必须对其加以限制。

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

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

现在考虑如果您从那里“下坡”会发生什么。显然,您最终将达到本地最低要求。(我们实际上不会这样做,因为它会花费太长时间。) 但是
,在滚动过程中,您永远不会离开该象限…因为这样做,您将不得不越过中间列或中间行,这些元素都不比您开始的地方小。因此,该象限在某处包含局部最小值。

因此,在线性时间内,我们确定了必须包含局部最小值的象限,并且将n切成两半。现在只需递归即可。

该算法需要2n + 2n / 2 + 2n / 4 + …的时间,等于4n,即O(n),所以我们完成了。

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

[更新]

正如Incassator指出的那样,这个答案并不完全正确,因为在您“递归”之后,您可能会再次退出象限…

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



欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5674165.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存