Recorrido de matriz

Recorrido de matriz

Para recorrer todos los elementos de una matriz o arreglo de N x N se necesitan dos bucles. De manera intuitiva existen dos estrategias de recorrido:

1) Tomar una fila y recorrer cada celda (o columna) hasta el final. Luego, tomar la siguiente fila.

2) Tomar una columna y recorrer cada celda (o fila) hasta el final. Luego, tomar la siguiente columna.

Cada uno de los programas puede escribirse como sigue:

public static void recorrerPorFila(byte m[][]){

   int filas = m.length;

   int columnas = m[0].length;

   for(int i = 0; i < filas; i++){

      for(int j = 0; j < columnas; j++){

         // Hacer algo con la celda.

         m[i][j] = 1;

      }

   }

}

public static void recorrerPorColumna(byte m[][]){

   int filas = m.length;

   int columnas = m[0].length;

   for(int i = 0; i < columnas; i++){

      for(int j = 0; j < filas; j++){

         // Hacer algo con la celda.

         m[j][i] = 1;

      }

   }

}

Bien, y ¿qué pasa si medimos la complejidad de ambos métodos?. Muy fácil, ambos son de orden cuadrático pues hay un for anidado a otro. Ahora bien, ¿si medimos el tiempo que nos demora uno y el tiempo que nos demora el otro?.

public static void main(String args[]){

   byte m[][] = new byte[100000][1000];

   long desde = System.currentTimeMillis();

   recorrerPorFila(m);

   long hasta = System.currentTimeMillis();

   System.out.println("Recorriendo por fila: " + (hasta – desde));

   desde = System.currentTimeMillis();

   recorrerPorColumna(m);

   hasta = System.currentTimeMillis();

   System.out.println("Recorriendo por columna: " + (hasta – desde));

}

Ambas salidas deberían ser muy similares, ¿no?. Por ejemplo: algo como 100 ms. Sin embargo, observe la salida:

Recorriendo por fila: 82

Recorriendo por columna: 1366