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

Question

Esta es una pregunta que me hizo una multinacional muy famosa. La pregunta es la siguiente ...

Ingrese una matriz 2D N * N de 0 y 1. Si A (i, j) = 1, entonces todos los valores correspondientes a la i-ésima fila y la j-ésima columna serán 1. Si ya hay un 1, se mantendrá como 1.

Como ejemplo, si tenemos la matriz

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 

deberíamos obtener la salida como

1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 0 
1 1 1 1 1 
1 1 1 1 0 

la matriz de entrada está escasamente poblada.

¿Esto es posible en menos de O (N^2)?

No se proporciona espacio adicional era otra condición. Me gustaría saber si hay una manera de lograr la complejidad usando un espacio < = O (N).

P.S: No necesito respuestas que me den una complejidad de O (N * N). Este no es un problema de tarea. He intentado mucho y no pude obtener una solución adecuada y pensé que podría obtener algunas ideas aquí. Deje la impresión de lado por la complejidad

Mi idea aproximada fue eliminar dinámicamente el número de elementos atravesados ​​restringiéndolos a alrededor 2N o más. Pero no pude tener una idea adecuada.

Answer 1

chicos Hii,

gracias al comentario de MB14 creo que podría conseguirlo solucionado en menos de O (N N) ... La peor llevaría O (N N) .. .

en realidad, hemos supongamos que la matriz dada

1 0 0 0 1 
    0 1 0 0 0 
    0 1 1 0 0 
    1 1 1 0 1 
    0 0 0 0 0 

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 ... Pu t aquellos con a [i] [1] = 0 en una matriz y luego a [1] [j] = 0 en otra ...

Luego tome solo esos valores y verifique la segunda fila y columnas ... De esta manera, obtenemos los valores de filas y columnas donde solo hay 0; 's completamente ...

El número de valores en el conjunto de filas da el número de 0 en la matriz de resultados y los puntos a [fila -los valores de matriz] [valor de matriz de columna] le da esos puntos ....

Podríamos resolverlo en O (N N) y lo peor es O (N N) ... Como podemos ver, las matrices (de tamaño N) disminuyen ....

Hice esto por un par de matrices y obtuve el resultado para todos ellos ... :)

Por favor, corríjanme si me equivoco en cualquier lugar ...

Gracias por todos sus comentarios chicos ... todos ustedes son muy útiles y que aprendí bastantes cosas en el camino ... :)

Answer 2

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

Answer 3

Me imagino que puede optimizarlo para el mejor de los casos, pero me siento tentado de decir que su peor caso sigue siendo O (N * N): su peor caso será una matriz de todos los 0, y usted tendrá que examinar cada elemento individual.

