这段小代码的时间复杂度是多少?
What is the time complexity of this little code?
这段小代码的时间复杂度是多少?
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
下降速度足以避免 linarithmic 增长。
n + n/2 + n/4 + ... + 1 = 2n,所以这是 O(n)。
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) 作为 per
1/2 + 1/4 + 1/8 + ....
收敛于 1。
这段小代码的时间复杂度是多少?
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
下降速度足以避免 linarithmic 增长。
n + n/2 + n/4 + ... + 1 = 2n,所以这是 O(n)。
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) 作为 per
1/2 + 1/4 + 1/8 + ....
收敛于 1。