给定代码的时间复杂度为何是O(logn)？如何计算其时间复杂度

首先给出待分析的代码片段：

int a = 0, i = N;
while (i > 0) 
{
a += i;
i /= 2;
}

计算时间复杂度的核心逻辑非常直接：先统计循环的实际执行次数，再乘以单次循环内的操作耗时即可。

• 先看单次循环的开销：循环内只有累加赋值、整数除法两个固定操作，都是和输入规模无关的常数级操作，耗时记为O(1)，因此总时间只和循环执行次数正相关。
• 再看循环的运行规则：循环变量i的初始值为N，每跑完一轮i就会被除以2，直到i小于等于0时循环直接终止。

我们可以代入具体数值直观感受循环次数的规律：

• 当N=16时，i的取值依次为16、8、4、2、1，下一次运算后i=0触发终止，循环一共执行5次
• 当N=32时，i的取值依次为32、16、8、4、2、1，下一次运算后i=0触发终止，循环一共执行6次
• 当N=1024时，循环累计执行11次就会终止

不难发现，循环执行次数k始终满足关系：2^k ≈ N，换算后可得k = log₂N。大O表示法本身不关注对数的具体底数——不同底数的对数之间只相差固定常数倍，按照大O记法的规则常数项可以直接忽略，因此最终的时间复杂度统一记为O(logN)。

实用判断技巧：只要看到循环内的控制变量每次是做乘2或者除以2的缩放变化，不用细算基本就能确定是logN级别的时间复杂度。

内容的提问来源于stack exchange，提问作者Bodhisattwa Basu