algorithm - 与 log(n) 行为混淆

Question

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

我正在尝试确定上述算法的大 O 复杂度。外层循环从1开始，运行到n，i中的计数器每次迭代加倍，因此这是一个log(n ) 行为。内部循环从 0 运行到 n，具有 O(n) 行为。我很困惑它是否是 O(n * log(n)) ，顺序是否重要？此外，j 从 0 开始，而不是 1，所以这不可能是 O(n * log(n))？

Answer 1

在这种情况下，内循环独立于外循环。所以我们可以只计算外循环运行的次数，然后将它与内循环运行的次数相乘，这就是复杂度。

没有。外循环运行的次数为 log2(n)，因为该数字每次都乘以 2。

没有。内循环运行的次数总是 n。

因此，复杂度将为 O(nlog2(n))。