这个小代码的时间复杂度是多少？
这个小代码的时间复杂度是多少？
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下降得足够快以避免线性增长。
回答
iteration | inner loop steps
0 | n
1 | n/2
2 | n/4
3 | n/8
4 | n/16
.
.
.
.
log(n) | n/(2^logn) = 1
n + n/2 + n/4 + n/8 ... + 1 = n(1 + 1/2 + 1/4 + ... 1/n)
这是 O(n)根据
1/2 + 1/4 + 1/8 + ....
收敛到 1。