0

我们有一个 n×n 网格，左下角的坐标为 (0,0)，右上角的坐标为 (n,n)。网格中的单元格都有不同的值，我们的目标是找到一个局部峰值，它被定义为一个单元格的值大于它的左、右、上、下邻居（即对角相邻的单元格没有事情）。

问题是，我们只能通过访问该单元格来查看该单元格的值（即，如果不先采取 (i+j) 步从 (0,0) 到达那里，我们就无法检查 (i,j) 的值） ）。我们如何在 O(n) 步中找到局部峰值？

4

1 回答 1

0

它可以使用分而治之的策略在 O(nlgn) 时间内计算。这比 O(n^2) 时间复杂度类中包含的蛮力算法略好一些。

我在谷歌上找到了这个pdf。希望它会有所帮助。

使用分而治之的局部最大值

于 2016-03-01T16:30:52.803 回答