时间戳

首页 > 解决方案 > 在 Java 中转置 2D 矩阵 - 时间和空间复杂度？

java - 在 Java 中转置 2D 矩阵 - 时间和空间复杂度？

问题描述

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

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

有没有更好的最优解？

标签： javatime-complexitybig-ocomplexity-theoryspace-complexity

解决方案

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

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

我说近似的原因是循环及其变量所需的额外时间和空间最少，但对于任何合理大小的输入矩阵来说，这些都变得微不足道。

推荐阅读