时间复杂度审查

Question

以下代码片段的时间复杂度是多少？

int[][] A = new int [n][];
for (int i=0; i<n; i++) {
    if (i % 2 == 0) // i is a multiple of 2
        A[i] = new int [n];
    else
        A[i] = new int [1];
}

for (int i=0; i<A.length; i++)
    for (int j=0; j<A[i].length; j++)
        sum = sum + A[i][j];

我的理解是第一个for循环循环了n次，然后，就会有n/2行长度为n的矩阵，还有n/2行长度为1的矩阵，总时间是不是n^2?

Answer 1

是的，复杂度为O(n²).

怎么样？

一半的次数（即n/2次），你会遍历n个元素= (n/2) * n = n²/2 .
一半的时间（同样，n/2 次），您将只有一个元素要迭代 = (n/2) * 1 = n/2.
因此，整体复杂度 = O(n²/2 + n/2) = O(n²)

Answer 2

好吧，首先让我们用术语来决定。例如，假设每个操作都等于 1。让我们使用您的代码（只是为了保持一致 - 我们将调用此方法）并逐行进行。

int[][] A = new int [n][];

这将等于 1。

for (int i=0; i<n; i++) {

这里有循环，在最坏的情况下会是 n。

    if (i % 2 == 0) // 1
        A[i] = new int [n]; // 1
    else
        A[i] = new int [1]; // 1
}

以上操作每个可以算作1

for (int i=0; i<A.length; i++)

循环等于 n 个元素。

    for (int j=0; j<A[i].length; j++)

内循环相同n。

        sum = sum + A[i][j];

同样，这将等于 1。

内部循环是相乘所以你是对的，但要考虑到这将是大O符号O(n²).

时间复杂度审查

Time Complexity Review

time

big-o

time-complexity