¿Qué es un algoritmo O (log n) para encontrar un máximo local de una matriz?

Definamos exactamente qué está buscando:

1. La peor complejidad de tiempo de O (log n), donde n es el número de elementos en la matriz.
2. No hay dos elementos iguales en la matriz (esto nos salva de considerar muchos casos especiales)
3. Para encontrar el máximo local que se define como: el número en la matriz es el máximo local si todos sus vecinos (uno o dos) son más pequeños.

Tenga en cuenta que los supuestos 2 y 3 implican que hay al menos un máximo local.

Puede resolver este problema dividiendo y conquistando el enfoque. Elija elemento en el medio. Consideremos todos los casos:

• ¿En qué secuencia se debe aprender la estructura de datos, el algoritmo y las matemáticas discretas?
• ¿De qué se trata exactamente la conjetura P / NP? ¿Por qué es tan importante demostrarlo?
• ¿Cuáles son los fundamentos matemáticos de la inteligencia artificial?
• ¿Por qué es P vs NP un problema importante para resolver?
• ¿Hay algún trabajo para estudiantes de informática teórica?

1. Es local máximo. Terminamos el algoritmo.
2. El elemento del lado izquierdo es más grande.
3. El elemento del lado derecho es más grande.

Tenga en cuenta que los casos número 2 y 3 no son mutuamente excluyentes. Considérelo como una declaración de cambio -> elija primero lo que se aplique a su situación.

Sin pérdida de generalidad, digamos que terminamos en el caso número 3 (el número 2 se puede resolver de la misma manera, pero los lados son opuestos). ¿Qué significa que en nuestro lado derecho hay un elemento más grande? Que tal vez ese elemento es el máximo local. O no, pero el siguiente es el máximo local. No lo sabemos Pero lo que sabemos con certeza es que en el lado derecho de este elemento podemos encontrar el máximo local. Eso es todo lo que necesitamos. Continuaremos con el mismo algoritmo, pero esta vez elegimos el elemento en medio del intervalo en nuestro lado derecho.

Ahora podemos preguntar, ¿cuál es la complejidad de este algoritmo? Si imagina una función recursiva que resolvería este problema, tendría 2 parámetros: el lado izquierdo del intervalo considerado y el lado derecho. En cada iteración encontramos la respuesta o reducimos a la mitad este intervalo. Entonces, el peor de los casos es que dividiremos a la mitad el intervalo tantas veces como sea posible. Pero, ¿cuántas veces puedes reducir a la mitad el intervalo que inicialmente es largo n unidades? Solo log (n) veces.

Este algoritmo resuelve su problema en el peor de los casos O (log n). Espero que esta respuesta te haya ayudado.