Алгоритм поиска пиков MIT OCW 6.006 - существует ли он всегда? - PullRequest
Новая
       4

Алгоритм поиска пиков MIT OCW 6.006 - существует ли он всегда?

1 голос
/ 09 января 2020

На этой неделе я начал читать лекции MIT OCW 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

Согласно его определениям:

[ab c defghi]
1 2 3 4 5 6 7 8 9
ai являются числами

Позиция 2 является Пик тогда и только тогда, когда b ≥ a и b ≥ c. Позиция 9 является пиком, если i ≥ h

Он предлагает этот алгоритм для повышения его сложности: 

If a[n/2] < a[n/2 − 1] then only look at left half 1 . . . n/2 − − − 1 to look for peak
• Else if a[n/2] < a[n/2 + 1] then only look at right half n/2 + 1 . . . n to look for peak
• Else n/2 position is a peak: WHY?
    a[n/2] ≥ a[n/2 − 1]
    a[n/2] ≥ a[n/2 + 1]

Однако, что если у меня есть этот пример массива:

[9,8,7,6,5,2,3,1]

Алгоритм будет работать так:

Шаг 1: a [n / 2] 6 <7? -> да, посмотрите на левую половину [9,8,7,6]
Шаг 2: a [n / 2] 8 <9? -> да, посмотрите на левую половину [9,8]
Шаг 3: ???

Не будет найдено ни одного пика, хотя есть пик: [9,8,7 , 6,5,2, 3 , 1]

Думаю, я что-то упустил, но не понял. Кто-то может объяснить мне, почему он не работает?

Я нашел этот связанный вопрос, но не ответил: Алгоритм поиска пиков

1 Ответ

0 голосов
/ 13 марта 2020

Вы должны рассмотреть граничное условие самостоятельно.
Здесь завершено Шаги: 

Step 1: a[n/2] < a[n/2-1]? --> 6 < 7? --> yes, look at left half [9,8,7,6]
Step 2: a[n/2] < a[n/2-1]? --> 8 < 9? --> yes, look at left half [9,8]
Step 3: ??? <br>
//if you put a check on boundary condition then
Step 3: a[n/2] > a[n/2+1]? --> 9 > 8? --> yes, look at right half [8]
Step 4: loop terminates as only one element is left(it is a peak)

Вы можете найти лучшее описание проблемы здесь .

...