c++ - 以对数递增计算嵌套循环的时间复杂度

Question

我正在按照自己的进度在线学习。我正在解决一些示例，但我无法全神贯注于此:

while(i<n)
{
     for(int j=1; j<=i; j++)
         sum = sum + 1;
     i *=2;
}

我认为答案应该是 2^n 但我的 friend 说是 nlog(n)

谁能找到这个循环的大 O 并向我解释如何去做？

Answer 1

外循环将进入它的主体log2(n)次，因为 i呈指数增长，从而到达终点n快点，再快一点。例如，如果 n是1024 ，它只需要 10 次迭代，使用 n=65536 ，这是 16 次迭代。准确计数是log2(n) ，但就运行时复杂性而言，对数行为就足够了。所以这里的复杂度是 O(log(n)) .

内循环for(int j=1; j<=i; j++) , 每次求值的时候，都会跑到对应的i .可以看出，平均运行宽度约为 n / log2(n)。 , 自 i是1 , 2 , 4 , ... n与 log2(n)脚步。例如，如果 n是31 , i是1 , 2 , 4 , 8 , 16 , 总和为 31与 5脚步。所以取复杂度是允许的O(n/log(n))在这里。

那么总体复杂度是O(log(n)*n/log(n)) ，即 O(n) .