为什么我不能通过乘法计算时间复杂度？

Question

我想得到这个伪代码的时间复杂度：

count = 0;
for (i = 1; i < n; i *= 2) 
    for (j = 0; j < i; j++) 
        count++;

我以为是log(n)*log(n)，结果答案是log(n)。有人告诉我，因为 i*2 具有非线性增长，所以我不能直接相乘。

我很困惑为什么我不能这样做：我不知道什么时候可以繁殖什么时候不能繁殖的规则。当我计算时间复杂度时，我只是在遇到嵌套循环时将它们相乘。我该如何正确计算？

Answer 1

你得到的答案是错误的。复杂度为 O(𝑛)。

对于给定的𝑖，内层循环的迭代次数等于𝑖，并且𝑖将取小于𝑛的每个2的幂的值。有 ⌈log₂𝑛⌉ 这样的权力。因此内循环的迭代总数就是这些幂的总和，即

2⁰ + 2¹ + 2² + ... + 2^{⌈log₂𝑛⌉−1}

这是几何级数第一项的总和，因此等于：

2^{⌈log₂𝑛⌉}−1

这是 O(𝑛)。

我们可以通过针对 𝑛 的多个值（尤其是 2 的幂）运行脚本来说明这一点：

function getCount(n) {
    let count = 0;
    for (let i = 1; i < n; i *= 2) 
        for (j = 0; j < i; j++) 
            count++;
    return count;
}

for (let n = 1; n < 70000; n *= 2) {
    let count = getCount(n);
    console.log("For", n, "count is", count);
}

可以看到，当

count++

是2的幂时，

n

执行的次数比

n

的值少1次。