C++循环时间复杂度分析：求解一段除2循环的复杂度

首先直接给结论：这段代码的时间复杂度是O(log n)，绝对不是O(n/2)。

推导过程： #

这段代码的逻辑是反复将n除以2，直到n变为奇数为止。循环执行的次数，等于n中包含的2的因子的个数——比如：

• 当n=8（即2³），循环执行3次（8→4→2→1，此时1是奇数，停止）；
• 当n=16（2⁴），循环执行4次；
• 当n=6（2×3），循环仅执行1次；
• 若n本身是奇数，循环直接不执行。

在最坏情况下，n是2的整数次幂（比如n=2ᵏ），此时循环执行的次数就是k，而k=log₂n。大O表示法中，对数的底数可以忽略（因为不同底数的对数只是常数倍关系），所以时间复杂度记为O(log n)。

为什么不是O(n/2)？因为O(n/2)本质和O(n)是同一量级的复杂度，意味着循环次数和n成正比。但这段代码的循环次数最多只有log₂n次，比如当n=10⁶时，log₂n≈20，和n/2=5×10⁵的差距天差地别，显然不属于线性复杂度的范畴。

内容的提问来源于stack exchange，提问作者raghav Aggarwal