算法的时间复杂度分析

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在一般wrt到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.