含条件内层循环的for循环Big-O时间复杂度分析咨询

问题内容 #

我正尝试理解这段程序的时间复杂度及其原因，已自行做了一些分析笔记，但不确定理解是否正确。代码如下：

public static int countSteps(int n) {
    int pow = 2;                             // O(1)
    int steps = 0;                           // O(1)
    for (int i = 0; i < n; i++) {            // O(n)
        if (i == pow) {                      // O(1)
            pow *= 2;                        // O(1)
            for (int j = 0; j < n; j++) {    // O(n)
                steps++;                     // O(1)
            }
        }
        else {
            steps++;                         // O(1)
        }
    }
    return steps; // O(1)
}

疑问：每次触发if语句时，内层循环都会遍历n次，这会影响时间复杂度吗？还是整体复杂度仍为常数？

复杂度分析 #

整体时间复杂度是O(n log n)，内层循环确实会影响复杂度，绝非常数复杂度，具体拆解如下：

1. 外层循环基础操作：外层循环一共执行n次（i从0到n-1），大部分迭代里只执行1次steps++，这部分总操作数是O(n)。

2. 内层循环触发次数：内层循环的触发条件是i == pow，pow初始为2，每次触发后翻倍，所以触发时机是i=2、4、8、16……直到pow的值超过n。这个触发次数是O(log n)级别的——比如n=1024时，只会触发9次（i=2、4、…、512），因为下一个pow是1024，此时i已经到不了1024（外层循环i<1024）。

3. 总操作数计算：

   • 不触发内层循环的迭代次数是n - k（k为触发次数），对应操作数n -k；
   • 触发内层循环的k次迭代，每次要执行n次steps++加1次pow翻倍，对应操作数k*(n+1)；
   • 总操作数合并后为n + k*n，代入k=O(log n)，得到总操作数是O(n log n)。

简单说，虽然内层循环触发次数不多，但每次触发都会带来n次操作，叠加后就会让整体复杂度从O(n)升级为O(n log n)。

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