我正在尝试分析此算法的时间复杂性,但是我很难弄清并计算最终循环将执行多少次.我意识到第一个循环是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.
更多推荐
算法时间复杂度分析
发布评论