算法时间复杂度分析

Question

嗨，我正在尝试分析此算法的时间复杂性，但是我很难弄清并计算最终循环将执行多少次。我意识到第一个循环是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通常执行到 n次

谢谢你的帮助！

Answer 1

它开着）。

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

对于特定的j，最后一个循环执行j次。

对于特定的i，内部2个循环执行1 + 2 + 4 + … + i次，大约等于2 * i。

因此，总执行时间为1 * 2 + 2 * 2 + 4 * 2 + … + N * 2，大约为4 *N。