Rotación de matriz in situ

Question

Una pregunta interesante que encontré, solicitó que se girara una matriz NxN, in situ 90 grados. Mi solución recursiva, en C, está debajo. Sin embargo, cuando busqué otras soluciones, la mayoría usaba un lazo anidado for para realizar la tarea (que parece funcionar bien). Las implementaciones de bucle anidado parecen ejecutarse en el tiempo O(n^2).

Ver: How do you rotate a two dimensional array?

creo que la solución recursiva se ejecuta en O((n^2-n)/2), que es O(n^2) también. Mi pregunta es doble 1) ¿Es mi análisis de complejidad superior correcto para las soluciones recursiva y no recursiva, y 2) ¿Hay alguna manera altamente eficiente o inteligente de rotar una matriz que no he encontrado?

TIA.

#include <stdio.h> 
#include <stdlib.h> 


int SIZE = 0; 


/** 
* In-place, recursive, clockwise, 90 degree matrix rotation. 
*/ 
static void rotate_in_place(int matrix[][SIZE], int n) 
{ 
    if(n < 2) 
     return; 


    int temp1, temp2; 

    for(int i = 0; i < (n-1); i++) 
    { 
     temp1 = matrix[i][n-1]; 
     matrix[i][n-1] = matrix[0][i]; 

     temp2 = matrix[n-1][n-i-1]; 
     matrix[n-1][n-i-1] = temp1; 

     temp1 = matrix[n-i-1][0]; 
     matrix[n-i-1][0] = temp2; 

     matrix[0][i] = temp1; 
    } 


    matrix = ((int*)matrix) + SIZE + 1; 
    n -= 2; 
    rotate_in_place(matrix, n); 
} 


static void print_matrix(int matrix[][SIZE]) 
{ 
    printf("\n"); 
    for(int i = 0; i < SIZE; i++) 
    { 
     for(int j = 0; j < SIZE; j++) 
      printf("%4i ", matrix[i][j]); 

     printf("\n"); 
    } 
} 


int main() 
{ 

    // Create some matrices and rotate them. 
    // 
     int matrices = 10; 

     for(int i = 2; i < matrices; i++) 
     { 
      int matrix[i][i]; 

      int count = 0; 
      for(int j = 0; j < i; j++) 
       for(int k = 0; k < i; k++) 
        matrix[j][k] = ++count; 


      printf("\n\nRotating %ix%i matrix.\n", i, i); 

      SIZE = i; 

      printf("\nOriginal matrix.\n"); 
      print_matrix(matrix); 

      rotate_in_place(matrix, i); 

      printf("\n\nRotated matrix.\n"); 
      print_matrix(matrix); 
     } 


    return EXIT_SUCCESS; 
} 

Answer 1

La rotación no se puede realizar en menos de n^2 operaciones ya que se requiere cambiar todo el elemento. Por lo general, sin embargo, como la rotación arruina la caché bastante, evitamos realizarla;)

Answer 2

Su análisis de complejidad es correcto, pero también muy confuso. Como el número de elementos en la matriz es n², O (n²) es efectivamente tiempo lineal en el tamaño de la entrada, que es la figura que importa.

Si desea imprimir toda la matriz después de rotarla, el tiempo lineal es lo mejor que puede hacer. Para otras operaciones, sería más prudente no rotar la matriz en su lugar, sino escribir un adapter que cambie su indexación, de manera que se pueda acceder a los elementos de la matriz girada sin realizar la rotación real en la memoria.

Answer 3

lugar en solución C sigue

void rotateRight(int matrix[][SIZE], int length) { 

    int layer = 0; 

    for (int layer = 0; layer < length/2; ++layer) { 

     int first = layer; 
     int last = length - 1 - layer; 

     for (int i = first; i < last; ++i) { 

      int topline = matrix[first][i]; 
      int rightcol = matrix[i][last]; 
      int bottomline = matrix[last][length - layer - 1 - i]; 
      int leftcol = matrix[length - layer - 1 - i][first]; 

      matrix[first][i] = leftcol; 
      matrix[i][last] = topline; 
      matrix[last][length - layer - 1 - i] = rightcol; 
      matrix[length - layer - 1 - i][first] = bottomline; 
     } 
    } 
}