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

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)项是纯粹由工作完成的工作总量.内循环.

希望这可以帮助!