这个矩阵和码的复杂度是多少？

Question

我刚刚开始了解复杂性，我找到了这段代码，这段代码的复杂性是什么？是 O(n!) 吗？

public static int func(int[][] mat)
{
    int sum = 0;

    for(int i = 0; i < mat.Length; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            sum += mat[i][j];
        }
    }
    return sum;
}

Answer 1

复杂度有两种类型，时间复杂度和内存复杂度。我想你在这里想知道时间复杂度。

在您的示例中，我假设您的数组大小为 NxN。为了计算时间复杂度，您可以计算步骤。所以，如果我们先开始 for 从 1 到 n 的循环：

i = 0, with the second loop 1 addition.
i = 1, with the second loop 2 additions.
...
i = n, with the second loop n + 1 additions.

总步数为 1 + 2 + ... + n + (n+1) = (n+1)*(n+2) / 2

这就是为什么这个例子的时间复杂度是 O(n^2).

Answer 2

不，这不是 O(n!)。您可以通过尝试思考 i:

的每个值发生了什么来轻松找出复杂性

对于 i = 0，内部循环将执行一次。
对于 i = 1，内部循环将执行两次。
对于 i = 2，内部循环将执行三次。
...
对于 i = k，内部循环将执行 k+1 次。

因此我们总共需要计算以下总和

1+2+3+...+ n+1 = (n+1)(n+2)/2 = (n^2+3n+2)/2

上面的总和显然是O(n^2).

Answer 3

不，答案不是 O(n!)。

最简单的方法是为"i"变量设置一个值，通过这项工作您可以理解复杂性。

我将告诉您如何找到代码的复杂性：

声明复杂度为 1。如果我想展示您的代码示例，我可以指向：

int sum = 0;

和for循环： (see image) Complexity description

T(n) = (n+1) + n*(n+2) + n*(n+1) T(n) = 2n^2 + 4n + 1

==> O(n^2).

希望我的描述对您有所帮助。

这个矩阵和码的复杂度是多少？

what is the complexity of this matrix sum code?

c#

complexity-theory