算法的時間複雜度分析

-1

嗨我想分析這種算法的時間複雜性，但我很難解開並計算最終循環將執行多少次。我意識到第一個循環是log（n），但在此之後，我似乎無法得到一個評估好的總和。下面是算法：算法的時間複雜度分析

for(int i = 1; i <= n; i = 2*i){ 
    for(int j = 1; j <= i; j = 2*j){ 
     for(int k = 0; k <= j; k++){ 
      // Some elementary operation here. 
     } 
    } 
}

我想不通環K的一般w.r.t多少次執行到ň

感謝您的幫助！

來源

2016-04-26 GenAsis

的可能的複製[如何找到時間的複雜性一個算法]（http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm） – 2016-04-26 11:32:22

它是O（n）。

1 + 2 + 4 + ... + 2^N == 2 ^（N + 1） - 1。

最後一個循環，對於特定的Ĵ，執行進行j次。

對於特定的i，內部2個循環執行1 + 2 + 4 + ... + i次，這等於大約2 * i。

所以總的執行時間爲1×2 + 2×2 + 4 * 2 + ... + N * 2，大約是4 * N.

來源

2016-04-26 11:48:52

算法的時間複雜度分析

回答

相關問題