algorithm - 这个算法的运行时间复杂度是多少

Question

这个算法的时间复杂度是多少：

sum = 0
i = 1

while (i < n) {

    for j = 1 to i {
        sum = sum + 1
    }

    i = i*2;
}

return sum

我知道while循环是O(logn)，但是循环的复杂性是for多少？是O(n)还是O(logn)？

Answer 1

对此进行分析的一种方法是计算内部循环的迭代次数。在第一次迭代中，循环运行一次。在第二次迭代中，它运行两次。它在第三次迭代中运行四次，在第四次迭代中运行八次，更一般地在第^k次迭代中运行 2k 次。这意味着内部循环的迭代次数由下式给出

1 + 2 + 4 + 8 + ... + 2 ^r = 2 ^{r + 1} - 1

其中 r 是内部循环运行的次数。正如您所指出的，r 大约是 log n，这意味着这个总和（大约）

2 ^{log n + 1} - 1 = 2(2 ^{log n} ) - 1 = 2n - 1

因此，内部循环在 O(n) 中的所有迭代中完成的总工作量。由于程序在运行外循环时总共做了 O(log n) 的工作，所以这个算法的总运行时间是 O(n + log n) = O(n)。请注意，我们不会将这些项相乘，因为 O(log n) 项是纯粹在维护外部循环中完成的工作总量，而 O(n) 项是纯粹由内循环。

希望这可以帮助！