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

Question

我对这个循环有点困惑。给定一个数字n，我们必须找出指令执行多少次。forint 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)