28

我最近开始看 MIT 的 6.006 课，在第一课中，讲师介绍了寻峰算法。

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf

根据他的定义：

给定一个数组 [a,b,c,d,e,f,g]，其中 ag 是数字，b 是一个峰值当且仅当 a <= b 且 b>= c。

他给出了递归的方法：

if a[n/2] < a[n/2 -1] then look for a peak from a[1] ... a[n/2 -1]
else if a[n/2] < a[n/2+1] then look for a peak from a[n/2+1] ... a[n]
else a[n/2] is a peak

他说算法是T(n) = T(n/2) + o(1) = o(lgn)

在他的pdf中，他还给出了一个完整的例子：[6,7,4,3,2,1,4,5]

7 和 5 都是峰值。但是上面的算法不是仅仅因为中间元素恰好满足第一个分支而发现 7 作为峰值吗？

  1. 所以如果我们要找到所有的峰，我们还会遍历整个阵列吗？这是否意味着最坏的情况N？

  2. 他的定义是否意味着我们只需要找到一个峰值？

我相信这个问题可以看作是在 Riverst 的算法介绍一书中找到最大和最小元素。

4

5 回答 5

29

是的，这个算法只找到一个峰值。

如果你想找到所有的峰，你必须检查所有的元素，所以它将是 O(n)。

注意：峰值不一定是全局最大值。

于 2013-09-21T12:16:49.343 回答
8

我不太相信这种算法是否是找到有趣峰值的最佳方法。它倾向于在中间元素进行比较，这可能会将搜索推向次优方向，最终算法总是会在边缘而不是中间找到峰值。简单的例子

[1,2,3,4,5,6,7,8] => 峰值为 8

[6,21,7,8,9,10,11,13] => 峰值为 13，而峰值为 21 更有趣

当然，算法保证找到一个峰值，因为它向更高的方向移动，但正如我在示例中所示，峰值可能不是有趣的！

于 2014-06-12T22:23:54.757 回答
5

我昨天刚开始这门课程，问题陈述是：

问题：如果存在峰，则查找它（它总是存在吗？）

因此，该算法所做的只是试图在尽可能短的时间内找到一个峰值，即第一个可用的峰值。

这就是为什么这个算法只能找到一个峰值。

于 2013-11-20T16:57:57.783 回答
0

这个算法看起来很像二分搜索算法。二进制搜索仅适用于已排序的数组，并且这种峰值搜索算法看起来应该与另一个定义一起使用：x[p]如果 for0 <= i < p x[i] <= x[i + 1]和 for是一个峰值p <= i < x.size x[i] >= x[i + 1]。如果我们确定问题中的定义是错误的，而这个定义是正确的：一切都很好。看起来它是错误的，因为它在第二种情况下给出了几个峰值，你是对的。

于 2013-09-21T12:23:43.913 回答
0

我最近也开始研究，这就是我发现的：如果一维数组元素不小于其邻居，则它是一个峰值，对于排序数组，最后一个元素始终是峰值，课程中提供的解决方案是与使用分而治之的二进制搜索非常相似，而且问题还说找到一个峰值，我们可以有多个峰值，但我们需要第一个峰值元素，我们就完成了。

例如，我们有长度为 n 的一维数组：

    DO:
    m = n/2
    neigborLeft = m-1
    neigborRight = m+1
    if neigborLeft >= 0 && a[neigborLeft] > a[m] 
       //recursion with left elements
    else if neigborRight <= n-1 && a[neigborRight] > a[m] 
        //recursion with right elements
     else
       // peak value is a[m]

阅读更多：geeksforgeeks.org/find-a-peak-in-a-given-array/

于 2020-06-11T10:19:39.353 回答