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 次迭代中运行 2^k 次。这意味着内循环的迭代次数由下式给出

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) 项是纯粹由内循环。

希望这对您有所帮助!