我在计算以下代码的大O时遇到问题。我从来都不是最聪明的饼干。 有谁能解释一下吗。由于嵌套循环,我在这里的猜测是O(N^2),但我知道还有更多原因。
static inline int f1 (int a, int b)
{
for (int c = 0; c < b; c++)
{
a -= n;
}
return a;
}
int f2 (int n)
{
int r = n * n * n;
for (double i = n; i >= 0; i -= 2)
{
r = f1(r, i);
}
return r;
}
首先,请注意F1的运行时完全依赖于第二个参数,该参数控制循环迭代的次数。因此,它的运行时在第二个参数中是线性的。
接下来,注意f2中的循环运行n/2次,其中i取值0、2、4、6、...、n。因为i是f1的第二个参数,所以运行时间由
给出0+2+4+...+n
=2(0+1+2+.+n)=2&theta;(n^2)
=&Theta;(n^2)
所以运行时是&theta;(n^2)。请注意,几乎所有其他事情都是为了让你分心,意在误导你。只关注控制迭代和循环的变量会揭示您需要关注的实际逻辑。
希望这能有所帮助!
这篇关于计算嵌套循环的大O的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持吉威生活!
[英文标题]Calculating Big O for nested loops
声明:本媒体部分图片、文章来源于网络,版权归原作者所有,如有侵权,请联系QQ:330946442删除。