我很难找到以下代码块中的操作总数:
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)