algorithm - if 条件复杂度 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
}

我正在尝试确定上述算法的大复杂度。外循环从 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)