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))。

這是我對代碼的理解。