为什么这段代码的时间复杂度是 O(n) 而不是 O(log n)

Question

以下代码的时间复杂度为O(n log n) 我认为对于外循环 log n 但对于内循环 n。所以，O(n logn )

x = n 
while ( x > 0 ) { 
    y = n 
    while ( y > 0 ) { 
        y = y - 1 
    } 
    x = x / 2 
}

但是下面代码的时间复杂度是O(n)

x = n 
while ( x > 0 ) { 
    y = x 
    while ( y > 0 ) { 
        y = y - 1 
    } 
    x = x / 2 
}

为什么上面代码的时间复杂度是O(n)？

Answer 1

因为内循环的迭代次数减少了与x减少相同的比例。迭代的总数将始终约为 2n - 1（当 n 是 2 的幂时它是准确的，它对其他数字有一点偏差）。 Big-O 忽略了总和的系数和低阶分量，所以这是 O(n)。

例如，当n == 16时，外循环的第一次迭代执行内循环的16次迭代。第二次迭代执行 8，然后执行 4，依此类推。所以总数是16+8+4+2+1 == 31.

Why time complexicity of this code is O(n) instead of O(log n)