山顶发现算法 [英] Peak finding algorithm
问题描述
最近，我开始寻找在麻省理工学院的6.006讲座，并在第一次讲座的讲师presented峰值寻找算法。
I recently started looking at MIT's 6.006 lectures and in the first lecture the instructor presented peak-finding algorithm.
<一个href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf">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]，其中股份公司是数字，b是一个峰值 当且仅当一个与所述; = B和B> = C
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.
他给了一个递归的方法：
He gave a recursive approach:
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）= 0（LGN）
He said the algorithm is T(n) = T(n/2) + o(1) = o(lgn)
在他的PDF，他也给了一个完整的示例： [6,7,4,3,2,1,4,5]
In his pdf he also gave a complete example: [6,7,4,3,2,1,4,5]
两者7和5是峰。但不高于只是算法找到7峰值只是因为中间元素恰好满足了第一支？
Both 7 and 5 are peaks. But doesn't the algorithm above only finds 7 as peak just because the middle element happens to satisfy the first branch?
-
因此，如果我们应该找到所有的山峰，那我们仍然可以通过整个数组走？它是否意味着最坏的情况下，N？
So if we were supposed to find all the peaks, would we still be walking through the entire array? Would it mean worst case N?
难道他的定义意味着我们只需要找到一个峰值？
Does his definition implies we just need to find a single peak?
我相信这个问题可以看作是寻找在Riverst引进的最大和最小元素算法的书。
I believe this problem can be viewed as finding the maximum and minimum element in Riverst's Introduction to Algorithm book.
推荐答案
是的，这个算法只发现一个单峰。
Yes, this algorithm only finds a single peak.
如果你想找到的所有的必须检查所有元素，所以这将是澳峰（N）。
If you want to find all the peaks you have to check all the elements, so it's going to be O(n).
注意：峰值不一定是一个全局最大
Note: a peak is not necessarily a global maximum.
这篇关于山顶发现算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
