这个小代码的时间复杂度是多少？
int count = 0;
for (int i = n; i > 0; i = i/2) {
for (int j = 0; j < i; j++) {
count++;
}
}
我想知道这段代码的时间复杂度。对我来说，我计算为O（n log n），因为外循环运行logn时间和内循环运行O(n)时间。但是我很困惑，因为内循环j取决于i。那么实际的时间复杂度是多少？为什么？
确切的总和是
n + n/2 + n/4 + ... + 1
这是
n * (1 + 1/2 + 1/4 + ... + 1/n)
众所周知，1/2的非负幂之和在极限中接近2，因此总和接近2*n。结果，复杂度为O(n); i下降得足够快，可以避免线性增长。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句