Yerinde Matris Dönüşü

Question

Bulduğum ilginç bir soru, bir NxN matrisinin 90 derece yerinde yerinde döndürülmesini istedi. Yinelemeli çözümüm C içinde. Ancak diğer çözümlere baktığımda, çoğu zaman görevi yerine getirmek için yuvalanmış bir for döngüsünü kullandı (ki bu iyi çalışıyor gibi görünüyor). Yuvalanmış döngü uygulamaları, O(n^2) zamanında çalışır.

bakınız: How do you rotate a two dimensional array?

Ben özyinelemeli çözüm de O(n^2) olduğunu O((n^2-n)/2), çalışır inanıyoruz. Sorum şu iki kat. 1) Karmaşıklık analizim, hem özyinelemeli hem de özyinelemeyen çözümler için doğrudur ve 2) Bulmadığım bir matrisi döndürmek için bazı yüksek verimli veya akıllıca bir yol var mı?

TIA. Tüm eleman takas için gereken olarak

#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

Rotasyon az 2^n daha operasyonlarda yapılamaz. Genellikle, ancak, rotasyon önbellek oldukça sert, ancak, biz bunu yapmaktan kaçının;)

Answer 2

Karmaşıklık analiziniz doğru ama aynı zamanda da çok kafa karıştırıcı. Matristeki eleman sayısı n² olduğundan, O (n²), girdinin büyüklüğünde etkili bir doğrusal zamandır, ki bu da önemli olan rakamdır.

Döndükten sonra tüm matrisi yazdırmak isterseniz, doğrusal zaman, yapabileceğiniz en iyisidir. Diğer işlemler için, matrisi yerinde döndürmemek akıllıca olacaktır, bunun yerine indekslemeyi değiştiren bir adapter yazınız, böylece döndürülen matrisin elemanlarına, bellekte gerçek dönüş yapmadan erişilebilir. yer C çözeltide

Answer 3

Yeni konumlara n * n elemanlarını hareket etmeliyiz

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