算法的时间复杂度分析

-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

算法的时间复杂度分析

回答

相关问题