인플레 이스 매트릭스 회전

Question

흥미로운 질문으로, NxN 행렬을 90도 회전시켜달라고 요청했습니다. C의 재귀 적 솔루션은 다음과 같습니다. 그러나 다른 솔루션을 찾아 보았을 때 대부분의 경우 중첩 된 for 루프를 사용하여 작업을 완료했습니다 (정상적으로 작동하는 것 같습니다). 중첩 루프 구현은 O(n^2) 시간으로 실행되는 것으로 보입니다.

은 참조 : How do you rotate a two dimensional array?

나는 재귀 솔루션뿐만 아니라 O(n^2)입니다 O((n^2-n)/2)에서 실행 믿습니다. 제 질문은 두 가지입니다. 1) 재귀 및 비 재귀 솔루션 모두에 대해 위에서 설명한 내 복잡성 분석이 맞습니까? 2) 내가 찾지 못한 행렬을 회전시키는 데 매우 효율적이거나 영리한 방법이 있습니까?

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

회전이 덜 2^n보다 작업에서 수행 할 수 없습니다. 그러나 회전은 캐시를 매우 어렵게 만듭니다. 수행을 피하십시오.)

Answer 2

복잡성 분석은 정확하지만 매우 혼란 스럽습니다. 행렬의 요소 수는 n²이므로 O (n²)는 입력 크기에서 효과적으로 선형 시간이며 이는 중요한 수치입니다.

회전시킨 후 전체 매트릭스를 인쇄하려면 선형 시간이 가장 좋습니다. 다른 연산의 경우에는 행렬을 내부에서 회전하지 말고 인덱스를 변경하는 adapter을 쓰는 것이 현명합니다. 따라서 메모리에서 실제 회전을 수행하지 않고도 회전 된 행렬의 요소에 액세스 할 수 있습니다. 장소 C 솔루션에

Answer 3

당신은 새로운 위치에 n 개의 * n 개의 요소를 이동할 수있어

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