如何找到操作的数量在一个嵌套循环与因变量?



我很难找到以下代码块中的操作总数:

for(int i = 1; i <= n; i *= 2) {
for(int j = 1; j <= i; j *= 2) {
// What is the number of operations here, with respect to n?
}
}

我的想法是:在外部循环中有floor(log_2(n))操作,在内部循环中有log_2(i)操作。我不确定我的想法是否正确,以及我将如何从这里走下去……这个怎么能用n来表示呢?

正如您所说,外循环中有floor(log_2(n))操作。为了简单起见,我们说log_2(n)操作。对于大量的输入,这就不那么重要了。在内循环中,每种情况的操作次数将为log_2(i)
因此,从i=1到i=n,内环操作次数:

A = log_2(1)+1 (i = 1) + log_2(2)+1 (i = 2) + log_2(4)+1 (i = 4) + ... + log_2(n)+1 (i = n)
A =  1 + 2 + 3 + ... log_2(n) + 1
A = (log_2(n) + 2) * (log_2(n)+1) / 2 
A = ((log_2(n))^2 + 3*log_2(n) + 2)/2

总运算次数=(log(n)^2 + 3log(n) + 2)/2
简言之,算法的时间复杂度为:O(log(n)^2)

相关内容

  • 没有找到相关文章

最新更新