j <= i条件的嵌套for循环的时间复杂度

Question

我对任务有这个问题。

确定嵌套循环的时间复杂性

for(int i=1; i<=n; i=2*i){ 
    for(int j=1; j<=i; i=2*j){ 
     stuff 
    } 
} 

据我所知，其中i和j是由2×递增，该复杂性将是沿LOG2的东西线（N）* LOG2（n）的，但内循环运行到我而不是n我完全失去了

我需要知道嵌套循环的复杂性和它如何解决的一步一步。

Answer 1

内循环运行log(i) + 1次（日志基数2）。

添加外环，总结上面的i = 1, 2, 4, ... n。

所以：(log(1) + 1) + (log(2) + 1) + (log(4) + 1) + ... + (log(n) + 1)

是：1 + 2 + 3 + ... + log(n)

使用算术级数的和是：(log(n) + 1) * (log(n) + 2)/2 = (log(n)*log(n) + 3log(n) + 2)/2 = O(log(n) * log(n))

Answer 2

假设N = 16例如，所以我将有值i = 1, 2, 4, 8, 16。所以：我基本上把log（n）的值看作log（16），即五次迭代。

现在为j的值，它取值为log(1) + log(2) + log(4) + log(8) + log(16)。它基本上等于每次迭代中的log（i）。

所以结合我们从上面两个语句得到的值，我们可以说上面代码的时间复杂度是O(log(n) * log(i))。

这是我对代码的理解。