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