查找的N×n矩阵当地最低为O（n）时间 [英] Find local minimum in n x n matrix in O(n) time

问题描述

所以，这不是我的家庭作业的问题，但它是从对算法和数据结构的coursera当然是一个不定级作业（也就是现在的完成）。

So, this is not my home work question, but it is taken from an ungraded homework of the coursera course on algorithms and data structures (which is now complete).

您将得到一个N的不同数字的n个网格。一个数字是局部最小值，如果它比所有的邻居小。 （一些邻居是一出，立即上方，下方，左侧或最右边的数字有四个邻国;就在旁边的数字有三个，四个角落有两个。）使用分而治之的算法设计范式来计算当地最低只有O（ N 的）对数之间的比较。 （注：由于存在的 N 的 ² 输入号码，你不能看所有这些提示：想想什么类型的复发会给你想要的上界。）

You are given an n by n grid of distinct numbers. A number is a local minimum if it is smaller than all of its neighbors. (A neighbor of a number is one immediately above, below, to the left, or the right. Most numbers have four neighbors; numbers on the side have three; the four corners have two.) Use the divide-and-conquer algorithm design paradigm to compute a local minimum with only O(n) comparisons between pairs of numbers. (Note: since there are n² numbers in the input, you cannot afford to look at all of them. Hint: Think about what types of recurrences would give you the desired upper bound.)

由于号码不以任何顺序，我看不出我们如何能逃脱任何东西，但O（ N 的 ² ）进行比较。

Since the numbers are not in any order, I don't see how we can get away with any thing but O(n²) comparisons.

推荐答案

我们能够适应的话犹如Jared的回答，看它如何去错。

We can adapt Words Like Jared's answer, by looking at how it can go wrong.

在这个问题的答案的想法 - 这是一个很好的 - 就是滚下坡。这也就意味着，如果你是一个元素，检查它是否是一个局部最小值。如果是这样，你做;否则，一步中最小的其最近的邻居。最终，这必须终止，因为每一步都是一个更小的元素，并不能永远持续下去在有限的数组。

The idea in that answer -- which is a good one -- is to "roll downhill". This just means, if you are on an element, check if it is a local minimum. If so, you are done; otherwise, step to the smallest of its nearest neighbors. Eventually this must terminate because every step is to a smaller element, and that cannot go on forever in a finite array.

使用这种方法的问题是，滚动可以蜿蜒所有的地方：

The problem with this approach is that the "rolling" can meander all over the place:

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

如果你开始在左上角，滚下坡，您将参观大约一半的数组中的元素。这实在是太多了，所以我们必须将它限制了一下。

If you start at the upper left and "roll downhill", you will visit around half of the elements in the array. That is too many, so we have to constrain it a bit.

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

Start by examining the middle column and middle row. Find the smallest element among all of those and start there.

滚动一名来自那里一步下坡，进入四个象限中的一个。就会进入象限之一，因为在中间列和/或行中的相邻的元件都较大，所以仅一个相邻的两个象限中可以是下坡

Roll one step "downhill" from there to enter one of the four quadrants. You will enter one of the quadrants, because the adjacent elements in the middle column and/or row are larger, so only one of the two adjacent quadrants could be "downhill".

现在考虑，如果你从那里滚下山会发生什么。很明显，你最终会达到一个局部极小。 （我们不会真正做到这一点，因为这会花费太长的时间。）但是，在滚来滚去的过程中，你永远不会离开该象限......因为这样做，你就必须跨越无论是中间一列或中间行，没有这些元素的比你开始的地方小。因此该象限包含一个局部最小值的某个地方。

Now consider what would happen if you "rolled downhill" from there. Obviously, you would eventually reach a local minimum. (We will not actually do this because it would take too long.) But, in the course of rolling around, you would never leave that quadrant... Because to do so, you would have to cross either the middle column or middle row, and none of those elements are smaller than where you started. Therefore that quadrant contains a local minimum somewhere.

因此​​，在直线的时候，我们已经确定，必须包含当地最低象限，我们已经削减氮的一半。现在只要递归。

Thus, in linear time, we have identified a quadrant that must contain a local minimum, and we have cut n in half. Now just recurse.

该算法的时间2N + 2N / 2 + 2N / 4 + ......，相当于4N，这是O（n），所以我们正在做的。

This algorithm takes time 2n + 2n/2 + 2n/4 + ..., which equals 4n, which is O(n) so we are done.

有趣的是，我们并没有使用滚下坡非常可言，除了关键的部分：证明，该方法适用

Interestingly, we did not use "rolling downhill" very much at all, except for the critical part: Proving that the algorithm works.

[更新]

由于 Incassator指出，这个答案是不完全正确的，因为在你只是递归你可能会推出再次的象限......

As Incassator points out, this answer is not entirely correct, because after you "just recurse" you might roll out of the quadrant again...

最简单的解决办法是找到中间行中最小的元素，中间一列，和边界的，然后滚下坡。

The simplest fix is to find the smallest element among the middle row, middle column, and boundary before you "roll downhill".

这篇关于查找的N×n矩阵当地最低为O（n）时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！