Encuentra el elemento menos en una matriz, que tiene un patrón

Question

Se da una matriz tal que el valor de su elemento aumenta desde el 0 ° índice a través de algún índice (k -1). En k el valor es mínimo y de nuevo comienza a aumentar a través del elemento n th. Encuentra el elemento mínimo.

Básicamente, es una lista ordenada adjunta a otra; ejemplo: (1, 2, 3, 4, , 1, 2, 3).

He intentado con todo tipo de algoritmos, como buliding min-heap, quick select o simplemente plain transversales. Pero no puedo obtenerlo debajo de O (n). Pero hay un patrón en este conjunto, algo que sugiere que el tipo de búsqueda binaria debería ser posible, y la complejidad debería ser algo así como O (log n), pero no puedo encontrar nada. ¿Pensamientos?

Gracias

Answer 1

No La caída puede estar en cualquier lugar, no hay estructura para esto.

Considere los extremos

1234567890 
9
1234056789 
1357024689 

Se reduce a encontrar el elemento mínimo.

Answer 2

Haga una búsqueda binaria amplia para un rango decreciente, con una superposición de un elemento en las divisiones binarias. En otras palabras, si usted tenía, digamos, 17 elementos, se comparan los elementos

0,8 
8,16 
0,4 
4,8 
8,12 
12,16 
0,2 
2,4 

etc., en busca de un caso en el que el elemento de la izquierda es mayor que la derecha.

Una vez que encuentre dicho rango, recurse, haciendo la misma búsqueda binaria dentro de ese rango. Repite hasta que encuentres el par adyacente decreciente.

La complejidad promedio no es inferior a O (log n), con el peor caso de O (n). ¿Alguien puede obtener una estimación de complejidad promedio más ajustada? Parece aproximadamente "a medio camino entre" O (log n) y O (n), pero no veo cómo evaluarlo. También depende de cualquier restricción adicional en los rangos de valores y el tamaño del incremento de un miembro al siguiente.

Si el incremento entre elementos es siempre 1, hay una solución O (log n).

Answer 3

No se puede hacer en menos de O (n).

El peor de los casos de este tipo nos mantendrá siempre preocupante -

una lista cada vez mayor a1, a2, a3 .... ak, ak + 1 ... un

con sólo una desviación ak < ak-1, por ejemplo 1,2,3,4,5,6,4,7,8,9,10

Y todos los demás números mantienen absolutamente ninguna información sobre el valor de 'k' o 'ak'

Answer 4

La solución más simple es solo mirar hacia delante a través de la lista hasta que el siguiente valor sea menor que el actual, o hacia atrás para encontrar un valor que sea mayor que el actual. Eso es O (n).

Hacer ambos simultáneamente todavía sería O (n) pero el tiempo de ejecución probablemente sería más rápido (dependiendo de factores complicados de procesador/caché).

No creo que pueda obtenerlo mucho más rápido de forma algorítmica que O (n) ya que muchos de los algoritmos de búsqueda de división y conquista dependen de tener un conjunto de datos ordenados.