c - 这个小代码的时间复杂度是多少？

Question

这个小代码的时间复杂度是多少？

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。那么实际的时间复杂度是多少，为什么？

标签： calgorithmcomplexity-theory

Answer 1

确切的总和是

n + n/2 + n/4 + ... + 1

这是

n * (1 + 1/2 + 1/4 + ... + 1/n)

众所周知，1/2 的非负幂的总和在极限内接近 2，因此总和接近2*n。结果，复杂度为O(n); i下降得足够快，以避免线性增长。