如何在具有因变量的嵌套循环中查找操作数？

Question

我在尝试查找以下代码块中的操作总数时遇到困难：

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来写？

Answer 1

如你所说，外循环有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)

如何在具有因变量的嵌套循环中查找操作数？

How to find the number of operations in a nested loop with dependent variable?

algorithm

math

computer-science

analysis