努力理解两个嵌套的 for 循环如何仍然具有 O(n) 运行时间

Question

我有以下解决方案代码可以将图像向右旋转。

先对矩阵进行转置，然后在纵轴上翻转：

public static void rotateSquareImageCW(int[][] matrix) {
    transposeMatrix(matrix);
    flipVerticalAxis(matrix);
}   


public static void transposeMatrix(int[][] matrix) {
    int n = matrix.length - 1;
    int temp = 0;
    for(int i = 0; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
}


private static void flipVerticalAxis(int[][] matrix) {
    int n = matrix.length - 1;
    int temp = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n/2; j++){
            temp = matrix[i][j];
            matrix[i][j] = matrix[i][n-j];
            matrix[i][n-j] = temp;
        }
    }
}

代码作者 (Firecode.io) 说这段代码运行时间为 O(n) space 和 O(1)。

但是，我们可以看到“transposeMatrix”和“flipVerticalAxis”函数具有嵌套的 for 循环，迭代矩阵的 rows/columns。

根据列和行的大小，这不应该是 O(N^2) 吗？

这怎么还是O(N)？任何人都可以对此进行解释或合理化吗？

Answer 1

正如评论中已经指出的那样，这取决于 O(n) 表达式中 n 的定义。

最合理的定义是n表示矩阵的宽度或高度。这符合各种矩阵算法分析，另外还得到以下事实的支持：代码使用名为 n 的变量，其含义完全相同。

该代码仅使用一组固定的附加存储元素，即 i、j、n 和 temp，因此它是常量 space （不包括预先存在的 matrix），意思是 O(1) space 复杂性。

两个嵌套循环分别遍历 n（或 n/2）个元素，所以你完全正确，这意味着 O(n²).

因此，它是 O(1) space 和 O(n²) 时间复杂度。

努力理解两个嵌套的 for 循环如何仍然具有 O(n) 运行时间

Struggling to understand how two nested for-loops can still have O(n) runtime

java

algorithm

matrix

big-o

space-complexity