algorithm - 寻峰算法

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

根据他的定义:

Given an array [a,b,c,d,e,f,g] where a-g are numbers, b is a peak if and only if a <= b and 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 的 Introduction to Algorithm 一书中找到最大和最小元素。

Answer 1

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

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

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