horspool - boyer-moore algorithm
Algoritmo de búsqueda de picos (4)
Acabo de comenzar este curso ayer, y la declaración del problema es:
Problema: encuentra un pico si existe (¿Existe siempre?)
Entonces, lo que hace el algoritmo es simplemente intentar encontrar un pico, el primero disponible, en el menor tiempo posible.
Es por eso que este algoritmo encuentra un solo pico.
Hace poco empecé a mirar las 6.006 conferencias del MIT y en la primera conferencia el instructor presentó el algoritmo de búsqueda de picos.
Según sus definiciones:
Dada una matriz [a, b, c, d, e, f, g] donde ag son números, b es un pico si y solo si a <= b y b> = c.
Dio un enfoque recursivo:
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
Dijo que el algoritmo es T (n) = T (n / 2) + o (1) = o (lgn)
En su pdf también dio un ejemplo completo: [6,7,4,3,2,1,4,5]
Tanto el 7 como el 5 son picos. Pero, ¿el algoritmo anterior no encuentra el pico 7 solo porque el elemento del medio satisface la primera rama?
Entonces, si tuviéramos que encontrar todos los picos, ¿seguiríamos caminando a través de toda la serie? ¿Significaría el peor de los casos N?
¿Su definición implica que solo necesitamos encontrar un solo pico?
Creo que este problema se puede ver como encontrar el elemento máximo y mínimo en el libro Introducción al algoritmo de Riverst.
Este algoritmo se parece bastante al algoritmo de búsqueda binario . La búsqueda binaria solo funciona en matrices ordenadas, y este algoritmo de búsqueda de picos parece que se supone que funciona con otra definición: x[p] es un pico si para 0 <= i < p x[i] <= x[i + 1] y para p <= i < x.size x[i] >= x[i + 1] . Si decidimos que la definición en la pregunta es incorrecta, y esta es correcta: todo está bien. Y parece que está mal, porque da varios picos en el segundo caso, tienes razón.
No estoy del todo convencido de si este algoritmo es la mejor manera de encontrar un pico interesante. Tiende a favorecer la comparación en el elemento central que podría conducir la búsqueda a una dirección subóptima y, finalmente, el algoritmo siempre terminaría en la búsqueda de un pico en los bordes y no en el medio. Ejemplo simple
[1,2,3,4,5,6,7,8] => El pico sería 8
[6,21,7,8,9,10,11,13] => El pico sería 13, mientras que el pico de 21 es más interesante
seguro, el algoritmo está garantizado para encontrar un pico porque se mueve en una dirección más alta, pero como muestro en el ejemplo, ¡el pico puede no ser el interesante!
Sí, este algoritmo solo encuentra un solo pico.
Si desea encontrar todos los picos, debe verificar todos los elementos, por lo que será O (n).
Nota: un pico no es necesariamente un máximo global.