算法
这个问题在这里已经有了答案：
在第一种情况下， sum++执行0 + 1 + ... + n-1次。 如果应用算术级数公式，则会得到n (n-1) / 2 ，即O(n^2) 。
在第二种情况下，我们将有0 + 1 + 4 + 9 + ... + (n-1)^2 ，这是第一个的平方和n-1数字，并且有它的公式： (n-1) n (2n-1)
最后一个很有趣。 实际上，您可以看到，只有当j是i的被乘数时，才会调用最嵌套的for循环，因此您可以按如下方式重写程序：
int n = 500;
for(int i = 0; i < n; i++) {
for(int m = 0; m < i; m++) {
int j = m * i;
for( k = 0; k < j; k++)
sum++
}
}
使用数学符号更容易：
该公式是通过分析得到的代码：我们可以看到， sum++在最内层的循环中被称为j次，称为i次，它被称为n次。 最后，问题归结为前n个数加上低阶项的立方和（不影响渐近线）
最后一个注意事项：它看起来很明显，但我想表明，在第d次幂中的前N自然数的总和为Ω(N^(d+1)) （参见Wikipedia for Big-Omega表示法）它的增长速度不及该功能。 你可以应用相同的推理来证明满足更强的条件，即它属于Θ(N^(d+1)) ，它将Ω和O相结合。
除了最后一个，对O(n^4)有一个更紧的界限，你是对的，注意最后的for循环只有在j是i的倍数时才被执行。 有x / i的倍数i低于或等于x ，和i * i / i = i 。 因此，最后一个循环仅针对i * i i值执行。
请注意，大哦给出了一个上限，所以i*i与n*n没有什么区别。 严格地说，他们都是O(n^2015)也是正确的（因为这是一个有效的上限），但它没有什么帮助，所以在实践中通常使用一个紧束缚。
IVlad已经给出了正确的答案。
我认为让你困惑的是“大哦”的定义。
从这里检查大哦的定义
链接地址: http://www.djcxy.com/p/39347.html上一篇: algorithm