如何计算以下算法的 Big-O 复杂度?
-
29-09-2020 - |
题
我一直在尝试计算以下算法的 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,这是我的第一项任务,因此对于我可能犯的任何基本错误表示歉意。
解决方案
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)$.
不隶属于 cs.stackexchange