Puede encontrar el problema aquí Dividiendo y conquistando la plaza en el artículo DIVIDIENDO Y CONQUISTANDO EL CUADRADO por Donna C Llewellyn y Craig A Tovey 10 de marzo de 1990
Explican un enfoque de divide y vencerás que resuelve el problema utilizando consultas 2.554n.
Llegar a 3n + 4log n es algo fácil:
- En entrevistas tecnológicas, ¿cómo podemos escribir un código que sea limpio, conciso, optimizado en tiempo y espacio y que cubra todos los casos básicos y de borde de una vez?
- Soy por naturaleza un pensador analítico lento y solucionador de problemas. ¿De todos modos puedo pasar una entrevista de programación?
- Mañana tengo una entrevista para un puesto de ingeniero integrado (ver descripción). ¿Qué preguntas puedo esperar en general y en el aspecto técnico?
- ¿Conoces casos en los que alguien consiguió un trabajo de programación sin una entrevista técnica?
- ¿Cuáles son las mejores preguntas que hacen los entrevistadores en la entrevista relacionada con C, si va a realizar una entrevista de la compañía 5-6 CTC?
Consulta todos los elementos en la columna central. Encuentre el mínimo en esta columna, observe que sus dos vecinos horizontales se repiten en la mitad de la matriz que contiene el más pequeño de los dos vecinos. Luego haga lo mismo después de consultar la fila del medio. En n + 2 + n / 2 + 2 pasos, hemos reducido el problema de un tamaño nxn a uno n / 2xn / 2. El número total de consultas será 3n + 4 log n.
La intuición detrás de por qué esto funciona me vino del algoritmo de descenso más empinado que busca un mínimo local.
En cada punto, mantenemos la mitad del problema que contiene el elemento mínimo que hemos visto hasta ahora. Ese elemento puede ser un mínimo local, o uno de sus vecinos puede ser más pequeño que él, pero la ruta de acceso a un elemento más pequeño siempre estará en la mitad que hayamos elegido porque todos los elementos en el borde son más grandes.