找峰算法

Question

给定一个数组[a,b,c,d,e,f,G],其中a-g是数,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]

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

我相信这个问题可以看作是在Riverst算法入门书中寻找最大和最小元素。

Answer 1

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

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

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