Podemos calcular esto en menos de O (n * n) ... (nlogn o n)

https://stackoverflow.com/questions/3659506

01-10-2019
|

Pregunta

Esta es una pregunta que a mí por un muy, muy famosa MNC. La pregunta es la siguiente ...

Input una matriz 2D N * N de 0 y 1'S. Si A (i, j) = 1, entonces todos los valores correspondientes a la i-ésima fila y la columna j-ésima van a ser 1. Si hay una ya 1, permanece como un 1.

Como un ejemplo, si tenemos el array

deberíamos obtener la salida como

La matriz de entrada está escasamente poblada.

Es esto posible en menos de O (N ^ 2)?

No hay espacio adicional es proporcionado fue otra condición. Me gustaría saber si hay una manera de lograr la complejidad utilizando un espacio <= O (N).

P.S: no necesito respuestas que me dan una complejidad de O (N * N). Esto no es un problema de tarea. He tratado mucho y no pudimos conseguir una solución adecuada y pensé que podría obtener algunas ideas here.Leave la impresión de lado por la complejidad

Mi idea aproximada era puede ser eliminar dinámicamente el número de elementos atravesados ??restringirlos a alrededor de 2 N aproximadamente. Pero no podía hacerse una idea adecuada.

Solución 7

chicos Hii,

gracias al comentario de MB14 creo que podría conseguirlo solucionado en menos de un tiempo O (N N) ... Lo peor sería tomar O (N N) ...

En realidad, hemos supongamos que la matriz dada

Vamos a tener 2 matrices de tamaño N (este sería el peor de los casos) ... Una está dedicada para las filas de indexación y otras columnas ... Ponga aquellos con un [i] [1] = 0 en una matriz y luego a [1] [j] = 0 en otro ..

A continuación, tomar esos valores solo y comprobar si la segunda fila y columnas ... De esta manera, se obtienen los valores de filas y columnas donde sólo son 0; 's del todo ...

El número de valores de la matriz fila da número de 0 de la matriz resultado y los puntos de un [valores de fila-array] [valor de matriz columna] da por esos puntos ....

podría resolverlo por debajo de O (N N) y lo peor es O (N N) ... Como podemos seee, las matrices de tamaño (N) disminuye ....

Lo hice por un par de matrices y obtuve el resultado para todos ellos ...:)

Por favor, corríjanme si estoy en cualquier lugar equivocado ...

Gracias por todos sus comentarios chicos ... Usted es muy servicial y me hizo aprender bastantes cosas en el camino ...:)

Otros consejos

En el peor de los casos, puede que tenga que alternar N * N - N bits de 0 a 1 para generar la salida. Parecería que está bastante bien pegado con O (N * N).

Me imagino que se puede optimizar para el mejor de los casos, pero estoy tentado a decir que el peor de los casos sigue siendo O (N * N): Su peor de los casos será un array de todos 0s, y usted que examinar cada elemento.

