如何找到这个嵌套for循环的复杂性？

Question

我对这个循环有点困惑。给定一个数字n，我们必须找出指令执行多少次。for

int j = 0;

for(int p = 0; p < n*n; p++ )

{

    for(int q = 0; q < p; q++ )

    {

        j++;

    }

}

我的回答是.这个答案正确吗？O(n^4)

Answer 1

您可以为时间复杂度 编写相关的西格玛。因此，您的答案对于说明的数量是正确的。T(n) = sum_{p = 1}{n^2} sum_{q=1}{p} (1) = sum_{p=1}{n^2} (p) = 1 + 2 + 3 + ... + n^2 = n^2(n^2 + 1)/2 = Theta(n^4)