algorithm - 如果条件复杂度为 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
}

我正在尝试确定上述算法的大 O 复杂度。外层循环从1开始，运行到n，i中的计数器每次迭代加倍，因此这是一个log(n ) 行为。内部循环从 0 到 n 独立运行，具有 O(n) 行为。?

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

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)