Niedawno zacząłem przyglądać się 6.006 wykładom MIT, a na pierwszym wykładzie instruktor przedstawił algorytm wyszukiwania pików.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec01.pdf

Zgodnie z jego definicjami:

Biorąc pod uwagę tablicę [a, b, c, d, e, f, g], gdzie a-g są liczbami, b jest szczytem wtedy i tylko wtedy, gdy a <= b i b> = c.

Podał podejście rekurencyjne:

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

Powiedział, że algorytm to T (n) = T (n / 2) + o (1) = o (lgn)

W swoim pdf dał również pełny przykład:[6,7,4,3,2,1,4,5]

Zarówno 7, jak i 5 to szczyty. Ale czy powyższy algorytm nie znajduje tylko 7 jako piku tylko dlatego, że środkowy element spełnia pierwszą gałąź?

Gdybyśmy mieli znaleźć wszystkie szczyty, czy nadal przechodzilibyśmy przez całą macierz? Czy oznaczałoby to najgorszy przypadek N?

Czy jego definicja sugeruje, że musimy znaleźć tylko jeden szczyt?

Uważam, że ten problem można postrzegać jako znalezienie maksymalnego i minimalnego elementu w książce Wprowadzenie do algorytmu Riverst.