algorithm - 这个算法的大O

Question

这个算法的大 O 是什么？在我看来，O(n^3) ^ 是指数。

A()
{
    int i,j,k,n;

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i^2;j++)
        {
            for(k=1;k<=n/2;k++)
            {
                statement ;
            }
        }
    }
}

Answer 1

不，它是O(n^4)。

解释:

第 1 次，最外层循环运行，第二个循环运行 1^2 次，最内层循环运行 n/2 次。

总体 1^2 。 n/2

第二次，最外层循环运行，第二个循环运行 2^2 次，最内层循环运行 n/2 次。

总体 2^2 。 n/2

……

类似地直到 n^2 。 n/2 在 i 的最后一次迭代中(最外层循环)

总结一下:(n/2)(1^2 + 2^2 + 3^2 + .... n^2)=n/2.[n (n+1)(2n+1)/6](利用前n个数的平方和的性质)

O(n^4)