该while循环的时间复杂度是多少？求逐行推导步骤讲解

代码说明 #

原代码末尾多余的闭合大括号属于粘贴冗余，不影响核心循环逻辑，规整后的核心代码如下：

int i = n;
while (i > 0) {
    cot += 1;
    i = i / 2;
}

注：代码中cot为统计循环次数的计数器变量

逐行执行步骤解释 #

• int i = n;：初始化循环变量i，将输入值n赋值给i，该行仅在循环开始前执行1次。
• while (i > 0)：循环入口判断，每次执行循环体前先检查i的值是否大于0，满足条件则进入循环体，不满足则直接终止循环。
• cot += 1;：循环内的计数操作，每进入一次循环就执行1次累加。
• i = i / 2;：循环变量更新逻辑，每次循环末尾将i的值折半（整型计算会直接舍去小数部分，例如i=3时执行后i=1，i=1时执行后i=0），之后回到循环入口做下一次判断。

O(log n)时间复杂度推导 #

时间复杂度衡量的是代码核心操作的执行次数随输入规模n的增长趋势，这里只需要统计循环的总执行次数即可：
循环每次执行都会把i折半，我们可以通过枚举实际运行次数找规律：

• 当n=1时，i的变化路径为1→0，循环共执行1次
• 当n=2时，i的变化路径为2→1→0，循环共执行2次
• 当n=4时，i的变化路径为4→2→1→0，循环共执行3次
• 当n=8时，i的变化路径为8→4→2→1→0，循环共执行4次
• 当n=2^{k时，i需要经过k+1次折半才能降到0，满足2}k = n，换算后k = log₂n

如果n不是2的整数次幂，循环次数只会和比它大的最近2的整数次幂的循环次数差常数级，不会改变整体增长趋势。大O表示法会忽略对数的底数、常数项的影响，因此该循环的时间复杂度为O(log n)。

内容的提问来源于stack exchange，提问作者Reiy Roan