这段短代码的运行时复杂度是多少？

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

这不是 O(n)。是 O(n^2)。具体来说，它将对 0 ≤ i ≤ n 执行 n-i 次交换。因此它将执行 0 + 1 + 2 + ... + n swaps = n(n+1)/2 swaps，即 O(n^2).

Answer 2

什么是N？

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

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

准确定义 N 在大 O 表示法中的含义始终非常重要。在学习 Big-O 时，大多数讨论都围绕单维输入展开，人们认为您不必定义 N。在现实世界中，事情是肮脏的，我们处理的是多维输入，你必须非常清楚N是什么。

Answer 3

n = matrix.length - 1;

时间复杂度：O(N^2)

Space 复杂度：O(1)

Explanation: In first for loop i will go from (0 --- N). And in second for loop, j will go from (i+1 --- N). For i = 0, you iterate N-1 elements. For i = 1, you iterate N-2 elements. Similarly, For i = N-1, you iterate for last element

In total, T  = (N-1) + (N-2) + (N-3) + ... + 2 + 1

T ~ N * (1+2+3+...+N)

T ~ O(N^2)

这段短代码的运行时复杂度是多少？

What is the runtime complexity of this short code?

algorithm

asymptotic-complexity