为什么这个代码的时间复杂度是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的幂时，它是准确的，对于其他数字它会偏离一点)。大0忽略了和的系数和低阶分量，所以是O(n)。

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