求解指定双层for循环的时间复杂度Big-O（大O）表示

代码片段 #

for (int i = 1; i < n; i = i * 2)
{
    for (int j = 1; j < i; j++)
    {
        //const time
    }
}

复杂度分析步骤 #

• 外层循环逻辑：i从1开始每次翻倍，直到小于n，总执行次数为log₂n次，对应时间复杂度阶为O(log n)
• 内层循环逻辑：每次外层循环的i值确定后，j从1遍历到i-1，单次外层循环对应的内层执行次数为i-1次
• 总执行次数统计：将所有外层循环对应的内层次数累加，可得总次数为 0 + 1 + 3 + 7 + ... + (2^k -1)，其中k为log₂n向下取整的结果
• 等比数列求和简化：上述累加式的核心项等价于首项为1、公比为2的等比数列前log₂n项和，代入等比数列求和公式可得总执行次数核心为 2^log₂n -1 = n-1
• 最终时间复杂度：忽略常数项和低阶项后，整个循环结构的时间复杂度为O(n)

内容的提问来源于stack exchange，提问作者ammar albakri