找峰算法

Question

我最近开始研究麻省理工学院的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是峰 如果和只有在< = 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的算法导论入门中找到最大和最小元素。

Answer 1

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

如果你想找到所有的峰你必须检查所有的元素，所以它会是O（n）。

注：峰值不一定是全球最大的。

Answer 2

这种算法看起来很相似binary search algorithm。二进制搜索只适用于排序数组，而这个峰值搜索算法看起来像它应该与另一种定义的工作：x[p]是如果0 <= i < px[i] <= x[i + 1]和p <= i < x.sizex[i] >= x[i + 1]峰值。如果我们确定问题中的定义是错误的，而且这是正确的，那么一切都可以。看起来它是错误的，因为它在第二种情况下给出了几个高峰，你是对的。

Answer 3

我昨天刚开始这个过程中，这个问题的说法是：

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

那么，究竟什么算法所作的仅仅是试图在尽可能最短的时间内找到第一个可用的峰值。

这就是为什么这个算法只发现单峰。

Answer 4

我不太相信，如果这算法是找到一个有趣的峰值的最佳途径。它倾向于支持中间元素的比较，这可能会导致搜索不理想的方向，最终算法最终会在边缘而不是中间找到峰值。 简单实例

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

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

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