algorithm - 你如何找到这些循环的渐近时间复杂度？

Question

你如何找到这段代码的渐近时间复杂度？

for i=1 to n do
    j=2
    while j<i do
        j=j*j

在我的笔记中我有答案 O(n*log(logn)) 但没有解释。

Answer 1

第一个 for 循环运行 n 次。内部循环在正方形中迭代，因此将采用 O(loglogn) 因此，总复杂度为 O(n*log(logn))。

要理解为什么在正方形中迭代需要 O(log(logn)) 时间，请看这个方式:

假设 n 是 2^16 这样大的数。

Initially: j = 2
1st step : j = 2^2
2nd step : j = 2^4
3rd step : j = 2^8
4th step : j = 2^16. 

因此它只需要 4 个步骤，即 loglog(2^16)。

所以现在对于任何 n = 2^k，您从 2 开始，每次都进行平方。因此，您最多可以进行 O(logk) 平方来达到 k。由于 n = 2^k，因此，k = log(n) 因此 O(logk) 与 O(日志(日志))。