峰值发现算法

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是数字,当且仅当a <= b且b> = c时,b是峰值.

他给出了递归方法:

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. 所以如果我们应该找到所有的峰值,我们还会走遍整个阵列吗？这是否意味着最坏的情况？

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

我相信这个问题可以被视为在Riverst的算法入门书中找到最大和最小元素.

Answer 1

是的,此算法仅查找单个峰值.

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

注意:峰值不一定是全局最大值.

Answer 2

我不太相信这种算法是否是找到有趣峰值的最佳方法.它倾向于支持中间元素的比较,这可能将搜索推向次优方向,并且最终算法总是最终在Edges而不是中间找到峰值.简单的例子

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

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

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

Answer 3

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

问题：如果存在，请找出一个峰值（它总是存在吗？）

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

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