¿Cuál es la forma más eficiente para encontrar el par más separado en una secuencia finita tal que el primero es mayor que el segundo?

Question

¿Dada cierta secuencia finita $a_n$ $n \in {1..N}$, hay un método más eficiente para resolver (P1) que el método de fuerza bruta de O($N^2$)?

($P1$) maximizar $n_2-n1$ tal que $a{n1}>a{n_2}$

Answer 1

Esto es $O(N)$.

Si $a_n$ es mayor que todos los elementos antes, llamar a un pico; y si $a_n$ es menor que todos los elementos después de que en un comedero.

Entonces si $(a_i,a_j)$ es un máximo separados par de satisfacciones $a_i>a_j$, sabemos que $a_i$ debe ser un pico (de lo contrario no sería un elemento anterior $a_k$ tal que $a_k>a_j$); y de manera similar, $a_j$ debe ser un comedero.

Así que aquí está el algoritmo:

1. Exploración hacia adelante a través de la secuencia de marcado de todos los picos ($N$ pasos).
2. Explorar hacia atrás a través de la secuencia, marcando todos los comederos ($N$ pasos).
3. Set $p = 1$ (este es el pico de índice). Tenga en cuenta que $a_1$ es un pico por definición.
4. Set $t$ (el comedero índice) para ser el índice del último canal tal que $a_t < a_p$.
5. Ahora $t-p$ es un candidato para la separación máxima; si es el mejor sin embargo, recuerde.
6. Si hemos escaneado todos los picos, hemos terminado. De lo contrario, establezca $p$ a ser el índice de la siguiente pico y vaya al Paso 4.

Tenga en cuenta que podemos iniciar el análisis en el Paso 4 el valor de $t$ en la iteración anterior, por lo que el número total de operaciones de utilizado por los que paso en el algoritmo es $O(N)$.

Editado para añadir: De hecho, podemos omitir el Paso 1, y con tan solo escanear el siguiente pico en el Paso 6. (No podemos omitir el Paso 2, ya que la digitalización de los comederos que se ha hecho al revés.)

Answer 2

Yo creo que se puede hacer esto en $O(N \log N)$, pero puede haber una manera más rápida. Aquí es un alto nivel de descripción del algoritmo:

1. La tienda de los elementos como de las tuplas de $(value, index)$ donde $value$ es el valor del elemento y el índice es su posición en la matriz original. Así, por ej. si su entrada fue [3, 1, 4, 2], se almacenaría como [(3,0), (1,1), (4,2), (2,3)]. Este va a ser $O(N)$
2. Ordenar esta nueva matriz por el primer elemento (valor de campo) en la tupla en orden decreciente. Así el ejemplo anterior podría verse como: [(4, 2), (3, 0), (2, 3), (1, 1)]. Esto se puede hacer en $O(N\log N)$
3. Encontrar la diferencia máxima entre el segundo de los elementos (campos de índice) de las tuplas tales que el mayor se produce después de que el más pequeño de la nueva matriz. Esto se puede hacer en $O(N)$.

Total de complejidad = $O(N \log N)$.

Creo que los pasos a $1$ $2$ son bastante auto explicativo. Si eres curioso acerca de cómo paso a $3$ se puede hacer en $O(N)$, aquí está el código:

def max_diff_indexes(arr):
    """
    @params:

        arr - This is just an array of the SECOND parts of the tuple in 
        the algorithm described above. That is, arr contains only ints 
        representing the second values of the tuple (index field) after 
        the sorting in step 2. 

    @return:

        max_pair - Returns a pair of indexes n_1 and n_2 that maximise 
        n_2 - n_1 such that a_{n_1} > a_{n_2}. The first property is 
        ensured by this algorithm while the second property in ensured
        by the fact that the array was initally sorted in decresing order
        of value

    """
    if not arr: return None
    min_val = arr[0]
    max_diff = 0
    for elem in arr:
        max_diff = max(elem - min_val, max_diff)
        min_val = min(elem, min_val)

    max_val = max_diff - min_val
    return min_val, max_val         

Answer 3

Bien, me llevó a una grieta en mí mismo y me encontré con el siguiente enfoque que parece ser $O\big( (N/M)^2 + N \log(N) \big)$ donde $M$ es el valor óptimo de (P1).

Bucle de la siguiente$k$$1,2,\dots$:

• Partición de la secuencia en $2^k$ secuencias contiguas de tamaño en la mayoría de las $\lceil N 2^{-k} \rceil $.
• Encontrar cada uno de los locales del grupo de los mínimos y máximos, el ahorro de los índices así.
• Realizar esta búsqueda de fuerza bruta entre los locales máximos / mínimos para encontrar el mejor $n_1$ $n_2$ pertenecientes a los diferentes grupos de
• si $n_2-n_1 > N 2^{-k}$, de salir de este bucle y volver a esta pareja, ya que no hay mejor pareja puede ser encontrado dentro de un mismo grupo de subdivisión más

Cada una de las $k$th iteración requiere: $O\big( N+ 4^k\big)$ operaciones, por ello la suma sobre todos los necesarios $k$ da la total complejidad de la $O\big((N/M)^2 + N \log(N) \big)$, donde el ex término domina para las pequeñas $M$ y los últimos términos domina por $M \gtrsim \sqrt{N}$.