Недавно я начал изучать лекции MIT 6.006, и в первой лекции преподаватель представил алгоритм поиска пиков.
Согласно его определениям:
Учитывая массив [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]
Оба 7 и 5 являются пиками. Но разве вышеприведенный алгоритм не находит только 7 как пик только потому, что средний элемент удовлетворяет первой ветки?
-
Итак, если мы должны были найти все вершины, мы все равно будем проходить через весь массив? Это будет означать худший случай N?
-
Имеет ли смысл его определение, нам просто нужно найти единственный пик?
Я считаю, что эту проблему можно рассматривать как поиск элемента максимума и минимума в книге Riverst Introduction to Algorithm book.