La optimización implicaría saltar una fila o columna, tan pronto como lo encontró un "1" (puedo dar detalles, pero dijo que no se preocupan por O (N * N)", pero a menos que tenga metadatos para indican que toda una fila / columna está vacía, o a menos que tenga una forma de estilo SIMD para comprobar varios campos a la vez (por ejemplo, si cada fila está alineado por 4, y se puede leer 32 bits de valor de datos, o si sus datos están en forma de una máscara de bits), siempre tendrá que lidiar con el problema de una matriz de todo ceros.

Es evidente que ni la matriz de salida ni su versión negada tiene que ser escasa (tome una matriz con la mitad del primer conjunto de filas a 1 y todo lo demás a 0 para ver), así que el tiempo depende de qué formato se le permite el uso para la salida. (Estoy suponiendo que la entrada es una lista de elementos o algo equivalente, ya que de lo contrario no podría tomar ventaja de la matriz siendo escasa.)

Una solución sencilla para O (M + N) espacio y el tiempo (M es el número de unos en la matriz de entrada): tomar dos matrices de longitud N llena de queridos, iterar a través de todos los de la entrada, y para cada dejar caer la coordenada X de la primera matriz y la y de la segunda. La salida es las dos matrices, que definen claramente la matriz de resultado:. Su (X, Y) de coordenadas es 0 si y sólo si la coordenada X de la primera matriz y la coordenada Y del segundo son 0

Actualización: en función del idioma, podría utilizar algunos trucos para devolver una matriz 2D normal, haciendo referencia a la misma fila varias veces. Por ejemplo, en PHP:

// compute N-length arrays $X and $Y which have 1 at the column 
// and row positions which had no 1's in the input matrix
// this is O(M+N)
$result = array();
$row_one = array_fill(0,N,1);
for ($i=0; $i<N; $i++) {
    if ($Y[$i]) {
         $result[$i] = &$row_one;
    } else {
         $result[$i] = &$X;
    }
}
return $result;

Por supuesto, esto es una matriz normal sólo, siempre y cuando no trate de escribir en él.

Debido a que cada entrada de la matriz tiene que ser revisado, el peor de los casos siempre va a ser N * N.

Con un pequeño 2 * N almacenamiento adicional, se puede realizar la operación en O (N * N). Basta con crear una máscara para cada fila y otra para cada columna - escanear la matriz y actualizar las máscaras a medida que avanza. A continuación, analizar de nuevo para poblar la matriz de resultados en función de las máscaras.

Si estás haciendo algo donde la matriz de entrada está cambiando, se podría almacenar un recuento de los no-cero entradas para cada fila y columna de la entrada (en lugar de una simple máscara). Entonces, cuando una entrada en la entrada cambia, se actualiza el recuento en consecuencia. En ese punto, me gustaría dejar caer la matriz de salida en su totalidad y consultar las máscaras / recuento directamente en lugar de mantener incluso la matriz de salida (que también podría ser actualizada a medida que el cambio que en menos de N N Tiempo de si realmente quería mantenerlo alrededor). Así la carga de la matriz inicial todavía sería O (N N) pero las actualizaciones podría ser mucho menos.

La matriz de entrada puede ser escasa, pero a menos que lo puede conseguir en un formato escasa (es decir, una lista de pares (i,j) que se establece inicialmente), acaba de leer su entrada consumirá O (2 ^ n) tiempo. Incluso con la entrada escasa, es fácil acabar con O (n ^ 2) de salida para escribir. Como un tramposo, si se dejen a la salida de una lista de filas del conjunto de columnas del conjunto y, a continuación, usted podría bajar a tiempo lineal. No hay magia que se tenía cuando su algoritmo tiene en realidad para producir un resultado más sustancial que 'sí' o 'no'.

El comentario de Mcdowella en otra respuesta sugiere otro formato alternativo de entrada: RLE. Para una entrada de escasa, que claramente no más de tiempo O (n) requiere para leerlo (Tenga en cuenta cuántas transiciones hay entre 0 y 1). Sin embargo, a partir de ahí se rompe. Considere una matriz de entrada estructurada como sigue:

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . . . 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . .
.     .
.       .
.         .

Es decir, alternando 0 y 1 en la primera fila, 0 en cualquier otro lugar. Claramente escasa, ya que son los n/2 en total. Sin embargo, la salida RLE tiene que repetir este patrón en cada fila, que conduce a O (n ^ 2) de salida.

Usted dice:

que debe recibir la salida como ...

Por lo que necesita para dar salida a toda la matriz, que tiene N ^ 2 elementos. Esto es O (N * N).

El problema en sí no es O (N * N): usted no tiene que calcular y almacenar toda la matriz: sólo se necesitan dos vectores, L y C, cada uno de tamaño N:

L [x] es 1 si la línea x es una línea de queridos, 0 en caso contrario;

C [x] es 1 si la línea x es una línea de queridos, 0 en caso contrario;

Se puede construir estos vectores en O (N), porque la matriz inicial es escasa; los datos de entrada no será una matriz, pero una lista que contiene las coordenadas (línea, columna) de cada elemento no nulo. Durante la lectura de esta lista, conjunto L [línea] = 1 y C [columna] = 1, y el problema se resuelve: M [l, c] == 1 si L [l] == 1 o C [c] = = 1

Es evidente que existe hasta el trabajo O(N^2) hacer. En la matriz

todos los bits tienen que establecerse a 1, y N*(N-1) no se establecen en uno (20, en este caso 5x5).

A la inversa, se puede llegar a un algoritmo que siempre lo hace en el tiempo O(N^2): suma lo largo de la fila superior y dejar que la columna, y si la fila o columna para crear una respuesta diferente de cero, de relleno en toda la fila o columna; a continuación, resolver el más pequeño (N-1) x (N-1) problema.

Por lo tanto, existen casos que deben tener al menos N^2 y ningún caso puede ser resuelto en N^2 sin espacio adicional.

Si su matriz es escasa, la complejidad depende mucho de la codificación de entrada y está en particular no bien medido en NN ² o algo así, pero en términos de N su entrada complejidad M ^en y su salida de la complejidad M ^{a cabo}. Yo esperaría algo así como O (n + m ^en + M ^{a cabo}) pero mucho dependiendo de la codificación y los trucos que se puede jugar con él.

Eso depende por completo de la estructura de datos de entrada. Si pasa su matriz (1 y 0) como una matriz 2D que necesita para atravesarlo y que es O (n ^ 2). Pero a medida que sus datos son escasos, si pasa únicamente los de 1 como entrada, puede hacerlo por lo que el ouptut es O (M), donde M no es el número de células, pero el número de células 1. Sería algo similar a esto (pseudocódigo siguiente):

list f(list l) {
   list rows_1;
   list cols_1;

    for each elem in l {
        rows_1[elem.row] = 1;
        cols_1[elem.col] = 1;
    }

    list result;
    for each row in rows_1 {
        for each col in cols_1 {
             if (row == 1 || col == 1) {
                 add(result, new_elem(row, col));
             }
        }
    } 
   return result;
}

No llene el centro de la matriz cuando se está comprobando los valores. A medida que avanza a través de los elementos, cuando se tiene 1 fijar el elemento correspondiente en la primera fila y la primera columna. A continuación, volver atrás y rellenar hacia abajo y al otro lado.

editar:. En realidad, este es el mismo que el de Andy

Depende de su estructura de datos.

Sólo hay dos casos posibles de filas:

una fila i se llena con 1 de si hay un elemento (i, _) en la entrada
Todas las otras filas son los mismos: es decir, el j-ésimo elemento es 1 si y sólo si existe un elemento (_, j) en la entrada

Por lo tanto el resultado podría ser representado de forma compacta como una matriz de referencias a las filas. Ya que sólo necesitamos dos filas el resultado también lo haría sólo consumen O memoria (N). Como ejemplo esto podría ser implementado en Python como sigue:

def f(element_list, N):
  A = [1]*N
  B = [0]*N
  M = [B]*N
  for row, col in element_list:
    M[row] = A
    B[col] = 1
  return M

Una llamada de ejemplo sería

 f([(1,1),(2,2),(4,3)],5)

con el resultado

[[0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]

El punto importante es que las matrices no se copian aquí, es decir, M [fila] = A es sólo una asignación de una referencia. Por lo tanto la complejidad es O (N + M), donde M es la longitud de la entrada.

#include<stdio.h>

incluir

int main () { int arr [5] [5] = {{1,0,0,0,0}, {0,1,1,0,0}, {0,0,0,0,0}, {1,0,0,1,0}, {0,0,0,0,0}}; int var1 = 0, var2 = 0, i, j;

for(i=0;i<5;i++)
   var1 = var1 | arr[0][i];

for(i=0;i<5;i++)
   var2 = var2 | arr[i][0];

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
      if(arr[i][j])
         arr[i][0] = arr[0][j] = 1;

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
          arr[i][j] = arr[i][0] | arr[0][j];

for(i=0;i<5;i++)
   arr[0][i] = var1;

for(i=0;i<5;i++)
   arr[i][0] = var2;

for(i=0;i<5;i++)
{
   printf("\n");             
   for(j=0;j<5;j++)
      printf("%d ",arr[i][j]);
}

getch();

}

Este programa hace uso de sólo 2 4 variables temporales (var1, var2, I y J) y por lo tanto se ejecuta en el espacio constante con la complejidad O (n ^ 2) .. Creo que no es posible en absoluto para resolver este problema en

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow