arrays - suma - ¿Hay un algoritmo O(n) para generar una matriz prefix-less para una matriz entera positiva?

suma de filas y columnas de una matriz en c++

Question

Para la matriz [4, 3, 5, 1, 2], llamamos prefijo de 4 es NULL, prefix-less de 4 es 0; el prefijo de 3 es [4], prefijo-menos de 3 es 0, porque ninguno en el prefijo es menor que 3; el prefijo de 5 es [4,3], prefijo-menos de 5 es 2, porque 4 y 3 son ambos menores que 5; el prefijo de 1 es [4,3,5], prefijo-menos de 1 es 0, porque ninguno en el prefijo es menor que 1; el prefijo de 2 es [4,3,5,1], prefijo-menos de 2 es 1, porque solo 1 es menor que 2

Entonces, para el arreglo [4, 3, 5, 1, 2], obtenemos un prefijo sin prefijo de [0,0, 2,0,1], ¿Podemos obtener un algoritmo O (n) para obtener un arreglo sin prefijo?

Answer 1

No se puede hacer en O(n) por las mismas razones por las que una clasificación de comparación requiere comparaciones O(n log n) . La cantidad de arreglos posibles sin prefijo es n! por lo que necesita al menos log2(n!) bits de información para identificar la matriz correcta sin prefijo. log2(n!) es O(n log n) , por la aproximación de Stirling .

Answer 2

Creo que esto debería funcionar, pero revisa los detalles. Llamemos a un elemento en la matriz original a [i] y uno en la matriz de prefijos como p [i], donde i es el elemento i-ésimo de las matrices respectivas.

Entonces, digamos que estamos en a [i] y ya hemos calculado el valor de p [i]. Hay tres casos posibles. Si a [i] == a [i + 1], entonces p [i] == p [i + 1]. Si a [i] <a [i + 1], entonces p [i + 1]> = p [i] + 1. Esto nos deja con el caso donde a [i]> a [i + 1]. En esta situación, sabemos que p [i + 1]> = p [i].

En el caso ingenuo, volvemos a través del prefijo y comenzamos a contar elementos menos de un [i]. Sin embargo, podemos hacerlo mejor que eso. Primero, reconozca que el valor mínimo para p [i] es 0 y el máximo es i. A continuación, observe el caso de un índice j, donde i> j. Si a [i]> = a [j], entonces p [i]> = p [j]. Si a [i] <a [j], entonces p [i] <= p [j] + j. Entonces, podemos comenzar a retroceder p actualizando los valores para p [i] _min yp [i] _max. Si p [i] _min es igual a p [i] _max, entonces tenemos nuestra solución.

Haciendo un reverso del análisis de la envolvente del algoritmo, tiene O (n) el mejor rendimiento de caso. Este es el caso donde la lista ya está ordenada. El peor caso es donde se revierte ordenado. Entonces el rendimiento es O (n ^ 2). El rendimiento promedio va a ser O (k * n) donde k es cuánto necesita retroceder. Mi suposición es que para enteros aleatoriamente distribuidos, k será pequeño.

También estoy bastante seguro de que habría formas de optimizar este algoritmo para casos de datos parcialmente ordenados. Me gustaría ver en Timsort algo de inspiración sobre cómo hacer esto. Utiliza la detección de ejecución para detectar datos parcialmente ordenados. Entonces la idea básica para el algoritmo sería ir a través de la lista una vez y buscar corridas de datos. Para las corridas de datos ascendentes, tendrá el caso donde p [i + 1] = p [i] +1. Para ejecuciones descendentes, p [i] = p_run [0] donde p_run es el primer elemento en la ejecución.

Answer 3

Suponiendo que los elementos de entrada sean siempre enteros de ancho fijo, puede usar una técnica basada en la ordenación de radix para lograr el tiempo lineal:

• L es la matriz de entrada
• X es la lista de índices de L en foco para el pase actual
• n es el bit en el que estamos trabajando actualmente
• Count es la cantidad de 0 bits en el bit n que queda de la ubicación actual
• Y es la lista de índices de una subsecuencia de L para la recursión
• P es una matriz inicializada cero que es la salida (la matriz sin prefijos)

En pseudo-código ...

Def PrefixLess(L, X, n)
    if (n == 0)
       return;

    // setup prefix less for bit n
    Count = 0

    For I in 1 to |X|
        P(I) += Count
        If (L(X(I))[n] == 0)
            Count++;

    // go through subsequence with bit n-1 with bit(n) = 1
    Y = []
    For I in 1 to |X|
        If (L(X(I))[n] == 1)
            Y.append(X(I))

    PrefixLess(L, Y, n-1)

    // go through subsequence on bit n-1 where bit(n) = 0
    Y = []
    For I in 1 to |X|
        If (L(X(I))[n] == 0)
            Y.append(X(I))

    PrefixLess(L, Y, n-1)

    return P

y luego ejecuta:

PrefixLess(L, 1..|L|, 32)