La optimización implica saltar una fila o columna tan pronto como encuentre un "1" (puedo proporcionar detalles, pero dijo que no le importa O (N * N) ", pero a menos que tenga metadatos para indicar que toda una fila/columna está vacía, o a menos que tenga una forma SIMD para verificar múltiples campos a la vez (por ejemplo, si cada fila está alineada por 4, y puede leer datos de 32 bits, o si sus datos está en forma de una máscara de bits), que siempre se tiene que tratar con el problema de una matriz de todo ceros.

Answer 4

hay claramente hasta O(N^2) trabajo que hacer. en la matriz

1 0 0 0 0 
0 1 0 0 0 
0 0 1 0 0 
0 0 0 1 0 
0 0 0 0 1 

todos los bits deben configurarse en 1, y N*(N-1) no están configurados en uno (20, en este caso de 5x5).

Por el contrario, puede encontrar un algoritmo que siempre lo hace en O(N^2) tiempo: sumar a lo largo de la fila superior y dejar columna, y si la fila o columna obtiene una respuesta distinta de cero, complete toda la fila o columna; luego resuelve el problema más pequeño (N-1) x (N-1).

Así que existen casos que deben tomar al menos N^2 y cualquier caso se puede resolver en N^2 sin espacio adicional.

Answer 5

Como cada entrada de la matriz debe verificarse, su peor caso siempre será N * N.

Con un pequeño almacenamiento adicional de 2 * N, puede realizar la operación en O (N * N). Simplemente cree una máscara para cada fila y otra para cada columna: escanee la matriz y actualice las máscaras a medida que avanza. Luego, vuelva a escanear para completar la matriz de resultados según las máscaras.

Si está haciendo algo donde la matriz de entrada está cambiando, puede almacenar un recuento de entradas distintas de cero para cada fila y columna de la entrada (en lugar de una máscara simple). Luego, cuando cambia una entrada en la entrada, actualiza los recuentos en consecuencia. En ese punto, soltaría la matriz de salida por completo y consultaría las máscaras/recuentos directamente en lugar de mantener la matriz de salida (que también podría actualizarse como cambio de cosa en menos de N N tiempo si realmente quisiera mantenerlo). . Entonces, cargar la matriz inicial seguiría siendo O (N N) pero las actualizaciones podrían ser mucho menores.

Answer 6

La matriz de entrada puede ser escasa, pero a menos que pueda obtenerla en un formato disperso (es decir, una lista de (i,j) pares configurados inicialmente), solo leer su entrada consumirá Ω (n^2) tiempo. Incluso con una entrada escasa, es fácil terminar con la salida O (n^2) para escribir. Como un truco, si se le permitiera mostrar una lista de filas y establecer columnas, entonces podría bajar al tiempo lineal. No hay magia para tener cuando tu algoritmo realmente tiene que producir un resultado más sustancial que 'sí' o 'no'.

El comentario de Mcdowella sobre otra respuesta sugiere otro formato de entrada alternativo: la codificación de longitud de ejecución. Para una entrada escasa, que claramente no requiere más de O (n) tiempo para leerla (considere cuántas transiciones hay entre 0 y 1). Sin embargo, a partir de ahí se descompone. Considere una matriz de entrada estructurada de la siguiente manera:

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 escaso, ya que hay n/2 en total. Sin embargo, la salida RLE tiene que repetir este patrón en cada fila, lo que lleva a la salida O (n^2).

Answer 7

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 ^eny su complejidad de salida M ^fuera. Esperaría algo como O (N + M ^en + M ^en) pero mucho dependiendo de la codificación y los trucos que se pueden jugar con ella.

Answer 8

Eso depende completamente de su estructura de datos de entrada. Si pasas tu matriz (1s y 0s) como una matriz 2D, necesitas atravesarla y es O (N^2). Pero como tus datos son escasos, si solo pasas los 1 como entrada, puedes hacerlo para que el ouptut sea O (M), donde M no es el número de celdas, sino el número de 1 celda. 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; 
} 

Answer 9

Usted dice:

deberíamos obtener la salida como ...

por lo que necesita para dar salida a la totalidad matriz, que tiene elementos N^2. 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 unos, 0 en caso contrario;

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

Puede construir estos vectores en O (N), porque la matriz inicial es dispersa; sus datos de entrada no serán una matriz, sino una lista que contiene las coordenadas (línea, columna) de cada elemento distinto de cero. Mientras lee esta lista, establece 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

Answer 10

No llene el centro de la matriz cuando esté comprobando los valores. A medida que recorre los elementos, cuando tiene 1 establece el elemento correspondiente en la primera fila y la primera columna. Luego regresa y rellena y cruza.

editar: En realidad, esto es lo mismo que Andy's.

Answer 11

Claramente, ni la matriz de salida ni su versión negada tienen que ser dispersas (tomar una matriz con la mitad de la primera fila establecida en 1 y cualquier cosa en 0), así que el tiempo depende del formato que se le permita usar para la salida. (Supongo que la entrada es una lista de elementos o algo equivalente, ya que de lo contrario no podría aprovechar que la matriz es escasa.)

Una solución simple para O (M + N) espacio y tiempo (M es el número de unidades en la matriz de entrada): tome dos matrices de longitud N llenas de unas, recorra todas las de la entrada y para cada gota 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: dependiendo en el idioma, podría usar algún truco para devolver una matriz 2D normal al hacer 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, esta es una matriz normal, siempre y cuando no intente escribirla.

Answer 12

Depende de su estructura de datos.

sólo hay dos casos posibles para las 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 hay un elemento (_, j) en la entrada.

Por lo tanto, el resultado podría representarse de forma compacta como una matriz de referencias a filas. Como solo necesitamos dos filas, el resultado solo consumirá memoria O (N).A modo de ejemplo, esto podría ser implementado en Python de la siguiente manera:

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 la muestra 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 son copiado aquí, es decir, M [fila] = A es solo una asignación de una referencia. Por lo tanto, la complejidad es O (N + M), donde M es la longitud de la entrada.

Answer 13

#include<stdio.h> 

incluyen

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 no es posible resolver este problema en < O (n^2).