Java中的二维转置矩阵-时空复杂性？

Question

这是我在主对角线上转置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 

---

我的代码：

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

这种方法的时间和空间复杂度是多少？

是否有更好的最佳解决方案？

Answer 1

算法的时间复杂度将为O（n）。如果传入16元素矩阵（4x4），则将花费大约16个时间单位。如果传入100个元素的矩阵（10x10），则大约需要100个时间单位。

空间复杂度将为O（n）-换句话说，所需的存储量大约与输入矩阵的大小成正比。在您的情况下，您可以说它将是O（2n）-因为它将占用您输入矩阵的空间的大约两倍（包括输入矩阵）。

我说近似的原因是循环及其变量所需的额外时间和空间最少，但是对于任何大小合适的输入矩阵来说，它们都是无关紧要的。