如果复杂度为 O(n * log(n))中的条件

Question

s=0
for(i=1; i<n; i = i*2){ 
if (i<20)
for (j=0; j<n; j++)
{
s=s+i*j;
}
s=s+1
}

我正在尝试为上述算法建立 big-o 复杂性。外循环从1开始并运行到 n，每次迭代 i中的计数器加倍，因此这是一个log(n(行为。内部循环以O(n(行为从0到n独立运行。？

我不明白语句如何影响复杂性。您可能不想为我提供答案，但请朝着正确的方向引导，因为我根本不明白。

Answer 1

内部循环O(N)，但它只会运行 5 次， 即当i = 1, 2, 4, 8, 16

在前 5 次迭代之后，您的代码基本上变成了

for(i=32; i<n; i = i*2){ 
s=s+1
}

这是O(log(N))

所以总复杂度是：

O(5 * N + log(N)) = O(N)