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

Question

我一直在尝试计算以下算法的 Big-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

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

三重嵌套循环相当于求和$$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$ $$=O(n^4)$$

---

按照 实际的 代码效率，因为 x=y+z 在循环中是不变的，任何好的优化编译器都会将语句从循环中提取出来（用编译器的话说，将语句提升到循环前置器），从而使编译后的代码运行在 $O(1)$.