小编典典

算法时间复杂度分析

algorithm

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

谢谢你的帮助!


阅读 278

收藏
2020-07-28

共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。

2020-07-28