如何计算指定代码的时间复杂度？O(log2n)推导疑问求解

先澄清循环的笔误 #

你给出的循环for(i=0;i<n;i*=2)确实会无限运行：i初始值为0，每次乘以2后仍为0，只要n>0，i<n的判断永远为真，不可能退出。标注O(log₂n)的前提是循环初始值应为i=1，这是这类倍增循环的标准写法，属于代码书写或标注时的笔误。

O(log₂n)的推导过程 #

基于修正后的循环for(i=1;i<n;i*=2)推导如下：

• 第1次循环时，i取值为1 = 2⁰
• 第2次循环时，i取值为2 = 2¹
• 第3次循环时，i取值为4 = 2²
• 第k次循环时，i取值为2ᵏ⁻¹

循环终止的触发条件是i >= n，代入第k次的i取值可得：
2ᵏ⁻¹ >= n
对不等式两边同时取以2为底的对数：
k-1 >= log₂n
即循环最多执行log₂n + 1次，忽略常数项后，时间复杂度最终为O(log₂n)。

内容的提问来源于stack exchange，提问作者Satya Sridevi