Rotation matricielle en place

Question

Une question intéressante que j'ai trouvée, a demandé qu'une matrice NxN soit pivotée, en place de 90 degrés. Ma solution récursive, en C, est ci-dessous. Cependant, lorsque j'ai recherché d'autres solutions, la plupart utilisaient une boucle imbriquée for pour accomplir la tâche (ce qui semble fonctionner correctement). Les implémentations en boucle imbriquées semblent fonctionner en O(n^2) heure.

Voir: How do you rotate a two dimensional array?

Je crois que la solution récursive fonctionne dans O((n^2-n)/2), qui est O(n^2) aussi bien. Ma question est double. 1) L'analyse de complexité ci-dessus est-elle correcte pour les solutions récursives et non récursives, et 2) Y a-t-il un moyen très efficace ou intelligent de faire pivoter une matrice que je n'ai pas trouvée?

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 rotation ne peut pas être effectuée en moins de n^2 opérations car vous devez échanger tous les éléments. Habituellement, cependant, comme la rotation détruit le cache assez dur, nous évitons de l'exécuter;)

Answer 2

Votre analyse de complexité est correcte, mais aussi très confuse. Puisque le nombre d'éléments dans la matrice est n², O (n²) est effectivement temps linéaire dans la taille de l'entrée, qui est la figure qui compte.

Si vous souhaitez imprimer la totalité de la matrice après l'avoir tournée, le temps linéaire est le meilleur que vous puissiez faire. Pour d'autres opérations, il serait plus sage de ne pas faire pivoter la matrice sur place mais d'écrire un adapter qui change son indexation, ainsi les éléments de la matrice pivotée peuvent être accédés sans effectuer la rotation réelle en mémoire.

Answer 3

en place une solution de C suit

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; 
     } 
    } 
}