这个短代码的运行时复杂性是多少？

Question

我在编程实践网站上找到了这个解决方案,它说复杂性是O(N).但是,它看起来更像是O(N ^ 2).有人可以告诉我为什么这是O(N)？

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

Answer 1

什么是N？

如果N是max(matrix.length, matrix[0].length),那么算法就是O(N ^ 2),如你所说.

如果N是矩阵的总大小,则算法为O(N).

确切地定义Nbig-O表示法中的内容始终非常重要.在学习Big-O时,大多数讨论围绕着单维输入,人们认为你不必定义N.在现实世界中,事情是肮脏的,我们处理多维输入,你必须非常清楚什么N是.