如何计算以下算法的Big-O复杂度？

Question

我一直在尝试计算以下算法的大 O，结果对我来说是 O(n^5)。我不知道正确答案是什么，但我的大多数同事都得到 O(n^3)。

for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++) 
        {
        x = y + z;
        }
     }
}

我所做的是从最里面的循环开始。所以我计算出最内层的循环将 运行 n/2 次，然后我进入第二个嵌套的 for 循环，它将 运行 i^2 次，从最外层的循环将 运行 i 次 i 从 1 到 n 变化。这意味着第二个嵌套 for 循环将 运行 总共 Sigma(i^2) from i=1 to i=n 所以总共 n*(n+1)*(2n+1)/6 次。所以代码的总数量 运行 结果是 n^5 的顺序，所以我得出结论，顺序必须是 O(n^5)。这种方法和我计算的答案有问题吗？

我刚刚开始使用 DSA，这是我的第一份作业，对于我可能犯的任何基本错误，我深表歉意。

Answer 1

内部循环总是有相同的迭代次数（n/2），因为它独立于i和j。它本身的复杂度为 O(n).

另外两个循环产生内部执行的平方序列 (1 + 4 + 9 + ...) 的总和。

这个平方和对应square pyramidal number，阶数为O(n³).

内循环的阶数为O(n)，所以我们得到O(n⁴) .