Поворот матрицы по месту

Question

Интересный вопрос, который я обнаружил, - это поворот матрицы NxN на 90 градусов.Мое рекурсивное решение, в C, ниже.Однако, когда я искал другие решения, большинство из них использовали вложенный цикл for для выполнения задачи (которая, кажется, работает нормально).По-видимому, реализации вложенного цикла выполняются за O(n^2) время.

См .: Как вращать двумерный массив?

Я считаю, что рекурсивное решение работает в O( (n^2-n)/2 ), что равно O(n^2).У меня вопрос двоякий.1) Является ли мой анализ сложности, приведенный выше, корректным как для рекурсивных, так и для нерекурсивных решений, и 2) Существует ли какой-нибудь высокоэффективный или умный способ поворота матрицы, которого я не нашел?*

#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

на месте C решения следует

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 2

Вращение не может быть выполнено менее чем за n ^ 2 операций, так как вы должны поменять местами все элементы. Обычно, однако, так как ротация разрушает кеш довольно сложно, мы избегаем ее выполнения;)

Answer 3

Ваш анализ сложности правильный, но также очень запутанный. Поскольку количество элементов в матрице равно n², O (n²) - это, по сути, линейное время в размере входных данных, то есть значение, которое имеет значение.

Если вы хотите напечатать всю матрицу после ее вращения, то лучше всего использовать линейное время. Для других операций было бы разумнее не вращать матрицу на месте, а вместо этого записать адаптер , который изменяет ее индексирование, чтобы к элементам повернутой матрицы можно было обращаться без фактического вращения в памяти.