算法时间复杂度分析 [英] Time complexity analysis of algorithm

问题描述

我正在尝试分析此算法的时间复杂性，但是我很难弄清并计算最终循环将执行多少次.我意识到第一个循环是log(n)，但是在那之后我似乎无法得出一个评估效果很好的总和.这是算法:

Hi I'm trying to analyze the time complexity of this algorithm but I'm having difficult unraveling and counting how many times the final loop will execute. I realize that the first loop is log(n) but after that I can't seem to get to a sum which evaluates well. Here is the algorithm:

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到 n

I cannot figure out how many times the loop k executes in general w.r.t to n

感谢您的帮助！

推荐答案

它是O(n).

1 + 2 + 4 + ... + 2 ^ N == 2 ^(N +1)-1.

1 + 2 + 4 + ... + 2^N == 2^(N + 1) - 1.

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

The last loop, for a specific j, executes j times.

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

And for a specific i, the inner 2 loops execute 1 + 2 + 4 + ... + i times, which is equal to about 2 * i.

所以总执行时间为1 * 2 + 2 * 2 + 4 * 2 + ... + N * 2，大约是4 * N.

So the total execution times is 1 * 2 + 2 * 2 + 4 * 2 + ... + N * 2, which is about 4 * N.

这篇关于算法时间复杂度分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！