Algorytm ustalania wartości szczytowej

Question

Niedawno zacząłem przeglądać 6.006 wykładów MIT, a na pierwszym wykładzie instruktor przedstawił algorytm wyszukiwania szczytów.

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

Według jego definicji:

Biorąc pod uwagę macierz [a, b, c, d, e, f, g] gdzie Ag numery, b oznacza pik Jeżeli i tylko jeśli < = b i b> = c.

Dał rekurencyjnego:

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ł algorytm T (n) = T (n/2) + f (1) = O (LGN)

W jego pdf podał także 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 wartości szczytowej tylko dlatego, że element środkowy spełnia pierwszą gałąź?

1. Więc jeśli mielibyśmy znaleźć wszystkie szczyty, czy nadal będziemy przechodzić przez całą tablicę? Czy oznaczałoby to najgorszy przypadek N?

2. Czy jego definicja sugeruje, że musimy znaleźć pojedynczy szczyt?

Wierzę, że ten problem może być postrzegany jako znalezienie maksymalnego i minimalnego elementu w książce Wprowadzenie do algorytmu Riversta.

Answer 1

Tak, ten algorytm znajduje tylko pojedynczy pik.

Jeśli chcesz znaleźć wszystkie szczyty musisz sprawdzić wszystkie elementy, więc będzie to O (n).

Uwaga: szczyt nie musi być globalnym maksimum.

Answer 2

Algorytm ten wygląda podobnie do binary search algorithm. Wyszukiwanie binarne działa tylko na posortowanych tablicach, a algorytm wyszukiwania pików wygląda tak, jakby miał działać z inną definicją: x[p] jest szczytem, ​​jeśli dla 0 <= i < px[i] <= x[i + 1] i dla p <= i < x.sizex[i] >= x[i + 1]. Jeśli uznamy, że definicja w pytaniu jest błędna, a ta ma rację: wszystko jest w porządku. I wygląda na to, że jest źle, ponieważ w drugim przypadku daje kilka szczytów, masz rację.

Answer 3

Właśnie zacząłem ten kurs wczoraj i rachunek problemem jest:

Problem: Znajdź szczyt, jeśli istnieje (? Czy zawsze istnieje)

Więc, co algorytm robi jest po prostu próbując znaleźć szczyt, pierwszy dostępny, w jak najmniejszym możliwym czasie.

Dlatego algorytm ten znajduje tylko pojedynczy pik.

Answer 4

Nie jestem do końca przekonany, czy ten algorytm jest najlepszym sposobem na znalezienie interesującego szczytu. Ma tendencję do faworyzowania porównania w środkowym elemencie, co może prowadzić do nieoptymalnego kierunku i ostatecznie algorytm zawsze kończy się znalezieniem szczytu w Krawędziach, a nie w środku. Prosty przykład

[1,2,3,4,5,6,7,8] => szczytowy wynosi 8

[6,21,7,8,9,10,11,13 ] => Szczyt będzie 13, a szczyt 21 jest bardziej interesujący

z pewnością algorytm ma pewność, że znajdzie szczyt, ponieważ porusza się w wyższym kierunku, ale jak pokazałem w przykładzie, szczyt może nie być interesujący !