算法时间复杂度分析

您好，我正在尝试分析该算法的时间复杂度，但我很难解开并计算最终循环将执行的次数。我意识到第一个循环是 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

谢谢你的帮助！

它开着）。

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。