Matrix rotation in place

Question

An interesting question I found was asking the NxN matrix to be rotated 90 degrees in place. A recursive solution in C is given below. However, when I searched for other solutions, most of them used a nested for loop to complete the task (which seems to work fine). Nested loop implementation works in O(n^2) time.

See: How do you rotate a two-dimensional array?

I believe that the recursive solution works in O( (n^2-n)/2 ) , which is equal to O(n^2) . My question is double. 1) Is my complexity analysis above correct for both recursive and non-recursive solutions, and 2) Is there any highly efficient or smart way to rotate the matrix that I have not found?

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][ni-1]; matrix[n-1][ni-1] = temp1; temp1 = matrix[ni-1][0]; matrix[ni-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

Rotation cannot be performed in less than n ^ 2 operations, since you need to change the entire element. Usually, however, since skull ingrowth of the cache is rather complicated, we avoid doing it;)

Answer 2

in place decision C follows

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

Answer 3

The complexity analysis is correct, but also very confusing. Since the number of elements in the matrix is ​​n², O (n²) is actually linear time in the input size that matters.

If you want to print the entire matrix after it rotates, then the best time you can make is linear time. For other operations, it would be wiser not to rotate the matrix in place, but instead write adapter , which changes its indexing, so the elements can be accessed by a rotating matrix without actually rotating in memory.