Algoritmo eficiente para encontrar el máximo de una secuencia unimodal

Question

Tenemos $a_{1}<a_{2}<\dots <a_{p}$ y $a_p > a_{p+1}>\dots>a_{n}$ . Queremos encontrar el elemento máximo $a_{p}$ de una secuencia unimodal leyendo el menor número de elementos posible.

Quiero hacer un algoritmo que resuelva este problema y encontrar su tiempo de ejecución. Asumo que la secuencia ya está en memoria por lo que para acceder a un elemento se necesita $(1)$ tiempo.

¿Puede alguien ayudarme con ello?

Una secuencia $A = (a_{1} a_{2} \dots a_{n})$ es unimodal si existe tal $p$ , $1\leq p \leq n$ .

Agradeceré los enlaces para un mayor estudio.

Answer 1

Si comparas dos elementos vecinos, puedes averiguar si estás en la parte creciente o decreciente de la secuencia. Ahora utiliza la búsqueda binaria para encontrar el vértice.

---

Con más detalle: Desde el principio sabemos que el índice del vértice se encuentra en algún lugar entre $L=\frac 12$ y $H=n+\frac 12$ donde las letras significan límites bajos y altos. Utilizaré los límites de medio entero para facilitar la exposición; en una implementación práctica los representarías con, por ejemplo, el siguiente entero mayor.

Ahora, si sucede que $H-L=1$ entonces sabemos exactamente dónde está el vértice. El índice del vértice es, por supuesto, un entero, y lo habremos puesto entre corchetes con el medio entero que está por encima y por debajo. Así que en ese caso hemos terminado.

En caso contrario, deja que $M$ sea un semi-integro aproximadamente a medio camino entre $H$ y $L$ -- es decir, o bien $\frac{H+L}{2}$ o $\frac{H+L+1}{2}$ , de tal manera que $M$ es un número entero más $\frac 12$ . Ahora comparamos los dos elementos vecinos $a_{M-\frac 12}$ y $a_{M+\frac 12}$ . Si el primero es mayor, el vértice debe estar entre $L$ y $M$ ; de lo contrario, el vértice se encuentra entre $M$ y $H$ . Por lo tanto, podemos sustituir $L$ o $H$ con $M$ y empezar de nuevo desde el párrafo anterior.

Cada vez que repetimos el bucle, la distancia entre $H$ y $L$ habrá disminuido, por lo que $H-L$ acabará llegando a $1$ el algoritmo termina. De hecho, $H-L$ será aproximadamente reducir a la mitad cada vez que hemos hecho una comparación, por lo que el número de iteraciones será de alrededor de $\log_2 n$ . Esto significa que el número de accesos al array es $2 \log_2 n$ lo que supone una gran mejora con respecto a una exploración lineal.

Se puede mejorar ligeramente con el algoritmo más complicado sugerido por Tony K, pero esto no afectará al asintótica (big-O) del algoritmo.

Answer 2

Editado para añadir: Acabo de descubrir que mi idea no es nueva. Esta página de Wikipedia describe la "búsqueda de la sección áurea" para las funciones unimodales.

---

No es probable que la búsqueda binaria ofrezca el mejor comportamiento en el peor de los casos. Sospecho que el algoritmo más rápido (con el menor número de accesos a la matriz en el peor de los casos) implica la proporción áurea $\varphi = (1 + \sqrt 5)/2$ . Podemos converger a la respuesta reduciendo el intervalo que la contiene en un factor de $\varphi$ para cada acceso a la matriz. A grandes rasgos (sin tener en cuenta el redondeo de los índices de las matrices a números enteros):

Comience con $lo = 1, hi = n$ y $x_0 = n / \varphi$ .

Entonces tenemos $p_{lo} < p_{x_0}$ y $p_{x_0} > p_{hi},$ y la relación de las longitudes de los dos subintervalos es $\varphi$ . Llama a estos dos subintervalos $L_0$ y $S_0$ (largo y corto). Ahora itera como sigue:

Elija el índice de la matriz $x$ para dividir $L_r$ en dos subintervalos con longitudes en la proporción $\varphi$ a $1$ para que el más corto de los dos nuevos subintervalos sea adyacente a $S_r$ . A continuación, establezca $S_{r+1}$ para que sea este intervalo más corto; y establecer $L_{r+1}$ para ser $S_r$ o el más largo de los nuevos subintervalos, según $p_x$ es mayor o menor que $p_{x_r}$ . Entonces $x_{r+1}$ será $x_r$ (en el primer caso) o $x$ (en el segundo caso). Debido a las propiedades de $\varphi$ , $L_{r+1}$ tiene la misma longitud que $S_r$ en cualquier caso.

No estoy afirmando que este algoritmo sea más rápido en el mundo real que la búsqueda binaria. Hay demasiados detalles complicados de entender. Pero creo que requiere menos accesos a la matriz (que cualquier otro algoritmo) en el peor de los casos.

Answer 3

La respuesta de Henning Makholm recuerda el concepto de búsqueda binaria en la "derivada" de una función, que en una secuencia discreta es la diferencia entre dos valores vecinos. En el caso de una función continua, o quizá de una que la obtención de vecinos sea costosa, existe un método más sencillo que la búsqueda de Fibonacci, llamado búsqueda ternaria .

En esencia, considera 3 intervalos. Llama a 2 puntos $m_1,m_2$ entre los límites del intervalo $l$ y $h$ tal que $l<m_1<m_2<h$ . Si $f(m_1)<f(m_2)$ el máximo no puede estar en $[l,m_1]$ por lo que la búsqueda se repite en el intervalo $[m_1,h]$ . Por simetría, si $f(m_1)>f(m_2)$ la búsqueda se repite en $[l,m_2]$ . Wikipedia señala que si $f(m_1)=f(m_2)$ la búsqueda puede repetirse en $[m_1,m_2]$ o ser considerado en uno de los dos casos anteriores. La búsqueda termina cuando el intervalo está dentro de un tamaño máximo deseado ( $1$ en el caso de una secuencia discreta).