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

How do you find the asymptotic time complexity of these loops?

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

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

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

第一个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(log(logn)).

相同