Транспонировать 2D матрицу в Java - сложность времени и пространства? - PullRequest
Новая
       41

Транспонировать 2D матрицу в Java - сложность времени и пространства?

1 голос
/ 11 февраля 2020

Вот мой алгоритм / подход для транспонирования 2D Матрицы на главной диагонали.

До: 

a L M d 
b G c N 
H K e F 
I J O P

После: 

a b H I 
L G K J 
M c e O 
d N F P

My код: 

public class Matrix {

    static String[][] matrix = {

            {"a", "L", "M", "d"},
            {"b", "G", "c", "N"},
            {"H", "K", "e", "F"},
            {"I", "J", "O", "P"}
    };

    public void transpose(String[][] matrix) {
       String[][] transposedArray = new String [4][4];
       for (int row =0; row < 4; row ++) {
           for (int col = 0; col < 4; col++) {
               transposedArray[row][col] = matrix[col][row];  
           }
       }
    }
}

Какова временная и пространственная сложность этого подхода?

Есть ли лучшее оптимальное решение?

1 Ответ

2 голосов
/ 11 февраля 2020

Сложность времени для вашего алгоритма будет O (n). Если вы передадите матрицу из 16 элементов (4x4), это займет примерно 16 единиц времени. Если вы передадите матрицу из 100 элементов (10x10), это займет приблизительно 100 единиц времени.

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

Причина, по которой я говорю приблизительный, заключается в том, для циклов и их переменных требуется минимальное дополнительное время и пространство, но они становятся незначительными для любой входной матрицы разумного размера.

...